Faster prompt lookup drafting in llama.cpp

TL;DR Highlight

Removing map copies and swapping data structures made llama.cpp prompt lookup drafting up to 42x faster.

Who Should Read

A backend developer running local LLM inference with llama.cpp who wants to know the drafting overhead of n-gram speculation.

Core Mechanics

Prompt lookup is a very simple draft model
- Prompt lookup decoding (n-gram speculation) is a special case of speculative decoding that uses an n-gram model as the draft model.
- llama.cpp, vllm, and Hugging Face transformers support it.
Three caches, tried in order
- llama.cpp keeps a context cache, a dynamic cache, and a static cache, and drafts the first token that passes thresholds for n=4,3,2,1.
- Dynamic is used only if context fails, and static alone if both fail.
Removing inner map copies gave 4.5x-25.6x
Inner maps were being copied unnecessarily on every drafting step, so they are now read by reference.
- Drafting got 4.5x to 25.6x faster depending on corpus size.
- The author says this is closer to a bug fix than an optimization.
Outer map became a flat hash map
- Replaced std::unordered_map with ankerl::unordered_dense segmented_map, versus the previous step (copy removal).
- Static cache loading got 1.41-1.65x faster, drafting 1.02-1.13x faster, and memory use dropped 1.07-1.11x.

Community Reactions

A question about real tokens-per-second gains
- A commenter asked how much this speeds up inference for end users in tk/s.
- The article does not answer this.
Author follow-up on Lemire's extra optimization
- The author said Lemire added another optimization via PR.
- They said they would benchmark it and add it to the article, and later reported that Lemire absolutely crushed it.
Criticism over the author's dispute with the llama.cpp community
- The author asked for advice on an interpersonal issue with the llama.cpp open source community.
- One commenter said that airing it here instead of resolving it privately was the wrong approach.

How to Apply

Measure drafting time in your setup with llama-lookup-stats
- Build a static cache with llama.cpp's llama-lookup-create and replay a file with llama-lookup-stats.
- Check latency per drafted token, load time, and memory to find the bottleneck.
Audit your own cache code for needless map copies
- Find places that return nested maps by value or copy them in loops, and switch to const references.
- This single change gave 4.5-25.6x in the article.
Move read-only data to immutable structures
- Put lookup tables that never change after loading into a constmap-like immutable map with contiguous arrays.
- Measure load time and memory together to compare.
Move early-exit checks ahead of scoring
- If your code scores all candidates before checking thresholds, check total count and the top candidate first.
- Skip the remaining computation when the top candidate fails.

Try It

copy & run

# Run in a terminal after building llama.cpp (tools from the article; check options with --help)
# 1) Build a static n-gram cache
./llama-lookup-create --help

# 2) Replay a corpus and measure drafting stats
./llama-lookup-stats --help

# Next: run 3 times per corpus size (25/50/100/200MB) and compare the median draft latency, load time, and memory.

Terminology

Prompt lookup decodingA method that finds the same pattern in already-seen text to guess the next tokens in advance. It is like autocomplete reusing what you wrote earlier.

Speculative decodingA speedup technique where a small model proposes several tokens and the big model verifies them in one pass. Think of a drafter and a reviewer.

n-gramA sequence of n consecutive tokens. It is used to predict the next token from the previous few.

ChainingA way to handle hash collisions with linked lists. It chases pointers around memory, which is bad for CPU caches.

constmapAn immutable map from strings to 64-bit integers by Lemire, built on binary fuse filters. It suits data that never changes after being built.