acceptodds
Under review as a conference paper at ICLR 2027

PILLAR: Private Inverted-Index Lexical Lookup for Augmented Retrieval

Abstract

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

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
PPRAG, RAG, PIR, AI, LLM, Security

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_8Vw7OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes PILLAR, which is a PIR-based protocol for privacy-preserving RAG system. In this work, a semi-honest server should learn nothing about the client's query. A formal proof of the security property is provided in the appendix. The authors compare PILLAR against baselines like PACMANN on multiple popular datasets like MS MARCO and SciFact.

Critical strengths
  • The problem being targeted by this work is real and important.

  • The evaluation is thorough.

Critical weaknesses
  • The technical novelty is somewhat limited. Both protocols adapt standard information retrieval structures by fixing the access schedule. It's hard to see the technical challenges to make such adaption.

  • The evaluation, although seemingly thorough, lacks the comparison with more baselines. The major baseline currently in the paper is only PACMANN. The conclusion is hard to generalize without the comparison results against more baselines.

Questions for authors
  • Please articulate the technical novelty
3 comments

Reviewer 8Vw7

We thank the reviewer for recognizing the problem as real and important and the evaluation as thorough. We address both weaknesses and the question in order:

1) Technical Novelty of PILLAR. We thank the reviewer for their feedback on PILLAR’s novelty. We will highlight some novel elements of PILLAR that we may not have made clear in the original text. PILLAR is the first PPRAG to combine both lexical scoring and dense retrieval. The reviewer notes that both PILLAR-Bin and PILLAR-Tree adapt standard information retrieval structures by fixing the access schedule, and that it is hard to see the technical challenge in doing so. The difficulty is fixing the schedule without: (1) leaking information about the client’s query, (2) affecting the quality of the documents retrieved, or (3) increasing the latency. Compared to PACMANN, which requires many rounds of PIR, PILLAR-Bin requires only a single PIR round. As a result, PILLAR-Bin retrieves documents of the same quality faster than PACMANN on every dataset we tested (general comment, Tables 2 and 3). Tiptoe and Coeus also need one round, but only because they scan the entire corpus for every query. PILLAR never scans the entire corpus, and it gives up no quality in exchange: PILLAR-Tree’s best configurations retrieve the highest-quality documents of any private protocol on every dataset (general comment, Table 1).

2) Comparison with more baselines. We agree that comparing PILLAR to PACMANN alone is not enough to generalize our conclusions. We perform multiple new experiments, adding two private baselines (Tiptoe and Coeus), three non-private baselines (BM25, exact dense, and fused hybrid), and three new datasets (FEVER, Natural Questions, and MS MARCO v2). We detail all of these results in the general comment (Tables 1–4). At the same MRR@10, PILLAR-Bin is 2–5× faster than PACMANN, and PILLAR-Tree is 1.2–1.7× faster, on all datasets.

We also address the reviewer’s question:

Q1) Novel achievements of PILLAR. The reviewer asks that we articulate the technical novelty of PILLAR. We articulated the novelty previously for Reviewer LDjq, and we provide the same summary of three novel components of PILLAR: (i) Round-robin interleaving of colliding documents in PILLAR-Bin (ii) a fixed-width beam search over a block-max tree, with the pruning threshold moved to the client in PILLAR-Tree (iii) sparse bound dictionaries in cuckoo tables with self-verifying keys in PILLAR-Tree.

I appreciate the author's clarification about the novelty. I also checked the replies to comments from other reviewers. I would like to raise my score from 2 to 3.

Thank you! We are glad you see the novelty of PILLAR. Thank you also for reading the comments from the other reviewers, we spent a lot of effort running extra experiments across a variety of configurations to make sure we could clear up any ambiguity about PILLAR’s performance.

Reviewer_kFL9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper presents PILLAR, a new protocol for private retrieval-augmented generation (RAG) that combines lexical keyword matching with dense semantic embeddings. Prior systems for private search such as PACMANN focused only on semantic search. The major contributions of the paper are 1) introducing the problem of hybrid private search and 2) introducing Pillar-Bin and Pillar-Tree, novel protocols for private BM25 matching via several interesting ideas. The authors validate PILLAR in a RAG setup over two standard retrieval benchmark corpora (MS MARCO and Scifact) where they report that PILLAR achieves a better search quality than PACMANN, a state of the art private semantic search system, at all fixed latency budgets evaluated.

