Optimizing Prompt Lookup Drafting in llama.cpp: A 42x Speedup

By Hayder Tirmazi | Originally published: 2026-09-26 [Homepage] | [GitHub] | [Twitter]

---

⚡ Executive Summary (TL;DR)

I have implemented a series of performance optimizations—heavily inspired by the research of Martin Ankerl and Daniel Lemire—that accelerate prompt lookup drafting in llama.cpp by up to 42x while simultaneously reducing memory consumption by up to 2.6x.

Update: Following my work, Daniel Lemire submitted a Pull Request that further boosts the speed of prompt lookup drafting by an additional 4.2x on top of my optimizations.

---

🔍 Understanding Prompt Lookup Decoding

Many high-performance inference engines (such as vllm and llama.cpp) and libraries (like Hugging Face's transformers) utilize prompt lookup decoding. This technique, also known as n-gram speculation, is designed to accelerate the generation of tokens.

Technically, this is a specialized form of speculative decoding. Instead of using a complex secondary model, it uses a sophisticated "really stupid" draft model: the n-gram model.

How it Works

The engine attempts to draft the next $k$ tokens. For a 3-gram model, it looks for sequences like:

• $(x_1, x_2, x_3)$
• $(x_2, x_3, x_4)$
• Generally: $(x_i, x_{i+1}, x_{i+2})$ for any $i \in \{1, \ldots, t-2\}$.

An n-gram model is probabilistic; it predicts the subsequent token based on the preceding $n-1$ tokens. By parsing a text corpus into n-grams, the model can simply select the token that most frequently followed that specific sequence in the training data.

The N-Gram Cache

The system relies on an n-gram cache, a data structure storing $c(\eta, y)$, which represents the count of how many times token $y$ follows the n-gram $\eta$.

---

⚙️ The Drafting Algorithm

To draft a new token, llama.cpp looks at the previous $n$ tokens, denoted as $X_n = (x_{t-n+1}, \ldots, x_t)$.

1. Scoring

For every token $y$ in the vocabulary, a score $s_n^{f}(y)$ is calculated:

$s_n^{f}(y) = f(X_n, y) \cdot w(y)$

Where the weight $w(y)$ is defined as: $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}$

Note: $f$ represents either the context cache ($c_{\text{ctx}}$) or the dynamic cache ($c_{\text{dyn}}$). The weight $w(y)$ ensures that tokens appearing in the static cache are heavily prioritized.

2. Selection and Validation

The token with the highest score is chosen: $y^* = \arg\max_y s_n^{f}(y)$. Let $F(X_n) = \sum_y f(X_n, y)$ be the total occurrences of $X_n$.

The token $y^*$ is accepted as a draft only if it meets these two conditions:

Condition: $F(X_n) \ge a_n \quad \text{and} \quad f(X_n, y^*) \ge p_n \, F(X_n)$

This means the sequence must appear at least $a_n$ times, and $y^*$ must follow it at least $p_n$ percent of the time.

3. Hard-coded Thresholds (Release b11182)

The values for $a_n$ (minimum count) and $p_n$ (minimum probability) are as follows:

• Context Cache:
  • $a = (2, 2, 1, 1)$
  • $p = (0.66, 0.5, 0.5, 0.5)$
• Dynamic Cache:
  • $a = (4, 3, 2, 2)$
  • $p = (0.75, 0.66, 0.66, 0.66)$

---

🛠️ Execution Flow

The drafting process follows a strict priority hierarchy:

Static Cache Fallback Logic: If both context and dynamic caches fail, llama.cpp uses the static cache independently. It selects $y$ with the largest $c_{\text{st}}(X_2, y)$ if:

• $C_{\text{st}}(X_2) \ge 2$
• $c_{\text{st}}(X_2, y) \ge 0.5 \, C_{\text{st}}(X_2)$

---

🧪 Experimental Setup

To validate these optimizations, I utilized the example provided in the llama.cpp repository.

Tools Used:

# Create static cache from corpus
llama-lookup-create 

# Benchmark the drafting performance
llama-lookup-stats 

Methodology:

1. Dataset: I used WikiText-103 to build the static cache.
2. Simulation: llama-lookup-stats treats the tokens in the test file as if they were generated by a model.
3. Verification: It iterates through the drafting loop and tracks:
   • Token match rate (Acceptance rate)
   • Drafting latency
   • Static cache load time

Since I did not alter the underlying algorithm, the acceptance rate should remain constant. I verified that my changes maintained nearly identical acceptance rates compared to the original implementation.

Key Metrics for Improvement:

1. $\text{Latency}_{\text{per\_token}}$
2. $\text{Time}_{\text{load\_static\_cache}}$

Figure 1: Conceptual representation of latency reduction.