Semi-Parametric Retrieval via Binary Bag-of-Tokens Index

Authors: Jiawei Zhou, Li Dong, Furu Wei, Lei Chen
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: information retrieval, efficient retrieval, retrieval-agumented applications, RAG

Abstract:
Information retrieval has transitioned from standalone systems into essential components across broader applications, with indexing efficiency, cost-effectiveness, and freshness becoming increasingly critical yet often overlooked. In this paper, we introduce SemI-parametric Disentangled Retrieval (SiDR), a bi-encoder retrieval framework that decouples retrieval index from neural parameters to enable efficient, low-cost, and parameter-agnostic indexing for emerging use cases. Specifically, in addition to using embeddings as indexes like existing neural retrieval methods, SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness. Our comprehensive evaluation across 16 retrieval benchmarks demonstrates that SiDR outperforms both neural and term-based retrieval baselines under the same indexing workload: (i) When using an embedding-based index, SiDR exceeds the performance of conventional neural retrievers while maintaining similar training complexity; (ii) When using a tokenization-based index, SiDR drastically reduces indexing cost and time, matching the complexity of traditional term-based retrieval, while consistently outperforming BM25 on all in-domain datasets; (iii) Additionally, we introduce a late parametric mechanism that matches BM25 index preparation time while outperforming other neural retrieval baselines in effectiveness.

Decision: accept (poster)
Reviewer scores: 6, 8, 8, 6

Reviews and discussion:
<thread>
creation date:
1729482807496

thread_type:
official_review

<thread_object>
creator: reviewer_yedm

<content>
summary:
This paper introduces a Semi-parametric Disentangled Retrieval (SiDR) strategy that integrates the advantages of non-parametric and parametric retrieval, achieving competitive performance through the late parametric mechanism while maintaining high efficiency.

strengths:
1. The proposed SiDR integrates the advantages of non-parametric and parametric retrieval, achieving competitive performance while maintaining high efficiency.
2. The paper provides clear explanations of the SiDR method, experiments, and analysis, making it easy to understand.

weaknesses:
1. In Table 1, the performance of SiDR in parametric retrieval scenario does not surpass ANCE, even with the late parametric mechanism, yet the authors still report it as the best result with the bolded values.
2. In Table 2, under the non-parametric retrieval scenario, SiDR fails to surpass BM25 in most of datasets.
3. The late parametric mechanism is not novel, and the experiments should include more comparisons to various methods in this category.
4. Because of the comparison results with SiDR and ANCE/BM25, the experimental analysis should include an examination of the reasons for SiDR's better performance in the late parametric scenario.

questions:
1. How does SiDR compare with other late parametric methods, and what are the reasons for its success in the late parametric scenario?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693511837

thread_type:
official_review

<thread_object>
creator: reviewer_14wh

<content>
summary:
The paper focuses on sparse neural retrieval using a SPLADE-like model. It proposes to train a neural sparse bi-encoder V for both queries Q and documents D in such a way that it works well when computing similarity in the standard bi-encoder fashion, i.e., as the inner product of V(Q) and V(D) as well as through the inner product of V(Q) and the binary bag-of-tokens representation of a document.

This can be quite useful since it permits using a neural encoder together with non-parametric document representations (that do not required encoding) for effective and efficient retrieval.

Initially I had several concerns regarding the fairness of comparison to BM25 (multi vs single-thread and running BM25 on GPU) as well as to a possibility of re-ranking using a stronger model. However, additional experiments and clarifications resolved the issues. 

There are also some clarity issues (see the weaknesses section), which I think could be resolved or mitigated in the final version. The paper is somewhat hard to read, but it's understandable with some effort.

I would like to emphasize that the final version of authors need to compare against the fast implementation of BM25 (i.e., using PISA or similar) and make sure they make it clear that the comparison is vs single-thread BM25 (this is only for efficiency evaluation, no need to re-run all experiments).

Last, but not least, that BM25 with re-ranking is a strong baseline is definitely worth highlighting and connecting it to prior work, e.g.:
Leonhardt, Jurek, et al. "Efficient neural ranking using forward indexes." Proceedings of the ACM Web Conference 2022. 2022.

