TL;DR
This paper provides the first formal theoretical proof that generative Autoregressive Ranking (ARR) with Large Language Models is strictly more expressive than traditional Dual Encoders, capable of ranking an arbitrary number of documents with a constant hidden dimension. To unlock this potential, the authors introduce SToICaL, a novel rank-aware training loss that uses prefix-tree marginalization to align LLM generation probabilities with ground-truth relevance. Experiments demonstrate significant improvements in ranking metrics and a drastic reduction in invalid document identifier generations.
What Problem Does This Paper Address?
Information retrieval traditionally relies on a multi-stage pipeline: an efficient but limited Dual Encoder (DE) to fetch a candidate set via vector similarity, followed by an accurate but computationally heavy Cross Encoder (CE) to rerank them. Recently, Autoregressive Ranking (ARR) has emerged as a promising alternative, where a generative Large Language Model (LLM) decodes unique document identifiers (docIDs) token-by-token to rank documents via beam search.
However, ARR has faced two major hurdles:
- Lack of Theoretical Foundation: While intuitively powerful, there was no formal proof showing why or if ARR is fundamentally superior to DEs in terms of expressive capacity.
- Rank-Agnostic Training: Standard LLM training relies on next-token prediction (cross-entropy), which treats target tokens as binary (correct vs. incorrect) and completely ignores the relative ordering or relevance of documents in a ranked list.
Methods
The authors tackle these problems with a two-pronged approach:
- Theoretical Capacity Analysis: They prove that for a DE to achieve any arbitrary ordering of $k$ documents, its embedding dimension must grow linearly with $k$. In contrast, an ARR model with a constant hidden dimension can theoretically rank an arbitrary number of documents, bypassing the "softmax bottleneck."
- SToICaL (Simple Token-Item Calibrated Loss): To replace rank-agnostic next-token prediction, the authors propose a generalized loss function consisting of two main components:
- Rank-Aware Item-Level Reweighting: Adjusts the loss contribution of each document based on its rank (using functions like $\lambda(r) = \frac{1}{r^\alpha}$), ensuring the model focuses heavily on top-ranked items.
- Prefix-Tree (Trie) Marginalization: Instead of standard one-hot target distributions, they construct a prefix tree over valid docID tokens. At each timestep, probability mass is distributed across all permissible continuation tokens proportional to the relevance scores of the documents they lead to.
Datasets
The authors evaluate their approach on two distinct datasets:
- WordNet: A hierarchical dataset of English noun concepts ("synsets"). Queries are synsets, and relevant documents are their hypernyms (abstract paths to the root). DocIDs are English nouns.
- ESCI Shopping Queries: A large-scale e-commerce benchmark for product search. To make it suitable for ARR, the authors use sparse dictionary learning to compress long product titles into short, structured numerical docIDs (e.g., "25,36,39") that are highly trie-friendly.
Key Insights and Ideas
- The Geometry of Ranking: The core "aha" moment is that Dual Encoders are geometrically constrained because they compress complex query-document interactions into a single dot product or distance metric. ARR avoids this by decomposing the ranking problem sequentially over time, allowing a fixed-size model to handle infinite permutations.
- Trie-Based Smoothing: Standard teacher-forcing forces the model to learn only one "correct" path. By using a prefix tree to smooth the target distribution, the model learns the relative relationships between all valid candidate documents simultaneously at the token level.
- DocID Design Matters: For generative retrieval to work efficiently on unstructured text (like product catalogs), docIDs shouldn't just be arbitrary strings; they should be engineered (e.g., via sparse coding) to form compact, structured prefix trees.
Key Results
- Constraint Violation Rate (CVR): On WordNet, standard next-token prediction suffers a 27.66% CVR (meaning it frequently scores an irrelevant document higher than a relevant one). SToICaL drops this rate to 0.0% under optimal item-level reweighting configurations.
- Ranking Performance: On both WordNet and ESCI, SToICaL significantly boosts normalized Discounted Cumulative Gain (nDCG) and Recall@K metrics for $K > 1$. For instance, on ESCI, nDCG improved from 95.23 to 97.21.
- Efficiency vs. Expressivity: Head-to-head comparisons on WordNet show that ARR performs on par with computationally expensive Cross Encoders while vastly outperforming Dual Encoders across all embedding dimensions.
Limitations and Future Work
- Training-Inference Mismatch: Due to teacher forcing during training, rank-aware token smoothing is fully effective only at the first token position ($t=1$). For later tokens ($t > 1$), a mismatch remains between training distributions and actual inference-time beam search choices.
- Scalability to Massive Corpora: While trie-based marginalization is highly efficient, scaling it to millions of documents without incurring significant memory overhead remains an open engineering challenge.
- Hyperparameter Tuning: Finding the optimal "sweet spot" balance between item-level reweighting ($\alpha$) and token-level marginalization ($\beta$) requires dataset-specific tuning.
Summary updated