Critical strengths
  1. The paper, to my knowledge, is the first to propose the idea of hybrid (lexical + semantic) retrieval for private search. This is a novel systems insight in this context and the paper makes a convincing case that hybrid retrieval provides value for private search. This insight has the potential to inspire further work in hybrid retrieval systems for private search.

  2. The Pillar-Bin and Pillar-Tree protocols for private lexical search are methodologically clever and insightful. They are non-obvious in both their design and implementation and present, to my knowledge, knew ideas.

Critical weaknesses
  1. The client-side storage requirements for Pillar are impractical as currently instantiated in the paper. On page 20, the authors report using 1 GB of client storage for MS Marco (8.8M documents). Since the full MS Marco raw text is roughly 2.3 GB of space (in a compressed file format on huggingface), this is within a small constant factor of the full search index size. At that point, the client could just download the entire search index and achieve privacy by just running the search locally. I suspect that if the authors moved to a different operating point with less client storage, the latency of Pillar-Tree would increase substantially since it involves many individual PIR queries.

More generally on this point, I think the paper would be much more compelling if the authors included experiments on larger dataset (such as on the 100M scale like pacmann and tiptoe) because that is a scale where a client can't trivially download the entire database to achieve privacy and client-side storage might become more of a real constraint. The scifact dataset used in the current evaluation, while interesting in testing lexical matching because of specialized terms, is trivially small (5000 documents) and could easily be downloaded and stored locally on the client, eliminating the need for a private search protocol to an untrusted server.

  1. The quality of Pillar's search is upper bounded by the capabilities of lexical retrieval since the semantic search step is performed only as a reranking of the BM25 retrieved results. Lexical search, while effective, is fundamentally limited by matching keywords. The protocol might be more useful if the semantic retrieval step could also operate over the full database.
Questions for authors
  1. Why is the client-side storage of Pillar so high? What would be the latency of running the protocol in a setting where the client storage roughly matched the storage used by protocols like Pacmann and Tiptoe?

  2. Are there any queries where Pillar performs worse than Pacmann because it relies solely on a lexical first stage matching engine? When might a user expect better or worse results from Pillar versus a purely semantic engine?

2 comments

Reviewer kFL9

We thank the reviewer for recognizing hybrid private retrieval as a new direction and for finding the protocols non-obvious. We ran new experiments for every proposed weakness, and address the reviewer’s concerns below:

W1) Client-side Storage and Scale. The reviewer points out that PILLAR’s required client storage on MS MARCO is close to 2.3 GB, the size of the compressed corpus, at which point the client could download everything and search locally. The reviewer suggests experiments on datasets with up to 100M documents to further determine how client storage in PILLAR scales. This is a good direction, and we address it by adding the experiments the reviewer requested.

The 2.3 GB figure the reviewer quotes for MS MARCO is compressed raw text, i.e., it is not searchable as is; a local search needs the embeddings (the MS MARCO embeddings are 6.8 GB). To test PILLAR on larger corpora, we use MS MARCO v2, which contains 138M documents and has 100 GB of embeddings. PACMANN must construct a graph for its ANN search, which takes several days on the full MS MARCO v2 dataset (i.e., it cannot compete with PILLAR at this scale), so we also created subsampled datasets of 25M and 50M documents. We compare at a fixed MRR@10 of 0.05, selecting the lowest-storage configuration if there are several:

Method8.8M WAN (s) ↓8.8M Storage (GB) ↓25M WAN (s) ↓25M Storage (GB) ↓50M WAN (s) ↓50M Storage (GB) ↓138M WAN (s) ↓138M Storage (GB) ↓
PACMANN0.261.00.271.60.531.5n/an/a
PILLAR-Bin0.050.40.200.60.211.01.734.3
PILLAR-Tree0.374.70.426.90.4410.71.0518.2

PILLAR-Bin consistently uses less storage than PACMANN. We explain why PILLAR-Bin uses so little storage in the general comment (Table 4).

W2) Quality is Upper-Bounded by Lexical Retrieval. The reviewer is correct: the dense reranking stage of PILLAR-Bin only sees the documents the first stage selects, and if a relevant document has no keyword overlap with the query, PILLAR-Bin’s first stage will never select it. PILLAR-Tree is less affected; its blocks are built with a clustering algorithm, so that similar documents share a block. A relevant document that has no keyword overlap with the client query can still be retrieved if any document in the block does share a keyword with the query. Table 1 in the general comments shows how PILLAR-Tree is affected, and the highest-scoring PILLAR-Tree configuration on MS MARCO is unaffected (it matches the dense baseline).

