Technical Summary: Privacy Without Losing Place (PAS)

Problem Statement

The emergence of Spatial Retrieval-Augmented Generation (Spatial RAG) has enabled Large Language Models (LLMs) to answer location-aware queries (e.g., "find restaurants north of me within 1 mile"). However, current implementations require access to a user's exact geographic coordinates to function. This creates a critical privacy bottleneck: exposing precise coordinates to retrieval systems risks leaking sensitive information such as home addresses, workplaces, and daily routines, potentially enabling surveillance and profiling.

Existing location privacy mechanisms—such as geo-indistinguishability (adding continuous noise), spatial cloaking, and $k$-anonymity—are ill-suited for Spatial RAG. They often suffer from a utility-privacy dichotomy: either they introduce excessive noise that shifts the user's location outside the query radius (rendering the retrieval useless), or they fail to provide sufficient protection against triangulation. Furthermore, these methods are not tailored to the semantic nature of RAG queries, which often rely on relative spatial relationships (e.g., "near a landmark") rather than absolute coordinates.

Methodology: Privacy Anchor Substitution (PAS)

The authors propose Privacy Anchor Substitution (PAS), a structured mechanism that replaces exact coordinates with a discrete, semantically meaningful representation. PAS operates via a three-stage transformation:

1. Probabilistic Anchor Selection: Instead of perturbing the raw location $u$, the system probabilistically maps $u$ to a public anchor $a^*$ from a finite set of known landmarks (e.g., transit hubs, civic centers). This selection utilizes the Exponential Mechanism to ensure differential privacy guarantees:
   $$\Pr(a^* | u) \propto \exp\left(-\frac{\epsilon d(u, a^*)}{s}\right)$$
   where $d(u, a^*)$ is the distance between the user and the anchor, $\epsilon$ is the privacy parameter, and $s$ is a scaling factor.

2. Coarse Semantic Encoding: Once an anchor $a^*$ is selected, the system encodes the spatial relationship between the true location $u$ and the anchor into two discrete bins:

   • Direction Bin ($B^*_\theta$): A sector of the compass (e.g., 8-way partition).
   • Distance Bin ($B^*_r$): A discrete ring of distance (e.g., 0–500m, 500–2000m).

3. Hybrid Retrieval: The retrieval system receives a triplet $z = (a^*, B^*_\theta, B^*_r)$ instead of coordinates. The retrieval process treats the user's location as an uncertainty region $U(z)$ defined by the anchor and bins.

   • Spatial Scoring: To retrieve relevant Points of Interest (POIs), the system approximates the probability of a POI satisfying the query constraints by sampling $K$ latent user locations within $U(z)$ using Monte Carlo approximation.
   • Hybrid Ranking: The final score combines semantic relevance (via dense vector retrieval) and spatial relevance (via the Monte Carlo approximation) using a weighted sum.

Key Contributions

• First Privacy Mechanism for Spatial RAG: This work represents the first attempt to specifically address location privacy within the Spatial RAG paradigm, moving beyond generic geo-indistinguishability.
• Structured Privacy Representation: PAS introduces a novel "anchor-relative" encoding that aligns with corpus indexing strategies. By anchoring noise to semantically meaningful locations, it prevents the generation of unrealistic, unhelpful perturbed points common in continuous noise mechanisms.
• Formal Privacy Guarantees: The mechanism satisfies $\epsilon$-geo-DP (geo-indistinguishability) over the set of public anchors, providing a coarse but provable security guarantee.
• Empirical Analysis of Non-Monotonicity: The paper provides empirical evidence that PAS exhibits a non-monotonic privacy-utility relationship. Unlike continuous noise mechanisms where increasing privacy (lower $\epsilon$) consistently degrades utility, PAS shows that increasing $\epsilon$ does not always linearly improve utility due to geometric biases introduced by anchor discretization.

Experimental Results

The authors evaluated PAS on a synthetic urban dataset based on New York City, comprising 1,010 POIs and 423 queries, using various retrievers (MiniLM, bge-base) and generators (Meta-Llama-3.3-70B, Gemma-3, GPT-oss).

• Privacy Performance: PAS achieves strong location obfuscation, resulting in an Adversarial Localization Error (ALE) of approximately 370–400 meters, effectively masking the user's location to a neighborhood level.
• Retrieval Utility: While privacy is achieved, there is a measurable cost. Retrieval performance (Recall@k and nDCG@k) drops to approximately 50–60% of the non-private baseline. However, the degradation is gradual rather than catastrophic, and the system retains the relative ordering of relevant documents.
• Generation Quality: Crucially, the downstream generation quality remains robust. Despite the drop in retrieval precision, F1 scores and Citation Correctness remain comparable to the baseline. In some configurations, F1 scores even slightly improved, suggesting that the "noise" in PAS may act as a regularizer, preventing overfitting to precise spatial cues and forcing reliance on semantic signals.
• Model Robustness: Larger instruction-tuned models (e.g., Llama-3.3-70B) demonstrated a superior ability to compensate for imperfect spatial retrieval compared to smaller models.

Significance and Claims

The paper claims that structured spatial representations offer a practical path forward for privacy in location-based reasoning. The core insight is that retrieval in RAG systems does not strictly require exact coordinates but rather semantic proximity. By decoupling the user's exact location from the query through anchor-based substitution, PAS enables:

1. Coarse Provable Security: Achieving formal privacy guarantees without the utility collapse associated with traditional noise injection.
2. Practical Viability: Maintaining sufficient retrieval signals (over 50% retention) and stable generation quality to support real-world applications like tourism guides and emergency response systems.
3. Paradigm Shift: Moving away from "hiding" location via noise toward "abstracting" location via semantic anchors, which is better aligned with how LLMs reason about space.

The authors acknowledge limitations, including the geometric bias inherent in anchor discretization, the computational overhead of Monte Carlo sampling, and the reliance on synthetic data. However, they conclude that PAS provides the necessary ingredients for building privacy-preserving Spatial RAG systems where strong privacy guarantees can coexist with functional downstream tasks.