📄 STAMP: Selective Task-Aware Mechanism for Text Privacy

Summary

The paper addresses client-side privatization of user text before it reaches a remote LLM or other downstream consumer, under local differential privacy (LDP). Earlier approaches, such as randomized response or isotropic Laplace/Gaussian noise on embeddings, typically apply the same budget to every token and damage meaning. STAMP instead splits tokens into groups along two axes. One is how relevant a token is to the task, measured by similarity to a task- or query-specific representation. The other is whether the token is sensitive, as flagged by NER/PII detection of items like names, dates and identifiers. Each group then receives its own privacy budget. For the noise itself, the authors propose a polar mechanism that keeps an embedding's norm fixed and randomizes only its direction on the unit sphere using von Mises-Fisher sampling. Text is recovered by cosine nearest-neighbor lookup, so the decoding geometry matches the noise geometry. On SQuAD, Yelp and AG News, STAMP gives better utility than uniform budgeting at equal per-token budgets, and the polar mechanism beats Laplace noise. The extra computation is negligible, which makes task-aware text privacy practical to deploy.

Key points

• Tokens are sorted into four groups (G1–G4) by crossing task importance with privacy sensitivity. Noise is concentrated on content that is sensitive but unimportant to the task. Utility falls steadily as more groups are perturbed, and Uniform allocation is the lowest-utility case.
• The gains are largest when importance is conditioned on a question, as in SQuAD. They are smaller with fixed prompts, as in Yelp and AG News.
• Overhead is small:
  • The grouping step adds about 0.002 s per SQuAD example (roughly 180 tokens).
  • STAMP-Polar runs at 35.16 s per example (195 ms/token), versus 34.54 s (192 ms/token) for the Laplace baseline.
• vMF sampling scales as O(d), comparable to Gaussian or Laplace sampling.
• The authors list several limitations:
  • The method needs a meaningful task description.
  • Grouping relies on static embedding similarity.
  • Results depend on the quality of PII detection.
  • With 768-dimensional embeddings, fairly large per-token ε values are needed to keep utility.