strengths:
See the summary for more details.
* An interesting approach
* A semi-parameteric index retrieval is easy to carry out on a GPU
* A substantial evaluation using the BEIR datasets (plus additional QA datasets)
* Promising results

weaknesses:
After discussion with authors, I have come to a conviction that the paper is generally solid, but presentation can be improved. 

There are several examples of where the paper is hard to read:
1. No explanation for the need of VDR (I still didn't quite get your explanations in the rebuttal).
2. The whole section of revisiting MLM is very confusing. You say "We provide insights into the consistencies between semi-parametric alignment and masked language
model pre-training", but this is already a pretty confusing phrase. To begin with you probably meant to say "connections". This is a small things, but a lot of such small things here and there complicate reading. Compare, e.g., how this was introduced in the SPLADE paper: We describe in Section 3.1 how the Masked Language Modeling (MLM) head of Pre-trained Language Models can be used to represent tokens in a sequence as vectors in the vocabulary space.
3. Then the whole section "PARAMETRIC AND NON-PARAMETRIC REPRESENTATION" is a bit of a slog to read. You need to explain what you mean by "parametric" vs "non-parameteric" vs "semi-parametric" representations. Moreover, when you talk about parametric representations it's IMHO better talk about **learned* token weights vs token computed using a hand-crafted rule (as in BM25). Don't get me wrong parametric vs non-parametric isn't wrong per se, but the distinction between parametric and non-parametric ML is a bit blurry. Plus, in the context of learned representations it is not frequently used IMHO.

BoT appears almost out of the blue. I think it was only mentioned in the MLM-section. IMHO, it's better to start by explaining that a document/query can be represented by a bag of words or tokens. In some cases these tokens are actual document/query tokens and in some cases they are "predicted" by the encoder model. Moreover, tokens can be weighted and non-weighted. Weights can come either from a model or from token-counting (as in BM25). This would have been a much less confusing explanation IMHO. Then, you can explain how weights are coming from an MLM head of a BERT model. This would have been much more logical, IMHO.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730703612403

thread_type:
official_review

<thread_object>
creator: reviewer_mxa4

<content>
summary:
This paper extends the VDR encoder (which also seems to be under review), aligning masked term prediction and bag of tokens representations. The paper shows that hybrid retrieval outperforms either vector based or token based retrieval alone, and the same parametric representation used in vector based retrieval can be "aligned" with bag of tokens to perform non-parametric retrieval.

strengths:
The paper is well motivated. The problems identified with constructing and refreshing vector based document indices are consistent with prevalent challenges in the industry. While most SOTA retrieval systems, especially those used in the industry, are hybrid, re-using representations across the two forms of retrieval seems novel. There is a good set of baselines, though the most relevant baselines are those that perform hybrid retrieval with vector based and token based approaches. The paper will also benefit from inclusion of more qualitative analysis, especially on how the aligned BoT query representations tackle classical IR problems like polysemy and synonymy.

weaknesses:
One of the strengths of bag-of-token based retrieval is that it is easily interpretable. The paper misses an opportunity to demonstrate how going from a parametric representation (which is considered semantic retrieval) allows us to tackle the standard problems in IR such as polysemy and synonymy. How do the lack of weights (a la BM25) on the document side affect retrieval? 

A nit: since the paper uses a hybrid retrieval system, comparison against either vector retrieval alone is not an apples to apples comparison. For example, in Table 1, this system seems to handily outperform BM25. But BM25 doesn't have the benefit of query side synonyms. While the index is non-parametric, the query is not (it's an "aligned version" of the parametric embedding). This doesn't invalidate the results. Rather it provides a channel for further investigation into the kinds of representations that are produced.  

Comparison against other hybrid retrieval systems (Gao et al 2021, Kuzi et Al 2020) would make the paper a lot stronger. (These are ones that come to mind, but there may be more). 

Luyu Gao, Zhuyun Dai, Tongfei Chen, Zhen Fan, Benjamin Van Durme, and Jamie Callan. Complement lexical retrieval model with semantic residual embeddings. In European Conference on Information Retrieval, 2021. URL https://api.semanticscholar.org/CorpusID:232423090