We also address both of the reviewer’s questions:

Q1) Why is Client Storage High, and What is the Latency at Matched Storage? The client storage is determined by the underlying PIR scheme, not by a PILLAR data structure, and it grows with the size of the corpus. In PILLAR-Bin's one-round variant, the client is required to store many full document embeddings. In the two-round variant, each embedding is stored once by the client and retrieved in a second round, so the client storage is smaller, at the cost of one extra round of retrieval. PILLAR-Tree initializes one PIR scheme per stage, and each contributes to the client storage, but the total is still asymptotically O(n)O(\sqrt{n}).

As the reviewer requests, we compare WAN latency on MS MARCO at fixed storage. If multiple configurations match the storage budget, we select the lowest WAN latency configuration:

Fixed 0.5 GB storage budget

MethodWAN (s) ↓MRR@10 ↑
PILLAR-Bin0.050.06
PACMANN0.250.02

Fixed 1.0 GB storage budget

MethodWAN (s) ↓MRR@10 ↑
PILLAR-Bin0.050.10
PACMANN0.260.06

Fixed 1.5 GB storage budget

MethodWAN (s) ↓MRR@10 ↑
PILLAR-Bin0.050.10
PACMANN0.280.16

PILLAR-Bin is faster than PACMANN at every budget and retrieves higher-quality documents at 0.5 GB and 1.0 GB. Only at 1.5 GB does PACMANN reach a higher MRR@10, but it is still slower than PILLAR-Bin.

Q2) When Does PILLAR Perform Worse than PACMANN? This is a good question, and we identify three cases, each backed by an experiment:

  • Short Queries. With few terms, the lexical stage has little to match on. In our truncation experiment (reply to reviewer LDjq, weakness 2), PILLAR-Tree’s MRR@10 on MS MARCO falls from 0.27 with eight query terms to 0.04 with one.
  • High-Quality Documents with PILLAR-Bin. PILLAR-Bin is the fastest protocol at low and moderate MRR@10, but Table 1 of the general comment shows that its highest-scoring configuration is below PACMANN’s on MS MARCO, FEVER, and NQ. Users who need the highest quality should use PILLAR-Tree.
  • Low Lexical Overlap Between Query and Relevant Documents. When a query shares few words with the document that answers it, the first stage of PILLAR has nothing to match on (see weakness 2). We tested this on Natural Questions, a dataset chosen because its queries rely on semantic matching more than exact keyword overlap. We display our results in Table 1 of the general comment, where PILLAR-Bin’s best MRR@10 falls below PACMANN’s, but PILLAR-Tree matches PACMANN.
Reviewer_LDjqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

summary: PILLAR is a privacy-preserving RAG system, where clients retrieves documents from a server having a public corpus, and the server learns nothing about the query. it first does lexical filtering with BM25 over PIR, then the client fetches the candidates’ embeddings and reranks them locally. There are two versions: PILLAR-Bin, which needs one round and is fast, and PILLAR-Tree, which uses tree-based pruning for better quality. The paper is well motivated and the system works in practice, but I think the contribution is more engineering and incremental than conceptual. The evaluation is also not strong enough to support the general claims. In its current form, I think it is below the acceptance threshold for ICLR. A deeper analysis of the lexical bottleneck, wider experiments and stronger baselines would make the paper much better.

strengths:

Weaknesses:

Critical strengths

(1) this paper Provides a well-articulated and provable guarantee; in this approach, the server only observes the length of the padded query and does not have access to the query itself. (2) It Offers improvements in speed and efficiency, as well as increased operational speed compared to PACMANN. (3) it Includes a comprehensive analysis and evaluation of response quality using RAGAS.

Critical weaknesses

(1) The novelty is limited. Most parts of PILLAR are already known techniques, like inverted index, block-max pruning, beam search, cuckoo hashing, PIR and dense reranking, and the main contribution is how they are combined for PIR. The authors should explain better what problem cannot be solved by just combining previous works like Tiptoe and Coeus.

