Standard autoregressive language models generate text through a sequence of highly optimized matrix multiplications. For each token, the model projects its top-layer hidden state to a vocabulary distribution, a process that modern GPU hardware executes with massive parallelism. However, non-parametric extensions—such as nearest-neighbor language models (Khandelwal et al.)—introduce an external datastore lookup directly into this inner generation loop.
Instead of relying solely on static parametric weights, the model queries millions or billions of high-dimensional vectors to find the $k$-nearest neighbors ($k$NN) for every single token generated. This architectural shift introduces a severe computational bottleneck: the primary cost of inference shifts from fast neural network forward passes to expensive, irregular vector database lookups.
The Anatomy of the Per-Token Latency Tax
To understand why per-token retrieval causes such a drastic slowdown, we must look at the mechanics of the generation step. In a standard transformer, the context window grows incrementally, and computing the next-token distribution requires minimal memory movement relative to the compute bound.
When a $k$NN retrieval mechanism is integrated, the workflow changes fundamentally:
- Query Generation: The model computes a dense hidden representation for the current token context.
- High-Dimensional Search: This representation is used as a query vector against an external datastore containing keys for every token in a reference corpus.
- Distribution Interpolation: The distances to the $k$-nearest neighbors are converted into a probability distribution and blended with the model's native vocabulary distribution.
As highlighted by Wang et al., executing these high-dimensional vector searches across millions of entries at every single decoding step creates an immense computational bottleneck. This latency tax is paid across a wide variety of tasks. Whether adapting models for machine translation (Deguchi et al.), deploying grammatical error correction (Vasselli et al.), or expanding label spaces via fuzzy verbalizers in zero-shot classification (Shi et al.), the requirement to perform top-$k$ retrieval at every timestep severely limits real-time deployment.
The Hardware and Algorithmic Mismatch
The root cause of retrieval-induced inference latency is a fundamental mismatch between neural network workloads and vector search operations on modern hardware.
GPUs are designed for high-throughput, dense, deterministic matrix mathematics. They excel when the same operations are applied to contiguous blocks of memory. Nearest-neighbor search over massive datastores, by contrast, is a sparse and irregular memory-access problem. Even when utilizing highly optimized approximate nearest neighbor (ANN) indexing structures, traversing a quantization tree or a proximity graph requires random memory lookups that are fundamentally memory-bandwidth bound rather than compute-bound.
Consequently, the time spent waiting for the vector database to return the nearest neighbors dwarfs the time required for the transformer's forward pass. In systems like Retrieval-Augmented Generation (RAG), this nearest neighbor search operation acts as the primary driver of end-to-end inference latency, frequently rendering the system impractical for high-throughput or interactive production environments (Bergman et al.).
Strategies for Overcoming the Bottleneck
To bridge the gap between the exceptional generalization capabilities of non-parametric models and the strict latency constraints of real-time applications, researchers have developed several distinct optimization paradigms.
Datastore Compression and Pruning
One direct way to reduce search latency is to shrink the size and dimensionality of the search space. The time complexity of nearest neighbor search scales with both the number of vectors in the datastore and their underlying dimensionality. To address this, Wang et al. introduced a cluster-based "Compact Network" designed to compress feature dimensions by over 90% while simultaneously pruning redundant tokens from the datastore. By reducing the footprint of the vector space, they achieved a 57% reduction in inference latency without degrading translation quality.
Approximate Caching
Rather than optimizing the search itself, another approach seeks to bypass the vector database entirely whenever possible. Because consecutive tokens in a generation sequence often share highly overlapping semantic contexts, querying the database at every single step is frequently redundant. Frameworks like PROXIMITY (Bergman et al.) exploit this temporal and semantic redundancy by implementing approximate caching mechanisms. By reusing previously retrieved document contexts for subsequent, highly similar queries, they significantly cut down the number of expensive database calls.
Dynamic Token Merging
The overhead of similarity calculations also appears internally when managing long-context attention mechanisms, such as Key-Value (KV) caches. In these scenarios, the "datastore" is the history of the current generation session. The $\text{D}_{2}\text{O}$ framework (Wan et al.) addresses this by dynamically calculating token similarity scores and executing weighted merges to compress the active cache. While computing these similarities introduces a minor per-token computational cost during the forward pass, it yields a net positive return by dramatically shrinking the memory pool, ultimately accelerating overall generation throughput.
Key Foundational Work
Improving Similarity Measures for Short Segments of Text (2007) — contributed 1 concept elements to this direction.
Similarity-Based Estimation of Word Cooccurrence Probabilities (1994) — contributed 1 concept elements to this direction.