REALM: Recursive Relevance Modeling for LLM-based Document Re-Ranking

Pinhuan Wang, Zhiqiu Xia, Chunhua Liao, Feiyi Wang, Hang Liu

TL;DR

This paper introduces REALM, a novel framework for LLM-based document re-ranking that tackles the challenges of uncertainty, instability, and high costs. By modeling relevance as Gaussian distributions and using recursive Bayesian updates, REALM achieves superior ranking quality while significantly reducing LLM inference calls and latency.

What Problem Does This Paper Address?

In modern Information Retrieval (IR), document re-ranking is crucial for refining initial search results to present the most relevant documents to users. While Large Language Models (LLMs) have shown immense promise in understanding complex queries and document content, their application in re-ranking faces significant hurdles. These include:

  • Ranking Uncertainty: LLMs can be stochastic, leading to inconsistent rankings even with minor input variations.
  • Unstable Top-K Recovery: Small changes in input can drastically alter the top-ranked documents, making results unreliable.
  • High Token Costs: Current LLM-based re-ranking methods often require extensive prompting, leading to high computational costs and slow inference times.

These limitations hinder the practical deployment of LLMs in real-world IR systems.

Methods

REALM introduces a recursive relevance modeling framework designed to address the aforementioned challenges. Its core components are:

  • Uncertainty-Aware Relevance Modeling: Instead of a single score, REALM models each document's relevance to a query as a Gaussian distribution, characterized by a mean (estimated relevance) and a variance (uncertainty). This explicitly captures the inherent noise in LLM outputs.
  • Recursive Refinement Framework: The framework employs a recursive process. It starts by selecting a "pivot" document and then conducts setwise comparisons between the pivot and subsets of other documents. These comparisons generate pairwise preference probabilities.
  • Bayesian Updates: These preference probabilities are used to update the relevance distributions of the documents via a Bayesian update mechanism, inspired by the TrueSkill rating system. This process iteratively refines the relevance estimates and reduces uncertainty.
  • Pivot-Centric Optimizations: To improve efficiency, REALM strategically selects high-confidence documents as pivots and uses an uncertainty-aware averaging technique to consolidate updates. A pivot adjustment mechanism further helps in effectively reducing the search space in each recursive step.

Datasets

The paper evaluates REALM on several standard benchmarks:

  • TREC Deep Learning (DL) 2019 and 2020: These datasets are designed for complex IR tasks and are based on MS MARCO corpora, featuring hundreds to thousands of candidate passages per query.
  • BEIR Benchmark: This benchmark includes four diverse datasets: Covid, SciFact, DBPedia, and NFCorpus, used to assess performance across various domains.

Key Insights and Ideas

  • Modeling Uncertainty is Key: The paper strongly advocates for explicitly modeling the uncertainty in LLM outputs, rather than treating them as definitive scores. This is crucial for robust re-ranking.
  • Recursion for Stability and Efficiency: The recursive nature of REALM allows for iterative refinement, leading to more stable rankings. By strategically reducing the candidate pool in each step, it also enhances efficiency.
  • Pivot Selection Matters: Choosing a document with low uncertainty as a pivot is critical for guiding the recursive process effectively and ensuring stable partitioning.
  • LLM Capabilities Vary: The performance of re-ranking methods is highly dependent on the LLM's capabilities. Larger models generally perform better, but some architectures (like decoder-only LLaMA) exhibit strong positional biases that hinder their re-ranking effectiveness.

Key Results

REALM demonstrates significant improvements over state-of-the-art re-ranking methods:

  • Improved Ranking Quality: REALM consistently outperforms baselines, achieving an average NDCG@10 improvement of 0.7-11.9% across TREC DL datasets.
  • Reduced Inference Costs: The framework significantly cuts down LLM inferences (23.4-84.4%) and inference latency (25.0-88.7%).
  • Lower Token Usage: Prompt token costs are reduced by 25.2-94.8%, and generation token costs are effectively eliminated.
  • Stability: REALM shows better stability against variations in initial ranking orders compared to methods like Setwise-Insertion.

Limitations and Future Work

The authors acknowledge several limitations:

  • Resource Constraints: The current evaluation is centered on a specific framework design that achieved strong empirical performance, and further exploration of other re-ranking methods with REALM's principles is possible.
  • Skew-Normal Distributions: The paper did not explore skew-normal distributions for relevance modeling, which might better capture skewed score distributions from retrievers.
  • Closed-Source Models: The evaluation primarily used open-source models (Flan-T5, LLaMA). Future work could investigate performance with closed-source models accessed via APIs (e.g., GPT-3.5, GPT-4).

Promising future directions include exploring these alternative distributions and extending the empirical evaluation to a wider range of LLMs and tasks.

Summary updated

Abstract

Large Language Models (LLMs) have shown strong capabilities in document re-ranking, a key component in modern Information Retrieval (IR) systems. However, existing LLM-based approaches face notable limitations, including ranking uncertainty, unstable top-k recovery, and high token cost due to token-intensive prompting. To effectively address these limitations, we propose REALM, an uncertainty-aware re-ranking framework that models LLM-derived relevance as Gaussian distributions and refines them through recursive Bayesian updates. By explicitly capturing uncertainty and minimizing redundant queries, REALM achieves better rankings more efficiently. Experimental results demonstrate that our REALM surpasses state-of-the-art re-rankers while significantly reducing token usage and latency, improving NDCG@10 by 0.7-11.9 and simultaneously reducing the number of LLM inferences by 23.4-84.4%, promoting it as the next-generation re-ranker for modern IR systems.
BibTeX
@inproceedings{wang2025realm,
  author = {Pinhuan Wang and Zhiqiu Xia and Chunhua Liao and Feiyi Wang and Hang Liu},
  title = {{REALM: Recursive Relevance Modeling for LLM-based Document Re-Ranking}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  url = {https://openreview.net/forum?id=M9kOVtJRU0},
}
Figure