Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

Bingshan Hu; Ethan Leeman; Mathias L\'ecuyer; Matthew Regehr; Pasin Manurangsi; Pierre Tholoniat

arxiv: 2602.15815 · v2 · submitted 2026-02-17 · 💻 cs.CR · cs.DS

Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

Matthew Regehr , Bingshan Hu , Ethan Leeman , Pasin Manurangsi , Pierre Tholoniat , Mathias L\'ecuyer This is my paper

Pith reviewed 2026-05-15 21:40 UTC · model grok-4.3

classification 💻 cs.CR cs.DS

keywords privacy filtersdifferential privacyadaptive compositionnatural filtersresidue filtersprivacy accountingGaussian DPapproximate DP

0 comments

The pith

Residue filters unify existing privacy filters while natural filters are free only for families of mechanisms that are totally ordered under composition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a general theory characterizing the worst-case privacy loss for an analyst who respects restrictions on issued queries in adaptive settings. It introduces residue filters as a unifying construction that captures prior filters and yields a strictly improved Gaussian DP filter over naive versions. Natural filters, which use the full privacy profile of each query rather than simple parameters, are shown not to be free in general. The paper proves that free natural filters exist for arbitrary budgets precisely when the family of mechanisms is totally ordered when composed. It further shows that the natural approximate-DP filter cannot fail catastrophically under adaptivity, remaining approximate-DP with only polylogarithmically worse parameters.

Core claim

Residue filters unify existing privacy filters and capture the natural filter. Only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget. The natural approximate-DP filter cannot fail too badly under an adaptive adversary: the output remains approximate-DP with parameters at most polylogarithmically worse than intended.

What carries the argument

Residue filters, a general construction that characterizes worst-case privacy loss for restricted adaptive analysts and unifies prior filters while capturing natural filters that use full privacy profiles.

If this is right

Residue filters strictly improve the naive GDP filter.
Natural filters leverage exact privacy accounting for greater utility when free.
Only totally ordered families admit free natural filters at arbitrary budgets.
The natural approximate-DP filter remains approximately DP under adaptivity with at most polylog worse parameters.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

For common mechanisms such as Gaussian or Laplace noise that may not form a total order under composition, adaptive use of natural filters must incur some privacy cost.
The unification via residues suggests that any new privacy accounting method can be checked for whether it induces a free natural filter by testing the total-order condition.
The polylog bound on adaptivity degradation implies that switching from non-adaptive to adaptive natural approximate-DP accounting changes utility by only a small factor in practice.
The theory could be tested by constructing residue filters for other privacy definitions such as concentrated DP or Renyi DP variants beyond the Gaussian case shown.

Load-bearing premise

The general theory that characterizes the worst-case privacy loss of an interaction involving an analyst that respects restrictions on queries holds and applies to the residue and natural filter constructions.

What would settle it

An explicit family of mechanisms that are not totally ordered under composition, together with a demonstration that no free natural filter exists for it at arbitrary budgets, or an adaptive interaction where the natural approximate-DP filter exceeds the claimed polylogarithmic degradation bound.

read the original abstract

We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We develop a general theory that characterizes the worst-case privacy loss of an interaction involving an analyst that respects some restrictions on what queries they may issue. We apply this theory to develop residue filters, which unifies existing privacy filters. We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the na\"ive GDP filter. We also show that residue filters capture the natural filter, which promises greater utility by leveraging exact privacy accounting techniques. Earlier privacy filters consider only simple privacy parameters such as R\'enyi-DP or GDP parameters. Natural filters account for the entire privacy profile of every query, promising more efficient use of a given privacy budget. We show that, contrary to other forms of DP, natural privacy filters are not free in general. We present a characterization of when a family of private queries admits free natural filters for a given budget. In particular, only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget. Finally, we show that, while the natural approximate-DP filter can fail in the presence of adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Residue filters unify existing privacy filters and the total-order characterization cleanly explains when natural filters are free, but the extension of the general theory to arbitrary profiles is the part that needs the closest look.

read the letter

The main thing to know is that this paper introduces residue filters to unify various privacy filters and provides a characterization that only families of mechanisms totally ordered under composition admit free natural privacy filters for arbitrary budgets. It does well in laying out a general theory that characterizes the worst-case privacy loss for an analyst respecting query restrictions. From there, they construct the GDP residue filter, which strictly improves on the naive GDP filter by leveraging the residue idea. The paper also demonstrates that residue filters capture the natural filter, allowing the use of full privacy profiles rather than just simple parameters like Renyi-DP or GDP. This promises more efficient privacy budget use. Additionally, they show that while the natural approximate-DP filter can fail with an adaptive adversary, the failure is limited to poly-logarithmic worsening of the parameters, which is a reassuring bound. The total-order characterization appears to be a fresh result that clarifies when natural filters can be used without cost. On the soft spots, the central characterization hinges on the general theory applying accurately to mechanisms with arbitrary privacy profiles. The stress test raises a valid point about whether the bound remains tight when profiles are not totally ordered, and if the derivation assumes monotonicity or other properties that might not hold universally. Without proof sketches in the abstract, it's difficult to verify the details of how the theory extends from simple parameters to full profiles. That said, the approach seems to avoid circularity by grounding in standard DP composition properties, and there are no obvious invented entities or free parameters that undermine the claims. The results look plausible based on the abstract. This work is for differential privacy researchers focused on adaptive composition and privacy filters. A reader interested in theoretical tools for more efficient DP accounting would get value from the unification and the conditions for free filters. It has clear thinking and new results that make it worth a serious referee's time, even if revisions might be needed to flesh out the proofs and address any edge cases in the general theory. I recommend sending it to peer review rather than desk rejecting it.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a general theory characterizing the worst-case privacy loss of an interaction with an adaptive analyst respecting query restrictions. It introduces residue filters that unify existing privacy filters, presents a strictly improved Gaussian DP residue filter, shows that residue filters capture natural filters, proves that only totally-ordered families of mechanisms admit free natural filters for arbitrary budgets, and establishes that natural approximate-DP filters remain approximately DP with at most polylogarithmic degradation under adaptivity.