(2) It seems that the retrieval is not really hybrid in the usual sense, because dense reranking only sees the documents that the lexical stage selects. So if a relevant document has low word overlap with the query and is not selected, it is lost, and this can also happen with paraphrased queries. Also only a few query terms are used (PILLAR-Bin just keeps the first ones), but there is no experiment that shows how much this hurts recall.

(3) Some claims in the paper seems to bee stronger than the results. On MS MARCO, PILLAR-Bin has clearly lower MRR@10 than PACMANN, so “comparable quality” is not accurate for retrieval. Also some MRR numbers in the main text do not match the appendix tables.

(4) The experiments are narrow, because Only two datasets are used, PACMANN is the only private baseline, and there are no non-private references like BM25, exact dense search or fused hybrid search. The RAGAS evaluation uses only 100 queries and reports no variance.

(5) Scalability and cost are not studied well. There is no experiment with different corpus sizes, and the best configurations need several GB of client storage and thousands of PIR lookups per query. It is also not clear how often the client state must be refreshed, or what happens when the corpus changes.

(6) Reproducibility is limited. There is no open source code, and some important details are missing, especially the clustering method for the blocks, which can change the results a lot.

Questions for authors

Check the weaknesses.

5 comments

We thank the reviewer for the detailed list and careful review. We fixed typos and missing numbers, and we addressed the larger concerns with new experiments (see the general comment). We now address the first 3 comments, and will post another comment adressing the others:

(1) Novelty of PILLAR.  We thank the reviewer for their feedback on PILLAR's novelty. PILLAR is the first privacy-preserving design to revisit classical information retrieval techniques, leveraging BM25 rather than relying exclusively on dense embeddings, as recent approaches have done. It is true that the components (in isolation) that make PILLAR work are known, but none works under PIR as-is. A naive application of each technique to PIR would either leak information about the client’s query or require a costly scan of the whole corpus. PILLAR adapts all these techniques (in a way not done before) so each piece works and outperforms prior work in most tested scenarios. We summarize the novel components: (i) Round-robin interleaving of colliding documents in PILLAR-Bin (ii) a fixed-width beam search over a block-max tree, with the pruning threshold moved to the client in PILLAR-Tree (iii) sparse bound dictionaries in cuckoo tables with self-verifying keys in PILLAR-Tree.

The reviewer also makes a good point that combining Tiptoe (a dense PPRAG) and Coeus (a sparse PPRAG) would be a ‘hybrid PPRAG’ and thus more comparable to PILLAR than PACMANN (a dense-only PPRAG). We ran new experiments comparing PILLAR-Bin and PILLAR-Tree to Tiptoe, Coeus, and a Tiptoe–Coeus hybrid (in which we merge both their top-k best documents ‘round-robin’ style). We detail the results at a fixed MRR@10 of 0.17 below:

MethodSciFact WAN (s) ↓NQ WAN (s) ↓FEVER WAN (s) ↓MS MARCO WAN (s) ↓
Tiptoe0.8610.9180.9230.934
Coeus0.2061.9213.6725.940
Tiptoe+Coeus1.0672.8394.5956.794
PILLAR-Bin0.0500.0510.0520.057
PILLAR-Tree0.2040.3030.2670.309

As the table shows, both Tiptoe and Coeus require more WAN time to achieve the same MRR@10. This is because both TipToe and Coeus can only perform a single query before requiring a large ‘refresh’ token to be sent.

(2) Incorrect Terminology and Query Truncation. We thank the reviewer for the careful reading. We refer to PILLAR as the first ‘private hybrid retrieval’ protocol, but in the wider non-privacy-preserving RAG literature, hybrid retrieval specifically means fusing a lexical score (like BM25) with a dense score (like an ANN) into a single decision rule to determine the top-k documents. In PILLAR, the two approaches are applied sequentially instead. That is, lexical scoring is used only to filter documents, and the final ranking uses the dense score alone. We are open to suggestions for another name; we propose ‘cascade hybrid protocol’ as an alternative. We also, as requested, compare PILLAR’s best configurations to non-private baselines in Table 1 of the general comment.

The reviewer also asks for experiments varying the number of query terms (as these determine the fixed PIR query and will be truncated if too long). We add our experiments detailing this result below:

Number of query terms used by PILLAR-TreeSciFact MRR@10MS MARCO MRR@10
10.3890.040
20.5000.134
30.5330.209
40.5890.245
60.6200.263
80.6410.269
120.6530.269

