Prompt lookup drafting in llama.cpp gets 42x faster, with a Lemire PR pushing it to 140x

A 42x speedup, now stacked to 140x

In a blog post published on September 26, Hayder Tirmazi describes a set of changes that make prompt lookup drafting in llama.cpp up to 42 times faster while using up to 2.6 times less memory. The optimizations draw on earlier performance work by Daniel Lemire and Martin Ankerl and focus on the data structures behind llama.cpp's n-gram caches. After publication, Lemire contributed a pull request adding a further 4.2x speedup, which Tirmazi says brings the combined improvement to as much as 140x. The post reached the Hacker News front page.

What prompt lookup decoding does

Prompt lookup decoding, also known as n-gram speculation, is a stripped-down form of speculative decoding. Rather than running a second neural network to draft tokens for the main model to verify, it uses an n-gram model: given the previous n tokens, it predicts whichever token most frequently followed that sequence in some corpus. llama.cpp, vllm and Hugging Face's transformers library all support the technique.

llama.cpp keeps three caches for this. The context cache stores n-grams of length 1 to 4 from the tokens currently being processed and is updated as generation proceeds. The dynamic cache accumulates counts from earlier runs, such as previous conversations. The static cache holds 2-grams from an offline text corpus built with the llama-lookup-create tool.

When drafting, llama.cpp tries n = 4, 3, 2 and 1 in that order, scoring each vocabulary token by how often it followed the previous n tokens in the context or dynamic cache, with candidates that also agree with the static cache given a large weight bonus. A token is only drafted if the n-gram has appeared at least a minimum number of times and the token followed it in at least a set fraction of those occurrences; as of release b11182 these thresholds are hard-coded. The dynamic cache is consulted only when the context cache produces no passing candidate at any n, and if both fail, llama.cpp falls back to the static cache alone.

Where the bottleneck was

According to Tirmazi, the caches were built from nested C++ std::unordered_map instances: an outer map keyed by n-gram, holding inner maps that map each following token to its count. His first fix was simply to stop copying the inner maps, an issue he characterizes as closer to a bug fix than an optimization. The rest of the work applies techniques drawn from Lemire's and Ankerl's prior performance engineering. Because none of the changes alter the drafting algorithm itself, token acceptance rates remain effectively identical to the original implementation; what improves is latency per drafted token, static cache load time and static cache memory footprint.

How it was measured

Tirmazi benchmarked with llama.cpp's own example tooling: llama-lookup-create to build static caches from WikiText-103, and llama-lookup-stats, which replays a file's tokens as simulated model output and records how many drafted tokens match, how long drafting took and how long the static cache took to load. He tested the full 541 MB corpus plus 25, 50, 100 and 200 MB subsets, along with a zero-corpus configuration that measures the context and dynamic caches alone. All figures are medians of three runs, with minimum and maximum values shown, at an assumed model context of 4,096 tokens. The hardware was an Apple M4 Pro with 14 cores and 48 GB of memory. The evaluation method follows the pull request by JohannesGaessler that originally added the static n-gram cache to llama.cpp, and Tirmazi has published his code and results in a companion repository.

Why it matters

Speculative decoding is one of the few ways to speed up autoregressive generation without changing the model itself, and prompt lookup is its cheapest variant because it requires no extra weights, a good fit for local inference where llama.cpp lives. But the drafting step sits on the critical path: if n-gram lookups are slow, or the static cache is expensive to load and hold, the technique gives back much of its benefit. Cutting drafting latency by up to 42x, and to a reported 140x with Lemire's follow-up, means more of the theoretical speedup survives to the user, while the 2.6x memory reduction frees room on machines where RAM is shared between model weights, the KV cache and any speculative machinery. The episode is also a reminder that in mature inference engines, plain data-structure engineering, replacing nested maps and eliminating unnecessary copies, can still deliver order-of-magnitude wins, and that open-source collaboration can compound them shortly after a blog post appears.