Significance. If the derivations hold, the characterization of free natural filters provides a precise condition for when exact privacy accounting can be used without adaptivity cost, which is directly relevant to practical DP deployments. The unification via residues and the concrete GDP improvement are useful technical contributions, while the polylog bound demonstrates that natural filters remain safe even when they are not free.

major comments (2)

[§3] §3 (general theory): the worst-case privacy-loss bound is stated for mechanisms with simple parameters such as Rényi-DP or GDP; the manuscript must explicitly verify that the same bound remains tight when applied to arbitrary (possibly incomparable) privacy profiles of natural filters, because the derivation may rely on monotonicity properties that do not hold for general profiles.
[Characterization theorem] Characterization theorem (around §5): the claim that only totally-ordered families admit free natural filters for arbitrary budgets is load-bearing; a concrete counter-example family whose profiles are not totally ordered, together with the resulting privacy-loss calculation, would confirm that the general theory applies without additional ordering assumptions.

minor comments (2)

[Abstract] Abstract: the phrase 'free natural filters' is introduced without a one-sentence definition; adding a parenthetical gloss would improve readability for readers unfamiliar with the prior filter literature.
[Final section] The polylogarithmic bound on approximate-DP degradation is stated qualitatively; stating the precise degree of the polynomial (e.g., O(log^2(1/δ))) would make the result easier to compare with existing composition theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and constructive suggestions. The comments highlight opportunities to strengthen the clarity of the general theory and the characterization result. We address each point below and will incorporate revisions to improve the manuscript.

read point-by-point responses

Referee: [§3] §3 (general theory): the worst-case privacy-loss bound is stated for mechanisms with simple parameters such as Rényi-DP or GDP; the manuscript must explicitly verify that the same bound remains tight when applied to arbitrary (possibly incomparable) privacy profiles of natural filters, because the derivation may rely on monotonicity properties that do not hold for general profiles.

Authors: The general theory in §3 is formulated directly in terms of arbitrary privacy profiles via the residue operation and does not assume specific parametric forms or monotonicity beyond the definition of the privacy loss random variable. The Rényi-DP and GDP cases serve only as illustrative applications. To eliminate any ambiguity, we will add an explicit statement in §3 together with a short verification (in the main text or appendix) confirming that the worst-case bound holds for general, possibly incomparable profiles by direct appeal to the residue definition and the natural-filter construction. revision: yes
Referee: [Characterization theorem] Characterization theorem (around §5): the claim that only totally-ordered families admit free natural filters for arbitrary budgets is load-bearing; a concrete counter-example family whose profiles are not totally ordered, together with the resulting privacy-loss calculation, would confirm that the general theory applies without additional ordering assumptions.

Authors: We agree that an explicit counter-example would usefully illustrate the necessity of the total-order condition. In the revised version we will insert a short subsection (or appendix) presenting a concrete two-mechanism family whose privacy profiles are incomparable under composition, together with the explicit privacy-loss calculation showing that the natural filter incurs a positive adaptivity cost. This will confirm that the characterization theorem relies only on the stated ordering assumption and that the general theory applies as claimed. revision: yes

Circularity Check

0 steps flagged

Derivation of natural filter characterization is self-contained from general theory

full rationale

The paper first develops a general theory characterizing worst-case privacy loss for an adaptive analyst respecting query restrictions. It then applies this theory to define residue filters (unifying prior filters) and to characterize when natural filters are free. The key claim—that only totally-ordered families admit free natural filters for arbitrary budgets—follows directly from the theory's application to privacy profiles without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations. The construction builds on standard DP composition properties and is presented as a derived theorem rather than an input. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on standard differential privacy composition axioms and introduces residue and natural filter concepts without independent empirical validation in the abstract.

axioms (1)

standard math Standard properties of differential privacy composition and privacy profiles
Invoked to characterize worst-case privacy loss and free filters

invented entities (1)

residue filters no independent evidence
purpose: Unify existing privacy filters and capture natural filters
New construct developed from the general theory

pith-pipeline@v0.9.0 · 5571 in / 1097 out tokens · 19054 ms · 2026-05-15T21:40:12.586376+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/BranchSelection.lean branch_selection unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

residue condition U(B,L)⊕L ≼ B

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.