(3) Overclaims and Mismatched Numbers. The reviewer correctly notes that describing PILLAR-Bin’s quality as “comparable” to PACMANN’s overstates our result, since (at the same speed) they do not achieve identical quality. We add fixed MRR@10 comparisons in the general comment (Table 2); we now say that “PILLAR-Bin is 2–5× faster than PACMANN at the same MRR@10”. We are grateful that the reviewer noticed mismatched numbers between the main text and appendix: The appendix configurations were selected to minimize the number of PIR calls, while the main text used configurations that minimize WAN latency. Both now use the configurations that minimize WAN latency.

(4) Expanded evaluation. The reviewer is correct that the lack of non-private baselines, too few datasets, and only one PPRAG baseline weaken our results. We added these new experiments and referenced them in the general comment (Table 1).

The reviewer is also concerned about our RAGAS evaluation reporting no variance. We include the confidence intervals for every method below:

MethodMS MARCO Answer relevancy (↑)MS MARCO Faithfulness (↑)MS MARCO WAN (s) (↓)SciFact Answer relevancy (↑)SciFact Faithfulness (↑)SciFact WAN (s) (↓)
PILLAR-Tree0.75 [0.69, 0.81]0.92 [0.89, 0.97]0.920.64 [0.57, 0.72]0.65 [0.57, 0.73]0.21
PILLAR-Bin0.64 [0.58, 0.73]0.85 [0.79, 0.91]0.520.62 [0.55, 0.70]0.63 [0.55, 0.72]0.46
PACMANN0.72 [0.66, 0.79]0.92 [0.88, 0.96]1.730.67 [0.60, 0.74]0.64 [0.56, 0.72]0.79

PILLAR-Tree and PACMANN have overlapping CI’s on both metrics and on both datasets. PILLAR-Bin is 0.07 below on MS MARCO but also has overlapping CI’s on SciFact. We bold the result with the best RAGAS metrics; if there are multiple results with overlapping confidence intervals, we bold the result with the lowest WAN latency.

5) Scalability and Cost. A very good point from the reviewer is that we do not show how PILLAR scales to much larger datasets, which matters because the best configurations require several GB of client storage on a dataset like MS MARCO (The MS MARCO DB is 6GB in total). We reported new results on PILLAR-Bin scaling in the general comments (Table 4). PACMANN requires constructing a graph to perform an ANN search over, which takes several days on the MS MARCO V2 dataset (i.e., it cannot compete with PILLAR at this scale). Thus, we created subsampled datasets using 25M documents and 50M documents. We compared at a fixed MRR@10 of 0.05, selecting the lowest client storage if there are multiple:

MethodMS MARCO WAN (s) ↓MS MARCO Storage (MB) ↓v2 (25M) WAN (s) ↓v2 (25M) Storage (MB) ↓v2 (50M) WAN (s) ↓v2 (50M) Storage (MB) ↓v2 WAN (s) ↓v2 Storage (MB) ↓
PACMANN0.261027.40.271579.30.531519.5n/an/a
PILLAR-Bin0.05437.00.2631.60.21953.91.734260.8
PILLAR-Tree0.374677.20.426934.10.4410724.41.0518178.6

PILLAR-Bin consistently uses less storage than PACMANN, as explained in the general comment.

The reviewer also asks how often the client state must be refreshed and what happens when the corpus changes. Similar to PACMANN, we measure the total time spent on PIR preprocessing (denoted ‘maintenance time’) and provide plots in the appendix. The reviewer also asked whether the corpus can be updated, which depends on the chosen PIR scheme. We chose the same PIR primitive as PACMANN, namely PIANO, which does not support corpus updates. TipToe and Coeus use “Fully homomorphic PIR schemes,” which also do not support corpus updates.

Reviewer_LDjqOpenReview ↗

Remaining concerns after the rebuttal

Thanks for the response and the new experiments. My main concerns remain. The numbers are not consistent. The new table reports PILLAR-Bin at 0.057 s for MRR@10 of 0.17 on MS MARCO, but in Table 4 the fastest configuration needs 0.098 s for only 0.145. The 2–5× speedup claim also does not follow from Tables 4 and 5, where the gap is about 1.2×. The experiments are still narrow. The new comparisons use very low quality levels (MRR@10 of 0.17 and 0.05), and RAGAS still uses only 100 queries. Scalability is also a problem, since PILLAR-Tree needs up to 18 GB of client storage. Finally, there is still no code. For these reasons I keep my score.

