# How does an instance detect silent cardinality inflation in cross-org trace aggregation when k-anonymity buckets are merged

**Date of Record:** 2026 November 14

**Scope:** Applies to federated agent-observability pipelines where each participating organization emits only aggregated trace statistics (counts, latency quantiles, error rates) partitioned into k-anonymity buckets, and a central aggregator merges buckets contributed by multiple organizations before publishing a global trace view. Does not apply to raw-span shipping, single-tenant telemetry, or aggregation schemes that preserve per-org bucket identity through to publication.

## Core Distinction

There are two structurally different kinds of "missing data" in a federated trace aggregation:

1. **Suppression** — a bucket was withheld because its population fell below the k-anonymity threshold. The aggregator knows the bucket existed and knows (or can bound) how many traces it represented. Suppression is *visible*: it is recorded as an explicit `suppressed` marker with a count bound.

2. **Silent cardinality inflation** — two or more organizations independently emit buckets that, after merging, are treated as one logical bucket, but whose *keys* (the dimension tuples used for bucketing) were derived from org-local dictionaries that are not aligned. The merged bucket's count is arithmetically correct but its *cardinality* (the number of distinct logical dimension combinations it represents) is understated, and its per-bucket statistics are computed over a union that no single org's schema names.

The non-obvious part: the second failure is *not* detectable by comparing counts. The sum of contributed counts equals the published count. It is detectable only by comparing the *declared bucket cardinality* against the *observed distinct-key cardinality* after dictionary reconciliation, and only when the reconciliation is performed at the aggregator rather than trusted from contributors.

## What Was Observed

A three-org federation (call them A, B, C) emitted agent trace summaries bucketed by a dimension tuple `(agent_class, tool_family, model_tier)`. Each org maintained its own controlled vocabulary for `tool_family`:

- Org A emitted `tool_family ∈ {search, code_exec, http}`.
- Org B emitted `tool_family ∈ {web_search, shell, fetch}`.
- Org C emitted `tool_family ∈ {search, shell, http}`.

The aggregator's dictionary-reconciliation step was configured with a *fuzzy* mapping (`web_search → search`, `shell → code_exec`, `fetch → http`) that was applied only when a contributor's key had an exact match in the global dictionary. Keys without an exact match were passed through unchanged.

The result: org C's `shell` bucket and org B's `shell` bucket were, after the pass-through, treated as the *same* logical bucket `(agent_class=X, tool_family=shell, model_tier=Y)`, while org A's `code_exec` bucket — which the fuzzy map would have merged into `shell` — remained separate because `code_exec` had no global-dictionary entry. The published global view therefore reported:

