PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval

Truong Son Nguyen; Daniel Blackley; Ni Trieu; Evgenios M. Kornaropoulos

cs.AISep 28, 2026

PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval

Authors: Truong Son Nguyen, Daniel Blackley, Ni Trieu, Evgenios M. Kornaropoulos

Organizations: Arizona State University · Department of Computer Science Arizona State University Tempe, AZ 85281, USA · George Mason University · Department of Computer Science George Mason University Fairfax, VA 22030, USA

Abstract

Retrieval-augmented generation (RAG) hands the user's query to whoever hosts the corpus. We propose PILLAR, a Privacy-Preserving RAG (PPRAG) system based on Private Information Retrieval (PIR) in which a client utilizes the k documents most similar to their query from a server-held and publicly known corpus to respond to their query, while the server learns nothing about the query, either its terms or its access pattern. Prior PPRAG constructions rely on dense retrieval alone, translating approximate nearest-neighbor search into many query-dependent rounds of PIR, and pay for it in both latency and retrieval quality. PILLAR instead performs private hybrid retrieval in two stages. A sparse stage issues a small, fixed number of PIR queries against a carefully designed index of precomputed BM25 scores, filtering the corpus down to candidates that share terms with the query without the server ever seeing which terms these are. A dense stage then fetches only those candidates' document embeddings and re-ranks them locally, avoiding the many costly PIR queries that private dense retrieval typically requires. We instantiate PILLAR with two protocols that trade latency against retrieval quality, each built on a different private rendering of lexical search. PILLAR-Bin bins posting lists into a hash table and is a single-round design that achieves lower latency than state-of-the-art private retrieval schemes. PILLAR-Tree turns block-max pruning into an oblivious tree traversal combined with cuckoo hash tables and achieves the highest retrieval quality at lower latency than state-of-the-art schemes.

Figures & tables

Figure 1: Pareto between a state-of-the-art private dense retrieval method PACMANN, and our private hybrid retrieval methods ( PILLAR-Bin & PILLAR-Tree ). In MS MARCO, our PILLAR-Tree (in orange) dominates across all quality metrics, while our PILLAR-Bin (in green) dominates in speed/latency.

Panel of Figure 2 — Figure 2: Three-stage PILLAR-Tree protocol illustration. The interaction are all private under PIR.

PILLAR-Bin
Param.	Meaning
$R$	Hash table size
$t$	# Documents per bin
$\textsf{DB}_{emb}$	Retrieve embeddings directly or use two PIR rounds
PILLAR-Tree
$r$	Branching factor of the tree

Table 1: The parameter grid searched for each protocol. Every combination was run on both SciFact and MS MARCO.

Panel of Figure 3 — Figure 3: Retrieval quality (MRR@10, Recall@10) and answer quality (Answer Relevancy, Faithfulness) (Y-axis, higher is better) against per-query WAN latency (X-axis, lower is better) for the five selected configurations of each protocol. The black line is the Pareto frontier, which highlights the best configurations. Configurations not on the Pareto frontier are slightly transparent.

Panel of Figure 4 — Figure 4: Left: Two PILLAR-Bin ablation plots, total communication cost per query against the size of the hash table (log scale), and retrieval quality against documents stored in a bin (log scale). Right: per-query latency of the five selected PILLAR-Tree configurations (C1-C5) (defined in Section 5.1 and Table 3 lists their specific parameters) by the 3 stages defined in Section 4.2 .

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Definition
$\mathcal{C}$	The corpus
$\mathcal{V}$	Set of all unique terms in $\mathcal{C}$
$d$	Embedding vector dimension
$D$	Documents in $\mathcal{C}$
$e_{D}$	Embedding vector of document $D$
$Q$	Client query

Appendix

Table 2: Definition of variables used in the paper

Dataset	Config	$B$	$r$	$q^{\star}$	$W$	$s$	$k_{s}$	Tuning		Test		PIR calls / query
								MRR@10	Recall@10	MRR@10	Recall@10	PIR calls / query
MS MARCO	C1	64	128	2	50	16	32	0.1833	0.3055	0.1962	0.3426	472
	C2	64	128	4	50	16	64	0.2833	0.4880	0.3190	0.5751	944
	C3	16	128	8	400	8	256	0.3218	0.5639	0.3551	0.6573	13616
	C4	64	128	8	400	4	256	0.3211	0.5649	0.3549	0.6631	13216
	C5	16	8	8	400	16	256	0.3213	0.5625	0.3556	0.6580	28352

Appendix

Table 3: Dense-only configurations selected from the plaintext parameter search. C1 has the lowest padded PIR cost, C2 is the effectiveness–cost knee, C3 has the highest tuning MRR@10, C4 has the highest tuning Recall@10, and C5 has the highest padded PIR cost. Tuning results use 6,980 MS MARCO queries and 300 SciFact queries; test results use 1,500 MS MARCO queries and 75 held-out SciFact queries. Bold metric values are column maxima within each dataset, while bold PIR costs are column minima. PIR-query counts assume constant-work padding and include two Cuckoo calls for every Stage 1 and Stage 2 lookup and one query for each retrieved embedding row. They count primitive PIR queries rather than network round trips after batching.

