llama.cpp Contributor Achieves Up to 140x Faster Prompt Lookup Drafting with New Optimizations

Hayder Tirmazi announced significant performance optimizations for prompt lookup decoding (also known as n-gram speculation) in llama.cpp. The initial set of optimizations achieved up to 42x faster drafting and 2.6x less memory usage compared to the previous implementation. An additional pull request by Daniel Lemire further improved performance, bringing the total speedup to up to 140x.

Core Optimizations

The improvements target the n-gram caches (context, dynamic, and static) used for speculative decoding. The process involved four key steps:

• Stop Copying Maps (PR #2): Changed inner maps to be read by reference instead of copied, resulting in 4.5x–25.6x faster drafting.
• Outer Map to Flat Hash Map (PR #5): Replaced std::unordered_map with ankerl::unordered_dense::segmented_map to improve cache friendliness, yielding 1.41x–1.65x faster load times.
• Inner Map to Sorted Vector (PR #10): Replaced inner hash maps with sorted std::vectors, leveraging the observation that 64% of 2-grams have only one follower. This reduced peak memory by up to 1.97x and improved drafting speed by 2.09x (without static cache).
• Static Cache to constmap: Utilized Daniel Lemire’s constmap for the static cache. This reduced static cache load times by 6.32x–16.12x and peak memory by up to 1.30x compared to the sorted vector implementation.

Performance Metrics

Benchmarks were conducted on an Apple M4 Pro (14 cores, 48GB RAM) using the WikiText-103 dataset. Key results include:

• Drafting Latency: For a 541MB corpus, latency dropped from 165.48 µs (baseline) to 1.18 µs (with Lemire’s additional PR #12). For smaller corpora (0 MB), latency dropped to 0.45 µs.
• Load Time: Static cache loading for a 541MB corpus improved from 3.76 s (sorted vectors) to 0.23 s (constmap).
• Memory Usage: Peak memory for a 541MB corpus decreased from 3.55 GB (baseline) to 1.31 GB (constmap + Lemire PR).

Technical Implementation

The constmap implementation packs 2-grams into contiguous arrays of (token, count) pairs. Daniel Lemire’s additional optimization (PR #12) speeds up the process by checking total n-gram counts before calculating individual candidate scores, skipping unnecessary computations when thresholds are not met.