InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy

Vishnu Vinod, Krishna Pillutla, Abhradeep Guha Thakurta

TL;DR

InvisibleInk is a highly scalable framework for generating long-form text with rigorous differential privacy (DP) guarantees at a fraction of the cost of prior methods. By isolating and clipping only the sensitive information in model logits and introducing a novel truncated decoding algorithm called Top-$k$+ sampling, it reduces computational overhead by $8\times$ or more compared to state-of-the-art baselines. This brings the cost of private text generation down to less than $4$-$8\times$ that of non-private generation, making DP practical for real-world large language model (LLM) deployments like Retrieval-Augmented Generation (RAG).

What Problem Does This Paper Address?

As LLMs are increasingly trusted with long-form text generation and complex reasoning tasks (such as RAG or "deep research" agents), they routinely process highly sensitive data provided at inference time. This includes confidential corporate documents, medical records, or private user queries. Unfortunately, detailed long-form generation carries a high risk of inadvertently leaking these sensitive details.

While Differential Privacy (DP) can provably mitigate this risk, existing white-box DP text generation methods suffer from severe practical limitations:

  1. Massive Compute Overhead: Prior state-of-the-art methods require up to $100\times$ or more computational overhead compared to non-private generation to avoid producing gibberish.
  2. Text Degeneration: To maintain privacy, these methods typically sample from the full vocabulary distribution at high temperatures, which destroys the fluency, coherence, and structure of the generated text.

Methods

InvisibleInk models next-token sampling as an iterative application of the exponential mechanism over the LLM's logits. It introduces two key innovations to solve the compute and quality bottlenecks:

Figure 1: INVISIBLEINK interprets differentially private text generation as an iterative application of the exponential mechanism over a subset of the LLM’s clipped logits. Our key innovations are: (a) DClip, an improved clipping function to reduce the 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.

1. DClip (Targeted Clipping Function)

Standard DP methods clip the raw private logits directly to bound sensitivity. However, private logits contain a massive amount of non-private information (e.g., grammar, syntax, and general world knowledge).

DClip isolates only the sensitive information by computing the difference between the private logits ($\phi_i$) and the public logits ($\phi_{pub}$) generated without the sensitive context: $$\text{DClip}_C(\phi_i, \phi_{pub}) := \phi_{pub} + \text{clip}_C(\phi_i - \phi_{pub})$$ Because the public model already provides a strong linguistic prior, the delta ($\phi_i - \phi_{pub}$) is tightly concentrated around zero. This allows the framework to use a much smaller clipping norm ($C \approx 1$ vs. $C \approx 10$ in baseline methods) without distorting the distribution, drastically lowering privacy sensitivity and compute cost.

2. Truncated Top-$k$+ Sampling

Standard top-$k$ sampling restricts token selection to the highest-probability tokens to prevent text degeneration, but doing so directly on private logits violates DP.

InvisibleInk introduces **Top-$k$+$ sampling**, which constructs a tight *superset* ($V_k^+$) of the top-$k$ private tokens using *only* the public logits. By mathematically shifting the public top-$k$ threshold downward by $2C/B$ (where $B$ is the batch size), the authors guarantee that any token that *would* have made it into the private top-$k$ vocabulary is safely included in this expanded public vocabulary. Because $V_k^+$ is constructed purely from public information, sampling from it incurs zero privacy cost while preserving the high utility of truncated decoding.

Datasets

The authors evaluated InvisibleInk across three distinct, privacy-sensitive domains featuring long-form text:

  • MIMIC-IV-Note: A large, de-identified collection of clinical ICU discharge summaries containing highly sensitive medical diagnoses and treatment plans. This dataset is legally unavailable for standard LLM pretraining, making it an excellent out-of-distribution test bed.
  • Yelp Reviews: A standard commercial benchmark dataset consisting of user-generated business reviews, personal opinions, and location references.
  • TAB (Text Anonymization Benchmark): A low-resource legal dataset containing court case transcripts from the European Court of Human Rights (ECHR), annotated with personal identifiers.

Key Insights and Ideas

  • Don't Pay for What the Public Model Already Knows: The core philosophical shift in DClip is recognizing that grammar, syntax, and basic facts aren't secrets. By penalizing only the deviation from the public model, the privacy budget is spent exclusively on protecting the actual sensitive context.
  • Graceful Fallback: If the compute or privacy budget approaches zero, InvisibleInk naturally and gracefully degrades to the performance of the base public model. In contrast, previous methods collapse into uniform random sampling, outputting pure gibberish.
Figure 3: Left two: Histograms of private logits ϕi and differences from public logits ϕi −ϕpub for a synthetic data sample generated from the MIMIC dataset, with 5th and 95th percentiles shown by the dotted lines. The spread of values for ϕi −ϕpub is significantly smaller (around 10×) than that of ϕi. Thus, DClipC(ϕi, ϕpub)(y) = ϕi(y) for over 95% of all y ∈V with C ≈1, while the naive clipping of Amin et al. [13] requires C ≈8. This translates into an 8× gain in computational efficiency. Right two: A small clip norm of C = 1 (using Amin et al. [13]’s method introduces significant bias resulting in a near-uniform distribution over the vocabulary. In contrast, DClip (see §4) preserves probabilities with minimal distortion even at C = 1.

Key Results

  • $8\times$ Compute Reduction: Across medical, legal, and commercial domains, InvisibleInk consistently achieved an $8\text{--}16\times$ reduction in computational cost (measured via next-token inference calls and wall-clock time) compared to prior state-of-the-art white-box baselines for the same privacy-utility trade-offs.
  • Superior Text Quality: Using the MAUVE metric to evaluate distributional similarity to real human text, InvisibleInk significantly outperformed baselines. For instance, on the MIMIC dataset with a strict compute budget ($B=7$), baselines completely failed to generate text (marking them as infeasible), while InvisibleInk achieved high-quality generations matching non-private baselines.
  • Downstream Utility: When training a RoBERTa classifier on synthetic data generated by the various private methods, data generated by InvisibleInk yielded substantially higher classification accuracy ($32.98\%$) compared to Amin et al. ($29.44\%$) and AdaPMixED ($7.44\%$).

Limitations and Future Work

  • White-Box Requirement: InvisibleInk assumes a trust model where a central aggregator has white-box access to the LLM's weights and next-token logits. It cannot be used out-of-the-box with closed, API-only models (like GPT-4), though it completely outperforms existing API-based DP alternatives like AugPE when white-box access is available.
  • Example-Level vs. User-Level Privacy: The current framework provides example-level DP (protecting a single document or reference text). Extending this to user-level DP (protecting all documents contributed by a single user) remains an open direction.
  • Token Budget Scaling: The privacy guarantee scales with the maximum token length $T$. Finding ways to improve this dependence using regularization or advanced composition techniques is left for future work.

Summary updated

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$-$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.
BibTeX
@inproceedings{vinod2025invisibleink,
  author = {Vishnu Vinod and Krishna Pillutla and Abhradeep Guha Thakurta},
  title = {{InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=B4NT8TexNS},
}
Figure