Figure 5: Effectiveness-PIR-cost trade-off over the complete plaintext grid. Blue marks are all tested configurations and circles are configurations nondominated in MRR@10, Recall@10, and padded PIR calls. The solid curve is the upper envelope

\mathcal{P}_{E}

, C1,C2,C3,C4,C5 are chosen configurations.

Dataset	Config	bs	dpb	MRR@10	Recall@10	WAN time / query (s)
MS MARCO	C1	$10^{6}$	250	0.145	0.2337	0.098
	C2	$10^{6}$	1500	0.2067	0.3474	0.334
	C3	$10^{6}$	2000	0.2160	0.3635	0.429
	C4	$10^{6}$	2500	0.2219	0.3739	0.523
	C5	$10^{6}$	1000	0.1925	0.3192	0.239
SciFact	C1	$10^{6}$	50	0.5607	0.6781	0.065

Appendix

Table 4: Bins configurations selected from the plaintext parameter search.

Dataset	Config	bs	dpb	MRR@10	Recall@10	WAN time / query (s)
MS MARCO	C1	5	48	0.1892	0.3306	0.293
	C2	15	40	0.2802	0.4955	0.853
	C3	20	48	0.2990	0.5275	1.157
	C4	30	48	0.3073	0.5422	1.727
	C5	25	48	0.3057	0.5397	1.442
SciFact	C1	5	40	0.6304	0.8104	0.270

Appendix

Table 5: PACMANN configurations selected from the plaintext parameter search.

Panel of Figure 6 — Figure 6: MRR@10 and Recall@10 against per-query WAN latency, LAN latency, and computation time. Highlighted points lie on the global Pareto frontier across all three methods.

Panel of Figure 7 — Figure 7: MRR@10 and Recall@10 against one-time PIR preprocessing time, per-query data sent, and one-time client storage. Highlighted points lie on the global Pareto frontier across all three methods.

Figure 8: PILLAR-Bin per-query cost. Left: varying the hash table size. Right: varying the number of documents per bin.

Figure 9: PILLAR-Bin worst-case client storage. Left: varying the hash table size. Right: varying the number of documents per bin.

Figure 10: PILLAR-Bin PIR preprocessing time (top) and retrieval quality (bottom). Left: varying the hash table size. Right: varying the number of documents per bin.

Figure 11: PILLAR-Bin per-query cost when embeddings are stored in the bins (Single DB) or in a separate database (Separate Embedding DB), varying the number of documents per bin.

Explore similar work

Quantization Enables Private Dense Retrieval against Malicious Service Providers
Sep 28, 2026Louis Tremblay Thibault, Sofiane Azogagh, Marc-Olivier Killijian +1Retrieval Layer Privacy
École de technologie supérieure and Mila · Eurecom · Université du Québec à Montréal
Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings
Sep 3, 2026Peichun Hua, Yunming XiaoText Corpora Trees
The Chinese University of Hong Kong, Shenzhen · State Key Laboratory of Internet Architecture, Tsinghua University
GoldenRetriever: Non-Interactive Homomorphic Encrypted Retrieval for Privacy-Preserving RAG
Jul 31, 2026Yang Gao, Gang Quan, Scott Piersall +3Agentic Retrieval-Augmented Generation Systems Homomorphic Encryption
Department of Computer Science, University of Central Florida, Orlando, FL, USA · Electrical and Computer Engineering Department, Florida International University, Miami, FL, USA · College of Design, Construction and Planning, University of Florida, Gainesville, FL, USA

Sep 28, 2026, cs.CRJ/K move · Enter open · S save

Quantization Enables Private Dense Retrieval against Malicious Service Providers

Louis Tremblay Thibault, Sofiane Azogagh, Marc-Olivier Killijian, Ulrich Aïvodji

École de technologie supérieure and Mila · Eurecom · Université du Québec à Montréal

Retrieval Layer Privacy Text Corpora Malicious Agents

Open paper AskPDF arXiv

Dense retrieval, the key component of Retrieval Augmented Generation (RAG), retrieves the most relevant documents by comparing dense vector representations of queries and passages from a large corpus. In privacy-sensitive applications, the server observes the query and controls which evidence is returned, creating both confidentiality and integrity risks. We formulate private dense retrieval as providing query privacy and retrieval integrity against a malicious server, and develop a two-round cryptographic protocol that provides both guarantees. Our protocol reduces private and verifiable retrieval to multiplication of a committed matrix by an encrypted vector and uses low-bit quantization to make this computation practical. We evaluate the resulting trade-off between cryptographic cost, retrieval quality, and downstream RAG accuracy across six embedding models, four language models, and corpora of up to 2.68 million passages. Our results show that, with a clipped quantizer, three-bit quantization largely preserves retrieval quality and downstream accuracy, while a private query over a corpus the size of a clinical reference requires one to three minutes of server time. These results suggest that private dense retrieval is already practical for moderately sized, privacy-sensitive corpora when minute-scale latency is acceptable.

Abstract

Explore similar work

Quantization Enables Private Dense Retrieval against Malicious Service Providers

Spruce: Scalable Private Outsourced Retrieval Using Compact Embeddings

GoldenRetriever: Non-Interactive Homomorphic Encrypted Retrieval for Privacy-Preserving RAG