arXiv CS open access

Tight End-to-End Accounting for Differentially Private Synthetic Data

Georgi Ganev et al. · arxiv_cs

arXiv CS · Papers

cryptography cybersecurity privacy security

Differentially private (DP) pipelines often combine heterogeneous mechanisms, yet their guarantees are best analyzed using different notions of privacy (e.g., bounded range, zCDP, ADP). When composing them, we have to analyze the guarantees through a reduced common representation that loses accounti

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Preprint

T IGHT E ND - TO -E ND ACCOUNTING FOR D IFFERENTIALLY P RIVATE S YNTHETIC DATA Georgi Ganev1,2 , Vadym Doroshenko3 , Arun Ganesh4 , Juan Felipe Gomez5 , Ryan McKenna4 , and Bogdan Kulynych6 1

UCL SAS 3 Google 4 Google Research 5 Hasso Plattner Institute 6 Lausanne University Hospital (CHUV)

arXiv:2610.17249v1 [cs.CR] 12 Oct 2026

A BSTRACT Differentially private (DP) pipelines often combine heterogeneous mechanisms, yet their guarantees are best analyzed using different notions of privacy (e.g., bounded range, zCDP, ADP). When composing them, we have to analyze the guarantees through a reduced common representation that loses accounting precision. This issue is particularly relevant in DP synthetic data generation, where data preprocessing, generation algorithms, and DP-SGD could appear within the same pipeline. We develop novel tools for tight end-to-end accounting of such compositions using privacy loss distributions (PLD), f -DP, and Gaussian DP (GDP). In particular, we derive PLD and GDP analyses of bounded-range mechanisms such as the Exponential mechanism. Building on these theoretical results, we introduce AIM-GDP, a GDP-native variant of AIM (a state-of-the-art DP synthetic data mechanism) that enables easy composability with complex pipelines via PLD, attack-aware risk calibration, and tight end-to-end auditing while consistently achieving better utility; and MixCal, an algorithm for calibrating adaptive mixed compositions using PLD accounting. Overall, our tools enable tighter end-to-end accounting and thus less noise at the same privacy level in DP synthetic data pipelines.

I NTRODUCTION

A core strength of differential privacy (DP) (Dwork et al., 2006; 2014) is its composability: we can construct highly complex randomized algorithms by combining multiple simpler primitives. At the same time, in modern data-analytic workflows, the components are highly heterogeneous, e.g., including different data preprocessing algorithms, and using combinations of learning algorithms. Despite the composability of DP, there is a bottleneck when analyzing the privacy guarantees of such heterogeneous workflows. DP primitives have been developed using disparate analytical approaches, e.g., zero-concentrated DP (zCDP) (Bun & Steinke, 2016; Dwork & Rothblum, 2016) for compositions of private selection and simple noise addition algorithms (Dong et al., 2020), bounded range (BR) (Durfee & Rogers, 2019) for private selection, Rényi DP (RDP) (Mironov, 2017) for data-dependent compositions (Papernot et al., 2018) and early analyses of DP-SGD (Abadi et al., 2016), and privacy loss distributions (PLDs) (Meiser & Mohammadi, 2018) for more recent analyses of DP-SGD (Koskela et al., 2020; Gopi et al., 2021; Doroshenko et al., 2022). Because of this, when composing multiple primitives analyzed using different approaches, we have to reduce the potentially rich representations to “lowest common denominators,” incurring loss in accounting precision. As an example, consider AIM (McKenna et al., 2022), a state-of-the-art algorithm for generating synthetic tabular data with DP. Internally, this algorithm is a fully adaptive composition (Rogers et al., 2016) of Exponential and Gaussian mechanisms (Dwork et al., 2014). The standard way to perform accounting for such compositions is using zCDP. This notion, although it is convenient and tightly characterizes the Exponential mechanism, does not tightly characterize the trade-off curve (Dong 1

Preprint

Table 1: Novel theoretical results Analysis

Ref.

Bounded range Bounded range Partition selection Poisson subsampling Group privacy

f -DP/GDP PLD PLD PLD Exponential

Sec. 3 Sec. 3 App. B App. B App. B

RDP

PLD (ours) ↑ 2.9%

0.8 ↑ 9.9%

Application

Algorithm/pipeline

Discrete synthesis PLD calibration End-to-end synthesis Multimodal synthesis

AIM-GDP MixCal AIM-GDP + DP preproc. + MixCal AIM-GDP + DP-SGD + MixCal

AIM (ε, δ )

0.035

0.4

51% lower average error

0.030 0.025

0.2

0.020 25

0.0

Empirical µemp

MAUVE →

0.040

ε=1

ε=4

(a) Improved utility

Attack advantage % 1

(b) Attack-aware calibration

100

i ii–iii i–v i–v

Theory µ = 0.53 0.5

0.045

0.6

Can use

AIM-GDP (µ)

0.050

Full marginal error ←

i ii iii iv v

Table 2: Specific applications and algorithms/pipelines

Mechanism

0.49

0.4

0.50

0.3 0.2

0.24

0.1 0.0

ck-

Bla

box

ite-

emb

Ens

1 (c) First end-to-end audit

Figure 1: Our methods provide improved utility and enable new capabilities in DP synthetic data workflows. Top: Summary of theoretical results and algorithmic contributions. Bottom: (a) Our methods improve utility in synthetic text generation using LLMs. (b) Our methods enable to efficiently calibrate DP workflows to attack risk, with the first application of attack-aware calibration to synthetic data. (c) Our methods support tight end-to-end privacy audits, with the first end-to-end audit of the synthetic data generator, AIM-GDP, our version of AIM. et al., 2022) of the Gaussian mechanism (Zhu et al., 2022; Riess et al., 2026). Because of this, the resulting privacy accounting is lossy both (1) within AIM itself, and (2) when AIM is further composed with DP-SGD for multimodal synthetic data generation (Hu et al., 2026). In contrast, Gaussian DP (GDP) (Dong et al., 2022) optimally characterizes the Gaussian mechanism, and would compose well with DP-SGD or other pipelines using PLD accounting, but there are no general analyses of the Exponential mechanism in terms of GDP that do not require a special structure (Gopi et al., 2022). In this work, we improve the accounting precision by developing methods that are more suited for end-to-end accounting of realistic synthetic data workloads. Our core contributions are: 1. PLD, f -DP, and GDP analyses of BR mechanisms for private selection. Using these results, we show that GDP enables more precise analyses than zCDP in fully adaptive compositions where most of the privacy budget is spent on Gaussian mechanisms (as in AIM). We provide additional results that enable the support of more workloads, e.g., involving private partition selection, data subsampling, and multiple user contributions in Appendix B. See a summary in Table 1. 2. AIM-GDP. Building on the GDP analysis of the Exponential mechanism, we propose AIM-GDP, a variant of AIM that natively satisfies GDP. It provides comparable/better utility (Fig. 1a) with additional benefits. First, AIM-GDP enables the first efficient attack-aware calibration for DP synthetic data (Kulynych et al., 2024; 2025), enabling practitioners to set privacy budgets based on target risk levels (Fig. 1b). Second, it supports tight audits (Nasr et al., 2023; Annamalai et al., 2024), making it the first end-to-end audited implementation of AIM (Fig. 1c). Third, it is easily composable in complex pipelines, as GDP is compatible with tight PLD composition analyses. 3. MixCal. We introduce MixCal, a new algorithm for calibrating parameters in mixed-mechanism adaptive compositions that combines the advantages of zCDP or GDP for simple calibration of parameters across multiple components, and of PLD accounting for precision. Building on this, we extend AIM-GDP to more complex pipelines by combining it with DP preprocessing for end-to-end synthetic data generation and with DP-SGD for multimodal synthesis. See a summary in Table 2. 4. We demonstrate the combinations of these algorithms in realistic synthetic data workflows, showing both performance improvements at the same privacy level and new qualitative capabilities. Additionally, we release open-source implementations of our main methods (e.g., AIM-GDP, MixCal) in https://github.com/google/dpsynth under Apache 2.0 License. 2

Preprint

P ROBLEM S TATEMENT

2.1

M OTIVATION AND O BJECTIVE

Our main motivating setting is private tabular or multimodal synthetic data generation, even though, as we show next, our technical results are relevant to any mixed-mechanism compositions. Discrete data. For synthetic tabular data, the bestperforming DP mechanisms are marginal-based (Tao et al., 2022; Chen et al., 2025); which typically operate on discrete domains, and consist of a combination of selection steps (e.g., using the Exponential mechanism), and measurement steps (e.g., using the Gaussian mechanism). Some mechanisms (like AIM) further rely on fully-adaptive composition, where privacy budget assigned to each Exponential and Gaussian mechanism is a data-dependent random variable. End-to-end data. Beyond discrete data, real-world datasets Figure 2: End-to-end synthesis. often contain a mix of categorical attributes with potentially unknown domains (open-set attributes) and numerical attributes. To leverage marginal-based mechanisms, we must map our data to a discrete domain. For numerical attributes, data-dependent discretization, e.g., via DP quantiles (Kaplan et al., 2022), is a preferred approach (Ganev et al., 2025b). For open-set categorical attributes, private domain discovery (Gopi et al., 2020) poses an additional challenge, and, to the best of our knowledge, existing synthetic data implementations lack such support. Fig. 2 shows an example pipeline, which we discuss in detail in Section 4. Multimodal data. Beyond tabular data, generating synthetic unstructured data usually involves using a DP-SGD-style mechanism (e.g., finetuning an LLM) (Ponomareva et al., 2026). ACTG, a state-of-the-art mechanism for this task consists of a synthetic tabular generation step plus conditional finetuning step (Hu et al., 2026). This work relies on RDP accounting due to the reliance on AIM that only provides a zCDP guarantee. We provide a review of related mechanisms for data preprocessing and synthetization used in DP synthetic data pipelines in Table 5 in the Appendix. Our goal. The objective of our work is to provide methods for tight end-to-end privacy analyses for such heterogeneous pipelines. We observe two key challenges: (1) we lack precise analyses of mixed-mechanism compositions involving the Exponential mechanism for both fully adaptive and adaptive settings, and (2) it is unclear how to calibrate the parameters of the component mechanisms in such composed pipelines. In the remainder, we introduce several fundamental results and new algorithms to solve these challenges. 2.2

T ECHNICAL BACKGROUND

We provide a concise overview of the technical notions we use. For a more in-depth treatment, we refer the reader to Zhu et al. (2022), Gomez et al. (2026) or any of the cited works in this section. Throughout, P and Q are probability distributions on a measurable space Y. In an abuse of notation, we also write P (y) and Q(y) to denote their densities with respect to a common σ-finite measure, e.g., P + Q. We write (x)+ ≜ max{x, 0} and use the conventions log(a/0) = +∞ and log(0/a) = −∞ for a > 0, and e−∞ = 0. We begin by defining two divergences: the hockeystick divergence of order eε > 0 and the Rényi divergence of order τ > 1, respectively: τ P (y) 1 Heε (P ∥ Q) ≜ sup (P (E) − eε Q(E)), Dτ (P ∥ Q) ≜ τ −1 log Ey∼Q Q(y) . E⊆Y

With these divergences, we can define two notions of differential privacy (DP). A mechanism M (·) satisfies (ε, δ)-DP if Heε (M (S) ∥ M (S ′ )) ≤ δ for any neighbouring dataset pair S ≃ S ′ . A mechanism satisfies (τ, εRDP )-Rényi DP (RDP) if Dτ (M (S) ∥ M (S ′ )) ≤ εRDP . Zero-concentrated DP (zCDP) (Dwork & Rothblum, 2016; Bun & Steinke, 2016) is a special case of RDP: a mechanism is ρ-zCDP if it is (τ, τ · ρ)-RDP for any τ > 1. 3

Preprint

