From 165 Microseconds to 1.18: The Data-Structure Surgery That Made llama.cpp's Speculative Drafting Up to 140x Faster

In an industry obsessed with trillion-parameter models and hundred-thousand-GPU clusters, the most satisfying speedup of the week came from something almost quaint: a hash map, a sorted vector, and a very careful look at how llama.cpp copies data it never needed to copy.

On September 26, Hayder Tirmazi published a detailed writeup of four optimizations to prompt lookup drafting in llama.cpp, the C/C++ inference engine that powers much of the local-AI ecosystem, including Ollama. Combined, they cut the latency of drafting a speculative token from 165.48 microseconds to 1.18 microseconds on the largest test corpus — roughly a 42x speedup. And in an update that reads like a passerby stopping to help push a car, computer-science professor Daniel Lemire contributed a fifth optimization on top, pushing the overall speedup to around 140x.

No model weights changed. No algorithm was reinvented. The acceptance rate of drafted tokens — the number that ultimately match what the model would have generated anyway — stayed essentially identical. This was pure data-structure surgery.

What prompt lookup decoding actually is

Speculative decoding is the trick behind most modern speedups in LLM inference: instead of asking the big model to generate every token one at a time, a cheap “draft” mechanism guesses several tokens ahead, and the big model verifies them in a single batched pass. When the guesses are right, you get multiple tokens for the cost of one forward pass.

Prompt lookup decoding — also called n-gram speculation — is the cheapest possible version of that idea. As Tirmazi puts it, it is speculative decoding “that uses a really stupid draft model, an n-gram model.” The engine simply looks at the last few tokens and asks: in text this model has already seen, what came next?

llama.cpp maintains three n-gram caches to answer that question. The context cache tracks n-grams of sizes 1 through 4 in the current token stream. The dynamic cache accumulates statistics from previous runs — earlier conversations, earlier sessions. The static cache is built offline from a text corpus using the llama-lookup-create tool and stores 2-grams from, in this benchmark, WikiText-103. Drafting consults these caches in priority order, with hardcoded acceptance thresholds — for example, the context cache requires a 4-gram to have appeared at least once and the top follower to account for at least half of occurrences.

The scheme is nearly free, which is exactly why its overhead matters. Every drafted token pays for a lookup into nested hash maps, and on a 541 MB static corpus those lookups were costing more than they should.

Fix one: stop copying maps

The first change, Tirmazi writes, was “almost more of a bug fix than an optimization.” The inner n-gram maps were being copied by value in multiple places on every drafting step instead of being read by reference.

Removing the copies alone made drafting 4.5x to 25.6x faster depending on corpus size. That single number is a quiet indictment of how easily avoidable overhead survives in widely used infrastructure — and how much headroom remains in code that everyone assumes is already fast.

Fix two: a better hash map

The n-gram caches were implemented as nested std::unordered_maps — a container whose reputation for slowness is well earned, since it resolves collisions with cache-hostile linked-list buckets. Tirmazi swapped the outer map for Martin Ankerl’s unordered_dense, choosing the segmented_map variant after discovering that the default variant’s final vector-doubling actually increased peak memory by 16% on the full corpus. The segmented variant grows in 4096-byte segments instead.

The gains here were more modest: 1.41–1.65x faster static cache loading, 1.02–1.13x faster drafting, and 7–11% less memory. But it set up the structural change that followed.

Fix three: sorted vectors and a branchless search

The real insight came from looking at the data. Some street-fighting statistics on the WikiText-103 static cache showed that 64% of the 2-grams used for drafting have exactly one follower. A hash map per n-gram is wildly overengineered for entries that contain a single (token, count) pair. But the distribution is heavy-tailed — a few frequent 2-grams are followed by thousands of distinct tokens — so a plain vector would degrade search on the tail.

Tirmazi’s answer: store followers in a sorted std::vector, keeping lookups O(log n). Then he went one step further and rewrote the binary search itself. The standard std::lower_bound loop makes the remaining search length depend on each comparison’s outcome, which means the CPU stalls waiting for a memory load before it can decide whether to continue. His version separates the length from the comparison — the length shrinks deterministically every iteration, so the processor can keep multiple searches in flight while earlier loads are still being fetched.

The result: drafting 2.09x faster without a static cache and 1.19–1.25x faster with one, plus peak memory reductions of up to 1.97x.

Fix four: an immutable map built on binary fuse filters

The static cache, once built, never changes — a perfect fit for Lemire’s recently published constmap, an immutable string-to-integer map built on binary fuse filters. Tirmazi packed all (token, count) pairs into one contiguous array and made the constmap return a 40-bit position and 24-bit count packed into a single 64-bit value. The static cache file becomes one buffer that is mapped directly into memory with zero deserialization.

This is where the numbers get dramatic: loading the static cache dropped from 3.76 seconds to 0.23 seconds on the 541 MB corpus — up to 16.12x faster. The in-memory cache now costs roughly its file size (463 MB for a 467 MB file), and peak memory fell from 1.71 GB to 1.31 GB.

The Lemire assist: check the threshold first

After the post went up, Lemire sent in a further pull request with an elegantly lazy observation: llama.cpp was computing scores for all candidate followers of an n-gram before checking whether they could pass the acceptance thresholds. If the most frequent follower can’t clear the probability threshold, no other candidate can either — so skip them all. Likewise, if the n-gram’s total count is below the minimum, skip scoring entirely.

That reordering made drafting up to 4.2x faster with a static cache and 1.9x faster without, stacking the cumulative speedup to roughly 140x over the original code.

The fine print, and why it still matters

All benchmarks ran on an Apple M4 Pro (14 cores, 48 GB RAM), replaying WikiText-103 test text through llama.cpp’s llama-lookup-stats tool against release b11182, with medians of three runs and a 4096-token context — a methodology borrowed from the upstream PR that introduced the static cache in the first place.

There is a caveat worth stating plainly: as of this writing, the pull requests live on Tirmazi’s fork of llama.cpp and have not been merged upstream, and the accompanying Hacker News thread (69 points) surfaced some friction over how the work was proposed. Until the changes land in a release, mainstream llama.cpp users won’t see these numbers.

The lesson, though, doesn’t depend on merge status. As the industry pours capital into ever-larger accelerators, the biggest percentage gains in local inference this week came from a blogger with a profiler: eliminating needless copies, matching data structures to the actual shape of the data, and letting a 64-year-old algorithm — binary search — be rethought for modern memory latency. The frontier of AI performance isn’t only in the datacenter. Sometimes it’s in the C++ between you and your model.