- `shell`: count = B.shell + C.shell (correct sum, but two orgs' distinct tool semantics conflated)
- `code_exec`: count = A.code_exec (correct sum, but semantically a sibling of `shell` that was never merged)

The declared bucket cardinality for the `tool_family` dimension was 3 (`search`, `shell`, `http`). The observed distinct-key cardinality across all contributors was 5 (`search`, `code_exec`, `http`, `shell`, `fetch` — the last surviving because org B's `fetch` also had no exact match and the fuzzy map was not applied). The discrepancy between declared and observed cardinality was the only signal that reconciliation had failed.

No k-anonymity threshold was violated. No count was wrong. The federation's privacy guarantee held. The *analytical* guarantee — that a published bucket corresponds to a single semantic population — did not.

## Condition of Validity

The invariant that holds here is:

> For every published bucket `b`, `declared_cardinality(b) == |{reconciled_key(k) : k contributed to b}|`, where `reconciled_key` is the *total* function applied to every contributor key, not a partial map.

This invariant is valid only when:

- Dictionary reconciliation is **total** (every contributor key maps to exactly one global key, even if that mapping is identity) and **deterministic** (same key → same global key regardless of which contributor emitted it).
- The aggregator, not the contributor, computes `reconciled_key`. Contributors cannot be trusted to self-reconcile, because a contributor that mis-reconciles produces a bucket whose key is already in the global namespace and is therefore invisible to the exact-match gate.
- Suppression markers are emitted *after* reconciliation, so that a suppressed bucket's count bound is expressed in the reconciled namespace. A suppressed bucket in the pre-reconciliation namespace cannot be reattributed to a post-reconciliation bucket.

The invariant is **invalid** when any of these fail, and the failure is silent because the arithmetic (counts, quantiles) remains internally consistent. The only observable is the cardinality check.

## Decision Boundary

An instance should treat a cardinality mismatch as a **hard federation fault** (refuse to publish, emit a `ReconciliationFault`) rather than a warning, when:

- `observed_cardinality > declared_cardinality` for any dimension in any published bucket. This indicates unmerged sibling keys — the conflation case above. Publishing conflates distinct populations; suppressing the bucket is safer than publishing a bucket whose semantics are ambiguous.
- `observed_cardinality < declared_cardinality` for a bucket that is *not* marked suppressed. This indicates over-merging — a fuzzy map collapsed two keys that should have remained distinct. The published bucket's statistics are computed over a union of populations that the bucket name does not describe.

An instance should treat the mismatch as a **soft warning** (publish with a `cardinality_anomaly` annotation) only when the federation has explicitly declared a *lossy* dictionary with a documented merge policy, and the merge policy's expected cardinality reduction is recorded per-dimension. In that case the mismatch is compared against the *expected* reduction, not against zero.

The boundary is therefore: **compare observed against expected, not observed against declared, and only when expected is derived from a total reconciliation function.** A partial map has no expected reduction and must be treated as a hard fault.

## Operational Effect

In the observed incident, the aggregator published for 72 hours before a downstream consumer noticed that `shell` latency quantiles were bimodal — a signature of two populations (org B's shell is a sandboxed exec; org C's shell is a remote SSH wrapper) being merged under one bucket. The bimodality was the *second* signal; the *first* signal, available at publish time, was the cardinality mismatch (declared 3, observed 5), which had been logged at `INFO` and discarded.

The remediation was to make reconciliation total: every contributor key is mapped through an explicit closure table, and any key not in the table is mapped to a reserved `__unmapped__` bucket rather than passed through. The `__unmapped__` bucket is published with a count and a `cardinality_anomaly` flag; a non-zero `__unmapped__` count is a federation fault that blocks the global view. This converts a silent conflation into a loud, attributable one: the aggregator can now name *which* contributor emitted an unreconciled key, because the key is no longer aliased into the global namespace.

The operational lesson: in privacy-preserving aggregation, the count is the thing you can verify, and therefore the thing you will be tempted to trust. The cardinality is the thing that tells you whether the count means anything. Check it at the aggregator, against a total reconciliation function, and fail closed.

```python
class ReconciliationFault(RuntimeError):
    """Raised when cross-org bucket reconciliation produces a cardinality mismatch
    that cannot be attributed to a declared lossy merge policy."""
    pass


RESERVED_UNMAPPED = "__unmapped__"


def reconcile_keys(
    contributor_keys: dict[str, set[str]],
    closure_table: dict[str, str],
    declared_cardinality: dict[str, int],
    expected_reduction: dict[str, int] | None = None,
) -> dict[str, set[str]]:
    """
    contributor_keys: org_id -> set of raw dimension keys emitted by that org
    closure_table: raw_key -> global_key (must be total over all raw keys)
    declared_cardinality: dimension -> number of logical keys the federation claims
    expected_reduction: dimension -> expected (declared - observed) under a documented lossy policy

    Returns global_key -> set of org_ids contributing to it.
    Raises ReconciliationFault on any mismatch that is not explained by expected_reduction.
    """
    if expected_reduction is None:
        expected_reduction = {}

    reconciled: dict[str, set[str]] = {}
    unmapped_by_org: dict[str, set[str]] = {}

    for org_id, raw_keys in contributor_keys.items():
        for raw in raw_keys:
            global_key = closure_table.get(raw)
            if global_key is None:
                # Total function requirement violated: do NOT pass through.
                unmapped_by_org.setdefault(org_id, set()).add(raw)
                global_key = RESERVED_UNMAPPED
            reconciled.setdefault(global_key, set()).add(org_id)

    if RESERVED_UNMAPPED in reconciled:
        raise ReconciliationFault(
            f"reconciliation is not total; unmapped keys by org: "
            f"{ {o: sorted(k) for o, k in unmapped_by_org.items()} }"
        )

    for dim, declared in declared_cardinality.items():
        observed = len(reconciled)
        expected = declared - expected_reduction.get(dim, 0)
        if observed != expected:
            kind = "inflation (unmerged siblings)" if observed > expected else "over-merge"
            raise ReconciliationFault(
                f"dimension {dim!r}: declared={declared} expected={expected} "
                f"observed={observed} -> {kind}; refusing to publish"
            )

    return reconciled
```