Paper deep dive
Canaries in the Bank: Auditing User-Level Privacy in Private Evolution
Sai Aparna Aketi, Enayat Ullah, Shripad Gade
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/20/2026, 3:16:33 AM
Summary
This paper introduces a protocol-aware empirical audit for Private Evolution (PE), a federated learning mechanism that generates synthetic data using differentially private histograms. The authors propose an attack vector where a server manipulates the shared candidate bank by injecting probes derived from known non-private 'canary' users (either real user data or synthetic nonces). Experiments on Yelp and Sentiment140 datasets demonstrate that while natural-text-based attacks result in privacy leakage significantly below the theoretical worst-case bound, high-entropy nonce-based attacks can recover a substantial portion (up to ~67%) of the theoretical privacy budget, quantifying the gap between formal guarantees and practical leakage.
Entities (9)
Relation Signals (7)
Private Evolution → providesguarantee → Differential Privacy
confidence 98% · Private Evolution (PE) generates high-fidelity synthetic data... with a differentially private histogram
Yelp Open Dataset → usedinexperiment → Private Evolution
confidence 95% · Experiments on Yelp and Sentiment140 show...
Sentiment140 → usedinexperiment → Private Evolution
confidence 95% · Experiments on Yelp and Sentiment140 show...
Private Evolution → uses → Candidate Bank
confidence 95% · It aggregates clipped user votes over a shared candidate bank into a differentially private histogram
Natural-text attacks → achievesprivacyleakage → Below 40% of theoretical bound
confidence 90% · strongest attack with natural text... attains 0.560 and 0.682 (below 40% of εtheory)
Nonce-based attacks → achievesprivacyleakage → 67% of theoretical bound
confidence 90% · nonce-norm attains 1.110 and 1.088 (~67% of εtheory)
Opacus → implements → PRVAccountant
confidence 85% · computing the matching theoretical guarantee using Opacus’s PRVAccountant implementation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Private Evolution (PE) generates high-fidelity synthetic data in federated settings without exposing users' raw data. It aggregates clipped user votes over a shared candidate bank into a differentially private histogram, with noise calibrated to the worst-case user contribution. However, it is unclear whether an adversary can realize this worst-case privacy loss while following the PE protocol. We introduce a protocol-aware empirical audit in which the server commits to a single shared candidate bank and replaces roughly 1% of its entries with probes derived from a known, non-private canary. We evaluate eight attacks, including an unchanged-bank baseline, exact copies, plausible paraphrases, and high-entropy synthetic nonces. Experiments on Yelp and Sentiment140 show that natural-text attacks remain substantially below the theoretical DP bound, while nonce-based attacks yield considerably stronger bounds and come closest to the mechanism's privacy ceiling. These results quantify the gap between formal worst-case privacy and leakage achievable through protocol-valid candidate-bank manipulation.
Tags
Links
- Source: https://arxiv.org/abs/2609.13499v1
- Canonical: https://arxiv.org/abs/2609.13499v1
Trouble viewing inline? Open PDF directly →
Full Text
48,125 characters extracted from source content.
Expand or collapse full text
Canaries in the Bank: Auditing User-Level Privacy in Private Evolution Sai Aparna Aketi Affiliation: Meta Platforms, Inc. Enayat Ullah Affiliation: Menlo Park, USA. Shripad Gade Affiliation: aketiaparna, enayat, shripadgade@meta.com Abstract Private Evolution (PE) generates high-fidelity synthetic data in federated settings without exposing users’ raw data. It aggregates clipped user votes over a shared candidate bank into a differentially private histogram, with noise calibrated to the worst-case user contribution. However, it is unclear whether an adversary can realize this worst-case privacy loss while following the PE protocol. We introduce a protocol-aware empirical audit in which the server commits to a single shared candidate bank and replaces roughly 1%1\% of its entries with probes derived from a known, non-private canary. We evaluate eight attacks, including an unchanged-bank baseline, exact copies, plausible paraphrases, and high-entropy synthetic nonces. Experiments on Yelp and Sentiment140 show that natural-text attacks remain substantially below the theoretical DP bound, while nonce-based attacks yield considerably stronger bounds and come closest to the mechanism’s privacy ceiling. These results quantify the gap between formal worst-case privacy and leakage achievable through protocol-valid candidate-bank manipulation. 1 Introduction Synthetic data can reduce reliance on direct access to sensitive records while retaining information useful for downstream analysis (Jordon et al., 2022). However, synthetic data is not inherently private but can still reveal sensitive information from the source data, motivating mechanisms with formal differential privacy guarantees (Cormode et al., 2025). Private Evolution produces synthetic data without training a model on private examples. In each round, a server proposes public candidates, clients vote for nearby candidates using private records, and a differentially private (DP) histogram determines which candidates survive (Lin et al., 2024; Xie et al., 2024; Hou et al., 2024). Because the released histogram is user-level DP, its Gaussian noise is calibrated to the worst contribution of any admissible user. This raises practical questions: (1) While following the PE protocol, can an honest-but-curious server design the candidate bank so that one user’s participation is as detectable as worst-case theory permits? (2) Does realistic user data make it substantially harder to detect user participation? Our goal is to build an operational audit of PE that is both informative and minimally invasive. The auditor replaces only a fixed, pre-declared fraction of the shared candidate bank with canary probes and otherwise leaves the mechanism unchanged. This restricted intervention creates a controlled membership signal while limiting disruption to output quality. The releases yield a confidence-bounded lower bound on attack-achievable privacy and thus directly quantifying its gap from εtheory _theory. We present a protocol-aware audit comprising eight attack variants. All variants commit to one candidate bank before user sampling, and range from an unchanged-bank baseline and exact copies to plausible paraphrases and synthetic nonce probes that calibrate the strongest attainable signal. The final hypothesis test accounts for hidden participation and reports a confidence-bounded empirical ε on two user-partitioned text datasets. Related Work. Privacy Auditing or Empirical DP is concerned with constructing privacy attacks i.e. datasets and events whose observed probabilities contradict or approach a claimed privacy curve (Jagielski et al., 2020; Nasr et al., 2023; Tramèr et al., 2022). Federated audits such as CANIFE and one-shot privacy estimation insert optimized or random canary clients while limiting interference with ordinary client updates (Maddock et al., 2023; Andrew et al., 2024). Our setting differs in that the adversarial object is not a client update or individualized model: it is one public candidate bank sent unchanged to all clients. Audits of DP synthetic data study worst-case datasets and disclosure from generated outputs (Annamalai et al., 2024; Meeus et al., 2025; Sun et al., 2025). SnapAudit separates deterministic computation from DP noise and searches for embedding signals in private in-context learning (Xia et al., 2025). To the best of our knowledge, no prior work studies the audit mechanisms for synthetic data generated via private evolution. 2 Methodology Let S=s1,…,spS=\s_1,…,s_p\ be a public bank of p candidate samples, and let DuD_u contain the capped records of user u. An embedding model maps records and candidates to a shared representation space. For each record x, the assignment vector aS(x)∈0,1pa_S(x)∈\0,1\^p identifies its top-k nearest candidates. After normalizing each user’s histogram and clipping it to threshold C, the user’s contribution is h¯u(S)=1|Du|k∑x∈DuaS(x),vu(S)=h¯u(S)min1,C‖h¯u(S)‖2. h_u(S)= 1|D_u|k _x∈ D_ua_S(x), v_u(S)= h_u(S) \! \1, C\| h_u(S)\|_2 \. (1) For independent participation indicators Iu∼Bernoulli(q)I_u (q), the released histogram is Y=∑uIuvu(S)+ZY= _uI_uv_u(S)+Z, where Z∼(0,(σC)2I)Z (0,(σ C)^2I) and σ is the Gaussian noise multiplier. In round t, PE releases a DP histogram Y(t)Y^(t) over the current synthetic population S(t)S^(t). PE uses this histogram feedback to generate new samples and appends them to the top-k~ k samples from S(t)S^(t) to form S(t+1)S^(t+1). Every histogram release consumes privacy budget whereas selection and generation from the released histogram are post-processing. See Algorithm A.1 for the complete pseudo-code of multi-round PE. Threat Model. We assume an honest-but-curious server (or auditor) that follows the PE protocol faithfully but uses the released DP histogram to infer whether a user participated. We assume that the server can insert canary users to the protocol. Further, it may inject r probes into the candidate bank, but commits to one ordered bank before the hidden inclusion draw. Every client receives the same bank. The server only observes aggregate messages from users but cannot inspect private traffic, individualize queries and alter any other specifics of the algorithm. We also assume access to an auxiliary public sample of nauxn_aux users drawn from the same distribution as the N eligible non-canary users. The axillary set represents the public knowledge the server may have and acts as proxy to the private data distribution. Protocol-Aware Canary and Probe Design. We consider two canary types: a randomly selected real user and a synthetic user whose records are high-entropy nonce11 1 A nonce is a pseudo-random number used only once in a cryptographic communication or security protocol. samples. Table 1 gives the eight attack variants. Each attack is evaluated on an independently selected set of five canaries. For the nonce variants, the synthetic users’ samples and candidate pools are generated independently of natural user data. Table 1: The eight audit attack variants. Nonce samples are independently generated high-entropy strings unrelated to natural text. Appendix B describes each construction in detail. Attack variant Canary type Candidate selection ordinary random real user use the original bank; inject no probes exact random real user inject exact copies of the canary records paraphrase random real user inject paraphrases spread across canary records paraphrase-norm random real user select paraphrases maximizing canary probe votes paraphrase-μeff _eff random real user maximize canary votes and minimize user votes on probes nonce synthetic nonce user inject a random subset of nonce probes nonce-norm synthetic nonce user select nonce probes maximizing canary probe votes nonce-μeff _eff synthetic nonce user maximize canary votes and minimize user votes on probes 2.1 Audit Mechanism We setup the hypothesis testing framework underlying differential privacy. Under H0H_0, a known canary user is absent from the eligible user pool; under H1H_1 it is present but participates only with probability q. The audit proceeds in five steps. All attack-design and calibration choices are fixed using public auxiliary data before the canaries are evaluated. Step 1: Construct and freeze the probe bank. Let S and P denote the shared candidate bank and its designated probe coordinates respectively. During attack design, a background-aware greedy procedure selects probe candidates – see Table 1 for variants. After each candidate is added, we recompute the canary’s exact top-k routing (see Appendix B.1). On completion, S and P are frozen. Let YP=[Y]PY_P=[Y]_P be the released histogram restricted to P. For user u, let vu,P=[vu(S)]Pv_u,P=[v_u(S)]_P be the user’s contribution on these coordinates after clipping, and write vcan,Pv_can,P for the canary’s contribution. Step 2: Estimate the canary-free background. Using only the auxiliary public samples, we estimate m0=[YP∣H0],ΣP=Cov(YP∣H0)=Σusers,P⏟random user participation+(σC)2I⏟DP noise.m_0=E[Y_P H_0], _P=Cov(Y_P H_0)= _users,P_random user participation+ (σ C)^2I_DP noise. (2) Here, Σusers,P _users,P captures variation due to the random participation of eligible non-canary users. Step 3: Score a participating canary. Conditional on the canary participating, its contribution shifts the mean by vcan,Pv_can,P. Under a shared-covariance Gaussian approximation, the corresponding log-likelihood ratio is ℓ(YP)=vcan,P⊤ΣP−1(YP−m0−vcan,P2),μeff=vcan,P⊤ΣP−1vcan,P. (Y_P)=v_can,P _P^-1 (Y_P-m_0- v_can,P2 ), _eff= v_can,P _P^-1v_can,P. (3) The quantity μeff _eff measures the canary’s separation from the background and is the objective maximized during greedy probe construction in Table 1. See Appendix E for details on the derivation. Step 4: Marginalize over hidden participation. Inclusion does not guarantee participation: under H1H_1, the canary participates independently with probability q. Marginalizing over this hidden participation event gives the mixture log-likelihood ratio ℓmix(YP)=log[(1−q)+qexpℓ(YP)]. _mix(Y_P)= \! [(1-q)+q \ (Y_P)\ ]. (4) Step 5: Calibrate the decision rule and lower-bound privacy loss. A calibration split fixes the decision threshold before final evaluation. On the held-out evaluation split, one-sided Clopper–Pearson confidence bounds on the confusion rates yield εlower=max0,logTPRL−δFPRU,logTNRL−δFNRU. _lower= \! \0,\, TPR_L-δFPR_U,\, TNR_L-δFNR_U \. (5) For each predeclared attack variant, we control the family-wise error rate at α=0.05α=0.05 across its five canaries. Each canary receives confidence budget α/5=0.01α/5=0.01, which is then divided equally among its four one-sided confidence bounds. We treat attack variants as separate predeclared experiments and therefore do not apply an additional simultaneous correction across variants. Finally, we compute the matching theoretical guarantee εtheory _theory using Opacus’s PRVAccountant implementation of numerical PRV composition (Gopi et al., 2021; Yousefpour et al., 2021), with the same participation probability q, noise multiplier σ, and failure probability δ. 3 Experiments, Results & Discussions We use Yelp Open Dataset reviews (Yelp, Inc., 2024) and Sentiment140 tweets (Go et al., 2009) that are naturally partitioned by users. Yelp users have 64 reviews and Sentiment140 users have 32–64 tweets. All canaries have 64 records. We use all-MiniLM-L6-v2 with 384-dimensional L2-normalized embeddings and Euclidean top-k voting (Sentence-Transformers, 2021) with p=8,192p=8,192 candidates where k=5k=5, and r=64r=64 probes. For each experiment, Qwen3-235B-A22B-Instruct-2507 (Qwen Team, 2025) generates the bank only using label information. We use dataset-splits with 500 user cohorts each for bank design and calibration and 1,000 user cohort for final testing. Unless stated otherwise, C=0.1C=0.1, σ=1σ=1, q=0.1q=0.1, δ=10−5δ=10^-5, with 100 participating users per round; we report the 95%-confidence lower bound εlower _lower and matching εtheory _theory. Table 2: εlower _lower for attacks with the label-only bank. Each entry is the maximum over five canaries with α=0.05α=0.05, each evaluated at α/5α/5 with 1M1M trials per hypothesis. Dataset ordinary exact paraphrase paraphrase-norm paraphrase-μeff _eff nonce nonce-norm nonce-μeff _eff εtheory _theory Yelp Open Dataset 0.268 0.371 0.276 0.316 0.560 1.049 1.110 1.110 1.695 Sentiment140 0.252 0.363 0.599 0.327 0.682 1.052 1.088 1.086 1.695 Table 2 reports εlower _lower for all eight attack variants at q=0.1q=0.1 and σ=1σ=1, against a theoretical budget of εtheory=1.695 _theory=1.695. Attacks constructed from natural user text remain well below the theoretical value. We observer that the passive ordinary baseline attains εlower=0.268 _lower=0.268 and 0.2520.252 on Yelp and Sentiment140, respectively (≈15%≈\!15\% of εtheory _theory), and the strongest attack with natural text, paraphrase-μeff _eff, attains 0.5600.560 and 0.6820.682 (below 40%40\% of εtheory _theory). Attacks based on high-entropy nonce records recover a substantially larger fraction of the budget: nonce-norm attains 1.1101.110 and 1.0881.088 (∼67% 67\% of εtheory _theory). These results indicate that, although the PE noise is calibrated to the worst-case user contribution, protocol-valid manipulation of the candidate bank with natural text realizes only a small fraction of the permitted privacy loss, whereas synthetic nonce probes approach the theoretical limit. The same trends holds across noise multipliers and sampling rates (Figure 1). Figure 1: Sentiment140 ablations (one canary, label-only bank, 5M5M trials); bands are 95% CIs. Multi-round PE with ICL: Figure 2 reports MAUVE utility (Pillutla et al., 2021) and privacy across PE rounds. Each round retains the top 5% of candidates and the probes, generates the next bank with ICL, and repeats the audit. We show the audit preserves synthetic-data utility across PE rounds while providing reasonable empirical epsilon lower bounds. Figure 2: Multi-round PE on Yelp: utility and privacy parameters (theory vs audit) against PE-round. Embedding comparison: Table 3 varies the encoder across three sentence-transformer models of increasing capacity: MiniLM-L6-v2 (22.722.7M parameters, 384384-d), MiniLM-L12-v2 (33.433.4M, 384384-d), and MPNet-base-v2 (109109M, 768768-d). We observe that the empirical epsilon of PE is insensitive to encoder capacity for this setup. Table 3: Embedding model ablation (εlower _lower). Attack Yelp Open Reviews Sentiment140 Tweets MiniLM-L6 MiniLM-L12 MPNET-Base-V2 MiniLM-L6 MiniLM-L12 MPNET-Base-V2 ordinary 0.268 0.232 0.273 0.252 0.272 0.249 exact 0.371 0.357 0.387 0.363 0.341 0.245 nonce 1.049 1.105 1.087 1.052 1.088 1.078 4 Conclusion and Limitations In this work, we designed a privacy auditing procedure for private evolution. Experiments show that practical attacks fall well short of worst-case theory, but (high entropy) nonce datasets bring empirical epsilon closer to theoretical epsilon. We note that designing and running a tight audit requires multiple trials, making it computationally expensive to run in production settings. In the future, we will explore design of one run auditing (Steinke et al., 2023) procedures to trade-off runtime and privacy measurement. References Andrew et al. (2024) G. Andrew, P. Kairouz, S. Oh, A. Oprea, H. B. McMahan, and V. M. Suriyakumar One-shot empirical privacy estimation for federated learning. In International Conference on Learning Representations, Cited by: §1. Annamalai et al. (2024) M. S. M. S. Annamalai, G. Ganev, and E. De Cristofaro “What do you want from theory alone?” Experimenting with Tight Auditing of Differentially Private Synthetic Data Generation. In 33rd USENIX Security Symposium (USENIX Security 24), p. 4855–4871. Cited by: §1. Cormode et al. (2025) G. Cormode, S. Maddock, E. Ullah, and S. Gade Synthetic tabular data: methods, attacks and defenses. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, p. 5989–5998. Cited by: §1. Go et al. (2009) A. Go, R. Bhayani, and L. Huang Twitter sentiment classification using distant supervision. CS224N Project Report Stanford University. Cited by: §3. Gopi et al. (2021) S. Gopi, Y. T. Lee, and L. Wutschitz Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, Vol. 34, p. 11631–11642. Cited by: §2.1. Hou et al. (2024) C. Hou, A. Shrivastava, H. Zhan, R. Conway, T. Le, A. Sagar, G. Fanti, and D. Lazar PrE-Text: training language models on private federated data in the age of LLMs. In International Conference on Machine Learning, p. 19043–19061. Cited by: §1. Jagielski et al. (2020) M. Jagielski, J. Ullman, and A. Oprea Auditing differentially private machine learning: how private is private SGD?. In Advances in Neural Information Processing Systems, Vol. 33, p. 22205–22216. Cited by: §1. Jordon et al. (2022) J. Jordon, L. Szpruch, F. Houssiau, M. Bottarelli, G. Cherubin, C. Maple, S. N. Cohen, and A. Weller Synthetic data: what, why and how?. arXiv preprint arXiv:2205.03257. Note: Commissioned by the Royal Society Cited by: §1. Lin et al. (2024) Z. Lin, S. Gopi, J. Kulkarni, H. Nori, and S. Yekhanin Differentially private synthetic data via foundation model APIs 1: images. In International Conference on Learning Representations, Cited by: §1. Maddock et al. (2023) S. Maddock, A. Sablayrolles, and P. Stock CANIFE: crafting canaries for empirical privacy measurement in federated learning. In International Conference on Learning Representations, Cited by: §1. Meeus et al. (2025) M. Meeus, L. Wutschitz, S. Zanella-Béguelin, S. Tople, and R. Shokri The canary’s echo: auditing privacy risks of LLM-generated synthetic text. In International Conference on Machine Learning, Cited by: §1. Nasr et al. (2023) M. Nasr, J. Hayes, T. Steinke, B. Balle, F. Tramèr, M. Jagielski, N. Carlini, and A. Terzis Tight auditing of differentially private machine learning. In 32nd USENIX Security Symposium (USENIX Security 23), p. 1631–1648. Cited by: §1. Pillutla et al. (2021) K. Pillutla, S. Swayamdipta, R. Zellers, J. Thickstun, S. Welleck, Y. Choi, and Z. Harchaoui MAUVE: measuring the gap between neural text and human text using divergence frontiers. In Advances in Neural Information Processing Systems, Vol. 34, p. 4816–4828. Cited by: §3. Qwen Team (2025) Qwen Team Qwen3-235B-A22B-Instruct-2507 model card. Note: Hugging Face, https://huggingface.co/Qwen/Qwen3-235B-A22B-Instruct-2507Accessed August 13, 2026 Cited by: §3. Sentence-Transformers (2021) Sentence-Transformers all-MiniLM-L6-v2 model card. Note: Hugging Face, https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2Accessed August 4, 2026 Cited by: §3. Steinke et al. (2023) T. Steinke, M. Nasr, and M. Jagielski Privacy auditing with one (1) training run. In Advances in Neural Information Processing Systems, Vol. 36, p. 49268–49280. External Links: Link Cited by: §4. Sun et al. (2025) Y. Sun, V. Schlegel, S. Nandakumar, I. Zahid, Y. Wu, Y. Wu, H. Li, J. Zhang, W. Del-Pinto, G. Nenadic, S. K. Lam, and A. A. Bharath SynBench: a benchmark for differentially private text generation. arXiv preprint arXiv:2509.14594. Cited by: §1. Tramèr et al. (2022) F. Tramèr, A. Terzis, T. Steinke, S. Song, M. Jagielski, and N. Carlini Debugging differential privacy: a case study for privacy auditing. arXiv preprint arXiv:2202.12219. Cited by: §1. Xia et al. (2025) Y. Xia, R. Liu, and L. Xiong SnapAudit: active auditing of differentially private in-context learning via snapshot-based simulation. arXiv preprint arXiv:2511.13502. Cited by: §1. Xie et al. (2024) C. Xie, Z. Lin, A. Backurs, S. Gopi, D. Yu, H. A. Inan, H. Nori, H. Jiang, H. Zhang, Y. T. Lee, B. Li, and S. Yekhanin Differentially private synthetic data via foundation model APIs 2: text. In International Conference on Machine Learning, p. 54531–54560. Cited by: §1. Yelp, Inc. (2024) Yelp, Inc. Yelp open dataset. Note: https://business.yelp.com/data/resources/open-dataset/Accessed August 4, 2026 Cited by: §3. Yousefpour et al. (2021) A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, G. Cormode, and I. Mironov Opacus: user-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.12298. Note: Privacy in Machine Learning Workshop, NeurIPS 2021 Cited by: §2.1. Appendix A Multi-Round Private Evolution Algorithm Algorithm A.1 presents multi-round PE independently of our experimental parameter choices. Each round computes a user-level DP histogram over the current synthetic population. If J(t)=Topk~(Y(t))J^(t)=Top_ k(Y^(t)), PE retains R(t)=sj(t):j∈J(t)R^(t)=\s_j^(t):j∈ J^(t)\ and constructs generation feedback F(t)F^(t) from S(t)S^(t) and Y(t)Y^(t). A public generator produces V(t)=(F(t))V^(t)=G(F^(t)), and PE sets S(t+1)=R(t)∪V(t)S^(t+1)=R^(t)∪ V^(t). The feedback rule is method-dependent and may request paraphrases or supply positively and negatively scored ICL examples. The private data enter only through the bounded client contributions in Lines 8–18. Subsequent selection and generation use only the DP histogram and public information, so they are post-processing. Because the candidate population evolves between rounds, the accountant must compose all T histogram releases under the declared sampling rule. Algorithm A.1 Multi-round Private Evolution with user-level DP top-k feedback 1: Private user datasets Duu∈\D_u\_u ; initial public population S(0)S^(0) 2: encoder ϕφ and distance d; top-k rule; user cap m 3: clipping threshold C; noise multiplier σ; user sampler SampleUsers 4: rounds T; retention count k~ k; number of variations g; public ICL generator G 5: for t=0,…,T−1t=0,…,T-1 do 6: Let pt←|S(t)|p_t←|S^(t)| and publish the same ordered bank S(t)S^(t) and encoder ϕφ to all sampled users 7: B(t)←()B^(t)← SampleUsers(U) 8: for all u∈B(t)u∈ B^(t) in parallel do 9: Du′←(Du,m)D _u← CapRecords(D_u,m) and hu←pth_u 0_p_t 10: for all x∈Du′x∈ D _u do 11: Nk(x)←argminJ⊆[pt],|J|=k∑j∈Jd(ϕ(x),ϕ(sj(t)))N_k(x)← J [p_t],\,|J|=k \ _j∈ Jd(φ(x),φ(s^(t)_j)) 12: for all j∈Nk(x)j∈ N_k(x) do 13: hu,j←hu,j+1h_u,j← h_u,j+1 14: end for 15: end for 16: h¯u←hu/(|Du′|k) h_u← h_u/(|D _u|k) ⊳ by-vote normalization 17: vu←h¯umin1,C/‖h¯u‖2v_u← h_u \1,C/\| h_u\|_2\ ⊳ user-level clipping 18: Send vuv_u to the protected aggregator 19: end for 20: Y(t)←∑u∈B(t)vu+Z(t)Y^(t)← _u∈ B^(t)v_u+Z^(t), where Z(t)∼(0,(σC)2Ipt)Z^(t) (0,(σ C)^2I_p_t) 21: J(t)←Topk~(Y(t))J^(t) _ k(Y^(t)) ⊳ indices selected by the DP histogram 22: R(t)←sj(t):j∈J(t)R^(t)←\s^(t)_j:j∈ J^(t)\ ⊳ retain top previous samples 23: F(t)←(S(t),Y(t))F^(t)← BuildFeedback(S^(t),Y^(t)) ⊳ e.g., paraphrases or positive/negative ICL 24: V(t)←(F(t),g)V^(t) (F^(t);g) ⊳ generate g new samples 25: S(t+1)←R(t)∪V(t)S^(t+1)← R^(t)∪ V^(t) ⊳ retain and append 26: end for 27: return S(T)S^(T) ⊳ evolved synthetic population Appendix B Attack Variant Details All variants preserve one ordered bank shared by every participating user. Active variants reserve an ordered list of r=64r=64 replacement positions before selection. Let SbaseS_base be the original bank after removing those positions. If probe jtj_t is selected in round t, it is assigned to replacement position t; the completed bank is then frozen before membership trials. Canary, auxiliary, and final-test users are disjoint: canary records define the desired signal, auxiliary users estimate background traffic for probe selection, and final-test users only evaluate the frozen attack. Candidate pools. Each paraphrase or nonce attack begins with an indexed pool =c1,…,cMQ=\c_1,…,c_M\ of M=512M=512 candidate probes and injects r=64r=64. The paraphrase pool contains non-verbatim rewrites generated across the 64 real-canary records. The nonce pool contains fresh high-entropy strings generated independently of natural text and of the synthetic nonce canary. The unoptimized variants choose 64 probes directly; the norm and μeff _eff variants use the greedy procedure in Algorithm B.1. Trial-set routing and scores. For a trial index set P, define S(P)=Sbase∪cj:j∈PS(P)=S_base∪\c_j:j∈ P\. For each of the 64 canary records, we recompute its five nearest entries in S(P)S(P). It is sufficient to merge the trial probes with that record’s five nearest entries in SbaseS_base: no lower-ranked base entry can enter the final top five. Let wPw_P be the resulting vector of probe-vote counts divided by the canary’s 64×5=32064× 5=320 total votes. The two optimized attacks differ only in the scalar score Jnorm(P)=‖wP‖22,Jμeff(P)=wP⊤Σ^P−1wP,J_norm(P)=\|w_P\|_2^2, J_ _eff(P)=w_P _P^-1w_P, (6) Before selection, we estimate a covariance Σ _Q over the full 512-candidate pool from the fixed auxiliary-user split and freeze it. A trial set P uses the corresponding principal submatrix Σ^P=[Σ^]P,P _P=[ _Q]_P,P. Thus the matrix used by the score changes with the selected coordinates, but it is not re-estimated from auxiliary users at every step. Norm rewards concentrated canary votes, while μeff _eff discounts probe coordinates that also receive background-user votes. The mechanism’s full-vector clipping is still applied when the frozen bank is audited. Appendix D gives the estimator and shrinkage coefficient. In Algorithm B.1, (S(P),Dcan,k) ProbeVotes(S(P),D_can,k) denotes the full re-routing operation above and returns the normalized vector wPw_P. It recomputes all 64 canary records rather than updating the previous round’s counts. Why forward selection is necessary. Probes compete for the same top-5 votes. Adding a closer probe can take a vote from an already selected probe, so the value of a probe depends on the rest of the selected set. Ranking all 512 candidates independently and taking the top 64 is therefore incorrect. At round t, the algorithm adds each remaining candidate to the t−1t-1 selected probes, recomputes all canary routes and the complete score, and commits the best trial set. Exact score ties are resolved by the lowest pool index for both objectives. This deterministic rule prevents arbitrary ties from creating a false difference between nonce-norm and nonce-μeff _eff when their objectives are equivalent. Algorithm B.1 Greedy construction of norm and μeff _eff probe sets 1: Non-probe bank SbaseS_base; indexed pool =cjj=1MQ=\c_j\_j=1^M with M=512M=512 2: Canary records DcanD_can with m=64m=64; auxiliary users DauxD_aux; k=5k=5; budget r=64r=64 3: Objective o∈norm,μeffo∈\norm, _eff\; ordered replacement positions (ρ1,…,ρr)( _1,…, _r) 4: P←∅P← 5: if o=μeffo= _eff then 6: Σ^←(,Daux) _Q← AuxCovariance(Q,D_aux) ⊳ estimate once and freeze 7: end if 8: for t=1,…,rt=1,…,r do 9: for all j∈[M]∖Pj∈[M] P do 10: T←P∪jT← P∪\j\ 11: wT←(S(T),Dcan,k)w_T← ProbeVotes(S(T),D_can,k) ⊳ recompute all top-k routes 12: if o=normo=norm then 13: sj←‖wT‖22s_j←\|w_T\|_2^2 14: else 15: Σ^T←[Σ^]T,T _T←[ _Q]_T,T 16: sj←wT⊤Σ^T−1wTs_j← w_T _T^-1w_T 17: end if 18: end for 19: jt←min(argmaxj∈[M]∖Psj)j_t← \! ( _j∈[M] Ps_j ) ⊳ lowest-index tie break 20: P←P∪jtP← P∪\j_t\ 21: end for 22: Insert cjtc_j_t at position ρt _t for t=1,…,rt=1,…,r and freeze the ordered bank 23: return frozen bank and selected sequence (j1,…,jr)(j_1,…,j_r) Ordinary. This passive baseline randomly selects a real canary user and leaves the candidate bank unchanged. The audit observes the histogram coordinates on which the canary naturally votes under the original top-k routing. It measures how distinguishable the canary is without adding probes or otherwise adapting the bank to that user. Exact. This variant uses the same randomly selected real user and injects one exact copy of each of its 64 records. Each copied record is at zero embedding distance from its source. Paraphrase. From the 512-item paraphrase pool, this unoptimized semantic baseline selects 64 probes spread across the canary’s records rather than concentrating on a few records. It uses no norm or background-aware score. Paraphrase-norm. This variant applies Algorithm B.1 to the 512-paraphrase pool using JnormJ_norm. It favors sets on which canary votes have high magnitude and are concentrated on relatively few probes, without accounting for background traffic. Paraphrase-μeff _eff. This primary realistic attack runs the same algorithm and pool with JμeffJ_ _eff. Its frozen pool covariance comes only from auxiliary users, and each trial uses the submatrix for its selected coordinates; no final-test user influences selection. It favors paraphrases that attract the canary but lie on coordinates with little or uncorrelated background traffic. Nonce. This calibration constructs a synthetic canary from 64 fresh, high-entropy nonce records and independently generates the 512-item nonce probe pool. It injects 64 pool entries selected uniformly without replacement. These are independent audit markers, not hashes of private records; they place signal where natural users are unlikely to vote and approximate the mechanism ceiling. Nonce-norm. This variant applies Algorithm B.1 to the 512-nonce pool using JnormJ_norm. It estimates the mechanism ceiling when selection explicitly maximizes the magnitude and concentration of nonce-canary votes without background covariance. Nonce-μeff _eff. This variant runs the same nonce search with JμeffJ_ _eff. If nonce strings separate cleanly from natural text, Σ^P _P is approximately isotropic and the selected sequence should match nonce-norm, including under ties. If natural users collide with nonce probes, the objective preserves canary votes while avoiding those background directions. Appendix C Complete Results Bank A is generated by Qwen3-235B-A22B-Instruct-2507 using label-only prompts. Bank B uses the same generator with three public in-context examples, yielding candidates that are better matched to the private-user distribution. Table 4 reports both candidate-bank arms for each dataset. Table 4: εlower _lower for two datasets and two candidate-bank arms. Each entry is the maximum over five canaries with α=0.05α=0.05, each evaluated at α/5=0.01α/5=0.01 and 1M1M trials per hypothesis; εtheory=1.695 _theory=1.695. Attack variant Yelp A Yelp B Sentiment140 A Sentiment140 B ordinary 0.247 0.295 0.475 0.429 exact 0.313 0.304 0.363 0.587 paraphrase 0.276 0.297 0.599 0.759 paraphrase-norm 0.316 0.457 0.327 0.871 paraphrase-μeff _eff 0.560 0.439 0.682 0.932 nonce 1.038 1.047 1.018 1.014 nonce-norm 1.110 1.120 1.088 1.063 nonce-μeff _eff 1.110 0.958 1.086 0.977 Appendix D Hyperparameter settings Users and record cap. All experiments cap each user at m=64m=64 records. Yelp admits users with exactly 64 records, whereas Sentiment140 admits users with 32–64 records. The single-release experiments use an eligible non-canary population of N=1,000N=1,000 users and q=0.1q=0.1 unless swept, giving 100 expected participants per release. We use 500 disjoint auxiliary users to design probes and estimate non-canary moments, 500 calibration users to lock the threshold, and the N=1,000N=1,000 final-test users only for evaluation. Trial budgets. Table 2 and Table 4 use 1M1M trials per hypothesis. Figure 1 uses 5M5M trials per hypothesis because small noise multipliers separate the hypotheses more strongly, making errors at the selected tail threshold rare; the larger budget stabilizes the Clopper–Pearson bounds. The multi-round audit also uses 5M5M trials per hypothesis. Multi-round accounting. Figure 2 composes T=6T=6 Poisson-sampled releases on Yelp with q=0.1q=0.1, σ=1.1088σ=1.1088, δ=10−5δ=10^-5, N=8,000N=8,000 eligible test users, and 500 auxiliary users. For each prefix t, a fresh Opacus PRVAccountant is stepped once per release with the same sampling rate and noise multiplier, then queried at δ=10−5δ=10^-5. This gives εtheory=1.345,1.540,1.682,1.800,1.905, _theory=1.345,1.540,1.682,1.800,1.905, and 2.0002.000 after releases one through six, respectively. The empirical audit composes the same prefixes by summing their mixture log-likelihood ratios. Appendix E Additional Mathematical Details This appendix supplies derivations omitted from the main text. In particular, it distinguishes the absent-canary, fixed-inclusion, and hidden-participation distributions; derives the Gaussian and mixture likelihood ratios; records the distribution of the resulting score; and connects the final hypothesis test to a confidence-bounded empirical privacy lower bound. These derivations do not change the audit mechanism or its assumptions. E.1 Background aggregate and its moments Let P denote the histogram coordinates inspected by the audit. Write the contribution of non-canary user u, restricted to these coordinates, as cu=vu,P.c_u=v_u,P. For a fixed eligible population of N non-canary users, define the background aggregate B=∑u=1NIucu+ZP,Iu∼indBernoulli(q),ZP∼(0,(σC)2I).B= _u=1^NI_uc_u+Z_P, I_u ind Bernoulli(q), Z_P \! (0,(σ C)^2I ). (7) The user vectors cuc_u are fixed after the candidate bank, routing rule, and clipping operation have been frozen. Randomness comes from user sampling and Gaussian DP noise. Since [Iu]=qE[I_u]=q, the absent-canary mean is m0:=[B]=q∑u=1Ncu.m_0:=E[B]=q _u=1^Nc_u. (8) For a fixed vector cuc_u, Cov(Iucu)=Var(Iu)cucu⊤=q(1−q)cucu⊤.Cov(I_uc_u)=Var(I_u)c_uc_u =q(1-q)c_uc_u . Independence therefore gives Σ:=Cov(B)=q(1−q)∑u=1Ncucu⊤+(σC)2I. :=Cov(B)=q(1-q) _u=1^Nc_uc_u +(σ C)^2I. (9) The off-diagonal entries capture correlated voting: one user may contribute to several inspected coordinates simultaneously. E.2 Three cases Let v=vcan,Pv=v_can,P be the known canary contribution on the inspected coordinates. Because the bank and canary records are fixed before the trial, v is a deterministic vector. Case Released vector Mean Covariance Canary absent B m0m_0 Σ Canary sampled B+vB+v m0+vm_0+v Σ Canary eligible B+JvB+Jv m0+qvm_0+qv Σ+q(1−q)vv⊤ +q(1-q)v Here J∼Bernoulli(q)J (q) is the canary’s sampling indicator, independent of B. The covariance is the same under absence and fixed inclusion because adding a deterministic vector changes only the mean: Cov(B+v) (B+v) =[(B+v−(m0+v))(B+v−(m0+v))⊤] =E\! [ (B+v-(m_0+v) ) (B+v-(m_0+v) ) ] =[(B−m0)(B−m0)⊤] =E\! [(B-m_0)(B-m_0) ] =Σ. = . (10) In contrast, the full eligible-canary hypothesis contains the random term JvJv: Cov(B+Jv) (B+Jv) =Cov(B)+Cov(Jv) =Cov(B)+Cov(Jv) =Σ+q(1−q)vv⊤. = +q(1-q)v . (11) Thus the full alternative does not have the same covariance as the null. It is a mixture of the absent and fixed-inclusion distributions. Independent Bernoulli sampling is important for this argument. Adding an eligible canary does not displace an ordinary user, so the background distribution remains unchanged. Under fixed-size sampling without replacement, conditioning on canary inclusion could change the distribution of the remaining sampled users. E.3 Gaussian approximation and fixed-inclusion likelihood ratio The background is a Bernoulli-weighted sum of user vectors convolved with Gaussian noise. The audit approximates it by B≈(m0,Σ).B (m_0, ). Consequently, the absent and fixed-inclusion component distributions are H0 H_0 :Y≈(m0,Σ), :Y (m_0, ), (12) Hinc H_inc :Y≈(m0+v,Σ). :Y (m_0+v, ). (13) The equality of the component covariances is exact; their Gaussian shape is the approximation. The fixed-inclusion log-likelihood ratio is ℓ(y):=logpinc(y)p0(y). (y):= p_inc(y)p_0(y). Using the two Gaussian densities, ℓ(y) (y) =−12[(y−m0−v)⊤Σ−1(y−m0−v)−(y−m0)⊤Σ−1(y−m0)]. =- 12 [(y-m_0-v) ^-1(y-m_0-v)-(y-m_0) ^-1(y-m_0) ]. Expanding the first quadratic form gives (y−m0−v)⊤Σ−1(y−m0−v) (y-m_0-v) ^-1(y-m_0-v) =(y−m0)⊤Σ−1(y−m0) =(y-m_0) ^-1(y-m_0) −2v⊤Σ−1(y−m0)+v⊤Σ−1v. -2v ^-1(y-m_0)+v ^-1v. The shared quadratic term cancels, leaving ℓ(y)=v⊤Σ−1(y−m0)−12v⊤Σ−1v=v⊤Σ−1(y−m0−v2). (y)=v ^-1(y-m_0)- 12v ^-1v=v ^-1 (y-m_0- v2 ). (14) The score is linear in y precisely because the two Gaussian components have equal covariance. E.4 Whitening and effective separation Define x=Σ−1/2(y−m0),s=Σ−1/2v.x= ^-1/2(y-m_0), s= ^-1/2v. In whitened coordinates, H0:x∼(0,I),Hinc:x∼(s,I),H_0:x (0,I), H_inc:x (s,I), and ℓ(x)=s⊤x−12∥s∥22. (x)=s x- 12 s _2^2. The distance between the component means is μeff=∥s∥2=v⊤Σ−1v. _eff= s _2= v ^-1v. (15) This is the Mahalanobis signal-to-noise ratio. Directions with large background variance receive less weight, while signal on quiet coordinates receives more weight. Writing d=μeffd= _eff, the score distributions are ℓ(Y)|H0 (Y) H_0 ∼(−d22,d2), \! (- d^22,d^2 ), (16) ℓ(Y)|Hinc (Y) H_inc ∼(+d22,d2). \! (+ d^22,d^2 ). (17) At threshold a, FPR(a) (a) =1−Φ(a+d2/2d), =1- \! ( a+d^2/2d ), (18) TPRinc(a) _inc(a) =1−Φ(a−d2/2d). =1- \! ( a-d^2/2d ). (19) At the equal-prior threshold a=0a=0, FPR=Φ(−d/2),TPRinc=Φ(d/2).FPR= (-d/2), _inc= (d/2). Because Σ⪰(σC)2Iand∥v∥2≤C, (σ C)^2I v _2≤ C, the conditional Gaussian separation satisfies μeff2=v⊤Σ−1v≤∥v∥22(σC)2≤1σ2. _eff^2=v ^-1v≤ v _2^2(σ C)^2≤ 1σ^2. (20) This is a ceiling on component separation, not directly an (ε,δ)( ,δ)-DP formula. E.5 Hidden participation and the mixture likelihood ratio Under the actual alternative, the canary is eligible but is sampled only with probability q. Therefore p1(y)=(1−q)p0(y)+qpinc(y).p_1(y)=(1-q)p_0(y)+q\,p_inc(y). (21) Dividing by p0(y)p_0(y) and using pinc(y)/p0(y)=eℓ(y)p_inc(y)/p_0(y)=e (y) gives ℓmix(y):=logp1(y)p0(y)=log[(1−q)+qeℓ(y)]. _mix(y):= p_1(y)p_0(y)= [(1-q)+qe (y) ]. (22) This expression explicitly preserves the mixture; it does not approximate full H1H_1 as a single Gaussian. The identity is exact if ℓ is the true component likelihood ratio. In the audit, it inherits the Gaussian approximation used to obtain Equation (14). For q>0q>0, dℓmixdℓ=qeℓ(1−q)+qeℓ>0. d _mixd = qe (1-q)+qe >0. Hence ℓ and ℓmix _mix rank observations identically for a single release, although only ℓmix _mix is the likelihood-ratio value for the eligible-canary hypothesis. For any fixed threshold event, TPR=(1−q)FPR+qTPRinc,TPR=(1-q)FPR+q\,TPR_inc, (23) and therefore TPR−FPR=q(TPRinc−FPR).TPR-FPR=q (TPR_inc-FPR ). This equation makes the effect of user subsampling explicit: only a fraction q of eligible-canary trials contain the canary’s signal. E.6 From test errors to an empirical privacy lower bound Let A be the event that the frozen audit predicts that the canary is present. Define TPR=ℙH1(A),FPR=ℙH0(A),TPR=P_H_1(A), =P_H_0(A), and, for the complementary event, TNR=ℙH0(Ac),FNR=ℙH1(Ac).TNR=P_H_0(A^c), =P_H_1(A^c). For neighboring user-level datasets, (ε,δ)( ,δ)-DP requires ℙH1(A) _H_1(A) ≤eεℙH0(A)+δ, ≤ e P_H_0(A)+δ, (24) ℙH0(Ac) _H_0(A^c) ≤eεℙH1(Ac)+δ. ≤ e P_H_1(A^c)+δ. (25) Substitution and rearrangement yield ε ≥logTPR−δFPR, ≥ TPR-δFPR, (26) ε ≥logTNR−δFNR. ≥ TNR-δFNR. (27) The rates are estimated from finitely many final-evaluation trials. Let TPRLTPR_L and TNRLTNR_L denote one-sided lower confidence bounds, and let FPRUFPR_U and FNRUFNR_U denote one-sided upper confidence bounds. A conservative empirical privacy lower bound is εlower=max0,logTPRL−δFPRU,logTNRL−δFNRU. _lower= \0,\, TPR_L-δFPR_U,\, TNR_L-δFNR_U \. (28) A branch whose lower-confidence numerator is at most δ supplies no positive bound. For x successes among n Bernoulli trials, the one-sided Clopper–Pearson endpoints at tail probability γ are pL p_L =0,x=0,FBeta(x,n−x+1)−1(γ),x>0, = cases0,&x=0,\\ F_Beta(x,n-x+1)^-1(γ),&x>0, cases (29) pU p_U =1,x=n,FBeta(x+1,n−x)−1(1−γ),x<n. = cases1,&x=n,\\ F_Beta(x+1,n-x)^-1(1-γ),&x<n. cases (30) With overall α=0.05α=0.05, five canaries per predeclared attack, and four one-sided rate bounds per canary, the audit uses γ=0.055⋅4=0.0025.γ= 0.055· 4=0.0025. The calibration split is independent of final evaluation so that the event A, including its threshold, is frozen before the final confusion counts are observed. E.7 Auxiliary moment estimation For nauxn_aux auxiliary users with clipped contributions cuc_u on the inspected coordinates, define μ^P μ_P =1naux∑u=1nauxcu, = 1n_aux _u=1^n_auxc_u, (31) M^P M_P =1naux∑u=1nauxcucu⊤. = 1n_aux _u=1^n_auxc_uc_u . (32) The second quantity is an uncentered second moment, rather than a sample covariance, because Bernoulli participation contributes Cov(Iucu)=q(1−q)cucu⊤.Cov(I_uc_u)=q(1-q)c_uc_u . Because nauxn_aux is finite, off-diagonal entries of M^P M_P can be noisy. We therefore use diagonal shrinkage shrink0.1(M^P)=0.9M^P+0.1diag(diag(M^P)),shrink_0.1( M_P)=0.9 M_P+0.1diag(diag( M_P)), (33) which preserves each diagonal second moment and multiplies the estimated off-diagonal terms by 0.90.9. The plug-in estimators thus used by the audit are m^0 m_0 =qNμ^P, =qN μ_P, (34) Σ^P _P =q(1−q)Nshrink0.1(M^P)+(σC)2I+10−9I, =q(1-q)Nshrink_0.1( M_P)+(σ C)^2I+10^-9I, (35) The term (σC)2I(σ C)^2I is the covariance of the Gaussian DP noise already present in the released histogram; no noise is added to the public auxiliary data. The final 10−9I10^-9I term is only a numerical ridge for stable inversion. E.8 Conditional composition across rounds When the candidate bank evolves across rounds, the joint transcript likelihood ratio follows the chain rule logp1(y1:T)p0(y1:T)=∑t=1Tlogp1(y(t)∣y(<t))p0(y(t)∣y(<t)). p_1(y^1:T)p_0(y^1:T)= _t=1^T p_1(y^(t) y^(<t))p_0(y^(t) y^(<t)). (36) Thus per-round mixture scores may be summed when each score is the appropriate conditional likelihood ratio given the realized earlier transcript. Summing unconditional marginal likelihood ratios would not generally be correct for an adaptive candidate-bank process. Formal DP accounting remains valid under adaptive composition because candidate retention and public generation are post-processing, while every new private histogram is separately composed.