Reviewer_5WYpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

PILLAR combines private lexical lookup with dense reranking on the client. PILLAR-Bin retrieves candidates from hashed posting lists in a fixed batch. PILLAR-Tree uses a fixed-width beam search over lexical score bounds to select candidate blocks. Both designs aim to hide the query and its access pattern from a semi-honest server. The paper compares them with PACMANN on MS MARCO and SciFact.

Critical strengths
  1. The two indexes address different serving needs. Bin retrieves candidate embeddings in one index round, while Tree spends additional rounds selecting promising blocks. In both cases, local reranking lets the client use the query embedding without sending it to the server.
  2. The evaluation covers both an 8.8-million-passage corpus and a small scientific corpus. The configuration sweeps and client-storage measurements in Appendix B help a reader assess how much latency or memory a gain in recall costs.
Critical weaknesses
  1. The headline speed comparison changes retrieval quality at the same time. On MS MARCO, the fastest Bin and PACMANN configurations take 0.098 s and 0.293 s, but their Recall@10 values are 0.2337 and 0.3306 (Tables 4–5). The timing endpoint also matters. Figure 15 requires a second, dependent private fetch after the client identifies the document IDs. Under the stated 50 ms network round trip, those two exchanges alone require at least 100 ms, before computation or transfer of the passages.
  2. Section 2 defines exact top-k retrieval over the whole corpus. Both posting-list truncation and beam pruning can discard a document that would have ranked first under dense scoring. Remark 4 acknowledges this approximation. The privacy proof also counts a different sequence of lookups from the optimized cuckoo-table and sub-block requests in Appendix D.3, making it difficult to check which transcript Theorem 3 covers.
Questions for authors
  1. On the same held-out queries, which Bin, Tree, and PACMANN configurations achieve comparable Recall@10? For each, could you report latency and bytes transferred both when the client knows the top-ten IDs and when it has received all ten passages?
  2. Could you state the functionality in terms of the approximate retrieval algorithm actually run, then list the padded requests visible to the server at each stage? Showing how that count gives the 472 PIR calls reported for MS MARCO configuration C1 in Table 3 would make the connection to Theorem 3 checkable.
5 comments

We thank the reviewer for checking the algorithmic details of PILLAR closely and suggesting a fairer evaluation. We also thank them for carefully checking the proof of Theorem 3 and noticing an inconsistency. We address every weakness (in order) below and provide a second post answering the questions:

1) Unfair Comparison & Extra Evaluation. We thank the reviewer for both pointing out a gap in our evaluation and providing the solution. The reviewer correctly notes that our headline speed comparison is unfair because, at the same speed, PACMANN and PILLAR-Bin retrieve different quality documents. We ran new experiments in which we fix a target MRR@10 and measure the speed of each method’s fastest configuration reaching it (see general comment, Tables 2 and 3). At the same MRR@10, PILLAR-Bin is 2–5× faster than PACMANN, and PILLAR-Tree is 1.2–1.7× faster, on all datasets.

The reviewer also points out that the ‘end-to-end’ RAG pipeline shown in Figure 15 cannot be what we are running, as PILLAR-Bin retrieves results faster than what would be possible. Thank you for bringing this to our attention. Figure 15 of the original submission shows that, after the client identifies the top-k document IDs, a second private fetch retrieves the document text. We did not include this step because it is the same for every method, and no SOTA methods include this either. We agree this can be misinterpreted when reading the results, so we have a new experiment in which we ran the extra retrieval step. It ends up being the exact same amount of time for every method (no comparative results in the main paper changes), so we just report the extra per-dataset WAN/communication cost:

DatasetWAN (s/query) ↓Comm (KB/query) ↓
SciFact0.05019.5
NQ0.05137.7
FEVER0.05153.4
MS MARCO v10.05138.7

