Ask in the Crowd: Differentially Private LLM Inference via Dummy-Augmented Shuffling

Zhihao Liu, Zixiong Guo, Shuo Shao, Yu He, Wenli Wang, Meihui Chen, Di Wang, Yuke HuarXiv 2026 · arXiv

TL;DR

DP-SPD is a novel framework for privacy-preserving LLM inference that hides a user's real query within a "crowd" of contextually plausible dummy queries. By combining local differential privacy with client-side shuffling and exploiting shared-prefix KV-cache reuse, it achieves near-perfect accuracy (utility) and significant speedups while keeping sensitive data safe from curious service providers.

What Problem Does This Paper Address?

As Large Language Models (LLMs) become ubiquitous via cloud-based "LLM-as-a-Service" (LLMaaS), we face a massive privacy bottleneck. To get an answer, you have to send your raw query—which might contain medical records, financial data, or private thoughts—directly to a server.

Existing solutions like Differential Privacy (DP) usually involve adding random noise to input embeddings. However, text is fragile; adding enough noise to truly hide the data often "breaks" the query, leading to gibberish outputs or massive drops in accuracy. Cryptographic methods like homomorphic encryption offer better privacy but are too computationally expensive for real-time use. The authors tackle this "privacy-utility-efficiency" trilemma by moving away from pure noise-injection toward a "hiding in plain sight" strategy.

Methods

The core idea of DP-SPD (Differentially Private Shuffling with Prefix-conditioned Dummies) is to make the server guess which query is the real one. The workflow happens entirely on the local user side before anything hits the cloud:

  1. Prefix-Suffix Splitting: The query is split into a shared prefix and a private suffix.
  2. Prefix Privatization: The prefix is perturbed with noise and projected back to tokens to ensure it doesn't leak information while remaining a valid starting point.
  3. Dummy Generation: A lightweight local model (like Qwen2.5-0.5B) generates $k$ "dummy" suffixes that are contextually consistent with the privatized prefix. This makes the dummies much harder for an adversary to distinguish from the real query.
  4. Local Shuffling: The real suffix and the dummy suffixes are independently perturbed with a small amount of noise, then randomly shuffled.
  5. Server-Side Inference & KV-Cache Reuse: The server receives a batch of $k+1$ queries. Because they all share the same prefix, the server can compute the prefix once and reuse the Key-Value (KV) cache for all suffixes, drastically reducing the extra work caused by the dummies.
  6. De-shuffling: The client receives all $k+1$ responses and simply picks the one corresponding to the original real query's position.
Figure 1: Full workflow of DP-SPD. The client generates prefix-consistent dummy suffixes, perturbs and shuffles them locally, and sends the shuffled noisy candidates to the server for inference.

Datasets

The authors evaluated DP-SPD across a wide range of tasks and models:

  • Classification: Evaluated on IMDb (sentiment), SST-2, and QNLI using BERT and LLaMA-2-7B-Chat.
  • Generation: Tested on WikiText-2, Stanford Alpaca, and Databricks-Dolly-15k.
  • Large-Scale/Real-World: Tested Qwen3-14B on CNN/DailyMail summarization and Qwen3-32B on 1,000 real-world queries from the WildChat dataset.

Key Insights and Ideas

  • Anonymity via Shuffling: Unlike standard DP which relies solely on noise, DP-SPD uses "privacy amplification by shuffling." Hiding one real query among 30 dummies allows the system to use much less noise on each individual query, preserving the semantic meaning.
  • Contextual Plausibility Matters: If you use random words as dummies, a modern LLM (or a GPT-based attacker) can easily spot the "weird" query. By conditioning dummies on the same prefix, they look like legitimate alternative intents.
  • The Efficiency "Free Lunch": Usually, adding $k$ dummies means $k$ times the cost. By exploiting the transformer's KV-cache mechanism, the authors turn a privacy feature into an architectural optimization, making "crowd-based" privacy practical.
  • Metric DP ($d_\chi$-privacy): The authors use a metric that measures privacy loss based on Euclidean distance in the embedding space, which better captures semantic similarity in language than traditional "neighboring dataset" definitions.

Key Results

  • Near-Plaintext Utility: On classification tasks (SST-2/QNLI), DP-SPD maintained over 90% accuracy, staying within ~1% of the non-private "plaintext" baseline. In contrast, older DP methods like DP-Forward often crashed to near-random guessing (approx. 50%).
  • Strong Generation Quality: For instruction-following tasks, DP-SPD achieved Perplexity (PPL) and ROUGE-L scores very close to the original model, significantly outperforming all evaluated baselines.
  • Efficiency Gains: For a 1024-token sequence with 24 dummies, shared-prefix reuse provided a 3.86× speedup compared to processing the queries independently.
  • Robustness to Attacks: The system was tested against "GPT-based attacks" where an attacker uses GPT-4o-mini to try and identify the real query. DP-SPD successfully reduced the attack success rate as the number of dummies ($k$) increased.
Figure 3: Comparison with related private-inference meth- ods on instruction generation using LLaMA-2-7B-Chat at ϵ = 2.5. Lower PPL and higher ROUGE-L are better; PPL uses a logarithmic scale.

Limitations and Future Work

  • Fixed Splitting: The current version uses a fixed split point for the prefix and suffix. The authors suggest that future work could dynamically identify "sensitive spans" to protect them more effectively.
  • Single-Turn Focus: The analysis currently focuses on single queries. Extending this to multi-turn conversations (where context must be maintained across several rounds) remains an open challenge.
  • Local Model Requirement: Users need a lightweight model locally to generate dummies. While 0.5B models are small, this still imposes a minor hardware requirement on the client side.

Summary updated

Abstract

Large language models are increasingly deployed as LLM-as-a-Service (LLMaaS), where user queries are sent to remote LLMs for inference, raising severe privacy concerns about the exposure of sensitive user inputs. Differentially private inference mitigates these risks by injecting noise into input embeddings. However, existing methods struggle to balance privacy and utility, as stronger privacy protection often leads to substantial accuracy degradation in LLM inference. In this work, we propose DP-SPD, a differentially private LLM inference framework that protects user queries by hiding the real query among client-generated dummy queries. All queries are randomly shuffled before being sent to the server, preventing direct identification of the user's true intent. To improve inference efficiency, we exploit the shared-prefix structure among queries and reuse transformer key--value (KV) caches during decoding. We analyze the privacy guarantee of DP-SPD and evaluate its utility on classification and generation tasks, as well as its privacy protection under QIA, EIA, and GPT-based attacks. Experimental results show that our method achieves strong inference-time privacy protection and near-plaintext utility while improving inference efficiency through shared-prefix KV-cache reuse.
BibTeX
@misc{liu2026ask,
  author = {Zhihao Liu and Zixiong Guo and Shuo Shao and Yu He and Wenli Wang and Meihui Chen and Di Wang and Yuke Hu},
  title = {{Ask in the Crowd: Differentially Private LLM Inference via Dummy-Augmented Shuffling}},
  year = {2026},
  eprint = {2611.25669},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25669},
}
Figure