PILLAR：面向增强检索的私有倒排索引词法查找

# PILLAR: Private Inverted-index Lexical Lookup for Augmented Retrieval
Source: [https://arxiv.org/html/2609.36326](https://arxiv.org/html/2609.36326)
Truong Son Nguyen††thanks:Equal contributionAffiliation:Department of Computer ScienceAffiliation:Arizona State UniversityAffiliation:Tempe, AZ 85281, USAEmail:[snguye63@asu\.edu](mailto:)Daniel Blackley11footnotemark:1Affiliation:Department of Computer ScienceAffiliation:George Mason UniversityAffiliation:Fairfax, VA 22030, USAEmail:[dblackle@gmu\.edu](mailto:)Ni TrieuAffiliation:Department of Computer ScienceAffiliation:Arizona State UniversityAffiliation:Tempe, AZ 85281, USAEmail:[nitrieu@asu\.edu](mailto:)Evgenios M\. KornaropoulosAffiliation:Department of Computer ScienceAffiliation:George Mason UniversityAffiliation:Fairfax, VA 22030, USAEmail:[evgenios@gmu\.edu](mailto:)

###### Abstract

Retrieval\-augmented generation \(RAG\) hands the user’s query to whoever hosts the corpus\. We proposePILLAR, a Privacy\-Preserving RAG \(PPRAG\) system based on Private Information Retrieval \(PIR\) in which a client utilizes thekkdocuments 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\.PILLARinstead 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 instantiatePILLARwith two protocols that trade latency against retrieval quality, each built on a different private rendering of lexical search\.PILLAR\-Binbins 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\-Treeturns 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\.

## 1Introduction

Retrieval\-augmented generation \(RAG\) is now the standard way to ground a Large Language Model \(LLM\) in knowledge that is not in its parameters\([Lewis et al\., 2020](https://arxiv.org/html/2609.36326#bib.bib21);[Gao et al\., 2023](https://arxiv.org/html/2609.36326#bib.bib22)\), and it is the mechanism major search engines rely on for AI summaries\. A RAG pipeline consists of a client that issues a query, a server that hosts a document corpus, and an LLM that generates an answer to the client’s query by retrieving documents from the server to augment its generated response\. This poses a severe privacy risk, the query is handed, verbatim, to the server\. Exposing a client’s query carries real risk; search engine logs can trivially be used to identify clients\([Barbaro and Jr\., 2006](https://arxiv.org/html/2609.36326#bib.bib38)\), clients disclose sensitive personal details to LLMs\([Mireshghallah et al\., 2024](https://arxiv.org/html/2609.36326#bib.bib39)\), and current models infer identifiable information from very little text\([Staab et al\., 2024](https://arxiv.org/html/2609.36326#bib.bib40)\)\.

Privacy\-Preserving RAG\.A privacy\-preserving RAG \(PPRAG\) protocol answers a client’s query over a public corpus such that the server hosting the corpus learns nothing about the query\. Due to the public nature of the corpus, such protocols are typically built on Private Information Retrieval \(PIR\)\([Chor et al\., 1995](https://arxiv.org/html/2609.36326#bib.bib5)\), a cryptographic primitive that lets a client fetch a non\-encrypted item from a server without revealing which item was fetched\. Existing PPRAG work falls into two categories,*dense*and*sparse*retrieval, with the majority focusing on the former\.

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, ourPILLAR\-Tree\(in orange\) dominates across all quality metrics, while ourPILLAR\-Bin\(in green\) dominates in speed/latency\.Among dense retrieval protocols, Tiptoe\([Henzinger et al\., 2023](https://arxiv.org/html/2609.36326#bib.bib3)\)privately searches over clustered embeddings, Compass\([Zhu et al\., 2025](https://arxiv.org/html/2609.36326#bib.bib25)\)traverses an HNSW graph using Oblivious RAM \(ORAM\), and PACMANN\([Zhou et al\., 2024b](https://arxiv.org/html/2609.36326#bib.bib1)\), the current state\-of\-the\-art \(SOTA\), has the client traverse an approximate nearest neighbor \(ANN\) graph\. Sparse retrieval, by contrast, is represented by Coeus\([Ahmad et al\., 2021](https://arxiv.org/html/2609.36326#bib.bib23)\), which scores the query against a term\-frequency matrix\.

Limitations of Existing PPRAG\.Existing PPRAG protocols face two limitations: First, ANN traversal is adaptive; each hop depends on the query, and the walk terminates once no closer neighbors are found\. Hiding the access pattern therefore requires a fixed, query\-independent schedule\. On MS MARCO, PACMANN requires2020round trips per query yet achieves only0\.2660\.266MRR@10, compared to roughly0\.310\.31for a non\-private ANN baseline over identical embeddings[Zhou et al\. \(2024b\)](https://arxiv.org/html/2609.36326#bib.bib1)\. Second, existing protocols support only a single retrieval architecture, whereas*real RAG deployments*commonly use hybrid architectures, with lexical scoring followed by comparing learned embedding similarities \(See Appendix[I\.2](https://arxiv.org/html/2609.36326#A9.SS2)for more details\)\. The two architectures fail in complementary ways: learned embeddings encode word meanings using their training data but fail when a query uses the same word in a different context, while lexical scoring does not consider semantically relevant words\([Ma et al\., 2021](https://arxiv.org/html/2609.36326#bib.bib41);[Thakur et al\., 2021a](https://arxiv.org/html/2609.36326#bib.bib42);[Bruch et al\., 2023](https://arxiv.org/html/2609.36326#bib.bib43)\)\. Used together, the methods mitigate each other’s weaknesses\. This points to a gap in PPRAG literature:

> *No PPRAG uses both sparse and dense retrieval architectures, and the single\-architecture alternatives pay for it in number of interactions and in answer quality\.*

Contributions\.We presentPILLAR, a new*hybrid\-retrieval*111In standard literature, a “hybrid\-retrieval RAG protocol” refers to a protocol that combines the scores from both dense and sparse retrieval; here hybrid\-retrieval refers strictly to the retrieval methods, not the final scorePPRAG architecture that retains the strengths while limiting the weaknesses of previous dense or sparse PPRAG protocols\.PILLARachieves a "best\-of\-both\-worlds" design, and we demonstrate its effectiveness with two new PPRAG protocols:PILLAR\-BinandPILLAR\-Tree\.PILLAR\-Binuses lexical scoring functions to resolve a query in a*single*round, achieving low latency\.PILLAR\-Treeadapts block\-max BM25[Broder et al\. \(2003\)](https://arxiv.org/html/2609.36326#bib.bib18);[Ding and Suel \(2011\)](https://arxiv.org/html/2609.36326#bib.bib19)to perform multiple rounds of increasingly accurate retrievals, achieving unmatched quality compared to SOTA\. We evaluate both the quality of the answer and latency forPILLAR\-Bin,PILLAR\-Tree, and the SOTA PACMANN, and provide an extensive evaluation in Section[5](https://arxiv.org/html/2609.36326#S5)and Appendix[D\.1](https://arxiv.org/html/2609.36326#A4.SS1)\. An indicative result is in Figure[1](https://arxiv.org/html/2609.36326#S1.F1), which shows the*Pareto frontier*over the Top\-5 configurations for each method\. Specifically, it captures the trade\-offs between the latency required to retrieve documents for a query \(X\-axis\) and the Relevancy of an LLM\-generated answer to that query, augmented with those documents \(Y\-axis\)\. The*only configurations*on the frontier belong to eitherPILLAR\-BinorPILLAR\-Tree, never once is PACMANN better in either latency or Relevancy\. In summary, our core contributions are as follows:

- •Hybrid Retrieval Under PIR\.We give the first PPRAG protocols that combine lexical and semantic scoring, and prove that bothPILLAR\-BinandPILLAR\-Treehide a client’s query from a semi\-honest server in the PIR\-hybrid model\.
- •Comprehensive Evaluation\.We benchmark both protocols against the SOTA, PACMANN, and plot the best configurations of all three protocols using a*Pareto frontier*in Section[5\.2](https://arxiv.org/html/2609.36326#S5.SS2), finding thatPILLARaccounts for93%93\\%of the configurations on the frontier\. We test on two standard RAG datasets, MS MARCO[Bajaj et al\. \(2018\)](https://arxiv.org/html/2609.36326#bib.bib45)and SciFact[Wadden et al\. \(2020\)](https://arxiv.org/html/2609.36326#bib.bib12), reporting retrieval quality, communication cost, and latency\. All code forPILLAR\-Binis available at[https://github\.com/dkblackley/bi\.\.\.](https://github.com/dkblackley/bi...)Unlike PACMANN, which evaluates retrieval alone, we also evaluate the end\-to\-end answers generated from the retrieved documents, using the Retrieval Augmented Generation Assessment metrics*faithfulness*and*answer relevancy*[Es et al\. \(2025\)](https://arxiv.org/html/2609.36326#bib.bib26)\.
- •A Low\-Latency PPRAG Protocol\.The fastest PACMANN configuration needs0\.2930\.293s, whilePILLAR\-Binretrieves documents in as little as0\.0980\.098s on MS MARCO, with comparable quality\.
- •A High\-Quality PPRAG Protocol\.The highest quality documents across the best configurations are retrieved byPILLAR\-Tree, with answer Relevancy0\.750\.75\. The PACMANN configuration that finds the best documents achieves0\.720\.72answer relevancy but requires over2×2\\timesmore latency\.

## 2Background & Preliminaries

Notation\.A*corpus*𝒞=\{D1,…,Dn\}\\mathcal\{C\}=\\\{D\_\{1\},\\dots,D\_\{n\}\\\}is an ordered set ofnndocuments\. The indexiiof a documentDi∈𝒞D\_\{i\}\\in\\mathcal\{C\}is also referred to as a document’s*identifier*\. An*analyzer*𝖠𝗇𝖺𝗅𝗒𝗓𝖾\\mathsf\{Analyze\}maps raw text to a finite sequence of tokens called*terms*\. The*vocabulary*𝒱=⋃D∈𝒞𝖠𝗇𝖺𝗅𝗒𝗓𝖾⁡\(D\)\\mathcal\{V\}=\\bigcup\_\{D\\in\\mathcal\{C\}\}\\mathsf\{Analyze\}\(D\)is the set of all unique terms in a corpus\. An*embedding function*𝖤𝗆𝖻\\mathsf\{Emb\}maps raw text to add\-dimensional dense vector\. With the term*document embedding*eD=𝖤𝗆𝖻⁡\(D\)∈ℝde\_\{D\}=\\mathsf\{Emb\}\(D\)\\in\\mathbb\{R\}^\{d\}, we refer to a document’s dense vector representation\. A*query*QQis raw text supplied by a client, so that𝖠𝗇𝖺𝗅𝗒𝗓𝖾⁡\(Q\)=\(w1,…,w\|Q\|\)\\mathsf\{Analyze\}\(Q\)=\(w\_\{1\},\\dots,w\_\{\|Q\|\}\)are its*query terms*andeQ=𝖤𝗆𝖻⁡\(Q\)∈ℝde\_\{Q\}=\\mathsf\{Emb\}\(Q\)\\in\\mathbb\{R\}^\{d\}its*query embedding*\. We sometimes abuse the notationQQto denote both a sequence of terms and the index of documents to be returned through PIR\. We make this distinction clear by referring to the latter case as the*PIR query*\.

Private Information Retrieval \(PIR\)\.There are multiple variants of PIR[Chor et al\. \(1995\)](https://arxiv.org/html/2609.36326#bib.bib5);[Kushilevitz and Ostrovsky \(1997\)](https://arxiv.org/html/2609.36326#bib.bib7);[Beimel et al\. \(2000\)](https://arxiv.org/html/2609.36326#bib.bib10)but we focus on Single\-server PIR with preprocessing designs[Zhou et al\. \(2024a\)](https://arxiv.org/html/2609.36326#bib.bib46);[Corrigan\-Gibbs and Kogan \(2020\)](https://arxiv.org/html/2609.36326#bib.bib14);[Beimel et al\. \(2000\)](https://arxiv.org/html/2609.36326#bib.bib10)\. These PIR protocols involve interactions between a stateful clientclntand a serversrv, consisting of a \(ii\) preprocessing phase followed by a \(i​iii\) query phase\. In the PIR preprocessing phase,srv’s input is a publicly known𝒞\\mathcal\{C\}, which it sends toclnt, who initializes a private state\. During the query phase,clnt’s input is an index0≤i≤\|𝒞\|0\\leq i\\leq\|\\mathcal\{C\}\|\(w\.r\.t\. to𝒞\\mathcal\{C\}\) and constructs a PIR queryQQto retrieve the requested documentDi∈𝒞D\_\{i\}\\in\\mathcal\{C\}\.clntsendsQQtosrvandclntuses the responses fromsrvand his internal state to outputDiD\_\{i\}\. A PIR protocol is*secure*ifsrvdoes not discover anything about the client’s input for the requested indexii\. Consistent with prior work[Henzinger et al\. \(2023\)](https://arxiv.org/html/2609.36326#bib.bib3);[Zhou et al\. \(2024b\)](https://arxiv.org/html/2609.36326#bib.bib1), we consider a semi\-honestsrv, wheresrvfollows the protocol but tries to recoverii\.

Privacy\-Preserving Retrieval Augmented Generation \(𝖯𝖯𝖱𝖠𝖦\\mathsf\{PPRAG\}\) Functionality\.A standard PIR protocol is incompatible with PPRAG because aclnttakes query termsQQas input rather than an indexii, and outputs the documents most similar toQQrather than the single document at indexii, where similarity is measured by a functionscore​\(⋅,⋅\)\\textsf\{score\}\(\\cdot,\\cdot\)mapping a \(query, document\) pair to a score under some metric\. For the cryptographic formalism, we consider the ideal two\-party𝖯𝖯𝖱𝖠𝖦\\mathsf\{PPRAG\}functionality, where the server and client both have input, but only the client has output, defined by𝖯𝖯𝖱𝖠𝖦⁡\(𝒞,Q\)=\(⊥,𝒟k\)\\mathsf\{PPRAG\}\(\\mathcal\{C\},Q\)\\;=\\;\\bigl\(\\,\\bot,\\mathcal\{D\}^\{k\}\\bigr\)\. In words:srvtakes in a public corpus𝒞\\mathcal\{C\}and outputs nothing \(denoted⊥\\bot\),clnttakes as input a privateQQand outputskkdocuments𝒟k⊆𝒞\\mathcal\{D\}^\{k\}\\subseteq\\mathcal\{C\}such that, for everyD∈𝒟kD\\in\\mathcal\{D\}^\{k\}, and everyD′∈𝒞∖𝒟kD^\{\\prime\}\\in\\mathcal\{C\}\\setminus\\mathcal\{D\}^\{k\}we have that:score​\(Q,D\)≥score​\(Q,D′\)\\textsf\{score\}\(Q,D\)\\;\\geq\\;\\textsf\{score\}\(Q,D^\{\\prime\}\)\. The new protocolPILLARin this work realizes this ideal functionality of𝖯𝖯𝖱𝖠𝖦\\mathsf\{PPRAG\}\.

## 3Challenges of PIR under RAG Architecture

This section discusses sparse and dense retrieval architectures for RAG with a public corpus, with particular attention to the challenges that arise when scaling each to a PIR\-based*private analog*\.

### 3\.1Sparse Retrieval and Privacy\.

At a high level,*sparse retrieval*scores each document \(via lexical scoring functions\) by the query terms appearing in it verbatim, weighting rare terms more heavily than common ones, and returns thekkhighest\-scoring documents\. Some well\-known lexical scoring functions are TF\-IDF[Robertson and Zaragoza \(2009\)](https://arxiv.org/html/2609.36326#bib.bib17), Okapi BM25[Robertson and Zaragoza \(2009\)](https://arxiv.org/html/2609.36326#bib.bib17), and SPLADE[Formal et al\. \(2021\)](https://arxiv.org/html/2609.36326#bib.bib20)\. Specifically, each score computed for a termw∈𝒱w\\in\\mathcal\{V\}in the documentDDis a function of the frequency ofwwinDD\. To facilitate this, each document is modeled as a vectorvvover𝒱\\mathcal\{V\}whose entry for a term is nonzero only if the document contains that𝒱\\mathcal\{V\}term \(hence*sparse*, since a document uses only a small fraction of the vocabulary\)\. Scoring a*single*DDagainstQQthus amounts to looking upvDv\_\{D\}’s entries at the coordinates named by the query’s terms and summing them, i\.e\., a small set of index lookups on vectorvDv\_\{D\}, where the indices are exactly the sensitive input/query\. The following exposition describes techniques without privacy in mind \(thus, the indices are visible to the server\)\.

Inverted Indexes\.An end\-to\-end PPRAG query under sparse retrieval requiressrvto scoreQQagainst*every*D∈𝒞D\\in\\mathcal\{C\}and return only thekkhighest\-lexical\-scoring documents\. Computing the lexical score for every document is wasteful since many documents typically won’t contain any terms in the query and will always score00\. A common way to filter out these documents is to organize documents using an abstract data type called an*inverted index*\. Inverted indexes are dictionaries that map each termw∈𝒱w\\in\\mathcal\{V\}to the set of documents in whichwwoccurs, called the*posting list*\. Retrieval protocols built on an inverted index avoid this exhaustive scan:srvuses the inverted index to fetch the posting list for eachw∈Qw\\in Qand scoresQQagainst*only the relevant documents*that reside in the posting lists\. We discuss two methods for instantiating an inverted index in this context: bin\-based and block\-based\.

Bin\-based BM25\.An inverted index can be instantiated as a*hash table*, where each hash table bin stores the posting list for each hashed term\. We refer to this simple approach as*bin\-based BM25\.*At query time,srvhashes eachw∈Qw\\in Qto a bin, fetches the posting lists stored there, scores the documents they contain, and returns thekkhighest\-scoring ones toclnt\. Thechallengesof applying PIR on top of a bin\-based BM25 are:1In non\-privacy\-preserving bin\-based BM25, theclntreceives the top\-kkdocuments thatsrvlocally filtered across posting lists; however, in a PPRAG rendition, the server does not seeQQ, thus, it cannot perform this task\.2In non\-privacy\-preserving bin\-based BM25, to minimize collisions we need a large hash table; however, PIR computation complexity scales superlinearly with the size of the hash table\. This introduces a trade\-off: a large hash table yields fewer posting lists \(i\.e\., less filtering\) but increases PIR complexity, while a small hash table yields more posting lists \(i\.e\., more filtering\) with faster PIR complexity\.

Block\-based BM25[Ding and Suel \(2011\)](https://arxiv.org/html/2609.36326#bib.bib19)\.In a typical RAG deployment,clntsendsQQtosrvand receives only thekkmost similar documents in𝒞\\mathcal\{C\}w\.r\.t\.QQ\. To speed up this search,srvcan*efficiently dismiss*documents that cannot reach the top\-kk\. We now discuss one such strategy built on the inverted index,*Dynamic Pruning*[Turtle and Flood \(1995\)](https://arxiv.org/html/2609.36326#bib.bib11);[Broder et al\. \(2003\)](https://arxiv.org/html/2609.36326#bib.bib18)\. The underlying intuition is as follows\. Recall that a document’sDDscore is the sum ofDD’s per\-term contributions over the query terms, so for a “batch”ℬ⊆𝒞\\mathcal\{B\}\\subseteq\\mathcal\{C\}of documents, taking the single largest contribution of eachw∈Qw\\in Q*across all*documents inℬ\\mathcal\{B\}and summing222Note that no document inℬ\\mathcal\{B\}need actually attain this bound, since the per\-term maxima may come from different documents, e\.g\.,D3D\_\{3\}forq1q\_\{1\}, say, andD9D\_\{9\}forq2q\_\{2\}\.these maxima provides an upper bound for the exact score of*every*document inℬ\\mathcal\{B\}\. If this over\-approximation falls below the current top\-kkexact score, the entire batch can be skipped without scoring any of its documents individually\. Dynamic Pruning realizes this idea as follows: At initialization,srvpartitions all documents into*blocks*where each one contains a fixed number of documents\. For each blockℬ\\mathcal\{B\}and termww,srvprecomputesσw​\(ℬ\)\\sigma\_\{w\}\(\\mathcal\{B\}\), the largest score betweenwwand any document inℬ\\mathcal\{B\}\(thus,\|𝒱\|\|\\mathcal\{V\}\|scores per block\)\. At query time,srvretrieves the blocks for eachw∈Qw\\in Qand scores the firstkkdocuments arbitrarily to establish a baseline threshold\. It then proceeds block by block: since no document inℬ\\mathcal\{B\}can score higher than∑w∈Qσw​\(ℬ\)\\sum\_\{w\\in Q\}\\sigma\_\{w\}\(\\mathcal\{B\}\), a bound below thekkth best exact score seen so far rules out the whole block, which is skipped, unscored\. Blocks clearing the threshold are scored in full and the running top\-kkupdated\. Once all blocks are traversed,srvreturns the final top\-kk; we refer to this as*Block\-based BM25*\.

Applying PIR to this procedure is challenging:1The algorithm attempts to find the top scoring documents but, given the lack of organization among blocks, the server needs to linearly scan all blocks to identify the right ones\.2In non\-private Block\-based BM25,srvtracks thekkth best score seen so far, a threshold that is*query\-dependent*\. Under PPRAG,srvnever sees \(sensitive\)QQand therefore*cannot compute*this threshold, let alone decide which blocks it prunes\.

### 3\.2Dense Retrieval and Privacy\.

Whereas sparse retrieval matches on exact term overlap, dense retrieval matches on*meaning*, so a document can rank highly without sharing a single word with the query\. Dense retrieval maps documents and queries into a shared vector space in which semantically similar texts lie close together[Karpukhin et al\. \(2020\)](https://arxiv.org/html/2609.36326#bib.bib4);[Murphy \(2013\)](https://arxiv.org/html/2609.36326#bib.bib44)\. A popular measure of closeness is cosine similarity: given a query embedding𝐞Q∈ℝd\\mathbf\{e\}\_\{Q\}\\in\\mathbb\{R\}^\{d\}and a document embedding𝐞D∈ℝd\\mathbf\{e\}\_\{D\}\\in\\mathbb\{R\}^\{d\}, we computecos⁡\(𝐞Q,𝐞D\)=\(𝐞Q⋅𝐞D\)/\(‖𝐞Q‖​‖𝐞D‖\)\\cos\(\\mathbf\{e\}\_\{Q\},\\mathbf\{e\}\_\{D\}\)=\(\\mathbf\{e\}\_\{Q\}\\cdot\\mathbf\{e\}\_\{D\}\)/\(\\\|\\mathbf\{e\}\_\{Q\}\\\|\\\|\\mathbf\{e\}\_\{D\}\\\|\)\.

Approximate Nearest Neighbor Search\.In a typical dense RAG deployment,clntsends its query embedding𝐞Q\\mathbf\{e\}\_\{Q\}tosrv, which computes the cosine similarity against every document embedding and returns thekkclosest\. This is exactlykk\-Nearest Neighbor \(NN\) search[Har\-Peled et al\. \(1998\)](https://arxiv.org/html/2609.36326#bib.bib13), at a cost ofO⁡\(\|𝒞\|​d\)O\(\|\\mathcal\{C\}\|d\)per query\. The common alternative is*Approximate*Nearest Neighbor \(ANN\) search[Karpukhin et al\. \(2020\)](https://arxiv.org/html/2609.36326#bib.bib4);[Zhou et al\. \(2024b\)](https://arxiv.org/html/2609.36326#bib.bib1), which in one popular form[Zhou et al\. \(2024b\)](https://arxiv.org/html/2609.36326#bib.bib1)represents𝒞\\mathcal\{C\}as a graph333This converts a high\-dimensional geometric search into a combinatorial one, with the geometry encoded into the edge set rather than evaluated at query time\.whose nodes are documents and whose edges join embeddings of high cosine similarity, reducing retrieval to a traversal toward increasingly similar documents rather than a full scan\. Dense retrieval poses its own challenges under PIR:1The graph traversal is*query\-dependent*: from an arbitrary starting node,srvscores𝐞Q\\mathbf\{e\}\_\{Q\}against the current node’s neighbors and moves to the closest one, so which node is accessed at each step is determined by the query\. Revealing this access pattern would*leak information*about𝐞Q\\mathbf\{e\}\_\{Q\}\.2The number of traversal steps also varies with the query, since the search halts once it stops finding closer neighbors\. This count is itself a function of𝐞Q\\mathbf\{e\}\_\{Q\}, so revealing it would*leak information*about the query\. A PPRAG\-friendly ANN must therefore fix the step count in advance, trading retrieval accuracy against cost on every query\.

Properties of a Hybrid Retrieval Protocol\.Sparse and dense retrieval succeed on complementary dimensions\. Sparse retrieval pinpoints domain\-specific terms that embeddings often fail to represent, while dense retrieval captures semantic relationships that exact lexical matching misses\. A hybrid PIR protocol should therefore combine both, inheritingAthe low,*fixed round complexity*of sparse search,Bsparse retrieval’s ability to*quickly dismiss documents*with no lexical overlap with the query, andCthe*semantic accuracy*of dense embeddings\.

## 4PILLAR:*PIR\-Friendly*Hybrid Retrieval

This section presents our protocolsPILLAR\-BinandPILLAR\-Tree, both of which realize𝖯𝖯𝖱𝖠𝖦\\mathsf\{PPRAG\}\. Their design follows directly from the three properties a hybrid architecture should have, stated at the end of Section[3](https://arxiv.org/html/2609.36326#S3)\. RegardingA, every adaptive component is removed\. The number of rounds and the size of every message depend only on publicly known parameters, never onQQ, so the communication pattern is fixed\. ForB, the crude part of sparse retrieval runs first on the server, and the refined filtering stage on the client\. Lexical scoring dismisses the bulk of𝒞\\mathcal\{C\}cheaply, leaving a small candidate set for the expensive stage\.CSemantic re\-ranking is moved completely toclnt\. After the sparse stage,clntfetches the candidates’ embeddings via PIR and ranks them locally, recovering the accuracy of dense retrieval withoutsrvever learningQQ\. We provide the full protocols for bothPILLAR\-Bin&PILLAR\-Treein Appendix[E](https://arxiv.org/html/2609.36326#A5)and the security analysis in Appendix[G](https://arxiv.org/html/2609.36326#A7)\.

### 4\.1A Simple Bin\-Based BM25

We discuss solutions for the two challenges identified for Bin\-based BM25 in Section[3\.1](https://arxiv.org/html/2609.36326#S3.SS1)\.

Solving Bin\-Based BM25 Challenges\.1Recall the first problem for Bin\-Based BM25 was that, in non\-privacy\-preserving Bin\-Based BM25,srvwould retrieve posting lists for each termw∈Qw\\in Qand score the documents in the posting lists, returning just the top\-kkhighest\-scoring documents\. Scoring documents requires access toQQ, whichsrvdoes not see in a PPRAG protocol\. To solve this,srvwill only return a fixed number ofttdocuments per query term toclnt, who can locally re\-rank without revealingQQ\. To ensure thettreturned documents are still relevant, we return documents from a posting list that is sorted by frequency of the hashed termw∈𝒱w\\in\\mathcal\{V\}used to retrieve the posting list, and thetthighest\-frequency documents are returned\. Empirical approaches for choosingttare explored in Section[5](https://arxiv.org/html/2609.36326#S5)\.2Recall the trade\-off: a large hash table keeps collisions rare but drives up PIR complexity, while a small one requires less PIR operations but conflates unrelated terms into the same bin\.PILLAR\-Binuses onlyR≪\|𝒞\|R\\ll\|\\mathcal\{C\}\|rows and maps each termwwto rowH⁡\(w\)\(modR\)H\(w\)\\pmod\{R\}under a public hash functionHH\. Thus,clntcan compute which row to request, and PIR hides that index fromsrv\.RRis also smaller than the vocabulary, so many terms share a row, and the postings lists of all colliding terms are merged into it\. Rows are truncated atttlength, so, crucially, the order of merging lists determines which documents survive truncation\. Naively appending lists would preserve the first list in full and cut off the last list entirely\.PILLAR\-Bintherefore*interleaves*lists in a round\-robin fashion, placing thejjth document of theiith list at position\(j−1\)​m\+i\(j\-1\)m\+iwhenmmterms collide\. Reading the firstt​mtmpositions then yields the topttdocuments from each colliding list\. Finally, thesrvomits duplicates when a document is contained in two colliding lists\.

Final Design Description\.At setup,srvcomputes the embedding𝐞D∈ℝd\\mathbf\{e\}\_\{D\}\\in\\mathbb\{R\}^\{d\}of everyD∈𝒞D\\in\\mathcal\{C\}and stores embeddings in place of documents, so thatclntcan re\-rank locally once retrieval completes, i\.e\., the dense retrieval part of the hybrid design\. It then builds the hash table as in non\-private bin\-based BM25 and applies the two designs above, i\.e\., hashing overRRrows and interleaving colliding postings lists round\-robin\. The result is a PIR database ofRRrows, each holding exactlyttembeddings \(after truncation\) and hencet⋅dt\\cdot dfield elements444Thus, all rows are indistinguishable in size regardless of how many terms collide in them\.\. Since a query contains several terms, retrieving one row per term with independent PIR queries would cost\|Q\|\|Q\|separate protocol executions; we instead use*batched PIR*, which packs multiple indices into a single query at sublinear amortized cost per index[Zhou et al\. \(2024b\)](https://arxiv.org/html/2609.36326#bib.bib1)\. The batch size is fixed to the padding bound of3rather than to\|Q\|\|Q\|, so the query length is identical across executions and leaks nothing about how many terms the client used\.clntissues one batched PIR query, decodes thettembeddings in each returned row, and aggregates them into a candidate pool𝒟cand\\mathcal\{D\}\_\{\\mathrm\{cand\}\}of at mosttttimes the batch size, discarding duplicates that arise when a document appears in several retrieved rows\. The entire protocol is a*single round*, and its message sizes depend onRR,tt,dd, and the batch bound\.

### 4\.2Tree\-based BM25 \(PILLAR\-Tree\)

This section discusses how to solve the previously identified challenges for block\-based BM25 in Section[3\.1](https://arxiv.org/html/2609.36326#S3.SS1)and provides the design principle forPILLAR\-Tree\.

Stage 1: Beam Search \(Tree\)rootleafAt each level, fetch children of topWWsuper\-blocks via PIR\.Keep top\-WWleaves \(beam frontier\)\.Stage 2: Sub\-block Score ComputationLeaf block A𝒮​ℬ1\\mathcal\{SB\}\_\{1\}𝒮​ℬ2\\mathcal\{SB\}\_\{2\}𝒮​ℬ3\\mathcal\{SB\}\_\{3\}✓𝒮​ℬ4\\mathcal\{SB\}\_\{4\}Leaf block B𝒮​ℬ5\\mathcal\{SB\}\_\{5\}𝒮​ℬ6\\mathcal\{SB\}\_\{6\}✓𝒮​ℬ7\\mathcal\{SB\}\_\{7\}𝒮​ℬ8\\mathcal\{SB\}\_\{8\}Fetch sub\-blockW⋅\|Q\|⋅⌈\|ℬ\|/s⌉W\\cdot\|Q\|\\cdot\\lceil\|\\mathcal\{B\}\|/s\\rceilrows via PIR\.Compute and Rank Sub\-block score locally to selectksk\_\{s\}promising sub\-blocks\.Stage 3: Client Local RankingSub\-block Document EmbeddingseD1e\_\{D\_\{1\}\}eD2e\_\{D\_\{2\}\}⋆\\stareD3e\_\{D\_\{3\}\}eD4e\_\{D\_\{4\}\}⋆\\stareD5e\_\{D\_\{5\}\}eD6e\_\{D\_\{6\}\}client:cos⁡\(𝐞Q,𝐞D\)\\cos\(\\mathbf\{e\}\_\{Q\},\\mathbf\{e\}\_\{D\}\)Output: top\-kkdoc IDsRetrieve embeddings via PIR;client ranks bycos⁡\(𝐞Q,𝐞D\)\\cos\(\\mathbf\{e\}\_\{Q\},\\mathbf\{e\}\_\{D\}\)and returns final top\-kkresults\.Top nodeRetrieved node \(beam\)Selected sub\-blockTop\-ranked document

Figure 2:Three\-stagePILLAR\-Treeprotocol illustration\. The interaction are all private under PIR\.Solving Block\-Based BM25 Challenges\.To resolve1, we organize the blocks recursively into a tree whose leaves are the individual blocks and whose internal nodes each represent a*super\-block*spanning the documents of all blocks in their subtree\. At every node we store an array of\|𝒱\|\|\\mathcal\{V\}\|entries, where theii\-th entry holds the maximum lexical score of termiiover all documents in that super\-block\. For full generality, we considerrr\-ary trees, i\.e\., branching factorrr, so as to reduce the height of the tree\. Next, we descend the tree with a*beam search*[Bisiani \(1987\)](https://arxiv.org/html/2609.36326#bib.bib2)of widthWW, confine the next level traversal to the children of the highest scoringWWnodes\. Since the previous level advances onlyWWsuper\-blocks \(and each super\-block hasrrchildren\), layeriiconsiders onlyW×rW\\times rcandidate super\-blocks\. For each candidate, the algorithm sums the upper bounds of the query terms inQQand retains theWWhighest\-scoring super\-blocks of the level\. It is worth noting that given that beam search is a heuristic technique, it doesn’t guarantee to find the true top\-kkblocks \(but our experiments show better\-than\-SOTA accuracy\)\. Overall, the traversal descends⌈logr⁡\(\|𝒞\|/\|ℬ\|\)⌉\\lceil\\log\_\{r\}\(\|\\mathcal\{C\}\|/\|\\mathcal\{B\}\|\)\\rceillevels and examines at mostW⋅rW\\cdot rnodes per level, for a total ofO⁡\(W⋅r⋅\|Q\|⋅logr⁡\|𝒞\|\|ℬ\|\)O\\\!\\left\(W\\cdot r\\cdot\|Q\|\\cdot\\log\_\{r\}\\frac\{\|\\mathcal\{C\}\|\}\{\|\\mathcal\{B\}\|\}\\right\)upper\-bound array fetches\. The baseline, in contrast, scans blocks linearly and requires\|Q\|​\|𝒞\|\|ℬ\|\|Q\|\\frac\{\|\\mathcal\{C\}\|\}\{\|\\mathcal\{B\}\|\}array fetches, i\.e\., from linear to logarithmic\. Regarding2, theclntproceeds interactively: at each levelclntretrieves via PIR the relevant array entries from the candidate super\-blocks thatclntalready identified, sums them locally to obtain the total upper bound for each candidate super\-block, and uses the result to select which super\-blocks become candidates at the next level\. Finally, the bottom level stores not the embeddings themselves but the identifiers of the embeddings contained in each block\. Retrieving the embeddings therefore requires one additional round of PIR, after which the client performs the dense retrieval step locally\. Overall, theclntperformslogr⁡\|𝒞\|\|ℬ\|\\log\_\{r\}\\frac\{\|\\mathcal\{C\}\|\}\{\|\\mathcal\{B\}\|\}PIR rounds, and at each round it batchesW⋅r⋅\|Q\|W\\cdot r\\cdot\|Q\|array indices to retrieve \(here, we concatenate all arrays\-of\-upper\-bounds of the level into a single one\)\. We apply four further optimizations to improve accuracy and performance\. First, at preprocessing timesrvclusters the corpus so that each block contains mutually similar documents\. Second, each PIR entry at a given nodeℬ\\mathcal\{B\}and wordwwstores the scores ofwww\.r\.t\.rrchildren ofℬ\\mathcal\{B\}rather than toℬ\\mathcal\{B\}itself\. At query time, this reduces the PIR cost from\|Q\|​W​r\|Q\|Wrqueries over a\|𝒱\|×rℓ\+1\|\\mathcal\{V\}\|\\times r^\{\\ell\+1\}\-sized child\-level PIR database to\|Q\|​W\|Q\|Wqueries over a\|𝒱\|×rℓ\|\\mathcal\{V\}\|\\times r^\{\\ell\}\-sized current\-level PIR database\. Third, we add a refinement layer below each leaf block, separate from the tree traversal\. Each leaf contains\|ℬ\|\|\\mathcal\{B\}\|documents and is partitioned into sub\-blocks ofssdocuments, giving branch factorr⋆=⌈\|ℬ\|/s⌉r^\{\\star\}=\\lceil\|\\mathcal\{B\}\|/s\\rceil\. After the tree traversal filters the search space toW×\|ℬ\|W\\times\|\\mathcal\{B\}\|candidate documents, the refinement layer selects the topksk\_\{s\}sub\-blocks, reducing the embedding\-fetch cost from\|ℬ\|×W\|\\mathcal\{B\}\|\\times Wembeddings toks×sk\_\{s\}\\times s\. Finally, to avoid storing\|𝒱\|\|\\mathcal\{V\}\|mostly\-zero upper bounds per super\-block at each level, we realize each level’s PIR database as a cuckoo hash table holding only non\-zero entries, tradingmmPIR queries per lookup for a substantial reduction in server storage and PIR cost \(see Appendix[H](https://arxiv.org/html/2609.36326#A8)\)\. There are many parameters that affect search speed and quality, such as branching factor,rr, beam width,WW, block size,\|ℬ\|\|\\mathcal\{B\}\|, etc\. we study the effect and the interplay of the different parameters in Appendix[D\.1](https://arxiv.org/html/2609.36326#A4.SS1)\. A high\-level design ofPILLAR\-Treeis shown in Figure[2](https://arxiv.org/html/2609.36326#S4.F2), where we split the design ofPILLAR\-Treeinto three stages: In Stage11, theclnttraverses the tree with beam search, using one PIR round per level, until it reachesWWleaf blocks\. In Stage22, theclntretrieves via PIR the upper bounds of the sub\-blocks of these leaf blocks, selects the topksk\_\{s\}sub\-blocks, and obtains the identifiers of their embeddings\. In Stage33, theclntretrieves these embeddings via PIR and performs the dense retrieval locally\.

## 5Evaluation

### 5\.1Experimental Setup

We implement our designsPILLAR\-BinandPILLAR\-Tree\(Section[4](https://arxiv.org/html/2609.36326#S4)\) in Go and compare them against PACMANN\([Zhou et al\., 2024b](https://arxiv.org/html/2609.36326#bib.bib1)\), the state\-of\-the\-art PPRAG protocol, which answers each query through a multi\-round private ANN traversal\. For all three protocols, we run a hyperparameter grid search over all parameters \(we detail the tunable parameters in Table[1](https://arxiv.org/html/2609.36326#S5.T1)\)\. We plot/detail the metrics for every configuration of every method over our chosen datasets in Appendix[D](https://arxiv.org/html/2609.36326#A4)\. Because the number of configurations is large, this section reports five representative configurations per protocol; Appendix[D](https://arxiv.org/html/2609.36326#A4)repeats each plot with all configurations included\.

On Selecting Representative Configurations\.We adapt a standard algorithm for determining how to minimize the metric*cost*while maximizing the metric*benefit*over multiple configurations, called*Kneedle*[Satopaa et al\. \(2011\)](https://arxiv.org/html/2609.36326#bib.bib9)\. We define the benefit of a configuration by the mean of its MRR@10 and Recall@10, each min\-max normalized first, which are standard metrics[Thakur et al\. \(2021b\)](https://arxiv.org/html/2609.36326#bib.bib47)in determining the quality of documents retrieved\. The ideal cost for a PPRAG must consider two quantities, \(ii\) the number of PIR rounds it needs, and \(i​iii\) the total data transferred\. We use per\-query WAN latency as a proxy for both: each sequential PIR round adds a full network round trip, and each byte transferred adds transmission time over the limited bandwidth\. Following Kneedle, for each of the three protocols, we compute and select five configurations from the Pareto frontier: The lowest\-cost configuration \(C1\), the configuration with the largest normalized benefit relative to its normalized cost \(C2\), the configurations with the highest MRR@10 \(C3\) and highest Recall@10 \(C4\), and the highest\-cost configuration \(C5\)\. Appendix[D](https://arxiv.org/html/2609.36326#A4)details the full procedure\. For completeness, we consider other instantiations of the metric cost, such as LAN latency, computation time, and total data sent, in Appendix[D](https://arxiv.org/html/2609.36326#A4)\.

Datasets\.We evaluate on the MS MARCO passage retrieval benchmark\([Bajaj et al\., 2018](https://arxiv.org/html/2609.36326#bib.bib45)\), consisting of8\.88\.8million passages and6,9806\{,\}980queries, and on SciFact[Wadden et al\. \(2020\)](https://arxiv.org/html/2609.36326#bib.bib12), a corpus of5,1835\{,\}183documents and300300queries\.

Table 1:The parameter grid searched for each protocol\. Every combination was run on both SciFact and MS MARCO\.These two datasets cover the qualities that matter for a PPRAG evaluation: MS MARCO is large, so latency, communication, and memory all matter, and its queries are open\-domain, so exact term overlap is a weak measure of similarity, which works against the lexical scoring components in bothPILLAR\-BinandPILLAR\-Tree\. SciFact is three orders of magnitude smaller, so cost differences matter less, but its queries are scientific claims with rare, specific terminology, where lexical scoring is strongest\.

Testbed\.Retrieval experiments were run on a Debian 12 container with a 64\-core, 128\-thread AMD EPYC Zen 2 CPU, but we limit each process to only 15 threads\. For end\-to\-end answer quality, the documents retrieved by each selected configuration are passed to an LLM, Qwen2\.5\-7B\-Instruct[Qwen et al\. \(2025\)](https://arxiv.org/html/2609.36326#bib.bib36)\. The resulting answers are scored by the RAGAS framework[Es et al\. \(2025\)](https://arxiv.org/html/2609.36326#bib.bib26), with Llama\-3\-70B[Grattafiori et al\. \(2024\)](https://arxiv.org/html/2609.36326#bib.bib37)as judge\. To simulate WAN latency, we use a round\-trip\-time of 50 milliseconds and 400 megabits per second bandwidth\. See further details in[I\.1](https://arxiv.org/html/2609.36326#A9.SS1)

### 5\.2Comparison against PACMANN and Ablation

\(a\)PPRAG Comparison \- MS MARCO\(b\)PPRAG Comparison \- SciFact
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\.Metrics\.To benchmark our proposed PPRAGs, we use Recall@10, which measures whether the correct document appears among the top1010retrieved, and MRR@10, which rewards placing the correct document near the top\. We also use RAGAS metrics,*Faithfulness*measures whether the claims in the LLM’s answer are supported by the retrieved documents, and*Answer Relevancy*measures whether the LLM actually answered the question, regardless of the presence of the correct document\. We report both groups, because MRR and Recall alone do not show whether the retrieved context is useful to an LLM555The evaluation of PACMANN only considers MRR and Recall, but a RAG pipeline needs to retrieve documents that generate a well\-informed answer, so we report RAGAS metrics alongside MRR and Recall\. As all of our configurations offer a cost\-benefit trade\-off, we show the*Pareto frontier*\(black line\) in Figure[3](https://arxiv.org/html/2609.36326#S5.F3)for each configuration in our two datasets\. If a configuration lies on the Pareto frontier, no configuration of any protocol achieves better quality \(Y\-axis\) at equal or lower latency \(X\-axis\)\. Across all of our experiments \(See Figure[3](https://arxiv.org/html/2609.36326#S5.F3)\),93%93\\%of the points on the Pareto frontier come from our proposedPILLARhybrid architecture and only7%7\\%come from PACMANN\.

On the Analysis of The Pareto Frontier\.PILLAR\-Binretrieves the top1010documents in as little as0\.0980\.098s on MS MARCO and0\.0650\.065s on SciFact\. There is no configuration of PACMANN \(on the Pareto frontier\) that runs under0\.10\.1s on either datasets \(whilePILLAR\-Binhas multiple\), the fastest PACMANN configuration takes0\.2930\.293s on MS MARCO and0\.2700\.270s on SciFact, which is3×3\\timesto4×4\\timesslower\. As forPILLAR\-Tree, in terms of speed,PILLAR\-Treerarely reachesPILLAR\-Bin’s latencies, since its traversal needs⌈logr⁡\(\|𝒞\|/\|ℬ\|\)⌉\\lceil\\log\_\{r\}\(\|\\mathcal\{C\}\|/\|\\mathcal\{B\}\|\)\\rceilrounds\. In terms of quality, across all configurations on the Pareto frontier in Figure[3](https://arxiv.org/html/2609.36326#S5.F3)that run in under1\.01\.0s,PILLAR\-Treeachieves the highest quality across all metrics and across both datasets\. Across all configurations used to produce Figure[3](https://arxiv.org/html/2609.36326#S5.F3),54%54\\%of the points are configurations ofPILLAR\-Tree\.

PILLAR\-TreeLatency by Stages\.ManyPILLAR\-Treeconfigurations retrieve documents that score highly across quality metrics, but, for some of them, the latency is increased\. To investigate this, we show how each of the three stages ofPILLAR\-Treeaffects latency in Figure[4\(b\)](https://arxiv.org/html/2609.36326#S5.F4.sf2)\. On MS MARCO, Stages11and33stay roughly constant, which are the traversal and embedding retrieval stages, respectively\. Almost all latency variability comes from Stage22, the sub\-block retrieval stage\. Stage22latency drives retrieval quality; the highest\-latency configuration \(C5\) reaches0\.3180\.318MRR on MS MARCO, while the lowest\-latency configuration reaches0\.2480\.248, a28%28\\%gain\.WWdetermines how many candidate documents Stage22refines, which makes it the first parameter to tune on a new dataset\. On SciFact, the five configurations differ by under2020ms\. This is due to the size of the tree, which will always be smaller on a small dataset \(such as SciFact\)\.

\(a\)PILLAR\-BinAblation\(b\)PILLAR\-TreeLatency by Stages
Figure 4:Left: TwoPILLAR\-Binablation 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 selectedPILLAR\-Treeconfigurations \(C1\-C5\) \(defined in Section[5\.1](https://arxiv.org/html/2609.36326#S5.SS1)and Table[3](https://arxiv.org/html/2609.36326#A4.T3)lists their specific parameters\) by the 3 stages defined in Section[4\.2](https://arxiv.org/html/2609.36326#S4.SS2)\.PILLAR\-BinAblation\.We test the two parameters ofPILLAR\-Bin: the size of the hash table, and the number of documents stored in a bin\. Specifically, we investigate \(ii\) how the size of the hash table affects the communication cost, as well as \(i​iii\) how the number of documents stored in a bin affects retrieval quality \(we provide a more extensive ablation onPILLAR\-Binin Appendix[D](https://arxiv.org/html/2609.36326#A4)\)\. The left plot of Figure[4\(a\)](https://arxiv.org/html/2609.36326#S5.F4.sf1)fixes the documents per bin at1010and varies the hash table size \(X\-axis\), showing that total communication cost per query \(Y\-axis, Comm KB\) increases with the size of the hash table \(as is expected when using PIR\)\. We vary the size of the hash table by66orders of magnitude, but see that the communication cost for the largest hash table is not even2×2\\timesthe cost of the smallest\. Thus, hash table size has little impact on the total communication cost, allowing flexibility to choose the hash table size that provides the best retrieval quality \(as shown in Appendix[D](https://arxiv.org/html/2609.36326#A4)\)\. The right plot of Figure[4\(a\)](https://arxiv.org/html/2609.36326#S5.F4.sf1)fixes the hash table sizes at11million for MS MARCO and55thousand for SciFact and varies the number of documents stored in a bin \(X\-axis\)\. We see that MRR@10/Recall@10 \(Y\-axis, Quality\) for the retrieved documents increases as the number of documents stored in a bin increases\. Scifact sees diminishing returns, after storing700700documents per bin, there is little more retrieval quality to gain\. MS Marco continues to see benefits from more returned documents, even at the highest tested values,1\.01\.0K\-2\.52\.5K documents per bin, MS MARCO still increases\.

## 6Conclusion

We presentedPILLAR, a pair of PIR\-friendly hybrid retrieval protocols \(PILLAR\-BinandPILLAR\-Tree\) that split retrieval between a cheap lexical score and a semantic re\-ranking performed entirely by the client\. We evaluate our two protocols using the state\-of\-the\-art, PACMANN\.PILLAR\-Binalways has a faster configuration available, answering queries three times faster than any configuration PACMANN admits, whilePILLAR\-Treefrequently retrieves better quality documents than PACMANN at the same speed\.

## Acknowledgements

Daniel Blackley and Evgenios M\. Kornaropoulos were partially supported by NSF awards \#2154732 and \#2439951\. Truong Son Nguyen and Ni Trieu were partially supported by NSF award \#2451972, ARPA\-H award \#1AY2AX000167\-01, and Amazon Research award\.

## References

- I\. Ahmad, L\. Sarker, D\. Agrawal, A\. E\. Abbadi, and T\. GuptaCoeus: a system for oblivious document ranking and retrieval\.InProceedings of the 28th ACM Symposium on Operating Systems Principles \(SOSP\),pp\. 672–690\.Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p3.1)\.
- Anthropic \(2024\)AnthropicIntroducing contextual retrieval\.Note:[https://www\.anthropic\.com/news/contextual\-retrieval](https://www.anthropic.com/news/contextual-retrieval)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Aumülleret al\.\(2018\)M\. Aumüller, E\. Bernhardsson, and A\. J\. FaithfullANN\-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms\.CoRRabs/1807\.05614\.External Links:[Link](http://arxiv.org/abs/1807.05614),1807\.05614Cited by:[Remark 4](https://arxiv.org/html/2609.36326#Thmdefinition4.p1.1.1)\.
- Bajajet al\.\(2018\)P\. Bajaj, D\. Campos, N\. Craswell, L\. Deng, J\. Gao, X\. Liu, R\. Majumder, A\. McNamara, B\. Mitra, T\. Nguyen, M\. Rosenberg, X\. Song, A\. Stoica, S\. Tiwary, and T\. WangMS marco: a human generated machine reading comprehension dataset\.External Links:1611\.09268,[Link](https://arxiv.org/abs/1611.09268)Cited by:[2nd item](https://arxiv.org/html/2609.36326#S1.I1.i2.p1.1),[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p3.1)\.
- Barbaro and Jr\. \(2006\)M\. Barbaro and T\. Z\. Jr\.A face is exposed for AOL searcher no\. 4417749\.Note:The New York TimesAccessed September 2026External Links:[Link](https://archive.nytimes.com/www.nytimes.com/learning/teachers/featured_articles/20060810thursday.html)Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p1.1)\.
- Beimelet al\.\(2000\)A\. Beimel, Y\. Ishai, and T\. MalkinReducing the servers computation in private information retrieval: pir with preprocessing\.InAdvances in Cryptology — CRYPTO 2000,M\. Bellare \(Ed\.\),Berlin, Heidelberg,pp\. 55–73\.External Links:ISBN 978\-3\-540\-44598\-2Cited by:[§2](https://arxiv.org/html/2609.36326#S2.p2.1)\.
- \[7\]A\. Berntson, A\. Stoica Beck, A\. Salvador Aguilera, F\. Sunavala, T\. Gisselbrecht, and X\. ChenRaising the bar for rag excellence\.Note:Whitepaper,[https://cdn\-dynmedia\-1\.microsoft\.com/is/content/microsoftcorp/microsoft/final/en\-us/microsoft\-brand/documents/ai\-search\-query\-engine\-performance\-whitepaper\.pdf](https://cdn-dynmedia-1.microsoft.com/is/content/microsoftcorp/microsoft/final/en-us/microsoft-brand/documents/ai-search-query-engine-performance-whitepaper.pdf)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Bisiani \(1987\)R\. BisianiBeam search\.InEncyclopedia of Artificial Intelligence,S\. C\. Shapiro \(Ed\.\),Cited by:[§4\.2](https://arxiv.org/html/2609.36326#S4.SS2.p2.1)\.
- Broderet al\.\(2003\)A\. Broder, D\. Carmel, M\. Herscovici, A\. Soffer, and J\. ZienEfficient query evaluation using a two\-level retrieval process\.InCIKM,Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p6.1),[§3\.1](https://arxiv.org/html/2609.36326#S3.SS1.p4.1)\.
- Bruchet al\.\(2023\)S\. Bruch, S\. Gai, and A\. IngberAn analysis of fusion functions for hybrid retrieval\.ACM Transactions on Information Systems\.Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p4.1)\.
- Chor and Gilboa \(1997\)B\. Chor and N\. GilboaComputationally private information retrieval \(extended abstract\)\.InProceedings of the Twenty\-Ninth Annual ACM Symposium on Theory of Computing,STOC ’97,New York, NY, USA,pp\. 304–313\.External Links:ISBN 0897918886,[Link](https://doi.org/10.1145/258533.258609),[Document](https://dx.doi.org/10.1145/258533.258609)Cited by:[Definition 1](https://arxiv.org/html/2609.36326#Thmdefinition1)\.
- Choret al\.\(1995\)B\. Chor, O\. Goldreich, E\. Kushilevitz, and M\. SudanPrivate information retrieval\.InFOCS,Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p2.1),[§2](https://arxiv.org/html/2609.36326#S2.p2.1)\.
- Cormacket al\.\(2009\)G\. V\. Cormack, C\. L\. A\. Clarke, and S\. BuettcherReciprocal rank fusion outperforms condorcet and individual rank learning methods\.InProceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval,SIGIR ’09,New York, NY, USA,pp\. 758–759\.External Links:ISBN 9781605584836,[Link](https://doi.org/10.1145/1571941.1572114),[Document](https://dx.doi.org/10.1145/1571941.1572114)Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Corrigan\-Gibbs and Kogan \(2020\)H\. Corrigan\-Gibbs and D\. KoganPrivate information retrieval with sublinear online time\.InAdvances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings, Part I,Berlin, Heidelberg,pp\. 44–75\.External Links:ISBN 978\-3\-030\-45720\-4,[Link](https://doi.org/10.1007/978-3-030-45721-1_3),[Document](https://dx.doi.org/10.1007/978-3-030-45721-1%5F3)Cited by:[§2](https://arxiv.org/html/2609.36326#S2.p2.1)\.
- Ding and Suel \(2011\)S\. Ding and T\. SuelFaster top\-k document retrieval using block\-max indexes\.InProceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval,SIGIR ’11,New York, NY, USA,pp\. 993–1002\.External Links:ISBN 9781450307574,[Link](https://doi.org/10.1145/2009916.2010048),[Document](https://dx.doi.org/10.1145/2009916.2010048)Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p6.1),[§3\.1](https://arxiv.org/html/2609.36326#S3.SS1.p4.1.1)\.
- \[16\]ElasticReciprocal rank fusion\.Note:Elasticsearch Reference,[https://www\.elastic\.co/docs/reference/elasticsearch/rest\-apis/reciprocal\-rank\-fusion](https://www.elastic.co/docs/reference/elasticsearch/rest-apis/reciprocal-rank-fusion)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Eset al\.\(2025\)S\. Es, J\. James, L\. Espinosa\-Anke, and S\. SchockaertRagas: automated evaluation of retrieval augmented generation\.External Links:2309\.15217,[Link](https://arxiv.org/abs/2309.15217)Cited by:[2nd item](https://arxiv.org/html/2609.36326#S1.I1.i2.p1.1),[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p5.1)\.
- Formalet al\.\(2021\)T\. Formal, B\. Piwowarski, and S\. ClinchantSPLADE: sparse lexical and expansion model for first stage ranking\.CoRRabs/2107\.05720\.External Links:[Link](https://arxiv.org/abs/2107.05720),2107\.05720Cited by:[§3\.1](https://arxiv.org/html/2609.36326#S3.SS1.p1.1)\.
- Gaoet al\.\(2023\)Y\. Gao, Y\. Xiong, X\. Gao, K\. Jia, J\. Pan, Y\. Bi, Y\. Dai, J\. Sun, Q\. Guo, M\. Wang, and H\. WangRetrieval\-augmented generation for large language models: a survey\.arXiv preprint arXiv:2312\.10997\.Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p1.1)\.
- Grattafioriet al\.\(2024\)A\. Grattafiori, A\. Dubey, A\. Jauhri, A\. Pandey, A\. Kadian, A\. Al\-Dahle, A\. Letman, A\. Mathur, A\. Schelten, A\. Vaughan, A\. Yang, A\. Fan, A\. Goyal, A\. Hartshorn, A\. Yang, A\. Mitra, A\. Sravankumar, A\. Korenev, A\. Hinsvark, A\. Rao, A\. Zhang, A\. Rodriguez, A\. Gregerson, A\. Spataru, B\. Roziere, B\. Biron, B\. Tang, B\. Chern, C\. Caucheteux, C\. Nayak, C\. Bi, C\. Marra, C\. McConnell, C\. Keller, C\. Touret, C\. Wu, C\. Wong, C\. C\. Ferrer, C\. Nikolaidis, D\. Allonsius, D\. Song, D\. Pintz, D\. Livshits, D\. Wyatt, D\. Esiobu, D\. Choudhary, D\. Mahajan, D\. Garcia\-Olano, D\. Perino, D\. Hupkes, E\. Lakomkin, E\. AlBadawy, E\. Lobanova, E\. Dinan, E\. M\. Smith, F\. Radenovic, F\. Guzmán, F\. Zhang, G\. Synnaeve, G\. Lee, G\. L\. Anderson, G\. Thattai, G\. Nail, G\. Mialon, G\. Pang, G\. Cucurell, H\. Nguyen, H\. Korevaar, H\. Xu, H\. Touvron, I\. Zarov, I\. A\. Ibarra, I\. Kloumann, I\. Misra, I\. Evtimov, J\. Zhang, J\. Copet, J\. Lee, J\. Geffert, J\. Vranes, J\. Park, J\. Mahadeokar, J\. Shah, J\. van der Linde, J\. Billock, J\. Hong, J\. Lee, J\. Fu, J\. Chi, J\. Huang, J\. Liu, J\. Wang, J\. Yu, J\. Bitton, J\. Spisak, J\. Park, J\. Rocca, J\. Johnstun, J\. Saxe, J\. Jia, K\. V\. Alwala, K\. Prasad, K\. Upasani, K\. Plawiak, K\. Li, K\. Heafield, K\. Stone, K\. El\-Arini, K\. Iyer, K\. Malik, K\. Chiu, K\. Bhalla, K\. Lakhotia, L\. Rantala\-Yeary, L\. van der Maaten, L\. Chen, L\. Tan, L\. Jenkins, L\. Martin, L\. Madaan, L\. Malo, L\. Blecher, L\. Landzaat, L\. de Oliveira, M\. Muzzi, M\. Pasupuleti, M\. Singh, M\. Paluri, M\. Kardas, M\. Tsimpoukelli, M\. Oldham, M\. Rita, M\. Pavlova, M\. Kambadur, M\. Lewis, M\. Si, M\. K\. Singh, M\. Hassan, N\. Goyal, N\. Torabi, N\. Bashlykov, N\. Bogoychev, N\. Chatterji, N\. Zhang, O\. Duchenne, O\. Çelebi, P\. Alrassy, P\. Zhang, P\. Li, P\. Vasic, P\. Weng, P\. Bhargava, P\. Dubal, P\. Krishnan, P\. S\. Koura, P\. Xu, Q\. He, Q\. Dong, R\. Srinivasan, R\. Ganapathy, R\. Calderer, R\. S\. Cabral, R\. Stojnic, R\. Raileanu, R\. Maheswari, R\. Girdhar, R\. Patel, R\. Sauvestre, R\. Polidoro, R\. Sumbaly, R\. Taylor, R\. Silva, R\. Hou, R\. Wang, S\. Hosseini, S\. Chennabasappa, S\. Singh, S\. Bell, S\. S\. Kim, S\. Edunov, S\. Nie, S\. Narang, S\. Raparthy, S\. Shen, S\. Wan, S\. Bhosale, S\. Zhang, S\. Vandenhende, S\. Batra, S\. Whitman, S\. Sootla, S\. Collot, S\. Gururangan, S\. Borodinsky, T\. Herman, T\. Fowler, T\. Sheasha, T\. Georgiou, T\. Scialom, T\. Speckbacher, T\. Mihaylov, T\. Xiao, U\. Karn, V\. Goswami, V\. Gupta, V\. Ramanathan, V\. Kerkez, V\. Gonguet, V\. Do, V\. Vogeti, V\. Albiero, V\. Petrovic, W\. Chu, W\. Xiong, W\. Fu, W\. Meers, X\. Martinet, X\. Wang, X\. Wang, X\. E\. Tan, X\. Xia, X\. Xie, X\. Jia, X\. Wang, Y\. Goldschlag, Y\. Gaur, Y\. Babaei, Y\. Wen, Y\. Song, Y\. Zhang, Y\. Li, Y\. Mao, Z\. D\. Coudert, Z\. Yan, Z\. Chen, Z\. Papakipos, A\. Singh, A\. Srivastava, A\. Jain, A\. Kelsey, A\. Shajnfeld, A\. Gangidi, A\. Victoria, A\. Goldstand, A\. Menon, A\. Sharma, A\. Boesenberg, A\. Baevski, A\. Feinstein, A\. Kallet, A\. Sangani, A\. Teo, A\. Yunus, A\. Lupu, A\. Alvarado, A\. Caples, A\. Gu, A\. Ho, A\. Poulton, A\. Ryan, A\. Ramchandani, A\. Dong, A\. Franco, A\. Goyal, A\. Saraf, A\. Chowdhury, A\. Gabriel, A\. Bharambe, A\. Eisenman, A\. Yazdan, B\. James, B\. Maurer, B\. Leonhardi, B\. Huang, B\. Loyd, B\. D\. Paola, B\. Paranjape, B\. Liu, B\. Wu, B\. Ni, B\. Hancock, B\. Wasti, B\. Spence, B\. Stojkovic, B\. Gamido, B\. Montalvo, C\. Parker, C\. Burton, C\. Mejia, C\. Liu, C\. Wang, C\. Kim, C\. Zhou, C\. Hu, C\. Chu, C\. Cai, C\. Tindal, C\. Feichtenhofer, C\. Gao, D\. Civin, D\. Beaty, D\. Kreymer, D\. Li, D\. Adkins, D\. Xu, D\. Testuggine, D\. David, D\. Parikh, D\. Liskovich, D\. Foss, D\. Wang, D\. Le, D\. Holland, E\. Dowling, E\. Jamil, E\. Montgomery, E\. Presani, E\. Hahn, E\. Wood, E\. Le, E\. Brinkman, E\. Arcaute, E\. Dunbar, E\. Smothers, F\. Sun, F\. Kreuk, F\. Tian, F\. Kokkinos, F\. Ozgenel, F\. Caggioni, F\. Kanayet, F\. Seide, G\. M\. Florez, G\. Schwarz, G\. Badeer, G\. Swee, G\. Halpern, G\. Herman, G\. Sizov, Guangyi, Zhang, G\. Lakshminarayanan, H\. Inan, H\. Shojanazeri, H\. Zou, H\. Wang, H\. Zha, H\. Habeeb, H\. Rudolph, H\. Suk, H\. Aspegren, H\. Goldman, H\. Zhan, I\. Damlaj, I\. Molybog, I\. Tufanov, I\. Leontiadis, I\. Veliche, I\. Gat, J\. Weissman, J\. Geboski, J\. Kohli, J\. Lam, J\. Asher, J\. Gaya, J\. Marcus, J\. Tang, J\. Chan, J\. Zhen, J\. Reizenstein, J\. Teboul, J\. Zhong, J\. Jin, J\. Yang, J\. Cummings, J\. Carvill, J\. Shepard, J\. McPhie, J\. Torres, J\. Ginsburg, J\. Wang, K\. Wu, K\. H\. U, K\. Saxena, K\. Khandelwal, K\. Zand, K\. Matosich, K\. Veeraraghavan, K\. Michelena, K\. Li, K\. Jagadeesh, K\. Huang, K\. Chawla, K\. Huang, L\. Chen, L\. Garg, L\. A, L\. Silva, L\. Bell, L\. Zhang, L\. Guo, L\. Yu, L\. Moshkovich, L\. Wehrstedt, M\. Khabsa, M\. Avalani, M\. Bhatt, M\. Mankus, M\. Hasson, M\. Lennie, M\. Reso, M\. Groshev, M\. Naumov, M\. Lathi, M\. Keneally, M\. Liu, M\. L\. Seltzer, M\. Valko, M\. Restrepo, M\. Patel, M\. Vyatskov, M\. Samvelyan, M\. Clark, M\. Macey, M\. Wang, M\. J\. Hermoso, M\. Metanat, M\. Rastegari, M\. Bansal, N\. Santhanam, N\. Parks, N\. White, N\. Bawa, N\. Singhal, N\. Egebo, N\. Usunier, N\. Mehta, N\. P\. Laptev, N\. Dong, N\. Cheng, O\. Chernoguz, O\. Hart, O\. Salpekar, O\. Kalinli, P\. Kent, P\. Parekh, P\. Saab, P\. Balaji, P\. Rittner, P\. Bontrager, P\. Roux, P\. Dollar, P\. Zvyagina, P\. Ratanchandani, P\. Yuvraj, Q\. Liang, R\. Alao, R\. Rodriguez, R\. Ayub, R\. Murthy, R\. Nayani, R\. Mitra, R\. Parthasarathy, R\. Li, R\. Hogan, R\. Battey, R\. Wang, R\. Howes, R\. Rinott, S\. Mehta, S\. Siby, S\. J\. Bondu, S\. Datta, S\. Chugh, S\. Hunt, S\. Dhillon, S\. Sidorov, S\. Pan, S\. Mahajan, S\. Verma, S\. Yamamoto, S\. Ramaswamy, S\. Lindsay, S\. Lindsay, S\. Feng, S\. Lin, S\. C\. Zha, S\. Patil, S\. Shankar, S\. Zhang, S\. Zhang, S\. Wang, S\. Agarwal, S\. Sajuyigbe, S\. Chintala, S\. Max, S\. Chen, S\. Kehoe, S\. Satterfield, S\. Govindaprasad, S\. Gupta, S\. Deng, S\. Cho, S\. Virk, S\. Subramanian, S\. Choudhury, S\. Goldman, T\. Remez, T\. Glaser, T\. Best, T\. Koehler, T\. Robinson, T\. Li, T\. Zhang, T\. Matthews, T\. Chou, T\. Shaked, V\. Vontimitta, V\. Ajayi, V\. Montanez, V\. Mohan, V\. S\. Kumar, V\. Mangla, V\. Ionescu, V\. Poenaru, V\. T\. Mihailescu, V\. Ivanov, W\. Li, W\. Wang, W\. Jiang, W\. Bouaziz, W\. Constable, X\. Tang, X\. Wu, X\. Wang, X\. Wu, X\. Gao, Y\. Kleinman, Y\. Chen, Y\. Hu, Y\. Jia, Y\. Qi, Y\. Li, Y\. Zhang, Y\. Zhang, Y\. Adi, Y\. Nam, Yu, Wang, Y\. Zhao, Y\. Hao, Y\. Qian, Y\. Li, Y\. He, Z\. Rait, Z\. DeVito, Z\. Rosnbrick, Z\. Wen, Z\. Yang, Z\. Zhao, and Z\. MaThe llama 3 herd of models\.External Links:2407\.21783,[Link](https://arxiv.org/abs/2407.21783)Cited by:[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p5.1)\.
- Har\-Peledet al\.\(1998\)S\. Har\-Peled, P\. Indyk, and R\. MotwaniApproximate nearest neighbor: towards removing the curse of dimensionality\.Theory of Computing8,pp\. 321–350\.External Links:ISBN 0897919629,[Document](https://dx.doi.org/10.4086/toc.2012.v008a014)Cited by:[§3\.2](https://arxiv.org/html/2609.36326#S3.SS2.p2.1)\.
- Henzingeret al\.\(2023\)A\. Henzinger, E\. Dauterman, H\. Corrigan\-Gibbs, and N\. ZeldovichPrivate web search with tiptoe\.Note:Cryptology ePrint Archive, Paper 2023/1438External Links:[Document](https://dx.doi.org/10.1145/3600006.3613134),[Link](https://eprint.iacr.org/2023/1438)Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p3.1),[§2](https://arxiv.org/html/2609.36326#S2.p2.1)\.
- Johnsonet al\.\(2019\)J\. Johnson, M\. Douze, and H\. JégouBillion\-scale similarity search with gpus\.InIEEE Transactions on Big Data,Cited by:[Remark 4](https://arxiv.org/html/2609.36326#Thmdefinition4.p1.1.1)\.
- Karpukhinet al\.\(2020\)V\. Karpukhin, B\. Oguz, S\. Min, P\. Lewis, L\. Wu, S\. Edunov, D\. Chen, and W\. YihDense passage retrieval for open\-domain question answering\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),B\. Webber, T\. Cohn, Y\. He, and Y\. Liu \(Eds\.\),Online,pp\. 6769–6781\.External Links:[Link](https://aclanthology.org/2020.emnlp-main.550/),[Document](https://dx.doi.org/10.18653/v1/2020.emnlp-main.550)Cited by:[§3\.2](https://arxiv.org/html/2609.36326#S3.SS2.p1.1),[§3\.2](https://arxiv.org/html/2609.36326#S3.SS2.p2.1)\.
- Kushilevitz and Ostrovsky \(1997\)E\. Kushilevitz and R\. OstrovskyReplication is not needed: single database, computationally\-private information retrieval\.InProceedings of the 38th Annual Symposium on Foundations of Computer Science,FOCS ’97,USA,pp\. 364\.External Links:ISBN 0818681977Cited by:[§2](https://arxiv.org/html/2609.36326#S2.p2.1),[Definition 1](https://arxiv.org/html/2609.36326#Thmdefinition1)\.
- Lewiset al\.\(2020\)P\. Lewis, E\. Perez, A\. Piktus, F\. Petroni, V\. Karpukhin, N\. Goyal, H\. Küttler, M\. Lewis, W\. Yih, T\. Rocktäschel, S\. Riedel, and D\. KielaRetrieval\-augmented generation for knowledge\-intensive NLP tasks\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p1.1)\.
- Maet al\.\(2021\)X\. Ma, K\. Sun, R\. Pradeep, and J\. LinA replication study of dense passage retriever\.arXiv preprint arXiv:2104\.05740\.Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p4.1)\.
- Malkov and Yashunin \(2018\)Y\. A\. Malkov and D\. A\. YashuninEfficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs\.IEEE TPAMI\.Cited by:[Remark 4](https://arxiv.org/html/2609.36326#Thmdefinition4.p1.1.1)\.
- \[29\]MicrosoftHybrid search using vectors and full text in Azure AI Search\.Note:[https://learn\.microsoft\.com/en\-us/azure/search/hybrid\-search\-overview](https://learn.microsoft.com/en-us/azure/search/hybrid-search-overview)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Miettinen \(1999\)K\. MiettinenNonlinear multiobjective optimization\.International Series in Operations Research and Management Science, Vol\.12,Springer\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4615-5563-6)Cited by:[§D\.1\.1](https://arxiv.org/html/2609.36326#A4.SS1.SSS1.Px1.p1.1)\.
- Mireshghallahet al\.\(2024\)N\. Mireshghallah, M\. Antoniak, Y\. More, Y\. Choi, and G\. FarnadiTrust no bot: discovering personal disclosures in human\-LLM conversations in the wild\.InConference on Language Modeling \(COLM\),Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p1.1)\.
- Murphy \(2013\)K\. P\. MurphyMachine learning : a probabilistic perspective\.MIT Press,Cambridge, Mass\. \[u\.a\.\]\.External Links:ISBN 9780262018029 0262018020,[Link](https://www.amazon.com/Machine-Learning-Probabilistic-Perspective-Computation/dp/0262018020/ref=sr_1_2?ie=UTF8&qid=1336857747&sr=8-2)Cited by:[§3\.2](https://arxiv.org/html/2609.36326#S3.SS2.p1.1)\.
- \[33\]OpenSearch ProjectHybrid search\.Note:[https://opensearch\.org/docs/latest/search\-plugins/hybrid\-search](https://opensearch.org/docs/latest/search-plugins/hybrid-search)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Qwenet al\.\(2025\)Qwen, :, A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Tang, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. QiuQwen2\.5 technical report\.External Links:2412\.15115,[Link](https://arxiv.org/abs/2412.15115)Cited by:[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p5.1)\.
- Reimers and Gurevych \(2019\)N\. Reimers and I\. GurevychSentence\-BERT: sentence embeddings using Siamese BERT\-networks\.InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing \(EMNLP\-IJCNLP\),K\. Inui, J\. Jiang, V\. Ng, and X\. Wan \(Eds\.\),Hong Kong, China,pp\. 3982–3992\.External Links:[Link](https://aclanthology.org/D19-1410/),[Document](https://dx.doi.org/10.18653/v1/D19-1410)Cited by:[§I\.1](https://arxiv.org/html/2609.36326#A9.SS1.p1.1)\.
- Robertson and Zaragoza \(2009\)S\. Robertson and H\. ZaragozaThe probabilistic relevance framework: bm25 and beyond\.Foundations and Trends in IR\.Cited by:[§3\.1](https://arxiv.org/html/2609.36326#S3.SS1.p1.1)\.
- Satopaaet al\.\(2011\)V\. Satopaa, J\. Albrecht, D\. Irwin, and B\. RaghavanFinding a “kneedle” in a haystack: detecting knee points in system behavior\.In2011 31st International Conference on Distributed Computing Systems Workshops,pp\. 166–171\.External Links:[Document](https://dx.doi.org/10.1109/ICDCSW.2011.20)Cited by:[§D\.1\.1](https://arxiv.org/html/2609.36326#A4.SS1.SSS1.Px2.p3.1),[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p2.1)\.
- Staabet al\.\(2024\)R\. Staab, M\. Vero, M\. Balunović, and M\. VechevBeyond memorization: violating privacy via inference with large language models\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p1.1)\.
- Thakuret al\.\(2021a\)N\. Thakur, N\. Reimers, A\. Rücklé, A\. Srivastava, and I\. GurevychBEIR: a heterogeneous benchmark for zero\-shot evaluation of information retrieval models\.InNeurIPS Datasets and Benchmarks Track,Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p4.1)\.
- Thakuret al\.\(2021b\)N\. Thakur, N\. Reimers, A\. Ruckl’e, A\. Srivastava, and I\. GurevychBEIR: a heterogenous benchmark for zero\-shot evaluation of information retrieval models\.ArXivabs/2104\.08663\.External Links:[Link](https://api.semanticscholar.org/CorpusID:233296016)Cited by:[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p2.1)\.
- Turtle and Flood \(1995\)H\. Turtle and J\. FloodQuery evaluation: strategies and optimizations\.Information Processing & Management31\(6\),pp\. 831–850\.External Links:ISSN 0306\-4573,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/0306-4573%2895%2900020-H),[Link](https://www.sciencedirect.com/science/article/pii/030645739500020H)Cited by:[§3\.1](https://arxiv.org/html/2609.36326#S3.SS1.p4.1)\.
- Waddenet al\.\(2020\)D\. Wadden, S\. Lin, K\. Lo, L\. L\. Wang, M\. van Zuylen, A\. Cohan, and H\. HajishirziFact or fiction: verifying scientific claims\.InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing \(EMNLP\),B\. Webber, T\. Cohn, Y\. He, and Y\. Liu \(Eds\.\),Online,pp\. 7534–7550\.External Links:[Link](https://aclanthology.org/2020.emnlp-main.609/),[Document](https://dx.doi.org/10.18653/v1/2020.emnlp-main.609)Cited by:[2nd item](https://arxiv.org/html/2609.36326#S1.I1.i2.p1.1),[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p3.1)\.
- Wanget al\.\(2024\)L\. Wang, N\. Yang, X\. Huang, B\. Jiao, L\. Yang, D\. Jiang, R\. Majumder, and F\. WeiText embeddings by weakly\-supervised contrastive pre\-training\.External Links:2212\.03533,[Link](https://arxiv.org/abs/2212.03533)Cited by:[§I\.1](https://arxiv.org/html/2609.36326#A9.SS1.p1.1)\.
- Wanget al\.\(2020\)W\. Wang, F\. Wei, L\. Dong, H\. Bao, N\. Yang, and M\. ZhouMiniLM: deep self\-attention distillation for task\-agnostic compression of pre\-trained transformers\.External Links:2002\.10957,[Link](https://arxiv.org/abs/2002.10957)Cited by:[§I\.1](https://arxiv.org/html/2609.36326#A9.SS1.p1.1)\.
- \[45\]WeaviateHybrid search\.Note:[https://docs\.weaviate\.io/weaviate/concepts/search/hybrid\-search](https://docs.weaviate.io/weaviate/concepts/search/hybrid-search)Accessed September 2026Cited by:[§I\.2](https://arxiv.org/html/2609.36326#A9.SS2.p1.1)\.
- Zhouet al\.\(2024a\)M\. Zhou, A\. Park, W\. Zheng, and E\. ShiPiano: extremely simple, single\-server pir with sublinear server computation\.In2024 IEEE Symposium on Security and Privacy \(SP\),Vol\.,pp\. 4296–4314\.External Links:[Document](https://dx.doi.org/10.1109/SP54263.2024.00055)Cited by:[§2](https://arxiv.org/html/2609.36326#S2.p2.1)\.
- Zhouet al\.\(2024b\)M\. Zhou, E\. Shi, and G\. FantiPacmann: efficient private approximate nearest neighbor search\.Note:Cryptology ePrint Archive, Paper 2024/1600External Links:[Link](https://eprint.iacr.org/2024/1600)Cited by:[§F\.1](https://arxiv.org/html/2609.36326#A6.SS1.p1.1),[§1](https://arxiv.org/html/2609.36326#S1.p3.1),[§1](https://arxiv.org/html/2609.36326#S1.p4.1),[§2](https://arxiv.org/html/2609.36326#S2.p2.1),[§3\.2](https://arxiv.org/html/2609.36326#S3.SS2.p2.1),[§4\.1](https://arxiv.org/html/2609.36326#S4.SS1.p3.1),[§5\.1](https://arxiv.org/html/2609.36326#S5.SS1.p1.1)\.
- Zhuet al\.\(2025\)J\. Zhu, L\. Patel, M\. Zaharia, and R\. A\. PopaCompass: encrypted semantic search with high accuracy\.In19th USENIX Symposium on Operating Systems Design and Implementation \(OSDI\),pp\. 915–938\.Cited by:[§1](https://arxiv.org/html/2609.36326#S1.p3.1)\.

## Appendix

## Appendix AAI use statement

In this work, we used generative AI tools to assist in implementing methods, namely writing code for our protocols and result plots\. We have not used generative AI tools to generate synthetic datasets, develop theoretical models or conceptual frameworks, formulate mathematical claims, provide critical ingredients for proving mathematical claims, assist in the writing of proofs, propose or refine hypotheses, design or provide feedback on research methodology or experiments, clean or reformat datasets, or interpret results, and assistance with translation and qualitative or thematic data analysis are not applicable to this work\. Additionally, we used generative AI tools to draft parts of the paper \(initial text, section structure and titles, andLaTeXlayout\), to edit the paper for grammar, spelling, and readability, and to identify and summarize relevant literature\. We have reviewed all AI\-assisted work\. All AI\-generated code was reviewed, re\-written, tested, and validated for correctness by the authors\. AI\-drafted text served only as a starting point and was revised by the authors, and all technical content, claims, and proofs are the authors’ own\. Literature identified or summarized with AI assistance was checked against the original sources, and all citations were verified manually\. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI\.

## Appendix BReproducibility

We provide an extensive Appendix that details the step\-by\-step operation ofPILLAR\-TreeandPILLAR\-Bin\(Appendix[E](https://arxiv.org/html/2609.36326#A5)\) and we also detail all the different parameters tested for all three protocols \(Appendix[D](https://arxiv.org/html/2609.36326#A4)and Table[1](https://arxiv.org/html/2609.36326#S5.T1)\)\. All code forPILLAR\-Binis available at[https://github\.com/dkblackley/bins\-go](https://github.com/dkblackley/bins-go)andPILLAR\-Treeat[https://github\.com/sonnguyenasu/bm25\-tree](https://github.com/sonnguyenasu/bm25-tree)\.

## Appendix CNotation

In the paper we use different hyper\-parameters and variables for our protocols\. We detailed the parameters notations and their corresponding definition in Table[2](https://arxiv.org/html/2609.36326#A3.T2)\.

Table 2:Definition of variables used in the paper
## Appendix DAdditional Experiment Results

In this section we present additional result of all configurations that we use some of them in the main paper\.

### D\.1Hyperparameter Tuning onPILLAR\-TreeConfigurations

We perform a grid search onPILLAR\-Treehyperparameters and evaluate recall, MRR@10, and estimated number of PIR calls needed\. From the evaluation results, we select one representative operating points from the Pareto frontier shown in Figure[5](https://arxiv.org/html/2609.36326#A4.F5)using a defined process detailed later, together with the four configurations attaining the lowest PIR call, the highest PIR calls, the highest MRR@10 and highest Recall@10\. We then run a full evaluation on these 5 configurations: we \(1\) evaluate the MRR@10 and Recall@10 of the configurations on a test set of1,5001,500queries from MSMARCO train set for MSMARCO, and a test set of7575queries from Scifact train set for Scifact– to make sure tuning set and test set are different – \(2\) execute each configuration under PIR to benchmark runtime and \(3\) use RAGAS to evaluate downstream generation quality\. For MSMarco, the search is performed overB∈\{16,32,64\},r∈\{8,32,128\},q⋆∈\{2,4,6,8\},W∈\{50,100,200,400\},s∈\{4,8,16\}B\\in\\\{16,32,64\\\},r\\in\\\{8,32,128\\\},q^\{\\star\}\\in\\\{2,4,6,8\\\},W\\in\\\{50,100,200,400\\\},s\\in\\\{4,8,16\\\}\. For Scifact, the search is performed overB∈\{8,16,32,64\},r∈\{4,8,32,128\},q⋆∈\{4,8,12,16\},W∈\{5,10,20,40,80\},s∈\{2,4,8\}B\\in\\\{8,16,32,64\\\},r\\in\\\{4,8,32,128\\\},q^\{\\star\}\\in\\\{4,8,12,16\\\},W\\in\\\{5,10,20,40,80\\\},s\\in\\\{2,4,8\\\}\. The set of 5 candidate configurations along with their corresponding MRR are shown in Table[3](https://arxiv.org/html/2609.36326#A4.T3)\.

#### D\.1\.1Representative Configurations Selection\.

As discussed earlier, we use Pareto frontier to choose a representative configuration along with two configurations represent the best recall@10 and best MRR@10\. Here we show how we choose the five configurations\.

##### Pareto Frontier

LetΘ\\Thetadenote the evaluated hyperparameter configurations\. Following the standard definition of Pareto optimality[Miettinen \[1999\]](https://arxiv.org/html/2609.36326#bib.bib8), a configurationθ′\\theta^\{\\prime\}dominatesθ\\theta, denotedθ′≻θ\\theta^\{\\prime\}\\succ\\theta, if

𝖬𝖱𝖱⁡\(θ′\)≥𝖬𝖱𝖱⁡\(θ\),𝖱𝖾𝖼𝖺𝗅𝗅⁡\(θ′\)≥𝖱𝖾𝖼𝖺𝗅𝗅⁡\(θ\),𝖯𝖨𝖱𝖢𝖺𝗅𝗅⁡\(θ′\)≤𝖯𝖨𝖱𝖢𝖺𝗅𝗅⁡\(θ\),\\mathsf\{MRR\}\(\\theta^\{\\prime\}\)\\geq\\mathsf\{MRR\}\(\\theta\),\\qquad\\mathsf\{Recall\}\(\\theta^\{\\prime\}\)\\geq\\mathsf\{Recall\}\(\\theta\),\\qquad\\mathsf\{PIRCall\}\(\\theta^\{\\prime\}\)\\leq\\mathsf\{PIRCall\}\(\\theta\),with at least one strict inequality\. The Pareto frontier is the set of configurations where improving one metric worsen at least another:

𝒫=\{θ∈Θ:∄θ′∈Θsuch thatθ′≻θ\}\.\\mathcal\{P\}=\\left\\\{\\theta\\in\\Theta:\\nexists\\theta^\{\\prime\}\\in\\Theta\\text\{ such that \}\\theta^\{\\prime\}\\succ\\theta\\right\\\}\.

##### Effectiveness Score\.

To visualize the effectiveness\-cost trade\-off, we min\-max normalize each retrieval metric:

𝖬𝖱𝖱~​\(θ\)=𝖬𝖱𝖱⁡\(θ\)−𝖬𝖱𝖱min𝖬𝖱𝖱max−𝖬𝖱𝖱min,𝖱𝖾𝖼𝖺𝗅𝗅~​\(θ\)=𝖱𝖾𝖼𝖺𝗅𝗅⁡\(θ\)−𝖱𝖾𝖼𝖺𝗅𝗅min𝖱𝖾𝖼𝖺𝗅𝗅max−𝖱𝖾𝖼𝖺𝗅𝗅min\.\\widetilde\{\\mathsf\{MRR\}\}\(\\theta\)=\\frac\{\\mathsf\{MRR\}\(\\theta\)\-\\mathsf\{MRR\}\_\{\\min\}\}\{\\mathsf\{MRR\}\_\{\\max\}\-\\mathsf\{MRR\}\_\{\\min\}\},\\qquad\\widetilde\{\\mathsf\{Recall\}\}\(\\theta\)=\\frac\{\\mathsf\{Recall\}\(\\theta\)\-\\mathsf\{Recall\}\_\{\\min\}\}\{\\mathsf\{Recall\}\_\{\\max\}\-\\mathsf\{Recall\}\_\{\\min\}\}\.We define the aggregate effectiveness score as

E⁡\(θ\)=𝖬𝖱𝖱~​\(θ\)\+𝖱𝖾𝖼𝖺𝗅𝗅~​\(θ\)2\.E\(\\theta\)=\\frac\{\\widetilde\{\\mathsf\{MRR\}\}\(\\theta\)\+\\widetilde\{\\mathsf\{Recall\}\}\(\\theta\)\}\{2\}\.
The effectiveness\-cost envelope𝒫E\\mathcal\{P\}\_\{E\}is the set when maximizingEEand minimizing𝖯𝖨𝖱𝖢𝖺𝗅𝗅\\mathsf\{PIRCall\}:

𝒫E=\{θ∈Θ:\\displaystyle\\mathcal\{P\}\_\{E\}=\\Bigl\\\{\\theta\\in\\Theta:\{\}∄θ′∈Θsuch thatE\(θ′\)≥E\(θ\)∧𝖯𝖨𝖱𝖢𝖺𝗅𝗅\(θ′\)≤𝖯𝖨𝖱𝖢𝖺𝗅𝗅\(θ\),\\displaystyle\\nexists\\,\\theta^\{\\prime\}\\in\\Theta\\text\{ such that \}E\(\\theta^\{\\prime\}\)\\geq E\(\\theta\)\\land\\mathsf\{PIRCall\}\(\\theta^\{\\prime\}\)\\leq\\mathsf\{PIRCall\}\(\\theta\),with at least one strict inequality\}\.\\displaystyle\\text\{with at least one strict inequality\}\\Bigr\\\}\.
Following the normalized difference construction of Kneedle[Satopaa et al\. \[2011\]](https://arxiv.org/html/2609.36326#bib.bib9), we define

x⁡\(θ\)=log⁡𝖯𝖨𝖱𝖢𝖺𝗅𝗅⁡\(θ\)−log⁡𝖯𝖨𝖱𝖢𝖺𝗅𝗅minlog⁡𝖯𝖨𝖱𝖢𝖺𝗅𝗅max−log⁡𝖯𝖨𝖱𝖢𝖺𝗅𝗅min,y⁡\(θ\)=E⁡\(θ\)−EminEmax−Emin\.x\(\\theta\)=\\frac\{\\log\\mathsf\{PIRCall\}\(\\theta\)\-\\log\\mathsf\{PIRCall\}\_\{\\min\}\}\{\\log\\mathsf\{PIRCall\}\_\{\\max\}\-\\log\\mathsf\{PIRCall\}\_\{\\min\}\},\\qquad y\(\\theta\)=\\frac\{E\(\\theta\)\-E\_\{\\min\}\}\{E\_\{\\max\}\-E\_\{\\min\}\}\.The knee point, which represents the point on the envelope which witness the strongest gain in effectiveness with respect to its PIR cost, is defined asθknee=arg⁡maxθ∈𝒫E⁡\(y⁡\(θ\)−x⁡\(θ\)\)\.\\theta\_\{\\mathrm\{knee\}\}=\\arg\\max\_\{\\theta\\in\\mathcal\{P\}\_\{E\}\}\\left\(y\(\\theta\)\-x\(\\theta\)\\right\)\.

We then chooses the points C1, C2, C3, C4, C5 as:

- •C1: Point C1 with lowest number of PIR calls
- •C2: Point C2 is the knee pointθknee\\theta\_\{\\mathrm\{knee\}\}
- •C3: Point C3 with highest MRR@10 on tune set
- •C4: Point C4 with highest Recall@10 on tune set
- •C5: Point C5 with highest number of PIR calls

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\.10310^\{3\}10410^\{4\}000\.50\.511C1C2 \(knee\)C3C4C5PIR calls / queryEffectivenessEEMS MARCO10210^\{2\}10310^\{3\}000\.50\.511C1C2 \(knee\)C3C4C5PIR calls / querySciFact

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𝒫E\\mathcal\{P\}\_\{E\}, C1,C2,C3,C4,C5 are chosen configurations\.Table 4:Bins configurations selected from the plaintext parameter search\.Table 5:PACMANN configurations selected from the plaintext parameter search\.PACMANN andPILLAR\-Binfollow a similar protocol toPILLAR\-Tree, but instead they*directly*use the recorded WAN time as the cost\. We detail PACMANN’s best configs in Table[5](https://arxiv.org/html/2609.36326#A4.T5)andPILLAR\-Bin’s best in Table[4](https://arxiv.org/html/2609.36326#A4.T4)\.

### D\.2Extensive comparisons

In this section, we plot every different configuration we ran across PACMANN,PILLAR\-BinandPILLAR\-Tree\. We use the same Pareot frontiers as were in Section[5](https://arxiv.org/html/2609.36326#S5)\. We have over2,0002\{,\}000total configurations, which is why we limited our comparison previously\. To keep each plot legible, we only show the entire Pareto frontier and circled points on the frontier with a black outline\. To get Faithfulness and Answer Relevancy for every single different configuration using the GPUs available to us would’ve taken a substantial amount of time, as a result, we decided to include more total configurations but with more basic metrics\. Every plot here only uses MRR and Recall

\(a\)MS MARCO\(b\)SciFact
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\.\(a\)MS MARCO\(b\)SciFact
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\.On the Time Costs\.Figure[6](https://arxiv.org/html/2609.36326#A4.F6)reports quality against per\-query WAN latency, LAN latency, and computation time\. If we fix the budget at thexx\-axis limits \(11s WAN,320320ms LAN, and900900ms computation on MS MARCO;250250ms,3535ms, and2525ms on SciFact\),PILLAR\-Treeachieves the highest MRR@10 and Recall@10 in every panel\.PILLAR\-Binoccupies the low\-latency end of every frontier\. On SciFact,PILLAR\-Binalready exceeds0\.50\.5MRR@10 within8383ms of WAN latency and accounts for50\.0%50\.0\\%of all frontier points\. PACMANN has no configuration on the Pareto frontier in eight of the twelve panels, so it is never the Pareto\-optimal choice\. These eight panels are MRR@10 under WAN latency and both metrics under computation on MS MARCO, and every panel on SciFact except Recall@10 under computation\. In the remaining four panels, PACMANN contributes at most55points\. Across all377377frontier points,97\.1%97\.1\\%are configurations ofPILLAR\-BinorPILLAR\-Tree\.

On the Preprocessing, Communication, and Storage Costs\.Figure[7](https://arxiv.org/html/2609.36326#A4.F7)reports quality against PIR preprocessing time, data sent, and client storage\. All costs are per query except PIR preprocessing and client storage, which are for the entire end\-to\-end run\.*Preprocessing\.*PACMANN has no configuration on the Pareto frontier on MS MARCO or for MRR@10 on SciFact\. This is because its additional rounds of PIR queries require correspondingly more PIR preprocessing\. At thexx\-axis limits \(5050min on MS MARCO,2020s on SciFact\),PILLAR\-Treeachieves the highest quality on both metrics\.*Data sent\.*At thexx\-axis limits \(3434MB on MS MARCO,1\.51\.5MB on SciFact\),PILLAR\-Treeagain achieves the highest quality\. PACMANN occupies the middle of the frontier on MS MARCO \(51\.9%51\.9\\%of points for MRR@10,51\.7%51\.7\\%for Recall@10\) but only11\.8%11\.8\\%and39\.1%39\.1\\%on SciFact\. Even though PACMANN may often be the choice for a low amount of total communication, as we have shown previously, the many rounds practically drag down WAN and LAN latency\.*Client storage\.*PACMANN’s many rounds of interaction let it keep the client\-side cost low, and it reaches near\-maximal quality with under2\.12\.1GB on MS MARCO and under4545MB on SciFact, whereasPILLAR\-Tree’s highest\-quality configurations require over4\.24\.2GB and9090MB, respectively\. The cost of these rounds is paid in latency, as shown in Figure[6](https://arxiv.org/html/2609.36326#A4.F6)\. Despite this, PACMANN does not hold a majority of the frontier, it only has35\.3%35\.3\\%and33\.3%33\.3\\%of the points on MS MARCO \(tied withPILLAR\-Tree\), and45\.5%45\.5\\%and50\.0%50\.0\\%on SciFact\.PILLAR\-Treestill achieves the highest quality at thexx\-axis limits \(6\.36\.3GB and140140MB\)\. Moreover, on MS MARCO nearly every configuration that is viable of every method requires client storage on the order of gigabytes, so PACMANN’s advantage does not change the scale of the client’s cost\. Across all262262frontier points in Figure[7](https://arxiv.org/html/2609.36326#A4.F7),75\.6%75\.6\\%are configurations ofPILLAR\-BinorPILLAR\-Tree, withPILLAR\-Treethe largest share on both datasets \(48\.0%48\.0\\%and41\.6%41\.6\\%\)\.

### D\.3FurtherPILLAR\-Binablation plots

Figure 8:PILLAR\-Binper\-query cost\. Left: varying the hash table size\. Right: varying the number of documents per bin\.
Figure 9:PILLAR\-Binworst\-case client storage\. Left: varying the hash table size\. Right: varying the number of documents per bin\.
Figure 10:PILLAR\-BinPIR preprocessing time \(top\) and retrieval quality \(bottom\)\. Left: varying the hash table size\. Right: varying the number of documents per bin\.We extend thePILLAR\-Binablation of Section[5](https://arxiv.org/html/2609.36326#S5)with system costs, client storage and preprocessing time\. As in the main text, when varying the hash table size we fix the number of documents per bin at1010, and when varying the number of documents per bin we fix the hash table size at11M for MS MARCO and55K for SciFact\. WAN latency, LAN latency, compute \(total running time\) and data sent \(upload and download\) are per query\. Client storage and PIR preprocessing total costs over the entire run\.

WAN, LAN and total compute\.Figure[8](https://arxiv.org/html/2609.36326#A4.F8)\(left\) shows that WAN latency, LAN latency and compute are either not affected by the hash table size increases or show no consistent trend\. Only data sent increases, the same trade\-off we discussed in Section[5](https://arxiv.org/html/2609.36326#S5)Figure[8](https://arxiv.org/html/2609.36326#A4.F8)\(right\) shows that all four costs increase with the number of documents per bin\. For SciFact, the increase is small up to250250documents per bin and steep between250250and500500\.

Figure 11:PILLAR\-Binper\-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\.Storage costs and PIR preprocessing\.Figure[9](https://arxiv.org/html/2609.36326#A4.F9)reports client storage in the worst case, where every hint is completely full\. In practice, client storage is dependent on how many bins are full and ranges from3030\-5050% better\. For MS MARCO, client storage is approximately11GB and does not change with the hash table size\. As we saw in the ablation comparing against PACMANN,PILLAR\-Binthat take up a large client hint tend to not perform well regardless\. For SciFact, client storage increases from1111MB at a hash table size of100100to3030MB at11M, with most of the increase above1010K\. Unlike the hash table size, the number of documents per bin has a large effect on client storage, which increases for SciFact and for MS MARCO\.Figure[10](https://arxiv.org/html/2609.36326#A4.F10)\(top\) shows that, surprisingly, PIR preprocessing time does not depend on the hash table size\. In our implementation, we made heavy use of multithreading to perform pre\-processing, so it is likely that the bottleneck was thrashing related, as a large hash table size \(should\) imply more entries to retrieve PIR hints from\. Preprocessing time increases with the number of documents per bin, from0\.60\.6minutes at1010to4\.94\.9minutes at500500for MS MARCO, and from a few seconds at up to100100to1\.71\.7minutes at500500for SciFact\. This implies that the most important factor is not actually the size of the bin, but instead the size of the entry\. Figure[10](https://arxiv.org/html/2609.36326#A4.F10)\(bottom left\) shows that retrieval quality increases with the hash table size\. For MS MARCO, MRR@10 and Recall@10 remain below0\.010\.01up to100100K and reach0\.0420\.042and0\.0540\.054at11M, still increasing at the largest tested size\. For SciFact, MRR@10 and Recall@10 increase up to5050K, reaching0\.450\.45and0\.530\.53, and see no notable benefit\.

1 or 2\-round PIRPILLAR\-Bincan store the document embeddings directly in the bins and return them with a single PIR query \(Single DB\), or store document IDs in the bins and retrieve the corresponding embeddings from a separate database with a second PIR query \(Separate Embedding DB\)\. Figure[11](https://arxiv.org/html/2609.36326#A4.F11)shows that Single DB has lower or comparable WAN latency, LAN latency, compute and data sent at every tested number of documents per bin, and that the gap grows with the number of documents per bin\. The difference is largest for SciFact: at500500documents per bin, Single DB reduces WAN latency from1\.21\.2s to240240ms, LAN latency from235235ms to7777ms, compute from110110ms to77ms, and data sent from1919MB to7\.87\.8MB\. Single DB is usually cheaper because it removes the second round of PIR, the most expensive component of the protocol\. Future protocols should always aim to minimize PIR rounds\.

## Appendix EProtocol Details

This section gives the detailed protocol figures forPILLAR\-BinandPILLAR\-Tree, together with some implementation details that Section[4](https://arxiv.org/html/2609.36326#S4)suppresses for clarity\. The first concerns what a RAG pipeline actually returns\. A RAG pipeline consumes document*text*, whereas the dense stage ofPILLAR\-Binoutputs embeddings, and an embedding does identify the document it came from\. PACMANN andPILLAR\-Treeare unaffected, since both retrieve document indices in their traversals, butPILLAR\-Bindoes not\. Each entry of the database held bysrvin thePILLAR\-Binprotocol stores an index alongside the embedding, using an extra3232bits per row, and the protocol outputs indices thatclntuses in the final PIR round of protocol[16](https://arxiv.org/html/2609.36326#A5.F16)\. Figure[12](https://arxiv.org/html/2609.36326#A5.F12)gives the construction in full\.

There is another concern regarding storage used by the client\. As described in Section[4](https://arxiv.org/html/2609.36326#S4), the database inPILLAR\-Bindoesn’t store one document per row, like PACMANN orPILLAR\-Tree, but insteadttdocument embeddings per row\. Under a PIR scheme with preprocessing,clntretains a collection of entries in the database, that scale sub\-linearly with the database size, so this falls on client storage rather than on the server alone \(see Appendix[D\.1](https://arxiv.org/html/2609.36326#A4.SS1)\)\. We therefore provide a second variant that splits retrieval into two rounds, the first recovers identifiers from a database of3232\-bit sized rows, and the second recovers the corresponding embeddings from a database holding each document embedding once\. Figure[13](https://arxiv.org/html/2609.36326#A5.F13)gives this variant, which trades one additional round for a client state independent ofRRandtt\.

Figure[15](https://arxiv.org/html/2609.36326#A5.F15)presents the formal construction ofPILLAR\-Treeprotocol\. Finally, Figure[16](https://arxiv.org/html/2609.36326#A5.F16)shows the whole PPRAG pipeline using thePILLAR\-Bin/PILLAR\-Treeconstructions\.

Protocol 1\.a:PILLAR\-Bin\(single\-round variant\)Participants\.Serversrvand clientclnt\.Public parameters\.Corpus𝒞=\{D1,…,DN\}\\mathcal\{C\}=\\\{D\_\{1\},\\dots,D\_\{N\}\\\}; analyzer𝖠𝗇𝖺𝗅𝗒𝗓𝖾\\mathsf\{Analyze\}; embedding function𝖤𝗆𝖻\\mathsf\{Emb\}of dimensiondd; BM25 parameters\(k1,b\)\(k\_\{1\},b\); row countRR; row depthtt; hash functionH:𝒱→\{0,…,R−1\}H:\\mathcal\{V\}\\rightarrow\\\{0,\\dots,R\-1\\\}; batch boundβ\\beta; output sizekk; reserved dummy index⊥\\bot\.Client input\.QueryQQwith𝖠𝗇𝖺𝗅𝗒𝗓𝖾⁡\(Q\)=\(w1,…,w\|Q\|\)\\mathsf\{Analyze\}\(Q\)=\(w\_\{1\},\\dots,w\_\{\|Q\|\}\)\.Preprocessing \(serversrv\)\.1\.srvinitialize empty databaseDBofRRrows\.2\.For eachw∈𝒱w\\in\\mathcal\{V\},srvscores everyD∈𝒞D\\in\\mathcal\{C\}containingwwunder BM25 withwwas a single\-term query, and setsℒw\\mathcal\{L\}\_\{w\}to thetthighest\-scoring documents in descending order, padded with⟨⊥,𝟎⟩\\langle\\bot,\\mathbf\{0\}\\rangleif fewer thanttdocuments containww\. Writeℒw​\[j\]\\mathcal\{L\}\_\{w\}\[j\]for itsjjth document\.3\.srvgroups terms by row:wwbelongs to rowz=H⁡\(w\)z=H\(w\)\. WriteWz=\{w∈𝒱:H⁡\(w\)=z\}W\_\{z\}=\\\{w\\in\\mathcal\{V\}:H\(w\)=z\\\}and letmz=\|Wz\|m\_\{z\}=\|W\_\{z\}\|be the number of terms that collide in rowzz, and fix an arbitrary orderw\(1\),…,w\(mz\)w^\{\(1\)\},\\dots,w^\{\(m\_\{z\}\)\}on them, so that𝒞z=\{ℒw\(1\),…,ℒw\(mz\)\}\\mathcal\{C\}\_\{z\}=\\\{\\mathcal\{L\}\_\{w^\{\(1\)\}\},\\dots,\\mathcal\{L\}\_\{w^\{\(m\_\{z\}\)\}\}\\\}are the ordered lists competing for rowzz\.4\.srvfills rowzzby interleaving the lists of𝒞z\\mathcal\{C\}\_\{z\}round\-robin, one rank at a time: thejjth document of theiith list goes to position\(j−1\)​mz\+i\(j\-1\)m\_\{z\}\+i:DB​\[z\]​\[\(j−1\)​mz\+i\]←ℒw\(i\)​\[j\]\\textsf\{DB\}\[z\]\[\(j\-1\)m\_\{z\}\+i\]\\leftarrow\\mathcal\{L\}\_\{w^\{\(i\)\}\}\[j\]\. The row therefore holds the best document of every colliding term, then the second\-best of every term, and so on\.5\.srvdiscards duplicates, which arise when a document appears in two colliding lists, and then truncates each row to its firstttdocuments\. A row withmz=0m\_\{z\}=0is left empty\.6\.srvthen replaces all document text with embeddings and an index: For every row index0<z≤R0<z\\leq Rand offset0<x≤t0<x\\leq t,srvretrievesD=DB​\[z\]​\[x\]D=\\textsf\{DB\}\[z\]\[x\], computeseD=𝖤𝗆𝖻⁡\(D\)e\_\{D\}=\\mathsf\{Emb\}\(D\)and setsDB​\[z\]​\[x\]=⟨id​\(D\),eD⟩\\textsf\{DB\}\[z\]\[x\]=\\langle\\textsf\{id\}\(D\),e\_\{D\}\\rangle\.7\.srvruns the PIR preprocessing phase overDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}withclnt, who stores the resulting private state\.Retrieval\.1\.clntcomputes𝖠𝗇𝖺𝗅𝗒𝗓𝖾⁡\(Q\)\\mathsf\{Analyze\}\(Q\)and the row indicesri←H⁡\(wi\)r\_\{i\}\\leftarrow H\(w\_\{i\}\)fori≤\|Q\|i\\leq\|Q\|, removing repeated indices\.2\.clntfixes the batch to exactlyβ\\betaindices and if\|Q\|\>β\|Q\|\>\\betait retains the firstβ\\betaor if\|Q\|<β\|Q\|<\\betathey pad with random indices from\{0,…,R−1\}\\\{0,\\dots,R\-1\\\}\.3\.clntsends a single batched PIR query for theseβ\\betaindices and recovers the correspondingβ\\betarows ofDBfromsrv’s response and its private state\.4\.clntlocally discards entries with index⊥\\botand duplicate indices, forming a candidate pool𝒟cand\\mathcal\{D\}\_\{\\mathrm\{cand\}\}of at mostβ​t\\beta tembeddings\.5\.clntcomputes𝐞Q=𝖤𝗆𝖻⁡\(Q\)\\mathbf\{e\}\_\{Q\}=\\mathsf\{Emb\}\(Q\)locally and ranks𝒟cand\\mathcal\{D\}\_\{\\mathrm\{cand\}\}bycos⁡\(𝐞Q,𝐞D\)\\cos\(\\mathbf\{e\}\_\{Q\},\\mathbf\{e\}\_\{D\}\)\.6\.clntoutputs thekkdocument indices of highest similarity to the query\.

Figure 12:Formal specification ofPILLAR\-Bin\(single\-round variant\)\.srvobserves exactlyβ\\betabatched PIR queries, and holds a databaseDBofRRrows\. Each row is an ordered list ofttentries and an entry is a pair⟨id​\(D\),𝖤𝗆𝖻​\(D\)⟩\\langle\\textsf\{id\}\(D\),\\mathsf\{Emb\}\(D\)\\rangleof a3232\-bit index and add\-dimensional vector\.Protocol 1\.b:PILLAR\-Bin\(two\-round variant\)Participants\.Serversrvand clientclnt\.Public parameters\.Identical to Protocol 1\.a, with a second batch boundβ′\\beta^\{\\prime\}\.Client input\.QueryQQwith𝖠𝗇𝖺𝗅𝗒𝗓𝖾⁡\(Q\)=\(w1,…,w\|Q\|\)\\mathsf\{Analyze\}\(Q\)=\(w\_\{1\},\\dots,w\_\{\|Q\|\}\)\.Preprocessing \(serversrv\)\.1\.srvbuildsDBexactly as in Protocol 1\.a preprocessing, steps 1–4\.2\.srvreplaces all document text with a unique index only\. For every row index0<z≤R0<z\\leq Rand offset0<x≤t0<x\\leq t,srvretrievesD=DB​\[z\]​\[x\]D=\\textsf\{DB\}\[z\]\[x\]and setsDB​\[z\]​\[x\]=id​\(D\)\\textsf\{DB\}\[z\]\[x\]=\\textsf\{id\}\(D\), the index alone\.3\.For eachDj∈𝒞D\_\{j\}\\in\\mathcal\{C\},srvinitializes a databaseDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}by writingeD=𝖤𝗆𝖻⁡\(Dj\)e\_\{D\}=\\mathsf\{Emb\}\(D\_\{j\}\)to rowjjofDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}\.4\.srvruns the PIR preprocessing phase overDBand overDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}withclnt, who stores the resulting private states\.Retrieval\.1\.clntcomputes retrieval steps 1–2 of Protocol 1\.a exactly\.2\.clntsends one batched PIR query toDB, and recoversβ\\betarows of indices\.3\.clntlocally discards⊥\\botand duplicate indices, obtaining a setIIof, at most,β⋅t\\beta\\cdot tdistinct indices\.4\.clntfixesIIto exactlyβ′\\beta^\{\\prime\}indices: if\|I\|\>β′\|I\|\>\\beta^\{\\prime\}it retains the firstβ′\\beta^\{\\prime\}indices, if\|I\|<β′\|I\|<\\beta^\{\\prime\}it appends indices drawn randomly from\{1,…,R\}\\\{1,\\dots,R\\\}\.5\.clntsends a single batched PIR query using theseβ′\\beta^\{\\prime\}indices toDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}and recovers the corresponding embeddings\.6\.clntcomputes𝐞Q=𝖤𝗆𝖻⁡\(Q\)\\mathbf\{e\}\_\{Q\}=\\mathsf\{Emb\}\(Q\)locally and ranks the documents ofIIbycos⁡\(𝐞Q,𝐞D\)\\cos\(\\mathbf\{e\}\_\{Q\},\\mathbf\{e\}\_\{D\}\), ignoring the embeddings returned for padding indices\.7\.clntoutputs thekkdocument indices of highest similarity to the query\.

Figure 13:Formal specification ofPILLAR\-Bin\(two\-round variant\)\. Thesrvstores two databases, one databaseDBofRRrows ofttindices each, and a databaseDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}ofNNrows, rowjjholding the single embedding𝖤𝗆𝖻⁡\(Dj\)\\mathsf\{Emb\}\(D\_\{j\}\)\. The primary difference is that the server only has to hold one embedding per entry, instead ofttembeddings per entry\.Protocol 1: BM25\-Tree — Privacy\-Preserving Lexical Pruning with Dense RankingParticipants\.Serversrvand clientclntPublic Parameters\.Corpus𝒞\\mathcal\{C\}ofNNdocuments:𝒞=\{D1,…,DN\}\\mathcal\{C\}=\\\{D\_\{1\},\\dots,D\_\{N\}\\\};𝒱\\mathcal\{V\}be set of all unique terms within all the documents in𝒞\\mathcal\{C\}; leaf block sizeBB, sub\-block sizess, tree branching factorrr, beam widthWW,𝒯\\mathcal\{T\}be set of all tree nodes,𝒯ℓ\\mathcal\{T\}\_\{\\ell\}be set of tree nodes on levelℓ\\ell, stage 2 number of retrieved sub\-blockksk\_\{s\}, maximum unique query termsq⋆q^\{\\star\},mmpublic hash functionsh1,…​hm:𝒱×𝒯→\{0,1\}⋆h\_\{1\},\\dots h\_\{m\}:\\mathcal\{V\}\\times\\mathcal\{T\}\\to\\\{0,1\\\}^\{\\star\}; Cuckoo Hash table load factorα\\alpha; target result sizekk;Client Input\.QueryQ=\{w1,…,wq⋆\}Q=\\\{w\_\{1\},\\ldots,w\_\{q^\{\\star\}\}\\\}\.Server state \(initialized\)\.1\.Letℋ=1\+⌈logr⁡\(N/B\)⌉\\mathcal\{H\}=1\+\\lceil\\log\_\{r\}\(N/B\)\\rceilbe height ofrr\-ary tree\. For each levelℓ∈\[ℋ\]\\ell\\in\[\\mathcal\{H\}\],srvcomputesNℓN\_\{\\ell\}the number of pairs\(w,ℬ\)∈𝒱×𝒯ℓ\(w,\\mathcal\{B\}\)\\in\\mathcal\{V\}\\times\\mathcal\{T\}\_\{\\ell\}such thatσw​\(ℬ\)≠0\\sigma\_\{w\}\(\\mathcal\{B\}\)\\neq 0\.srvthen initializes a databaseDBt​r​e​e,ℓ\\textsf\{DB\}\_\{tree,\\ell\}of⌈Nℓ/α⌉\\lceil N\_\{\\ell\}/\\alpha\\rceilrows for eachℓ∈\[ℋ\]\\ell\\in\[\\mathcal\{H\}\]\.2\.srvinitialize an empty databaseDBv​e​c​t​o​r\\textsf\{DB\}\_\{vector\}of⌈N/s⌉\\lceil N/s\\rceilrows\.Preprocessing \(serversrv\)1\.For each nodeℬi,ℓ\\mathcal\{B\}\_\{i,\\ell\}in levelℓ\\ellfor1≤ℓ≤ℋ−11\\leq\\ell\\leq\\mathcal\{H\}\-1\(a\)srvcomputesσw​\(ℬi,ℓ\+1,j\)\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,j\}\)for child nodeℬi,ℓ\+1,j\\mathcal\{B\}\_\{i,\\ell\+1,j\}ofℬi,ℓ\\mathcal\{B\}\_\{i,\\ell\}\(j∈\[r\]j\\in\[r\]\) and all wordswwthat appears in documents inℬi,ℓ\\mathcal\{B\}\_\{i,\\ell\}\.\(b\)For each wordw∈ℬi,ℓw\\in\\mathcal\{B\}\_\{i,\\ell\}, the tuple\(w,id​\(ℬi,ℓ\),σw​\(ℬi,ℓ\+1,1\),…,σw​\(ℬi,ℓ\+1,r\)\)\(w,\\textsf\{id\}\(\\mathcal\{B\}\_\{i,\\ell\}\),\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,1\}\),\\dots,\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,r\}\)\)ofr\+2r\+2fields are added to the databaseDBt​r​e​e,ℓ\\textsf\{DB\}\_\{tree,\\ell\}using Cuckoo Hash rule on input\(w,id​\(ℬi,ℋ\)\)\(w,\\textsf\{id\}\(\\mathcal\{B\}\_\{i,\\mathcal\{H\}\}\)\)overmmhash functionsh1,…,hmh\_\{1\},\\dots,h\_\{m\}\.2\.For each leaf blockℬ\\mathcal\{B\},srvcomputes the score of their sub\-blocks𝒮​ℬ1,…,𝒮​ℬ⌈B/s⌉\\mathcal\{SB\}\_\{1\},\\dots,\\mathcal\{SB\}\_\{\\lceil B/s\\rceil\}of sizesswith respect to each wordwwappearing in the block, store\(w,id​\(ℬ\),σw​\(𝒮​ℬ1\),…,σw​\(𝒮​ℬ⌈B/s⌉\)\)\(w,\\textsf\{id\}\(\\mathcal\{B\}\),\\sigma\_\{w\}\(\\mathcal\{SB\}\_\{1\}\),\\dots,\\sigma\_\{w\}\(\\mathcal\{SB\}\_\{\\lceil B/s\\rceil\}\)\)toDBt​r​e​e,ℋ\\textsf\{DB\}\_\{tree,\\mathcal\{H\}\}using Cuckoo Hash on input\(w,id​\(ℬ\)\)\(w,\\textsf\{id\}\(\\mathcal\{B\}\)\)andmmhash functionsh1,…,hmh\_\{1\},\\dots,h\_\{m\}\.3\.For each sub\-block𝒮​ℬ\\mathcal\{SB\}at positionp=id​\(𝒮​ℬ\)p=\\textsf\{id\}\(\\mathcal\{SB\}\), store at rowppofDBv​e​c​t​o​r\\textsf\{DB\}\_\{vector\}the tuple\(eD1,…,eDs\)\(e\_\{D\_\{1\}\},\\dots,e\_\{D\_\{s\}\}\)the embedding vectors ofssdocumentsD1,…,DsD\_\{1\},\\dots,D\_\{s\}within𝒮​ℬ\\mathcal\{SB\}\.

Figure 14:The BM25\-Tree protocol for privacy\-preserving lexical pruning with dense re\-ranking \(Part I: setup and preprocessing\)\.Protocol 1: BM25\-Tree \(continued\)Stage 1: Tree Traversal1\.clntinitializesF0=\{ℬ1,0\}F\_\{0\}=\\\{\\mathcal\{B\}\_\{1,0\}\\\}, whereℬ1,0\\mathcal\{B\}\_\{1,0\}is the root node of the tree\.2\.For each levelℓ=0,…,ℋ−1\\ell=0,\\dots,\\mathcal\{H\}\-1do\(a\)LetFℓ=\{ℬ1,ℓ⋆,…,ℬ\|Fℓ\|,ℓ⋆\}F\_\{\\ell\}=\\\{\\mathcal\{B\}\_\{1,\\ell\}^\{\\star\},\\dots,\\mathcal\{B\}\_\{\|F\_\{\\ell\}\|,\\ell\}^\{\\star\}\\\}be the set of candidate nodes at levelℓ\\ell\. For eachw∈Qw\\in Q,clntsends PIR tosrv, retrieving rows\(ha​\(w,id​\(ℬi,ℓ⋆\)\)\)a∈\[m\]i∈\[\|Fℓ\|\]\\left\(h\_\{a\}\\\!\\left\(w,\\textsf\{id\}\(\\mathcal\{B\}\_\{i,\\ell\}^\{\\star\}\)\\right\)\\right\)\_\{\\begin\{subarray\}\{c\}a\\in\[m\]\\\\ i\\in\[\|F\_\{\\ell\}\|\]\\end\{subarray\}\}fromDBt​r​e​e,ℓ\\textsf\{DB\}\_\{tree,\\ell\}, for a total ofm×\|Fℓ\|m\\times\|F\_\{\\ell\}\|rows\.\(b\)For eachi∈\[\|Fℓ\|\]i\\in\[\|F\_\{\\ell\}\|\],clntchecks whether any retrieved row has its first two fields equal towwandid​\(ℬi,ℓ⋆\)\\textsf\{id\}\(\\mathcal\{B\}\_\{i,\\ell\}^\{\\star\}\)\. If none does,clntsetsσw​\(ℬi,ℓ\+1,j\)=0\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,j\}\)=0, for allj∈\[r\]j\\in\[r\], whereℬi,ℓ\+1,j\\mathcal\{B\}\_\{i,\\ell\+1,j\}is thejj\-th child ofℬi,ℓ⋆\\mathcal\{B\}\_\{i,\\ell\}^\{\\star\}\. Otherwise,clntsetsσw​\(ℬi,ℓ\+1,j\)\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,j\}\)to the\(j\+2\)\(j\+2\)\-th field of the matching row\.\(c\)clntcomputesσQ​\(ℬi,ℓ\+1,j\)=∑w∈Qσw​\(ℬi,ℓ\+1,j\)\\sigma\_\{Q\}\(\\mathcal\{B\}\_\{i,\\ell\+1,j\}\)=\\sum\_\{w\\in Q\}\\sigma\_\{w\}\(\\mathcal\{B\}\_\{i,\\ell\+1,j\}\)for every child of every node inFℓF\_\{\\ell\}\.\(d\)clntlocally ranks these child nodes according toσQ\\sigma\_\{Q\}and letsFℓ\+1F\_\{\\ell\+1\}be the set of the topmin⁡\{W,\|𝒯ℓ\+1\|\}\\min\\\{W,\|\\mathcal\{T\}\_\{\\ell\+1\}\|\\\}nodes\.3\.clntoutputsFℋ=\{ℬ1,ℋ⋆,…,ℬW,ℋ⋆\}F\_\{\\mathcal\{H\}\}=\\\{\\mathcal\{B\}\_\{1,\\mathcal\{H\}\}^\{\\star\},\\dots,\\mathcal\{B\}\_\{W,\\mathcal\{H\}\}^\{\\star\}\\\}as topWWleaf block\.Stage 2: Sub\-Block Retrieval1\.For eachw∈Qw\\in Qdo\(a\)clntsends PIR tosrv, retrieving rows\(hi∈\[m\]​\(w,id​\(ℬ1,ℋ⋆\)\),…,hi∈\[m\]​\(w,id​\(ℬW,ℋ⋆\)\)\)\(h\_\{i\\in\[m\]\}\(w,\\textsf\{id\}\(\\mathcal\{B\}\_\{1,\\mathcal\{H\}\}^\{\\star\}\)\),\\dots,h\_\{i\\in\[m\]\}\(w,\\textsf\{id\}\(\\mathcal\{B\}\_\{W,\\mathcal\{H\}\}^\{\\star\}\)\)\)\(m×Wm\\times Wrows total\) fromDBt​r​e​e,ℋ\\textsf\{DB\}\_\{tree,\\mathcal\{H\}\}\(b\)For eachi∈\[W\]i\\in\[W\],clntchecks if any of the retrieved data has the first two field equal towwandid​\(ℬi,ℋ⋆\)\\textsf\{id\}\(\\mathcal\{B\}\_\{i,\\mathcal\{H\}\}^\{\\star\}\)\. If there are non,clntsetsσw​\(𝒮​ℬi,ℋ,j\)=0\\sigma\_\{w\}\(\\mathcal\{SB\}\_\{i,\\mathcal\{H\},j\}\)=0for all sub\-block𝒮​ℬi,ℋ,j\\mathcal\{SB\}\_\{i,\\mathcal\{H\},j\}ofℬi,ℋ\\mathcal\{B\}\_\{i,\\mathcal\{H\}\}, elseclntmatches correspondingσw​\(𝒮​ℬi,ℋ,j\)\\sigma\_\{w\}\(\\mathcal\{SB\}\_\{i,\\mathcal\{H\},j\}\)with thej\+2j\+2\-th retrieved value of the corresponding row matches\(w,ℬi,ℋ\)\(w,\\mathcal\{B\}\_\{i,\\mathcal\{H\}\}\)\.2\.clntcomputesσQ​\(𝒮​ℬi,ℋ,j\)=∑w∈Qσw​\(𝒮​ℬi,ℋ,j\)\\sigma\_\{Q\}\(\\mathcal\{SB\}\_\{i,\\mathcal\{H\},j\}\)=\\sum\\limits\_\{w\\in Q\}\\sigma\_\{w\}\(\\mathcal\{SB\}\_\{i,\\mathcal\{H\},j\}\)for all sub\-blocks of top\-WWleaf block\.3\.clntlocally rank and get set of topksk\_\{s\}sub\-blocks𝒮​ℬ1⋆,…,𝒮​ℬks⋆\\mathcal\{SB\}\_\{1\}^\{\\star\},\\dots,\\mathcal\{SB\}\_\{k\_\{s\}\}^\{\\star\}Stage 3: Dense Retrieval and Ranking1\.clntsends PIR query tosrv, retrieving rows\(id​\(𝒮​ℬ1⋆\),…,id​\(𝒮​ℬks⋆\)\)\(\\textsf\{id\}\(\\mathcal\{SB\}\_\{1\}^\{\\star\}\),\\dots,\\textsf\{id\}\(\\mathcal\{SB\}\_\{k\_\{s\}\}^\{\\star\}\)\)fromDBv​e​c​t​o​r\\textsf\{DB\}\_\{vector\}2\.Let𝒟c​a​n​d=\{D1⋆,…,Dks×s⋆\}\\mathcal\{D\}\_\{cand\}=\\\{D\_\{1\}^\{\\star\},\\dots,D\_\{k\_\{s\}\\times s\}^\{\\star\}\\\}be set ofks×sk\_\{s\}\\times sdocuments whose embedding vectors are retrieved\.clntlocally computescos⁡\(eQ,eDj⋆\)\\cos\(e\_\{Q\},e\_\{D\_\{j\}^\{\\star\}\}\)for allj∈\[ks×s\]j\\in\[k\_\{s\}\\times s\]and ranks the score3\.Client output topkkdocuments in𝒟c​a​n​d\\mathcal\{D\}\_\{cand\}with highest similarity\.

Figure 15:The BM25\-Tree protocol for privacy\-preserving lexical pruning with dense re\-ranking\.Protocol 3: Full PPRAG based onPILLARParticipants\.Serversrvand clientclnt\.Public parameters\.Corpus𝒞\\mathcal\{C\}ofNNdocuments:𝒞=\{D1,…,DN\}\\mathcal\{C\}=\\\{D\_\{1\},\\dots,D\_\{N\}\\\}, Set𝗉𝖺𝗋𝖺𝗆𝗌\\mathsf\{params\}of parameters forPILLAR\(PILLAR\-Bin/PILLAR\-Tree\) retrieval algorithm\.Client input\.Keyword queryQ=\{w1,…,w\|Q\|\}Q=\\\{w\_\{1\},\\dots,w\_\{\|Q\|\}\\\}\.Server state \(initialized / preprocessing\)\.1\.srvrunsPILLARinitialization on𝗉𝖺𝗋𝖺𝗆𝗌\\mathsf\{params\}2\.srvrunsPILLARpreprocessing on𝒞,𝗉𝖺𝗋𝖺𝗆𝗌\\mathcal\{C\},\\mathsf\{params\}3\.srvandclntpreprocess𝒞\\mathcal\{C\}for PIR, each documentDi∈𝒞D\_\{i\}\\in\\mathcal\{C\}associate with an identifieri∈\[N\]i\\in\[N\]\.Retrieval1\.clntandsrvparticipate in private retrievalPILLARprotocol onQQand𝒞\\mathcal\{C\},clntreceive indices top\-kkdocuments in𝒞\\mathcal\{C\}with respect toQQ\. Call the set𝖨𝖣t​o​p−k=\{D1⋆,…,Dk⋆\}\\mathsf\{ID\}\_\{top\-k\}=\\\{D\_\{1\}^\{\\star\},\\dots,D\_\{k\}^\{\\star\}\\\}2\.clntruns PIR to retrieve content ofkkdocumentsD1⋆,…,Dk⋆D\_\{1\}^\{\\star\},\\dots,D\_\{k\}^\{\\star\}\.Generationclntruns local LLM to generate answer with input queryQQandkkdocumentsD1⋆,…,Dk⋆D\_\{1\}^\{\\star\},\\dots,D\_\{k\}^\{\\star\}, output answer𝒜\\mathcal\{A\}

Figure 16:PILLAR\-based PPRAG protocol\.clntandsrvparticipates in online secure retrieval beforeclntruns inference on its local LLM\.
## Appendix FComplexity Analysis

### F\.1Notation

We denote the cost of a batch PIR call onψ\\psirows over a database ofℛ\\mathcal\{R\}rows, each row consist ofCCfields asPIRCost​\(ψ,ℛ,C\)\\texttt\{PIRCost\}\(\\psi,\\mathcal\{R\},C\)\. For Batch PianoPIR implementation from PACMANN[Zhou et al\. \[2024b\]](https://arxiv.org/html/2609.36326#bib.bib1), the cost isO~​\(C​ℛ​ψ\)\\widetilde\{O\}\(C\\sqrt\{\\mathcal\{R\}\\psi\}\)

### F\.2PILLAR\-BinComplexity

##### Round complexity\.

There are two variants ofPILLAR\-Bin\. For the first variant in Figure[13](https://arxiv.org/html/2609.36326#A5.F13), the client runs two rounds of communication: The first round to retrieve\|Q\|\|Q\|rows from the database, the second round to retrieve the document embedding corresponding to the document indices retrieved in the first round\. For the second variant in Figure[12](https://arxiv.org/html/2609.36326#A5.F12),clntrun a single round and retrieve the embeddings directly fromsrvand rank those\|Q\|×t\|Q\|\\times tretrieved embeddings locally\.

##### PIR cost\.

The number of rows being fetched areβ\\betafor the first round over a total ofRRrows, where each row has an average ofO⁡\(\|𝒱\|​t/R\)O\(\|\\mathcal\{V\}\|t/R\)document IDs, andO⁡\(β′×t\)O\(\\beta^\{\\prime\}\\times t\)rows for the second round over a database ofNNrows, each withddfields\. Thus, the total cost of thePILLAR\-Bin\(2\-round\) is:PIRCost​\(β,R,\|𝒱\|​t/R\)\+PIRCost​\(t​β′,N,d\)\\boxed\{\\texttt\{PIRCost\}\(\\beta,R,\|\\mathcal\{V\}\|t/R\)\+\\texttt\{PIRCost\}\(t\\beta^\{\\prime\},N,d\)\}\.

For thePILLAR\-Bin\(1\-round\), the complexity is simplyβ\\betaqueries over a database ofRRrows, each withttdocument embeddings, resulting in total PIR cost ofPIRCost​\(β,R,t​d\)\\boxed\{\\texttt\{PIRCost\}\(\\beta,R,td\)\}

##### Local computation\.

The client locally computes cosine distance between the query embedding and all retrieved document embeddings, incurringO⁡\(\|Q\|​t​d\)O\(\|Q\|td\)computation complexity at client\.

### F\.3PILLAR\-TreeComplexity

##### Round Complexity\.

The client runs a total ofℋ\+1\\mathcal\{H\}\+1rounds: Firstℋ−1\\mathcal\{H\}\-1rounds to perform interactive tree traversal, 1 round for sub\-block retrieval, and 1 round for embedding retrieval\.

##### PIR cost\.

\(1\) For tree traversal, the number of rows being fetched on levelℓ\\ellism​W​q⋆mWq^\{\\star\}over a database of⌈Nℓ/α⌉\\lceil N\_\{\\ell\}/\\alpha\\rceilrows, each row consist ofr\+2r\+2fields, resulting a cost ofPIRCost​\(m​W​q⋆,⌈Nℓ/α⌉,r\+2\)\\texttt\{PIRCost\}\(mWq^\{\\star\},\\lceil N\_\{\\ell\}/\\alpha\\rceil,r\+2\)\. \(2\) For sub\-block retrieval, the client fetchesm​W​q⋆mWq^\{\\star\}over a vector of⌈Nℋ/α⌉\\lceil N\_\{\\mathcal\{H\}\}/\\alpha\\rceilrows each with⌈B/s⌉\+2\\lceil B/s\\rceil\+2fields, resulting in aPIRCost​\(m​W​q⋆,⌈Nℋ/α⌉,⌈B/s⌉\+2\)\\texttt\{PIRCost\}\(mWq^\{\\star\},\\lceil N\_\{\\mathcal\{H\}\}/\\alpha\\rceil,\\lceil B/s\\rceil\+2\)\. \(3\) For embedding retrieval, the client fetchesksk\_\{s\}rows overDBv​e​c​t​o​r\\textsf\{DB\}\_\{vector\}of⌈N/s⌉\\lceil N/s\\rceilrows, each row hass​dsdfields, resultingPIRCost​\(ks,⌈N/s⌉,s​d\)\\texttt\{PIRCost\}\(k\_\{s\},\\lceil N/s\\rceil,sd\)cost\.

Hence, the total PIR cost of thePILLAR\-Treeprotocol is

PIRCostt​r​e​e=∑ℓ=1ℋ−1PIRCost​\(m​W​q⋆,⌈Nℓ/α⌉,r\+2\)\+PIRCost​\(m​W​q⋆,⌈Nℋ/α⌉,⌈B/s⌉\+2\)\+PIRCost​\(ks,⌈N/s⌉,s​d\)\\boxed\{\\begin\{aligned\} \\texttt\{PIRCost\}\_\{tree\}=&\\sum\\limits\_\{\\ell=1\}^\{\\mathcal\{H\}\-1\}\\texttt\{PIRCost\}\(mWq^\{\\star\},\\lceil N\_\{\\ell\}/\\alpha\\rceil,r\+2\)\\\\ &\+\\texttt\{PIRCost\}\(mWq^\{\\star\},\\lceil N\_\{\\mathcal\{H\}\}/\\alpha\\rceil,\\lceil B/s\\rceil\+2\)\\\\ &\+\\texttt\{PIRCost\}\(k\_\{s\},\\lceil N/s\\rceil,sd\)\\end\{aligned\}\}

##### Local computation\.

The client local computation involves computing block score at each level between the input query and retrieved blocks’ children\. This costsO⁡\(m​W​r​q⋆\)O\(mWrq^\{\\star\}\)at each level fromℓ=2,…,ℋ−1\\ell=2,\\dots,\\mathcal\{H\}\-1\(the first level has only 1 node so it does not require any computation\)\. At sub block level, client performs the subblock score computation, costingO⁡\(m​W​⌈B/s⌉​q⋆\)O\(mW\\lceil B/s\\rceil q^\{\\star\}\)\. Finally, the client computes the cosine similarity between his query andks×sk\_\{s\}\\times sretrieved document embeddings, resulting inO⁡\(ks​s​d\)O\(k\_\{s\}sd\)computation\.

Thus, the client local computation costsO⁡\(m​W​r​ℋ​q⋆\+m​W​⌈B/s⌉​q⋆\+ks​s​d\)\\boxed\{O\(mWr\\mathcal\{H\}q^\{\\star\}\+mW\\lceil B/s\\rceil q^\{\\star\}\+k\_\{s\}sd\)\}

## Appendix GDetailed Security Analysis

We prove that both protocols provide security against a semi\-honest server\. Security is formally defined via the standard simulation paradigm\.

We first define computationally private PIR ideal functionality as:

###### Definition 1\(Computationally Private PIR\[[Kushilevitz and Ostrovsky, 1997](https://arxiv.org/html/2609.36326#bib.bib7),[Chor and Gilboa, 1997](https://arxiv.org/html/2609.36326#bib.bib6)\]\)\.

A single\-server PIR schemeΠP​I​R=\(𝖰𝗎𝖾𝗋𝗒,𝖠𝗇𝗌𝗐𝖾𝗋,𝖣𝖾𝖼𝗈𝖽𝖾\)\\Pi\_\{PIR\}=\(\\mathsf\{Query\},\\mathsf\{Answer\},\\mathsf\{Decode\}\)over a databaseD​BDBofNNrecords satisfies:

1. 1\.Correctness:For any indexi∈\[N\]i\\in\[N\]: Pr\[𝖣𝖾𝖼𝗈𝖽𝖾\(𝖠𝗇𝗌𝗐𝖾𝗋\(DB,𝖰𝗎𝖾𝗋𝗒\(i\)\)\)=DB\[i\]\]≥1−𝗇𝖾𝗀𝗅\(λ\)\.\\Pr\[\\mathsf\{Decode\}\(\\mathsf\{Answer\}\(DB,\\mathsf\{Query\}\(i\)\)\)=DB\[i\]\]\\geq 1\-\\mathsf\{negl\}\(\\lambda\)\.
2. 2\.Computationally Private:for all indicesi,j∈\[N\]i,j\\in\[N\]and all PPT distinguishers𝒟\\mathcal\{D\}: \|Pr\[𝒟\(𝖰𝗎𝖾𝗋𝗒Π\(i\)\)=1\]−Pr\[𝒟\(𝖰𝗎𝖾𝗋𝗒Π\(j\)\)=1\]\|≤𝗇𝖾𝗀𝗅\(λ\)\.\\Bigl\|\\Pr\\bigl\[\\mathcal\{D\}\(\\mathsf\{Query\}\_\{\\Pi\}\(i\)\)=1\\bigr\]\-\\Pr\\bigl\[\\mathcal\{D\}\(\\mathsf\{Query\}\_\{\\Pi\}\(j\)\)=1\\bigr\]\\Bigr\|\\leq\\mathsf\{negl\}\(\\lambda\)\.

Before stating the main theorems, we establish a composition lemma that underpins the security ofPILLAR\-Tree’s multi\-round interaction\.

###### Lemma 2\(Sequential PIR Composition\)\.

LetΠP​I​R\\Pi\_\{PIR\}be a computationally private PIR scheme\. LetT=T⁡\(λ\)T=T\(\\lambda\)be a polynomial\. Any protocol that issues a sequence ofTTindependent PIR queries, whereTTis determined solely by public parameters, remains computationally private against a semi\-honest server\.

###### Proof\.

Define a sequence of hybrid experiments𝖧0,𝖧1,…,𝖧T\\mathsf\{H\}\_\{0\},\\mathsf\{H\}\_\{1\},\\ldots,\\mathsf\{H\}\_\{T\}where𝖧ℓ\\mathsf\{H\}\_\{\\ell\}denotes the distribution in which the firstℓ\\ellPIR queries are replaced by simulated queries𝖰𝗎𝖾𝗋𝗒Π​\(ui\)\\mathsf\{Query\}\_\{\\Pi\}\(u\_\{i\}\)for independently uniformui←$\[N\]u\_\{i\}\\xleftarrow\{\\$\}\[N\], while the remainingT−ℓT\-\\ellqueries are real\.𝖧0\\mathsf\{H\}\_\{0\}is the real server view;𝖧T\\mathsf\{H\}\_\{T\}is the fully simulated view\.

By Definition[1](https://arxiv.org/html/2609.36326#Thmdefinition1), for eachℓ∈\[T\]\\ell\\in\[T\]and every PPT distinguisher𝒟\\mathcal\{D\}:

\|Pr\[𝒟\(𝖧ℓ−1\)=1\]−Pr\[𝒟\(𝖧ℓ\)=1\]\|≤𝗇𝖾𝗀𝗅\(λ\)\.\\bigl\|\\Pr\[\\mathcal\{D\}\(\\mathsf\{H\}\_\{\\ell\-1\}\)=1\]\-\\Pr\[\\mathcal\{D\}\(\\mathsf\{H\}\_\{\\ell\}\)=1\]\\bigr\|\\leq\\mathsf\{negl\}\(\\lambda\)\.Summing overT=poly⁡\(λ\)T=\\mathrm\{poly\}\(\\lambda\)hybrids, the total distinguishing advantage is at mostT⋅𝗇𝖾𝗀𝗅⁡\(λ\)=𝗇𝖾𝗀𝗅⁡\(λ\)T\\cdot\\mathsf\{negl\}\(\\lambda\)=\\mathsf\{negl\}\(\\lambda\), completing the proof\. ∎

###### Theorem 1\(Security ofPILLAR\-Bin\(1\-round\)\)\.

SupposeΠP​I​R\\Pi\_\{PIR\}is a computationally private PIR scheme \(Definition[1](https://arxiv.org/html/2609.36326#Thmdefinition1)\)\. Then Protocol 1 \(PILLAR\-Bin, Figure[12](https://arxiv.org/html/2609.36326#A5.F12)\) is secure against a semi\-honest server\.

###### Proof\.

Server’s real view\.The serversrvperforms all preprocessing locally and therefore already knows the full hash table\. During retrieval,srv’s view consists solely of theβ\\betaPIR queries\{𝖰𝗎𝖾𝗋𝗒Π​\(ri\)\}i=1β\\\{\\mathsf\{Query\}\_\{\\Pi\}\(r\_\{i\}\)\\\}\_\{i=1\}^\{\\beta\}issued by the client, whereri=H⁡\(wi\)modRr\_\{i\}=H\(w\_\{i\}\)\\bmod Rfor keywordwi∈𝒱∪\{⊥\}w\_\{i\}\\in\\mathcal\{V\}\\cup\\\{\\bot\\\}in the padded/truncatedQQ\. No other message passes fromclnttosrv\.

Simulation\.Construct𝖲𝗂𝗆\\mathsf\{Sim\}as follows: given only the public parameters\(N,R,k,λ\)\(N,R,k,\\lambda\)and the fixed query lengthβ\\beta, output\{𝖰𝗎𝖾𝗋𝗒Π​\(ui\)\}i=1β\\\{\\mathsf\{Query\}\_\{\\Pi\}\(u\_\{i\}\)\\\}\_\{i=1\}^\{\\beta\}where eachui←$\[R\]u\_\{i\}\\xleftarrow\{\\$\}\[R\]is independently uniform\.

Indistinguishability\.The simulated view consists ofβ\\betauniformly random PIR queries; the real view consists ofβ\\betaPIR queries for indicesr1,…,rβ∈\[R\]r\_\{1\},\\ldots,r\_\{\\beta\}\\in\[R\]determined by the query keywords\. By Lemma[2](https://arxiv.org/html/2609.36326#Thmdefinition2)\(applied with database sizeRRandT=βT=\\betaqueries\), the real and simulated views are computationally indistinguishable, completing the proof\. ∎

###### Theorem 2\(Security ofPILLAR\-Bin\(2\-round\)\)\.

SupposeΠP​I​R\(1\),ΠP​I​R\(2\)\\Pi\_\{PIR\}^\{\(1\)\},\\Pi\_\{PIR\}^\{\(2\)\}is a computationally private PIR scheme \(Definition[1](https://arxiv.org/html/2609.36326#Thmdefinition1)\) on the index databaseDBand the vector databaseDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}respectively\. Then Protocol 1 \(PILLAR\-Bin, Figure[13](https://arxiv.org/html/2609.36326#A5.F13)\) is secure against a semi\-honest server\.

###### Proof\.

Server’s real view\.The serversrvperforms all preprocessing locally and therefore already knows the full hash table\. During retrieval,

- •First round:srv’s view consists solely of theβ\\betaPIR queries\{𝖰𝗎𝖾𝗋𝗒Π\(1\)​\(ri\)\}i=1β\\\{\\mathsf\{Query\}^\{\(1\)\}\_\{\\Pi\}\(r\_\{i\}\)\\\}\_\{i=1\}^\{\\beta\}issued by the client, whereri=H⁡\(wi\)modRr\_\{i\}=H\(w\_\{i\}\)\\bmod Rfor keywordwi∈𝒱∪\{⊥\}w\_\{i\}\\in\\mathcal\{V\}\\cup\\\{\\bot\\\}in the padded/truncatedQQ\.
- •Second round:srv’s view consists ofβ′\\beta^\{\\prime\}queries\{𝖰𝗎𝖾𝗋𝗒Π\(2\)​\(ζi\)\}i=1β′\\\{\\mathsf\{Query\}^\{\(2\)\}\_\{\\Pi\}\(\\zeta\_\{i\}\)\\\}\_\{i=1\}^\{\\beta^\{\\prime\}\}whereζi∈I⋆\\zeta\_\{i\}\\in I^\{\\star\}666I⋆I^\{\\star\}denotes the padded/truncated version ofIIwithβ′\\beta^\{\\prime\}items, as described in Retrieval Step 4, Figure[13](https://arxiv.org/html/2609.36326#A5.F13)to the embedding databaseDB𝖤𝗆𝖻\\textsf\{DB\}\_\{\\mathsf\{Emb\}\}issued by the client, whereβ′\\beta^\{\\prime\}is a known public parameter\.

No other message passes fromclnttosrv\. We note that de\-duplication and removal of⊥\\boton retrieval step 3 of Figure[13](https://arxiv.org/html/2609.36326#A5.F13)are happening locally at client for internal score ranking, andclntstill sends a constant payload ofβ′\\beta^\{\\prime\}queries in step 4\-5 regardless of deduplication/removal results of step 3\.

Simulation\.Construct𝖲𝗂𝗆\\mathsf\{Sim\}as follows: given only the public parameters\(N,R,k,λ\)\(N,R,k,\\lambda\)and the fixed query lengthsβ,β′\\beta,\\beta^\{\\prime\}, output\{𝖰𝗎𝖾𝗋𝗒Π\(1\)​\(ui\)\}i=1β,\{𝖰𝗎𝖾𝗋𝗒Π\(2\)​\(zi\)\}i=1β′\\\{\\mathsf\{Query\}^\{\(1\)\}\_\{\\Pi\}\(u\_\{i\}\)\\\}\_\{i=1\}^\{\\beta\},\\\{\\mathsf\{Query\}^\{\(2\)\}\_\{\\Pi\}\(z\_\{i\}\)\\\}\_\{i=1\}^\{\\beta^\{\\prime\}\}where eachui←$\[R\],zi←$\[N\]u\_\{i\}\\xleftarrow\{\\$\}\[R\],z\_\{i\}\\xleftarrow\{\\$\}\[N\]are independently uniform\.

Indistinguishability\.The simulated view consists ofβ\+β′\\beta\+\\beta^\{\\prime\}uniformly random PIR queries; the real view consists ofβ\\betaPIR queries for indicesr1,…,rβ∈\[R\],ζ1,…,ζβ′∈\[N\]r\_\{1\},\\ldots,r\_\{\\beta\}\\in\[R\],\\zeta\_\{1\},\\dots,\\zeta\_\{\\beta^\{\\prime\}\}\\in\[N\], determined by the query keywords\. By Lemma[2](https://arxiv.org/html/2609.36326#Thmdefinition2)\(applied with database sizeRRandT=βT=\\betaqueries; database sizeNNandT=β′T=\\beta^\{\\prime\}queries\), the real and simulated views are computationally indistinguishable, completing the proof\. ∎

###### Theorem 3\(Security ofPILLAR\-Tree\)\.

SupposeΠP​I​R\\Pi\_\{PIR\}is a computationally private PIR scheme \(Definition[1](https://arxiv.org/html/2609.36326#Thmdefinition1)\)\. Then Protocol 2 \(PILLAR\-Tree, Figure[15](https://arxiv.org/html/2609.36326#A5.F15)\) is secure against a semi\-honest server

###### Proof\.

PILLAR\-Treeproceeds in three sequential rounds; we analyze each in turn and then apply Lemma[2](https://arxiv.org/html/2609.36326#Thmdefinition2)\.

Round 1 \(Block\-Max Tree Traversal\)\.At levelℓ∈\{1,…,ℋ\}\\ell\\in\\\{1,\\ldots,\\mathcal\{H\}\\\}of therr\-ary tree with heightℋ=1\+⌈logr⁡\(N/B\)⌉\\mathcal\{H\}=1\+\\lceil\\log\_\{r\}\(N/B\)\\rceil, the client expands the beam frontierFℓ−1F\_\{\\ell\-1\}of at mostWWnodes by fetching the block\-max scores of all\|Fℓ−1\|⋅r≤W⋅r\|F\_\{\\ell\-1\}\|\\cdot r\\leq W\\cdot rchildren via PIR\. BecauseWWandrrare public parameters, the number of PIR queries at each level is at mostW⋅rW\\cdot rregardless of the query contentQQ\. The server therefore observes at mostℋ⋅W⋅r\\mathcal\{H\}\\cdot W\\cdot rPIR queries over a database ofNnodesN\_\{\\mathrm\{nodes\}\}tree nodes, whereNnodesN\_\{\\mathrm\{nodes\}\}andℋ⋅L⋅r\\mathcal\{H\}\\cdot L\\cdot rare both fixed public quantities\.

Round 2 \(Sub\-Block Retrieval\)\.The client fetches block\-max scores for exactlyZ=W⋅\(B/s\)Z=W\\cdot\(B/s\)sub\-blocks, a count determined entirely by public parameters\(W,B,s\)\(W,B,s\)\. The server observes exactlyZZPIR queries over the sub\-block database\.

Round 3 \(Dense Embedding Fetch\)\.The client fetches exactlyks⋅sk\_\{s\}\\cdot sdocument embeddings via PIR over the database ofNNdocuments\. The countks⋅sk\_\{s\}\\cdot sis a fixed public parameter\.

Sequential Composition\.The total number of PIR queries across all three rounds isT=ℋ⋅W⋅r\+Z\+ks⋅sT=\\mathcal\{H\}\\cdot W\\cdot r\+Z\+k\_\{s\}\\cdot s, which is a deterministic polynomial function of the public parameters\. By Lemma[2](https://arxiv.org/html/2609.36326#Thmdefinition2)applied to thisTT\-query sequence, the server’s view across all rounds is computationally indistinguishable from a simulation issuingTTuniformly random PIR queries, completing the proof\. ∎

## Appendix HPIRPILLAR\-TreeDatabase via Cuckoo Hashing

Notation\.With the term𝖳𝗋𝖾𝖾⁡\(𝒞\)\\mathsf\{Tree\}\(\\mathcal\{C\}\)we denote the tree build upon corpus𝒞\\mathcal\{C\}while with the termℒℓ\\mathcal\{L\}\_\{\\ell\}we denote the collection of superblocks of layerℓ\\ellof the tree\. We useH=O⁡\(logr⁡\|𝒞\|/\|ℬ\|\)H=O\(\\log\_\{r\}\|\\mathcal\{C\}\|/\|\\mathcal\{B\}\|\)to denote the height of the tree\. For ease of exposition, we may abuse the notationℬ\\mathcal\{B\}for both the block and the super block in the tree\. Letid​\(ℬℓ\)\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)denote the index of blockℬℓ\\mathcal\{B\}\_\{\\ell\}within levelℓ\\ell\. The client can compute this value locally, i\.e\., to fetch, say, the 4th node of levelℓ\\ell, it simply setsid​\(ℬℓ\)=4\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)=4\.

Storage Blowup\.Recall the initial proposal from the main paper in which at each levelℓ\\ell, every super blockℬ∈ℒℓ\\mathcal\{B\}\\in\\mathcal\{L\}\_\{\\ell\}is associated with an array of\|𝒱\|\|\\mathcal\{V\}\|integers storing the upper bounds\. Such an array is extremely sparse \(most of its entries are00\) so this representation wastes a substantial amount of storage\. Crucially, the cost is not confined to space, i\.e\., PIR performance scales with the size of the PIR database, which here isO⁡\(\|ℒℓ\|⋅\|𝒱\|\)O\(\|\\mathcal\{L\}\_\{\\ell\}\|\\cdot\|\\mathcal\{V\}\|\)for levelℓ\\ell, so the same redundancy inflates query time as well\. Summing over all levels, representing each level as a concatenation of\|ℒℓ\|\|\\mathcal\{L\}\_\{\\ell\}\|sparse arrays forces the server to storeO⁡\(∑ℓ\|ℒℓ\|⋅\|𝒱\|\)O\\\!\\left\(\\sum\_\{\\ell\}\|\\mathcal\{L\}\_\{\\ell\}\|\\cdot\|\\mathcal\{V\}\|\\right\)integers, the vast majority of which are00\.

Proposed Optimization\.In order to reduce the PIR database storage, for each levelℓ\\ellon the tree, we present its corresponding PIR database as a*dictionary*\(specifically, a hash map\) ofkey\-valuepairs where the key is the stringkey=w\|\|id\(ℬℓ\)\\textsf\{key\}=w\|\|\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)and the value isvalue=σw​\(ℬℓ\)​‖w‖​id​\(ℬℓ\)\\textsf\{value\}=\\sigma\_\{w\}\(\\mathcal\{B\}\_\{\\ell\}\)\|\|w\|\|\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)\. The dictionary stores an entry only for those blocks whose score is non\-zero, i\.e\.,σw​\(ℬℓ\)\>0\\sigma\_\{w\}\(\\mathcal\{B\}\_\{\\ell\}\)\>0, which is precisely what eliminates the sparsity of the previous representation\. This, however, means the client may issue a query on a combination ofwwandOPENid​\(ℬℓ\)\)\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)\)that has no entry in the dictionary\. Because our dictionary always returns*some*entry \(it cannot signal that a key is absent\) the client needs a way to tell a genuine answer from an unrelated entry it happened to collide with\. Repeatingw\|id​\(ℬℓ\)w\\,\\\|\\,\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)insidevaluesupplies exactly this check; the client compares the returned suffix against the key it queried, and interprets a mismatch asσw​\(ℬℓ\)=0\\sigma\_\{w\}\(\\mathcal\{B\}\_\{\\ell\}\)=0\. Concretely, on levelℓ\\ellofTree​\(𝒞\)\\textsf\{Tree\}\(\\mathcal\{C\}\), letNℓN\_\{\\ell\}be the number of dictionary entries such thatw∈𝒱,ℬℓw\\in\\mathcal\{V\},\\mathcal\{B\}\_\{\\ell\}on levelℓ\\ellof the tree, andσw​\(Bℓ\)\>0\\sigma\_\{w\}\(B\_\{\\ell\}\)\>0\. Thus, we haveNℓ≪\|ℒℓ\|⋅\|𝒱\|N\_\{\\ell\}\\ll\|\\mathcal\{L\}\_\{\\ell\}\|\\cdot\|\\mathcal\{V\}\|\. The hash map is implemented via a*Cuckoo Hash Table*, with load factorα\\alpha, which hasO⁡\(1\)O\(1\)search time\. We usemmhash functionsh1,…,hm:𝒱×ℒℓ→\[Nℓ/α\]h\_\{1\},\\dots,h\_\{m\}:\\mathcal\{V\}\\times\\mathcal\{L\}\_\{\\ell\}\\to\[N\_\{\\ell\}/\\alpha\]to map dictionary entries to a table ofNℓ/αN\_\{\\ell\}/\\alphaslots such that each slot contains at most onekey\-valuepair, and the entry\(w\|\|id,σw\(ℬℓ\)\|\|w\|\|id\(ℬℓ\)\)\\left\(w\|\|\\textsf\{id\},\\sigma\_\{w\}\(\\mathcal\{B\}\_\{\\ell\}\)\|\|w\|\|\\textsf\{id\}\(\\mathcal\{B\}\_\{\\ell\}\)\\right\)is mapped to slothi\(w\|\|id\)h\_\{i\}\(w\|\|\\textsf\{id\}\)for onei∈\{1,…,m\}i\\in\\\{1,\\dots,m\\\}\. For an empty row in Cuckoo table, the data is\(⊥,0\)\(\\bot,0\)\. At query time, suppose the client wishes to learn the score of a blockℬc∈ℒℓ\\mathcal\{B\}\_\{c\}\\in\\mathcal\{L\}\_\{\\ell\}with respect to one of its own keywordswcw\_\{c\}\. It forms the keykeyc=wc\|id​\(ℬc\)\\textsf\{key\}\_\{c\}=w\_\{c\}\\,\\\|\\,\\textsf\{id\}\(\\mathcal\{B\}\_\{c\}\), issuesmmPIR queries for the candidate slotsh1​\(keyc\),…,hm​\(keyc\)h\_\{1\}\(\\textsf\{key\}\_\{c\}\),\\dots,h\_\{m\}\(\\textsf\{key\}\_\{c\}\), and receivesmmvalues\. Applying the check described above, the client compares each returned suffix againstkeyc\\textsf\{key\}\_\{c\}to verify if this word appears in the corresponding superblock\.

Complexity\.On layerℓ\\ellof the tree, the new representation incursm⋅w⋅r⋅\|Q\|m\\cdot w\\cdot r\\cdot\|Q\|queries on a database of sizeNℓ/α⋅3N\_\{\\ell\}/\\alpha\\cdot 3\(Nℓ/αN\_\{\\ell\}/\\alpharows, three fields per row\)\. On comparison, the old, unoptimized version hasw⋅r⋅\|Q\|w\\cdot r\\cdot\|Q\|queries on a database of size\|𝒱\|⋅\|ℒℓ\|\|\\mathcal\{V\}\|\\cdot\|\\mathcal\{L\}\_\{\\ell\}\|\(i\.e\.,\|𝒱\|⋅\|ℒℓ\|\|\\mathcal\{V\}\|\\cdot\|\\mathcal\{L\}\_\{\\ell\}\|rows with one field per row\)\. In total overHHlevels, the storage size of the new representation is∑ℓ=1HNℓ/α\\sum\_\{\\ell=1\}^\{H\}N\_\{\\ell\}/\\alphacomparing to the old cost ofO⁡\(\|𝒱\|⋅\|𝒞\|\|ℬ\|\)O\(\|\\mathcal\{V\}\|\\cdot\\frac\{\|\\mathcal\{C\}\|\}\{\|\\mathcal\{B\}\|\}\), where∑ℓ=1HNℓ≪∑ℓ=1H\|ℒℓ\|⋅\|𝒱\|=O⁡\(\|𝒱\|⋅\|𝒞\|\|ℬ\|\)\\sum\_\{\\ell=1\}^\{H\}N\_\{\\ell\}\\ll\\sum\_\{\\ell=1\}^\{H\}\|\\mathcal\{L\}\_\{\\ell\}\|\\cdot\|\\mathcal\{V\}\|=O\(\|\\mathcal\{V\}\|\\cdot\\frac\{\|\\mathcal\{C\}\|\}\{\|\\mathcal\{B\}\|\}\)\.

## Appendix ISupplementary details

### I\.1Full Testbed\.

We detail the extra details regarding our testbed that would be too verbose for the main body: We also test LAN latency in Appendix[D](https://arxiv.org/html/2609.36326#A4), which has 1000 megabits per second bandwidth and 5 millisecond round\-trip\-time\. Every configuration was given120120GB of RAM, with the exception ofPILLAR\-Binconfigurations that: hold the embedding database in memory and have more than1\.51\.5K documents per row, those were run on a machine with11TB of RAM\. For SciFact’s document/query embeddings we used192192\-dimension embeddings created from thee5\-base\-v2\[[Wang et al\., 2024](https://arxiv.org/html/2609.36326#bib.bib33)\]embedding function\. For MS MARCO’s document/query embeddings we used192192\-dimension embeddings created from themsmarco\-MiniLM\-L\-6\-v3\(The same as PACMANN did, to keep the comparison fair\), Sentence\-BERT bi\-encoder\[[Reimers and Gurevych, 2019](https://arxiv.org/html/2609.36326#bib.bib34)\], built on MiniLM\[[Wang et al\., 2020](https://arxiv.org/html/2609.36326#bib.bib35)\]and fine\-tuned on MS MARCO\. We ran our LLM/AI experiments on a single NVIDIA A100 \(80GB VRAM\) and fixed the RAGAS evaluation stage to the same100100queries per dataset\.

### I\.2Hybrid Retrieval in Practice\.

Combining lexical and dense retrieval is a standard, first\-class feature of the search engines on which RAG pipelines are built\. Elasticsearch exposes a reciprocal rank fusion \(RRF\) retriever\[[Cormack et al\., 2009](https://arxiv.org/html/2609.36326#bib.bib24)\]that merges the rankings of a BM25 query and akk\-NN query into a single result list\[[Elastic,](https://arxiv.org/html/2609.36326#bib.bib27)\]\. OpenSearch introduced a dedicated hybrid query in version 2\.11 that normalizes and combines keyword and neural scores inside the engine\[[OpenSearch Project,](https://arxiv.org/html/2609.36326#bib.bib28)\]\. Weaviate runs vector and BM25 search in parallel and fuses the two result sets with a configurable weighting\[[Weaviate,](https://arxiv.org/html/2609.36326#bib.bib29)\]\. Azure AI Search likewise executes keyword and vector queries in parallel and merges them with RRF, and its documentation reports that, in most benchmark tests, hybrid queries with semantic reranking return the most relevant results\[[Microsoft,](https://arxiv.org/html/2609.36326#bib.bib30)\]\. A Microsoft whitepaper, drawing on production RAG applications serving billions of queries per day, describes hybrid search with reranking as “table stakes” for RAG\[[Berntson et al\.,](https://arxiv.org/html/2609.36326#bib.bib31)\]\. Model providers make the same recommendation: Anthropic’s Contextual Retrieval pipeline pairs embeddings with BM25, and adding the BM25 component reduced the top\-20 retrieval failure rate from3\.7%3\.7\\%to2\.9%2\.9\\%\[[Anthropic, 2024](https://arxiv.org/html/2609.36326#bib.bib32)\]\. These sources establish that hybrid retrieval is broadly supported and recommended in practice; they do not constitute a census of deployed systems, and many simple RAG pipelines remain dense\-only\.