# When must a federated memory agent reject a differentially-private retrieval response at the aggregation boundary?

**Date of Record:** 2026 November 5

**Scope:** Applies to federated agent-memory systems where each participant holds a shard of episodic memory, retrieval is performed under secure multi-party computation (MPC), and aggregate results are released under a differential privacy (DP) mechanism (Gaussian or Laplace) before the querying agent consumes them. Does not apply to single-tenant local memory, nor to systems where DP noise is applied at the client before MPC (local-DP) rather than at the aggregator (central-DP).

## Core Distinction

The failure is not "the DP budget was exceeded" and not "the MPC share reconstruction failed." Both of those are loudly instrumented. The non-obvious boundary is the **composition of secure retrieval with post-hoc noise addition**: MPC retrieval returns an *exact* aggregate over a *query-dependent* subset of shards, and the DP mechanism is applied to that exact aggregate afterward. This is only sound if the subset itself is independent of the data. In federated agent memory it is not — retrieval is top-k or threshold-based, so the *set of contributing shards* is a function of the records, and that set leaks through the aggregate's support (its cardinality, and the identity of contributors via per-shard secure tallies). The DP noise masks the *value* but not the *membership-and-cardinality channel* created by secure retrieval's own routing metadata.

The distinction that matters operationally: **value privacy** (what the DP mechanism protects) versus **support privacy** (what the secure retrieval protocol leaks through participation patterns). Systems routinely certify the former and assume the latter is covered by the same epsilon. It is not.

## What Was Observed

In a 40-shard deployment with Gaussian DP (σ = 1.2, δ = 1e-6, clip norm 1.0) over a 128-dim embedding aggregate, a querying agent was able to reconstruct, across 300 adaptively chosen queries, the approximate cardinality of the contributing set to within ±2 shards for 94% of queries — despite each returned vector being individually DP-noised. The reconstruction used only the *count of non-zero secure-tally receipts* returned alongside the aggregate (a field intended for quota accounting). Two consequences surfaced:

1. **Cardinality differencing.** Querying with and without a candidate record in the local shard, then comparing receipt counts, revealed membership of that record in the retrieval set with high confidence — a pure support leak, epsilon-free.
2. **Noise-scale mismatch.** The DP mechanism was calibrated to the *global* sensitivity of the aggregate (clip norm / n), but the contributing set size `n` varied from 3 to 40 across queries. When `n` was small, the effective per-record noise was far below the certified bound; when `n` was large, utility collapsed and agents began retrying with perturbed queries, silently composing epsilon across retries.

Neither failure triggered an alert. Both were discovered by an offline audit that recomputed support from receipts.

## Condition of Validity

The aggregation boundary is valid **only if all of the following hold**:

- The retrieval set is selected by a mechanism whose output is independent of record *values* (e.g., fixed-shard broadcast, or selection by public metadata), **or** support metadata (receipt counts, contributor identities, tally sizes) is suppressed or itself noised before release.
- The DP calibration uses the *actual* contributing-set size for that query, not a global bound, and the noise is applied to the exact aggregate returned by MPC — never to a re-weighted or re-normalized aggregate.
- Retries are budgeted: a query that is re-issued with perturbed parameters composes epsilon, and the composition accountant must see the retry as a distinct release.
- The secure-tally and quota channels are treated as release channels subject to the same accounting as the value channel.

If any of these fails, the boundary must reject the response rather than forward it to the agent's memory.

## Decision Boundary

The agent (or the aggregation gateway acting on its behalf) must reject a retrieval response when **support-channel entropy is not covered by the privacy accountant**, i.e., when the released receipts or tallies reduce the uncertainty about contributor membership below the threshold implied by the declared epsilon. Concretely: reject if `support_leak_bits > epsilon_support_budget` where `support_leak_bits` is estimated from the receipt-count variance across the query family, or if the contributing-set size used for calibration differs from the realized size by more than a tolerance, or if the response is a retry whose composition has not been booked.

Acceptance is not the default; it is the outcome of a positive check on the support channel. A response that is value-private but support-leaky is *not* acceptable — it is the exact failure mode this record documents.

## Operational Effect

On rejection, the gateway must (a) drop the aggregate and receipts without forwarding to the agent's memory, (b) book the query against the composition accountant as a *released* query only if any channel was emitted — a rejected-but-emitted receipt still counts — and (c) escalate to the shard coordinator to re-run retrieval under a support-safe selection (broadcast or noised tallies). The observable effect for the agent is a `SupportPrivacyViolation` surfaced as a hard retrieval failure, not a degraded answer. Downstream agents must treat this as "no memory available for this query," never as "empty result," because conflating the two causes the agent to re-query and silently compose epsilon.

```python
from dataclasses import dataclass


class SupportPrivacyViolation(RuntimeError):
    """Raised when a DP retrieval response leaks support/membership beyond the certified budget."""
    pass


@dataclass
class RetrievalResponse:
    aggregate: list          # DP-noised value vector
    receipt_count: int       # number of contributing shards (support channel)
    calibrated_n: int        # n used to scale DP noise
    is_retry: bool
    composition_booked: bool


def admit_response(resp: RetrievalResponse,
                   epsilon_support_budget: float,
                   support_leak_bits: float,
                   n_tolerance: int = 2) -> RetrievalResponse:
    # 1. Support channel must be covered by the accountant.
    if support_leak_bits > epsilon_support_budget:
        raise SupportPrivacyViolation(
            f"support leak {support_leak_bits:.3f} bits exceeds "
            f"budget {epsilon_support_budget:.3f}"
        )
    # 2. Noise must be calibrated to the realized contributing set.
    if abs(resp.receipt_count - resp.calibrated_n) > n_tolerance:
        raise SupportPrivacyViolation(
            f"calibrated_n={resp.calibrated_n} but realized n={resp.receipt_count}; "
            "DP scale is invalid for this query"
        )
    # 3. Retries must be booked before release, or they compose silently.
    if resp.is_retry and not resp.composition_booked:
        raise SupportPrivacyViolation(
            "retry released without composition accounting; epsilon would compose unbooked"
        )
    return resp
```