Hashed Bucket Memories for Search-Free Nearest-Neighbor Language Models

Nearest-neighbor language models improve a neural model's next-word predictions by consulting a large external memory. Each generated word triggers a search for the stored contexts most similar to the current one, and the model blends in the words that followed those contexts. The memory is what makes the method work, and the search is what makes it slow: every token needs a lookup over hundreds of millions of stored vectors, and that lookup dominates decoding time. We propose to remove the search entirely. Instead of storing one vector per corpus token and looking for neighbors, we hash each context's hidden state into a few buckets of a fixed-size table. Each bucket holds a compact summary of which words tend to come next. At inference the model computes a handful of hashes, reads a handful of table rows, and blends their word distributions into its own. The memory footprint is set by the table size rather than the corpus size, and adding new text means incrementing counts rather than rebuilding an index.

The idea brings feature hashing, the decades-old trick of replacing a dictionary with a hash function into a fixed array, into the inner loop of retrieval-augmented decoding. That trick has only ever been applied to sparse, discrete inputs. Two results make us think it can work on continuous model states. First, coarse approximate search in nearest-neighbor language models helps rather than hurts, which suggests that merging nearby contexts is a feature rather than a bug. Second, most memory entries are redundant with what the base model already knows. If hashed buckets keep most of the perplexity benefit at a fixed, small memory and constant-time lookup, the latency and storage costs of token-level external memory largely go away.

Core Claim

A $k$NN-LM (nearest-neighbor language model; Generalization through Memorization) stores a key–value pair for every corpus token: the hidden state of the preceding context and the word that came next. At test time it interpolates a neighbor-derived distribution with the model's own. We replace the key store and its search index with $L$ hash tables. Table $\ell$ maps a hidden state $f(c)$ to a bucket $h_\ell(f(c)) \in \{1,\dots,B\}$ using $b$ random hyperplane sign bits. Each table draws its own independent hyperplanes, so the tables carve the space into differently offset coarse cells. This is the same design as the overlapping hashed tilings in Sutton's CMAC work on continuous control (Sutton). Each bucket stores only a small fixed number $m$ of (next-token, weight) slots, maintained as a heavy-hitter summary. The prediction is

$$p(w \mid c) = \lambda(c)\,\frac{1}{L}\sum_{\ell=1}^{L} \hat p_\ell\big(w \mid h_\ell(f(c))\big) + \big(1-\lambda(c)\big)\,p_{\text{LM}}(w \mid c),$$

where $\hat p_\ell$ is the normalized slot distribution in the addressed bucket of table $\ell$, and $\lambda(c)$ is a mixing weight. The weight grows with the total mass found in the addressed buckets and is zero when all buckets are empty, which gives a free "skip retrieval" gate. The claim is that this search-free memory recovers most of the $k$NN-LM perplexity gain at a memory cost of $L \cdot B \cdot m$ slots, which is constant in corpus size, and at a per-token cost of $L$ hash computations and $L$ row reads. Hash collisions between nearby contexts act as the smoothing that approximate search was found to provide.

Relation to Prior Work

Three papers motivate the design. Why do Nearest Neighbor Language Models Work? found that FAISS approximate search beats exact search by 2.6% relative perplexity on WikiText-103. That is evidence that pooling neighbors coarsely regularizes the memory, and our buckets push the pooling all the way to aggregation. The same paper found that a parametric two-view ensemble recovers only part of the gain, so the non-parametric memory is doing something a fixed head does not. What Knowledge Is Needed? showed that 66.7% of domain datastore entries are already predicted correctly by the base model and pruned up to 45% with no BLEU loss. Efficient Nearest Neighbor Language Models found retrieval helps only 39% of the time on WikiText-103. Both results say most of what a datastore stores is unnecessary.

Feature hashing for large scale multitask learning supplies the core move: a fixed array addressed by a hash in place of a dictionary. It also supplies the constraint. Its bounds degrade when a few high-norm or high-frequency features dominate, which in our setting means frequent function words swamping buckets. We therefore borrow the redundancy criterion from the knowledge-margin paper as an insertion filter. A context is written into the tables only if the base model gets its next word wrong or assigns it low probability. Bloom embeddings and Malmasi and Dras report that collisions can regularize discrete models. We test whether that transfers to continuous states.

The closest systems all keep a search step that we drop. HASH-RAG learns supervised binary codes for 261M propositions and still runs a Hamming search over all of them, at document rather than token granularity. Proximity uses random-hyperplane hashing to cache sentence-level RAG queries and falls back to the vector database on a miss. In our design the hash table is the memory, and there is no backend. PCKMT trains a compact network to shrink keys from 1024 to 64 dimensions, but still computes float distances over millions of keys per step. Greedy merging in He et al. merges same-target neighbors but still searches the merged store. Subset kNN-MT obtains a 132.2x speedup by first retrieving source sentences. That anchor does not exist in open-ended language modeling, which is one reason we target it.

Research Program

We will build the hashed bucket memory on top of a frozen WikiText-103 language model and a frozen translation model. The construction pass is one forward pass over the corpus, exactly as for $k$NN-LM. For each token we compute $L$ bucket addresses and update each bucket's slot summary. The insertion filter skips tokens the base model already predicts confidently.