2) Theorem 3 Clarification. We thank the reviewer for identifying the inconsistency in Theorem 3. We agree that the ideal PPRAG functionality defined in Section 2 specifies exact top-k retrieval, whereas PILLAR (like existing PPRAG protocols) performs approximate retrieval. We will revise this definition and clarify that our constructions do not claim to realize exact top-k retrieval. However, this distinction does not invalidate the privacy guarantee. Retrieval correctness and privacy are separate properties. Our Theorems concern the privacy of PILLAR against a semi-honest server, not the exactness of the documents it retrieves, and the security argument relies on the privacy guarantees of the underlying PIR scheme. In particular, PIR hides the indices the client requests, regardless of whether those indices correspond to the exact top-k documents or an approximate candidate set.

The reviewer also correctly notes that the proof (Theorem 3) and complexity analysis (Appendix D.3) of PILLAR-Tree state different numbers of PIR lookups, so it is unclear which one Theorem 3 covers. Appendix D.3 gives the correct number of PIR lookups. Theorem 3 still holds for the protocol as described in Appendix D.3, because the number of PIR lookups in every round is fixed by public parameters and does not depend on the query. We will update the revised version so that Theorem 3 and Appendix D.3 describe the same protocol.

We also address the two questions of the reviewer:

Q1) Configurations with Comparable Quality. The reviewer asks for a comparison at fixed retrieval quality, which we address in Tables 2 and 3 in the general comment. The reviewer also asks for the WAN/bytes sent for each method using the protocol in Figure 15, which we addressed in weakness 1 (above).

Q2) True Functionality of PILLAR-Tree and Worked Example. The true functionality of PILLAR-Tree and the corrected lookup count are discussed in weakness 2 (above). The reviewer also requests that we describe what the server sees and explicitly calculate PILLAR-Tree’s padded requests at each stage, so that it gives the 472 PIR calls reported in the original text. We provide this below:

We use the following notation: q∗q^* is the fixed number of query terms (every query is padded or truncated to exactly q∗q^* terms), mm is the number of cuckoo probes issued per lookup, WW is the beam width, i.e. the number of nodes kept at each tree level, $n_\ell ∗∗isthenumberofnodesattreelevelℓ,and∗∗** is the number of nodes at tree level ℓ, and **k_s$ is the number of sub-blocks whose embeddings are fetched.

The server then sees:

  • Stage 1 (beam search): m⋅q∗⋅min(W,nℓ)m \cdot q^* \cdot \text{min}(W, n_\ell) lookups at each tree level ℓ,
  • Stage 2 (sub-blocks): m⋅q∗⋅Wm \cdot q^* \cdot W lookups,
  • Stage 3 (embeddings): ksk_s lookups.

Note that the min(W,nℓ)\text{min}(W, n_\ell) is the same regardless of the query. We show the explicit calculation of the number of PIR calls for the requested PILLAR-Tree MS MARCO configuration:

RoundStageFormulaPIR calls
1Stage 1: tree level 1 (root)m⋅q∗⋅min(W,n1)m \cdot q^* \cdot \text{min}(W, n_1)2 · 2 · min(50, 1) = 4
2Stage 1: tree level 2m⋅q∗⋅min(W,n2)m \cdot q^* \cdot \text{min}(W, n_2)2 · 2 · min(50, 9) = 36
3Stage 1: tree level 3m⋅q∗⋅min(W,n3)m \cdot q^* \cdot \text{min}(W, n_3)2 · 2 · min(50, 1,080) = 200
4Stage 2: sub-blocksm⋅q∗⋅Wm \cdot q^* \cdot W2 · 2 · 50 = 200
5Stage 3: embeddingsksk_s32
Total472

The same formula gives 944 (MS MARCO C2) and 53 (SciFact C1), matching Table 3. We will add this example to the appendix.

Thank you for the detailed response and additional experiments. While the protocol clarifications and matched-MRR comparisons are helpful, matching MRR@10 does not establish comparable Recall@10, leaving my original concern about the recall–latency trade-off only partially resolved. I therefore maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Responses to Common Concerns Raised by All Reviewers and Requested Experiments

We thank all four reviewers for their careful and constructive reviews. Three concerns recur for our proposed protocols, and to address them effectively, we designed and report new experiments. The three recurring concerns are listed here (we note that we also answer each individual reviewer’s feedback):

