💬 NLP

Beyond Direct Identifiers: Probabilistic Privacy Risk Estimation for Privacy-Conscious LLM Query Delegation

This paper proposes a probabilistic variant of Privacy-Conscious Delegation that utilizes an LLM-driven k-anonymity estimation metric and the newly created PUPA-SD dataset to better protect users from privacy risks arising from PII-free self-disclosures, demonstrating that this approach achieves an optimal privacy-utility balance for models like Llama-3.2-3B.

Original authors: Li Siyan, Zhou Yu, Julia Hirschberg

Published 2026-08-11

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Li Siyan, Zhou Yu, Julia Hirschberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're chatting with a super-smart robot friend who knows everything in the world. You might feel safe sharing a secret, thinking, "I won't tell it my name or address, so I'm fine!" But here's the twist: even without your name, the robot could still guess who you are just by putting together tiny clues. It's like trying to hide in a crowded room by wearing a mask but leaving your unique hat, shoes, and a specific scar visible. If enough people in the room have that same hat, you're safe. But if only one person in the whole city has that hat and those shoes and that scar, the mask doesn't help much. This is the world of "privacy," where scientists worry that even when we remove obvious secrets (like names), the mix of small details we share can still let strangers figure out exactly who we are.

This paper dives into a new way to protect us when we ask these robot friends for help. The researchers are working on a system where a small, safe robot on your phone (the "local" model) rewrites your question before sending it to the big, powerful robot in the cloud (the "remote" model). The goal is to make the question still make sense to the big robot, but strip away anything that could identify you. The paper suggests that just removing obvious secrets isn't enough. Instead, they propose a new "privacy score" called k-anonymity. Think of this score as a measure of how many other people in the world could be described by the same set of clues. If your rewritten question describes a "34-year-old nurse in Austin," that's a very small group (low score). If it describes "someone managing a health issue," that could be millions of people (high score). The higher the score, the harder it is for anyone to pinpoint you.

The authors built a special playground of real user questions to test their idea, creating a dataset called PUPA-SD with 166 examples of people sharing personal stories. They then tried to teach their local robot to rewrite these questions not just to hide names, but to maximize that "privacy score." They found that for some robots, this new training worked wonders. Specifically, a model called Llama-3.2-3B became much better at the job: after training, it kept the quality of the answers high (scoring 67.4 out of 100) while drastically cutting down the number of secrets it accidentally leaked (dropping to 11.0). However, the paper notes that this isn't a magic fix for everyone. Smaller robots, like the Qwen-2.5-0.5B model, struggled to balance being helpful and being private; when they tried to get better at privacy, they sometimes started leaking more secrets or gave worse answers. The researchers suggest that using this "privacy score" as a guide is a promising step, but they also admit their current tools for counting how many people match a description rely on the robot's memory of the world, which might not be perfectly up-to-date. Ultimately, the study shows that while we can't perfectly hide in a crowd yet, we can start teaching our AI helpers to blend in a little better.

Technical Summary: Beyond Direct Identifiers: Probabilistic Privacy Risk Estimation for Privacy-Conscious LLM Query Delegation

1. Problem Statement

Current approaches to protecting user privacy in Large Language Model (LLM) interactions, specifically Privacy-Conscious Delegation (PCD), primarily focus on eliminating explicit Personally Identifiable Information (PII) (e.g., names, emails, specific locations) before queries are sent to untrusted remote models. However, the authors argue that removing explicit identifiers is insufficient for preserving anonymity. Users remain identifiable through quasi-identifiers—combinations of non-explicit traits (e.g., "34-year-old nurse in Austin with Type 2 diabetes") that, when aggregated, uniquely narrow the anonymity set.

The paper posits that existing PCD frameworks fail to account for probabilistic privacy risks arising from these self-disclosures. To address this, the authors propose augmenting PCD objectives with a probabilistic estimation of k-anonymity, a metric formalizing the ease of pinpointing an individual given a set of traits within a known population.

2. Methodology

