Constrained Auto-Regressive Decoding Constrains Generative Retrieval
Shiguang Wu, Zhaochun Ren, Xin Xin, Jiyuan Yang, Mengqi Zhang, Zhumin Chen, Maarten de Rijke, Pengjie Ren
Abstract
Generative retrieval seeks to replace traditional search index data structures with a single large-scale neural network, offering the potential for improved efficiency and seamless integration with generative large language models. As an end-to-end paradigm, generative retrieval adopts a learned differentiable search index to conduct retrieval by directly generating document identifiers through corpus-specific constrained decoding. The generalization capabilities of generative retrieval on out-of-distribution corpora have gathered significant attention. Recent advances primarily focus on the problems arising from training strategies, and addressing them through various learning techniques. However, the fundamental challenges of generalization arising from constrained auto-regressive decoding still remain unexplored and systematically understudied. In this paper, we examine the inherent limitations of constrained auto-regressive generation from two essential perspectives: constraints and beam search. We begin with the Bayes-optimal setting where the generative retrieval model exactly captures the underlying relevance distribution of all possible documents. Then we apply the model to specific corpora by simply adding corpus-specific constraints. Our main findings are two-fold: (i) For the effect of constraints, we derive a lower bound of the error, in terms of the KL divergence between the ground-truth and the model-predicted step-wise marginal distributions. This error arises due to the unawareness of future constraints during generation and is shown to depend on the average Simpson diversity index of the relevance distribution. (ii) For the beam search algorithm used during generation, we reveal that the usage of marginal distributions may not be an ideal approach. Specifically, we prove that for sparse relevance distributions, beam search can achieve perfect top-1 precision but suffer from poor top-k recall performance. To support our theoretical findings, we conduct experiments on synthetic and real-world datasets, validating the existence of the error from adding constraints and the recall performance drop due to beam search. This paper aims to improve our theoretical understanding of the generalization capabilities of the auto-regressive decoding retrieval paradigm, laying a foundation for its limitations and inspiring future advancements toward more robust and generalizable generative retrieval.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Autoregressive Search Engines: Generating Substrings as Document Identifiers cites Language Models are Few-Shot Learners
- Autoregressive Search Engines: Generating Substrings as Document Identifiers cites Transformer Memory as a Differentiable Search Index
- ZeroGR: A Generalizable and Scalable Framework for Zero-Shot Generative Retrieval cites Autoregressive Search Engines: Generating Substrings as Document Identifiers
- ZeroGR: A Generalizable and Scalable Framework for Zero-Shot Generative Retrieval cites Transformer Memory as a Differentiable Search Index
- Improving Language Models by Retrieving from Trillions of Tokens cites Language Models are Few-Shot Learners
- Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender Systems cites Language Models are Few-Shot Learners
- Transformer Memory as a Differentiable Search Index cites Improving Language Models by Retrieving from Trillions of Tokens
- Transformer Memory as a Differentiable Search Index cites Language Models are Few-Shot Learners
Cited by top-tier papers2
- ZeroGR: A Generalizable and Scalable Framework for Zero-Shot Generative RetrievalWeiwei Sun, Keyi Kong, Xinyu Ma, Shuaiqiang Wang et al.ICLR 2026 · 6 citations
- Stochastic Primal-Dual Decoding for Multiobjective Generative Recommender SystemsDmitrii Moor, Ben Carterette, Senthilkumar Krishnamoorthy, Kyle Kretschman et al.KDD 2026
Builds on37
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Improving Language Models by Retrieving from Trillions of TokensSebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai et al.ICML 2022 · 1,629 citations
- BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and ComprehensionMike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad et al.ACL 2020 · 1,224 citations
- Transformer Memory as a Differentiable Search IndexYi Tay, Vinh Tran, Mostafa Dehghani, Jianmo Ni et al.NeurIPS 2022 · 506 citations
- Autoregressive Search Engines: Generating Substrings as Document IdentifiersMichele Bevilacqua, Giuseppe Ottaviano, Patrick Lewis, Scott Yih et al.NeurIPS 2022 · 242 citations
Related papers
- GLEN: Generative Retrieval via Lexical Index LearningSunkyung Lee, Minjin Choi, Jongwuk LeeEMNLP 2023 · 6 citations
- Auto Search Indexer for End-to-End Document RetrievalTianchi Yang, Minghui Song, Zihan Zhang, Haizhen Huang et al.EMNLP Findings 2023 · 9 citations
- CA-GAR: Context-Aware Alignment of LLM Generation for Document RetrievalHeng Yu, Junfeng Kang, Rui Li, Qi Liu et al.ACL Findings 2025 · 1 citation
- Generative Retrieval via Term Set GenerationPeitian Zhang, Zheng Liu, Yujia Zhou, Zhicheng Dou et al.SIGIR 2024 · 13 citations
- Generative Retrieval Meets Multi-Graded RelevanceYubao Tang, Ruqing Zhang, Jiafeng Guo, Maarten de Rijke et al.NeurIPS 2024 · 18 citations
