Autoregressive Ranking: Bridging the Gap Between Dual and Cross Encoders

Benjamin Rozonoyer, Chong You, Michael Boratko, Himanshu Jain, Nilesh Gupta, Srinadh Bhojanapalli, Andrew McCallum, Felix Yu

Abstract: The success of Large Language Models (LLMs) has motivated a shift toward generative approaches to retrieval and ranking, aiming to supersede classical Dual Encoders (DEs) and Cross Encoders (CEs). A prominent paradigm is pointwise Autoregressive Ranking (ARR), where an LLM generates document identifiers (docIDs) token-by-token to enable ranking via beam search. ARR offers the promise of superior expressivity compared to DEs while avoiding the prohibitive computational cost of CEs. However, a formal theoretical foundation for this expressive power has been missing. Moreover, the standard next-token prediction loss is rank-agnostic and inappropriate for finetuning an LLM for ranking tasks. In this paper, we first prove that the expressive capacity of ARR is strictly superior to DEs. While a DE requires an embedding dimension that grows linearly with corpus size to achieve arbitrary rankings, ARR can solve it with a constant hidden dimension. We then propose SToICaL (Simple Token-Item Calibrated Loss), a generalized rank-aware training loss for LLM finetuning. By using item-level reweighting and prefix-tree marginalization, we distribute probability mass over valid docID tokens based on their ground-truth relevance. Experiments on WordNet and ESCI datasets verify that our loss suppresses invalid docID generations and significantly improves ranking metrics beyond top-1 retrieval.

The Evolution of Retrieval and Ranking

Modern search and recommendation systems typically rely on a two-stage pipeline. The first stage uses Dual Encoders (DE), which are computationally efficient but limited by a "bottleneck": they compress queries and documents into single vectors, ignoring complex textual interactions. The second stage employs Cross Encoders (CE), which are highly accurate as they process query and document text jointly, but their latency makes them impractical for scoring millions of documents in real-time.

Autoregressive Ranking (ARR) has emerged as a compelling "third way." In this paradigm, an LLM generates the document identifier (docID) of a relevant item one token at a time. While ARR has shown empirical promise, it has historically lacked a formal theoretical foundation and suffered from a training mismatch, as standard next-token prediction (NTP) treats all tokens as equally important regardless of their document's relevance.

Comparison of ranking architectures: (a) Dual Encoder, (b) Cross Encoder, and (c) Autoregressive Ranking.

Theoretical Capacity: ARR vs. Dual Encoders

A primary contribution of this work is the formal proof of ARR's superior expressive capacity. The authors demonstrate that for a Dual Encoder to perfectly represent arbitrary rankings across a corpus of $k$ documents, its embedding dimension must grow linearly with $k$. In contrast, an ARR model can achieve the same ranking performance with a constant hidden dimension, regardless of the corpus size. This advantage stems from the LLM's internal cross-attention mechanisms, which allow it to capture deep query-document interactions that a single vector similarity cannot represent.

SToICaL: A Rank-Aware Training Objective

To bridge the gap between standard LLM training and the specific requirements of ranking, the authors introduce SToICaL (Simple Token-Item Calibrated Loss). This novel loss function addresses two critical issues:

  1. Rank-Aware Reweighting: Standard training treats every document equally. SToICaL scales the loss based on ground-truth relevance, ensuring that the model prioritizes learning the identifiers of high-ranking documents.
  2. Prefix-Tree (Trie) Marginalization: To prevent the model from generating invalid docIDs (hallucinations), the authors construct a trie of all valid identifiers. During training, the loss is marginalized over the entire tree of valid continuations, distributing probability mass based on the relevance of the documents those paths lead to.
The SToICaL loss mechanism: (a) Trie over docIDs, (b) standard one-hot supervision, and (c) the proposed marginalization approach.

Experimental Evaluation

The researchers evaluated SToICaL on two distinct datasets:

  • WordNet: A hierarchical dataset of English nouns where the model must rank hypernyms (e.g., ranking "ruminant" higher than "animal" for the query "deer").
  • ESCI (Shopping Queries): A large-scale Amazon search dataset. To facilitate ARR, the authors used sparse dictionary learning to generate structured numerical docIDs that are easily organized into a prefix tree.

Key Results

  • Eliminating Hallucinations: SToICaL reduced the Constraint Violation Rate (CVR)—the frequency of generating non-existent docIDs—from approximately 27% to nearly 0% on WordNet.
  • Superior Ranking Performance: On both WordNet and ESCI, SToICaL significantly outperformed standard Next-Token Prediction across metrics like nDCG and Recall@K.
  • Closing the Gap: ARR models trained with SToICaL performed on par with computationally expensive Cross Encoders while remaining significantly more powerful than Dual Encoders of various dimensions.

Conclusion and Future Directions

This work provides the first formal proof that Autoregressive Ranking is fundamentally more expressive than traditional Dual Encoders. By introducing the SToICaL loss, the authors provide a robust framework for training LLMs to understand document relevance and identifier structure. Future work remains in scaling prefix-tree marginalization to billion-document corpora and further optimizing the co-design of docID structures with rank-aware loss functions.

Summary updated

Abstract

The success of Large Language Models (LLMs) has motivated a shift toward generative approaches to retrieval and ranking, aiming to supersede classical Dual Encoders (DEs) and Cross Encoders (CEs). A prominent paradigm is pointwise Autoregressive Ranking (ARR), where an LLM generates document identifiers (docIDs) token-by-token to enable ranking via beam search. ARR offers the promise of superior expressivity compared to DEs while avoiding the prohibitive computational cost of CEs. However, a formal theoretical foundation for this expressive power has been missing. Moreover, the standard next-token prediction loss is rank-agnostic and inappropriate for finetuning an LLM for ranking tasks. In this paper, we first prove that the expressive capacity of ARR is strictly superior to DEs. While a DE requires an embedding dimension that grows linearly with corpus size to achieve arbitrary rankings, ARR can solve it with a constant hidden dimension. We then propose SToICaL (Simple Token-Item Calibrated Loss), a generalized rank-aware training loss for LLM finetuning. By using item-level reweighting and prefix-tree marginalization, we distribute probability mass over valid docID tokens based on their ground-truth relevance. Experiments on WordNet and ESCI datasets verify that our loss suppresses invalid docID generations and significantly improves ranking metrics beyond top-1 retrieval.
BibTeX
@inproceedings{rozonoyer2026autoregressive,
  author = {Benjamin Rozonoyer and Chong You and Michael Boratko and Himanshu Jain and Nilesh Gupta and Srinadh Bhojanapalli and Andrew McCallum and Felix Yu},
  title = {{Autoregressive Ranking: Bridging the Gap Between Dual and Cross Encoders}},
  booktitle = {FoGen @ ICML},
  year = {2026},
  url = {https://openreview.net/forum?id=eubfy1vnlq},
}
Figure