Overcoming the Sequential Decoding Bottleneck in Generative Retrieval

29 concepts28 papers1 proposal

Traditional information retrieval (IR) and recommendation systems rely on a dual-encoder architecture. They map queries and items into a shared continuous vector space and find relevant matches using Maximum Inner Product Search (MIPS).

Recently, a compelling alternative has emerged: Generative Retrieval (GR). Pioneered by frameworks like the Differentiable Search Index (DSI) by Bahri et al., GR collapses indexing, retrieval, and ranking into a single sequence-to-sequence model. Instead of calculating vector similarities against an external index, the model internalizes the entire corpus within its parameters and directly generates a unique document identifier (DocID) or item identifier (ItemID) in response to a query. This paradigm has rapidly expanded across domains, unifying diverse tasks in recommendation systems—such as the P5 framework by Geng et al.—and knowledge-intensive language tasks.

Despite its conceptual elegance and strong accuracy, generative retrieval faces a critical roadblock preventing widespread industrial deployment: autoregressive inference latency.


The Root Cause: The Autoregressive Latency Penalty

To understand why generative retrieval is slow, we must contrast the mechanics of vector lookups with autoregressive decoding.

In a traditional dual-encoder setup, retrieval requires a single forward pass through an encoder to obtain the query vector. From there, highly optimized, sub-linear vector search algorithms (like Hierarchical Navigable Small Worlds, or HNSW) scan millions of documents in milliseconds.

In contrast, generative retrieval models must generate identifiers token-by-token. As analyzed by Lesota et al. and Bevilacqua et al., this sequential generation process introduces massive computational overhead:

  1. Sequential Dependencies: To generate a DocID of length $L$, the model must execute $L$ sequential forward passes. Each token depends on the computation of all previous tokens.
  2. Beam Search Overhead: To retrieve a ranked list of top-$K$ documents rather than just a single top match, models rely on beam search. If the beam size is $B$, the model must evaluate $B$ candidate paths at each step.

As a result, generating a short identifier can require dozens of full transformer forward passes. As noted by Lee et al. and Zhou et al., this token-by-token decoding is fundamentally slower than vector similarity lookups, often creating an order-of-magnitude latency penalty that fails the real-time constraints of large-scale production engines.

To resolve this bottleneck, recent research has converged on three primary strategies: coarse-to-fine hybridization, identifier optimization, and decoding acceleration.


Strategy 1: Coarse-to-Fine Hybridization

Instead of forcing a generative model to decode a long, highly specific identifier from scratch, several architectures offload the fine-grained search to vector space, using generation only to narrow down the search space.

[Query] ──> [Generative Model] ──> Generates Cluster ID (Fast) ──> [Dense Vector Search within Cluster] ──> [Final Document]

The Model-enhanced Vector Index (MEVI) by Zhang et al. instantiates this approach by training a sequence-to-sequence model to predict semantic cluster IDs rather than exact document IDs. This dramatically narrows down the candidate pool before a standard vector search finishes the retrieval.

Similarly, Generative Dense Retrieval (GDR), proposed by Yuan et al., uses a generative model to map queries to document clusters, offloading the "memory burden" and sequential latency that plagues pure generative models as the corpus grows. In the recommendation space, Yang et al. introduced COBRA, a framework that cascades the generation of sparse semantic IDs and dense representations to preserve the reasoning capabilities of large models while maintaining high throughput.


Strategy 2: Redesigning and Constraining Identifiers

Another line of work focuses on shortening the target sequence length $L$ or structuring the identifier space so that beam search can prune invalid paths immediately.

In the SEAL framework, Bevilacqua et al. reject arbitrary string identifiers, opting instead to generate direct substrings (n-grams) occurring within the documents. By pairing the language model with a compressed FM-Index, the authors constrain the generation exclusively to valid corpus strings, preventing the model from wasting compute on invalid search paths. This approach was unified across granularities by Chen et al. in the UGR framework.

Furthermore, the choice of how identifiers are structured determines how efficiently the beam search tree can be traversed. The MERGE framework by Zhang et al. organizes DocIDs using multi-level relevance data. By ensuring that semantically similar documents share identical prefix tokens, the model naturally groups candidates during the early steps of beam search, preventing redundant path exploration and reducing overall inference latency.


Strategy 3: Algorithmic and Decoding Optimizations

The final frontier focuses on optimizing the decoding execution itself, either by breaking sequential constraints or leveraging engineering shortcuts like caching.

For tasks involving structured document reconstruction where autoregressive overhead is notoriously prohibitive, Li et al. introduced DREAM, an end-to-end model that employs a parallel decoding strategy. By predicting layout and content information simultaneously rather than sequentially, the authors bypass traditional autoregressive bottlenecks.

In high-traffic commercial environments, engineering optimizations can make pure generative retrieval viable. In an e-commerce setting, Xie demonstrated with the GRAM framework that generative models can achieve industrial-scale performance. By utilizing highly optimized decoding configurations—specifically minimizing beam sizes and implementing real-time caching of attribute-based text codes—the system successfully competes with traditional vector-based systems under intense production traffic.

Key Foundational Work

Transformer Memory as a Differentiable Search Index (2022) — contributed 2 concept elements to this direction.
A Modern Perspective on Query Likelihood with Deep Generative Retrieval Models (2021) — contributed 1 concept elements to this direction.
Generative Multi-hop Retrieval (2022) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generative_retrieval_latency_0e36a63d,
  title = {generative retrieval latency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generative-retrieval-latency/rdr_0e36a63d33c444c28fece113ec4ca0b3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_generative_retrieval_latency_0e36a63d_v1,
  title = {generative retrieval latency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generative-retrieval-latency/rdr_0e36a63d33c444c28fece113ec4ca0b3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake