Quam: Adaptive Retrieval through Query Affinity Modelling

Mandeep Rathee, Sean MacAvaney, Avishek Anand

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:

  1. Heuristic Graphs: They rely on simple lexical or semantic similarity to build their graphs, which doesn't always align with actual relevance.
  2. 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.
Figure 1: Quam remains robust as the number of neighbors increases, whereas the baseline GAR degrades.

Methods

The authors propose Quam, which introduces two core innovations to make adaptive retrieval more "principled":

  1. 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.
  2. 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.
Figure 2: An overview of the Quam pipeline, showing the alternating steps between initial re-ranking and graph-based expansion.

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.
Figure 5: Comparison of recall across different graph depths and batch sizes. Quam (green) consistently stays at the top.

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

Abstract

A central task in information retrieval and the NLP communities is relevance modeling, which aims to rank documents based on their expressed information needs Many knowledge-intensive retrieval tasks are powered by a first-stage retrieval stage for context selection, followed by a more involved task-specific model. However, using this filtering (cascading) approach inherently limits the recall of subsequent stages. Recently, adaptive re-ranking techniques have been proposed to overcome this issue by continually selecting documents from the whole corpus, rather than only considering an initial pool of documents. However, so far these approaches have been limited to heuristic design choices, particularly in terms of the criteria for document selection. In this work, we propose a unifying view of the nascent area of adaptive retrieval by proposing Quam, a query-affinity model of adaptive re-ranking that includes two complementary components: (1) a more principled algorithm for document selection, and (2) a data-driven approach to model document co-relevance during indexing. Our extensive experimental evidence shows that our proposed approach improves the recall performance by up to 26% over the standard re-ranking baselines. Further, the query affinity modelling and relevance-aware document graph components can be injected into any adaptive retrieval approach. The experimental results show the existing adaptive retrieval approach improves recall by up to 12%.
BibTeX
@inproceedings{rathee2025quam,
  author = {Mandeep Rathee and Sean MacAvaney and Avishek Anand},
  title = {{Quam: Adaptive Retrieval through Query Affinity Modelling}},
  booktitle = {WSDM},
  year = {2025},
  url = {https://openreview.net/forum?id=JAoyAnFu9X},
}
Figure