2.1. The PCD-k Framework
The authors build upon PAPILLON, a strong baseline PCD framework where a trusted local model ( $M_{LOCAL}$ ) rewrites a user query ( $q$ ) into a sanitized query ( $q'$ ) before sending it to a powerful, untrusted remote model ( $M_{REMOTE}$ ). The authors introduce PCD-k, which adds k-anonymity as an additional optimization objective alongside response quality and PII leakage reduction.

2.2. Probabilistic Risk Estimation (BRANCH Integration)
To operationalize k-anonymity for free-form text, the authors integrate BRANCH (Zheng et al., 2025), a probabilistic framework that leverages an LLM's knowledge of census data and logical dependencies. The process involves:

Disclosure Extraction: Identifying personal attributes (e.g., age, occupation, location) from the text.
Bayesian Modeling: Ordering disclosures as random variables and determining conditional dependencies (e.g., occupation depends on location and age).
Estimation: The LLM estimates the probability of each attribute given the preceding ones based on pretraining demographic knowledge.
Calculation: The joint probability is multiplied by a population size (e.g., 400M English speakers) to yield the expected number of matching individuals ( $k$ ).

To improve efficiency, the authors simplify the Bayesian structure into cumulative conditioning groups and implement a caching mechanism using text embeddings to avoid redundant LLM calls for similar queries.

2.3. The PUPA-SD Dataset
To train and evaluate this probabilistic framework, the authors constructed PUPA-SD (Privacy-Conscious Delegation - Self-Disclosure).

Source: Extracted from WildChat and LMSYS-Chat-1M.
Content: 166 real user queries containing self-disclosures.
Processing: A validated extraction module (using GPT-5-mini) filters for self-disclosures, removing non-English and sexual content.
Characteristics: The dataset contains instances where explicit PII is absent, yet quasi-identifiers remain, demonstrating that standard PII detectors are insufficient.

2.4. Optimization Strategy
The authors use DSPy's SIMBA prompt optimizer to optimize the local model's rewriting prompt. The optimization metric is a weighted sum of:

Utility: Response quality and prompt well-formedness.
Privacy: The estimated k-anonymity score (normalized to [0,1] using a logarithmic scale: $\log_2(k) / \log_2(400M)$ ).
Note: PII leakage is not included in the optimization metric to prevent the model from simply deleting text to maximize k-anonymity; it is measured only during evaluation.

3. Key Contributions

Conceptual Shift: Proposes moving beyond explicit PII removal to probabilistic k-anonymity estimation as a core objective in PCD.
Dataset Creation: Introduces PUPA-SD, a dataset specifically curated to evaluate privacy risks arising from self-disclosures and quasi-identifiers.
Efficient Estimator: Adapts the BRANCH framework into a more data-efficient pipeline suitable for prompt optimization loops, utilizing cumulative conditioning and caching.
Empirical Analysis: Provides a comprehensive evaluation of how different local model sizes (ranging from 0.5B to 8B parameters) handle the trade-off between utility and probabilistic privacy.

4. Results

The experiments were conducted by optimizing on PUPA-SD and evaluating on the held-out PUPA-TNB dataset using various local models ( $M_{LOCAL}$ ) and GPT-4o-mini as the remote model ( $M_{REMOTE}$ ).

Quality vs. Privacy Trade-off:
- Llama-3.2-3B achieved the best balance, improving response quality (from 54.22 to 67.37) while significantly reducing PII leakage (from 29.13 to 11.03) and maintaining high k-anonymity.
- Smaller Models (e.g., Qwen-2.5-0.5B/1.5B): Struggled to jointly optimize quality and privacy. While quality improved, PII leakage often increased after optimization (e.g., Qwen-1.5B leakage rose from 54.40 to 62.95).
- Larger Models (e.g., Llama-3.1-8B): Showed significant quality gains but also experienced increased PII leakage, suggesting a difficulty in simultaneously satisfying all constraints.
k-Anonymity Stability: k-anonymity scores remained relatively stable across models and conditions. The authors note this may be because rewritten queries either removed disclosures entirely or became impossible to estimate with public data, causing the estimator to fall back to the full population size.
Correlation: A negative correlation ( $\rho = -0.4045$ ) was observed between the number of PIIs in original queries and estimated k-anonymity, confirming the pipeline's monotonic behavior.

5. Significance and Claims

The paper claims to take a "first step" toward probabilistic privacy-conscious delegation. Its primary significance lies in demonstrating that:

Eliminating explicit identifiers is insufficient; quasi-identifiers pose a real, quantifiable risk.
k-anonymity can serve as a useful auxiliary metric for PCD systems, provided the estimation is efficient enough for optimization loops.
Model capacity is a critical factor in navigating the privacy-utility trade-off; smaller models may struggle to jointly optimize for high-quality rewriting and strict privacy constraints.

Limitations Acknowledged:

Calibration: The k-anonymity estimates rely on LLM-encoded prior knowledge rather than real-time census data, potentially leading to inaccuracies or outdated statistics.
Dataset Size: PUPA-SD is small (166 instances), limiting statistical power and preventing post-training approaches for smaller models.
Language: The current pipeline and dataset are restricted to English.

The authors conclude that while their approach shows promise, future work is needed to ground estimates in current data (e.g., via agentic web search) and to expand the dataset to support more robust training and evaluation.