Retrieved article excerpt
Open article · Retrieved 2026-09-26T20:26:32.627999+00:00
### 42x faster prompt lookup drafting in llama.cpp
Hayder Tirmazi
[[homepage](https://jadidbourbaki.github.io/)]
[[github](https://github.com/jadidbourbaki)]
[[twitter](https://x.com/jadidbourbaki)]
This article was originally published on 2026-09-26.
**TL;DR** I make drafting for prompt lookup decoding in llama.cpp up to 42x faster while using up to 2.6x less memory through
a set of simple performance optimizations largely based on the work of
[Daniel Lemire](https://github.com/lemire) and [Martin Ankerl](https://github.com/martinus).
Drafting latency per drafted token by corpus size. Upstream llama.cpp takes 8.54, 45.61, 59.73, 83.46, 113.46, and 165.48 µs for corpora of 0, 25, 50, 100, 200, and 541 MB. With all four changes, drafting takes 0.89, 3.06, 3.25, 3.32, 3.47, and 3.98 µs.
Many popular inference engines including llama.cpp and vllm, and machine learning libraries
such as hugging face's transformers library, support
[prompt lookup decoding](https://github.com/apoorvumang/prompt-lookup-decoding)
(also called [n-gram speculation](https://x.com/joao_gante/status/1747322413006643259))
for faster token generation. Prompt lookup decoding is technically a special case of speculative decoding
that uses a really stupid draft model, an n-gram model. When prompt lookup decoding is used,
the inference engine drafts the next $k$ tokens using the following rule.
Let $x\_1, \ldots, x\_t$ be the current tokens of a model.
An n-gram is a sequence of $n$ consecutive tokens. For example, a 3-gram would be $(x\_1, x\_2, x\_3)$ or
$(x\_2, x\_3, x\_4)$ or, in general, $(x\_i, x\_{i+1}, x\_{i+2})$ for any $i \in \{1, \ldots, t-2\}$.
Now an n-gram model is a probabilistic model that predicts the next token based on the previous $n - 1$ tokens.
The idea is extremely simple. You first select some corpus of text and parse it into n-grams. You then
count the frequency of each n-gram. When your n-gram model needs to predict the next token after a sequence
of $n-1$ tokens, you make the n-gram model select the token that most frequently follows that sequence of
$n-1$ tokens in your corpus.
llama.cpp maintains three types of *n-gram caches*. Let $\eta$ be any n-gram and $y$
be any token. An n-gram cache
is a data structure that stores $c(\eta, y)$, i.e., the count of how many times the token $y$ follows the n-gram $\eta$,
for all n-grams $\eta$ and all tokens $y$ in a given corpus and vocabulary. The three n-gram caches used
by llama.cpp are the context cache, the dynamic cache, and the static cache.
llama.cpp's context cache stores n-grams of sizes 1 to 4 for the current tokens $x\_1, \ldots, x\_t$ being
processed by the model. The context cache is updated as the model generates new tokens. The
dynamic cache stores the counts of n-grams from previous runs of the model, e.g., any earlier
conversations. Finally, the static cache stores n-grams of size 2 from a static text corpus, built
with `llama-lookup-create`.
I denote the context, dynamic, and static caches by $c\_{\text{ctx}}$, $c\_{\text{dyn}}$, and $c\_{\text{st}}$, respectively.
llama.cpp drafts a new token using its n-gram caches in the following way. Let $X\_n = (x\_{t-n+1}, \ldots, x\_t)$ be the previous
$n$ tokens processed by the model. For all tokens $y$ in the vocabulary, llama.cpp computes a score using the formula
$$s\_n^{f}(y) = f(X\_n, y) \cdot w(y) \,\, \text{where} \,\,
w(y) = \begin{cases} 100 \, c\_{\text{st}}(X\_2, y) & \text{if $c\_{\text{st}}(X\_2, y) > 0$} \\ 1 & \text{otherwise} \end{cases}$$
where $f$ is either the context cache $c\_{\text{ctx}}$ or the dynamic cache $c\_{\text{dyn}}$.
Note that the weight $w(y)$ favors tokens that also agree with the static cache. Without a
static cache, $w(y) = 1$ for every token.
For each $n$, llama.cpp takes the highest-scoring token $y^\* = \arg\max\_y s\_n^{f}(y)$. Let
$F(X\_n) = \sum\_y f(X\_n, y)$ be the number of times $X\_n$ appeared with a token after it.
llama.cpp drafts $y^\*$ based on two configurable thresholds $a\_n$ and $p\_n$ in the following way.
$$F(X\_n) \ge a\_n \,\, \text{and} \,\, f(X\_n, y^\*) \ge p\_n \, F(X\_n)$$
In other words, $X\_n$ must appear at least $a\_n$ times and the token $y^\*$
must have followed $X\_n$ in at least a fraction $p\_n$ of those occurrences for $y^\*$
to be accepted as a draft token. As of release b11182 of llama.cpp, the thresholds are hard-coded
as follows.
For the context cache,
$(a\_1, a\_2, a\_3, a\_4) = (2, 2, 1, 1)$ and $(p\_1, p\_2, p\_3, p\_4) = (0.66, 0.5, 0.5, 0.5)$. For the
dynamic cache, $(a\_1, a\_2, a\_3, a\_4) = (4, 3, 2, 2)$ and $(p\_1, p\_2, p\_3, p\_4) = (0.75, 0.66, 0.66, 0.66)$.
llama.cpp tries $n = 4, 3, 2, 1$ and drafts the first $y^\*$ that passes the conditions above. It first scores with
$c\_{\text{ctx}}$. It scores with $c\_{\text{dyn}}$ only when no candidate from $c\_{\text{ctx}}$
passes for any $n$. If no candidate from $c\_{\text{dyn}}$ passes either, llama.cpp falls back to
relying only on the static cache (as opposed to only using it to reweight candidates in the other caches).
As a side note, the static cache's thresholds in llama.cpp are the same values as the context cache's thresholds for the corresponding $n$,
i.e., $n = 2$. Let $C\_{\text{st}}(X\_2) = \sum\_y c\_{\text{st}}(X\_2, y)$. llama.cpp takes the token $y$ with the
largest $c\_{\text{st}}(X\_2, y)$ and drafts it when
$C\_{\text{st}}(X\_2) \ge a\_2 = 2$ and $c\_{\text{st}}(X\_2, y) \ge p\_2 \, C\_{\text{st}}(X\_2) = 0.5 \, C\_{\text{st}}(X\_2)$.
If the static cache also fails, llama.cpp does not draft the next token.
#### Experimental Setup
llama.cpp's repository includes an example for prompt lookup decoding
[here](https://github.com/ggml-org/llama.cpp/tree/master/examples/lookup).
It includes two tools I use: `llama-lookup-create` for building a static cache from a corpus
and `llama-lookup-stats` for benchmarking prompt lookup decoding.
`llama-lookup-stats` essentially reads a file and treats the file's tokens
as the output of a model. It runs the drafting loop from llama.cpp over the simulated
"model output" (i.e. the file) and records how many drafted tokens match the file, the time it took
to draft the tokens, and the time it took to load the static ngram cache.
I build the static caches using `llama-lookup-create` with
[WikiText-103](https://arxiv.org/abs/1609.07843) and then I
replay the WikiText-103 test text through `llama-lookup-stats`. I borrowed
this evaluation method from the
[PR](https://github.com/ggml-org/llama.cpp/pull/5479)
by [@JohannesGaessler](https://github.com/JohannesGaessler) that added
the static n-gram cache to llama.cpp. Note that since I am not making any
algorithmic modifications to how prompt lookup decoding works in llama.cpp, the dataset
mainly matters for the acceptance rate, which my changes leave unchanged. Just to be safe, I make
sure my changes still have almost identical acceptance rates to the original implementation.
The important metrics here that actually change are 1) latency
per drafted token, 2) the load time of the static cache, and 3) the memory used by the static cache.
I also wanted to observe how the performance changes with different corpus sizes for the static
n-gram cache. So in addition to evaluating the full corpus of WikiText-103, which is about
541 MB, I also build static caches from the first 25, 50, 100, and 200 MB of the WikiText-103 training text.
A corpus size of 0 in the figures means I run without a static cache, which measures the context and
dynamic caches alone.
For all the results in this work, I am reporting the median of 3 runs with the error bars displaying the
min and the max value for the runs. Following the llama.cpp PR I linked
in the previous paragraph, I also benchmark assuming a model context side of 4096 tokens.
I run all my experiments on an Apple M4 Pro with 14 cores and 48 GB of memory.
All of my code and results are in this
[repository](https://github.com/jadidbourbaki/ngram-cache-bench).
#### Stop Copying Maps
The n-gram caches in llama.cpp are currently implemented as nested `std::unordered_map`s. An outer
map sends each n-gram to an inner map of the tokens that follow it and their counts.
This one is almost more of a bug fix than an optimization. I found that the inner maps were
being copied unnecessarily in multiple places on every drafting step.
I created this simple [PR](https://github.com/jadidbourbaki/llama.cpp/pull/2)
to read them by reference instead.
This immediately made drafting 4.5x to 25.6x faster depending on the size of the
corpus (see figure below). The latency is the average time spent
drafting per drafted token.
Drafting latency per drafted token by corpus size. Baseline takes 8.54, 45.61, 59.73, 83.46, 113.46, and 165.48 µs for corpora of 0, 25, 50, 100, 200, and 541 MB. The PR takes 1.89, 4.12, 4.42, 4.64, 5.62, and 6.47 µs.
Static cache load time by corpus size. Baseline takes 0.44, 0.90, 1.33, 2.46, and 5.49 s for corpora of 25, 50, 100, 200, and 541 MB. The PR takes 0.47, 0.85, 1.30, 2.52, and 5.28 s.
Peak memory by corpus size. Baseline peaks at 0.89, 1.11, 1.29, 1.60, 2.11, and 3.47 GB for corpora of 0, 25, 50, 100, 200, and 541 MB. The PR peaks at 0.90, 1.15, 1.35, 1.64, 2.18, and 3.55 GB.
#### Outer Map -> Flat Hash Map
llama.cpp implements an n-gram cache as a map of maps.
```
typedef std::unordered_map<common_ngram, common_ngram_cache_part,
common_ngram_hash_function> common_ngram_cache;
```
The outer map, `common_ngram_cache`, maps each n-gram to an inner map. The inner
map, a `common_ngram_cache_part`, map stores the counts of each token in the vocabulary
that follows the given n-gram. As an example, if
"of the" is followed by "city" 6 times, "war" 3 times, and "year" once, the n-gram cache looks like this.
```
common_ngram_cache
("of", "the") -> common_ngram_cache_part { "city": 6, "war": 3, "year": 1 }
("in", "the") -> common_ngram_cache_part { ... }
....
```
llama.cpp currently implements both the outer and inner maps as an `std::unordered_map`.
However, the standard library's implementation of `std::unordered_map` is
[famously slow](https://stackoverflow.com/a/42588384)
because it uses chaining for collision resolution with linked lists as its buckets
which is cache unfriendly. There are many great alternatives here such as Google's
[Swiss Tables](https://abseil.io/about/design/swisstables) (which
were also [recently added](https://go.dev/blog/swisstable) to Golang)
and [Martin Ankerl's](https://github.com/martinus) [unordered\_dense maps](https://github.com/martinus/unordered_dense).
I decided to go with `ankerl::unordered_dense` because 1) I really like its design and
performance, and 2) it is less of an annoyance than trying
to add all of abseil as a dependency to llama.cpp.
My change is in this [PR](https://github.com/jadidbourbaki/llama.cpp/pull/5).
This makes 1) loading the static n-gram cache 1.41x to 1.65x faster depending on the size of the corpus,
2) drafting a new token 1.02x to 1.13x faster, and 3) the static cache use 1.07x to 1.11x
less memory. See the figures below. Note that I use the `segmented_map` variant
of `ankerl::unordered_dense` instead of the default `map` variant.
The default `map` variant keeps all entries in one vector that doubles as it fills.
When I experimented with the `map` variant on the full 541 MB corpus,
the final doubling of the vectors caused the static cache to use 1.16x more memory than the baseline.
Note that the baseline here is my previous PR where I removed
the unnecessary map copying. The `segmented_map` variant avoids this issue by growing the map in
segments of 4096 bytes allowing for lower peak memory usage.
Drafting latency per drafted token by corpus size. The copy fix takes 1.89, 4.12, 4.42, 4.64, 5.62, and 6.47 µs for corpora of 0, 25, 50, 100, 200, and 541 MB. The PR takes 1.72, 3.94, 4.11, 4.55, 4.96, and 5.81 µs.
Static cache load time by corpus size. The copy fix takes 0.47, 0.85, 1.30, 2.52, and 5.28 s for cor