InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy
Authors: Vishnu Vinod
Krishna Pillutla
Abhradeep Guha Thakurta
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Text Generation
Synthetic Data
Private Inference
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose InvisibleInk for DP synthetic text generation. It can produce of hundreds of tokens at 8 times lesser computational cost at the same privacy/utility trade-offs compared to prior state-of-the-art methods.

Abstract: As major progress in LLM-based long-form text generation enables paradigms such as retrieval-augmented generation (RAG) and inference-time scaling, safely incorporating private information into the generation remains a critical open question. We present InvisibleInk, a highly scalable long-form text generation framework satisfying rigorous differential privacy guarantees with respect to the sensitive reference texts. It interprets sampling from the LLM's next-token-distribution as the exponential mechanism over the LLM logits with two innovations. First, we reduce the privacy cost by isolating and clipping only the sensitive information in the model logits (relative to the public logits). Second, we improve text quality by sampling without any privacy cost from a small superset of the top-$k$ private tokens. Empirical evaluations demonstrate a consistent $8\times$ (or more) reduction in computation cost over state-of-the-art baselines to generate long-form private text of the same utility across privacy levels. InvisibleInk is able to generate, for the first time, high-quality private long-form text at less than $4\text{-}8\times$ times the computation cost of non-private generation, paving the way for its practical use. We open-source a pip-installable Python package (invink) for InvisibleInk at https://github.com/cerai-iitm/invisibleink.

InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy
Vishnu Vinod' CeRAL, IIT Madras
Krishna Pillutla 1.2
Abhradeep Thakurta² Google DeepMind
WSSL, IIT Madras
Abstract
As major progress in LLM-based long-form text generation enables paradigms such as retrieval- -aggeeeed generation (RAG) and inference-tine scaling, safely incor- porating private information into the generation remains critical open question. We present INVISIBLEINK, a highly scalable long-form text generation framework satisfying rigorous differential privacy guarantees with respect to the sensitive reference texts. It interprets sampling from the LLM's s rext-loken-ddsttibution as the exponential mechanism over the LLM logits with two innovations. First, we reduce the privacy cost by isolating and clipping only the sensitive information in quality
the model logits (relative the public logits). Second, improve by sampling without any privacy cost from small superset of the top-k private tokens. Empirical evaluations demonstrate a consistent 8x (or more) reduction in computation cost over state-of-the-arr baselines to generate long-form fag-form private text of the same utility across privacy levels. INVISIBLEINK for the first time, high-quality private long-form text at less than 4-8x times the computation cost of non-private generation, paving the way for practical use. We open-source pip-installable Python package (invink) for InvisibleInk at comm/crrii-i iiiiiiiittmiiiiiii inwisibleiii...
able to generate,
https://git
Introduction
Large Language Models (LLMs) have demonstrated remarkable inference-time capabilities, synthe- sizing information from multiple sources into coherent responses via vetrieval-augmenter generation (RAG), and generating increasingly long and sophisticated outputs via the recent "deep research" and inference-time scaling paradigms [1-3]. Larger token budgets also allow these models to effectively "think," enabling self-reflection and correction of potential errors during generation [4-8].
The power of these models, however, often relies on their ability to process and reason over vast amounts of information, including potentially sensitive data provided inference time. This context might come from user prompts containing private details or documents retrieved by RAG systems from confidential knowledge bases. There some risk that the model's 's outputs, particularly detailed long-form generation [9], could inadvertently leak sensitive details from this private context [10].
Differential Privacy (DP) [11] mitigate such risks by providing provable guarantees that the output distribution is statistically indistinguishable whether or not any single piece of sensitive information included in the input context. This guarantee is not just desirable but often essential in sensitive domains like healthcare and finance, where information leakage carries severe regulatory (e.g., HIPAA, GDPR) and ethical consequences and merely anonymizing personally identifiable information (PII) is not sufficient [12] Therefore, developing effective DP mechanisms for inference- time generation critical for the responsible application of LLMs in privacy-sensitive applications. We tackle the challenge of achieving high- figh-fideitty long-form text generation under the rigorous DP guarantees on sensitive source text(s) used as references for generation.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Meat-isken logits
Difference
Aspregatiinn
Agompiii Lagai
Aotinttaal poiutoe
Truncated Tapeh+
vecabutery
Expanentirr
Woad
DEUIEE
Decord
Figure I: INVISIBLEINK interprets differentially private text generation exponential mechanism over subset of the LLM's clipped logits. Our key innovations are: (a) DClip, an improved clipping function to reduce sensitivity, and hence, the privacy cost; and (b) Top-k+ sampling, a truncated decoding algorithm to improve utility by selecting a subset of logits to sample each token from.
iterative application of the
Despite the importance of this problem, existing approaches for DP text generation suffer from severe practical limitations. Consider the prior state-of-the-arr method of Amin et al. [13], which interprets token sampling from the LLM as an instance of the canonical exponential mechanism [14] over the next-token logits. It requires computational overhead of 100x that of non-private generation or more, to produce non-degenerate text.' This makes them intractable at scale for large models.
Moreover, from quality perspective, these methods typically resort to high-temperature sampling from the full vocabulary distribution. This decoding strategy well known to produce degenerate or low-quality text, falling significantly short of the fluency and coherence achieved by standard non-private decoding algorithms, which rely on sampling from truncated distributions [16-18].
We bridge this gap with the following:
We propose INVISIBLEINK for DP synthetic text generation. It can produce hundreds of tokens 8x lower computational cost at the same privacy/utility trade-offs compared to prior SoTA methods.
Our main contributions are follows:
We propose INVISIBLEINK, an exponential mechanism-based [14] sampling framework to allow LLM-based text generation with rigorous DP guarantees under the replace-by-nt adjacency. We make two key innovations: (a) DClip to isolate and clip only the sensitive information in the model logits and avoid paying privacy cost on prior information on language; and (b) Top-k+ decoding: a truncated decoding algorithm that approximates sampling from the top-k private tokens with a small superset of size k se k ensuring high utility without losing out on private tokens that are unlikely under a public model.
INVISIBLEIIK Framework:
Privacy-Utility- Colelite- Tradeoffs: By empirically analyzing synthetic text generation on three domains-medde medical, legal, and commercial-wy demonstrate an 8-16x reduction in computation cost across the board to achieve the same privacy and utility. 2 Thus, INVISIBLEINK can produce hundreds of tokens at significantly smaller compute budgets (such as < 10x the non-private cost), including in settings where baselines extinguish their privacy budgets within handful of tokens.
User-friendly Accounting: Given privacy budget and compute budget, give non- adaptive privacy accounting procedure and practical heuristics to tune hyperparameters. This makes INVISIBLEINK usable off fff-the-shelf. In contrast, prior works [13, 19] require grid search to tune hyperparameters that affect the privacy-uility-comppe algorithm behavior (e.g. number of tokens generated) for practical deployment. In addition to increased computational cost, this can add to the privacy cost [20].
tradeoff or estimates of the adaptive
We also open source pip-installable Python package (invink), available at https: /ttp::///gthuu thub com/ cerai- titmmmmmtii iniisibeink,, to generate differentially private synthetic text using INVISIBLEINK. See $G for example of the invink package in action.
'Generally, the drop in utility from DP can be offset by increasing data and computation, e.g., by averaging over larger batches reduce sensitivity; DP model training also admits similar phenomenon [1.5]. Thus, we compare methods by the computation cost necessary to attain given privacy and utility levels.
We allow some baselines advantage by (incorrectly) reducing their sensitivity by 2 v2; see $5.

---