The function δ : R → [0, 1] such that a mechanism satisfies (ε, δ(ε))-DP for any ε ∈ R is called a privacy profile (Balle et al., 2018), and is closely related to the operational formulation of DP known as f -DP (Dong et al., 2022). Let T (P ∥ Q) denote the trade-off function which maps the Type I error (denoted by α) of the most powerful test distinguishing H0 ∼ P and H1 ∼ Q to its Type II error (denoted by β). We say a mechanism satisfies f -DP if f = T (P ∥ Q) for some pair (P, Q) and f ≤ T (M (S) ∥ M (S ′ )) for all S ≃ S ′ . An important special case of f -DP is Gaussian DP (GDP). We say a mechanism is µ-GDP if it satisfies fµ -DP, with fµ (α) = Φ(Φ−1 (1 − α) − µ), where Φ(t) is the CDF of the standard normal distribution (Dong et al., 2022). The celebrated Gaussian mechanism (Dwork et al., 2014), which adds Gaussian noise N (0, σ 2 · Id ) to a vector query q with ∥q(S) − q(S ′ )∥2 ≤ 1 for any pair S ≃ S ′ , is µ-GDP with µ = 1/σ. The 2 Gaussian mechanism also satisfies ρ-zCDP with ρ = µ /2. One of the most fundamental properties about differential privacy is composition, where the outputs of one mechanism are used as the input of another. For example, the composition of M1 and M2 is Mcomposed = M1 (D, M2 (D)). We refer to M1 and M2 as primitive mechanisms. We distinguish between two types of composition: the first, which we call adaptive composition or simply composition, is when the number of primitive mechanisms and the choice of all (ε, δ) is fixed ahead of time. The second type, which we call fully adaptive composition, occurs when the number of primitive mechanisms is not known, and only a fixed budget (ε, δ) is known ahead of time (Rogers et al., 2016). RDP admits a simple composition rule: if M1 satisfies (τ, εRDP )-RDP and M2 satisfies (τ, ε′RDP ), then the composed mechanism satisfies (τ, εRDP + ε′RDP )-RDP. For ρ-zCDP, the composition rule is particularly simple: sum the ρ of the components. This RDP composition result holds for both adaptive and p fully-adaptive composition (Feldman & Zrnic, 2021). GDP composition also admits a simple form µ21 + µ22 , and this holds in fully-adaptive setting (Smith & Thakurta, 2022; Koskela et al., 2023). Tight composition results for (ε, δ)-DP and its generalizations (i.e. privacy profiles, f -DP) are not as simple, and there are different results for adaptive and fully-adaptive composition. For adaptive composition, tight composition results can be derived via dominating pairs (Zhu et al., 2022). A pair of distributions P, Q is a dominating pair for a mechanism M (·) if for any ε ∈ R, we have Heε (P ∥ Q) ≥ supS≃S ′ Heε (M (S) ∥ M (S ′ )). We say (P, Q) is a tightly dominating pair if the inequality is equality. Given a dominating pair (P, Q), composition becomes simple: if M1 has dominating pair (P1 , Q1 ) and M2 has dominating pair (P2 , Q2 ), then the composed mechanism has dominating pair (P1 ⊗ P2 , Q1 ⊗ Q2 ). Privacy Loss Distributions (PLDs) and Privacy Loss Random Variables (PLRVs) (Sommer et al., 2019) make this analysis even simpler. Given a dominating pair (P, Q), define the random variable ωP/Q ≜ log P (y)/Q(y) with y ∼ P as the privacy loss random variable, and, its distribution as the PLD. If M1 has PLRV ωP1 /Q1 and M2 has PLRV ωP2 /Q2 , then the composed mechanism has PLRV ωP1 /Q1 + ωP2 /Q2 . Because this addition is over independent random variables, the composed mechanism’s PLD is a convolution of the individual PLDs. Given a PLD, we can compute the privacy profile as δ(ε) = E[(1 − eε−ωP /Q )+ ]. Analogously to dominating pairs, we say that a PLD ω dominates a mechanism M (·) if its privacy profile is an upper bound of the actual privacy profile of the mechanism for all ε ∈ R. PLDs provide a recipe for tight composition of mechanisms: first, compute the PLD of each primitive, then convolve their PLDs and compute the composed profile or the trade-off function from the convolved PLD. For fully-adaptive composition, the PLD approach generally does not provide valid bounds (Regehr et al., 2026; Tran et al., 2026), and, as far as we are aware, the tightest known bounds for general heterogeneous fully-adaptive composition of mechanisms are given by ρ-zCDP or µ-GDP. We conclude this section with one last privacy representation: bounded range (BR) (Durfee & Rogers, 2019). We say a mechanism M : 2D → Y satisfies ν-bounded range (BR) if for any S ≃ S ′ there exists 0 ≤ t ≤ ν such that for all measurable E ⊆ Y, the range of privacy loss is bounded: Pr[M (S) ∈ E] ∈ [−t, −t + ν]. (1) log Pr[M (S ′ ) ∈ E] Bounded range is especially suitable to characterizing the standard Exponential mechanism. An Exponential mechanism M (·) with a discrete output space Y is a mechanism with probability distribution Pr[M (S) = y] ∝ exp (−ν/2 · q(S, y)), where q : 2D → R is a query such that for any S ≃ S ′ and y ∈ Y, we have |q(S, y) − q(S ′ , y)| ≤ 1. Exponential mechanism satisfies ν-BR. 4

Preprint

Notably, it also satisfies zCDP with ρ = 1/8 · ν 2 (Durfee & Rogers, 2019), with a tighter expression recently given by Harrison & Manurangsi (2026a).

N EW B UILDING B LOCKS FOR H ETEROGENEOUS ACCOUNTING

