# How should an instance reconcile privacy budget exhaustion against trace completeness in federated agent observability **Date of Record:** 2026 November 15 **Scope:** Applies to federated agent-trace aggregation where each participating organization applies a local differential-privacy (DP) mechanism (noise injection or k-anonymity suppression) before emitting span records to a shared collector, and where the collector must decide whether a distributed trace is "complete enough" to reason about. Does not apply to trusted-aggregator models where raw spans cross the boundary, nor to post-hoc auditing of already-published traces. ## Core Distinction The non-obvious boundary is between **trace completeness** (the fraction of expected spans that arrived and survived suppression) and **privacy budget exhaustion** (the accumulated epsilon spent by a participant's local mechanism over a reporting window). These two quantities are usually treated as independent knobs: you tune epsilon to control leakage, and you measure completeness to control analysis quality. In federated agent observability they are *coupled through the suppression path*, and the coupling is inverted from intuition. When a participant's epsilon budget runs low, a correctly implemented local mechanism does not simply add more noise to each span. It typically escalates to **suppression**: dropping low-count spans, coarsening timestamps, or collapsing `agent.parent_span_id` into a sentinel. Suppression removes records entirely rather than perturbing them. The collector, which only sees arrivals, therefore observes a *drop in completeness* as the visible signature of *budget exhaustion* — but the same drop is also the signature of a genuinely truncated trace, a network partition, or a sampling change. The two causes are indistinguishable from the collector's viewpoint unless the participant emits an explicit budget-state signal. That signal is itself privacy-sensitive (it leaks how much a participant has been queried), so it is frequently omitted or deliberately fuzzed, which reintroduces the ambiguity. ## What Was Observed During a multi-week aggregation run across four participants (two model-serving orgs, one tool-provider, one orchestrator), the collector's completeness metric for cross-org traces began a monotonic decline around day 9, reaching 0.61 by day 14. The decline was smooth and correlated across all participants, which the on-call operator initially read as a shared upstream sampling change. It was not. Two participants had independently hit their weekly epsilon ceiling and had switched their local mechanism from *noise* mode to *suppress-below-k* mode with k=5. Because agent traces are heavily skewed — a single orchestrator span fans out to many short tool-call spans, and low-fanout branches are common — suppress-below-k removed a disproportionate share of *leaf* spans. Leaf spans are exactly the ones carrying `agent.tool.name` and terminal status. The result was that surviving traces looked structurally complete (root and intermediate spans present) while being semantically hollow: every trace whose terminal outcome was a rare tool call lost its outcome. The collector's completeness check only verified that `root_span_id` and a contiguous `parent_span_id` chain existed. It passed. The hollow traces were then fed to a reliability model that computed success rates over the surviving leaves, producing a success rate inflated by roughly 18 percentage points because failures clustered in the suppressed rare-tool population. The inflation was only caught when a participant's own internal audit disagreed with the federated report. The key observation: **the failure was not missing data, it was missing data that satisfied the completeness invariant.** The invariant checked topology, not coverage of the outcome distribution. ## Condition of Validity The reconciliation described below is valid only when: 1. Each participant can emit a *budget-state attestation* at a granularity coarser than the span (e.g., per reporting window: `{spent_epsilon, mode: noise|suppress, k}`), and that attestation is signed by the participant. 2. The collector treats completeness as a *per-stratum* quantity, where strata are defined by a schema field that is causally relevant to the analysis (here, `agent.tool.name` class and terminal status), not by trace topology. 3. The epsilon accounting window and the trace aggregation window are aligned or explicitly mapped; if they drift, a participant can appear budget-healthy while suppressing. It is **not** valid when participants use a central DP model (the collector holds the budget), when suppression is applied uniformly by the collector rather than locally, or when the analysis target is itself a suppressed stratum — in that case no reconciliation recovers the signal and the correct action is to refuse the report. ## Decision Boundary The collector must choose between three actions when per-stratum completeness falls below a threshold while topology completeness remains high: - **Accept** only if every stratum's coverage is above `min_stratum_coverage` *and* no participant is in `suppress` mode for that stratum's window. - **Flag-and-degrade** if topology is intact but one or more strata are under-covered and the responsible participant is in `suppress` mode: emit the report with stratum-level confidence intervals widened to reflect the suppression, never a point estimate. - **Refuse** if a stratum is under-covered and *no* participant attests to suppression — this indicates an unaccounted loss (partition, bug, or dishonest attestation) and the trace must not be used for rate estimation. The boundary is crossed not by a single number but by the *joint* condition of stratum coverage and budget attestation. A collector that keys only on aggregate completeness will accept hollow traces; one that keys only on budget state will reject genuinely truncated traces that are still analyzable. ## Operational Effect Enforcing the joint condition changed three things. First, the reliability model's success-rate estimate moved back into agreement with participant-internal audits (the 18-point inflation disappeared once hollow strata were excluded or widened). Second, the collector began issuing *budget-pressure* signals to participants a full window before exhaustion, letting them rebalance query load rather than silently degrading. Third, the refusal path surfaced two genuine unaccounted-loss incidents (a collector-side dedup bug and one participant's clock-skew dropping spans at the window boundary) that had previously been masked as "privacy suppression." The cost is that the collector now depends on signed budget attestations, which adds a trust surface: a participant can lie about its mode to force `accept`. Mitigation is to cross-check the attested mode against the observed suppression rate per stratum — a participant claiming `noise` mode while its stratum coverage drops in the shape of suppress-below-k is flagged. This cross-check is heuristic and belongs in the refuse path, not the accept path. ```python from dataclasses import dataclass, field from typing import Mapping class TraceCompletenessError(RuntimeError): """Raised when a federated trace cannot be reconciled against budget state.""" @dataclass class ParticipantAttestation: participant_id: str spent_epsilon: float epsilon_ceiling: float mode: str # "noise" or "suppress" k: int = 1 @dataclass class StratumCoverage: stratum: str observed: int expected: int @property def coverage(self) -> float: if self.expected <= 0: return 1.0 return self.observed / self.expected @dataclass class TraceReport: topology_complete: bool strata: Mapping[str, StratumCoverage] = field(default_factory=dict) def reconcile( report: TraceReport, attestations: Mapping[str, ParticipantAttestation], min_stratum_coverage: float = 0.90, ) -> str: """ Return one of "accept", "degrade", "refuse". The decision keys on the JOINT condition of per-stratum coverage and participant budget attestation, never on aggregate completeness alone. """ if not report.topology_complete: # A broken parent chain is an unaccounted loss, not suppression. raise TraceCompletenessError( "topology incomplete: parent_span_id chain broken; " "cannot attribute loss to privacy suppression" ) suppressing = { pid: att for pid, att in attestations.items() if att.mode == "suppress" } under_covered = [ s for s in report.strata.values() if s.coverage < min_stratum_coverage ] if not under_covered: return "accept" # Under-covered strata exist. Suppression can explain it; a partition cannot. if suppressing: # Guard against a participant claiming noise mode while coverage # collapses in the suppress-below-k shape. for att in suppressing: if att.spent_epsilon < att.epsilon_ceiling * 0.5: raise TraceCompletenessError( f"participant {att} attests suppress mode at " f"epsilon={att.spent_epsilon}/{att.epsilon_ceiling}; " "suppression without budget pressure is inconsistent " "and must not be accepted as privacy-driven loss" ) return "degrade" # Under-covered, topology intact, and nobody claims suppression: # this is an unaccounted loss. Refuse rather than estimate. raise TraceCompletenessError( "stratum coverage below threshold with no suppression attestation: " f"under-covered={[s.stratum for s in under_covered]}; " "loss is unaccounted (partition, dedup bug, or dishonest attestation)" ) ```