In the world of Information Retrieval (IR), the standard "retrieve and re-rank" pipeline is a double-edged sword. We use fast, efficient models (like BM25 or dense retrievers) to grab a few hundred candidates, then hand them off to a "heavyweight" model (like a Cross-Encoder) for precise ranking. The catch? If the first stage misses a relevant document, the second stage never even sees it. This is the bounded-recall problem, and it creates a hard ceiling on how good our search results can ever be.
A new paper, "Quam: Adaptive Retrieval through Query Affinity Modelling," introduces a clever way to break through this ceiling by turning the retrieval process into a dynamic exploration of the document landscape.
TL;DR
Quam is an adaptive retrieval framework that bypasses the limitations of fixed-pool re-ranking by dynamically exploring a "document affinity graph." By modeling how likely documents are to be co-relevant to the same query, Quam achieves up to a 26% improvement in recall over standard baselines with minimal computational overhead.
What Problem Does This Paper Address?
Traditional search is static: you pick a pool of documents and re-rank them. Adaptive retrieval tries to be more fluid. It assumes that if a document is highly relevant, its "neighbors" in the corpus might also be relevant—even if the first-stage retriever missed them.
However, previous adaptive methods (like the Graph Adaptive Retriever, or GAR) have two major flaws:
- Heuristic Graphs: They rely on simple lexical or semantic similarity to build their graphs, which doesn't always align with actual relevance.
- Indiscriminate Expansion: They treat all neighbors of a relevant document as equally promising, which leads to "noise" and performance degradation as the graph gets denser.
Methods
The authors propose Quam, which introduces two core innovations to make adaptive retrieval more "principled":
- Document Affinity Graph ($G_a$): Instead of using raw similarity, they train a model to predict co-relevance. If two documents often satisfy the same types of queries, they get a high "Laff" (Learnt Affinity) score. This creates a graph where edges represent a high probability of shared relevance.
- Query Affinity Modelling (SetAff): During the search, Quam doesn't just look at one document's neighbors. It calculates a Set Affinity score for candidate documents. This score is a weighted sum of the affinities between a candidate and the entire set of top-ranked documents found so far.
The algorithm operates in a loop: it scores a batch from the initial pool, identifies the "best" documents, looks up their neighbors in the affinity graph, calculates their $SetAff$ scores, and then prioritizes the most promising neighbors for the next round of expensive re-ranking.
Datasets
The researchers evaluated Quam using:
- MSMARCO Passage Ranking: Used for training the document affinity model. Since true co-relevance labels are rare, they used a "pseudo co-relevant" strategy to generate training triples.
- TREC Deep Learning (DL) 2019 & 2020: Used as the primary benchmarks for evaluating retrieval effectiveness (nDCG and Recall).
Key Insights and Ideas
- The Clustering Hypothesis in Action: The paper reinforces the idea that relevant documents "cluster" together, but argues that we need a relevance-aware definition of "nearness" to exploit this effectively.
- Noise Filtering is Key: One of the most striking findings is Quam's robustness. In Figure 5, you can see that as you increase the number of neighbors ($k$), the baseline GAR's performance eventually drops because it gets overwhelmed by non-relevant neighbors. Quam’s $SetAff$ scoring acts as a filter, allowing it to maintain or improve performance even with very dense graphs.
- Efficiency as a First-Class Citizen: Adaptive retrieval sounds expensive, but the authors show it only accounts for 2-3% of the total re-ranking time. Because Quam is more "judicious" about which neighbors it picks, it can actually be faster than simpler graph methods at higher budgets.
Key Results
- Recall Boost: On the TREC DL19 dataset, Quam improved Recall@50 by 23.39% compared to a standard BM25 + MonoT5 pipeline.
- Outperforming Baselines: Quam consistently beat the previous state-of-the-art adaptive method (GAR) by up to 12% in recall.
- Beating Exhaustive Search: Surprisingly, Quam sometimes outperformed an exhaustive search (scoring every document in the corpus). This is likely because the graph-based approach constrains the search space to high-quality neighborhoods, avoiding the "noise" that a global search might encounter.
Limitations and Future Work
While Quam is powerful, the authors note a few areas for growth:
- Low-Depth Optimization: At very low retrieval budgets (e.g., only scoring 10-20 documents), there is still room to optimize how candidates are chosen.
- Training Data: The model relies on co-relevance data. While they successfully used pseudo-labels, performance might improve with higher-quality human-annotated co-relevance datasets.
- Broadening Scope: The current work focuses on ad-hoc passage retrieval; extending this to more complex structures or different "learning to rank" scenarios is a logical next step.
For those interested in the implementation, the authors have made their code available at https://github.com/Mandeep-Rathee/quam.
Summary updated