In this section, we provide several new theoretical results that we later use as building blocks. Novel analyses of Bounded Range mechanisms. We introduce a tight characterization of BR mechanisms by deriving their privacy profile, trade-off function, and PLD. From the trade-off function, we also derive a tight GDP bound. The latter is useful for analyzing fully adaptive compositions of mechanisms involving BR, such as the AIM algorithm for synthetic data generation. Theorem 3.1. Let M (·) satisfy ν-BR. Then M (·) satisfies f -DP and (ε, δ(ε))-DP for all ε ∈ R, with  eε , ε ≤ −ν,  1 − 2 ν/2 1−α e −eε/2 ) ( (2) f (α) = , δ(ε) = , −ν < ε < ν, eν −1  αeν + 1 − α  0, ε ≥ ν. Moreover, M (·) is dominated by the PLD with density: gν (x) = Dν ex/2 1[−ν,ν] (x),

−1 where Dν = 12 eν/2 − e−ν/2 .

(3)

These bounds are tight over the class of ν-BR mechanisms: for every α ∈ [0, 1] (respectively, every ε ∈ R) there exist a ν-BR mechanism and a pair S ≃ S ′ that attain f (α) (respectively, δ(ε)). Theorem 3.2. Suppose that a mechanism M (·) satisfies ν-BR. Then, it also satisfies µ-GDP with: 1 −1 µ = −2Φ . (4) eν/2 + 1 We provide the proofs of both statements and some discussion of them in Appendix A. There are various ways of comparing our new bounds to the previous tightest known zCDP bounds. We choose to compare the trade-off functions due to their interpretability. We show the optimal BR trade-off function, our derived GDP trade-off function, and the tightest known trade-off function implied by zCDP in Fig. 3. We observe that our optimal trade-off function provides a tighter bound than zCDP in all regimes, and our GDP bound provides a tighter bound than zCDP in some, but not all regimes.

1.0

As we consider compositions of BR mechanisms, it is natural to ask if our analyses actually yield better results than zCDP. In practice, we care about compositions of mixed-mechanisms, often compositions of Gaussians and Exponential mechanisms. Fig. 4 illustrates that our GDP analysis is tighter for mixed-mechanism compositions containing BR mechanisms where the majority of the budget is spent in Gaussian mechanisms, which is the setting of AIM, and we leverage this property next; and the PLD analysis is tighter for non-fully adaptive compositions, which is the setting of preprocessing workloads.

Figure 3: Trade-off curves of a BR mechanism (higher is more precise) with ν = 4, given by our f -DP (Theorem 3.1) and GDP analyses (Theorem 3.2), and zCDP using the recent optimal conversion (Harrison & Manurangsi, 2026a). To show the trade-off curves given by zCDP we use the conversion from RDP to f -DP (Riess et al., 2026), for orders > 1.

BR GDP zCDP DP

0.8 0.6 0.4 0.2 0.0 0.00

0.02

0.04

0.06

0.08

0.10

Subsampling, group privacy, tight partition selection. We provide a number of additional analyses for mechanisms of interest in various realistic data generation pipelines. All of these results are deliberately designed to be compatible with open-source software PLD libraries such as dp accounting. Due to space constraints, we defer the details to Appendix B. 5

Preprint

0.5

∆ε (RDP − PLD)

∆ε (zCDP − GDP)

0.25 0.0

0.20

T 1 5 10 20 50 100

−0.5 −1.0 0.2

0.4

0.6

0.8

0.15 0.10

0.05 0.1 0.15 0.2

0.05 0.00 0

1.0

100

Number of features

Proportion of the budget for Gaussian

Figure 4: Our methods enable tighter accounting in the regimes of interest. On the y axis, we show the ε decrease (> 0 means our methods are better) at δ = 10−5 . Left: Using GDP, as a function of the budget proportion of Gaussian mechanisms (x axis) and number of iterations (hue) in AIM-like workloads containing fully adaptive compositions of Exponential and Gaussians. Right: Using PLD, as a function of the number of features (x axis) and the per-feature privacy parameter µ in data preprocessing-like workloads containing compositions of Exponential and Threshold Gaussian mechanisms. Details in Appendix D. Poisson subsampling of arbitrary mechanisms. We provide a method for converting a PLD of an arbitrary mechanism to the PLD for the mechanism wrapped with Poisson subsampling (Abadi et al., 2016). Previously, only additive mechanisms like Gaussian and Laplace mechanisms were supported. By enabling Poisson subsampling for arbitrary mechanisms, it becomes possible to scale synthetic data workflows to large datasets. Group privacy for Exponential and other mechanisms on partitioned datasets. We show that partitioning a dataset and then running, in particular, a ν-BR mechanism on each subset of the partition satisfies kν-bounded range for groups of k records. This enables a privacy analysis of mechanism such as DP quantiles (Kaplan et al., 2022) even when users can contribute multiple records. Characterization of Threshold Gaussian and Threshold Laplace. The Threshold Gaussian and Laplace mechanisms (Gopi et al., 2020) are useful mechanisms for DP partition selection. We provide a tighter characterization of their privacy guarantees in terms of PLD and privacy profiles.

A PPLICATIONS

Next, we use the results in Section 3 to develop better algorithms for heterogeneous data analysis. Discrete synthetic data with AIM-GDP. The developments in Section 3 can be used to improve the privacy analysis of any mechanism that uses the Exponential mechanism as a primitive. One such example is AIM (McKenna et al., 2022), a state-of-the-art mechanism for synthetic data generation that operates within the select-measure-generate paradigm. AIM selects the worst-approximated marginal using Exponential mechanism, “measures” the selected marginal query using Gaussian mechanism, and repeats these two steps until the budget is depleted. Afterwards, a synthetic dataset is generated based on the measured marginals about real data. AIM is designed to spend the majority of the budget on the marginal measurements (Gaussian mechanism) because the signal is divided among the histogram bins and is hence more sensitive to noise. Whereas the original algorithm uses zCDP, our new GDP analysis in Section 3 provides improvements in exactly the regime where the majority of the budget in a mixed-mechanism composition is spent in Gaussian mechanisms. As a result, a GDP analysis of AIM is tighter than the original zCDP analysis. We present algorithms for both the original AIM, and our version, AIM-GDP, in Appendix C. End-to-end synthetic data with AIM-GDP, DP preprocessing, and MixCal. One downside of AIM is that it can only be run on datasets with closed-domain or discrete attributes. In contrast, real-world tabular datasets typically contain a mix of numerical attributes and open-set categorical attributes with unbounded vocabularies (Fig. 2). Applying AIM to real datasets thus requires preprocessing these attributes with DP. As this is done on top of AIM without referencing the privacy budget, preprocessing workloads can be thought of as primitives that we compose non-fully adaptively with 6

Preprint

AIM. For numerical attributes, we focus on using DP quantiles via recursive bisection (Kaplan et al., 2022) (see Algorithm 7 in the Appendix). Because this algorithm is a composition of standard Exponential mechanisms, it directly benefits from our PLD characterization of BR. For open-set categorical attributes, existing implementations either perform data-dependent domain construction without accounting for it (Qian et al., 2023), or do not support it at all (OpenDP, 2021; Mahiou et al., 2025). We introduce the first principled integration of private partition selection, e.g., the Threshold Gaussian mechanism (Gopi et al., 2020) (see Algorithm 8 in the Appendix), into synthetic data pipelines, using our new PLD characterization to tightly account for domain discovery. Concretely, given a tabular dataset with numerical and open-set categorical attributes, first, we apply DP Quantiles and the Threshold Gaussian mechanism to map these attributes to discrete ones, and then, apply AIM-GDP to generate synthetic data. The Gaussian PLD from AIM-GDP, the PLDs of private set partition via Threshold Gaussian, and of discretization via DP quantiles (we introduce both in Appendix B), are composable in a straightforward way using standard PLD accountants. Taken together, these results extend the usage of AIM to a larger class of tabular datasets. Moreover, in such workflows, different components might measure the same queries. In Appendix C, we also describe how to enable the re-use of such query outputs. Calibrating the components. In practice, however, there is a salient challenge when using PLD accounting in such workflows. We normally have a target guarantee, e.g., (ε⋆ , δ ⋆ ), or (α⋆ , β ⋆ ) for f -DP based attack-aware calibration (see Section 5). Therefore, we require a method to assign noise parameters (e.g., Gaussian parameter σ, Exponential Mechanism parameter ν) to the primitive mechanisms such that the composed PLD satisfies the target guarantee. A key challenge of this approach is that there is no clear way to decompose our target such that εpreprocess + εAIM = ε⋆ . This makes it difficult to “assign” more privacy budget to AIM and less to preprocessing, which is often desirable in practice. To solve this problem, we introduce a “dummy” privacy budget, denoted as b. As a simple example, suppose we are handling a composition of Gaussians, Exponential Mechanisms, and AIM-GDP, all of which have a known PLD and ρ-zCDP guarantee. Starting from, e.g., the target (ε⋆ , δ ⋆ ), we use a conversion (e.g., Bun & Steinke, 2016) to zCDP to obtain the dummy privacy budget b = ρ(ε⋆ , δ ⋆ ). If we have a weight w1 for preprocessing and weight w2 for AIM-GDP such that w1 + w2 = 1, we calibrate the preprocessing noise parameters to satisfy w1 · b-zCDP budget and calibrate AIM-GDP to satisfy w2 · b-zCDP budget. We then use PLD accounting to analyze the composed mechanism. As our calibration itself is not precise, we would add more noise than necessary. We thus perform binary search over b: if the resulting ε is larger than the target ε⋆ , we decrease b. Otherwise, we increase it. This allows us to meaningfully assign more or less privacy budget to preprocessing vs. AIM-GDP, while making use of the tighter analysis of PLD over zCDP. This algorithm can be generalized to use any “dummy” budget that is additive under composition, e.g., GDP, and to variable numbers of compositions. We call this algorithm MixCal and present it in Algorithm 9 in the Appendix. Multimodal synthetic data with AIM-GDP, DP-SGD, and MixCal. Recent work in synthetic text data generation with LLMs used AIM as a building block. For instance, the ACTG mechanism (Hu et al., 2026) consists of several steps: (1) annotate input text data using a predefined tabular schema, (2) run AIM on the generated tabular data with a fraction of the budget, and (3) run DP-SGD to finetune a language model to predict the text given the tabular metadata (see Fig. 5). The privacy analysis is hence a composition of AIM with DP-SGD, and, because AIM satisfies zCDP, Hu et al. Figure 5: Multimodal synthesis. (2026) used RDP instead of the tighter PLD accounting. By replacing AIM with AIM-GDP, we can analyze the algorithm end-to-end with PLD, and use MixCal to allocate the budget. Beyond precision, PLD accounting enables more capabilities, such as using random allocation (Feldman & Shenfeld, 2025) instead of Poisson subsampling in DP-SGD, which provides better utility in most regimes and is only analyzable using PLD, and subsampling large datasets using our new analyses in Appendix B.

E XPERIMENTAL E VALUATION

We now evaluate the algorithms introduced in Section 4 across three synthetic data generation applications: discrete, end-to-end, and multimodal. 7

Preprint

Table 3: AIM-GDP consistently shows better utility. We show 1/2/3-way and full marginal errors, number of measured marginals, and runtime, averaged across four datasets and four privacy budgets.

5.1

Algorithm

1-way

2-way

3-way

Full

#Marginals

Time (s)

Discrete

AIM AIM-GDP (ours)

0.0035 0.0033

0.0224 0.0216

0.0556 0.0542

0.0451 0.0439

40.33 40.68

399.2 404.6

End-to-end

AIM AIM-GDP (ours)

0.0038 0.0036

0.0284 0.0274

0.0763 0.0746

0.0613 0.0599

42.20 42.38

426.3 444.8

D ISCRETE S YNTHETIC DATA WITH AIM-GDP

We evaluate AIM-GDP on four standard discrete datasets (with known categorical features; see Table 6 in the Appendix) across four privacy budgets, ε ∈ {0.5, 1, 2, 5}, δ = 10−5 , with five runs per setting. We assess utility using the mean TV distance between the marginal distributions of real data and model projections, computed over 1/2/3-way and full workloads. We also demonstrate two additional capabilities enabled by AIM-GDP: attack-aware risk calibration, and tight end-to-end privacy auditing. Note that these capabilities are also applicable to the entire pipelines analyzable via PLD using MixCal. We focus on their evaluation for a standalone AIM-GDP instance for simplicity. Utility. AIM-GDP consistently outperforms the standard AIM analyzed with zCDP, reducing marginal error by 3% on average across datasets/privacy budgets. See top of Table 3 for a summary. In the Appendix, we present detailed comparisons (Fig. 9), and additional diagnostics over 25 runs on the Adult dataset with ε = 1, which show that AIM-GDP adds less noise per measurement step, enabling it to run for more iterations (Fig. 10), while selecting a very similar set of marginals (Fig. 11). Thus, our tighter accounting improves utility without substantially changing AIM’s underlying behavior. These results provide evidence that AIM-GDP can serve as a drop-in replacement for standard AIM. Attack-aware calibration. Choosing ε is challenging in practice because it does not directly quantify an operational privacy risk. In contrast, the µ-GDP guarantee of AIM-GDP, and the PLD representation of AIM-GDP after composition with data preprocessing, directly characterize (Kulynych et al., 2024) the full trade-off of any membership inference attacks (MIAs) (see, e.g., Shokri et al., 2017; Carlini et al., 2022), which is a standard way to quantify the operational privacy risk. This enables practitioners to specify an operational risk target, e.g., a maximum attack true positive rate (TPR) at a given low false positive rate (FPR), and calibrate AIM-GDP directly to it, rather than first selecting (ε, δ) and subsequently translating it to attack risk (Kulynych et al., 2024). See Appendix D for details. In Fig. 1b we show the results of calibrating AIM-GDP to attack advantage (Yeom et al., 2018), a standard risk measure that equals maximum TPR − FPR of MIAs. As the plot shows, attack-aware calibration substantially improves the utility at the same level of risk (e.g., by 51% on Adult). To the best of our knowledge, this is the first such application to DP synthetic data. Auditing. It is crucial to audit (see, e.g. Nasr et al., 2023; Annamalai et al., 2024; Ganev et al., 2025a) practical implementations of DP algorithms, as they often introduce software bugs that invalidate the theoretical guarantees. Our GDP analysis enables us to tightly audit the privacy guarantees of AIM-GDP. To do so, we train 10,000 models on worst-case neighboring datasets and use the FPR/TPR of a MIA to statistically estimate a lower bound on the empirical privacy parameter µemp . See Appendix D for details. As shown in Fig. 1c, our attacks achieve µemp = 0.50, closely approaching the theoretical bound of µ = 0.53. To the best of our knowledge, this is the first tight end-to-end empirical audit of fully adaptive AIM, i.e., including its data-dependent marginal selection, as prior work restricted AIM to fixed marginal structures (e.g., all 1-way marginals) and did not establish comparable tightness (Ganev et al., 2026). 5.2

E ND - TO - END SYNTHETIC DATA WITH AIM-GDP, DP PREPROCESSING , AND MixCal

We now evaluate AIM-GDP in an end-to-end synthetic data pipeline, following the evaluation setup from the previous section, but privately preprocessing every column via either DP quantiles or Threshold Gaussian, as described in Section 4. We use MixCal with zCDP as “dummy” budget to calibrate the pipeline components, allocating 10% for preprocessing and 90% for synthetization. 8

Preprint

Table 4: Our analyses enable adding substantially less noise in ACTG pipelines (combination of synthetization and DP-SGD). The table shows DP-SGD noise multipliers σSGD at fixed iterations T = 512, K = 8, δ = 10−6 for varying values of ε. Poisson subsampling uses q = K/T . ε

RDP (Poisson)

PLD (Poisson)

PLD (Random Alloc.)

1 2 4 8

2.34 1.40 0.97 0.74

2.18 1.32 0.92 0.71

2.25 1.30 0.89 0.69

As before, AIM-GDP outperforms AIM (with RDP accounting in this setting), reducing marginal error by over 2% across datasets (see bottom of Table 3 and Fig. 12 in the Appendix). Compared with the discrete setting in Section 5.1, errors decrease for predominantly categorical datasets but increase for predominantly numerical ones, showing that there are avenues for improvement in numerical preprocessing mechanisms. Next, we illustrate how our end-to-end analyses can be used to support large-scale settings (e.g., more than 200K records) using the Poisson subsampling results (see Section 3). For this, we simulate a workload with 16 numerical attributes, each discretized into 16 bins using 4 iterations of DP Quantiles. The resulting pipeline composes 64 Exponential mechanisms. We compare our tight PLD accounting, which applies subsampling directly in the PLD space, against an RDP baseline that bounds the Exponential mechanisms via zCDP. Our analysis yields a lower ε across all sampling rates, improving over RDP by 5.6% without subsampling (q = 1) and by up to 66.7% at q = 2−6 , with the gains increasing as the subsampling probability decreases. We show the results in Fig. 13 in the Appendix. 5.3

G ENERATING S YNTHETIC T EXT DATA WITH LLM S AND TABULAR C ONDITIONING

To further demonstrate the benefits our methods, we replicate the attribute-conditioned text generation (ACTG) pipeline (Hu et al., 2026). This work has improved on existing DP synthetic text evaluations (Xie et al., 2024; Tan et al., 2025), and found that ACTG outperformed strong baselines such as vanilla DP-SGD, private evolution (Xie et al., 2024), and CTCL (Tan et al., 2025). ACTG assumes records that consist of structured tabular attributes and text. ACTG uses AIM to produce a synthetic dataset of structured attributes, then finetunes a language model with DP-SGD to generate text conditioned on these attributes (see Fig. 5). We reproduce this pipeline on the bioRxiv dataset using the Gemma 3 1B base model. ACTG has a reinforcement learning stage, but, as it is independent of the privacy analysis, we omit it in our demonstration. We compare the original AIM vs. AIM-GDP with end-to-end PLD accounting using MixCal. We used budget allocation weights that replicate the allocation used by Hu et al. (2026). See further details in Appendix D. We report our results in terms of the standard MAUVE scores (Pillutla et al., 2023) in Fig. 1a. We observe consistent improvement in using PLD with MixCal and AIM-GDP, over RDP accounting with AIM. This gain is due to a combination of using AIM-GDP over AIM and using lower noise parameters for DP-SGD when using PLD accounting compared to RDP accounting. Additionally, we show the improvements in noise multipliers of DP-SGD in Table 4, using Poisson subsampling and Random Allocation, which is a new capability enabled by PLD accounting compared to the RDP approach.

C ONCLUSIONS

We unified disparate DP primitives under a single analytical and algorithmic framework, providing both qualitative and quantitative advantages for DP synthetic data pipelines with heterogeneous components. To support this, we presented GDP and PLD analyses for bounded range mechanisms, alongside a series of other results such as the PLD analysis of private partition selection (e.g., Threshold Gaussian). These analyses provide a versatile toolbox for future DP mechanism design. Applying these theoretical results, we introduced MixCal and AIM-GDP to calibrate and tightly account for mixed-mechanism workloads. By reducing the analytical slack in heterogeneous composition, our framework yields immediate utility gains across tabular and multimodal use cases without requiring major mechanism modifications. Ultimately, this work establishes a principled foundation for building and tightly accounting for increasingly complex, multimodal DP mechanisms. 9

Preprint

Limitations. Our GDP and PLD analyses of BR mechanisms do not provide tighter accounting than standard zCDP in all cases. E.g., as we show in Section 3, GDP is only beneficial in heterogeneous pipelines when the majority of the budget is used for the Gaussian mechanisms, which is the case for AIM, but not other fully adaptive workflows, e.g., interactive statistical queries. Our MixCal algorithm enables allocating the budget according to pre-specified weights, but we do not introduce a way for optimally choosing these weights. Finding optimal ways to do so is an avenue for future work. Finally, although the GDP analysis used in AIM-GDP is more precise than the zCDP analysis, it is not as tight as it would have been had the algorithm used only homogeneous components internally. Future work could compare our version to possible variants of AIM that, e.g., only use Gaussian mechanisms, which would enable even tighter analyses. AI USE STATEMENT We have used AI-based systems to assist with the implementation of the code for the experiments, visualizations, and LaTeX source code, as well as with proof ideation and verification. All the final text and proofs are written by the authors.

R EFERENCES Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. In ACM CCS, 2016. Meenatchi Sundaram Muthu Selva Annamalai, Georgi Ganev, and Emiliano De Cristofaro. “What do you want from theory alone?” Experimenting with Tight Auditing of Differentially Private Synthetic Data Generation. In USENIX Security, 2024. Sergül Aydöre, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Ankit Siva. Differentially Private Query Release Through Adaptive Projection. In ICML, 2021. Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In NeurIPS, 2018. Rina Foygel Barber and John C Duchi. Privacy and Statistical Risk: Formalisms and Minimax Bounds. arXiv:1412.4451, 2014. David Blackwell. Equivalent Comparisons of Experiments. Ann. Math. Stat., 1953. Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In TCC, 2016. Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 2020. Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramèr. Membership Inference Attacks from First Principles. In IEEE S&P, 2022. Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Algorithmic Learning Theory, 2021. Kai Chen, Xiaochen Li, Chen Gong, Ryan McKenna, and Tianhao Wang. Benchmarking Differentially Private Tabular Data Synthesis:[Experiments & Analysis]. PACMMOD, 2025. Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In ACM SIGKDD, 2016. Giovanni Cherubin, Boris Köpf, Andrew Paverd, Shruti Tople, Lukas Wutschitz, and Santiago Zanella-Béguelin. Closed-Form Bounds for DP-SGD against Record-level Inference Attacks. In USENIX Security, 2024. Damien Desfontaines, James Voss, Bryant Gipson, and Chinmoy Mandayam. Differentially private partition selection. PoPETs, 2022. 10

Preprint

Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal Differential Privacy Composition for Exponential Mechanisms. In ICML, 2020. Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. J. R. Stat. Soc., B: Stat. Methodol., 2022. Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions. PoPETs, 2022. David Durfee and Ryan M Rogers. Practical Differentially Private Top-k Selection with Pay-whatyou-get Composition. In NeurIPS, 2019. Cynthia Dwork and Guy N Rothblum. Concentrated Differential Privacy. arXiv:1603.01887, 2016. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, 2006. Cynthia Dwork, Aaron Roth, et al. The Algorithmic Foundations of Differential Privacy. Found. Trends Theor. Comput. Sci., 2014. Vitaly Feldman and Moshe Shenfeld. Privacy Amplification by Random Allocation. In NeurIPS, 2025. Vitaly Feldman and Tijana Zrnic. Individual Privacy Accounting via a Rényi Filter. In NeurIPS, 2021. Georgi Ganev, Meenatchi Sundaram Muthu Selva Annamalai, and Emiliano De Cristofaro. The Elusive Pursuit of Eeproducing PATE-GAN: Benchmarking, Auditing, Debugging. TMLR, 2025a. Georgi Ganev, Meenatchi Sundaram Muthu Selva Annamalai, Sofiane Mahiou, and Emiliano De Cristofaro. The Importance of Being Discrete: Measuring the Impact of Discretization in End-to-End Differentially Private Synthetic Data. In ACM CCS, 2025b. Georgi Ganev, Meenatchi Sundaram Muthu Selva Annamalai, and Bogdan Kulynych. Tight Auditing of Differential Privacy in MST and AIM. In TPDP, 2026. Quan Geng and Pramod Viswanath. Optimal Noise Adding Mechanisms for Approximate Differential Privacy. IEEE Trans. Inf. Theory, 2015. Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially Private Quantiles. In ICML, 2021. Juan Felipe Gomez, Bogdan Kulynych, Georgios Kaissis, Flavio du Pin Calmon, Jamie Hayes, Borja Balle, and Antti Honkela. Gaussian DP for Reporting Differential Privacy Guarantees in Machine Learning. In IEEE SaTML, 2026. Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Differentially Private Set Union. In ICML, 2020. Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical Composition of Differential Privacy. In NeurIPS, 2021. Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private Convex Optimization via Exponential Mechanism. In COLT, 2022. Charlie Harrison and Pasin Manurangsi. Exact zCDP characterizations for fundamental differentially private mechanisms. In FORC, 2026a. Charlie Harrison and Pasin Manurangsi. Optimal partition selection with Rényi differential privacy. In FORC, 2026b. Yuzheng Hu, Ryan McKenna, Da Yu, Shanshan Wu, Han Zhao, Zheng Xu, and Peter Kairouz. ACTG-ARL: Differentially Private Conditional Text Generation with RL-Boosted Control. In ICML, 2026. 11

Preprint

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The Composition Theorem for Differential Privacy. In ICML, 2015. Haim Kaplan, Shachar Schnapp, and Uri Stemmer. Differentially Private Approximate Quantiles. In ICML, 2022. Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In AISTATS, 2020. Antti Koskela, Marlon Tobaben, and Antti Honkela. Individual privacy accounting with gaussian differential privacy. In ICLR, 2023. Bogdan Kulynych, Yao-Yuan Yang, Yaodong Yu, Jaroslaw Blasiok, and Preetum Nakkiran. What You See is What You Get: Principled Deep Learning via Distributional Generalization. In NeurIPS, 2022. Bogdan Kulynych, Juan Felipe Gomez, Georgios Kaissis, Flavio du Pin Calmon, and Carmela Troncoso. Attack-Aware Noise Calibration for Differential Privacy. In NeurIPS, 2024. Bogdan Kulynych, Juan Gomez, Georgios Kaissis, Jamie Hayes, Borja Balle, Flavio Calmon, and Jean Raisaro. Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy. In NeurIPS, 2025. Terrance Liu, Giuseppe Vietri, and Zhiwei Steven Wu. Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods. In NeurIPS, 2021. Sofiane Mahiou, Amir Dizche, Reza Nazari, Xinmin Wu, Ralph Abbey, Jorge Silva, and Georgi Ganev. dpmm: Differentially Private Marginal Models, a Library for Synthetic Tabular Data Generation. In TPDP, 2025. Ryan McKenna. Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML. In ICLR, 2025. Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphical-model Based Estimation and Inference for Differential Privacy. In ICML, 2019. Ryan McKenna, Siddhant Pradhan, Daniel R Sheldon, and Gerome Miklau. Relaxed Marginal Consistency for Differentially Private Query Answering. In NeurIPS, 2021. Ryan McKenna, Brett Mullins, Daniel Sheldon, and Gerome Miklau. AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data. PVLDB, 2022. Sebastian Meiser and Esfandiar Mohammadi. Tight on Budget? Tight Bounds for r-Fold Approximate Differential Privacy. In ACM CCS, 2018. Ilya Mironov. Rényi Differential Privacy. In IEEE CSF, 2017. Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight Auditing of Differentially Private Machine Learning. In USENIX Security, 2023. OpenDP. SmartNoise SDK: Tools for Differential Privacy on Tabular Data. https://github.com/ opendp/smartnoise-sdk, 2021. Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Úlfar Erlingsson. Scalable Private Learning with PATE. In ICLR, 2018. Krishna Pillutla, Lang Liu, John Thickstun, Sean Welleck, Swabha Swayamdipta, Rowan Zellers, Sewoong Oh, Yejin Choi, and Zaid Harchaoui. MAUVE scores for generative models: Theory and practice. JMLR, 2023. Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A practical guide to machine learning with differential privacy. JAIR, 2023. 12

Preprint

Natalia Ponomareva, Zheng Xu, H Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent Cohen-Addad, Cristóbal Guzmán, Ryan McKenna, Galen Andrew, Alex Bie, et al. How to DP-fy Your Data: A Practical Guide to Generating Synthetic Data With Differential Privacy. JAIR, 2026. Zhaozhi Qian, Rob Davis, and Mihaela Van Der Schaar. Synthcity: A Benchmark Framework for Diverse Use Cases of Tabular Synthetic Data. In NeurIPS Datasets and Benchmarks Track, 2023. Matthew Regehr, Bingshan Hu, Ethan Leeman, Pasin Manurangsi, Pierre Tholoniat, and Mathias Lécuyer. Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity. arXiv:2602.15815, 2026. Anneliese Riess, Juan Felipe Gomez, Flavio du Pin Calmon, Julia Anne Schnabel, and Georgios Kaissis. Optimal Conversion from Rényi Differential Privacy to f -Differential Privacy. In ICML, 2026. Ryan M Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan. Privacy Odometers and Filters: Pay-as-you-Go Composition. In NeurIPS, 2016. Michael R Sampford. Some Inequalities on Mill’s Ratio and Related Functions. Ann. Math. Stat., 1953. Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership Inference Attacks against Machine Learning Models. In IEEE S&P, 2017. Amanpreet Singh, Mike D’Arcy, Arman Cohan, Doug Downey, and Sergey Feldman. SciRepEval: A Multi-Format Benchmark for Scientific Document Representations. In EMNLP, 2023. Adam Smith and Abhradeep Thakurta. Fully Adaptive Composition for Gaussian Differential Privacy. arXiv:2210.17520, 2022. David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy Loss Classes: The Central Limit Theorem in Differential Privacy. PoPETS, 2019. Bowen Tan, Zheng Xu, Eric Xing, Zhiting Hu, and Shanshan Wu. Synthesizing Privacy-Preserving Text Data via Finetuning without Finetuning Billion-Scale LLMs. In ICML, 2025. Yuchao Tao, Ryan McKenna, Michael Hay, Ashwin Machanavajjhala, and Gerome Miklau. Benchmarking Differentially Private Synthetic Data Generation Algorithms. In PPAI, 2022. Long Tran, Antti Koskela, Ossi Räisä, and Antti Honkela. f -Differential Privacy Filters: Validity and Approximate Solutions. arXiv:2602.06756, 2026. Chulin Xie, Zinan Lin, Arturs Backurs, Sivakanth Gopi, Da Yu, Huseyin A Inan, Harsha Nori, Haotian Jiang, Huishuai Zhang, Yin Tat Lee, et al. Differentially Private Synthetic Data via Foundation Model APIs 2: Text. In ICML, 2024. Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting. In IEEE CSF, 2018. Santiago Zanella-Béguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, Boris Köpf, and Daniel Jones. Bayesian Estimation of Differential Privacy. In ICML, 2023. Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. PrivSyn: Differentially Private Data Synthesis. In USENIX Security, 2021. Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal Accounting of Differential Privacy via Characteristic Function. In AISTATS, 2022.

Preprint

P ROOFS AND A NALYSIS OF B OUNDED R ANGE M ECHANISMS

A.1

BR TO f -DP, PRIVACY PROFILES AND PLD

The proof of the theorem rests on one result, which Dong et al. (2020) establish in the course of proving their reduction to generalized randomized response (their Lemma 4.1). Lemma A.1 (Dong et al., 2020). Suppose that a mechanism M : 2D → Y satisfies ν-BR. Then, for any S ≃ S ′ there exists 0 ≤ t ≤ ν such that for any test ϕ : Y → {0, 1}, we have: βϕ ≥ max{1 − et αϕ , et−ν (1 − αϕ )}.

(5)

Moreover for each αϕ ∈ [0, 1], there exists the mechanism, such that the inequality turns to the equality. We show the result next. Theorem 3.1. Let M (·) satisfy ν-BR. Then M (·) satisfies f -DP and (ε, δ(ε))-DP for all ε ∈ R, with  ε ≤ −ν, eε ,  1 − 2 ν/2 1−α e −eε/2 ) ( (2) f (α) = , δ(ε) = , −ν < ε < ν, eν −1  αeν + 1 − α  0, ε ≥ ν. Moreover, M (·) is dominated by the PLD with density: gν (x) = Dν ex/2 1[−ν,ν] (x),

−1 where Dν = 12 eν/2 − e−ν/2 .

(3)

These bounds are tight over the class of ν-BR mechanisms: for every α ∈ [0, 1] (respectively, every ε ∈ R) there exist a ν-BR mechanism and a pair S ≃ S ′ that attain f (α) (respectively, δ(ε)). Proof. We prove the statements in three main steps. The f -DP trade-off function and its tightness. To show the result, for a given α it suffices to find the smallest Lemma A.1 bound for all t ∈ [0, ν]: f (α) = min max{1 − et α, et−ν (1 − α)}. t∈[0,ν]

(6)

As the first term is decreasing in t, and the second one is increasing, the optimal value must occur at their intersection. Equating the two terms and solving for t we get: 1 − et α = et−ν (1 − α) ⇒ et =

1 . α + (1 − α)e−ν

(7)

Substituting et into Eq. (6), we have: f (α) = 1 −

α (1 − α)e−ν 1−α = = . −ν α + (1 − α)e α + (1 − α)e−ν αeν + 1 − α

(8)

The tightness follows from the fact that each point (α, f (α)) is attainable by Lemma A.1. From f -DP to privacy profile.

1−α , and write Let a = eν − 1, so f (α) = 1+aα

δ(ε) = sup g(α), where g(α) = 1 − eε α − f (α). α∈[0,1] ν

e ′′ Concavity. As f ′ (α) = − (1+aα) > 0, the function g is concave. Its derivative g ′ (α) = 2 and f ν

e ε ′ ν ε ′ −ν − eε . (1+aα)2 − e decreases from g (0) = e − e to g (1) = e

Boundary cases. 14

Preprint

If ε ≥ ν, then g ′ ≤ 0 throughout, so δ = g(0) = 0. If ε ≤ −ν, then g ′ ≥ 0 throughout, so δ = g(1) = 1 − eε .

Interior case: |ε| < ν. In this case, g ′ (α∗ ) = 0 at 1 + aα∗ = s ≜ e(ν−ε)/2 ∈ (1, eν ). At this point, ν ν f (α∗ ) = e as−s , and eε s = es = e(ν+ε)/2 . Therefore: eν/2 − eε/2 a − eε (s − 1) − (eν − s)/s eν + eε − 2e(ν+ε)/2 δ(ε) = = = a eν − 1 eν − 1

2 .

At ε = ±ν this equals 0 and 1 − e−ν respectively, which matches the boundary cases. The tightness follows from the tightness of the tradeoff function. From the privacy profile to PLD. If δ(ε) is twice-differentiable profile function, then by Sommer et al. (2019), we have that g = δ ′′ − δ ′ is the density of PLD. On (−ν, ν), differentiating δ(ε) = eν − 2e(ν+ε)/2 + eε /(eν − 1) gives: eε − 12 e(ν+ε)/2 − eε − e(ν+ε)/2 eν/2 ′′ ′ δν − δν = = eε/2 = Dν eε/2 , (9) eν − 1 2 (eν − 1) where 2 eν/2 − e−ν/2 = 2e−ν/2 eν − 1 gives Dν =

1 2

eν/2 − e−ν/2

eν/2 . 2 (eν − 1)

(10)

Observe that outside of the interval [−ν, ν], the density vanishes: δ(ε) ≡ 0 on (ν, ∞), and on (−∞, −ν) we have δν′′ − δν′ = −eε + eε = 0.

Next, we provide several observations about these results. Dominating PLD of a ν-BR mechanism corresponds to 2ν-BR. The dominating PLD gν in Theorem 3.1 is supported on [−ν, ν], so the corresponding mechanism is, surpisingly, 2ν-BR and not ν-BR, as one would expect. This is because a pair dominating the whole class, for all neighbouring datasets, must have privacy loss reaching up to ν, and, applying the same argument to the reversed pair, reaching down to −ν. Consequently, no dominating pair with privacy loss having bounded range ν, and thus no single ν-BR mechanism, dominates the entire class of BR mechanisms: every point of the bounds in Theorem 3.1 is attained by some ν-BR mechanism, yet no single mechanism attains all of them simultaneously. This contrasts with, e.g., the Laplace and Gaussian mechanisms, including their subsampled versions, whose tightly dominating pairs are realized by the mechanism itself on a worst-case pair of inputs. Suboptimality of the PLD analysis. Theorem 3 of Dong et al. (2020) provides the exact optimal privacy profile for the homogeneous non-adaptive composition of k mechanisms that are ν-BR. At k = 1, the two results coincide. For any k > 1, however, the PLD approach of the k-fold convolution of gν should be larger (i.e., worse guarantees), as the result from Dong et al. is optimal for the homogeneous composition of BR mechanisms. At the same time, the PLD analysis has an important advantages over the optimal expression: It enables simple composition with any mechanisms that also support PLD analyses, unlike the optimal expression that only works for homogenous compositions of BR mechanisms. The looseness is thus the price of that flexibility. Despite the suboptimality, PLD analysis is tighter than zCDP in low-composition regimes. In Fig. 6 we show empirical evaluations illustrating that, under homogeneous composition of BR mechanisms, for some number of compositions, zCDP provides a better (ε, δ)-DP bound. The explanation is that both are upper bounds and the tight PLD of BR is not bounded-range itself, thus it might have larger zCDP. 15

Preprint

ν = 0.1

ν = 0.25

ν = 0.5

2.5 5

0.8 2.0 0.6

analysis

1.5

0.4

1.0

0.2

0.5

Num. of compositions

Opt. PLD zCDP

Num. of compositions

Figure 6: The DP ε at δ = 10−5 reported using the PLD (ours), zCDP (Harrison & Manurangsi, 2026a), and optimal (Dong et al., 2020) analyses for the compositions of homogeneous BR mechanisms. Simple form of a TV privacy guarantee. We observe an interesting form in terms of total-variation (TV) privacy (see, e.g., Geng & Viswanath, 2015; Barber & Duchi, 2014; Kulynych et al., 2022): An algorithm satisfies η-TV privacy if it satisfies (0, η)-DP. TV is not a useful privacy notion on its own, but it provides simple forms of risk and generalization bounds (Cherubin et al., 2024; Kulynych et al., 2025). For the classical notion of (ε, 0)-DP, Kairouz et al. (2015) showed that an (ε, 0)-DP mechanism satisfies η-TV privacy with: η=

eε − 1 = tanh(ε/2). eε + 1

(11)

The conversion from BR to TV privacy is as follows: Corollary A.1. Suppose that a mechanism M (·) satisfies ν-BR. Then, it satisfies η-TV privacy with: ν

η=

e2 − 1 = tanh(ν/4). ν e2 + 1

Curiously, this is exactly the conversion from ε-DP to TV privacy from Eq. (11) with a difference of a factor of two. A.2

PLD OF L APLACE MECHANISM AS A MIXTURE OF RR AND BR

Next, we discuss an interesting relationship of the result in Theorem 3.1 to the PLD of the Laplace mechanism. We write Lapν for the Laplace mechanism of scale 1/ν on a statistic of sensitivity 1, which is ν-DP, and let ωνLap denote its PLD. Define the following distribution:  eν  ν, w.p. , 1 + eν ωνRR := (12) 1  −ν, w.p. , 1 + eν which is the PLD of the standard randomized response (RR) mechanism with parameter ν, which tightly dominates the class of ν-DP mechanisms (Kairouz et al., 2015), and let ωνBR be the PLD with density gν of Theorem 3.1. All three are supported on [−ν, ν]. The Laplace PLD is well-known: Lemma A.2 (Sommer et al., 2019, App. A.3). ωνLap is the measure on [−ν, ν] consisting of two atoms, Pr ωνLap = −ν = 21 e−ν , (13) Pr ωνLap = ν = 12 , together with an absolutely continuous part on (−ν, ν) of density 1 −ν/2 w/2 e . 4 e

(14)

Next, we show the that the PLD of Laplace mechanism is a mixture of the PLD of randomized response and bounded range: 16

Preprint

Proposition A.1. For every ν > 0, ωνLap = λν ωνRR + (1 − λν ) ωνBR ,

λν =

1 + e−ν , 2

(15)

as an identity of distributions on R. Proof. By Lemma A.2 the atoms carry total mass 12 (1 + e−ν ) = λν , and after normalisation their 1 eν masses are those of ωνRR , since 1/2 λν = 1+e−ν = 1+eν . The continuous part carries the remaining mass: Z ν 1 −ν/2 ew/2 dw = 21 1 − e−ν = 1 − λν , (16) 4e

−ν 1 −ν/2 w/2 e and normalising its density gives 41−λν ew/2 = 2 eν/2e −e−ν/2 = Dν ew/2 , i.e. exactly gν . ( )

Because δ(ε) = E (1 − eε−ω )+ is linear in the law of ω, the mixture form of (15) also extends to privacy profiles. Corollary A.2. For every ε ∈ R, δLapν (ε) = λν δωνRR (ε) + (1 − λν ) δν (ε) ≥ δν (ε),

(17)

that is, ωνBR ⪯ ωνLap . In particular the Laplace PLD is itself a valid, but strictly loose, dominating PLD for the ν-BR class. Proof. The equality is linearity of δ in the mixture. Since ωνRR dominates every ν-DP mechanism (Kairouz et al., 2015), we have δωνRR ≥ δν pointwise. Substituting this into the equality and using λν + (1 − λν ) = 1 gives the inequality. A.3

BR TO GDP

In this section, we prove the GDP guarantee for BR mechanisms: Theorem 3.2. Suppose that a mechanism M (·) satisfies ν-BR. Then, it also satisfies µ-GDP with: 1 −1 µ = −2Φ . (4) eν/2 + 1 First, we make use of the properties of the inverse Mills ratio. Proposition A.2 (Sampford, 1953). The inverse Mills ratio λ(t) ≜ φ(t)/Φ(t), where φ(t) is the density of the standard Normal distribution, is convex on R. In particular, λ′ is nondecreasing. We express the statement in Theorem 3.2 as a condition in terms of an expression log (Φ(t/2)/Φ(−t/2)), which has the following properties: Φ( /2) ′ Lemma A.3. Let L(t) ≜ log Φ(− t/2) . Then, L is odd and differentiable. Its derivative L is even, and nondecreasing on [0, ∞). t

Proof. Oddness is immediate from L(−t) = log Φ(−t/2) Φ(t/2) = −L(t). Differentiating, we get: d t d t φ(t/2) φ(−t/2) 1 t t L′ (t) = log Φ − log Φ − = + = λ + λ − , dt 2 dt 2 2 Φ(t/2) 2 Φ(−t/2) 2 2 2 using φ(−s) = φ(s). The derivative L′ is even as L is odd. Finally, for any t ≥ 0, d ′ 1 ′ t t L (t) = λ − λ′ − ≥ 0, dt 4 2 2 as λ′ is nondecreasing by Proposition A.2 and t/2 ≥ −t/2 for t ≥ 0. Finally, we can show the proof of Theorem 3.2. 17

Preprint

Proof. To prove the statement, we need to show that we have, for any α ∈ [0, 1]: Φ(Φ−1 (1 − α) − µ) ≤

1−α , αeν + 1 − α

(18)

where µ is defined as in Eq. (4). To accomplish this, we will simplify this condition to a form that is more amenable to analysis. For this, first, let us write down ν in terms of µ by solving Eq. (4): µ 1 = ν . Φ − 2 e2 + 1 As Φ(t) = 1 − Φ(−t), we have that: Φ

µ 2

1 e2 =1− ν = ν . e2 + 1 e2 + 1

Dividing the two expressions, we have: ν Φ(µ/2) = e2 . Φ(−µ/2)

Using the definition of L(t) in Lemma A.3, we thus have: ν = 2L (µ) . Next, denoting by z = Φ

−1

(19)

(1 − α), so that α = 1 − Φ(z) = Φ(−z), we have: Φ(z − µ) ≤

Φ(z) . Φ(−z)eν + Φ(z)

(20)

Observing that the denominator in r.h.s. is always positive, we can multiply both sides: Φ(z − µ)Φ(−z)eν + Φ(z − µ)Φ(z) ≤ Φ(z). Rewriting to group the Φ(z) terms: Φ(z − µ)Φ(−z)eν ≤ Φ(z) (1 − Φ(z − µ)) = Φ(z)Φ(µ − z). Taking logarithms on both sides: log Φ(z − µ) + log Φ(−z) + ν ≤ log Φ(z) + log Φ(µ − z) Φ(z − µ) Φ(z) ν + log ≤ log . Φ(µ − z) Φ(−z) Using the definition of L(t) above and the form of ν in Eq. (19): 2L (µ) ≤ L(2z) − L(2z − 2µ).

Next, to derive a useful form, we write z = µ2 + u2 for some u ∈ R: 2L (µ) ≤ L (u + µ) − L(u − µ). As L is odd by Lemma A.3, we have −L(u − µ) = L(µ − u). Therefore, the condition in Eq. (18) that we need to show is equivalent to the following: D(u) ≜ L(µ + u) + L(µ − u) − 2L(µ) ≥ 0

∀u ∈ R.

(21)

This form is easier to analyze. We start by observing that, as D is even, we have D(u) = D(|u|) for any u ∈ R, thus it suffices to consider u ≥ 0. Moreover, observing that D(0) = 0, it suffices to show that D is nondecreasing on [0, ∞). Its derivative is: D′ (u) = L′ (µ + u) − L′ (µ − u).

By Lemma A.3, L′ is even and nondecreasing on [0, ∞). This implies that L′ (a) ≥ L′ (b) whenever |a| ≥ |b|. As |µ + u| ≥ |µ − u| for µ, u ≥ 0, we get D′ (u) ≥ 0, and the claim follows. 18

Preprint

A DDITIONAL ACCOUNTING R ESULTS

B.1

P OISSON S UBSAMPLING FOR A RBITRARY P RIVACY L OSS D ISTRIBUTIONS

We present a novel method for converting a privacy guarantee for an arbitrary mechanism to a privacy guarantee for a Poisson subsampled version of that mechanism, which is compatible with modern privacy accounting libraries such as dp accounting. Our method operates by representing the privacy guarantee as a privacy profile. Although we could then convert the privacy profile to a PLD representation, we found empirically that in this case the PLD approach is less numerically stable to apply the conversion to than the δ(ε) representation. R We recall the hockey-stick divergence has a form Hα (P, Q) = (P (x) − αQ(x))+ dx, and if a dominating pair (P, Q) for M (·) satisfies Heε (P, Q) ≤ δ then M (·) is (ε, δ)-DP. Finally, Theorem 11 of Zhu et al. (2022) shows that if (P, Q) is a dominating pair for the unsampled mechanism in the remove direction, then (P ′ , Q), where P ′ = q · P + (1 − q) · Q, is a dominating pair for Poisson-subsampled mechanism with sampling probability q in the remove direction, and vice-versa in the add direction. The following theorem gives a conversion from hockey-stick divergences between P, Q to hockeystick divergences between P ′ , Q, which by the above facts suffices to convert a privacy profile for a non-subsampled mechanism to a privacy profile for its Poisson-subsampled counterpart. Theorem B.1. Let P ′ = q · P + (1 − q) · Q. Then: ( q · H eε +q−1 (P, Q) if eε > 1 − q, ′ q Heε (P , Q) = 1 − eε otherwise. ( 1 (1 − eε (1 − q)) · H eεε ·q (Q, P ) if eε < 1−q , 1−e (1−q) Heε (Q, P ′ ) = 0 otherwise. Proof. We have: Z

′

H (P , Q) = eε

′

(P (y) − e Q(y))+ dy =

(q · P (y) + (1 − q − eε )Q(y))+ dy.

If eε ≤ 1 − q then 1 − q − eε ≥ 0 and: Z (q · P (y) + (1 − q − eε )Q(y))+ dy Z = q · P (y) + (1 − q − eε )Q(y)dy Z Z =q P (y)dy + (1 − q − eε ) Q(y)dy =q + 1 − q − eε = 1 − eε .

Otherwise:

′

(q · P (y) − (eε + q − 1)Q(y))+ dy Z eε + q − 1 = q (P (y) − Q(y))+ dy = q · H eε +q−1 (P, Q), q q

Heε (P , Q) =

Similarly we have: ′

Heε (Q, P ) =

′

(Q(y) − e P (y))+ dy =

((1 − eε (1 − q)) · Q(y) − eε q · P (y))+ dy.

1 If eε < 1−q then:

((1 − eε (1 − q)) · Q(y) − eε q · P (y))+ dy. Z eε q =(1 − eε (1 − q)) (Q(y) − · P (y))+ dy 1 − eε (1 − q) =(1 − eε (1 − q))H eεε q (Q, P ), 1−e (1−q)

Preprint

Otherwise, 1 − eε (1 − q) ≤ 0 and so: Z Z ((1 − eε (1 − q)) · Q(y) − eε q · P (y))+ dy = 0 dy = 0.

B.2

E XACT C HARACTERIZATION OF P RIVATE PARTITION S ELECTION

In this section, we present characterizations of mechanisms such as the Threshold Gaussian and Threshold Laplace (Gopi et al., 2020) for private partition selection. It rests on the following result: Lemma B.1. Let M be a mechanism with the following property: There exists P, Q such that for any inputs S ≃ S ′ where S contains an example not in S ′ , there is an event E occurring with probability at least 1 − τ such that: T (M (S)|E, M (S ′ ))(α) ≥ T (P, Q)(α) for all α ∈ [0, 1], where A|E denotes the random variable A conditioned on event E. Then P × Bern(τ ), Q × Bern(0) is a dominating pair of M , where × denotes a product distribution. Proof. We use the following fact, a corollary of Blackwell’s informativeness theorem (Blackwell, 1953): (P, Q) is a dominating pair for M (·) if and only if for any S ≃ S ′ , there is a randomized function f such that T (P ) ≡ M (S), T (Q) ≡ M (S ′ ) where ≡ denotes distributional equivalence.

Fix a S ≃ S ′ , and let T (·) be the randomized function such that M (S)|E ≡ T (P ), M (S ′ ) ≡ T (Q). By the preceding fact, it suffices to define a randomized function T ′ (·) such that T ′ (P × Bern(τ )) ≡ M (S), T ′ (Q × Bern(0)) ≡ M (S ′ ). Our function is:   T (x) if y = 0    T ′ (x, y) = x′ ∼ M (S) | Ē if y = 1 w.p. Pr[τĒ]     T (x) if y = 1 w.p. 1 − Pr[τĒ]

We have: Pr[Ē] Pr[Ē] · M (S)|Ē + 1 − T (P ) τ τ ≡ (1 − τ + τ − Pr[Ē]) · T (P ) + Pr[Ē] · M (S)|Ē

T ′ (P × Bern(τ )) ≡ (1 − τ ) · T (P ) + τ ·

≡ Pr[E] · M (S)|E + Pr[Ē] · M (S)|Ē ≡ M (S).

and more straightforwardly, T ′ (Q × Bern(0)) ≡ T (Q) ≡ M (S ′ ), completing the proof. The proof of Gopi et al. (2020, Theorem 5.1) exactly specifies an event E for their mechanism (namely, E is the event that for S ≃ S ′ and S ⊃ S ′ , M (S) is in the support of M (S ′ )), which is what implies that their policy Gaussian algorithm (that we refer to as Threshold Gaussian) is a composition of a Gaussian mechanism and a mechanism with dominating pair (Bern(τ ), Bern(0)). B.3

G ROUP P RIVACY G UARANTEES FOR BASIC P REPROCESSING M ECHANISMS

In real-world settings, individual users often contribute multiple records to the dataset. Practitioners typically handle this by enforcing hard contribution bounding, randomly truncating each user’s history to at most one record (K = 1). While conceptually simple, contribution bounding introduces a truncation bias. An alternative is to retain up to K > 1 records per user and evaluate the resulting user-level guarantee via group privacy. A user with K records contributes up to K× more signal to linear queries, equivalently the sensitivity increases by K, requiring K× more noise to preserve the same signal-tonoise ratio/privacy guarantee. Below, we formalize how group privacy plumbs through our unified framework across each primitive class. 20

Preprint

• Gaussian Mechanism: If a user contributes at most K records, the global L2 sensitivity of a marginal scales by at most K. Under Gaussian Differential Privacy (GDP), the guarantee scales strictly as µ → Kµ. The dominating pair remains Gaussian (GKµ ), retaining exact hypothesistesting duality. • Exponential Mechanism: When each record can alter the selection score by at most ∆s, K records alter the score by at most K∆s, scaling the effective privacy parameter ε → Kε. • Threshold Gaussian: A user with K records can alter the counts of measurements by a total of K across all measurements. After the partition selection primitive, this mechanism is just a Gaussian mechanism and thus we can reduce to the above analysis for group privacy of the Gaussian mechanism. For partition selection at cutoff θ, the (0, τ )-DP failure event corresponds to the probability that a measurement with zero count in S ′ exceeds the threshold θ. In the worst case, all K additional records contribute to measurements with zero count in S ′ . The probability of one of these measurements being released can be formulated as: ! j Y τ (K) = max 1− (1 − pki ) , k1 ≥...≥kj ≥1 k1 +···+kj =K

i=1

where pk is the probability that a record with count k is released by the partition selection mechanism: θ−k pk ≜ = 1 − Φ . σ When e.g. K ≤ 46, there are less than 105 distinct terms in the max defining τ (K) and hence evaluating τ (K) via brute-force enumeration can be done reasonably efficiently. Calibrating θ (possibly jointly with σ) to achieve a desired failure probability τ can also be done efficiently via binary search. Because every mechanism in the taxonomy admits an exact representation parameterized by K, our framework allows us to output precise privacy profiles for multiple group sizes. With this approach, we can calibrate our mechanism to any group size K, then post-hoc report the privacy profiles for any other K ′ (noting that if there are Threshold Gaussian mechanisms, we must have K ′ ≤ K). One could alternatively consider taking the record-level privacy guarantee of the composed mechanism, and trying to convert this in a black-box manner to a group privacy guarantee. For example, any f -DP mechanism satisfies f ′ -DP with respect to add-or-remove-up-to-k where f ′ (x) = 1 − (1 − f )◦k (x), ◦k denotes self-composition of a function k times. However, black-box approaches to group privacy are generally loose. Especially for mechanisms like the exponential mechanism, a black-box privacy guarantee might be pointwise tight everywhere, as in at each FPRFNR pair there is an instantiation of the mechanism and two inputs S, S ′ that achieve that FPR-FNR pair, but not “globally” tight in the sense that a single mechanism and pair of inputs achieves all the FPR-FNR pairs simultaneously. A black-box group privacy analysis might try to combine information at different FPR-FNR points that are not “globally” tight, thus giving an upper bound that no instantiation of the mechanism and inputs can realize, whereas a “white-box” group privacy analysis looking directly at M (S), M (S ′ ) for S ≃ S ′ would avoid this issue entirely. B.4

G ROUP P RIVACY OF H OMOGENOUS C OMPOSITIONS OF E XPONENTIAL M ECHANISMS

In this section, we give a group privacy guarantee of the homogenous composition of Exponential mechanisms, which is the case of the DP quantiles (Kaplan et al., 2022) in Algorithm 7. We give a privacy guarantee under “add-or-remove-up-to-k” adjacency ≃AR≤k , i.e. S ≃AR≤k S ′ if S ⊇ S ′ and S contains at most k elements not in S (or vice-versa). Theorem B.2. Any ν-BR mechanism with respect to the add-or-remove-one adjacency is kν-BR with respect to ≃AR≤k . Proof. Let S ≃AR≤k S ′ , assuming without loss of generality |S \ S ′ | = k, and let S0 = S, S1 , S2 , . . . , Sk = S ′ be a sequence of datasets where |Si − Si+1 | = 1. As the Exponential 21

Preprint

mechanism is ν-BR, for any output set E and any i we have log for some t0 , t1 , . . . , tk−1 . In turn, we have: log

Pr[M (S) ∈ E] Pr[M (S ′ ) ∈ E]

Pr[M (Si )∈E] Pr[M (Si+1 )∈E]

∈ [−ti , −ti + ν]

Pr[M (S0 ) ∈ E] Pr[M (Sk ) ∈ E] k−1 X Pr[M (Si ) ∈ E] = log , Pr[M (Si+1 ) ∈ E] i=0

= log

h P i Pk−1 k−1 which is in − i=0 ti , − i=0 ti + kν . Theorem B.3. Let g : D → [m] be any function from the data universe to [m]. Let M be the following mechanism: Given the input S, partition S into {S1 , S2 , . . . Sm } where Si = {x ∈ S : g(x) = i}, then return (M1 (S1 ), M2 (S2 ), . . . , Mm (Sm )) where each Mi is an (independent) ν-BR mechanism (with respect to add-or-remove-one). Then M is kν-BR with respect to ≃AR≤k . Proof. Let S ≃AR≤k S ′ , assuming without loss of generality |S \ S ′ | = k. Let ki be the number of elements in S \ S ′ in Si . By Theorem B.2, for some t1 , t2 , . . . tm and any i, output oi for Mi we have Mi (S)(oi ) ∈ [−ti , −ti + ki ν]. log Mi (S ′ )(oi ) Since the mechanisms are run independently and the elements in S ′ are assigned to the same subset of the partition whether we receive input S or S ′ , we have for any output o = (o1 , o2 , . . . om ) for M : X m Mi (S)(oi ) M (S)(o) = log log M (S ′ )(o) Mi (S ′ )(oi ) i=1 " m # " m # m m m X X X X X ∈ − ti , − ti + ν ki = − ti , − ti + kν . i=1

i=1

Theorem B.4. Algorithm 7 satisfies any privacy guarantee satisfied by the composition of a kε1 -BR, kε2 -BR, . . . , and kεL -BR mechanisms. Proof. We can assume the mechanism is run in a “top-down” fashion, i.e. we run all mechanisms at ℓ = i before running any mechanism at level ℓ = i − 1. Viewing the concatenation of all mechanisms being run at ℓ = i as a single mechanism, Algorithm 7 is then just an adaptive composition of the per-level mechanisms. Each per-level mechanism is exactly a partition of the dataset and a run of the exponential mechanism on each subset of the partition, exactly as described/analyzed by Theorem B.3, giving the theorem.

A LGORITHMS AND P IPELINE D ETAILS

In this section, we provide additional algorithmic and pipeline details for the methods introduced in Section 4, including AIM-GDP, DP preprocessing, and MixCal. For reference, Table 5 summarizes the DP mechanisms relevant to data preprocessing and tabular synthesis considered in our pipelines. C.1

AIM-GDP

Algorithms 1 to 6 present the original AIM and our AIM-GDP variant. We introduce AIM-GDP as the base synthetic data mechanism in Section 4 and evaluate it in Section 5, both in isolation and as a component of the end-to-end and multimodal pipelines. 22

Preprint

Mechanism

Param

Base Events

Fully Adaptive

Accounting

Preprocessing & Domain Discovery DP Quantiles (Gillenwater et al., 2021) DP Quantiles (Kaplan et al., 2022) Noisy Histogram Threshold Gaussian (Gopi et al., 2020)

ε ε1 , . . . , εl σ σ, δ

No No No No

ADP zCDP GDP GDP

Optimal Partition (Desfontaines et al., 2022)

ε, δ

ADP

RDP Partition (Harrison & Manurangsi, 2026b)

σ, δ

Exponential Exponential Gaussian Gaussian Failure Laplace Failure Gaussian Failure

RDP

Base Mechanism AIM (McKenna et al., 2022)

Yes

zCDP

AIM-GDP (Algorithm 4)

Yes

GDP

GEM (Liu et al., 2021)

zCDP

RAP (Aydöre et al., 2021)

zCDP

PrivSyn (Zhang et al., 2021) MST (McKenna et al., 2021)

ρ ρ

Exponential Gaussian Exponential Gaussian Exponential Gaussian Exponential Gaussian Gaussian Exponential Gaussian

No No

zCDP zCDP

Language Model Finetuning Poisson DP-SGD (Abadi et al., 2016) Random Allocation DP-SGD (Feldman & Shenfeld, 2025) DP-BandMF (McKenna, 2025)

σ σ σ

Sub. Gaussian Sub. Gaussian Corr. Gaussian

No No No

RDP, PLD PLD Monte Carlo

Table 5: Classification of differentially private synthetic data mechanisms across domain discovery, tabular synthesis, and language model finetuning pillars.

C.2

DP P REPROCESSING

C.2.1

DP Q UANTILES

Algorithm 7 shows the recursive-median DP quantile mechanism from Kaplan et al. (2022) used to discretize numerical attributes in our end-to-end pipeline. We describe it in Section 4, and evaluate the pipeline in Section 5. C.2.2

DP O PEN -S ET PARTITION S ELECTION

Algorithm 8 presents the Threshold Gaussian (Gopi et al., 2020) partition-selection mechanism used for private domain discovery of open-set categorical attributes. We describe it in Section 4, and evaluate the pipeline in Section 5. C.2.3

M EASUREMENT R ECYCLING FOR E ND - TO -E ND S YNTHETIC DATA

Beyond tight accounting, we can use an additional enhancement that allows us to skip the dedicated one-way marginal measurement step in AIM-GDP by reusing information measured during the preprocessing step of mixed tabular domains (open set discovery and quantile-based discretization). A naı̈ve implementation would treat preprocessing as disjoint from the application of the base mechanism by spending a fraction of the privacy budget to establish discrete domains, and a separate fraction of the privacy budget measuring one-way marginals. This is wasteful, as it pays twice for single-attribute information and diminishes the remaining budget available for capturing multivariate interactions. Rather than measuring one-way marginals again, we eliminate this step entirely by recycling the private information obtained during preprocessing. Under the hood, synthetic data mechanisms like AIM rely on estimation algorithms like PGM (McKenna et al., 2019). These attempt to estimate the discrete data distribution p̂ given noisy linear measurements of its marginals of the form y = Qp + ξ, where p denotes the true data vector, Q is a linear query matrix, and ξ is zero-centered noise with standard deviation σ. Whereas 23

Preprint

Algorithm 1 AIM

Algorithm 4 AIM-GDP

Dataset D, workload privacy parameter ρ (zCDP)

1: Input:

Dataset D, workload privacy parameter µ2 (GDP)

1: Input:

2: Output: Synthetic dataset D̂ 3: Hyper-Parameters: MAX-SIZE=80MB,

T = 16d, α = 0.9 p 4: σ0 = T /(2 α ρ) 5: ρused = 0 6: t = 0 7: Initialize P p̂t using Algorithm 2 8: wr = s∈W cs | r ∩ s | p 9: σt+1 ← σ0 νt+1 ← 8(1 − α)ρ/T 10: while ρused < ρ do 11: t=t+1 12: ρused ← ρused + 18 νt2 + 2σ1 2

T = 16d, α = 0.9 p

νt+1 ← b−1 (1 − α)µ2 /T 10: while µ used < µ2 do 11: t=t+1 12: µ2 used ← µ2 used + b(νt ) + σ12

13: n Ct

13:

4: σ0 = T /(α µ2 ) 5: µ2 used = 0 6: t = 0 7: Initialize P p̂t using Algorithm 5 8: wr = s∈W cs | r ∩ s | 9: σt+1 ← σ0

= o rt ∈ W+ | JT-SIZE(r1 , . . . , rt ) ≤ ρused ρ · MAX-SIZE

14:

15:

select rt ∈ Ct using the exponential mechanism with: p qr (D) = wr ∥Mr (D) − Mr (p̂t−1 )∥1 − 2/π·σt ·nr

p̂t = arg min p∈S

i=1

σi

14:

select rt ∈ Ct using the exponential mechanism with: p qr (D) = wr ∥Mr (D) − Mr (p̂t−1 )∥1 − 2/π·σt ·nr measure marginal on rt : ỹt = Mrt (D) + N (0, σt2 I)

16:

estimate data distribution using PGM: t X 1

Ct = 2 rt ∈ W+ | JT-SIZE(r1 , . . . , rt ) ≤ µ µused · MAX-SIZE 2

15:

measure marginal on rt : ỹt = Mrt (D) + N (0, σt2 I)

16:

estimate data distribution using PGM: p̂t = arg min

∥Mri (p) − ỹi ∥2

p∈S

t X 1 i=1

σi

∥Mri (p) − ỹi ∥2

17: anneal νt+1 and σt+1 using Algorithm 6 18: generate synthetic data D̂ from p̂t using

17: anneal νt+1 and σt+1 using Algorithm 3 18: generate synthetic data D̂ from p̂t using

PGM

PGM 19: return D̂

19: return D̂

Algorithm 2 Initialize pt (subroutine of Algorithm 1)

Algorithm 5 Initialize pt (subroutine of Algorithm 4)

1: for r ∈ {r ∈ W+ | |r| = 1} do 2: t = t + 1 σt ← σ0 rt ← r 3: ỹt = Mr (D) + N (0, σt2 I)

µ2 used ← µ2 used + σ12 t Pt 2 5: p̂t = arg minp∈S i=1 σ1i ∥Mri (p) − ỹi ∥2

ρused ← ρused + 2σ1 2 t Pt 2 5: p̂t = arg minp∈S i=1 σ1i ∥Mri (p) − ỹi ∥2

Algorithm 3 Budget annealing (subroutine of Algorithm 1) p 1: if ∥Mrt (p̂t ) − Mrt (p̂t−1 )∥1 ≤ 2/π · σt · nrt then 2: νt+1 ← 2 · νt 3: σt+1 ← σt /2 4: else 5: νt+1 ← νt 6: σt+1 ← σt 2 7: if (ρ − ρused ) ≤ 2 2σ12 + 18 νt+1 then t+1 p 8: νt+1 = 8 · (1 − α) · (ρ − ρused ) p 9: σt+1 = 1/(2 · α · (ρ − ρused ))

Algorithm 6 Budget annealing (subroutine of Algorithm 4) p 1: if ∥Mrt (p̂t ) − Mrt (p̂t−1 )∥1 ≤ 2/π · σt · nrt then 2: νt+1 ← 2 · νt 3: σt+1 ← σt /2 4: else 5: νt+1 ← νt 6: σt+1 ← σt 7: if (µ2 −µ2 used ) ≤ 2 σ21 + b(νt+1 ) then t+1

8: 9:

νt+1 = b−1 (1 − α) · (µ2 − µ2 used ) p σt+1 = 1/(α · (µ2 − µ2 used ))

Figure 7: Left: the original AIM with zCDP accounting ( orange ). Right: AIM-GDP, the same algorithm with the budget tracked in GDP units µ2 , which compose additively ( teal ). The Gaussian mechanism with noise scale σ is exactly 1/σ-GDP, and the exponential mechanism with parameter ν is 2 a ν-BR mechanism with exact squared GDP budget b(ν) = 2Φ−1 eν/21 +1 given by Theorem 3.2, Φ( /2) with b−1 (µ2 ) = 2 ln Φ(− µ/2) denoting its inverse used for calibrating the parameter to a given budget. µ

Preprint

Algorithm 7 DP Quantile Discretization via Recursive Medians Require: 1D histogram c = (c0 , . . . , cK−1 ) ∈ NK , tree depth L, per-level privacy budgets {ϵℓ }L ℓ=1 . Ensure: Set of discretized bin cutpoints E ⊂ {0, . . . , K − 1}. 1: function R ECURSIVE B ISECTION(lo, hi, ℓ) 2: if ℓ = 0 then 3: return ∅ Phi−1 ▷ Target median rank within current sub-interval 4: r ← 12 j=lo cj 5: for each candidate split v ∈ {lo, . . . , hi − 1} do Pv−1 Pv 6: Lv ← j=lo cj , Rv ← j=lo cj ▷ Cumulative rank bounds of cell v 7: u(v) ← − max (0, Lv − r, r − Rv ) ▷ Distance to target median rank

8: 9: 10: 11:

Sample v ∗ ∈ {lo, . . . , hi − 1} w.p. ∝ exp (ϵℓ · u(v)) Eleft ← R ECURSIVE B ISECTION(lo, v ∗ , ℓ − 1) Eright ← R ECURSIVE B ISECTION(v ∗ , hi, ℓ − 1) return Eleft ∪ {v ∗ } ∪ Eright

▷ Exp. Mech. with ∆u = 1/2

12: return R ECURSIVE B ISECTION(0, K, L)

Algorithm 8 DP Open-Set Partition Selection via Threshold Gaussian Require: Partition counts y ∈ N|V| over active keys V = {k : yk ≥ τmin }, noise scale σ, target failure probability δ, minimum threshold τmin . b noisy partition counts ỹ, and closed-domain mapping M. Ensure: Discovered vocabulary V, 1: T ← τmin + σΦ−1 (1 − δ) ▷ Threshold cutoff bounding false positives to ≤ δ per empty bin b ← ∅, ỹ ← ∅ 2: V 3: for each active partition key k ∈ V do 4: Sample ξk ∼ N (0, σ 2 ) 5: ỹk ← yk + ξk ▷ Perturb count with Gaussian noise 6: if ỹk ≥ T then b←V b ∪ {k} 7: V ▷ Retain key in discovered vocabulary 8: ỹ[k] ← ỹk b ∪ {[OTHER]} 9: Closed vocabulary domain D ← V b else [OTHER] 10: Construct mapping M(k) = k if k ∈ V ▷ Collapse unselected tail categories b 11: return Discovered vocabulary V, noisy counts ỹ, mapping M

closed-set categorical attributes directly yield complete noisy histograms and thus total dataset size estimates, open-set and numerical attributes provide only partial information that we treat as follows: b = {k1 , . . . , km } and an unmeasured tail • For open-set categories with discovered frequent items V bucket at index 0, partition selection provides noisy counts ỹ ∈ Rm . We incorporate these as a partial linear measurement with query matrix Qopen = [0m×1 Im ], which depends only on the observed categories while leaving the unmeasured tail unconstrained. • For continuous attributes handled via quantile discretization, the distribution over bins is approximately uniform by definition of quantiles. Given an estimate of the total dataset size Ñ , we construct an identity query Qnum = IK with target ynum = Ñ/K · 1K and (heuristic) uncertainty σnum ∝ 1/√ρ calibrated to the ρ-zCDP quantile budget. Accounting for precisely what was measured during preprocessing allows downstream models to initialize one-way marginals for free, preserving the entire synthesis budget for modeling higher-order dependencies. When applied to 1D data, the improvement from measurement recycling was easily observable and matches expectations, as shown in Fig. 8. When we applied this to an end-to-end synthetic data mechanism like AIM, however, we observed no meaningful difference in performance between the 25

Preprint

Non-recycled

Recycled (ours)

Open-Set Categorical

1-way marginal error ←

1.4

×10−3

Numerical

0.16 1.0

0.12

0.6

0.08

0.2

0.04 2−7 2−6 2−5 2−4 2−3 2−2

2−7 2−6 2−5 2−4 2−3 2−2

Privacy budget ρ

1 Figure 8: One-way marginal measurement recycling after preprocessing. Algorithm 9 MixCal Require: Target guarantee (ε⋆ , δ ⋆P ); mechanism family Mi (·) each parameterized by additive budget bi ; weights w1 , . . . , wk with i wi = 1 ▷ privacy cost of the composition at budget b

1: function PLDACCOUNTINGδ (b) 2: for i = 1, . . . , k do 3: bi ← wi b 4: Calibrate Mi (·) to satisfy bi privacy. 5:

▷ allocate the budget additively

return ε of M1 ◦ · · · ◦ Mk at δ ∗

6: Binary search for the largest b with PLDACCOUNTINGδ⋆ (b) ≤ ε⋆ . 7: return a calibrated mechanism M = M1 ◦ · · · ◦ Mk .

recycling approach and the naive baseline that splits the budget between preprocessing and one-way marginal measurement. We therefore consider this a negative result. Future work, however, could investigate whether there exist settings where marginal recycling provides benefits. C.3

MixCal

Algorithm 9 formalizes MixCal, which we introduce in Section 4 to calibrate the component mechanisms of heterogeneous compositions while retaining tight PLD accounting. In MixCal, we introduce a budget parameter b that should represent an additive privacy notation like zCDP or GDP. Suppose that a budget split for a given component is bi . Then, in MixCal, we calibrate the component to satisfy this privacy guarantee bi . A practically useful property of MixCal is that the correctness of the final guarantee only depends on the correctness of PLD accounting. Therefore, intermediate calibration steps to budget shares need only be approximate. For instance, when using GDP as the budget notion, we can calibrate a Gaussian mechanism exactly to its budget share bi = µi by setting σ = 1/µi , but when calibrating Threshold Gaussian with a relatively small probability of failure, e.g., τ < 10−5 , using the results of Appendix B, we can ignore the failure term and treat the mechanism as Gaussian for the purposes of budget allocation in MixCal. For instance, using a zCDP interpretation of bi , we could use: q • Gaussian Mechanism: σ = 2b1i (exact) √ • Exponential Mechanism ν = 8bi (pessimistic) 26

Preprint

• Threshold Gaussian: σ =

1 2bi (approximate)

• DP-SGD noise multiplier: σ = assuming no amplification).

T 2bi , where T is the number of iterations (approximate;

A DDITIONAL E XPERIMENT D ETAILS

D.1

D ETAILS OF THE ACCOUNTING C OMPARISONS

In this section, we describe the setups behind Fig. 4. In both panels, we report εzCDP − εours at δ = 10−5 , so positive values mean that our analysis is tighter. For the zCDP analysis of the Exponential mechanism, we use the tightest available expression due to Harrison & Manurangsi (2026a): ν e −1 ν + log − 1, ρBR (ν) = ν e +1 ν and convert zCDP to (ε, δ)-DP with the standard numerical conversion from Canonne et al. (2020). The GDP parameter µBR (ν) of a ν-BR mechanism is given by Theorem 3.2. Left: GDP vs. zCDP in fully adaptive compositions. We consider T ∈ {1, 5, 10, 20, 50, 100} fully adaptive compositions of a Gaussian and an Exponential mechanism, which represents AIM-like workloads. We fix the zCDP cost of each pair to ρ = 0.01 and split it according to the proportion p ∈ [0.1, 0.99] allocated to the Gaussian mechanism. To split the budget between the two mechanisms, we follow the MixCal approach outlined in Appendix C. Using the standard analyses (Cesar √ & Rogers, 2021; Durfee & Rogers, 2019) for simplicity, we set the Gaussian parameter to µ = 2ρ, and the Exponential mechanism parameter to p ν = 8ρ(1 − p). For the final accounting, we use tight expressions. The GDP analysis composes the pairs as: p µtotal = T · (µ2 + µBR (ν)2 ), and the zCDP analysis uses: ρtotal = T ·

µ2 + ρBR (ν) . 2

We find that the GDP analysis is tighter when the majority of the budget of each pair is consumed by the Gaussian mechanism (e.g., in AIM, the default is p = 0.9). This directly translates into improvements in the performance of AIM-GDP, as we show in Section 5.1. Right: PLD vs. zCDP for preprocessing workloads. We consider a preprocessing-like workload with T ∈ {1, . . . , 49} features, composed non-fully-adaptively. Each feature is processed by one Exponential mechanism that satisfies ν-BR, and one Threshold Gaussian mechanism. For simplicity, we set ν = µ ∈ {0.05, 0.1, 0.15, 0.2} for all features, where µ is the GDP parameter of the Gaussian part, so a larger µ means less noise. We model the Threshold Gaussian mechanism as a composition of the Gaussian mechanism and a (0, τ )-DP mechanism with τ = 10−8 , which accounts for the failure probability of the threshold (see Appendix B). For our analysis, we convolve the PLDs of all mechanisms: T copies of the PLD from Theorem 3.1 with parameter ν, and T copies of the Gaussian PLD composed with the (0, τ )-DP event as per the 2 analysis in Appendix B. For the zCDP baseline, the total budget is ρ = T · (µ /2 + ρBR (ν)), with a corresponding accounting for the failure probability. D.2

DATASETS

For our discrete and end-to-end synthetic data experiments, we use four standard datasets from the machine learning literature that have been extensively used in prior work on DP synthetic data (see, e.g., McKenna et al., 2022; Tao et al., 2022; Annamalai et al., 2024; Ganev et al., 2025b): Adult, Fire, Page blocks, and Gas. A summary is provided in Table 6. We use two versions of each dataset: 1) a 27

Preprint

Table 6: Datasets used in our discrete/end-to-end synthetic data experiments. n is the number of training records, d the number of columns, and dnum and dcat the numbers of numerical and categorical columns, respectively. The final column reports the categorical column with the largest domain and its domain size. n

dnum

dcat

Largest categorical domain

32,561 244,106 4,378 22,191

11 10 11 11

0 0 10 10

11 10 1 1

native country (42) Station Area (46) block (2) TEY (2)

Dataset Adult Fire Page blocks Gas

adult – discrete

fire – discrete

AIM AIM-GDP (ours)

0.04

Full marginal error ←

0.05

AIM AIM-GDP (ours)

0.0150 0.0125

0.03

0.0100 0.0075

0.02

0.5

ε (log scale)

1 page blocks – discrete

gas1 – discrete

0.125

AIM AIM-GDP (ours)

0.100

Full marginal error ←

ε (log scale)

Full marginal error ←

0.5

AIM AIM-GDP (ours)

0.12 0.10

0.075

0.08

0.050

0.06

0.5

ε (log scale)

ε (log scale) 1

Figure 9: AIM-GDP vs. AIM across full marginal error across four datasets in a discrete pipeline. We report 95% bootstrap CI over the replications. fully discretized version, using uniform discretization into 16 bins, for our discrete experiments, and 2) the original, unprocessed version for our end-to-end experiments. For our multimodal experiments, we use the bioRxiv dataset, a corpus of scientific abstracts (n = 34k, average number of tokens per sample around 300). We use the filtered dataset from (Hu et al., 2026), that is, we keep only the abstracts that appear after the knowledge cutoff date of Gemma-3 family models (Aug 2024). We perform train/validation/test split and obtain a train set of size n = 28, 846. D.3

D ISCRETE S YNTHETIC DATA WITH AIM-GDP

Detailed results for all four (discrete) datasets are shown in Fig. 9, with additional diagnostic experiments on the Adult dataset presented in Figs. 10 and 11. We discuss these experiments in Section 5.1. D.3.1

ATTACK -AWARE C ALIBRATION

In the standard approach to calibrating DP mechanisms, we start with a target (ε⋆ , δ ⋆ )-DP guarantee for a small δ ⋆ , usually smaller than the size of the dataset (see, e.g., Ponomareva et al., 2023). We can then evaluate the risk due to MIAs (Kulynych et al., 2024) or other attacks (Kulynych et al., 2025) by converting (ε⋆ , δ ⋆ )-DP guarantee to f -DP via a standard conversion (Dong et al., 2022): fε,δ (α) = max{0, 1 − eε α − δ, e−ε (1 − α − δ)}. 28

(22)

35 34 33 32 31 30 29 28 27

AIM AIM-GDP (ours)

Noise (σ ) ←

Number of rounds

Preprint

AIM

AIM-GDP (ours)

Round 1

1 Figure 10: AIM-GDP vs. AIM across number of rounds and noise (σ) per round averaged across 25 runs on Adult in a discrete pipeline.

Respectively, when we want to calibrate ε⋆ to a given level of risk in terms of f -DP, i.e., (α⋆ , β ⋆ ), we solve Eq. (22) for a given small δ ⋆ . We refer to this as standard risk calibration. In attack-aware calibration (Kulynych et al., 2024), we start with the f -DP target (α⋆ , β ⋆ ), and calibrate the parameters of the DP mechanism directly to satisfy the f -DP level. In the case of a GDP mechanism, we can then solve the direct f -DP expression to derive the µ parameter that satisfies the target (α⋆ , β ⋆ ). In the case of PLD analysis, we can can run search, e.g., bisection, for the mechanism parameters until the f -DP curve dervied from the PLD (Kulynych et al., 2024) satisfies the target requirement. D.3.2

AUDITING

DP auditing empirically tests whether the privacy leakage of an implementation is consistent with its theoretical guarantee (Nasr et al., 2023; Annamalai et al., 2024). Following Ganev et al. (2026), we formulate auditing as a hypothesis-testing problem: a challenger repeatedly runs the mechanism on two neighboring datasets, and an adversary attempts to distinguish which dataset was used from the mechanism’s output. The resulting FPR and TPR define an empirical point on the privacy trade-off curve. As AIM-GDP directly satisfies GDP, we convert this point into a statistical lower bound µemp on the privacy leakage and compare it directly with the theoretical µ. We use the worst-case neighboring datasets Dout = {[0, 0, 0]}10 and Din = Dout ∪ {[1, 1, 1]}, chosen to maximize the target record’s influence on the measured marginals. We train 10,000 independent instances of AIM-GDP, equally split between Dout and Din , and generate synthetic records from each model. Unlike prior audits of AIM, we run the full AIM-GDP model, including its adaptive/data-dependent marginal selection. We consider black-box attacks using features computed from the released synthetic data, white-box attacks using the mechanism’s internal measurements, and an ensemble using both. We split the 10,000 labeled runs into 4,000 training, 2,000 validation, and 4,000 test examples, train an XGBoost classifier (Chen & Guestrin, 2016), and select the decision threshold on the validation set to maximize attack advantage (TPR − FPR). We evaluate the selected attack once on the held-out test set and use the resulting FPR/TPR with the Bayesian procedure (Zanella-Béguelin et al., 2023; Ganev et al., 2026) to obtain a 90%-posterior lower bound µemp . The resulting audit is discussed in Section 5.1. D.4

E ND - TO -E ND S YNTHETIC DATA WITH AIM-GDP, DP PREPROCESSING , AND MixCal

We show detailed results for all four (original/mixed-type) datasets in an end-to-end pipeline in Fig. 12. Additionally, we evaluate the pipeline under Poisson subsampling in simulation (Fig. 13). We discuss these in Section 5.2. D.5

G ENERATING S YNTHETIC T EXT DATA WITH LLM S AND TABULAR C ONDITIONING

We follow the conditional generation approach of Hu et al. (2026), which we summarize here. The goal is to generate a synthetic version of the bioRxiv dataset. First, Hu et al. fed each abstract in the bioRxiv dataset to Gemini-2.5-flash-lite to extract structured features. In particular, the 29

Preprint

age | hours_per_week

Selected marginal

occupation | hours_per_week age | relationship age | workclass age | education

Round

(a) 1AIM 25

age | hours_per_week

Selected marginal

occupation | hours_per_week age | relationship age | workclass age | education

Round

(b) AIM-GDP 1 (ours)

Match rate

1.00 0.75 0.50 0.25 0.00 0

Round (c) Selected marginal match rate 1

Figure 11: AIM-GDP vs. AIM across the selected marginal per round averaged across 25 runs on Adult in a discrete pipeline.

Preprint

0.04

fire – end-to-end

AIM AIM-GDP (ours)

Full marginal error ←

adult – end-to-end

AIM AIM-GDP (ours)

0.014 0.012

0.03

0.010

0.02

0.008

0.5

ε (log scale)

1 – end-to-end page blocks

gas 1– end-to-end

Full marginal error ←

0.5

AIM AIM-GDP (ours)

0.4

Full marginal error ←

0.5

AIM AIM-GDP (ours)

0.18 0.16 0.14

0.3

0.12

0.5

0.10

0.5

ε (log scale)

ε (log scale) 1

Figure 12: AIM-GDP vs. AIM across full marginal error across four datasets in an end-to-end pipeline. We report 95% bootstrap CI over the replications. 20 2

RDP PLD (ours)

−1

2−2

2−3 2−4 2−5 2−6

2−6

2−5

2−4

2−3

2−2

2−1

Poisson sampling probability p 1 Figure 13: DP ε at δ = 10−6 across Poisson sampling probabilities p = 2−k (k = 0, . . . , 6), with ρ calibrated to an un-amplified ε = 1.0 at p = 1.

following 8 features were extracted: primary-research-area, model-organism, experimental-approach, dominant-data-type, research-focus-scale, disease-mention, sample-size, research-goal. Each feature is categorical. See Figure 7 in Hu et al. (2026) for the allowed values of each category. The result is 8 categorical features for each abstract in the dataset. These features are treated as sensitive, hence AIM is run on them to generate a list of synthetic features. The next step is to condition a DP-finetuned language model on these privatized features. Here, Gemma 3 1B is fine tuned with differential privacy on the feature/abstract pairs. We used a batch size of 448 and iterations T = 512 (8 epochs). We set clipping norm c to 1. We tune the learning rate η ∈ {1 × 10−4 , 3 × 10−4 , 1 × 10−3 }, with 3 × 10−4 converging the fastest. We used a cosine decay learning rate schedule. We perform LoRA finetuning with a LoRA rank of 8, α = 16 and dropout of 0.05. Training took 3 hours on 2 A100 GPUs, where data parallel was used to parallelize training. Since the 95% quantile of the abstracts in bioRxiv had 512 tokens, we used a context length of 512. We use the MAUVE scores (Pillutla et al., 2023) as the main evaluation metric for this demonstration. We remark that we trained for a tenth as long as Hu et al. did, as they trained for 80 epochs whereas we trained for 8. Moreover, we used a smaller learning rate of 3 × 10−4 whereas they used 1 × 10−3 . While our evaluation loss values are within a tenth of (Hu et al., 2026), our MAUVE scores are 31

Preprint

smaller than (Hu et al., 2026) reported scores, likely due to this reason. Namely, we report a MAUVE score of 60% at ε = 1 for the RDP baseline, which corresponds to vanilla ACTG, where as (Hu et al., 2026) reports a little under 80%. Nevertheless, we are confident that, had we run for the full 80 epochs, we would still see improvement in our PLD approach since our approach allows for training at a smaller DP-SGD noise multiplier as reported in Table 4. Once the model was fine tuned, we used nucleus decoding to sample conditioned on the features from AIM. We used temperature T = 1.0, top-p = 0.95, top-k = 0, and a batch size of 64. We sampled Nsyn = 5,000 abstracts. Sampling took 3.5 hours on 2 A100 GPUs, where the parallelization was done by feeding half the features to condition on (2,500) to each GPU. The MAUVE score from Fig. 1a was computed between the 5,000 synthetic examples sampled from the fine tuned LLM and the 5,000 real heldout examples from the test data from bioRxiv. MAUVE scores use an embedding model. Following (Hu et al., 2026), we used Spector2 (Singh et al., 2023), a specialized sentence embedding model finetuned on abstracts of scientific papers. (Hu et al., 2026) showed that this domain-specific embedding model improved the reliability of the MAUVE scores. We repeated the ACTG training pipeline twice, once using Hu et al.’s original accounting approach, which used RDP accounting with AIM, and our proposed technique, which uses AIM-GDP and PLD accounting. The MixCal algorithm was used in the following manner. We discuss the PLD approach here. The RDP approach follows analogously. Suppose our target is for the composition of AIM-GDP and DP-SGD to satisfy (ε⋆ , δ ⋆ )-DP. Given a starting dummy budget (εdummy , δdummy ), we allocate 71% to AIM and 29% to DP-SGD following (Hu et al., 2026). By this, we mean we calibrate AIM-GDP to satisfy (0.71 · εdummy , 0.71 · δdummy )-DP, and DP-SGD to satisfy (0.29 · εdummy , 0.29 · δdummy )-DP. We then run PLD composition on the mechanism. As mentioned in the main body, the resulting PLD ε will larger than our target ε⋆ , hence we run a binary search over the dummy value of εdummy until the composed mechanisms under PLD composition satisfies our target (ε⋆ , δ ⋆ ).

Tight End-to-End Accounting for Differentially Private Synthetic Data

Analyze & explore related research in Conceptio

Related documents