Traditional information retrieval relies on a "match-and-rank" paradigm: a system converts a query into a vector, searches a massive index for the closest neighbors, and returns a list of candidates. However, a new research direction is fundamentally reimagining this process as a generative task. Instead of searching for a document, a model simply writes the identifier of the document it wants.
This shift, pioneered by researchers like Nicola De Cao and Sebastian Riedel in Autoregressive Entity Retrieval, treats retrieval as a sequence-to-sequence problem. While powerful, this approach faces a critical flaw: Large Language Models (LLMs) are prone to "hallucinations," often generating identifiers for entities or documents that do not exist in the real world. The solution emerging across the field is Prefix Constrained Decoding.
The Mechanism of Constrained Search
The core intuition behind constrained decoding is to transform the model's output space from a "free-form" vocabulary into a "closed-world" search. In a standard LLM, the model can choose any token from its 50,000+ word vocabulary at each step. In a constrained system, the model is only allowed to pick tokens that form a valid path within a predefined set of identifiers.
This is typically implemented using a Prefix Tree (Trie). As the model generates an identifier token-by-token, the system looks up the current prefix in the Trie. If the model has generated "New_Yo", the Trie restricts the next possible tokens to those that could complete a valid entity, such as "rk" (for New York) or "n" (for New Yonkers), effectively blocking all other irrelevant tokens in the vocabulary.
As Jinghui Yan and colleagues demonstrate in their work on Chinese Medical Procedure Entity Normalization, this mechanism ensures a zero percent out-of-dictionary rate. By integrating the knowledge base structure directly into the decoding process, the model is physically incapable of hallucinating a non-existent medical code.
From Tries to Compressed Full-Text Indexes
While Tries work well for short entity names, they can become memory-intensive when indexing millions of long documents. To solve this, researchers like Michele Bevilacqua and Patrick Lewis introduced SEAL (Search Engines with Autoregressive LMs).
Instead of a simple Trie, SEAL uses a compressed FM-Index—a data structure that allows the model to generate any substring found within a document as a valid identifier. This allows the model to be highly flexible, retrieving a document by its title, a famous quote, or a specific technical phrase, while the FM-index acts as a factual guardrail ensuring that every generated string actually exists within the corpus. This approach was further extended in DiffusionRet by Shanbao Qiao, which uses these constraints to ground "hallucinated" pseudo-documents back into real-world evidence.
Scaling to Massive Databases and Toolkits
The utility of constrained decoding extends beyond simple search into complex reasoning tasks:
- Database Querying: In DBCopilot, Le Sun uses trie-based constraints to ensure that when an LLM generates SQL, the table and column names it chooses are strictly present in the database schema, preventing syntax errors in massive data lakes.
- Tool Use and APIs: As LLMs become agents, they must call external tools. Renxi Wang introduced ToolGen, which treats tool calling as a generative retrieval task. By constraining the beam search to a valid set of tool tokens, the system reduces tool hallucination rates to zero.
- Recommendation Systems: Models like TIGER, developed by Shashank Rajput and Yi Tay, represent items as "Semantic IDs"—hierarchical tuples of codewords. Constrained decoding ensures that the model only recommends items that actually exist in the product catalog.
Why It Works: Guiding vs. Correcting
The power of this research direction lies in its proactive nature. Traditional methods often use "post-processing" to fix errors—for example, generating a name and then using fuzzy string matching to find the closest real entity. However, as noted in VulLibGen, post-hoc correction cannot recover from a model that has already wandered down a completely wrong reasoning path.
By contrast, prefix-constrained decoding guides the model's "thought process" at every single token. It doesn't just fix the output; it reallocates the model's probability mass toward valid candidates during the search itself. This turns a generative model into a high-precision retrieval engine, combining the deep semantic understanding of neural networks with the rigorous integrity of structured databases.