Researchers Speed Up LLM Decoding by Up to 82% by Swapping in a Vector Search Trick

TL;DR

• Researchers Martin Loretz and Sepp Hochreiter propose replacing the standard dense vocabulary projection in LLMs with an HNSW-based vector index for maximum inner product search.
• Tested on CPU inference across Gemma 3, Llama 3.2, and Qwen 3, the method boosted batch-size-one decoding throughput by up to 82% on Gemma 3 270M.
• Generation quality held up under AlpacaEval evaluation, meaning the speed didn’t come at the cost of coherent output.
• The technique is a drop-in swap for one specific step in decoding, not a retrain of the whole model.

A Fix Aimed at One Slow Step

Every time an autoregressive language model spits out a word, it has to score that word against every single entry in its vocabulary before picking the winner. For a compact model with a huge multilingual vocabulary, that scoring step becomes a memory-bandwidth headache, and it’s one that gets worse, not better, as models shrink and vocabularies grow.

Loretz and Hochreiter’s paper reframes that step as a search problem instead of a brute-force sweep. They swap the dense output projection and top-k selection for an HNSW-based vector index, essentially asking the model to look up its best candidates rather than compute a score for every token in the dictionary. The team ran the approach on CPU inference across three model families, Gemma 3, Llama 3.2, and Qwen 3, and measured end-to-end throughput at batch size one, the setting that matters most for single-user, latency-sensitive chat.

The headline number is an 82% throughput increase for Gemma 3 270M, a genuinely small model where the vocabulary-to-parameter ratio is brutal. Crucially, the paper reports that AlpacaEval scores held steady, so the speedup didn’t come from cutting corners on output quality.

What This Means

I’ve read a lot of inference-optimization papers that shave a few percentage points off latency and call it a breakthrough. An 82% throughput jump on a real model, without a quality hit on a real eval, is the kind of number that makes you sit up. Whether it survives contact with production traffic is a separate question, but it’s not a rounding-error claim.

Here’s the analogy that keeps this concrete for me. Picture an apartment building with fifty thousand mailboxes and one elevator. Every time someone needs mail, the standard approach is to ride up, check every single box on every floor, then come back down, even though the mail carrier already knows which handful of boxes are likely to have something in them. That’s what dense vocabulary projection does at every decoding step: it scores the entire vocabulary when only a tiny slice of it will ever get chosen. What Loretz and Hochreiter built is the equivalent of a directory board in the lobby, sorted so you walk straight to the three or four doors most likely to answer, instead of checking all fifty thousand.

Why does this matter more for small models than large ones? Because a compact model’s parameter count doesn’t shrink its vocabulary. Gemma 3 270M still needs to cover the same multilingual token space as its bigger siblings, which means the output embedding matrix eats a disproportionate share of memory bandwidth relative to the rest of the model. That’s exactly the mismatch this paper targets, and it’s why the biggest gain shows up on the smallest model tested. Larger models with more compute to hide the bottleneck behind should see smaller, though probably still real, gains.

The fact that this works across three separate model families, Gemma 3, Llama 3.2, and Qwen 3, without architectural surgery is the part worth sitting with. A drop-in swap that doesn’t require retraining is the kind of thing that actually gets adopted, versus the kind that gets cited and forgotten.

Where This Bottleneck Comes From

This isn’t a new problem, it’s an old one getting sharper. As vocabularies have ballooned to handle dozens of languages and better tokenization, the final projection layer, sometimes called the LM head, has quietly become one of the heaviest single matrices in many architectures. For a big frontier model with tens of billions of parameters, that matrix is a rounding error. For a 270-million-parameter model built to run on a phone or an edge device, it can be a huge chunk of the total memory footprint.

Approximate nearest-neighbor search, the family of techniques HNSW belongs to, has been a workhorse in recommendation systems and embedding retrieval for years. Applying it to the vocabulary projection step is a fairly natural idea in hindsight, but natural ideas still need someone to actually build and measure them. That’s what this paper does: it takes a well-understood search structure and points it at a decoding bottleneck that’s been hiding in plain sight, especially as the industry pushes harder on small, on-device models where every millisecond of latency and every byte of memory bandwidth counts.

Three Things Worth Watching

The first thing to watch is whether this holds up on GPU inference, not just CPU. The paper’s numbers come from CPU decoding, and GPU memory bandwidth characteristics are different enough that the gains could shrink, stay flat, or even grow. Second, keep an eye on larger vocabulary models, especially heavily multilingual ones, where the theoretical case for this approach is strongest but hasn’t yet been demonstrated at scale. And third, watch whether any inference-serving framework actually ships an HNSW-based output layer as an option. A research result is one thing. A checkbox in a production serving stack is another, and that’s usually where ideas like this either take off or quietly die.

Source: arXiv