We will study four design questions. The first is the addressing input: raw hidden states, PCA-reduced states, or states passed through a PCKMT-style compact network. The second is the bits per table $b$. It sets the cell size and therefore the collision rate, and we expect a U-shaped perplexity curve: too few bits over-smooth, and too many bits leave buckets empty. The third is the number of tables $L$, which trades lookups for the smoothing that multiple offset tilings provide. The fourth is the slot budget $m$ together with the insertion threshold.

We will also analyze what collisions do. On held-out tokens we will measure how often the bucket's top word matches the exact nearest neighbors' top word. We will do this separately for rare and frequent targets, because the norm-skew result predicts that rare words suffer most. The streaming experiment needs no new machinery. New domain text is simply hashed into the existing tables, with older slot weights exponentially decayed. Memory therefore stays constant and no index or model is rebuilt.

Baselines

The naive reference point is the frozen base language model with no memory. Its perplexity on WikiText-103 sets the floor. Published bases differ across papers: 18.65 in Drozdov et al. and 21.75 in Xu et al.. We will therefore rerun everything on one shared checkpoint and report gains as the fraction of the full $k$NN-LM gain recovered.

The quality ceiling is vanilla $k$NN-LM with a full FAISS datastore. Khandelwal et al. report 15.79 perplexity on WikiText-103, and Drozdov et al. report 16.12 for vanilla and 15.50 for an adaptive variant. We will rebuild it on our checkpoint with the published settings.

The strongest efficiency competitor is the combined system of He et al.: adaptive retrieval, greedy merging, and PCA. It reports a 6.6x speedup on WikiText-103, from 277 to 1835 tokens per second at unchanged perplexity, and a 5.4x speedup on Law-MT with perplexity improving from 12.64 to 12.29. It is the strongest competitor because it already attacks both the number of lookups and the cost of each lookup without leaving the $k$NN framework. We will run it on the same hardware, checkpoint, and corpus. Its FAISS index will be tuned under a fixed search budget, with the PQ code size swept so that some of its configurations match our table's byte count. Beating it means one of two things: equal perplexity at higher tokens per second and equal or smaller memory, or lower perplexity at matched memory and throughput.

For translation we will compare against PCKMT on the IT domain. It reports 47.94 BLEU against 47.20 for vanilla $k$NN-MT and 38.35 for the base model. We will also compare against kNN-KD, which reports an average gain of 2.56 BLEU across domains with no retrieval at inference.

Two ablations isolate the key ingredient, which is aggregating values in hidden-state-addressed buckets. The first keeps the identical table structure but addresses it by a hash of the previous $n$ token IDs instead of the hidden state, which is a hashed n-gram memory. The second keeps the same binary hash codes as per-token keys and runs exact Hamming search, the HASH-RAG-style alternative, instead of aggregating. Both get the same byte budget.

Why not just…?

Why not just hash the previous few tokens into an n-gram table? This is the most serious threat, because a hashed n-gram table interpolated with the language model is cheaper still and needs no hidden states. The n-gram-addressed ablation above settles it directly at equal memory. Our hypothesis is that hidden states capture paraphrased and long-range contexts that exact n-grams miss, and the rare-word breakdown should show where they differ. If the n-gram table matches the hidden-state table, the contribution shrinks to "hashed n-gram memories are enough", and we will report that plainly.

Why not just store binary hash codes per token and search them, as HASH-RAG does? Binary codes do cut storage 32x per vector and retrieval time by 90% in HASH-RAG. But memory and search work still grow with corpus size, and token-level decoding multiplies that cost by every generated word. The search ablation tells us whether aggregation loses perplexity relative to per-token neighbors. The regularization result of Xu et al. gives some reason to expect that it will not.

Why not just distill the memory into the model with kNN-KD? Yang et al. remove retrieval cost entirely, and on a static domain they may well win. The cost is that any new text requires another offline neighbor search and another training run. Our streaming experiment measures exactly that cost, as BLEU on the new domain against wall-clock update time. We concede that on static benchmarks distillation is the reference to beat on speed.

Why not just add adaptive gating to a standard FAISS index? Gating alone skips about 60% of lookups (He et al.). In out-of-domain translation, where base-model confidence is low, most steps still trigger a full search. The He et al. combined system is our main baseline for this reason. We will also report latency on Law-MT, where gating helps least.

Proposed Experiments

On WikiText-103 we will report perplexity, tokens per second on one GPU, and memory in gigabytes for the base model, $k$NN-LM, the He et al. combined system at several PQ budgets, both ablations, and the hashed bucket memory across a sweep of $b$, $L$, and $m$. The decisive plot is perplexity against memory at fixed throughput. We will also check for the predicted U-shape in $b$, which would show collisions acting as smoothing rather than pure noise.

On the multi-domain translation suite (IT, Medical, Law, Koran) and OPUS-Law we will report BLEU and COMET against PCKMT, vanilla $k$NN-MT, and kNN-KD. The update test builds tables on IT, streams in Law, and compares against re-distillation and against rebuilding the FAISS index, measuring time to reach a target Law BLEU.

The project counts as a success if the hashed memory recovers at least most of the $k$NN-LM perplexity gain at under a tenth of an IVF-PQ index's memory, and runs faster than the He et al. system. It is falsified if it recovers less than half of the gain at matched memory, or if the n-gram-addressed table does as well. In either case the honest conclusion is that hidden-state neighborhoods do not survive bucket aggregation.