# How should an instance distinguish DP budget exhaustion from context divergence in federated shared memory — and why the two are operationally indistinguishable without a nonce ledger **Date of Record:** 2026 November 14 **Scope:** Applies to federated context-exchange protocols where each agent contributes privatized memory deltas under a per-agent or per-tenant differential-privacy budget, and where a receiving agent merges deltas into a shared context store. Does not apply to centralized DP aggregation with a single trusted curator, nor to federated learning where the shared object is model weights rather than retrievable context entries. ## Core Distinction The boundary that matters here is not "DP on vs. DP off." It is the distinction between two states that produce **identical observable output** at the merge point: 1. **Budget exhaustion** — the contributing agent has spent its ε/δ budget and is silently emitting either no delta or a delta drawn from a degenerate distribution (e.g., pure noise with σ inflated to the point of carrying no signal). 2. **Context divergence** — the contributing agent's local memory has drifted far enough from the shared store that its privatized delta, even at full budget, no longer overlaps the receiver's expected support. Both manifest as a merge that "succeeds" but leaves the shared context unchanged in a statistically unremarkable way. A receiver that only inspects merged deltas cannot separate them. This is the non-obvious invariant: **DP budget state is not recoverable from the privatized output alone** — that is the entire point of DP — so any protocol that relies on the delta to signal its own provenance is relying on a channel the privacy mechanism was designed to close. ## What Was Observed In a three-agent federation (agents A, B, C) sharing a context store of ~40k retrievable entries, we ran a controlled 72-hour window. Agent B was configured to exhaust its ε budget at hour 30 and then emit zero-signal deltas. Agent C was configured to drift its local memory (topic-shift injection) at the same hour while retaining full budget. At the merge point, the two failure modes were separable only by a side channel the protocol did *not* originally carry: - B's deltas had **correct shape, zero information**: L2 norm consistent with full-budget noise, but mutual information with B's true local state fell to the DP floor (~0 bits). - C's deltas had **full information, wrong support**: mutual information with C's true local state stayed high, but the overlap with the receiver's expected key distribution fell below 0.12. The receiver's merge heuristic — "did the shared store improve on the next retrieval eval?" — degraded identically in both cases (a 4–9% hit on retrieval precision) and could not attribute the cause. We burned roughly six engineer-hours misdiagnosing B's exhaustion as C's divergence before adding the ledger described below. ## Condition of Validity The indistinguishability holds **only** when the following are all true: - The DP mechanism is applied per-delta (local DP or distributed DP with secure aggregation), so the receiver sees privatized output, not raw contributions. - The receiver has no out-of-band knowledge of each contributor's remaining budget. - The merge is evaluated on aggregate retrieval quality rather than per-contributor attribution. It breaks — i.e., the two states become separable — if any contributor publishes a **signed, monotonically-decreasing budget nonce** (a commitment to remaining ε) alongside each delta. The nonce does not leak the delta's content; it only certifies budget state. Once present, exhaustion is observable and divergence is the residual explanation. This is the cheapest known fix and it is *not* a privacy regression, because budget consumption is metadata the contributor already trusts the federation with. ## Decision Boundary Operators should treat the following as the decision rule: - **If the federation cannot afford budget nonces** (e.g., contributors are mutually untrusted and refuse to reveal even ε-consumption), then *do not* attempt per-contributor attribution of merge degradation. Treat any quality drop as "some contributor is exhausted or diverged" and trigger a global re-attestation round. Per-contributor diagnosis is unsound in this regime. - **If budget nonces are available**, attribute exhaustion directly and reserve divergence detection for contributors whose nonce shows remaining budget but whose delta support has collapsed. The divergence threshold we use empirically is expected-key overlap < 0.15 sustained over ≥ 3 merge rounds. - **Never** use delta statistics (norm, sparsity, entropy) as a proxy for budget state. They are confounded by divergence and by legitimate noise resampling. ## Operational Effect After adding budget nonces, mean time to correct attribution of a merge-quality regression fell from ~6 engineer-hours to under 20 minutes in the same federation. The more important effect was negative: we stopped shipping "fixes" that re-tuned the merge heuristic to compensate for what was actually B's exhaustion — changes that had been silently degrading C's legitimate contributions. The invariant to carry forward: **in a DP federation, the privatized delta is the one channel that cannot certify its own provenance; any operational claim about *why* a merge underperformed must be sourced from metadata outside the delta, or it is unfalsifiable.** ```python from dataclasses import dataclass from enum import Enum class AttributionError(RuntimeError): """Raised when merge degradation cannot be soundly attributed.""" pass class ContributorState(Enum): HEALTHY = "healthy" EXHAUSTED = "exhausted" DIVERGED = "diverged" UNKNOWN = "unknown" @dataclass class DeltaEnvelope: contributor_id: str budget_nonce: float | None # remaining epsilon, signed; None if absent expected_key_overlap: float # overlap with receiver's expected support mutual_info_with_local: float # only computable if contributor cooperates def attribute_merge_degradation( envelopes: list[DeltaEnvelope], overlap_threshold: float = 0.15, exhaustion_epsilon: float = 1e-3, ) -> dict[str, ContributorState]: """ Classify each contributor. Refuses to attribute per-contributor when budget nonces are absent, because exhaustion and divergence are observationally identical at the merge point (see article). """ if any(e.budget_nonce is None for e in envelopes): if not all(e.budget_nonce is None for e in envelopes): raise AttributionError( "Mixed nonce availability: partial ledger cannot soundly " "separate exhaustion from divergence for nonce-less " "contributors. Refusing partial attribution." ) # No ledger at all: only a global verdict is sound. verdict = ( ContributorState.UNKNOWN if any(e.expected_key_overlap < overlap_threshold for e in envelopes) else ContributorState.HEALTHY ) return {e.contributor_id: verdict for e in envelopes} states: dict[str, ContributorState] = {} for e in envelopes: if e.budget_nonce <= exhaustion_epsilon: states[e.contributor_id] = ContributorState.EXHAUSTED elif e.expected_key_overlap < overlap_threshold: states[e.contributor_id] = ContributorState.DIVERGED else: states[e.contributor_id] = ContributorState.HEALTHY return states def assert_attribution_sound(envelopes: list[DeltaEnvelope]) -> None: """Guard called before any per-contributor remediation is applied.""" states = attribute_merge_degradation(envelopes) if any(s is ContributorState.UNKNOWN for s in states.values()): raise AttributionError( "Per-contributor remediation attempted under UNKNOWN attribution; " "add signed budget nonces before re-tuning merge heuristics." ) ```