New Datasets and Baselines. A fair point is that we demonstrate PILLAR on only two datasets, and it is unclear whether our conclusions apply to others. We add three datasets: Natural Questions (2.7M passages) and FEVER (5.4M), whose queries might be retrieved better by a purely semantic search (requested by reviewer kFL9), and MS MARCO v2 (138M), to test cost when there are many more documents (reviewers kFL9 and LDjq). We also compare with more PPRAG protocols than just PACMANN, namely Coeus and Tiptoe. We added both, along with three non-private baselines (BM25, exact dense, and fused hybrid).

Table 1 — best overall MRR@10, compared to non-private baselines. The first three rows (BM25, Exact dense, and a BM25–dense Fused hybrid) are non-private baselines.

MethodMS MARCO (8.8M) MRR@10 ↑SciFact (5K) MRR@10 ↑FEVER (New) (5.4M) MRR@10 ↑NQ (New) (2.7M) MRR@10 ↑MS MARCO v2 (New) (25M) MRR@10 ↑MS MARCO v2 (New) (50M) MRR@10 ↑
BM250.180.640.610.260.140.10
Exact dense0.320.640.790.480.270.21
Fused hybrid0.280.680.770.440.240.18
PILLAR-Bin0.290.630.700.430.220.12
PILLAR-Tree0.320.670.780.460.250.19
PACMANN0.300.640.710.460.240.17
Tiptoe0.210.570.500.25n/an/a
Coeus0.170.640.590.26n/an/a

The best-scoring PILLAR-Tree configuration retrieves the highest-quality documents of any private protocol on every dataset (and matches PACMANN on NQ). On MS MARCO, it matches the exact dense baseline.

Comparison at Fixed MRR@10. Reviewer 5WYp pointed out that our comparison to PACMANN was unfair because, even though PILLAR-Bin is faster, PACMANN has higher recall. To make the comparison fair, we ran new experiments in which we fixed a target MRR@10, then measured the speed of each method’s fastest configuration reaching that MRR@10.

Table 2 — WAN latency (s/query) per dataset, for each method, at target MRR@10 0.10.

MethodMS MARCO WAN (s) ↓SciFact WAN (s) ↓FEVER (New) WAN (s) ↓NQ (New) WAN (s) ↓
PILLAR-Bin0.050.050.160.06
PACMANN0.280.260.350.27
Tiptoe1.00.100.920.11
Coeus5.900.213.672.00

We observe that PILLAR-Bin is roughly 2–5× faster than PACMANN at the same MRR@10 on all datasets — even on the two new datasets FEVER and NQ, PACMANN cannot reach the same speeds as PILLAR-Bin.

Table 3 — WAN latency (s/query) per dataset, for each method, at target MRR@10 0.15.

MethodMS MARCO WAN (s) ↓SciFact WAN (s) ↓FEVER (New) WAN (s) ↓NQ (New) WAN (s) ↓
PILLAR-Tree0.420.210.480.44
PACMANN0.550.260.840.54
Tiptoe1.00.870.920.92
Coeus5.870.223.672.00

When retrieval quality is equal, PILLAR-Tree runs 1.2–1.7× faster than PACMANN on all datasets. Even when choosing a dataset in which lexical retrieval may fail, PILLAR-Tree still retrieves documents of equal quality in less time.

Client Storage Concerns. Reviewers LDjq and kFL9 raise valid concerns that, in the presented settings, PILLAR requires too much client-side storage, and reviewer LDjq asks how this changes with corpus size. We ran new experiments on MS MARCO v1 and nested subsets of MS MARCO v2 to explore how client-side storage grows as the number of documents grows.

Table 4 — cost at fixed MRR@10 = 0.05 We select the lowest storage configuration that meets this MRR@10.

Method8.8M WAN (s) ↓8.8M Storage (GB) ↓25M (New) WAN (s) ↓25M (New) Storage (GB) ↓50M (New) WAN (s) ↓50M (New) Storage (GB) ↓
PILLAR-Bin0.050.40.20.60.211.0
PACMANN0.261.00.271.60.531.5

Table 4 demonstrates how PILLAR-Bin’s required client storage changes as corpus size grows. PILLAR-Bin’s PIR database is indexed by vocabulary term rather than by the number of documents, and the vocabulary grows far more slowly than the corpus, so PILLAR-Bin’s client storage stays roughly flat while PACMANN’s grows with the number of documents.

We believe the revised evaluation (five datasets, three non-private baselines, equal MRR experiments) addresses the reviewers' concerns, and we're happy to discuss any follow-up comments. We will post individual responses as soon as we finalize them.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.