2 Related Work
Generating synthetic data with DP has an extensive literature, particularly over categorical fea- tures [21-25]. Many such approaches rely on the exponential mechanism [26-28]. Unfortunately, it is cryptographically hard to generate DP synthetic data that preserves all 2-way marginals with poly- nomial sample complexity [29]; also [30, Thm. 6. 12] and [31, Ch. 9]. Fortunately, public data can provide strong priors over data distributions to partially circumvent these lower bounds. Public data has long been used in private tabular data generation [32-35]. More recently, pretrained generative foundation models provide strong priors, enabling the DP generation of complex image/text data [36-41]. In this work, we focus on practical and scalable DP generation of text using LLMs.
We focus on practical and scalable DP text generation. DP text can be generated from DP fine- tuned models [42 [6] or via private inference." We focus on the latter as private finettuing can be prohibitively expensive, especially with large models [15]. Private inference is possible with various types of LLM access: via text generation API [41, 46, 47], or white-box access to next-token logits [13, 47, 48]; we focus on the latter. Other DP text manipulation tasks include paraphrasing [49, 50] and next-token prediction [19, 51-54). We adapt [19] text generation
baseline in $5.
Most prior approaches to DP text generation suffer from one or more restrictions: (1) a small number of generations, enough to serve exemplars for in-context learning [48, 55, 56]; (2) short or highly constrained generations in classification or directed text generation tasks such as summarization or question-answeriie (as opposed to open-ended long-form generation) [13, 47]. Of these, only the API-access method of [41] and the white-box method of [13, 57] apply to long-form generation.
Prior DP text generation approaches diverge significantly from successful decoding algorithms in the NLP literature. Sampling from truncated next-token distributions [16, 58-62] is strongly backed by qualitative [16], quantitative [17, 18, 63], and theoretical [64] evidence; see the survey [8] for further details. INVISIBLEINK generates high-utility text by adapting truncated decoding to the DP setting.
The concurrent work of [57] extends the approach of Amin et al. [13] by clustering similar references into batch. This orthogonal approach can also be integrated with INVISIBLEINK for synthetic text generation, though clustering may not be applicable to some tasks, such as RAG. [57] also replaces mean aggregation with median aggregation, with smaller local sensitivity and a tighter data-dependent ex-post DP guarantee [65] (evaluated after observing the algorithm's 's output). In contrast, INVISIBLIINK provides stronger standard indeeendntnt and ex-ante) DP guarantee (evaluated before the algorithm is run).
3 Preliminaries: Differentially Private Text Generation
Language Models & Decoding, An auto-regressive language model P over a vocabulary V defines a distribution P(xx over the next token 22 E V in response to prefix x: (x1 (#1...... ......... xt-1) V*; here, V denotes the set of all sequences of elements from V. These probabilities are typically obtained as the softmax of the next-token logits o(- xx))) as ( exp (6(x,(=<))).
Given a query q E V* and reference text r E V*, we could iteratively sample a response I, P(- q,r, xe) from the LLM P with concatenation of q.r. æec context, and æ<1 = 0. Unfortunately, this approach tends to over-represent incorrect low-probability tokens (as V ~ O(10²) or larger), leading to degenerate text [16, 17]. A common strategy is to use decoding algorithms that reshape P(- I)) into another distribution Q |-) from which we sample the next token.
Typical decoding algorithms promote more conservative outputs by suppressing the unreliable low- probability tokens. For example, temperature rescaling [66] temperature r >> rescales the logits, while top-k sampling [58] only samples from the k largest logits. Mathematically,
(x(k)(e))) & exp (+ (x)l(()))) and Q x { (((x) if E VE,
{0,
else.
where V& C V is the set of tokens with highest logits o( |x See Fig. 2 for an example.
'Private inference can be used on pretrained models prompted with private data (our setting) or non-DP fine-tuned models. Both are conceptually identical as they privatize set of non-private predictions.
3

---

Effect of Temperature
Top-k
MAUVE Scores
107
Probabiity
Probubiilty
3.86
Temperature
2.
0.000
117
107
287
227
227
121
157
Token Rank
Token Rank
Top-k sampling (F)
Figure 2: Left & Center: Illustration of how two common decoding algorithms temperature rescaling and top-k sampling -esshiing the next-token probabilities for (uon-private LLM-based text generation. Right: Heatmap of MAUVE scores [17, 18] of synthetic generated for the MIMIC-IV-Notes dataset (without using any sensitive references). The best generations (highest MAUVE scores) are obtained at Rs 1.1 and = 100; INVISIBLEINK exhibits similar behavior of decoding hyperparameters for private text generation.
The quality of non-DP long-form text generation is primarily determined by the decoding algorithm and its hyperparameter or k) [16, 17, 63). Typically, these hyperparameters are tuned balance two competing objectives: reducing (or zeroing out) the probability of generating contextually inappropriate or low-probability tokens, while allowing the selection of moderately probable but contextually appropriate tokens to maintain diversity and coherence. In practice, this typically translates to temperature r x 1 or slightly smaller, and & E [10, 100] (ef. Fig. 2).
In this work, we generate text with a set of privacy-sensitive references R = (ri,..., TB) E (V*) This setting arises in synthetic text generation, where we instruct an LLM generate text similar to given references, or in RAG systems where R contains retrieved information over confidential knowledge bases. The model output may leak sensitive information from R in such cases.
Differential Privacy (DP). DP provides formal protections against such privacy leakage. At a high level, a (randomized) text generation algorithm A satisfies DP at the example level, if for all adjacent reference sets R, R' (that differ in a single sensitive example), the probability distributions A(g, R) and A(g, R') over responses æ E V* are "nearly indistinguishable.. A fully specified example-level DP guarantee requires precise notions adjacency and indistinguishability. We focus on the replace-by-null adjacency, where an adjacent R' is obtained by replacing one element of R by the empty string (or vice versa); we denote it as R ~ R'. This is functionally similar to adding or removing a reference. but simplifies the theoretical technicalities; adjacency notions. We use the indistinguishabiliy notion of cero-concentrated DP (zCDP) [67]. Let Da denote the a-Rényi divergence. Then, an algorithm A satisfies p-zCDP if
[15] or $B for comparison of
Do (AAg, R) A(q,, R))) S pa for all > 1 and all adjacent R ~ R'.
Smaller values of mean that A(q. R) and A(q, R') are closer to each other (in terms of the Rényi divergence) and the impact of the differing example between R, R' on the output low, indicating higher privacy. The zCDP guarantee can be converted into other notions, e.g., (c. 5)-DP [68-70]. Our techniques also translate directly to other notions of adjacency and indistinguishabiity:: see $C.
DP Text Generation via the Exponential Mechanism. Our goal is to design an algorithm A(g, R) to generate text in response to given query q and references R with desired p-zCDP guarantee. We assume the whitebox setting where model logits o( 0 x) can be queried for any æ E V*. An increasing number of sfate-of-the-ann DeepSeek, LLaMA3, Mistral, GPT-OSS allow whitebox access to model logits. This is in contrast to the more restrictive API-access setting, where one inference call returns entire text sequence [41].
and reasoning open- weights models including
We describe the prior state-of-the-an approach of Amin et al. [13], which generates the next token It E V via the canonical exponential mechanism [14] over the next-token logits of the given LLM. Given a query q and sensitive references R, the first step is to obtain the next-token logits Φi = o(- q, r;, xx E R VV for each E [B] with an LLM inference call. Second, we clip and aggregate the logits as o- = (1/B) Σ (1pi), where (() clips each coordinate of Φi to lie in C). We can then sample a p>ZCDP token P; E V by sampling [71] from the distribution
Qxx+ q, R, mx))) x exp
2p
o (xxt))
sens(
'The clipping in [13] re-centers the logits (which are invariant to additive shifts). While this is empirically important, we omit the details in our exposition the underlying mathematical properties do not change.

---

Histograms of db
Historamms of dlyu
Naive Clipping
Improved Clipping DCip
Probabiity
Probabiltt
6477
0.00
Uedope
Und sped DC
640
Taken Rank
Token Ronk
Left two: Histograms of private logits 6; and differences from public logits di pub for synthetic data sample generated from the MIMIC dataset, with 5thh and 95th percentiles shown by the dotted lines. The spread of values for Φ Aub is significantly smaller (around 10x) than that of db.. Thus, ( (y) (y( for over 95% of all y V with C' = 1, while the naive clipping of Amin et al. [13] requires C' This translates into an 8x gain computational efficiency. Right two: small clip norm of = 1 (using Amin et al. [13]'s method introduces significant bias resulting in a near near- uniform distribution over the vocabulary. In contrast, DClip (see $4) preserves probabilities with minimal distortion even at C' = 1.
Figure 3:
where the sensitivity (Φ)) measures the maximum change in Φly), when move to adjacent set R' ~ R of references for any y E V. The clipping and aggregating steps control the sensitivity as sens Φ)) OCC/B), that Eq. (2) reduces to sampling with temperature OCC/Byp)
Drawbacks of Prior Work. If the clip norm C' is too small, the resulting distortions in the next- token logits boost the probabilities of the unlikely tail tokens (see Fig. 3), and if C is too large, the temperature T x C/ B becomes too large. Both scenarios lead to degenerate text. Generating non-degenerate text from this method requires taking C sufficiently large (e.g. Amin al. [13] recommend C R 10), and B large enough to ensure a temperature of T = OCC R
That is, generating each private token requires a large number B of LLM next-token inference calls, which can be prohibitive if the minimum admissible B is large. In practice, we can typically control B, as this is the number of reference documents we use for one synthetic generation, or the number of retrieved references in RAG systems. However, we find in $5 that the method of [13] fails to produce coherent text at batch size B smaller than 50 or 100, making it prohibitively expensive at scale.
Finally, Amin et al. [13] adaptively use tokens generated from public logits @uub = 0(-1(.(1 2x) using the sparse vector technique (SVT) [72] if they are close enough to the aggregated private logits Φ. This improves the overall privacy-utility tradeoffs, but makes noise calibration challenging. The privacy guarantee scales with the number of private tokens adaptively generated (often unknown a priori), as opposed to the total number of generated tokens (a priori specified). This leaves two choices to calibrate the noise hyperparameters: (a) estimate the fraction of times SVT chooses private tokens, or (b) use grid search. Both options can incur increased computation and privacy costs [20].
Next, we describe how INVISIBLEINK overcomes these drawbacks.
4 INVISIBLEINK: DP Text Generation under Strict Compute Budgets
INVISIBLEINK aims to improve the privacy loss with a surgical clipping function, and the utility with approximating the top-k decoding over private logits at any given computation budget.
DClip: A Targeted Clipping Function. The private next-token logits Φ; o( -1 T., xx)) encode not just the sensitive information in the reference rú, but also general information about language, grammar and syntax, semantics, degree of world knowledge and common sense, and style/tone of the preceding tokens [e.g. 73-75). Clipping the next-token logits involves paying a privacy cost for this general non-private information, leading to wasted privacy budget.
This non- non-private information is already captured by a pretrained model, even without access to the sensitive reference r.. We isolate and selectively clip only the extra information conveyed by the private logits Φ; over and above the public logits @pub == oi - g, 2e))) E RIV,, as follows:
DClipc ppub) == pub + (l, pbub),
We have sens(Ø) 2C (resp. ④ under replace-by-null (resp. zero-out) adjacency; cf. $B. We give this method advantage in $5 by (incorrectly) taking sēns( C/B B under replace-by
by-uul bull adjacency.
5

---

Algorithm 1 INVISIBLEINK for DP Text Generation
Require: LLM logit API o(-1.), I.). vocabulary V. query q, sensitive references R
length T,, clip norm C, temperature T, top-k parameter, initial generation = ( rB). max text
1: for t ,,..., do
2: For i E [B], set Φ; = o( q. (x E IRI and doub = 6( (() E RRIM (pru ki C, B)
> LLM calls
3:
V EXPAADED
Vocubulary for Top-k + sampling
4: Set Φ @pub 1 Ei_, ( Øbub)
Aggregated clipped logits
5: Sample
softmax( I/T)
Exponential mechanism over V
6: Yield next token 2iz append it æ. and break if It <eos>
Generated Token
7: procedure
8: Set é to be the kthh largest entry of 6uu k. C)
To lop-k threshold of Duus Expand top-k threshold of D by 2C| B
9:
Return [y E V ppnn 2 f 2C/B]
where C > O is a specified clip norm, and (l) projects each coordinate of Φ onto the interval [-C, C). The clipped and aggregated logits & can then be drop-in replacement in Eq. (2) is
お = मे Σi= DClipo (.. Qpub) = pub + 1
B Ei= clipo (#: -pub))
Its sensitivity is also conveniently bounded as follows (see $C for proof):
Property Fix a query q and prefix 3et, and denote Φ: ø( q. q.T() Then, the sensitivity of the map (rı...., TB) + B E DClip pubb) under the replace-by-nun adjacency is C/B.
Fig. 3 shows that the spread of Φ; pub is typically much smaller than that of Φ; since Pub already contains a strong prior on language. We utilize a smaller clip norm C without distorting the model outputs, and hence a smaller compute cost B to maintain temperature of T C/B close to 1.
Truncated Top-k+ Sampling. As discussed in $3, the degeneracies of sampling long-form text with temperature T $ 1 can be fixed by truncated decoding [16]. We now adopt this to DP text generation. Define (Ø) C V as the top-k vocabulary corresponding to logits & E RIV:
(Ø) = ( }
Φ(v1) 2 2 <(y)) 2 max Φ(v).
Vanilla (non-prine (non-private) top-k sampling from one logit vector Φ; = Φz( |q. Fee)) would restrict the vocabulary to (Ø.)). Our goal is to extend the truncation to union of the top-k contributions of the B logit vectors $1,... ΦB in Eq. (4). To get the contribution of the logit vector Φ; to Eq. (4), we plug in Φ; = pub for * i, since Φ does not contain any private information about &.,, follows:
dlp Pub (lipo(d): Puhh) $
Then, the top-k vocabulary for private generation simply the union VA U
Unfortunately, restricting our vocabulary to this privcc--ensitive top-k set Vj. fails to satisfy DP. Changing the dataset from R to an adjacent R', can cause token y V to "jump out" of the top-k set Vg. Its probability of being generated then goes from a non-zero value to zero value, leading to a privacy loss of log (yylQ R, ( R', xz.))) oo (see [e.g. 70, Def. 2] for definitions).
An alternative explored in previous work is to simply sample from the top-k tokens from the public logits Φuub- This incurs no privacy cost as the restricted vocabulary is independent of the private logits but may fail to generate tokens that are rare in the pretraining data but common in the sensitive data R. These are likely relevant to the data generation domain, and it desirable to recover them.
To do
build tight superset of Vr U Vi((, based purely on the public logits Φpub- Observe that clipping ensures ddipp (y) épub (v)l s C/B for each i. So, each y e Vi((ppu)) satisfies clip (v) C/B > f, where f is the top-k threshold of Φpub. Thus, the top-k threshold &, of Φ is bounded as E, 2 C/B. It thus follows that:
y E Vi( + 2et
(2))())) - & c C
(5)
In other words, the private top-k vocabulary Vi( always lies in the set V == {u E V @pub(y) 2 L BC/B). Since this is true for each E [B], we have that V is a superset of V/= = Vi (d. We refer to sampling from the set Vet as Top-k sampling.

---

Since Vi is constructed without using the private logits, sampling from it does not incur any privacy cost. We find in $5 that |V V& (&ppb)) & 10 < [V] i.e. V is indeed a right superset of Vi. We further develop the intuition on Top-k+ sampling using toy example in SC.3.
INVISIBLEINK: Text Generation & Privacy Accounting, Our approach wraps the above two components in an exponential mechanism-bases outer loop: see Algorithm 1. Crucially, Algorithm I does not involve any dependentt privacy mechanisms. This lets us give zCDP bound, building directly upon the zCDP analysis of the exponential mechanism [71] and adaptively composing [70] the per-token zCDP guarantee over T tokens. Adaptive composition ensures that previously generated tokens can be reused safely in future steps without additional privacy cost; see $C for proof.
Theorem 2. Algorithm/ I with a maximum token budget T, clipping threshold C. a set of B = R references, and temperature satisfies Preq PCeq with Peeq = TC2 /2B²
When running the algorithm in practice, we assume that we are given the privacy budget Pseq. the maximum sequence length T, and the number of references B (which fixes the compute budget). We recommend a default temperature of T x 1. Then, Theorem lets us set the clip norm C = BT 2 T to get the desired privacy guarantee (independent of the top-k parameter).
Another advantage of our method is that generation gracefully falls back on that of the public model if the compute or privacy budget too small. In this case, we get a very small C and Φ; ~ pubb This nice property is not satisfied by existing baselines. For example, as the privacy or computation budget gets smaller, [13] requires a small clip norm C, reducing their method to uniform sampling over the full vocabulary (see Fig. 3). This leads to gibberish text. Similarly, AdaPMixED [19] has data-dependent privacy guarantee that depends on the number of tokens sampled per generation. As the privacy or computation budget gets smaller, the length of synthetic generations falls sharply.
Finally, we note that it might be possible to improve the dependence of Theorem 2 on the token budget I' with regularization [e.g. 76, 77]; we leave this for future work.
5 Experiments
Setup. Given a reference dataset D = [fr,,..., TN J. our task is to create synthetic texts I1.... Ix that are statistically similar D while satisfying given -CCP guarantee with respect to D. We generate synthetic example æ, based on a batch R, = (ry "( 1))+1)B) of sensitive references with query q instructing a generation similar to the given references. By parallel composition, each example 2, must also satisfy Psea- -CDP. Since the batch size B fixes the computation budget, we allow (B 11 LLM next-token inference calls per generated token. This also limits us n S [N/B] synthetic examples. See $D for additional details on the task and experimental setup.
We report central DP guarantee for single hyperparameter setting to generate synthetic text sam- ples; the randomized mechanism here is a set of n autoregressive text generations from L.MMs, which output sequence of tokens? each. We propose heuristics for choosing optimal hyperparameters in $5.3 in lieu of accounting for privacy lost in hyperparameter tuning. Throughout this work, we report example-level (an example a single text sample drawn from the reference dataset) p-zCDP guaran- tees (converted to (s, o)-DP where necessary) under the replace-by-null adjacency; see $B for details. We release our code at: https: // //g /ggggth.bb.... comm/erai--. -iii-iittt titmmmiiiiiiii Iweiiiiiiiiiiiii sirreisibeennnne Inpe-xieiiieetss...
Datasets. We experiment with three datasets in clinical, legal, and commercial domains, see Tab. 1. MIMIC-IV-Note [78, 79] is a de-identified collection of medical text associated with ICU patients; we use the discharge summaries, which contain sensitive diagnosis, treatment, and medication information. Further, this dataset is legally unavailable for LLM pretraining, making it valuable in modeling real-world distribution-shiftt sensitive domains. The Text Anonymization Benchmark (TAB) [80] contains N 1013 (training set) court case notes (in English) from the European Court of Human Rights (ECHR) with personal identifiers and other confidential attributes. This low-resource dataset only admits extremely small batch sizes B (c.g., B 127 gives us a maximum of synthetic texts). The Yelp Reviews dataset [81] contains user-generated reviews and ratings for businesses with
'For example, the word "differential"" might be made up of two tokens "differ" and "-ential". Sampling uniformly at random could yield the "-ential" token without an appropriate preceding token, producing gibberish. The token string ends in <EOS> token unless the number of tokens generated reaches the limit I first.
7

---

Dataset
Domain
Text Type
Size
Avg. Length
# Generations
Max. Length
MIMIC-IV-Note
Medical
Discharge Summaries
311K
298.4
1000
500
Yelp
Commercial
Reviews
19M
145.2
500
200
TAB
Legal
Court Case Texts
1013
387.7
100
500
Table 1: Dataset summaries. Lengths are measured in tokens and we use at most Bn - 128K reference texts.
personal opinions and location references, and a standard benchmark in DP text generation [13, 41]. We intentionally choose real privacy-sensitie datasets (e.g. MIMIC, TAB) datasets with long-form text, rather than standard internet datasets (AGNews, IMDB, etc.) that are well-represented in the pretraining data of most L.Mss [82, 83J. See $D.2 for further discussion.
Models. We primarily use the TinyLLaMA I.IB [84], a compact open-weights model with strong performance in compute-constrained settings. We also use L.aMA3.2-1B [85] to study the effect of large vocabularies (VV) = 128K vs. 32K for TinyL.aama), and ILLMM3-8B [86] for scaling.
Baselines and Hyperparameters. We compare INVISTBLEINK (with and without Top-k+ sampling) with the prior white-box SoTA methods Amin et al. [13] for DP text generation and AdaPMixED [19] for DP next-token prediction. We iteratively sample from the predicted next-token distribution of AdaPMixED to adapt to DP text generation. For all methods, we fix the batch size B as it fixes the computation budget. We select other hyperparameters. such the clip norm C' for INVISIBLEINK and Amin et al. [13] to achieve a desired privacy guarantee. See $D.5 for further details.
The method of Amin et al. [13] has sensitivity of C/B under the zero-out adjacency, compared to BC/B under the replace-by-null adjacency (see Theorem 9 of ŞB). Yet, we give an advantage by (incorrectly) taking the sensitivity to be C/ B under the replace-by-null adjacency. AdaPMixED originally gives data-dependent DP guarantee under the rol-ove-reoov adjacency in [19]. Since find that the utility trends under both adjacency notions are qualitatively similar (see $E.6), we modify AdaPMixED directly and report the results for replace-by by-null adjacency here.
The DP guarantees of [13] are calibrated on the number of times the adaptive SVT step (whose output deta-depe selects the private tokens. Further, AdaPMixED [19] gives deta-dependent DP guarantees. This makes precise pre-hoc privacy accounting difficult. In our experiments we select hyperparameters that give the desired DP guarantee "on average". For example, we find that the adaptive SVT step in [13] selects private tokens around 25% of the time, so we calibrate their method to produce R T/4 private tokens and generate until the privacy budget is exhausted. We find that the privacy loss always exhausts the maximum budget for at least one batch across all settings.
We also compare INVISIBLEINK with the API-access method of Xie et al. [41] (AugPE). This restrictive setting naturally makes privatization harder. AugPE makes two types of LLM inference calls: generation and paraphrasing. We cannot make an apples-to-apples comparison between the computational cost of INVISIBLEINK to AugPE using the number of LLM inferences per generated tokens since AugPE calibrated using the number of paraphrasing iterations made per generated sequence. Instead, we directly use the wall-clock runtime of both methods as a measure of computation cost. We also allow AugPE an advantage of /2 in the sensitivity under applace-by-nule adjacency (see $B.3.3). For additional results and detailed generation settings, see $E.1.
Metrics. We evaluate the statistical similarity between the generated text and reference distribution with MAUVE scores [17, 18, 87], the gap between the average perplexities of generated and reference texts (denoted APPL), and average generation lengths to ensure that sufficient tokens are generated before exhausting the privacy budgets. The MIMIC discharge notes also contain medical named- entities such as names of medical conditions, procedures, and medicines. We plot the number of such entities identified by a MedNER model [88], as a measure of the domain-relevance of generated text.
5.1 Experimental Results
We compare the saap---ttiiitttpppppe tradeoffss of INVISIBLEINK with the baselines at a target level
of (e 10, 5 1--P in Fig. 4. See Tab. 2 for evaluations other values (with 8 = 10-9).
We find that INVISIBLEINK with Top-k-+ sampling consistently produces the highest quality text with the longest generations (and the most medical named entities for MIMIC) at smaller compute budgets
8

---

MALIFE (1) MIMIC
GenPPL (13 MIMIC
Leugh (1) MIVIC
MoNNER (1)
MAIVE
Length
8.5
1
Neakitoken Infonare Calee
Nect-tobe Infermece Cals
Nest-mnknn Inferncce Colks
Nechnsken Infeoeace Cals
P.Nic Invshie-lrkke (+ = (V])
Inskuble-lnk (1 1091
ArdPMiuFD
Amin (2004)
Text
MAUVE (1) Yelp
Gen. Length (1) for Yop
MAUVE (r) for TAB
Gen. Length for TAB
1.1
809
1:00
CRR
ERR
Du Method
Next: Inference
Next toker Inference Calls
Method
Invisblelnkk (6 [7])
Inoebbe-ikk
ArisPMiFD
Amin (2004)
Figure 4: Utility- compute tradeoff's at (e = 10,0 = 10 9) DP on each dataset across varying compute budget from B E (1.3...., 127}. Results reported over 3 runs with 95% confidence intervals (see &D.6) for MIMIC and 1 run for Yelp/TAB datasets. INVISIBEEINK produces text that matches exceeds the baselines at fraction of the compute. The baselines do not even work for the low-resource TAB datasct at small batch sizes
INVISIBLEINK (k- 100)
INVISIBLEINK (A- [VD)
Amin et al. [13]
AdaPMisED [19]
B
3
7
15
3
31
127
7
31
127
e=1
68.3
68.9
67.9
69.2
6T.3
67.6
68.2 14
INF
58.8
56.8
59.2
==3
67
69.7 az
70.9 12
66.9 20
69.1 L
69
INF
INF
55, 50
58.5 01
58.9
61.7 ia
61
70.3 L0
69.7 0s
73.5
68.6
68.9
69.0
INP
INF
69.5
50.4
59.8
69.9
08.4
720
73.7
75.0
68.3
70.4
72.4
INP
68.9 as
70.1 13
08.2
58.9
Table 2: MAUVE (%) scores, reported with mean and 95% confidence intervals (see $D.6) over 3 runs, for 1000 synthetic generations of the MIMIC dataset using TinyL.LaMA Synthetic generation without any private references
0) yields MAUVE of 68. 56% (best hyperparameters). INVISIBLEINK outperforms every private baseline with x smaller batch size. The results for INVISIBLEINK with |V] are reported for T = 1.0 and for k = 100 are reported for T = 1.1. AdaPMixED [19] sometimes exceeds a wall clock time of 36 hours (denoted TLE- Time Limit Exceeded); Amin et al. [13]'s method fails to generate any synthetic text for small privacy/compute budgets (denoted INF- infeasible). The top two scores for every are highlighted.
across datasets. Consider the results MIMIC, for example: INVISIBLEINK can achieve MAUVE score of = 71-74% with 8-16 inference calls per token, while Amin et al. [13] achieves z 70-72% at with 64-128 inference calls: this is an 8x improvement in computation cost. INVISIBLEINK also produces more medical named entities than Amin et al. [13] capturing the domain-specific information in the sensitive references and producing qualitatively better text.
Tab. shows that INVISIBLEINK exhibits graceful degradation in utility when operating under tight privacy budgets or compute constraints, where baselines fail. Specifically, Amin et al. [13]'s method uses up all its privacy budget for the SVT term and cannot produce any text at (a) B < 31, (b) < 5 and B S. 63, and (c) = 1 and B < 127; see $E. Mcanwhile, AdaPMixED extinguishes its data-dependent privacy budget after generating as few as 10 tokens for B = 8. Both basclines require large batch sizes to operate meaningfully, rendering them impractical in compute-constrained environments. We discuss the full sets of hyperparameters explored, in $D.5.
Comparison with API-Access Methods. We find that INVISIBLEINK completely outperforms the API-access based method AugPE [41] across privacy budget settings and evaluation metrics in Fig. 5. We remark that this is expected due to the more restrictive API-access setting of AugPE. Interest- ingly, we found in preliminary experiments that AugPE showed competitive (with INVISIBLEINK) performance on the Yelp dataset. This can likely be attributed to the L.LM-based paraphrasing step working best when the dataset of private references well-represented in the pre-training data. See 1, for more details and additional results.
9

---

MAUVE Scores (1) for MIMIC
GeaPPL (1) for MIMIC
Gen. Longths (1) for MIMIC
ModNER Counts (1) for MIMIC
375
Counta
+
Wall Cook Runtime (hrs)
Wall Clock Runtime (hrs)
Wall Clock Runtime (hrs)
Wall Clock Runtime (hrs)
Invislie-ink (2 100)
AugP
Real Text.
Figure 5: INVISIBLEINK outperforms the API-access method of AugPE [41] across all settings: Utility vs Compute plots (avg. over 3 runs with 95% confidence intervals) for INVISIBLENN and AugPE for = 10 for 1000 synthetic texts generated for the MIMIC dataset. Wall-clock run time is used proxy for computational cost. We report results for B 1 4, 8, 16, 32 for INVISIBLEINK and and TrugPE 1, 3, 5, for AugPE.
MALIVE Scorm (1) (e
MAUVE Stowes (13 (e =3)
MAINF Scores (*) te 6
MAIIVE Screm (1) (r 10)
MAUVE
0.3
085
013
080
Parometer
Parameter
Parameter
Top Paramteer
2 1B
TinyLaMM
Figure 6: Truncated decoding offers significant benefits: MAUVE scores (avg. over 3 runs with 95% confi- dence intervals) for DP synthetic text generation of 1000 samples from the MIMIC Dataset using TinyLLaMA and LLaMA3.2-IB models at a temperature = 1.1 and batch size B = 7.
5.2 Understanding INVISIBLEINK: Ablations, Scaling and Additional Experiments
We examine the importance of the two key components DClip and the Top-k+ sampling of INVISIBLEINK. Fig. 3 shows that the smaller active range of Φ; Pub allows us to use smaller C, when clipping using DClip, to maintain similar levels of distortion. This translates into an s 8x improvement (see Fig. 4) in computation cost at the same privacy-utility levels. Fig. 6 shows us that Top-k- decoding offers significant improvements (in MAUVE scores) over using the full vocabulary (72% vs. 65% at 10 for TinyL This distinction is more pronounced for the similar-sized Llama-3.2 IB model (76% vs. 62% at E = 10), with a 4x larger vocabulary (128K vs. 32K).
Additional Experiments. We present additional statistics of Top-k+ sampling from the expansion set (V₁* V2), in $E.3 and show empirically that V is a tight superset of Vy. We also conduct additional experiments evaluating the suitability of private synthetic text for downstream classification task on the Yelp dataset in $E.2. To highlight the scalability of INVISIBLEINK to larger models we generate synthetic text using LLaMA3 8B model at low batch sizes (incompatible with baselines) in $E.4. $E.5 gives additional ablations on the effect of the temperature, clip norm, and top-k parameters. In particular, show that setting the temperature near-optimal generations across settings. As noted previously, a comparison of the performance of AdaPMixED for replace-by-null and add-or-remove adjacency is also presented in $E.6 to show that the quantitative results for either notion follows similar trends.
[1.0, 1.1] and the top-k parameter k z 100 yields
5.3 Practical Recommendations
We recommend tuning temperature parameter 7 s 1 (generally in the range of 0.9 to 1.2), if permitted by the computation budget. reasonable heuristic to avoid tuning is to directly set 7 1, as it achieves competitive performance. Then, we set a clip norm C BT BT/ /2rea/2 where the batch size B fixes the computation budget, Pseq P zCDP is the target privacy guarantee, and T the maximum token budget. Finally, we must tune free parameter for Top-k+ sampling. We recommend tuning k following best practices for non-private decoding (e.g., ht (50, 100) for open-ended settings and smaller for more directed settings such as reasoning).
Conclusion. We introduce INVISIBLEINK, scalable framework for long-form text generation that provides rigorous differential privacy guarantees with respect to sensitive references. For a detailed discussion of the limitations and broader impact of our work, see $F.
10

---

Acknowledgments
The authors thank Ambreesh Parthasarathy, Krithi Shailya, Danish Pruthi, and Balaraman Ravindran for fruitful discussions, as well as the authors of [13] for constructive discussions. VV is supported by the aost-aaccalaureate Fellowship at the Centre for Responsible AI (CeRAT), IIT Madras. KP grateful for funding from ANRF's PM ECRG AARF//FCKG/2022000552///9 A12050 program, the startup compute grant of the Wadhwani School of Data Science Al (WSAT), IIT Madras, and faculty research awards.
Schmidt Sciences'
References
[1] Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solvingg In Proc. of ICLR, 2025.
[2] Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. sl: Simple test-time scaling. arXiv, 2025.
[3] Vidhisha Balachandran, Jingya Chen, Lingjiao Chen, Shivam Garg. Neel Joshi, Yash Lara, John Langford, Besmira Nushi, Vibhav Vincet, Yue Wu, ct al. Inference- Scaling for Complex Tasks: Where We Stand and What Lies Ahead. arXiv, 2025.
[4] Maxwell I. Nye. Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieher, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show Your Work: Scratchpads for Intermediate Computation with Language Models, arXiv, 2021.
[5] Jason Wei, Xuezhi Wang. Dale Schuurmans, Maarten Bosma, Brian Tehter, Fei Xia, Fd H. Chi, Quoe V. Lee, and Denny Zhou. Shain-of-Thought Prompting Elicits Reasoning in Large Language Models. In Proc. of NeurlPS, 2022.
[6] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D Goodman. STaR: Self-Taught Reasoner Bootstrapping Reasoning With Reasoning. Proc. of NeurIPS, 2022.
[7] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of Thoughts: Deliberate Problem Solving with Large Language Models. In Proc. of NeurlPS, 2023.
[8] Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From Decoding to Language Models. TMLR, 2024.
Inference- time Algorithms for Large
[9] Milad Nasr, Javier Rando, Nicholas Carlini, Jonathan Hayase, Matthew Jagielski, A. Feder Cooper, Daphne Ippolito, Christopher A. Choquette- Chooue Florian Tramer, and Katherine Lec. Scalable Extraction of Training Data from Aligned, Production Language Models. In Proc. of ICLR, 2025.
[10] Matthieu Meeus, Lukas Wutschitz, Santiago Zanella- Bégullln, Shruti Tople and Reza Shokri. The Canary's Echo: Auditing Privacy Risks of LLM- Generated Synthetic Text. In Proc. of ICML, 2025.
[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. of Theory of Cryptography Conference (TCC), 2006.
[12] Rui Xin, Niloofar Mireshghallah, Shuyue Stella Li, Michael Duan, Hyunwoo Kim, Yejin Choi, Yulia Tsvetkov, Sewoong Oh, and Pang Wei Koh. A False Sense of Privacy: Evaluating Texual Data Sanitization Beyond Surface-level Privacy Leakage. arXiv, 2025.
[13] Kareem Amin, Alex Bie, Weiwei Kong, Alexey Kurakin, Natalia Ponomareva, Umar Syed, Andreas Terzis, and Sergei Vassilvitskii. Private prediction for large-scale synthetic text generation. In Proc. of FMNLP Findings, 2024.
[14] Frank McSherry and Kunal Talwar. Mechanism Design via Differential Privacy. In Proc. of FOCS, 2007.
[15] Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guba Thakurta. How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy. Journal of Artificial Intelligence Research, 2023.
[16] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The Curious Case of Neural Text Degeneration. In Proc. of ICLR, 2020.
[17] Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Scan Welleck, Yejin Choi, and Zaid Harchaoui. Mauve: Mcasuring the gap between neural text and human text using divergence frontiers. In Proc. of NeurIPS, 2021.
[18] 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.

---

[19] James Flemings. Meisam Razaviyayn, and Murali Annavaram. Adaptively Private Next-Token Prediction of Large Language Models, arXiv, 2024.
[20] Nicolas Papernot and Thomas Steinke. Hyperparameter Tuning with Renyi Differential Privacy. In Proc. of ICLR, 2022.
[21] Avrim Blum, Katrina Ligett, and Aaron Roth. A Learning Theory Approach to Non-Interactive Database Privacy. Proc. of STOC, 2008
[22] Moritz Hardt and Guy N. Rothblum. A Multiplicative Weights Mechanism for Privacy-Preservingg Data Analysis. In Proc. of Foundations of Computer Science (FOCS), pages 61-70. IEEE Computer Society, 2010.
[23] Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan, On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proc. STOC, 2009.
[24] Giuseppe Vietri, Cédric Archambeau, Sergül Aydöre, William Brown, Michael Kearns, Aaron Roth, Amaresh Ankit Siva, Shuai Tang, and Zhiwei Steven Wu. Private Synthetic Data for Multitask Learning and Marginal Queries. In Proc. of NeurlPS, 2022.
[25] Yiyun He, Roman Vershynin, and Yizhe Zhu. Online Differentially Private Synthetic Data Generation. IEFE Transactions on Privacy, 2024.
[26] Moritz Hardt, Katrina Ligett, and Frank McSherry. A Simple and Practical Algorithm for Differentially Private Data Release. In Proc. of NeurlPS, 2012.
[27] Amir Reza Asadi and Po-Ling Loh. On the Gibbs Exponential Mechanism and Private Synthetic Data Generation. In Proc. of International Symposium on Information Theory (ISIT), 2023.
[28] David Pujol, Amir Gilad, and Ashwin Machanavajhala. PreFair: Privately Generating Justifiably Fair Synthetic Data. In Proc. of VLDB Endow., 2023.
[29] Jonathan R. Ullman and Salil P. Vadhan. PCPs and the Hardness of Generating Private Synthetic Data. In Proc. of Theory of Cryptography Conference (TCC), 2011.
[30] Salil P. Vadhan. The Complexity of Differential Privacy. In Tutorials on the Foundations of Cryptography. Springer International Publishing, 2017.
[31] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trendso Theoretical Computer Science, 2014.
[32] Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan R. Ullman. and Zhiwei Steven Wu. Leveraging Public Data for Practical Private Query Release. In Proc. of ICMI,, 2021.
[33] Terrance Liu, Giuseppe Vietri, and Steven Wu. Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods. In Proc. of NeurlPS, 2021.
[34] Miguel Fuentes, Brett C. Mullins. Ryan McKenna, Gerome Miklau, and Daniel Sheldon. Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data. Proc. of AISTATS, 2024.
[35] Samuel Maddook, Shripad Gade, Graham Cormode, and Will Bullock. Leveraging Vertical Public-Privatt Split for Improved Synthetic Data Generation. arXiv, 2025.
[36] Ali Shahin Shamsabadi, Brij Mohan Lal Srivastava, Aurélien Bellet, Nathalie Vauquier, Emmanuel Vincent, Mohamed Maouche, Mare Tommasi, and Nicolas Papernot. Diffcrentially Private Speaker Anonymization. In Proc. of Privacy Enhancing Technologies (PET), 2023.
[37] Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially Private Diffusion Models. TMLR, 2023.
[38] Kecen Li, Chen Gong, Zhixiang Li, Yuzhong Zhao, Xinwen Hou, and Tianhao Wang. PrivImage: Differentially Private Synthetic Image Generation using Diffusion Models with Semantic-Aware Pretraining. In Proc. of USENIX Security Symposium, 2024.
[39] Margarita Vinaroz, Mohammad-Amen Charusaie, Frederik Harder, Kamil Adamezewski, and Mijung Park. Hermite Polynomial Features for Private Data Generation. In Proc. of TCMI,, 2022.
[40] Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. Differentially Private Synthetic Data via Foundation Model APIs 1: Images. In Proc. of ICLR, 2024.
[41] Chulin Xie. Zinan Lin, Arturs Backurs, Sivakanth Gopi, Da Yu, Huseyin A Inan, Harsha Nori, Haotian Jingg Huishuai Zhang. Yin Tat Lee, Bo Li, and Sergey Yekhanin. Differentially Private Synthetic Data via Foundation Model APIs 2: Text. In Proc. of ICMI., 2024.
[42] Sean Augenstein, H. Brendan McMahan, Daniel Ramage, Swaroop Ramaswamy, Peter Kairouz, Mingqing Chen, Rajiv Mathews, and Blaise Agûera y Arcas. Generative Models for Effective ML Private, Decentralized Datasets. Proc. of ICLR, 2020.
[43] Justus Mattern, Zhijing Jin, Benjamin Weggenmann, Bernhard Schölkopf, and Mrinmaya Sachan, Differ- entially Private Language Models for Secure Data Sharing. In Proc, of EMNLP, 2022.
12

---

[44] Xiang Yue, Huseyin A. Inan. Xuechen Li, Girish Kumar, Julia McAnallen, Hoda Shajari, Huan Sun, David Levitan, and Robert Sim. Synthetic Text Generation with Differential Privacy: A Simple and Practical Recipe. In Proc. of ACL, 2023.
[45] Alexey Kurakin, Natalia Ponomareva, Umar Syed, Liam MacDermed, and Andreas Terzis. Harnessing large-lngguage models to generate private synthetic text. arXiv, 2024.
[46] Da Yu, Peter Kairouz, Sewoong Oh, and Zheng Xu. Privacy-preervingg instructions for aligning large language models. In Proc. of ICML, 2024.
[47] Tong Wu, Ashwinee Panda, Jiachen T. Wang, and Prateek Mittal, for Large Language Models. In Proc. of ICLR, 2024.
In-Context Learning
[48] Xinyu Tang, Richard Shin, Huseyin A. Inan, Andre Manoel, Fatemehsadat Mireshghallah, Zinan Lin, Sivakanth Gopi. Janardhan Kulkarni, and Robert Sim. Trivacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation. In Proc. of ICLR, 2024.
[49] Ricardo Silva Carvalho, Theodore Vasiloudis, Oluwascyi Feyisetan, and Ke Wang. TEM: High Utility Metric Differential Privacy on Text. In SIAM International Conference on Data Mining, 2023.
[50] Saiteja Utpala, Sara Hooker, and Pin- Yu Chen. Locally Differentially Private Document Generation Using Zero Shot Prompting. In Proc. of EMNLP Findings, 2023.
[51] Jimit Majmudar, Christophe Dupuy, Charith Peris. Sami Smaili, Rahul Gupta, and Richard S. Zemel. Diffcrentially Private Decoding in Large Language Models, arXiv, 2022.
[52] Antonio Ginart, Laurens van der Maaten, James Zou, and Chuan Guo. Submix: Practical Private Prediction for Large-Seale Language Models, 2022.
[53] Rushil Thareja, Preslav Nakov, Praneeth Vepakomma, and Nils Lukas. DP-Fusion: Token-L.evel Differen- tially Private Inference for Large Language Models, 2025.
[54] James Flemings, Meisam Razaviyayn, and Murali Annavaram. Differentially Private Nexe-Token Prediction of Large Language Models. In Proc. of NAACL, 2024.
[55] Haonan Duan. Adam Dziedzic, Nicolas Papernot, and Franziska Boenisch. Flocks of stochastic parrots: Differentially private prompt learning for large language models. In Proc. of NeurlPS, 2023.
[56] Junyuan Hong. Jiachen T. Wang, Chenhui Zhang, Zhangheng Li, Bo Li, and Zhangyang Wang. Dp-opt: Make large language model your privacy-preservee prompt engineer. In Proc. of ICLR, 2024.
[57] Kareem Amin, Salman Avestimehr, Sara Babakniya, Alex Bie, Weiwei Kong, Natalia Ponomareva, and Umar Syed. Clustering and Median Aggregation Improve Differentially Private Inference. arXiv, 2025.
[58] Angela Fan, Mike Lewis, and Yann N. Dauphin. Hierarchical Neural Story Generation. In Proc. ACL. 2018.
[59] Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. Locally Typical Sampling. Transactions of ACL, 2022.
[60] John Hewitt, Christopher D Manning, and Percy Liang. Truncation Sampling Language Model Desmoothing. Proc. of EMNLP Findings, 2022.
[61] Wenhong Zhu, Hongkun Hao, Zhiwei He. Yiming Ai, and Rui Wang. Improving Open-Ended Text Generation via Adaptive Decoding. In Pruc. of ICML, 2024.
[62] Nguyen Nhat Minh, Andrew Baker. Clement Neo, Allen G. Roush, Andreas Kirsch, and Ravid Shwartz- Ziv. Turning Up the Heat: Min-p Sampling for Creative and Coherent LLM Outputs. In Proc. of ICLR, 2025.
[63] Estchan Garces Arias, Meimingwei Li, Christian Hcumann, and Matthias Aßenmacher. Decoding Decoded: Understanding Hyperparameter Effects in Open-Ended Text Generation. In Proc. of COLING, 2025.
[64]
Matthew Finlayson, John Hewitt, Alexander Koller, Swabha Swayamdipta, and Ashish Sabharwal. Closing the Curious Case of Neural Text Degeneration. In Proc. of ICLR, 2024.
[65] Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM. In Proc. of NeurlPS, 2017.
[66] David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A Learning Algorithm for Boltzmann Machines. Cognitive Science, 1985.
[67] Mark Bun and Thomas Steinke. Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. In Proc. of Theory of Cryptography Conference (TCC), 2016.
[68] Ilya Mironov. Rényi Differential Privacy. In Proc. of Computer Security Foundations Symposium, 2017.
[69] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis Testing Interpreta- tions and Renyi Differential Privacy. In Proc. of AISTATS, 2020.
[70] Thomas Steinke. Composition of Differential Privacy & Privacy Amplification by Subsampling, arXiv. 2022.
13

---

[71] Ryan Rogers and Thomas Steinke.
A Better Privacy Analysis of the Exponential exponential-mechane rre
Mechanism. DifferentialPrivacyoorg
2021.
https///hifferenciaprrvae org/
[72] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. Boosting and Differential Privacy. In Proc. of Foundations of Computer Science (FOCS), 2010.
[73] Javier Ferrando, Gerard Gållego, Ioannis Tsiamas, and Marta R. Costa-jussà. Explaining How Trans- formers Use Context to Build Predictions. In Proc. of ACL, 2023.
[74] Sofia Serrano, Zander Brumbaugh, and Noah A Smith. Language Models: A Guide for the Perplexed. arXiv, 2023.
[75] Nora Belrose, Zach Furman, Logan Smith, Danny Halawi, Igor Ostrovsky, Lev McKinney, Stella Biderman, and Jacob Steinhardt. Eliciting Latent Predictions from Transformers with the Tuned Lens. arXiv, 2023.
[76] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private Convex Optimization via Exponential Mechanism. In Proc. of COLT, 2022.
[77] Arun Ganesh, Abhradeep Thakurta, and Jalaj Upadhyay. Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets. In Proc. of COLT, 2023.
[78] Alistair Johnson, Tom Pollard, Steven Horng, Leo Anthony Celi, and Roger Mark. MIMIC-IV-Note: Deidentified free-text clinical notes, 2023.
[79] Alistair E. W. Johnson, Lucas Bulgarelli, Lu Shen, Alvin Gayles, Ayad Shammout, Steven Horng, Tom J. Pollard, Sicheng Hao, Benjamin Mondy, Brian Gow, Li wei H. Lehman, Leo A. Celi, and Roger G. Mark. MIMIC-IV, freely accessible electronic health record dataset. Scientific Data, 10, January 2023. ISSN
2052-4463. doi: 10. 1038/03//4 1138//41597-022 597-022-01 -19--x..
[80]
Idiióó Pilán and Pierre Lison and Lilja Øvrelid and Anthi Papadopoulou and David Sánchez and Montserrat Batet The Text Anonymization Benchmark (TAB): A Dedicated Corpus and Evaluation Framework for Text Anonymization. arxiv, 2022.
[81]
Yclp dataset, 2023. https: / ht///uusisssseeeeeeeee yelp com/ www//ooo//aaaeeee tatta/rresourceee/penn wttprcceeeeppeeaaaeee/e.
[82]
Florian Tramèr, Gautam Kamath, and Nicholas Carlini. Position: Considerations for Differentially Private Learning with Large-Scale Public Pretraining. Preprins, 2022.
[83] Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geamhasu, Yangsibo Huang, Matthew Jagielski, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, et al. Advancing Differential Privacy: Where We Are Now and Future Directions for Real-World Deployment. Harvard Duta Science Review, 2024.
[84] Peiyuan Zhang, Guangtao Zeng, Tianduo Wang. and Wei Lu. TinyLlama: An Open-Source Small Language Model. arXiv, 2024.
[85]
AI@ Llama 3.2 Model Card, 2024.
[86]
AI@ Meta. Llama 3 Model Card, 2024.
[87]
Lang Liu, Krishna Pillutla, Sean Welleck, Sewoong Oh, Yejin Choi, and Zaid Harchaoui. Divergence Frontiers for Generative Models: Sample Complexity, Quantization Effects, and Frontier Integrals. In Proc.
of NeurlPS, 2021.
[88] Saketh Mattupalli. DeBERTa-MedNER 2. 2024.
https://huugiingtacc. co/
[89] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal Accounting of Differential Privacy via Charac- teristic Function. In Proc. of AISTATS, 2022.
[90] Gautam Kamath, Argyris Mouzakis, Matthew Regehr, Vikrant Singhal, Thomas Steinke, and Jonathan R. Ullman. A Sias-Variance--rrvaal Trilemmaa for Statistical Estimation. arXiv, 2023.
[91] Alex Kulesza, Ananda Theertha Suresh, and Yuyan Wang. Mean Estimation in the Add-Re Add-Remove Model of Differential Privacy. In Proc. of ICMI., 2024.
[92] Nils Reimers and Iryna Gurevych. Sentence-BERT Sentence Embeddings using Siamese BERT-Networks. In Proc. of EMNLP, 2019.
[93] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural Machine Translation of Rare Words with Subword Units. In Proc. of ACI. 2016.
[94] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: Robustly Optimized BERT Pretraining Approach. arXiv, 2019.
[95] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proc. of ICLR, 2019.
[96] Nikhil Kandpal, Krishna Pillutla. Alina Oprea, Peter Kairouz, Christopher A. Choquette- and Zheng Xu. User Inference Attacks on Large Language Models. Pruc. of EMNLP, 2024.
14

---

Appendix
Table of Contents
A Notation
16
B Adjacency Notions and DP Guarantees for LLM Inference
16
B.1 Adjacency Notions in LLM Inference
17
Sensitivity for the Exponential Mechanism
B.3 Technical Details of DP Baselines
C Full Proofs and Additional Details of INVISIBLEINK
20
C.I Adapting INVISIBLEINK for other Adjacency Notions
22
C.2 Technical Lemmas
22
C,3 Intuition for Top-k+ Sampling
23
Experimental Setup
23
D.I Task: Synthetic Text Generation
................................
23
D.2 Datasets
................................
24
D.3 Models
26
D.4 Evaluation Metrics
26
D.5 Hyperparameter Selection
................................
28
D.6 Confidence Intervals
................................
30
D.7
Computational Resources
30
E
Additional Experimental Results
31
E.1
Comparison with AugPE
31
E.2
Yelp Downstream Utility Experiments
32
E.3
Top-k Selection Statistics
33
E,4
Scaling INVISIBLEINK to Larger Models: Results on LLaMA3 8B
33
E.5
Ablation Studies: Effect of Temperature, Clip Norm, and Top-k paramcter Comparison Adjacency Notions for AdaPMixED
34
35
F
Limitations, Discussion, and Broader Impact
36
G Software Package
36
Example Generations
37
NeurIPS Paper Checklist
15

---

A
Notation
We summarize our main notation in Tab. 3.
Symbol
Description
V
LLM vocabulary, set of all allowed tokens
V*
set of all sequences of tokens (of any length)
(21,...,T:-1) V all previously generated tokens before time-step t-token
LLM logit function, where ((r, (<x)) denotes logit score of next token 2, E V given the prefix æş
o(. (m<))
the vector of next-token logits in R indexed by the token y V
query or prompt for generation (not privacy-sensitive) reference text (privacy sensitive)
R
batch of sensitive references (ri,.... (ri....,pp) rp)
D
dataset of sensitive references
NV
(D). dataset number of generations
Pub
Logit vector d( zee) R!V generated without using any sensitive references from
Φ
Logit vector o( r:, T<))
TR| generated using sensitive reference ri
(lipo(
clips its input vector @ component-wise have norm
DClip ( pub)
Puub + clipe @oub), our proposed clipping function that clips the difference with public logits
Vi
of tokens with highest public logits Pubb
Vi
expanded top-k set of tokens; see $4
B
R|. batch size; controls the computational cost of INVISIBLEINK clipping norm
C
sampling temperature
maximum number of tokens allowed per generation
Table 3: A summary all important notation used throughout paper.
B Adjacency Notions and DP Guarantees for LLM Inference
The goal of this section is clarify the technicalities of the provided DP guarantees for LLM inference and private text generation. In particular, we describe the adjacency notions used (implicitly or explicitly) prior work and how they differ from the ones used in this work. also describe how the advantage we give to the baselines in our experimental comparisons of $5.
DP algorithm must satisfy the guarantee that changing the input dataset by one unit data leads to nearly indistinguishable output. To fully specify this guarantee, we need to mention each of the underlined quantities [15].
Adjacency notion. It describes what it means to change the input dataset (e.g., add/remove/replace some data). We explain this in detail in S..1.
Privacy unit. The unit of data that protected under the definition is known as the privacy unit. This quantity determines whether we protect individual examples (or documents; known as example-level DP), or all examples contributed by a single "user" (known as user-level DP). this work, only consider example-level DP.
16

---

Indistinguishability Notion. This refers to the specific way we quantify how similar the output distributions on two adjacent datasets are. We use CrrceConnetteteed DP (zCDP) throughout:
Definition (Zero-concentrated DP). An algorithm satisfies p-zCDP if
(A(A Alllq, R") pa for all > and all adjacent R. R', where Da denotes the o-- a-Rényi divergence between probability distributions
(6)
1 a log (Ex-q (Bx-)((P())//(XX))
Da(P))))
Conversion formulae between various notions of indistinguishabiiiy are known [e.g. 89, Fig. 2]. For example, p-zCDP guarantee implies (s, 6DD with [69, Thm. 21]
1 log a- as
+ log(1 (all-a-1)) -a-1 Sp+2/plog(1))
inf a>l
ap
B.1 Adjacency Notions in LLM Inference
We explain the different adjacency notions that might arise when the DP definition is instantiated in the context of LLM inference. Recall that we wish to generate text in response to a query using sensitive references R V*.
We define various notions of adjacency between two sets of sensitive references R, R'. Arguably, the most commonly used one in the literature is the add-remove adjacency, where the adjacent dataset is obtained by adding or removing one datapoint.
Definition 4 Remeove Adjacency). Two sets R, C V are said to be add-or-remove adjacent R' RU (r) R R' (r) for some E EV..
This notion of adjacency is semantically meaningful and maps to intuitive expectations of privacy guarantee. Unfortunately, it can be technically challenging to develop rigorous algorithms this setting. In particular, we cannot assume the sensitive dataset size R to be fixed, as adjacent R. R are of different sizes. This makes the dataset size a privacy-sensitivv quantity that needs to be protected with privacy mechanisms; see [90, ŞE), [15, 12.1.1], and [91] for further discussions.
For example, the sensitivity of the mean operation (#1, ........ 8n) + (1/n) Σ 8; function of the dataset size n, meaning that we cannot directly use it in the add-or-remove paradigm. A common workaround (used, for example, in private learning with DP-SGD) is to privatize the sum query ($1,.... sn) + 2i=1 and post-process it to obtain an estimator of the mean. Unfortunately, this is not possible in the setting of $3: the logit vector & in Eq. (2) is actually obtained by averaging, and we cannot directly use the above trick here.
common workaround to avoid these technical challenges with the add-on aud-or-removy adjacency is to the so-called replace-by gelacc-byynulll by-null adjacency, where the removal of element is simulated by swapping it with a special (prohlem-dependeel seplace-bynnil adjacency in the context of L.LM inference in this work by choosing the null element as the empty string:
null element [e.g. 70, Sec. 6.2]. We instantiate the
Adjacency). Two sets R R= (ri..... ra) and R' (r'(...,, ...,,,")) of equal size said to be adjacent in the replace-by-uull model of adjacency if there exists index j E [n] such that r; = = for all i + and one of F r' equal the empty string Q.
Definition (Replace-by-
Another common way to instantiate the null element leads the so-called zero-out adjacency:
Definition (Zero-Out Adjacency). Let 1 denote a special null element such that the logits Φ(v q, =1, = 0 are always equal to zero for any token E V. query q E V*, and prefix &ee. Two sets R = (ri,..., ......,r], ro and R' = -r'i...., .....,))) of equal size n are said to be adjucent in the zero-out notion of adjacency if there exists index j E [m] such that r; r for all i 4 and one of " equal this null element 1.
'To be fully formal, the space of all possible reference sequences r should be enlarged to V U Uf1} to accommodate the null element 1.
17

---

Note that zero logit vector implies next-token probabilities that are uniform over the vocabulary. As argued $4, this rather unrealistic could produce incomplete word pieces, while r = 0 as the empty string still gives reasonable next-token predictions using the pretrained model's language and world knowledge. Further, the empty string of Theorem is a semantically more meaningful null element than an artificially created 1 element from Theorem 6. Thus, we primarily adopt the replace-by-nui by-ull adjacency in this work.
The replace-one (or swap) notion of adjacency is also commonly studied. Here, one element of R is replaced by any other arbitrary element to get R'. It provides an se 2x stronger privacy guarantee at the same (usually at the cost of a larger noise multiplier); see [15] for discussion.
Remark 7.
B.2 Sensitivity for the Exponential Mechanism
Throughout this work, we consider the following notion of sensitivity in the context of the exponential mechanism. Note that the sensitivity depends on the exact notion of adjacency considered ($B.1).
Definition 8 (Sensitivity). The -ee-siiittvv referred throughout as simply the sensitivity, of function f F:S. + R (for any set S and any output dimension d) under an adjacency relation is defined as:
sens(f) max [I) f(R) = max max R-R
[[(()))
R R I.....
The exponential mechanism with a target privacy level of p-zCDP selects an item i {L..... d} with respective scores [f(]], with probability [71]
u2p sens(s)
[f(R)];
exp
E/= exp
VRp sens(
[f(]],
Recall that we wish to generate text in response to query q using sensitive references R C V*. In this context, Theorem 8 is instantiated with f(R) = o( R, x<1) E R/V, where we index an element RVV with a corresponding token E V.
B.3 Technical Details of DP Baselines
In this subsection, we clarify the notions of adjacency used in prior works.
B.3.1 Adjacency Notion of Amin et al. [13] and Theory-implementtiion Gap
The theoretical analysis of Amin et al. [13] (in particular, their Theorem 1) operates under the add-or-remove notion of adjacency (Theorem 4). As discussed in $B.1, aggregating the clipped logits using the mean operation requires particular care the size of adjacent datasets can be different. Amin et al. [13] address this issue with two changes:
(a) they batches of variable sizes (e.g. via hashing datapoints to batches); and
sB) (b) they use the re-scaled sum query (s1..... (B) + (1/G) E ( 8s, where G is guess of the (variable and possibly random) batch size B.
To ensure correctness of the privacy guarantee, the scaling factor G must be fixed priori and in data-independent manner. The accuracy of the guess G (relative to the true batch size B) does not impact the correctness of the privacy guarantee, though it can significantly affect the utility.
However, there is mismatch between the analysis and implementation Amin et al. [13]. In their implementation, they form batches of a fixed size B by sampling without replacement. Further, they take the guess of the batch size as G = B. Since this depends on the dataset (specifically, via its size B), the experimental setting is not covered by their stated DP guarantee (which requires G to be fixed a priori) under or-eoveee adjacency.
We circumvent this issue by choosing appropriate adjacency notion: we directly analyze the bred-batch--sze version of Amin et [13] (i.e. the one that is actually implemented) in the zero-out (Theorem 6) replace-by-null (Theorem 5) notions of adjacency instead of the add-or-remove
18

---

adjacency. As discussed in ŞB.1, this small change allows us to treat the batch size B as public (see also [15. $2.1.1J,, and lets us take G without any privacy leakage.
Sensitivity Bounds. We have the following bound on the sensitivity of the clipped-and-aggrealle logits Φ:
Property Let the dataset set B R be fixed. Then, the sensitivity of the operation, 9
S(R)= = R
clipo (Ø(- R. x2))
(8)
given by:
under zero-oul udjacency,
sens(f) = 2C
under replace-by-mull adjacency.
B
Proof. We start with zero-out adjacency. Let R = R'' differ in their first element where rí =.1. Then, have that
[])(R) - f(R'Il
| (. r1, - clipo (e( ,,,)))l
B
|Icipo (o( mi a
C
Similarly, for replace-by-null adjacency, let R ~ R' differ in their first element where r' = 0 is the empty string.
1
s(R))l
||cipe (d( (1, - (o xx))
B
1
$ B
+ ||cipc 1. al))
2C
< B
where we used the triangle inequality on the fo norm for the first inequality.
the more natural replace-by by-llll adjacency in our experiments, we (incorrectly) use the sensitivity bound obtained for the zero-out adjacency from Theorem 9. This gives Amin et al. [13] advantage of factor of 2 in the sensitivity. Yet, find that INVISIBLEINK outperforms their method in sartaccy-uiltyy-ooppr tradeoffs.
Convention in our Experiments. While
B.3.2 AdaPMixED: Adjacency and Data-Dependent DP Guarantees
AdaPMixED [19] uses the add-remov notion of adjacency, but it gives data- data-dependent privacy guarantee, while we give a data-ine lata-independent privacy guarantee under the replace- by-lll adjacency.
Strictly speaking, the privacy guarantees across different adjacency notions cannot be directly compared. Thus, we modify AdaPMixED to use the replace-by-null adjacency and report these results in the main paper.
We can also cautiously compare the add-or-remove adjacency of AdaPMixED and the replace-by- null adjacency of INVISIBLEINK. This is because the semantics of these two notions of adjacency are expected to be similar [15, 70]. Comparing (AdaPMixED, re-rove) and (AdaPMixED, replace-by by-icl--byuuull) reveals no significant difference in the qualitative trends; see $E.6 for details.
Furthermore, AdaPMixED gives data-dependent privacy guarantees. For example, the 7CDP notion (Theorem 3) can be phrased in the data-dependent setting under the replace-by-null adjacency as follows. An algorithm A(g, R) satisfies p( R))xZDPPi if
Daym (A(g, R), Alg, R')) S P(R)a
'The clipping function employed by Amin et al. [13] incorporates recentering step, logits are invariant to additive shifts. We omit this detail in our exposition it does change the mathematical properties.
19

---

for all a > 1 and all datasets R' that can be obtained from the given dataset R by replacing any one of its elements with the empty string here
Da (P. Q) max (.(
is symmetrized Rényi divergence. This guarantee holds only for the given sensitive dataset R. In contrast, Theorem must hold for all R R!.
Thus, our data-independent guarantees are strictly more general than the data data-dependent guarantees given by AdaPMixED. The latter are, general, privacy-sensttive and need be sanitized before release. In contrast, our privacy guarantees are worst-case and hold independent of the dataset.
Finally, have the advantage of straightforward privacy accounting. Given desired privacy level, compute budget, and maximum generation length (in terms of number of tokens), we give a recipe in $4 to tune the other hyperparameters of our method. In contrast, data-dependent DP guarantees can only be given by grid search on the actual sensitive dataset R. In practice, one must account for the privacy of such hyperparameter tuning [20], making potentially more costly in terms of both computation budget and privacy budget.
B.3.3 Adjacency Notion of AugPE
AugPE [41] is synthetic text generation algorithm in the API access model. Note that focus the less restrictive whitebox model, where per-token model logits are assumed to be available.
AugPE assumes the add-remove notion of adjacency (Theorem 4). Their key technical step is to
construct a nearest neighbor histogram. Given a set 5 = (æ1...... Fmm) of candidate synthetic generations and set D {ri,...,PM) TN of real data points, the idea is to compute the nearest neighbor histogram
N H(x)) = Σ I(NN(r), =x;) where NN(r,, arg min dist(x,r.) 1=1
(9)
#ES
the nearest neighbor of r, from the set S according a given distance metric dist(-. (with ties resolved arbitrarily) and II()) is the indicator function which takes the value I when its argument is true and zero otherwise. Xie al. [41] take dist as the Fuclidean distance some embedding space. This histogram H(-) E I is then privatized using the Gaussian mechanism. Its fz-sensitivity is as follows (with an elementary proof provided for completeness).
Property 10. For any fixed set of synthetic text S {ri,..., F.), the fz-sensitivity of the map (ri...., TN3 +
(xm)) ) is:
under the add-or-un re-oovee adjacency;
. .2 under the replace-by-null or zero-out adjacency.
Proof. Under the add-or-remove adjacency, moving from dataset D neighboring D' will change at most one entry of the histogram H-) by at most I, leading to an fz-sensitivity of at most However, under the replace-by-nie or zero-out adjacency notions, most two entries of the histogram (-) will change by at most This leads to la sensitivity of /2.
Convention in our Experiments. Similar to the case of Amin et al. [13], we give AugPE an advantage by incorrectly using its best sensitivity from Theorem 10. In particular, we use the more natural replace-by-ne bound obtained for the add-or-remow adjacency from Theorem 10. This gives AugPE an advantage of a factor of /2 in the sensitivity. Yet, we find that INVISIBLEINK far outperforms AugPE in privacy-utility compute tradcoffs.
adjacency in our experiments but we (incorrectly) use the AugPE's sensitivity
C Full Proofs and Additional Details of INVISIBLEINK
Below, we give the proofs of Theorem I and Theorem We also give the sensitivity DClip under different notions of adjacency below.
20

---

Proof of Theorem 1. Let the dataset size B = R be fixed. For replace-by-mon adjacency. consider the adjacent dataset R {ri...., rB) and R' (ri....,T'!) that differ their first element where ri 0 is the empty string. We need to bound the sensitivity of the map
B
fDC (1 (ri.... TB) = B
( 1 ri xet), 0l | q,x)))
(10)
Below, use shorthand pubb o( q, and Φ; := llg, are public and private
logits respectively for R and Ø :- o6- q, T 2et) are private logits for Rt. Noting that (a) Φ; = of for + by assumption, and (b) Φ1 Puub under the replace- splaac-by-null adjacency, we upper bound the sensitivity as
sens(Socip)
[DCiipp R
Soccip 1l
B
B clipo (0) )pmu))
clip Qpub)
Σ
|Icipo (Φ) Opub)
clipo (0i @oub) 1100
|clipa( Qbub) 110
IA
B
where the last line follows because too norm of logits clipped using clipa is bounded by C.
Proof of Theorem 2. Algorithm 1 consists of the application of the map SDClip. defined previously in Eq. (10), followed by the application the exponential mechanism with a temperature of 7 (in the form of softmax sampling). Note that the Top-k+ selection step in Algorithm is agnostic to the values of the private logits .i...., ΦB and therefore does not incur any additional privacy cost.
Consider the generation of one token using Algorithm 1 given arbitrary Eet. Using the definition of the exponential mechanism in $B.2 (ef. (7)), the p-zCDP guarantees for generating any one token is given by
1
(sens(focip)) 2
1
C
2
C2
Ptok
2
T
BT
2B2
(11)
where sens(foclip) is obtained from Theorem 1.
To generate sequences which may contain at most T tokens T1,..., ,T. the zCDP guarantees obtained for single-token generation in Eq. (11) may be adaptively composed sequentially over all tokens. Then, the entire sequence x (FI,...,TTT) with T' < T satisfies PCpp where (cf. Theorem 13())
TC²
Preq S T Ptok 2B2
This completes the proof of Theorem 2.
Note that this guarantee holds for the generation of multiple sequences using disjoint batches of references from the full sensitive reference dataset by parallel composition of the p-7CDP guarantees.
Corollary 11. Consider partitioning a dataset D = {ri,..., TN) into n. disjoint batches RI...., Rn of size B N/n (assumed an integer), i.e. R, n R, = AAvi + j. Suppose further that this partition is data-independent. 10 Suppose we generate texts Lt, Fy using Algorithm I such that &; only sees sensitive examples R; and satisfies CCPP individually. Then, the map D (x), .......... Rr,) also satisfies PCea
Proof. This follows from Theorem 2, and from the parallel composition for p-zCDP guarantees in Theorem 13.
1hah is, a partitioning is performed using process that is agnostic to the content of the data. This ensures that the partition is not influenced by any patterns, information, or outcomes within the dataset. This precludes partitioning based clustering, for instance.
21

---

Note that the privacy guarantee in Theorem 11 does not depend on the number of synthetic texts generated. The number of possible generations using INVISIBLEINK for fixed dataset size N is thus limited only by the number of possible partitions n S [N/B].
C.1 Adapting INVISIBLEINK for other Adjacency Notions
The notion of adjacency used is central to the interpretation of the obtained privacy guarantees, as well as to the sensitivity analysis. We use replace-by-null adjacency to derive the privacy guarantees for INVISIBLEINK
Theorem and Theorem 2; refer to $B for a full discussion of other adjacency notions and on how they have been used in previous work.
We also state the sensitivity of fociip under zero-out adjaceney in Theorem 12.
Property 12. Let the dataset B |R| be fixed. Then the sensifivity of the map fDCiip (ri,...:TB) + B E DClipo pubb) defined in Theorem I, under zero-out adjacency, 2C
sens(foccip) = B
Proof. For zero-out adjacency, consider adjacent datasets R (ri...., and R' (ri...., r')} } that differ in their first element where r' = the empty string. We need to bound the sensitivity of the map fDClip from Eq. (10), As in the proof of Theorem 1, we use shorthand @pub == o( 1.g. (.) and Φ; == o( q, Ts; &ett) are public and private logits respectively for R and &f s( q, r, (x) are private logits for R'. Noting that (a) Φ; &f for i A 1 by assumption, and (b) of under the zero-out adjacency, we upper bound the sensitivity as
sens(JDcip)
[[ciip R - SDccip( 1l
B
B
clipo (Ø: - @pub)
Σ
clipo (Ø) )pub)
B
1=1
||cipo Qbub) - clipo - @bub) llo 1l
1
| @pub) - -clipo( - @pub) 1loo
B
(0) 1
1
|| @ppb) 1o +
|clipo(
@pub) 11:00
B
2C
where (c) follows from the triangle inequality on the foo norm and the last line follows because the foo norm of any logits clipped using c- is upper bounded by C.
L
The 2x increase in the sensitivity of fDclip under zero-out adjacency causes 4x increase in the p-zCDP guarantee of Algorithm for the same parameters and settings as under the replace-by-null adjacency. This highlights the need for careful definition of adjacency notions in DP.
C.2 Technical Lemmas
We recall some technical results that are useful for other proofs.
Lemma 13 (Adaptive Composition of zCDP [67]). For any fixed sets X,Y, let Ai X +Y, be Pi-zDDP, and A2 : X* x Y > Y22 be P2-ZCDP mechanism with respect to its firsi argument for any fixed second argument. Then, we have the following adaptive composition resulis:
(a) Sequential: the mechanism A(D) = A2D, for Ai(D) is P2)
(b) Parallel: the mechanism A(D) = A2,, Yi)) for Y1 = (Di)) and any fixed
iata-inndpendeen partition Dr, D2 of is max (Pixpp)--CDD
This result can be extended to an arbitrary number of mechanisms by induction.
22

---

C.3
Intuition for Top-k+ Sampling
As described in $4, we isolate the contribution of each private logit vector Φi, following clipping and averaging, as -
Public logits Puh
Clipped Private Logits 9; c
Expanded Top-k
Vocabulary
Sensitivity = C/B
Suyseoura Foog valuuc
Lub top-k threshold
Discarded for dao but not oj
2C
Discarded for d Ppu
B
top-k
Expanded top-k
threshold
Figure 7: Schematic describing Top-k+ sampling. After clipping and aggregating using DClip, the logit values corresponding each token change by at most c. i.c., the sensitivity of the private clipped logits. Top-k+ sampling, lowers the top-k threshold of the public logits by B The expanded vocabulary Vi captures all tokens in superset of the top-k vocabularies of the public logits Ppub. and all the clipped private logits dh
2C
In Fig. 7, the logit values of each token in Φ differ from those in Φ by at most C. Further, the top-k sets of both these logits may differ as token ordering around the top-k threshold changes in the following two ways: (i) tokens in the top-k of pubb can drop out of the top-k set of $ their logit value decreases, and (ii) tokens outside the top-k set of @uub can enter the top-k set of delip as their logit value increases.
B.
All tokens which exit the top-k set of pubb due (i), must still lie within C of the top-k threshold B of Puub- However, this could potentially decrease the top-k threshold of @ by at most B when moving Th Thus, all tokens which enter the top-k set of -h due (ii) must lie within 2C of the top-k threshold of pubb Thus, lowering the top-k threshold of @ubb by captures all tokens of interest, as shown by the toy example in Fig.
C
B
D Experimental Setup
D.I Task: Synthetic Text Generation
Our goal is to generate high-quality, long-form synthetic data from a given private dataset of refer- ences, while under rigorous DP guarantees on the privacy of the references. We model the references R R= (Ti. T ) as part of the context for next-token generation in the LLM. The query prompts q. contain instructions for text generation including general details about the sensitive dataset such as domain, type of text document, etc. The public and private (here, private prompts mean prompts with sensitive references embedded in-context) query prompts used for the generation of synthetic text samples for various datasets are listed in Tab. 4. Examples of the references for both Yelp and TAB datasets given in Tab. 5.
Algorithm describes the generation of 1 text sample from a batch sensitive references R size B. To generate multiple synthetic text samples, we partition the entirety of the sensitive reference dataset into B-sized chunks. Since the dataset partitions are defined completely lata-independent manner, we may compose the DP guarantee parallely across batches; see Theorem 11. The theoretical
23

---

privacy guarantee for the generation of multiple text samples is thus the same as that of 1 text sample, i.e. the overall privacy guarantees are independent of the number of synthetic samples generated and only depend on the maximum number of BPE encoded tokens in each input.
Prompt Type
Dataset
Prompt Text
Private
Here is the text of the discharge summary of a patient discharged from hospital
MIMIC
Text: "<private reference here>"
Please give me another text of fake patient discharge summary for discharge from a hospital. Include typical sections like admit- ting diagnosis, major procedures (if any), discharge medications (using fictional drug names and dosages), and general follow-up instructions. Do not include any names, dates, or specitic medical record numbers. The output text must begin with the exact words "Discharge Instructions.".
Public
Please give me text of a fake patient discharge summary for discharge from hospital. only need fictional and representative examples for a non- con-medical purpose. Include typical sections like admitting diagnosis, major procedures (if any), discharge medications (using fictional drug names and dosages), and general follow-up instruc- tions. Do not include any names, dates, or specific medical record numbers. The output text must begin with the exact words "Dis- charge Instructions:".
Private
Here a text with Business Category: "<business category>" and Review Stars "<review score>" out of 5.0. Text: "<private reference here>"
Yelp
Please output one more similar review of a fictional place with the same score and of the same category of business. Poor reviews have lower scores and good reviews have higher scores.
Public
Please give me fake Yelp customer review of fictional business with Business Category : "<husiness categorys" and Review Stars "<review score>" out of 5.0. Poor reviews have lower scores and good reviews have higher scores.
:
Private
Here is the text of a case transcript set before the European Court for Human Rights.
TAB
Text: "<private reference here>"
Please output a similar transcript of fictional case under European Court for Human Rights. Begin with the phrase: "PROCEDURE: The case originated in an application'.
Public
Please output transcript of fictional case under European Court for Human Rights. Begin with the phrase: 'PROCEDURE: The case originated in an application'.
Table 4: Public and private prompts for MIMIC, Yelp and TAB datasets; The private references are inserted in the space denoted by "<private reference here>". The system prompt across all settings is: "You chatbot".
D.2 Datasets
We use both publicly available open-access datasets and licensed datasets: MIMIC IV Clinical Notes dataset [78, 79], Yelp Reviews dataset [81], and the Text Anonymization Benchmark (TAB) [80] dataset. The respective license and data use agreements of the various assets use have been duly followed throughout this work.
MIMIC-IV Clinical Notes. This dataset is large, de-identified collection of medical text associated with ICU patients, including discharge summaries, radiology reports, and nursing notes. It is widely used for clinical NLP tasks such as diagnosis classification, named entity recognition, and patient cohort identification. The dataset poses significant privacy challenges due the presence of sensitive patient information, making it ideal choice for evaluating privacy-preserve language models.
24

---

Dataset
Sensitive References (Exemplars)
I've been here a few times. The service has been very good all times. The food is hit or miss on some entrees. Do not order the poutine frics. They have sauce. It's like cating fries with cheese and meat on them. No gravy like poutine is supposed to have. Their salmon special that they had one day was very good. It had an Asian flare. I also have had the Asian noodle dish which was good. Their burgers are vel popular there and look tasty. There is something the menu for everyone! They Also have good cocktails.
Yelp
PROCEDURE The case originated in application (no. 36244/06) against the Kingdom of Denmark lodged with the Court under Article 34 of the Convention for the Protection Human Rights and Fundamental Freedoms ("the Convention") by Danish national, Mr Henrik Hasslund ("the applicant"), on 31 August 2006. The applicant was represented by Mr Tyge Trier, lawyer practising in Copenhagen. The Danish Government ("the Government") were represented by their Agent, Ms Nina HlosstChhristensen of the Ministry of Justice. On 5 September 2007 the Acting President of the Fifth Section decided to give notice of the application to the Government. It was also decided to rule on the admissibility and merits of the application at the same time (Article 29 $3).
TAB
Table Examples from the Yelp and TAB datasets. We use these are privacy-sensitive references for synthetic text generation. We do not provide examples of the MIMIC dataset (or even synthetic generations) to comply with its license.
Further, the dataset is not available for open-access and cannot legally be used for pre-training general-purpose LLMs such as those we use in our experiments. This dataset is released under the PhysioNet Credentialed Health Data License 1.5.0, and may be accessed via the PhysioNet website (uttps://payyiionet org/ http//oonn///mmiiiiiieeeeee ientlmmcc-iiinei wit.iiiiiiiiiiteeee.mmmm ntt.nootte//////
For our synthetic text generation task, we use the discharge summaries released as part of the dataset. In particular, we extract the discharge instructions from within these files. These are selected as they often contain succinct summaries of patient symptoms, diagnosis, treatment, as well as aftercare instructions. Further, almost all discharge summaries contain a section on "Discharge Instruction" " allowing us to extract almost 311K valid private references from the dataset. In accordance with the License and Data Use Agreement of the dataset, we do not release the original dataset, processed text samples, or synthetically generated private samples.
Yelp Reviews. We use the processed Yelp Open dataset [81] from [44] released by [41]. This dataset contains 1.9M of user- seeeereedd reviews and ratings for businesses (see Tab. 1 for precise size), labelled by business category (10 categories) and review scores (5 possible scores) to give a total of 50 sub-categories. Although not overtly sensitive, it contains personal opinions and location references and has previously been used to design private synthetic text generation algorithms 441,
The Yelp Open dataset is released under data agreement and terms of use, which present in the downloadable zip file hosted by Yelp. This is distinct from but similar to the (also publicly available) Yelp Reviews dataset hosted by HuggingFace; in particular, they contain examples of similar reviews, labelled by review scores across several (unlabelled) business categories.
The respective GitHub repositories of [41] (link) and [44] (link) are released under the Apache 2.0 and MIT licenses. The license under which the processed dataset released not explicitly mentioned in either repository. The dataset may be downloaded from this link by following the instructions given by [41].
Text Anonymization Benchmark (TAB). This dataset [80] is a dedicated, open-source corpus designed for evaluating text anonymization systems. It comprises 1268 English-language court cases from the European Court of Human Rights (ECHR), manually annotated with semantic categories of personal identifiers, masking decisions based on re-identification risk, confidential attributes, and co-reference relations. TAB provides a high-quality benchmark for assessing the effectiveness of anonymization models in legal and crivacy-riticcll domains. We use the text released in this dataset as low-resource task for generating high-quality synthetic data when the batch size is constrained to be small. Using a large batch size for this dataset results in a very small yield of synthetic data, for maximum of 8 synthetic examples this constrains to a batch size B < 7 if we wish to generate at least 100 examples.
example: B = 127 gives
The dataset is released under the MIT License and is publicly available at this link.
25

---

Note on Choice of Dataset. We note that several common datasets used in prior work (such as AGNews, TREC, DBPedia, WikiMovies, etc.) are incompatible with our setting of long-form text generation due to their relatively shorter texts (< 200 tokens). Further, several of these datasets (like IMDb, etc.) are well-represented in the pretraining data of most L.LMs. Since publicly prompted LLMs can generate high-quality synthetic text for such datasets, high degree of overlap between the pretraining and target data distributions skews the conclusions of private data analysis [82]. Thus, we prefer using benchmarks that are sufficiently out-of-distribution relative to the pretraining data and preferably contain real privacy- data.
Accordingly, we use the MIMIC IV Notes dataset as the primary dataset for experiments, since contains real patient discharge notes with sensitive medical data, and cannot legally be used for pretraining LLMs as per its data use agreement. Similarly, the TAB dataset contains sensitive identifying information (demographic traits, spatio-temporal markers, biographical details, etc.) from European Court of Human Rights cases. We use the Yelp dataset representative dataset that overlaps significantly with the pretraining data (similar to the other datasets discussed above).
D.3 Models
We use the following language models in our empirical evaluation: TinyLLaMA IB [84], LLaMA3.2- IB [85], and LLaMA3 8B [86]. All models were loaded in torch. boato116 precision.
LLMYLLaMA is a compact, open-weight language model trained on trillion tokens and with only 1.1B parameters. Despite a smaller size, it retains strong performance on basic language modeling tasks and is ideal for fast experimentation in compute-constrained settings. For our experiments, we used the instruction-tuned version TinyLlama-1 11-11BChhh Chat-hhatll 0 of this model. This model is released under the Apache 2.0 License and may be accessed via HuggingFace at: TinyLLaMA IB.
The LLaMA3.2 IB model is a smaller variant from the LLaMA3 family. Being multilingual model with very large vocabulary (128K tokens) and context size, an ideal candidate demonstrate the improvements offered by Top-k+ sampling. Additionally, we also conduct one set of experiments on larger ILLMA3 8B model. For our experiments, we use instruction-tuned versions of both models. The former is released under the Llama 3.2 Community License Agreement and may be accessed via huggingface at: I.LaMA3.2 1B. The latter released under the Llama 3 Community License Agreement and may be accessed via huggingface at: LLaMA3 8B.
D.4 Evaluation Metrics
For our empirical evaluation, we evaluate the generated text on several different metrics to highlight the advantages of INVISIBLEINK compared to baselines.
MAUVE score. To evaluate the distributional similarity between synthetic and real text corpora, we use the MAUVE score [17, 18, 87], which is designed capture both quality and diversity in text generation quality. Unlike traditional metrics (e.g., BLEU, ROUGE). MAUVE compares entire distributions rather than individual samples. The result a number between and with denoting that the two distributions are identical, and O denoting that the two distributions have no similarity.
We make the following choices compute the MAUVE scores:
Implementation: We use the open-source mauve-tes package released by [17, 18)."
Reference samples: Held-out samples used
Number of generations and references: Varying between 100 and 1000, as described in Tab. 1. We use equal number of samples from both the generations and references.
Embedding model: Sentence Transformer model [92], version all all-mpnet baannet-baeeve22
Number of bins: N/20 where both reference and generated distributions have N samples.
Scaling factor: 0.9, across all settings throughout this work.
To compute all MAUVE scores in this paper, we use the Transformme embeddings of the text sample [92]. We find these embeddings to be of higher quality, and corresponding to better and
11 Available at https://github. http:///ggttuuu..oommriiieeeeeee com/ http://risshhn////ennn /mauve.
Available https::/huggingtteee cotaaacee....eoeeeeeeeeeeeeeeeee http//entnnceeeeeeeeeeeeeeeeeeee htt/s//teeeeeetttaaoreeeeeeeeeee www.stttrannnnnseeeeeeeeeaa aapmm/ett-mmmm--aaeeeeaaaaa-ee-e base
26

---

MedNER Category
Example(s)
Counted
THERAPEUTIC SERRAPPETICCPROOEDUURE
"paracentesis", "colonoscopy"
PROCEDURE
"blood pressure", "endoscopy"
DETALED_DESCRIPTONN
DETAILED DESCRIPTION
"IV", "constipating"
DISEASE DISORDER
"cirrhosis", "pneumonia" "pain", "fever"
SIGN SYMPTOM
SEVERITY
"worsening", "severe"
DISTANCE
"1.SL", "5 "5pounds"
DOSAGE
"40 mg". tablet every hours"
LAB VALUE
"high". "improved"
MEDICATION
"Lassix", "Tylenol"
COREFERENCE
"incision", "splint"
ADMINISTRATION
"intravenous", "oral"
BIOLOGICAL STRUCTURE
"stomach". "esophagus" "hospital". "emergency room" "yourself" "admitted", "discharged"
NONBIOLOGICAL LOCATION LOCATIOO
FAMILY HISTORY"
CLINICAL_EVENT
DURATION
"I day", "several weeks"
HISTORY
"alcohol", "activities" "I week", "24 hours" "up"
X
DATE
AGE
SEX
"male". "female" ":55pm". ":20am"
TIME
AREA
VOLUME
"7 x 6.6 cm". "4.9 6.4 centimeter"
OTHER ENTITY
22" "day"
Table 6: Medical Named Entities: The various medical named entities captured by the DeBERTa-Med-NER
model [88] and some identified examples for each category. most medically relevant among these categories, as denoted by rightmost column. Note that some of omitted columns are not reliably detected by the model (denoted by ").
MedNER evaluations, we only count the
more meaningful MAUVE scores. In particular, we use the all- 1el1-mpnet-base-ve model, which returns 768-dimensional embeddings of imput texts, truncated to 384 tokens. The final score is also scaled appropriately to facilitate easy comparisons by setting the scaling factor to 0.9. It is crucial to note that the value of the scaling factor and other hyperparameters used to calculate MAUVE scores impact the obtained scores. MAUVE scores are thus best used for relative comparisons, such as in this work, and the absolute values themselves are less meaningful.
Medical Named-Entice Recognition (MedNER). The original MIMIC discharge notes contain details on various medically significant terms such diseases, medications, treatments, etc. We found in our early experiments that some generation methods can fail to generate such domain-specific terms. Since wish the synthetic generations to reflect all statistical properties of the original dataset, it is desirable for generation algorithms to also generate relevant medical entities, at the same rate the original data.
In other words, we are interested in Medical Named Entity Recognition (Medical NER). This is common task that focuses on identifying clinically significant entities such diseases, medications, procedures, anatomical terms, and patient attributes from clinical notes, health records, or other medically relevant text data. We use the counts of medical named-entities in the generated text measure of the level of detail and specificity preserved in the synthetic text.
We the DeBERTa- MEEERRT--Me--ER-- [88] model to label all medical named entities in the generated text. The model recognizes 41 categories of named-entities of which the text subset of the MIMIC dataset extract, as described in $D.2, contains only 25 classes. We further select and count the presence of the most relevant medical named entities; 13 classes like therapeutic procedure and disease/disorder included, but donain-agnostic classes like date and time excluded. The exact details presented in Tab.
Generation Perplexity. Perplexity is a standard metric used to evaluate the quality of generations of probabilistic language models, including I.MMs. Perplexity is defined as the exponent of the average negative likelihood of generating every token of the observed sequence, conditioned on
27

---

the previously generated tokens. The perplexity of a sequence a = (01. is defined as
PPL(x) exp
log P(x: xx(e)
where log P(æx xee.) is the log-likelihood of the hhhh token conditioned on the preceding tokens æ<r (with <<1 0), according to the language model P. We take the model P used calculate the perplexity of all text samples as GPT-2 small (with 117M parameters).
A low perplexity value indicates that the model assigns a higher likelihood to the observed sequence. We wish the generated synthetic text to match the original text dataset in all statistical properties, including perplexity under any given language model. Thus, achieving small difference in the average perplexities between the generated and original text distributions is desirable. This is measured by the APPL metric [16], defined as
APPL-
Σ ØE
(2)(2)
1 R
Σ PPL(()) PER
X
where R is the original dataset of sensitive references and X is the synthetically generated dataset.
Length Distributions. The privacy budget of per-token privatization algorithms is composed over the number of tokens generated. For methods like Amin et al. [13] and AdaPMixED [19], the number of tokens generated limited by the privacy budget. In contrast, for our method, we set a predetermined maximum number of allowed tokens and calculate other hyperparameters based on this number. Further, unlike previous methods that are not well-suited for long-form text generation due to either computational privacy constraints, we aim produce longer and higher-quality text. Since the length of generated text is another statistical property of the private reference dataset we wish to mimic, we use the number of tokens generated by the model, referred henceforth as the generation length, as an evaluation metric.
The set of all possible tokens, called the vocabulary, differs from model model. A tokenizer is used by language models to convert text strings into sequences of valid tokens (each denoted by an integer). The I.L.MA3 models use byte-pair encoding (BPE) model based tiktoken, whereas TinyLLaMA uses a BPE model based on SentencePiece. A characteristic of BPE models, introduced in [93], sub-word tokenization, which splits up one word into one or more tokens depending on the length of the word and the substrings in it. The number of words in text sample is thus not equal to the number of tokens in the same sample. The latter also depends on the exact tokenizer used.
To measure the generation length for generations corresponding to a given model, we use the number of BPE tokens generated by the corresponding tokenizer. Generation lengths reported are thus not directly comparable across families of models. The generation lengths of real texts are calculated separately for every model and reported with the corresponding results (wherever applicable) for comparison. We report the average generation length (in number of tokens) over all generations of æ (and its confidence intervals, described in $D.6).
D.5 Hyperparameter Selection
We discuss the choices of hyperparameters, the range explored, and the settings for reported results across all methods, INVISIBI.EINK and other baselines, in this section. We also note that to allow comparisons between methods, we convert all DP guarantees into (e, 6) g
INVISIBLEINK. INVISIBLEINK, described in Algorithm 1, has the following hyperparameters: the clipping norm C, the batch size B, the sampling temperature and the top-k sampling parameter. For given e, the heuristics for choosing optimal hyperparameters are given in $5. To arrive at this heuristic, conducted thorough hyperparameter search for full vocabulary A [V| variant of the model; the full range of hyperparameters explored for each dataset and model we use is given in Tab. 7. We report results by tuning the sampling temperature for various values of and B.
Based on these results (presented in detail in $E) and on the exploration of non-private generation in Fig. 2, we report results for INVISIBEEINK with fixed sampling temperature 1.1 for A < [V]
138 for all methods is chosen be sufficiently small value of 10
28

---

Dataset
Model
Hyperparameter
Range Explored
B
[4, 16, 32)
TimALLaMA IB
[0.8, 0.9, 1.0, 1.1, 1.2]
MIMIC
B
8
LLaMA3.2 IB
1.1
B
8
LLaMA3 8B
1.2
B
[2, 4, 8, 16, 32]
Yelp
LinYLLaMA IB
[0.8, 1.0, 1.2]
B
8 [0.8, 1.0, 1.2]
TAB
TinyL.LaMA 1B
Table 7: Hyperparameters for INVISIBLEINK variant with [V].
and r = 1.0 for & = V.. We explore a range of top-k parameters for various settings; see Tab. Our empirical results in $5 show that setting k 50 100 shows superior performance all existing baselines, as well as the full-vocabulary (k [V] variant of INVISIBLEINK.
Dataset
Model
Hyperparameter
Range Explored
B
[4. 8, 16, 32] [10, 50, 100, 500] [1.0, L.2.
LanyLLaMM 1B
k
MIMIC
B
8 [10, 50, 100, 500]
LLaMA3.2 IB
1.1
8
LLaMA3 8B
k
[10, 50, 100, 500, 1000, 5000]
[4, 8, 16, 32]
Yelp
TinyLLaMA 1B
k
[10, 50, 100]
8 [10. 50, 100]
TAB
TinyLLaMA IB
k
Table 8: Hyperparameters for INVISIBLEINK (k: < [V]. We set T = 1.2 wherever unspecified.
Amin al. [13]. The algorithm proposed by [13] has similar hyperparameters: C clipping norm, B batch size, Tprv private sampling temperature, Tpub public sampling temperature, 0 threshold for Sparse Vector Technique (SVT), noise parameter for SVT. Further, the privacy guarantees depend on the number of times token is sampled from the aggregated and clipped private logits. As
Dataset
Model
Hyperparameter
Range Explored
B
332, 64, 128] [0.8, 1.0, 1.2]
MIMIC
TinyLLaMA IB
B
[32, 64, 128] [0.8, 1.0, 1.2]
Yelp
TinyLLaMA IB
Table 9: Hyperparameters for Amin al. [13]'s method.
mentioned in $5, preliminary experimentation showed that the SVT step in [13]'s method selected private tokens Rs 25% the time. We select a value of pew =100 for datasets (where T Tyro is the maximum number of private tokens allowed) and maintain the total tokens generated at the same levels as the settings for INVISIBLEINK described Tab. As seen in the plots in Fig. 4, this does not affect the average generation length of synthetic samples generated by this method. As seen in $5, for number of settings, this method fails to yield any synthetic text (INF or infeasible in Tab. 2). All results available reported tuned the sampling temperature
AdaPMixED [19]. AdaPMixED [19] is a next-token prediction algorithm adapted to generate synthetic text sequences sampling one token at time under data-dependent privacy guarantees. The

---

approach described in [19] uses models fine-tuned (without privacy) on partitions of the private references dataset. We focus on private inference methods and adapt AdaPMixED fashion similar to [13], using the sensitive references as context for the synthetic text generation. Private inference can be used on pretrained models prompted with private data (our setting) or non-DP fine-tuned models. Both are conceptually identical as they privatize a set of non-private predictions.
We use custom implementation of the method, modifying it to use the replace-by adjaceney; see $B.3 & $E.6. We note that AdaPMixED has significant (non-GPU) computational overhead compared to other methods due repeated calculation of optimal mixing parameters; see [19, Alg 1, Line 11]. We implement this using the brentq optimizer from the scipy Python package. For generations, we use the same values of T (maximum allowed tokens per generation) discussed previously; see Tab. 1. We fix some hyperparameters across settings: sampling temperature at 7 = 1, noise multiplier a 0.01 and mixing parameter for noisy screening À = 10-1; for all other hyperparameters, we use the recommended default values for the PubMed dataset in [19, Tab 4].
AugPE [41]. AugPE is private text generation algorithm that relies on iterative LLM-basel paraphrasing and construction of privatized (noisy) nearest neighbour histograms at every step to generate private text. See $E.1 for a full discussion on all the generation settings for this method.
D.6
Confidence Intervals
We report the mean of the evaluation metrics across all generated text samples for given generation setting, wherever applicable. In addition, we also report the (1 - a) x 100% = 99% confidence intervals calculated using the standard error (standard deviation of the mean) follows,
CI = H + Za/2 mm
where 7 is the sample mean, s is the sample standard deviation and m is the number of samples. Here, Za/2 is the (1 - a/2) percentile of the standard normal distribution. These are Wald confidence intervals, given under the assumption that error is unbiased and normally distributed. For 99% confidence interval, we have Za/2 = 2.576 and for a 95% confidence interval, we have Za/2 = 1.96.
D.7 Computational Resources
Software. We used Python 3.1..2, PyTorch 2.6 and HuggingFace Transformers 4.50.1.
Hardware. All experiments requiring a GPU (LLM inferences, APPL calculation, MedNER count calculation etc.) were conducted on one of two machines: (a) with 4 NVIDIA RTX L40S GPUs (with 48G memory each), or (b) with 4 NVIDIA H100 GPUs (with 80GB memory each). Each task used only one GPU at a time. All wall-clock time measurements, if any, are performed using the L.00S GPUs The non-GPU jobs, such as computing MAUVE, were run on a machine with 240 AMD EPYC 9554 CPUs (clock speed: 3.10 GHz) with 64 virtual cores each and total memory of 845GB.
Evaluation Time. The approximate wall clock runtimes for synthetic text generation using various methods are given below. The runtime varies with the size of the model and batch size used, in particular with the maximum number of parallel LLM inferences that may be run the GPU. For our experiments using TinyLLLMM, maximum of min B + 1, 16) inferences were run in parallel on 1 GPU. The runtimes also scale (approximately) linearly with the length of individual generated samples and the number of samples generated. All numbers reported below are for 1000 generations of 500 token synthetic samples using MIMIC as the reference dataset.
INVISIBLEINK: hours for B 15
Amin et al. [13]: R 12 hours for B = 127
AdaPMixED [19]: 12 hours for B 127 and
AugPE [41]: 2 18 hours for 7 variations per iteration and 10 iterations
The runtimes for AdaPMixED [19], in particular, have a very high variance with both B and E as a higher privacy budget corresponds to longer generations and higher runtimes. For = 127 and & > 5. the runtime exceeds 24 hours for 1000 generations, denoted by TLE in our experimental results. The runtimes for AugPE [41] scale (approximately) linearly with both the number of iterations and the number of variations generated per iteration.
30

---

E Additional Experimental Results
In this section, we present the following additional results:
Additional results comparing INVISIBLEINK and AugPE [41] on the MIMIC dataset.
Additional experiments the downstream utility of data generated from the Yelp dataset.
Additional statistics for the selection of tokens from the expanded vocabulary described by the Top-k+ step in INVISIBLEINK.
Additional results for synthetic generations for the MIMIC dataset using LLaMA3 8B.
Additional experiments designed to highlight the effect of sampling temperature т, clipping norm C' and top-k sampling parameter on the quality of generation.
Experiments comparing the quality of private text generation for AdaPMixED with the replace-by-nul adjacency and add-or-remove notions of adjacency.
E.1
Comparison with AugPE
Fig. gives additional experimental results comparing the utility vs computational cost of INVIS- IBLEINK and AugPE for various privacy budgets. The trends agree with those in Fig. 5; see $5.
Invisiblelnk AugPE Comparison (E 1)
MAUVE Scores MIMIC
CenPPL MIMIC
Gen. Lengths (*) for MIMIC
MedNER Counts (1) for MIMIC
MAUVE
Length
Counts
0.65
1.53
101
Wall-Clock Runtime (hrs)
Wall-Clock Runtime (hvs)
Calk Runtime (hrs)
Wall-Clock Runtime (hrs)
Invisiblelnk AugPE Comparison (s -5 3)
MAUVE Scores MIMIC
GenPPL for MIMIC
Gen. Longths (?) for MIMIC
McdNER Counts (1) for MIMIC
MAUVE
0.53
Length
Counts
2.45
0.03
Clock Runtime (hrs)
Wall Clock Runtime (hrs) Invisiblelnk AugPE Comparison (s 5)
Clock Runtime (hrs)
Wall Clock Runtime (hrs)
MAUVE Scores (t) for MIMIC
GenPPL (1) for MIMIC
Gen. Lengths (1) for MIMIC
MedNNER Counts (1) for MIMIC
MAUVE
8.3
Length
Counts
8.4
8.43
Wall-Clock Runtime (hrs)
Wall-Clck Runtime (hrs)
Wall-Clock Runtime (hrs)
Wall-Clock Runtime (hrs)
Invisible 100)
AugPE
Figure 8: Utility Compute plots (avg. over 3 runs) for INVISIBLEINK and AugPE for varying privacy budgets e for 1000 synthetic texts generated for MIMIC dataset. We compare utility using a variety of metries INVISIBLEINK outperforms AugPE across all settings and evaluation metrics. Wall-clock run time is used to measure the computational cost. We report results for B + 1 = 4, 8, 16, 32 next-token inference calls per generated token and TAugPE 1,3,5 5 for INVISIBLEINK and AugPE, respectively.
The number of variations of the candidate synthetic texts generated every iteration of AugPE (the parameter I. in [41, Alg 1]) is fixed to be 7. We also limit the total number of sensitive references the algorithm sees to 7 x n (where n is the total number of synthetic texts generated). The total number of full-sequence LLM generations per synthetic text is given by 8 TAugPE, where T'ugPE is the
31

---

Prompt Type
Prompt Text
System Prompt
Please act sentence generator for the medical domain. Generated sentences should mimic the style of medical discharge summaries, using variety of sentence structures.
Generation Prompt
Using variety sentence structures, write a patient discharge summary. Begin the output with the phrase: "Discharge Instructions."
Variation Prompt
Please rephrase the following sentences "iinsett candidate synthetic text>" as a patient discharge summary: "<insert rephrase style>"
Begin the output with the phrase: "Discharge Instructions."
Table 10: Random sample generation and Variation prompts for MIMIC adapted in the style of AugPE; The candidate synthetic generations at the current iteration are inserted in the space denoted by "< candidate synthetic text>" and information about the stylc in which the LLM should rephrase the text is inserted in the space denoted by "<insert rephrase style>".
number of iterations, and varies from 8 80. In contrast, we disad our model by limiting the number of effective full-sequence LLM generations to B + 1, ic, 4 32. Further, we use the official implementation of AugPE released by Xie et al. [41] and adapt it for generating synthetic samples from MIMIC with minimal changes. In particular, we preserve the same style of random sample generation and text variation prompts used for other datasets; see Tab. 10.
E.2 Yelp Downstream Utility Experiments
We evaluate the synthetic data generated from the Yelp dataset on a downstream classification task. We finetune a RoBERTa model [94] for sequence classification on a dataset of 500 generated synthetic texts from the Yelp dataset into 50 classes, obtained as all combinations of 5 review score labels and 10 business category labels. We note that since the synthetic data generation is conditioned on these classes, the class label information is also available in the synthetic data.
We evaluate the resulting classifier on the Yelp test set. Tab. 11 reports the 50-class top-1 and top-5 accuracy (resp. columns "Accuracy" and "Top-5 Acc."), 10-class accuracy over categories (column "Cat. Ace."), 5-class accuracy over score labels (column "Score Acc."), and the L1 distance between the predicted and true numeric scores (column "Score L, "). We finetune the RoBERTa model [94] for 15 epochs with an AdamW optimizer [95] with a batch size of 20, a learning rate of 2 x 10-5, weight decay of 0.01 and 10% warmup steps.
The results presented in Tab. 11 compare the downstream utility metries for text generated by various methods with a fixed privacy budget of E = 10. INVISIBLEINE outperforms all baseline methods by large margin at a significantly smaller computation cost, even when measured in terms of this downstream task utility.
Method
Batch Size B
Accuracy (1)
Top-5 Acc. (1)
Cat. Acc. (1)
Score Acc. (t)
Score L; (L)
INVISIBLEINK
32.98
72.16
64,90
52.2
0.652
Amin et al. [13]
127
29.44
64.56
60.18
46.64
0.748
AdaPMixED [19]
31
7.44
34.72
56.82
15.44
1.858
Table 11: Downstream utility of synthetic text Multiple evaluation metrics task for sequence classification task using RoBERTa [94] model finetuned synthetic sequences generated from the Yelp dataset with privacy budget e 10. INVISIBLEINK outperforms the baselines significantly.
We note that measuring utility in downstream tasks not a reliable indicator of overall text quality, coherence, or distributional similarity to the original dataset. Several prior works on DP text generation [13, 19, 47, 48] rely heavily on such metrics evaluate generated text. However, it is possible for poor-quality synthetic text to "hack" these metrics, especially in the case of sequence classification by relying on keywords related the target category. This can be observed in the case of AdaPMixED, where sequences with an average length of < 30 tokens (see Fig. 4) perform significantly better than random: 7% (vs. 2% random) for overall classification accuracy, 56%
Available https: httpp:::////tt////g//e/ www. wwwp//AIasccuuuuuuaaaaa
32

---

(vs. 10% at random) for category prediction accuracy, and = 1.8 (vs. 2.0 at random) for average L1 distance (lower is better) between predicted and true scores. We also note that in the case of open-ended text generation, such notions of downstream utility are not directly applicable. Thus, we adopt a combination of metrics to evaluate DP synthetic text.
E.3 Top-k Selection Statistics
Some additional statisties of selection from the expanded vocabulary described by the Top-k+ step of INVISIBLEINK are presented Tab. 12. In particular, we show the following:
: Effective-k, which is the size of the vocabulary Vi*
ok: standard deviation of kett = V
#toks: number of tokens generated from the expanded vocabulary V Va per generation
For each metric, we report the average over all generations or generated tokens for a setting. As the privacy budget increases, the clipping norm C' also increases. We observe that larger expansions of the top-k threshold (2C/B) B), lead to larger effective-k (ker = IV \) of Top-k+ sampling. Further, as reported in $5, we also observe that the number of tokens sampled from the expanded set very low (typically < 10), supporting the claim that V is a very tight superset of V.. Further, the standard deviation of keff scales roughly with kottt - k, i.c., the square root of the size of the expansion.
The number of sampled tokens also decreases as k increases. Despite larger increase in effective k due to the expansion of the top-k vocabulary, the probability selection of tokens decreases sharply with rank since the increased expansion is offset by lower probabilities of selection.
= 10
k = 50
À 100
k 500
C
Kar
#toks
#toks
Ran
#toks
Ran
#toks
0.08
10.17
6.14
50.69
0.97
1.50
101.07
1.28
0.91
506.43
3.95
0.73
3.0
0.23
10.52
0.76
7.71
52.57
1.77
2.62
104.98
2.54
2.04
524.04
7.11
1.81
5.0
0.36
10.52
0.77
7.77
53.09
2.00
2.89
106 80
3.02
2.51
534.82
9.31
2.60
10.0
0.66
11.25
1.25
11.15
56.57
3.04
5.04
113.35
4.55
4.45
568.28
16.33
4.77
Table 12: Statistics for Top-k+ sampling step of INVISIBLEINK for 1000 synthetic text samples generated for
the MIMIC dataset using TinyLLaMA 1B model, batch size of B = 7, and sampling temperature 1.2. We report the size of Vx"" (ker), the standard deviation in kea (a))), and number of tokens sampled from the expanded vocabulary V2* Vi (#toks); all metrics reported averaged over all generations or generated tokens.
E.4 Scaling INVISIBLEINK to Larger Models: Results on LLaMA3 8B
The utility scores (MAUVE) for 1000 synthetic texts generated using a LLaMA3 8B model are presented in Tab. 13. The results agree qualitatively with trends observed for smaller models: intermediate values of k 100 to 1000 consistently perform better than very small or very large
e
k=10
k=50
k=100
k=500
k ==1000
k=5000
1.0
58.90.4
61.605
62.9,.9
62.406
63.0po
61.806
3.0
59.20.
60.0a.
60.5
62.1es
62.2as
62.2n.5
5.0
59.9ns
60.7as
62.2
62.8ea
63.0g3
62.603
10.0
59.4n.4
61.3ox
62.9p
63.6n.
63.0no
63.2
Table 13: MAUVE (%) scores, reported with mean and 95% confidence intervals (see $D.6) over 3 runs, for 1000 synthetic text generations using LLaMA3 8B for the MIMIC dataset with varying and & for INVISIBLEINK with T 1.2 and
The best scores for every privacy budget are highlighted.
We note that generation from the LLaMA3 8B at such small batch sizes (B = 7) is completely infeasible for the other baselines we consider, such as AdaPMixED [19] and Amin et al. [13]'s method. As we use larger (in terms of number of parameters) LLMs, the computational cost in terms of both GPU memory and computational time increases sharply. Using batch sizes > 50, as proposed by the baselines [13, 19] unreasonable with large models. This highlights the scalability of INVISIBLEINK larger models, and by extension, its suitability for high-quality text generation.
33

---

However, we note that the overall MAUVE scores of the generated texts falls compared to generations from smaller models like TmyLLaMA and LLaMA3.2 IB. We attribute this the strong alignment of the L. 8B model against generating (fake) medical records or divulging patient data. We further note that despite our detailed prompts (see Tab. 4), the output private text generated by the model contains text other than the synthetic text to be generated, usually in the form of disclaimers of the form: "Here is fake patient discharge summary". Sanitizing the output private text, post- -enerrtttn, by removing this disclaimer leads to ~ 1 - 2% increase in MAUVE scores across all settings.
While our primary experiments (reported in Fig. 4 and Tab. 2) show that INVISIBLEINK performs well, even when generating tut-of-domiin text, strong alignment of LLMs impacts generation ad adversely. We leave full investigation of this phenomenon to future work.
E.5 Ablation Studies: Effect of Temperature, Clip Norm, and Top-k parameter
INVISIBLEINK has the following key hyperparameters: the batch size B (which is determined by the compute budget), temperature T. clip norm C, and top-k parameter. $5 shows the effect of varying the batch size B (Fig. 4) the top-k parameter (Fig. 6).
Ablation: Effect Sampling Temperature (r)
MAUVE Scores (1)
GenPPL (1)
Gon. Lengthi
MecINER Counts
8.54
MAUVE
APPP
Lenghh
Counts
0.45
1.64
Batch Size (B)
Batch Size (B)
Batch Size (B)
Batch Size (B)
Figure 9: Variation of utility (measured using variety of metrics) with sampling temperature. for the full- vocabulary variant of INVISIBLEINK (k- [VD. reported for 1000 synthetic generations. averaged over runs, for the MIMIC datasct using TimyL.LaMA 1B model. Temperature is varied from 0.8 to 1.1 for fixed privacy budget æ = 5. We observe that selecting temperature of r R 1.0 - 1.1 consistently gives better performance. When coupled with Top-k+ sampling for k ss 50 100 (chosen based on empirical observations in Fig. 2), observe that the best performance is obtained for 1.1. We report these results in the main paper; Fig. 4.
As per the heuristics for hyperparameter selection proposed in $5, we tune across various temperatures and calculate the clip norm C² for the fixed privacy budget and sampling temperature т. The effects of varying the temperature and clip norm are thus coupled. We first report the performance of INVISIBLEINK for various temperatures and top-k parameters. We observe from Fig. 9 & Fig. 10 that the optimal choice of sampling temperature and top-k k parameter is T = 1.1 and k = 100.
Ablation: Effect Sampling Temperature (r)
1.72
MAUVE
4.53
MAUNE
642
1030
100
1030
196
Top-k parameter
Top-k A parameter
Top- parameter
Top-k parameter
1.
1.2
Figure 10: Variation of utility (measured using MAUVE scores) with sampling temperature and top-k parameter, reported for 1000 synthetic generations, over one run, for the MIMIC datasct using TinyLLaMA 1B model. Temperature is varied from 1.0 to 1.2 for various privacy budgets. We observe that selecting temperature of 1.1 consistently gives the best performance when coupled with Top-k sampling for k s 50 100 (chosen based on empirical observations in Fig. 2). We report these results the main paper; in Fig.
We now decouple the effect of clipping by removing the constraint on privacy budget and instead varying C freely for a given fixed temperature (see Fig. 11). We also report the variation of calculated clip norm for INVISIBLEINK and Amin et al. [13]'s method with batch size B for various privacy
34

---

budgets. As discussed in Fig. 3, the clipping norms required for high-utility generation using INVISIBLEINK can be achieved with much lower batch sizes as compared Amin et al. [13].
Effect Clipping Norm (C)
Invisible lnk
Amin al. (2024)
MAUVE Scores (1) MIMIC
MedNER Counts (1) for MIMIC
12
Clipping Norm
Clipping Norm
MNDVE
Counts
3x1
1P
Batch Size
Batch Size
(C)
(C)
Indsilioslkk
( (V]
Figure 11: Effect of clipping norm. Left two: Variation of calculated C' for INVISIBLEINK and Amin et al. [13]'s method with hatch size B for various privacy budgets. The latter needs much larger batch sizes give comparable clip norms for a given privacy budget. Right two: Variation of utility with C' 1000 synthetic generations for the MIMIC dataset using a TinyLLaMA 1B model using INVISIBLEINK (k [V]. Temperature (r = 1.2) and batch size (B 7) are fixed while we vary the clip norm. Each setting of the clip norm implies DP parameter given by Theorem 2. In particular, it varies from 1.3 for C' = 0.1 17.6 for C = 1.0.
E.6 Comparison of Adjacency Notions for AdaPMixED
As discussed in $B.3, we use an implementation of AdaPMixED that employs the eeplace-b--in notion of adjacency, in INVISIBLEINK, in the main paper instead of the add-or-remove notion of adjacency used by Flemings et al. [19] as it allows for an upples-to-apple comparison.
Add-or-remove adjacency
Ceplacc-by-nnit adjacency
B 8
B = 32
B = 128
B 8
B 32
B = 128
1.0
58.68
58.7
58.51
14
57.64
59.51
3.0
58.29
58.81
61.50
58.30
57.97
58.80
5.0
60.24
58.74
TLE
58.20
59.32
TLE
10.0
60.23
59.23
TLE
59.18
59.61
TLE
Table 14: MAUVE (%) for 1000 synthetic generations (over one run only) for the MIMIC dataset
using TinyLLaMA different privacy budgets (e) and batch sizes (B), comparing two adjacency notions: Add-or-remove and Replace-by-ne for AdaPMixED. TLE denotes runs where a wall-clock time limit of 24 his was exceeded. Top-performing configurations per tend to vary with adjacency notion and batch size; highlighting the sensitivity of MAUVE scores both.
To do so, we modify the data-dependent privacy accounting step (defined in [19, Eqn. 3)), which accounts for the maximum symmetric a-Rényi Divergence between probability distributions corre- sponding to the reference set and all its possible neighbours under addd-rr-remove adjacency.
We modify this step to instead account for the maximum a- Ré-ééyi Divergence between the probability distribution corresponding to the current reference set and all possible neighbours using the replace- by-null adjacency notion. In contrast to the add-or-ree or-remove notion, where removing a particular reference zeroed out its contributing probabilities [19, Alg 1, Line 15], our modified algorithm, replacing particular reference by "null" (empty string 0: see Theorem 5) means that the contributing probabilities default to that of the public distribution. Mathematically, we modify [19, Alg 1, Line 15] to be (borrowing all notation from [19]):
1 N
P-((x)=
Σ (x) ) + PPub (2x) /+1
We note that this lends an advantage to the replace-by-nal. implementation of AdaPMixED, since the per-token privacy accounted for must be slightly lesser. However, the quantitative results, presented Tab. 14, fail to reflect this meaningfully, since the generated sequences are very small. Regardless, INVISIBLEINK outperforms AdaPMixED significantly irrespective of the notion of adjacency used.
35

---

F Limitations, Discussion, and Broader Impact
INVISIBLEINK casts next-token sampling as an instance of the exponential mechanism over LLM logits and introduces two key innovations. First, it reduces privacy cost by isolating and clipping only the sensitive portion of the logits, measured relative to public logits. Second, improves utility by sampling from a tight superset of the top-k private tokens. Empirical results demonstrate an 8x (or more) reduction in compute cost compared state-of-the-art baselines, while preserving utility, across privacy levels. Notably, INVISIBLEINK enables private long-form generation at less than 4-8x the cost of non-private decoding, offering a practical and efficient solution for privacy-preserving language generation. While INVISIBLEINK significantly reduces the computational complexity of generating DP text, it still has some limitations that we now discuss.
Limitations. The trust model of INVISIBLEING requires specific assumptions that could potentially be restrictive. A direct implementation of INVISIBLEINK requires trusted central aggregator who has access to the raw sensitive references, whitebox access to the model weights (to query the next-token logits), and the necessary computational resources to run INVISIBLEINK, Relaxing these requirements is interesting avenue for future work.
Second, INVISIBLEIN provably protects against privacy leakage through inference, but not in the training fine-tuning stage. Leakage could still be possible through data contamination or backdoor adversarial attacks. Furthermore, even in the case of inference, we tackle example-level DP only. However, user-level privacy leakage is also possible [e.g. 96], and extending INVISTBLEINK to user-level DP is an interesting direction.
Finally, while INVISIBLEINK drastically improves the computational cost of private text generation, the 8x overhead over non-private generation could still be restrictive with large frontier models under extremely tight privacy budgets. Pushing the envelope of the privacy-uility-comuu tradeoff's of text generation is fruitful avenue for future research.
Broader Impact. The development of computationally efficient DP text generation can allow safe deployment of large language models (LLMs) in privacy-sensitive domains such healthcare, law, and finance. By addressing the steep privacy-utility-ee saracy-utlity-compuut compute tradeoffs that currently hinder practical use, our work could help unlock high-impact applications that require both strong privacy guarantees and high-quality long-form generation.
In doing this research contributes sustaining public trust in Al systems. As LLMs become increasingly integrated into everyday decision- making processes, ensuring that user data is handled with dignity and protected by rigorous guarantees is ethically and, in sensitive domains like healthcare, legally warranted. We view computationally efficient and provably sewacy-preservigg techniques as key to building ethical and trustworthy AI.
However, the existence of formal privacy guarantees may lead overconfidence or misuse, particu- larly if system integrators overlook practical limitations such as implementation errors, misconfigured parameters, or unrealistic threat models [e.g.. 82, 83). Differential privacy is powerful but narrow tool: it provides provable anonymization but is only one component in an end-to-end system. The prac- tical use of such a system must be considered in a holistic manner, along with clear communication of failure modes.
G Software Package
We illustrate the use of the accompanying software package, available on GitHub, and installable via pip. 16 as pip install invink.
import invink
from datasets import dataset
Load the TAB dataset for this example.
data datasett ("nattadjaga/text www.mmiataaoottiiiiii.on..o benchmark train")
Shtppe///tthal..co//rrrrsttttt/t "nttps://pypt.org///e/ org/proojet//nninn//
36

---

Reference texts given as list of strings. ref_txts "
10 Use smaller models for lower memory footprint.
11 model "google/gemma -amma-3-4b-14
Description should contain privacy-eensitive information.
14
dataset_deac "The dataset comprises English-langue court cases from the European Court of Human Righta (ECHR)
15
Generate text samples with (10, 1e-5)
17 output invink, generate (ref_ txts, model, num=10, epsilon=10,
18 batch_size=8, max_toke=500, dateet_
19
list of private synthetic text strings print (output. texts)
Listing 1: Generate private synthetic text using INVISIBLEINK
The demo code in Listing reads reference texts from the TAB dataset and generates num=10 synthetic texts, each at 500 tokens long, with parameter patch_size corresponds to B + in the paper, i.e., the total number of LLM inferences per generated token. Thus, (batch_size-11 1) num= (8 1) 10 70 private references are used to generate 10 synthetic texts in the above example.
10, 8 10 10-5)-DP guarantee. The
H
Example Generations
See Tab. 15 for some example generations from INVISIBLEINK.
37

---

Dataset
Examples of Generated Synthetic Text
"We chose cozy restaurant that delivered impeceable service, excellent fare, and even better music our table." " (ReviewStars: 4.8 out of 5.0) Naturally, walked to find spacious and serene lobby. Our server welcoming. and she immediately recommended seasonal cocktail and the restaurant's signature dish, Chicken Cacsar. The servers were friendly, knowledgeable, and efficient which contributed gready our experience. Tucking into each other's orders, we feasted our eyes on sophisticated appetizers like Caprese, Grilled Salmon, and Grilled Caesar Wings, accompanied by the juiciest and most lip-smacking chicken you'll 'Il ever taste, alongside delicate glass of Pinot Noir to top it off. The food arrived quickly without forgetting the music
Yelp
"Although the staff may not able to befriend every customer, their attentiveness and positive attitude really go a long way. Our recent visit to a new coffee shop led by a chatbot could have gone further in helping patrons' preferences, with many potential avenues to cater the atmosphere. From a personal observation. however, believe that udding more personalities the virtual assistants could cater to a wider-range of needs while engaging customers. Nevertheless, the chathot is smart and proficient in its tasks, and we enjoyed getting tips about the local coffee culture from their knowledgeable baristas. Although we were a bit inconveniently served at our preferred location for a quick lunchtime fix, we were glad to taste some delicious homemade sushi on the go. Overall, our overall experience was positive with bit more effort and personalization in terms of addressing specific preferences could lead to repeat vis
The case originated in an Application for Judicial Review filed by Ms. Smith, petitioner(s), against the Bulgarian State from January 8th of the year 2019. The Respondent for this jurisdictional issue the Ministry of the Interior of the Bulgarian Republic and the Bulgarian National Antiterrorism Bureau. The alleged event occurred at the intersection of public place known as Sidi Boutha Crescent Vezhub Khayri Crescent in the city of Sofia. Bulgaria that caused contributed significantly and directly to plaintiff Smith's 's physical injury causing death pursuant to Section 4, Article 3 of the Bulgarian Medical Registration Act.
PROCEDŽURE:
TAB
The procedural steps involved in the application included the preparing of the written petition as well as its formality submitted to the Court for review.
Upon review of the documents, the Registrar of the Court sent the petition to the Bulgarian Ministry of the Interior as legal source and required from the said organization to verify and respond in court about the availability of sufficient grounds for such judicial review against the Bulgarian state.
Following the review process, the request for verification made by plaintiff' Smith's 's attorney was submitted before the Ministry of the Interior of the Bulgarian Republic.
The Bulgarian Minister of the Interior received the request per the requirement and made a decision within one month from the submission date based on the relevant document provisions as provided by law.
After this, the Ministry communicated to the plaintiff regarding the reply received from the National Antiterrorism Bureau, and the said communication stated that the respondent is satisfied with having received the reply and that the Bulgarian state is willing to conduct judicial investigation of the event from the incident that caused or contributed significantly to the death of the petitioning defendant Smith.
Respectfully, as per the international human rights instrument cited in the previous reference to the jurisdiction as mentioned in the jurisdictional challenge brought in favor of Ms. Smith, all facts and circumstances of the criminal matter that led to the loss of a life of Bul Bulgarian citizen constitutes a violation of her right to physical integrity protected by Article 2 (Prohibition of T
Table 15: Randomly chosen examples of private text generated with 10 from the Yelp and TAB datasets using the TiMA IB model, sampling temperature T = 1.2, & = 50, and batch sizes B = 31 and B = 7 respectively; INVISIBLEINK provides high-quality text. We do not provide examples of synthetic generations for the MIMIC dataset to comply with its license. Amin et al. [13]'s method is infeasible for text generation at the same batch sizes.
38

---

I NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made the abstract and introduction, as well as all contributions listed supported by experimental evidence and theoretical proofs. The main paper gives a summary and the appendices give the full technical details including proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification: detailed discussion of the limitations and scope of our work given in the appendix $F.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
39

---

Answer: [Yes]
Justification: All theoretical claims, theorems, properties etc. made in our work are proved in detail in the appendix: See SC.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All details regarding the experimental settings, including models, metries, prompts etc. and any other information necessary to ensure full reproducibility is covered between the relevant sections in the main paper and the appendix; See $D and
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
40

---

We report the mean and standard emror for applicable metrics; See $D for 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
All code and scripts required to reproduce the results in our work will be available https: //ggth/bbbb.. wwt.com/cccce/e datasets we use are public (MIMIC dataset is credentialed access only, and researchers can apply for access to it).
Justification:
Ee.peeeneee.r.eeettte.... All
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Seaiii/guidds//ooeeeeeee ceaibbmisssooPooi oeeiionooliyy olicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cccppblic/guiceee /eeegguuddde/eoeuubnnnn ss iesionPolll onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details regarding the experimental settings, including models, metrics, prompts etc. and any other information necessary to ensure full reproducibility is covered between the relevant sections in the main paper and the appendix; See $D and $E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
details.
Guidelines:
The answer NA means that the paper does not include experiments.
41

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Details about computational resources used are discussed in the appendix: See $D.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : /tt./ieuuripp/ee hwablii//Echicsuiieelenneee
Answer: [Yes]
Justification:
We adhere strictly to the NeurlPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiciio))
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
A discussion the broader impact our work is present in the appendix. See
SF.
42

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
We do not release any sensitive data or models which pose risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All licenses for use of data and models have been respected and due acknowl- edgement has been made to every asset used in our work.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
43

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdaatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets (data, models etc.)
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our use of LLMs is limited to grammar, spellchecks and minor writing edits only.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: htt////eurrppppepe for what should or should not be described.
45


Reviews:
[{"review_id": "5E74zlYEqR", "reviewer": "Reviewer_9N2Q", "summary": "There is a strong desire to understand how to add sensitive data to LLM context for the purposes of text generation without having the model leak private information. Differential privacy is a formal privacy guarantee that can ensure that sensitive data are not leaked, but designing DP algorithms for LLM text generation with private context is technically challenging and can be computationally expensive. This work develops several techniques for improving white-box private LLM text generation and combines these techniques into the proposed method InvisibleInk. These techniques include DClip for bounding the contribution of each sensitive text sample tightly and top-k+ for clipping irrelevant tokens from the sampling distribution. Both these methods use public logits (generated from the LLM without any private context) without utilizing the sparse vector technique (SVT), this allows for InvisibleInk to decay gracefully when provided with a small privacy budget as opposed to prior work that can fail catastrophically in the high-privacy regime. The authors demonstrate experimentally that InvisibleInk outperforms prior work both across several metrics and datasets for text generation.", "questions": "How would you adapt InvisibleInk to a RAG question answering setting where you need to balance the computation cost and effective temperature tau with the added consideration of retrieving enough information to answer the questions?\n\nYou utilize the public logits heavily, how would you handle a setting where the public logits are very different from the private logits (perhaps a very specialized setting where the model needs important context to generate high-quality responses)? Would this change the best value of the clipping parameter?", "limitations": "The authors discuss the limitations of their methods in the supplementary material. I do not have additional limitations to add.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nThe work clearly justifies their method from a privacy perspective and also from an LLM decoding perspective. This will allow readers from either background to understand the contributions and why InvisibleInk is effective\n\nThe work intelligently incorporates the public logits into DClip and top-k+ to get performance gains from it without using the SVT, which is often unreliable in practice.\n\nInvisibleInk is a user-friendly and practical approach because of the graceful degradation w.r.t. the privacy budget and the useful heuristics for selecting hyperparameters. Hyperparameter tuning under DP is difficult (so many people tune hyperparameters non-privately) but important; the fact that this method comes with practical recommendations for how to set hyperparameters based on the generation length and privacy budget is very useful.\n\nThe experiments show general results about the quality of InvisibleInk and they also investigate DClip and top-k+ to demonstrate that these techniques are doing what the authors claim.\n\nWeaknesses:\n\nThe authors discuss the batch size B as a quantity that should always be minimized in order to reduce computational cost and increase the number of synthetic records you can generate. However, if you are generating text to answer questions in a RAG system you may need to use more records to gather sufficient context for the generated answer. The introduction mentions this kind of setting but the methods and experiments don’t engage with this setting.", "was_revised": true, "final_justification": "The reviewers gave helpful context in their responses to my review. This helped give me confidence that my original score of 5 was and still is appropriate. While the paper is a meaningful contribution to the private text generation literature, I do not believe it meet the threshold of being technically flawless and groundbreaking for a 6.", "rebuttal": "Thank you for the thorough review and the thought-provoking questions! We respond to each point in detail below.\n\n> ... how would you handle a setting where the public logits are very different from the private logits ...\n\nIn a setting where the public logits are very different from private logits due to very specialized queries, the clipping parameter would have to be increased slightly to preserve downstream utility and quality of the generated text. This results in a larger privacy budget being used up per token generated. (This is unsurprising, as the public logits are now less informative.) \n\nIn order to account for such settings, we select 2 out-of-distribution datasets (relative to the pretraining distribution): MIMIC and TAB, for our experiments (MIMIC is commonly used for cross-domain transfer experiments, see e.g., Khaled et al. (2025) [1]). Our empirical results clearly show that InvisibleInk retains much of its performance even at very low privacy budgets in these settings. The loss in utility is negligible in this case, demonstrating that InvisibleInk is sufficiently robust to specialized generation contexts. \n\n> ... in a RAG system you may need to use more records to gather sufficient context ...\n\nThis is a great point. It is true that in some practically relevant cases, the batch size $B$ is not necessarily a quantity to be minimized. However, for the previous state-of-the-art methods, the values of $B$ required to generate high-quality text were prohibitively large (ranging from 200-1000). This is in stark contrast to RAG methods that usually retrieve many fewer relevant documents (typically 3-10). In our work, we remove this restriction on large $B$ and allow private text generation to be done in a compute-friendly way for the first time.\n\nRAG is one such potential application of InvisibleInk. In our synthetic text generation setting, batches of sensitive references are sampled (from a partition) from the dataset, agnostic to the query. For RAG, one would have to privatize the selection of the batch of sensitive references, and as the reviewer correctly points out, possibly use more records for sufficient context. The former is a non-trivial and nuanced extension of our work; for the latter, it may suffice to set B to be a reasonable upper bound on the number of references.\n\nHowever, InvisibleInk is the first such scalable private text generation framework that can act as a starting point for future research on private RAG systems. \n\n> How would you adapt InvisibleInk to a RAG question answering setting ...\n\nHistorically, the core task of RAG has been *short-form* question answering. For instance,private RAG methods, such as Koga et al. (2024) [2], focus on *extremely short-form* question answering with output generally limited to 20-30 tokens for a privacy budget of $\\varepsilon=10$. InvisibleInk is designed keeping in mind the increasing need for private RAG systems where the output is long-form text (e.g. in recent AI-based search engines such as Perplexity or Google search’s AI-mode). \n\nOur preliminary experiments and ablation studies show that the quality of generation is highly-sensitive to the effective temperature ($\\tau$). As previously discussed, RAG places additional constraints on batching as it is no longer agnostic to the query. We hypothesize that the clipping parameter will play an important role in balancing privacy and utility. We conjecture that the improved clipping function, DClip, will thus be crucial for future work in this direction. However, careful experimental evaluation is necessary to understand the nuances of private RAG fully, and is beyond the scope of this work. \n\n[1] Khaled, et al. \"Leveraging MIMIC Datasets for Better Digital Health: A Review on Open Problems, Progress Highlights, and Future Promises.\" arXiv preprint arXiv:2506.12808 (2025).\n\n[2] Koga, et al. \"Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy.\" arXiv preprint arXiv:2412.04697 (2024)."}, {"review_id": "JGIxt7BdUT", "reviewer": "Reviewer_8Xcz", "summary": "This paper proposes a method, InvisibleInk, for privately generating synthetic text data. Unlike other recent approaches such as Private Evolution, which only allows the mechanism API access to the language model, this paper considers the white-box setting, where the mechanism has access to the logits over tokens with respect to next token prediction. This work builds of the method proposed in Amin et al. (2024).\n\nThe private component of InvisibleInk uses the exponential mechanism using batch-aggregated logits as the score function with candidate set a superset of the top-k tokens. The score function is the sum of two components: the logits from the language model without using sensitive data as context and the clipped difference between the logits on private data and the public logits. This has the advantage of reducing to the public logits when the privacy budget diminishes to zero. The score function and candidate set are the primary technical contributions.\n\nEmpirically, InvisibleInk yields better quality synthetic data than competitor methods.", "questions": "Additional Comments\n- I suggest moving the AugPE experiments to the main text in the camera ready version.\n- In the related work section, it may be helpful to the reader to give the names of the referenced methods such as Augmented PE rather than just pointing to a reference number. I understand this is difficult with respect to Amin et al. (2024).\n- In Section 3, is $B$ defined before it is used? Why not just say that $B = |\\mathcal{R}|$? The first place I see $B$ formally defined is Line 205.\n- On Line 151, do you mean $B < 50$ instead of $B < O(50)$?\n- Line 158: you don't need the comma.\n- Regarding related work: one way to think about using pretrained models is that they are incorporating public information to augment the private data generation. Several methods for tabular data generation have explored ways to incorporate public data such as prior data releases: PMW-Pub [0], GEM-Pub [1], JAM-PGM [2], Conditional AIM [3].\n\n[0] Liu et al. Leveraging Public Data for Practical Private Query Release (2021)\n\n[1] Liu et al. Iterative Methods for Private Synthetic Data - Unifying Framework and New Methods (2022)\n\n[2] Fuentes et al. Joint Selection: Adaptively Incorporating Public Information for Private Synthetic Data (2024)\n\n[3] Maddock et al. Leveraging Vertical Public-Private Split for Improved Synthetic Data Generation (2025)", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The proposed method is interesting and the primary contributions directly address weaknesses of existing methods, e.g., Amin et al. (2024). \n- The privacy analysis appears correct.\n- The empirical evaluation supports the main claims of the paper.\n- The paper is well-written and readable.\n\nWeaknesses\n- Much of the narrative of the paper is built around the comparison between the proposed method and Amin et al. (2024). AdaPMixED somewhat comes out of nowhere. Perhaps, discussion of AdaPMixED could be better integrated. \n- The discussion of the privacy guarantees of prior work is unclear (Lines 255-260).", "was_revised": true, "final_justification": "This is a strong paper that makes a clear contribution. After the rebuttal, I am keeping my score at an Accept.", "rebuttal": "Thank you for the thorough review and the helpful suggestions and pointers! We respond to each point in detail below.\n\n> ... the discussion of AdaPMixED could be better integrated.\n\nThis is a good point. We would be happy to elaborate and improve the discussion on AdaPMixED in the main paper.\n\n> The discussion of the privacy guarantees of prior work is unclear (Lines 255-260).\n\nIn lines 255-260, we discuss the specifics of the adaptive DP guarantees of prior work like AdaPMixED, and the method proposed by Amin et al. (2024).\n\nSuch DP guarantees can only be computed post-generation. For example, the latter method computes the DP guarantees to scale with the number of private tokens selected during SVT. This cannot be known before generation, making it challenging to tune the hyperparameters without a grid search. We use the following heuristic: for a fixed privacy budget and maximum allowed tokens, we set the number of allowed private tokens to be ~25% of all tokens. This heuristic is motivated by empirical observations: in our early explorations of the method of Amin et al. (2024), we found that their SVT step consistently selected approx. 25% of tokens privately, across privacy budgets.\n\nIn general, adaptive data-dependent DP guarantees can make precise pre-hoc privacy accounting difficult, as it is infeasible to calculate how many tokens are required to use up the full privacy budget. In contrast, InvisibleInk gives standard DP guarantees and allows pre-hoc privacy accounting. It is straightforward to calculate the maximum number of allowed tokens before generation using the privacy budget and relevant hyperparameters of generation.\n\nFor a more detailed discussion on the privacy guarantees of prior work, we refer to Appendix B3 (pp. 25-27).\n\n> In Section 3, B is defined ...\n\nOnce again, we thank the reviewer for pointing this out. We are happy to clarify and formally define B along with its first occurrence in Line 112.\n\n> ... Several methods for tabular data generation have explored ways to incorporate public data such as prior data releases...\n\nWe thank the reviewer for pointing out additional relevant works. \n\nWe note that PMW-Pub, GEM-Pub, and JAM-PGM may be considered analogous to our setting as they use public data to augment private tabular data generation. Further, similar to our experiments on MIMIC (out-of-distribution for pretrained LLMs) and YELP (significant overlap with pretraining data), multiple settings where public data has varying distributional similarity to the private data are studied. Conditional AIM, on the other hand, considers a setting where there exists a vertical split between public and private data; i.e., some attributes (columns) of the dataset are public whereas others are private. This does not have a straightforward analogue in synthetic text generation. A setting where only specific parts (e.g, keywords, proper nouns, etc.) of the reference texts are privacy-sensitive may be an interesting research direction.\n\nWe would be happy to include this discussion in the next revision of our work.\n\t\n> Other minor corrections\n\nWe thank the reviewer for the suggestions. We will incorporate them in the next revision of the paper and shift AugPE experiments to the main paper as well."}, {"review_id": "siDyNN8koJ", "reviewer": "Reviewer_8mTj", "summary": "This paper proposes *InvisibleInk*, a novel framework for differentially private (DP) text generation that targets both high utility and computational efficiency. The core idea is to aggregate token-level logits from private reference data using a new *DClip* mechanism, which clips their differences against a public logit vector. To reduce computational cost, the authors further introduce a *Top-k⁺* pruning technique that limits the sampling space without additional privacy expenditure. The method is analyzed under the zCDP framework, and experiments demonstrate strong performance relative to prior work, with better trade-offs between privacy and utility.", "questions": "See weaknesses.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n1. The paper tackles an practical challenge: how to conduct efficient and private text generation. The proposed method is compatible with autoregressive language models and can be deployed in real-world settings where public references are available.\n2. The modular design of *DClip* and *Top-k⁺* filtering makes the method potentially applicable to a wide range of DP text generation pipelines.\n\n**Weaknesses:**\n1. The assumption of “zero-cost” privacy for public information in DClip is overly idealized. A central innovation of *InvisibleInk* is the construction of aggregated logits via clipping against public logits ($ϕ_{pub}$), which assumes $ϕ_{pub}$ is non-sensitive. However, since $ϕ_{pub}$ is computed on \"*prompt + prefix $x_{<t}$*\", the prompt may still reveal private user intent or context, and therefore the assumption of public safety may not always hold.\n2. The privacy composition analysis assumes each token-generation step is independent and uses standard composition under zCDP. However, text generation is inherently *contextual and autoregressive*, meaning that each token depends on previously generated tokens. This violates the independence assumption, especially for long-form generation, and could lead to an underestimation of true privacy leakage.\n3. While *InvisibleInk* performs well in white-box settings, most widely deployed LLMs (e.g., GPT-4, Claude, Gemini) are only accessible via black-box APIs. The proposed method cannot be directly applied to such settings, limiting its practicality.\n4. The experimental scope is relatively narrow, using only three datasets (MIMIC-IV, Yelp, and TAB). For stronger empirical support, additional datasets should be included, such as AGNews, TREC, DBPedia, IMDB, WikiMovies, and JSON, to improve the comprehensiveness and credibility of the evaluation.\n5. The paper lacks analysis of generalization and robustness with respect to key hyperparameters (e.g., τ, C, k). Understanding the sensitivity of the method to these parameters is crucial for assessing its stability and deployment readiness.", "was_revised": true, "final_justification": "The rebuttal has resolved most of my concerns. I have updated my score to 4 accordingly.", "rebuttal": "We thank the reviewer for the review and answer their questions below.\n\n> The privacy composition analysis assumes ...\n\nThe adaptive composition property of DP allows us to analyze privacy in settings such as autoregressive text generation, where each token is generated based on the previously generated tokens. Below, we recall the adaptive composition property of zero-concentrated DP and instantiate it more precisely in our setting. For precise reference, see Proposition 19, [1], also recalled in Lemma 13 (pp. 29-30, Appendix C).\n\n**Lemma (Adaptive Composition of zCDP)**: \nIf a mechanism $\\mathcal{A}_1: \\mathcal{X}^* \\rightarrow \\mathcal{Y}_1$ is $\\rho_1$-zCDP and a mechanism $\\mathcal{A}_2: \\mathcal{X}^* \\times \\mathcal{Y}_1 \\rightarrow \\mathcal{Y}_2$ is $\\rho_2$-zCDP, then their (adaptive) composition $\\mathcal{A}: \\mathcal{X}^*\\rightarrow \\mathcal{Y}_2$ defined by $\\mathcal{A}(x) := \\mathcal{A}_2(x, \\mathcal{A}_1(x))$ is $(\\rho_1+\\rho_2)$-zCDP.\n\nFor simplicity, consider the setting of generating two tokens in an autoregressive fashion. (The same can be extended to multiple tokens by induction.) \n\nHere, each $x \\in \\mathcal{X}^*$ denotes a set of sensitive input references. $\\mathcal{Y}_1$ and $\\mathcal{Y}_2$ denote the set of all possible output sequences of length 1 and 2, respectively, ie, $\\mathcal{Y}_1 = V^1$ and $\\mathcal{Y}_2 = V^2$, where $V$ is the model vocabulary. $\\mathcal{A}_1$ denotes the generation of the first token given the input, while $\\mathcal{A}_2$ denotes the generation of the second token given the input prompt and the first token. We see that $\\mathcal{A}$ generates the two-token sequence from the input alone, with an overall $(\\rho_1+\\rho_2)$-zCDP privacy guarantee, where the second token generation is conditioned on the output of the first token.\n\nThus, the dependence of a given token on previously generated tokens is handled gracefully by adaptive composition, and the privacy loss incurred is also correctly accounted for in the analysis. We are happy to elaborate on this in the next revision of the paper. \n\nFinally, we note that other works in the text generation setting also rely on the same adaptive composition property, e.g. [2].\n\n> While InvisibleInk performs well in white-box settings ...\n\nWhile LLMs like Claude, GPT4, and Gemini are hidden behind an API, there is an increasing number of state-of-the-art general-purpose and reasoning open-weights models like DeepSeek, LLaMA3, and Mistral series of models. Such models allow white-box access to next-token logits and are compatible with InvisibleInk.\n\nFurther, white-box access to next-token logits is a commonly studied setting in the literature on DP text generation. For example, see [2, 4, 5, 6]. InvisibleInk operates under the same assumptions but demonstrates an order-of-magnitude improvement in the privacy-utility-compute tradeoff even over previous SoTA *whitebox* methods.\n\n> The experimental scope is relatively narrow ...\n\nWe respectfully disagree with the reviewer’s assessment that the experimental scope is relatively narrow for the following reasons: \n- Three diverse and carefully chosen domains. In particular, the MIMIC (real medical discharge summaries) and TAB (real ECHR case documents) contain real privacy-sensitive data, making the evaluations more realistic than treating non-private internet data (that the models have likely already seen in pretraining) as “private” for the sake of evaluations. We elaborate on this further below. \n- We also respectfully point out that several previous works in this field have demonstrated the efficiency of their approaches on 2-4 datasets, for example: one [9], two [4,7,8], or four [5] datasets.\n- We give an exhaustive comparison to various state-of-the-art baselines from diverse families of algorithms, including a previous exponential mechanism-based generation approach (Amin et al. (2024) [2]), a private next-token prediction approach (AdaPMixED [5]), and a blackbox evolutionary algorithm (AugPE [3]). \n- We perform these evaluations across model scales from 1B to 8B parameters.\n- We conduct detailed analyses on the effect of all important hyperparameters (see also response to your question on this).\n- We also give practical recommendations and heuristics (p.9) on how to select the hyperparameters to use InvisibleInk effectively in new settings with minimal tuning.\n- The unanimous conclusion across all of these experiments is that InvisibleInk enjoys a *consistent 8x improvement* (or better) on the computational cost of generating high-quality synthetic data at the same privacy level.\n\nThus, we argue that our experimental evaluation is, in fact, extensive and comprehensive (in the sense that all relevant scientific questions have been addressed thoroughly in diverse settings). If the reviewer can point out precise scientific questions that need to be addressed with additional benchmarks/experiments, we would be happy to consider them.\n\n**Why not other datasets?** We did consider the various datasets pointed out by the reviewer. Yet, we preferred our datasets for the following reasons.\n\nFirst, we specifically target  *long-form* text generation (e.g. >= 500 tokens) in this paper. This rules out *short-form* question answering and classification datasets such as AGNews, TREC, DBPedia, and WikiMovies as they do not contain sufficiently long real text for generation (<200 tokens on average).\n\nFurther, these datasets, and others such as IMDB, are well-represented in the pretraining data of most LLMs. It is well-established in the literature that a high degree of overlap between the pretraining and target data distributions skews the conclusions of private data analysis [10]. In particular, publicly prompted LLMs can generate high-quality synthetic text for such datasets. Thus, researchers and thought leaders advocate the use of benchmarks that are sufficiently out-of-distribution relative to the training data and preferably contain real privacy-sensitive data, rather than treating non-privacy-sensitive internet data as “private” for experimentation [10].  \n\nAccordingly, we select the MIMIC dataset to be our primary dataset for experiments. It is a dataset of real patient discharge notes containing sensitive medical data, and cannot legally be used for pretraining LLMs as per its data use agreement. Similarly, the TAB dataset contains sensitive identifying information (e.g. demographic traits, spatio-temporal markers, biographical details) from European Court of Human Rights cases. We use the Yelp dataset as a representative dataset that overlaps significantly with the pretraining data (similar to the other datasets proposed by the reviewer).\n\n> ... lacks analysis of generalization and robustness with respect to key hyperparameters …\n\nWe have already performed all these sensitivity and robustness analyses. We refer to the following sections in the main paper and the supplement:\n\n- Effect of temperature $\\tau$: Figure 7 (p. 40, Appendix E) shows the corresponding effect of the temperature on InvisibleInk. These results are similar in spirit to those in Figure 2 of the main paper, which shows the effect of the temperature in the *non-private* setting.  \n\n- Top-k parameter: Figure 5 (p. 9, Section 5) illustrates the effect of the top-k parameter. We observe that intermediate values of k=50 or 100 show the best performance. This is further detailed in Table 11 (p. 39, App. E) and Table 12 (p. 40, App. E) in the supplement.\n\n- Clip norm $C$; Figure 8 (p. 41, Appendix E) explores the effect of the clip norm parameter. \n\nIn short, the dependence on these hyperparameters is intuitive and predictable. We recommend practical heuristics for selecting a good set of hyperparameters with minimal tuning cost in the discussion on “Practical Recommendations” in Page 9 of the main paper. We would be happy to elaborate further on these points if necessary. \n\nWe would also be happy to consider other suggestions on ablations or additional analyses.\n\n> The assumption of “zero-cost” privacy for public information in DClip is overly idealized …\n\nWe consider the setting where only the references used to generate text are privacy-sensitive, while the user prompt is not considered privacy-sensitive (similar to the setting considered in previous papers such as [2]). If the reviewer is concerned about the user instructions in the prompt $p$ leaking privacy, this is an interesting question, but it is not the subject of this work.\n\nNote that the use of the previously generated tokens in the public logits does not incur any additional privacy cost due to the postprocessing property of DP (see e.g., Corollary 21 of [1]). Thus, the overall privacy cost (w.r.t. the sensitive references) of generating a full string of T tokens using InvisibleInk is estimated accurately in our Theorem 1.\n\n[1] Steinke. \"Composition of differential privacy & privacy amplification by subsampling.\" Chapter 3 of the book “Differential Privacy in Artificial Intelligence: From Theory to Practice.”\n\n[2] Amin, et al. \"Private prediction for large-scale synthetic text generation.\" EMNLP 2024.\n\n[3] Xie, et al. \"Differentially Private Synthetic Data via Foundation Model APIs 2: Text.\" ICML 2024.\n\n[4] Flemings et al. \"Differentially private next-token prediction of large language models.\" NAACL-HLT 2024.\n\n[5] Flemings et al.. \"Adaptively private next-token prediction of large language models.\" (2024).\n\n[6] Tang et al. \"Privacy-preserving in-context learning with differentially private few-shot generation.\" ICLR 2024.\n\n[7] Mattern, et al. \"Differentially private language models for secure data sharing.\" EMNLP 2022.\n\n[8] Yue et al. \"Synthetic text generation with differential privacy: A simple and practical recipe.\" ACL 2023.\n\n[9] Yuet al. \"Privacy-preserving instructions for aligning large language models.\" ICML 2024.\n\n[10] Tramèr et al.. \"Position: Considerations for differentially private learning with large-scale public pretraining.\" ICML 2024."}, {"review_id": "uvWVrrliVp", "reviewer": "Reviewer_wRyU", "summary": "This paper proposes an efficient differential privacy long text generation framework called InvisibleInk, which aims to solve the problem of protecting sensitive information when generating text while ensuring the quality of the generated text and low computational cost.", "questions": "For specific questions, please see \"Weaknesses\".", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths：\n\n1.The two core technologies proposed in this paper, DClip and Top-k+ sampling, fundamentally solve the pain points of high computational overhead and poor text quality in traditional DP text generation. DClip avoids redundant privacy consumption of language prior knowledge by directional clipping of sensitive information differences, while Top-k+ sampling cleverly combines the efficiency of non-private decoding with the privacy protection of DP.\n\n2.By deeply combining differential privacy with the LLM generation process, a complete long text generation framework was constructed. Different from the previous method of simply applying the exponential mechanism, the design of InvisibleInk is more in line with the generation characteristics of LLM, providing new ideas for the application of DP in the field of NLP.\n\n3.Experiments are conducted on datasets from three different fields: medical, legal, and commercial, including MIMIC-IV, TAB, and Yelp, to verify the universality and cross-domain adaptability of the framework.\n\nWeaknesses：\n\n1. The privacy protection capability of the algorithm has not been verified under specific attack scenarios (e.g. membership inference attack).\n\n2. The algorithm description in Figure 1 is too simple, and the algorithm execution process cannot be intuitively seen, especially Top-k+ sampling. I don’t know what the green dotted line means.\n\n3. The horizontal axis of Figure 3 is not clearly stated.\n\n4. Why is privacy loss of +∞ in line 190?\n\n5. Why is Top-k+ sampling constructed? The full text does not seem to explain it clearly, so I don’t know whether it is necessary.\n\n6. This method is only applicable to white-box LLMs, and cannot benefit from the closed-source black-box LLMs.\n\n7. The experiment only compares the MAUVE scores of synthetic text and reference text, which can only reflect the similarity of the overall distribution, and does not test the utility on specific downstream tasks. The RAG mentioned in the abstract and introduction does not seem to have specific experiments in this scenario.", "was_revised": true, "final_justification": "I have read the authors' response. Thanks for the rebuttal. The response mainly addressed my concerns. I will raise my rating accordingly.", "rebuttal": "We thank the reviewer for the thorough review and the questions they have raised. We answer each one in detail.\n\n> The privacy protection capability of the algorithm has not been verified ...\n\nFollowing established practice in the literature, we do not perform attack evaluations. Most prior works in private text generation [1-6] do not conduct additional study on the effectiveness of privacy protection when subjected to membership inference attacks. This is similar in spirit to DP model training, where one does not usually evaluate the effectiveness of training algorithms with membership inference attacks.\n\nAs an aside, we note that research on designing effective membership inference attacks for text generated by LLMs is a new and emerging research topic ( the first promising work in this field is the recent paper by Meeus et al. (ICML 2025) [7]). \n\n> … description in Figure 1 is too simple ... what the green dotted line means.\n\nThe green dotted line in Figure 1 is the top-k threshold of the public logits. Only tokens in the clipped-and-aggregated logits that lie in the public top-k set are selected in naive top-k sampling; the rest are discarded. \n\nHowever, when private logits are clipped and aggregated using DClip, individual private logits may cause a deviation of at most C/B to the public logit values of every token. In particular, some tokens outside the public top-k set may now clear the threshold. Top-k+ sampling (modified threshold denoted by the solid green line) allows us to recover a few such tokens, which would otherwise have been discarded with naive top-k sampling.\n\nWe would be happy to elaborate on any specifics and update the figure as required. \n  \n> The horizontal axis of Figure 3 is not clearly stated.\n\n- Leftmost fig.:  The horizontal axis denotes the value of the logits $\\phi_i(y)$ for different values of the index $i$ and the token $y$. This is calculated based on one batch of size B=127 from the MIMIC data, pooled over 500 generated tokens. \n- Middle left fig.: Same setting as the above, but the horizontal axis now denotes the difference of private and public logits, i.e., $\\phi_i(y)  - \\phi_{pub}(y)$ for different values of the index $i$ and token $y$. \n- Right two fig.: The horizontal axis denotes the token index, when ranked in decreasing order of the unclipped logit value (which we refer to as token rank). We select an unclipped private logit vector from the MIMIC data generation and compare the distortion introduced by using the clipping function of Amin et al. (2024) [2] and our proposed clipping function, DClip.\n\nWe will make this clear in the caption.\n\n> Why is privacy loss of +∞ in line 190?\n\nWhen the inclusion or exclusion of a sensitive reference causes a token to \"jump out\" of the top-k set, its probability of being generated goes from a non-zero value to a zero value. In such a case, the privacy loss random variable takes a value of $+\\infty$. We elaborate on this below.\n\nWe first recall the definition of the privacy loss (e.g. Definition 2 of Steinke (2022) [8]).  Let $P$ and $Q$ be 2 probability distributions on $\\mathcal{Y}$, which correspond to the outputs of a randomized mechanism on two “neighbouring” inputs. The privacy loss random variable, denoted by $Z$, is defined as $Z=f_{P||Q}(Y)=log(P(Y))/log(Q(Y))$ where $Y$ is distributed according to $P$. \n\nSuppose a given token $y$ lies in $\\bar{V}_k$ as defined in line 183 of the main paper for a given set of references $R=(r_1, \\dots, r_B)$. Let $y\\notin \\bar{V}_k$ for some $R’$ adjacent to $R$. Note that this is possible since $\\bar{V}_k$ is dependent on the clipped private logits $\\phi^{\\text{clip}}_i$. Since we discard all tokens not in $\\bar{V}_k$, the probability of token $y$ being output for the reference set $R$ and $R’$ are non-zero (i.e. $P(y) \\neq 0$) and zero (i.e. $Q(y) = 0$), respectively. Thus, the corresponding value of the privacy loss random variable at $Y=y$ is $\\log( P(y) / Q(y)) = +\\infty$. \n\nNote that when the set of discarded tokens does not depend on the private logits, moving from reference set $R$ to $R’$ does not affect the probabilities of outputting any given token. Thus, privacy loss remains zero for all tokens, i.e., no privacy is leaked.\n\n> Why is Top-k+ sampling constructed ...\n\nNaively sampling the top-k tokens from the public logits potentially discards tokens that are highly ranked in the private logits. Such tokens are likely to be relevant to the data generation domain, and it is thus desirable to recover them. However, selecting them based on the private logits leaks privacy (as above). \n\nTo circumvent this issue, we design Top-k+ sampling. We explain this step-by-step below:\n\n- We calculate the top-k threshold $l$ of the public logit $\\phi_{\\text{pub}}$\n- We lower the threshold by $2C/B$. The new threshold $l’ = l - 2C/B$ (Note that this modified threshold is still agnostic to private logits)\n- We select all tokens in $V$ that have public logit values higher than $l’$ into $V_k^+$. \n\nTo summarize, we construct a tight superset of the public top-k token set by lowering the public top-k threshold by $2C/B$. \n\nWhen private logits are clipped and aggregated using DClip, individual private logits may cause a deviation of at most $C/B$ to the public logit values of every token. Let $\\phi_i^{\\text{clip}} = \\phi_{\\text{pub}} + \\frac{1}{B}\\text{clip}\\_C(\\phi_i, \\phi_{\\text{pub}})$ be the contribution of one private logit. Then for a token $y\\in V$ (token indexed by $k$, i.e. $\\phi(k)$ refers to top-k$^{th}$ token):\n\n$$ \\phi_i^{\\text{clip}}(y) \\geq \\phi_i^{\\text{clip}}(k) \\Rightarrow \\phi_{\\text{pub}}(y) + \\frac{1}{B}\\text{clip}\\_C(\\phi_i(y), \\phi_{\\text{pub}}(y)) \\geq \\phi_{\\text{pub}}(k) + \\frac{1}{B}\\text{clip}\\_C(\\phi_i(k), \\phi_{\\text{pub}}(k)) \\Rightarrow \\phi_{\\text{pub}}(y) \\geq \\phi_{\\text{pub}}(k) - 2C/B,$$\n\nwhere the last step uses the fact that each $\\text{clip}\\_C(x,y)$ is bounded to lie in the range $[-C, +C]$. Since $C\\ll B$ typically, and $|V_k^+ - V_k(\\phi_{\\text{pub}})| \\ll |V|$ from Table 11 (p.39 App. E2), we see that $V_k^+$ is indeed a tight superset of the public top-k token set.\n\nWe would be happy to add this discussion to the revised draft.\n\n> This method is only applicable to white-box LLMs...\n\nWhile LLMs like Claude, GPT4, and Gemini are hidden behind an API, there is an increasing number of state-of-the-art general-purpose and reasoning open-weights models like DeepSeek, LLaMA3, and Mistral. Such models allow white-box logit access and are compatible with InvisibleInk.\n\nAs demonstrated in Fig. 6 (p. 38, App. E) of the supplement, leveraging the whitebox access to the logits allows us to significantly outperform the state-of-the-art API-access method AugPE [9].\n\nFurther, white-box access to next-token logits is a commonly studied setting in the literature on DP text generation. For example, see [1-4]. InvisibleInk operates under the same assumptions but demonstrates an order-of-magnitude improvement in the privacy-utility-compute tradeoff.\n\n> ... does not test the utility on specific downstream tasks ...\n \nFollowing the reviewer’s excellent suggestion, we ran additional experiments to evaluate the synthetic data on a downstream task. We finetune a RoBERTa model for sequence classification of the generated synthetic text from the Yelp dataset into 50 classes, obtained as all combinations of 5 review score labels and 10 business category labels. (Since the synthetic data generation is conditioned on these axes, the class label information is also available in the synthetic data.) \n\nWe report the following metrics: \n\n- Classification Accuracy: correct predicted class (%age)\n- Top-5 Accuracy: correct class in the top-5 predictions (%age)\n- Category Accuracy: correct business category (%age)\n- Score Accuracy: correct review score (%age)\n- Score L1: Average L1 distance between predicted and true review scores\n\nThe results presented in the table compare the downstream utility metrics for text generated by various methods with a fixed privacy budget of $\\varepsilon=10$.\n\n| Method | Accuracy ($\\uparrow$) | Top-5 Acc. ($\\uparrow$) | Cat. Acc. ($\\uparrow$) | Score Acc. ($\\uparrow$) | Score L1 ($\\downarrow$) |\n|---|---|---|---|---|---|\n| InvisibleInk (B=8) | **32.98**  | **72.16**  | **64.90** | **52.2**  | **0.652** |\n| Amin et al. (2024) (B=128) | 29.44 | 64.56 | 60.18 | 46.64  | 0.748 |\n| AdaPMixED (B=32)  | 7.44 | 34.72 | 56.82 | 15.44  | 1.858 |\n\nInvisibleInk outperforms all baseline methods by a large margin at a significantly smaller computation cost, even when measured in terms of this downstream task utility. We will include these in the revision. These results are similar to MAUVE and overall text similarity metrics.\n\nApart from MAUVE scores, we also report additional evaluation metrics, such as MedNER counts, average generation lengths, and the difference in generation perplexity between real and synthetic data; see App. D4 (pp. 33-34).\n\n[1] Amin, et al. \"Private prediction for large-scale synthetic text generation.\" EMNLP (2024).\n\n[2] Flemings et al.. \"Differentially private next-token prediction of large language models.\" NAACL-HLT 2024.\n\n[3] Flemings et al.. \"Adaptively private next-token prediction of large language models.\" (2024).\n\n[4] Tang et al. \"Privacy-preserving in-context learning with differentially private few-shot generation.\" ICLR (2024).\n\n[5] Yue, et al. \"Synthetic text generation with differential privacy: A simple and practical recipe.\" ACL 2023.\n\n[6] Yu, et al. \"Privacy-preserving instructions for aligning large language models.\" ICML 2024.\n\n[7] Meeus, et al. \"The Canary's Echo: Auditing Privacy Risks of LLM-Generated Synthetic Text.\" ICML (2025).\n\n[8] Steinke. \"Composition of differential privacy & privacy amplification by subsampling.\" (2022). Chapter 3 of the book “Differential Privacy in Artificial Intelligence: From Theory to Practice.”\n\n[9] Xie, et al. \"Differentially Private Synthetic Data via Foundation Model APIs 2: Text.\" ICML 2024."}]

Author rebuttal:

Meta-review: The paper proposed a new approach for private-RAG-based synthetic text generation.  The authors did a good job in the rebuttal in clarifying matters. All concerns are addressed and all four reviewers endorse the paper.  I briefly checked the algorithm and the proof and it appears to be correct.  

I'd be happy to recommend accept.
Decision: Accept (poster)