STAMP: Smarter Text Privacy by Treating Tokens Differently

Paper: 2603.12237 Authors: Fengwei Tian, Payel Bhattacharjee, Heidi Hanson, Geoffrey D. Rubin, Joseph Y. Lo, Ravi Tandon Categories: cs.LG, cs.CR, cs.IT

The Gap

Text privatization under local differential privacy (LDP) has been an active area since Feyisara et al.’s CusText and the Mahalanobis mechanism (Xu et al.), and more recently the metric-LDP approaches like SanText and CMP. These methods perturb token embeddings by adding calibrated noise, then decode back to the nearest word. The problem: they treat every token the same. “The” gets the same privacy budget as “John Smith.” A date of birth gets the same noise as a filler word. This uniform allocation is wasteful — you’re burning privacy budget on tokens that don’t matter and under-protecting the ones that do.

There’s also a geometric mismatch. Most mechanisms add isotropic Gaussian or Laplace noise in embedding space, but decoding is done via cosine similarity (nearest neighbor on the unit sphere). You’re perturbing in one geometry and decoding in another. That’s like measuring a room in feet and cutting lumber in meters — the numbers don’t line up.

Problem: Uniform budget + geometry mismatch
         |
         v
Assumption: Token importance and sensitivity vary;
            perturbation geometry should match decoding geometry
         |
         v
Method: STAMP = selective budget allocation (task + sensitivity)
               + polar mechanism (direction-only perturbation)
         |
         v
Evidence: SQuAD, Yelp, AG News -- better privacy-utility curves
         |
         v
Conclusion: Fine-grained token treatment beats uniform noise
            when you align geometry with decoding

The Increment

One sentence: Before STAMP, text privatization treated every word as equally important and perturbed embeddings in a geometry misaligned with decoding; after STAMP, budgets are allocated by what matters and noise lives on the same sphere where decoding happens.

Core Mechanism

STAMP has two separable ideas that work together. The first is the budget allocation policy. For each token in the input, STAMP computes two scores: a task-relevance score (how much does this token affect the downstream prediction — think attention weights or gradient-based importance) and a privacy-sensitivity score (is this a named entity, a date, an identifier?). These two scores jointly determine how much of the total privacy budget epsilon gets assigned to this token. High-sensitivity tokens get more noise; low-importance tokens also get more noise (since corrupting them costs little utility). The sweet spot — high task importance, low sensitivity — gets the most budget preserved.

The second idea is the polar mechanism. Instead of adding a noise vector anywhere in embedding space, STAMP projects the token embedding onto the unit sphere and perturbs only its direction. The magnitude stays fixed. The perturbation is drawn from a distribution on the sphere calibrated to the assigned epsilon. Decoding then uses cosine nearest-neighbor search, which is exactly the right operation on a unit sphere. The geometry of perturbation and the geometry of decoding are now the same thing.

At inference time: tokenize input → embed tokens → score each token for task relevance and sensitivity → assign per-token epsilon → apply polar perturbation → decode each perturbed embedding via cosine NN → reconstruct privatized text → send to downstream model.

Input text
    |
    v
[Tokenizer] --> token_1, token_2, ..., token_n
                    |
                    v
             [Embedding layer]
                    |
                    v
         +----------+----------+
         |                     |
  [Task relevance]    [Sensitivity tagger]
  (attention/grad)    (NER, rule-based)
         |                     |
         +----------+----------+
                    |
                    v
         [Budget allocator]
         epsilon_i = f(relevance_i, sensitivity_i)
                    |
                    v
         [Polar mechanism]
         project to unit sphere
         perturb direction by epsilon_i
                    |
                    v
         [Cosine NN decoder]
         find nearest word on sphere
                    |
                    v
         Privatized token sequence
                    |
                    v
         Downstream task (QA, classification, etc.)

Think of it like a postal sorting office with a security clearance system. Each letter (token) arrives and gets two stamps: one for how important it is to the recipient (task relevance) and one for how sensitive its contents are (privacy sensitivity). The sorting office then decides how much to scramble each letter before forwarding it — important but non-sensitive letters go through mostly intact, sensitive letters get heavily redacted, and junk mail gets scrambled freely because nobody cares. The scrambling itself (polar mechanism) is done by rotating the letter’s orientation on a globe rather than stretching or shrinking it — so when the recipient uses their globe-based decoder to read it, the geometry matches perfectly. Without this metaphor: you’re back to staring at epsilon allocation tables.

Key Concepts