Saar Kuzi, Mingyang Zhang, Cheng Li, Michael Bendersky, and Marc Najork. Leveraging semantic and lexical matching to improve the recall of document retrieval systems: A hybrid approach, 2020. URL https://arxiv.org/abs/2010.01195.

questions:
BM25 as a token retrieval baseline has stood the test of time, being competitive for three decades. Why do the authors think SiDR_beta handily outperform BM25? What can we learn from this? Could this be because it's not an apples to apples comparison? Are there other underlying factors? 

Why did the authors not consider hybrid retrieval systems a more natural baseline?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730743442813

thread_type:
official_review

<thread_object>
creator: reviewer_pzgy

<content>
summary:
This paper main contribution is a retrieval model where documents are represented by the presence (boolean) of tokens (i.e. a binary bag of tokens). The advantage of such an approach is that the index has to be computed just once (it does not depend on parameters). However, the precision of such a model being low, the authors show that it can be successfully trained with a dense model (used as a second-stage ranker) - and combined with it at inference time. Experiments are conducted on the Wiki21m and BEIR benchmarks and retrieval latency is evaluated - showing that this approach offers a good compromise between effectiveness and efficiency.

strengths:
The main strength of the paper lies in the static representation of documents. As far as I know, this is the first model that relies on a simple index structure, that of representing the documents as a binary bag-of-token. This allows for potentially fast retrieval (although this can be debated, see weaknesses) of potential candidates that have then to be re-ranked.

weaknesses:
One of the main weaknesses is related to the number of collisions (i.e. number of documents for one token) increases with the size of the collection. It is unclear how this approach performs when the number of documents, their length, or both, increase. It would be important thus to investigate using the model on a larger collection (e.g. MS-Marco).

Another point is that the authors state (l. 329) that SOA training "techniques are orthogonal to the retrieval model and have not been applied in our works.". It is not clear if this is truly the case here, and no experiments have been conducted to check the potential of e.g. simple techniques like knowledge distillation. 

Other things:
- The authors propose to use the elu1p (p. 4) - it is not clear why softplus has not been used, the function is quite close to this and more "standard".
- The negative mining proposed for the Wikipedia collection is very specific to this collection (l. 292-293). In my opinion, this invalidates the results reported on the Wikipedia collection (table 1 p. 7) and would justify the use of the dismissed SOA training techniques.

questions:
- what is the purpose of section 3.1? I guess the argument is around the relationship between MLM and vocabulary expansion - see e.g. https://dl.acm.org/doi/10.1145/3634912

- Unless I miss something, there is no justification of the second par of $L_{semi-para}$, i.e. $L(V_{BoT}(q), V_\theta(p))$ since it is never used. And no ablation shows the importance of this factor

- What is $VDR_{\beta}$ in table 1? I could not find this model in the VDR paper.

- I do not agree on the difference in efficiency (lines 499-506) between your model and BM25. While it is true that leveraging GPU is useful in your case, BM25 could actually be implemented on GPU, so the reported speedup does not mean much.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732126980268

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to Reviewers

comment:
We thank all the reviewers for their thoughtful and constructive feedback! We are pleased they found the work is well-presented, the problem we address is important, and the methods we proposed are well motivated.

---
### _**Scope and Contribution**_

In this work, we present SiDR, a semi-parametric design bi-encoder retriever that supports both embedding-based index, as in neural retrievers, and tokenization-based index, similar to BM25. 

Based on reviewer feedback, we highlight two key features of our work to better outline its scope and contributions:

1. **SiDR supports tokenization as index, with indexing complexity comparable to BM25 and the ability to learn.** As RAG gain broader adoption, retrieval systems are applied to more complex tasks where BM25 falls short in capturing nuanced relevance and neural retrievers can be costly to deploy. SiDR offers a cost-efficient and learnable alternative for such scenarios.

2. **SiDR enables search on a fixed index within its training loop, addressing a common challenge of co-training retrievers with LLMs.** While training retrieval-based LLMs in an end-to-end manner offers benefits, it requires costly and frequent re-indexing of datastores during the training. SiDR addresses this issue by naturally supporting a bag-of-tokens index that remains fixed throughout training.

