Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "Privacy Filters are Captured by Residues".
Elias: Here's the gist of the paper. Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602.15815#pg2>.
Nadia: This paper develops a general theory to characterize the worst-case privacy loss of an interaction involving an analyst that respects restrictions on query issuance, leading to residue filters which unify existing privacy filters<ref:2602.15815#pg5>.
Elias: The work introduces the Gaussian DP (GDP) residue filter, showing it strictly improves upon the naïve GDP filter and captures the natural filter under certain conditions<ref:2602.15815#pg5>.
Nadia: Theoretical Framework for Privacy Accounting The paper establishes a framework using privacy loss distributions (PLDs) to characterize privacy characteristics, where PLDs are defined based on likelihood ratios between mechanisms<ref:2602.15815#pg4>.
Paper summary: Nadia: We just touched on how this paper sets up a general theory to characterize the worst-case privacy loss for an analyst who respects restrictions on query issuance, leading to residue filters which unify existing privacy filters, as it’s laid out on page five of this work <ref:2602.15815#pg3>.
Elias: Exactly. The authors develop a framework using privacy loss distributions or PLDs to define these characteristics based on likelihood ratios between mechanisms, and they show that these PLDs form a partially-ordered commutative monoid under convolution, which is crucial for analyzing adaptive composition, as you can see on page five <ref:2602.15815#pg3>.
Priya: That sounds mathematically dense. Can you translate what that means for us in terms of the actual data we are looking at? What is the big picture here?
Nadia: It means they are building a general theory to characterize the worst-case privacy loss of an interaction involving an analyst that respects some restrictions on what queries they may issue, leading to residue filters which unify existing privacy filters, as it’s laid out on page five of this work <ref:2602.15815#pg3>.
Elias: The authors apply this theory to develop residue filters, which perform exact accounting under a residual update condition, and they introduce the Gaussian DP residue filter specifically to improve upon the standard GDP filter by searching for the largest valid residual GDP budget, as seen on page thirteen of this work.
Priya: So instead of just using a simple parameter like epsilon or delta, they are looking at how the privacy loss accumulates across multiple queries in a way that respects these update conditions, right?
Nadia: Right. And they show that this approach captures the natural filter under certain conditions, which is significant because the natural filter promises greater utility by leveraging exact accounting techniques instead of just simple parameters like Rényi-DP or GDP parameters.
Elias: That’s what page one states: "Natural filters account for the entire privacy profile of every query, promising more efficient use of a given privacy budget," which is on page one.
Priya: So when you look at the numbers and caveats, are we talking about a method that gives us tighter bounds than standard approximate DP methods?
Nadia: They prove that natural filters are not free in general by showing counterexamples where they fail for certain queries and budgets, which is on page thirty-one of this work.
Priya: So it’s not perfect protection, but it's not completely useless either if we know what to look for in terms of the query structure.
Nadia: It depends entirely on the structure of the queries; they show that universal freeness only holds for queries that are closed under composition and totally-ordered, as they explain on page thirty-five.
Elias: That condition links the mathematical properties of how queries can be combined to whether we get a free natural filter, which is a core theoretical finding here.
Conclusion: Nadia: So we’ve walked through how this paper develops a general theory to characterize the worst-case privacy loss for an analyst, leading to residue filters that unify existing ones, as outlined in the title of this work.
Elias: And they’ve shown that by introducing things like the Gaussian DP residue filter, they can strictly improve upon older methods like the standard GDP filter by finding a larger valid residual budget.
Priya: What does all this mean for us moving forward? If we apply these concepts, what is the practical implication for how we think about building privacy accounting systems?
Nadia: It means that residue filters capture all existing privacy filters, including Rényi and GDP forms, which provides a unified way to handle different types of DP mechanisms.
Elias: And they provide concrete conditions—being closed under composition and totally-ordered—for when the natural filter becomes universally free, which is on page thirty-five.
Priya: So if we take this theory seriously, it suggests that for specific types of queries and budgets, we can leverage exact accounting techniques to get better privacy guarantees than what's currently available with simpler methods.
Nadia: Exactly. It suggests that when the query structure is right, you can get more efficient use of your budget by leveraging the natural filter’s ability to account for the entire profile of every query.
Elias: The authors show that post-processing can achieve a bound on epsilon delta l star that is better than what we might expect from additive methods, as they detail on page thirty-one.
Priya: So in the end, it’s about moving towards a framework where we aren't just looking at one type of privacy filter, but one that can handle the whole family under specific structural constraints.
University of Waterloo · University of British Columbia · Google Research
cs.CR, cs.DS
Submitted: 2026-02-17
Updated: 2026-11-06
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 99/100
The gist: Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602.15815#pg2>.
Key concepts
- Privacy Loss Distributions (PLDs)
- These distributions quantify privacy loss by looking at likelihood ratios between different mechanisms. They form a mathematical structure that helps characterize how privacy degrades when information is queried adaptively.
- Residue Filters
- 'Residue filters' are a new framework designed to capture all existing privacy filters, including pure DP and GDP filters. They provide a general way to characterize the worst-case privacy loss resulting from an interaction involving an analyst respecting query restrictions.
- Natural Filter
- A natural filter is a type of privacy mechanism that arises from specific query structures. The paper characterizes when these filters are 'free' (meaning they don't incur excessive loss) based on the structure and composition of the queries being made.
Terminology
Summary
Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602. p. 0 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écuyer∗∗
April 17, 2026
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 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ïve GDP filter. We also show that residue filters capture the natural
filter, which promises greater utility by leveraging exact privacy accounting techniques.Where the paper says it
Where the paper says it
Where the paper says it
Theoretical Framework for Privacy Accounting
The paper establishes a framework using privacy loss distributions (PLDs) to characterize privacy characteristics, where PLDs are defined based on likelihood ratios between mechanisms<ref:2602.15815#pg4>. It defines the Blackwell order on pairs of distributions and shows that PLDs form a partially-ordered commutative monoid under convolution, which is crucial for analyzing adaptive composition<ref:2602. p. 4 It
is straightforward to show that this order is well-defined regardless of the underlying representations
(P, Q) and (P
′
, Q′
). When equipped with the Blackwell order, PLDs also form a partially-ordered
commutative monoid under convolution. For convenience, we will sometimes write hL to denote the unique hockey-stick curve associated
to a PLD L, namely hL(x) := EZ∼L[(1 − xe−Z)+]. Moreover, like PLDs, hockey-stick curves also
capture adaptive composition in a natural way.Where the paper says it
Where the paper says it
Characterization of Free Natural Filters
The central theoretical contribution is the characterization of when a family of private queries admits free natural filters for a given budget, specifically showing that only families totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget<ref:2602.15815#pg5>. The paper proves that the natural filter is universally free for any budget only for queries that are closed under composition and totally-ordered, in which case the natural filter is captured by a residue filter<ref:2602. p. 2 • In §5 we apply our theory of constrained adversaries to calculate the exact privacy cost of an
interaction with the natural filter. We show that the natural filter is universally free for any
budget only for queries that are closed under composition and totally-ordered, in which case
the natural filter is captured by a residue filter.Where the paper says it
Residue Filters and Their Scope
Residue filters are developed to capture all existing privacy filters, including the pure DP filter, Rényi filter, and GDP filter<ref:2602.15815#pg11>. A key result is Theorem 1 that states that for an update rule U satisfying a natural residue condition (⋆), the resulting update filter Algorithm 1 is free<ref:2602. p. 9 Now, notice that Algorithm 1
can be captured succinctly by the recursive privacy rule
UpdateU,B(λ) := {L ∈ L : L ⪯ B}
UpdateU,B |L1
:= UpdateU,U(B,L1)
. Our key result is that privacy filters derived from budget updates are valid as long as the updates
satisfy a natural residue condition. 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ïve GDP filter.Where the paper says it
Where the paper says it
Failure Modes and Bounds
The paper demonstrates that natural filters are not free in general, showing counterexamples where they fail for certain queries and budgets<ref:2602.15815#pg31>. However, it proves that the natural approximate-DP filter cannot fail too badly; the output remains approximate-DP with parameters at most poly-logarithmically worse than intended privacy parameters<ref:2602. p. 0 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. Let P and Q be distributions on Ω. The PLD of (P, Q), denoted PLD(P ∥ Q), is the
distribution over R := R ∪ {±∞} of log( dP
dQ (ω)), ω ∼ P.Where the paper says it
Where the paper says it
Universal Freeness Conditions
The paper identifies specific query families that admit universally free natural filters, including GDP queries and (0, δ)-DP queries<ref:2602.15815#pg38>. Corollary 6 shows that the natural filter for (0, δ)-DP queries is universally free for every budget B in Lall<ref:2602. p. 2 • In §5 we apply our theory of constrained adversaries to calculate the exact privacy cost of an
interaction with the natural filter. We show that the natural filter is universally free for any
budget only for queries that are closed under composition and totally-ordered, in which case
the natural filter is captured by a residue filter. 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.Where the paper says it
Where the paper says it
Post-Processing as a Privacy Guarantee
The analysis of the additive discretized PL profile filter shows that it is less strict than the natural (ε, δ)-DP PLD filter<ref:2602.15815#pg31>. Theorem 15 proves that PLD Discretekε,l∗⪯ Rχ·(ε+1),χ·δ<ref:2602. p. 0 lecuyer@ubc. ca
1
arXiv:2602.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved Privacy Accounting through Residue Filters: The system can utilize residue filters to unify existing privacy filters, such as pure DP, Rényi-DP, and GDP filters, by monitoring a remaining privacy budget according to the condition that
every budget encountered during the interaction dominates the privacy cost of the next budget plus the cost of the next query.
-
Enhanced Budget Management for Adaptive Interactions: The system can implement an update filter based on a residue condition, ensuring that if an analyst issues queries with constrained per-query privacy costs,
the resulting interaction provably satisfies a meaningful privacy guarantee,
which is formalized by Theorem 1. -
Superior Gaussian DP Filter: A new GDP residue filter can be developed that
strictly improves upon the naïve GDP filter,
specifically showing that for non-Gaussian queries,the residual GDP budget, when composed with the query, is very close to the starting budget.
-
Characterization of Free Natural Filters: The system can determine when a family of private queries admits free natural filters by checking if
the queries are closed under composition and totally-ordered,
as this condition is necessary for the filter to be universally free against an arbitrary privacy budget. -
Robust Guarantees for (Epsilon, Delta)-DP Filters: When using the natural (epsilon, delta)-DP filter on symmetric queries, the system can guarantee a stronger privacy level of
chi times epsilon plus one, chi times delta,
where chi is bounded by a value logarithmic in the number of rounds and inverse epsilon. -
Efficient Approximation via Additive Discretized Profile Filter: The system can employ an additive discretized privacy loss profile filter to approximate the natural (epsilon, delta)-DP filter with a privacy loss distribution bounded by Rchi times epsilon plus one, where chi is determined by k and 1/delta.
Abstract
We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We show that the worst-case privacy loss of interacting with any privacy filter is characterized by a Bellman equation. We apply this theory to develop residue filters, which unify existing privacy filters. We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the naïve GDP filter. We show that, in the average case, this new filter asymptotically permits as many pure DP queries as in the non-adaptive case and a factor π/2 more pure DP queries than the naïve 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ényi-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 an adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters.
Sources
- Publishing Wikipedia usage data with strong privacy guarantees
- Concentrated Differential Privacy
- Gaussian Differential Privacy
- The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
- Practical Privacy Filters and Odometers with R'enyi Differential Privacy and Applications to Differentially Private Deep Learning
- Scalable Extraction of Training Data from (Production) Language Models
- LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale
- f-Differential Privacy Filters: Validity and Approximate Solutions
- Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data