• Metric Local Differential Privacy (metric-LDP): Regular LDP says “your output shouldn’t reveal which of two possible inputs you had.” Metric-LDP relaxes this: inputs that are *close to each other (by some distance metric) are allowed to produce more similar outputs. In text, two semantically similar words (“happy” and “joyful”) can produce more similar privatized outputs than two unrelated words (“happy” and “carburetor”). This lets you add less noise while still providing meaningful privacy guarantees — the privacy budget epsilon now scales with semantic distance rather than being a flat bound.

• Polar mechanism: Standard noise mechanisms add a vector sampled from a ball or Gaussian in R^d. The polar mechanism instead samples a perturbation *on the unit sphere — only the direction changes, not the magnitude. This matters because cosine similarity (used for NN decoding) is purely a function of direction. If you add radial noise, you’re perturbing something the decoder ignores. The polar mechanism wastes no noise budget on the radial component.

• Privacy-utility trade-off curve: For a given epsilon, you get some level of privacy (measured by how hard it is to recover the original token) and some level of utility (measured by downstream task accuracy). The “trade-off” is the curve you trace as epsilon varies. A better mechanism shifts this curve — same privacy, higher utility, or same utility, stronger privacy. STAMP claims to shift the curve favorably compared to SanText and CMP baselines.

Framework Shift

Before (mainstream approach):        After (this paper):

Input tokens                         Input tokens
  |                                    |
  v                                    v
[Embed all tokens]               [Embed + Score each token]
  |                                    |  (task relevance + sensitivity)
  v                                    v
[Apply uniform epsilon]          [Assign per-token epsilon_i]
  |                                    |
  v                                    v
[Isotropic noise in R^d]         [Polar perturbation on S^(d-1)]
  |                                    |
  v                                    v
[Cosine NN decode]               [Cosine NN decode]
  |                                    |
  v                                    v
Privatized text                  Privatized text

  * same noise everywhere            * noise proportional to what matters
  * geometry mismatch                * geometry aligned end-to-end

From uniform-and-misaligned to selective-and-coherent, the core shift is treating token heterogeneity as a first-class design variable rather than an afterthought.

Expert Assessment

Problem choice: This is a real gap. The uniform budget allocation problem has been noted informally in the community for a while, and the geometry mismatch between isotropic perturbation and cosine decoding is a genuine inconsistency that’s easy to overlook. The paper sits at a natural next step in the metric-LDP-for-text trajectory. It’s not a manufactured gap, though it’s also not a surprising one — someone was going to close this.

Method maturity: The polar mechanism is a clean, principled insight. The budget allocation is more heuristic — the specific function mapping (relevance, sensitivity) to epsilon is not deeply theorized, and the choice of task-relevance proxy (attention weights vs. gradients) is left somewhat open. The combination is clever but not tight. A simpler baseline worth comparing: just allocate more budget to named entities and nothing else. The paper doesn’t show this ablation clearly enough.

Experimental integrity: The datasets (SQuAD, Yelp, AG News) are standard and the baselines (SanText, CMP) are appropriate. The privacy-utility curves look convincing. One concern: the task-relevance scoring requires access to a model, which means the privacy guarantee is conditioned on that model being available at privatization time. This is a non-trivial assumption for deployment scenarios (e.g., client-side privatization before sending to a server). The paper acknowledges this but doesn’t stress-test it. Also, the sensitivity tagger is rule-based NER — it would be worth knowing how performance degrades when the tagger makes errors.

Writing quality: The theoretical section on the polar mechanism is solid. The budget allocation section is where the paper gets hand-wavy — the joint scoring function is introduced without enough justification for why this particular combination is principled rather than just empirically tuned. Rewriting Section 3 (or wherever the allocation policy lives) with a cleaner theoretical motivation — even a simple information-theoretic argument — would elevate the whole paper from “nice engineering” to “principled framework.”

Verdict: weak accept — the polar mechanism is a genuine contribution and the selective allocation idea is well-motivated, but the allocation policy lacks theoretical grounding and the deployment assumptions deserve more scrutiny.

Takeaways

A few things worth stealing:

The geometry alignment principle is broadly applicable. Whenever you’re adding noise in one space and decoding in another, check whether your perturbation geometry matches your decoding geometry. This applies beyond text — any embedding-based retrieval system with privacy constraints has this issue.

The two-axis token scoring (task relevance × sensitivity) is a useful framing for any selective processing pipeline. You can apply this logic to attention masking, data augmentation, or even active learning sample selection — not just privacy.

The polar mechanism specifically is worth keeping in your toolkit if you work with cosine-similarity-based retrieval. Perturbing only direction while preserving magnitude is a clean way to add controlled noise without breaking the retrieval geometry.