---

### _**Major Updates**_

Here, we briefly summarize the major updates made to the manuscript in response to reviewer feedback.

- **Appendix B**: we include a BM25 baseline with search performed on GPU.
- **Appendix D**: we present an ablation study on term weighting and term expansion on query and document side.
- **Appendix E**: we present more late-parametric baselines, with cost-effectiveness analysis. 

---

### _**Common Questions**_

We address some common questions below and will provide more detailed responses in the individual responses.

1. **Further Comparson to BM25 (in terms of success factors,  cost-effectiveness, GPU/multithread utilization).**

Given that our method uses a simple representation (i.e., bag-of-tokens) for the index, Reviewer PzGy and Reviewer 14wh have raised thoughtful concerns regarding comparisons with BM25, while Reviewer MXa4 and Reviewer YeDM have expressed interest in understanding the factors behind its effectiveness. To better address these concerns:
- In Appendix D, we present an ablation study on term weighting and term expansion in our method, showing that the learned query terms are the primary driver of improvement over BM25 when using a BoT index. The study also emphasizes the critical importance of training-inference consistency.
- In Appendix E, we present a cost-effectiveness analysis of our method compared to existing neural IR frameworks. While using a BoT index requires additional cost for embedding queries, this embedding effort is minimal—approximately 0.01% of what is required by existing neural systems.
- We include further comparisons with BM25, focusing on GPU utilization, multi-thread utilization, and different sources of implementation, to address each concern individually in the responses.

2. **Comparison of Training Techniques from a Training Complexity Perspective.**

Reviewer PzGy raised the point that our in-training retrieval techniques justify the use of other SOTA training techniques (referred to as advanced baselines in our paper), and Reviewer YeDM noted our underperformance compared to ANCE, which uses the same in-training retrieval for negatives. We would like to justify these points from a training complexity perspective.
- We provide a comparison of our in-training retrieval with other SOTA techniques in terms of training cost. SiDR supports searching on a fixed index, making in-training retrieval inexpensive, adding at most one hour of training as noted in Section 4.3. In contrast, based on our estimates, ANCE's index rebuilding every 10k batches adds 32 hours with our computational resources, and E5's pre-training on millions of weak-positive pairs takes weeks—both are significant compared to our current training period of just 9 hours.
- We compare SiDR to ANCE in terms of effectiveness at a comparable training cost. We rebuilt SiDR_full parametric index once to mine hard negatives for continual training, and the results show that, with a similar investment in training, SiDR achieves better performance than ANCE.

3. **Additional Late-parametric Baselines.**

Reviewers MXa4 and YeDM suggested incorporating additional baselines to strengthen the paper, which we fully agree with. In Appendix E, we provide additional baselines of late-parametric methods, along with a cost-effectiveness analysis. Our findings indicate that using BM25 as the first-stage retriever, followed by a stronger SOTA re-ranker (e.g., E5), can outperform SiDR_beta (m=100). However, SiDR_beta offers a distinct advantage by consistently achieving better in-domain performance as the first-stage retriever compared to BM25.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a new, efficient retrieval method, namely “semi-parametric disentangled retrieval framework (SiDR)”. The key idea is to have two encoders: (1) a VDR-based neural encoder (called parametric), and (2) a simple bag-of-words representation (called nonparametric). The neural encoder is trained in a way that these two encoders would align to each other. At test time, retrieval is done by using parametric encoder for the query and nonparametric encoder for the passage, optionally with reranking using parametric encoder for both. This brings benefits of both worlds, with indexing as efficient as nonparametric retrieval like BM25 and expressivity that is comparable to neural retrieval. Results on open-domain QA datasets and BEIR show the effectiveness of the method.

All reviewers acknowledged that this is the first model where the index building is as efficient as BM25 while the expressivity and performance is comparable to dense retrieval, and the benefit of this model is clear given the widely known importance of constructing and refreshing retrieval indexes.

Minor concerns were raised on the writing (e.g., method description and the section revisiting MLMs) and justification of certain modeling choices such as the use of elu1p for the parametric encoder.