9月26日、Hayder Tirmziが「42x Faster Prompt Lookup Drafting in llama.cpp」と題した記事を公開した。この記事では、llama.cppのn-gramキャッシュ実装に対するシンプルな最適化を積み重ねることで、プロンプトルックアップドラフティングをコーパスサイズに応じて4.5倍〜42倍高速化した手法が紹介されている。なお記事公開後にDaniel Lemireによる追加最適化も加わり、元のllama.cppからの総合的な高速化は最大140倍に達する。この点については末尾のセクションで触れる。
プロンプトルックアップデコーディングとは
プロンプトルックアップデコーディング（n-gramスペキュレーションとも呼ばれる）は、llama.cpp、vLLM、Hugging Faceのtransformersライブラリなど主要な推論エンジンが採用するトークン生成高速化手法だ。投機的デコーディング（Speculative Decoding）の一種で、「ドラフトモデル」として極めて単純なn-gramモデルを使う。
仕組みはシンプルだ。テキストコーパスをn-gram（連続するnトークンの列）に分解し、各n-gramに続くトークンの出現頻度を数える。推論時には、直前のn-1トークンに最もよく続くトークンを「下書き（ドラフト）」として提示し、本体モデルが一括検証する。
llama.cppは3種類のn-gramキャッシュを管理している：
- コンテキストキャッシュ：現在処理中のトークン列から構築（サイズ1〜4のn-gram）
- 動的キャッシュ：過去の会話など以前の実行から構築
- 静的キャッシュ：
llama-lookup-createで事前ビルドした固定コーパス由来のビグラム（2-gram）
最大のボトルネック：マップの無駄なコピー
記事の核心は4つの最適化だが、最も効果が大きかったのが「マップの不要コピーの除去」だ。
llama.cppのn-gramキャッシュはstd::unordered_mapのネスト構造で実装されている。外側のマップがn-gramを内側のマップに対応付け、内側のマップがそれに続くトークンとその出現回数を保持する。
typedef std::unordered_map<common_ngram, common_ngram_cache_part,
common_ngram_hash_function> common_ngram_cache;
Tirmziが発見したのは、ドラフトステップのたびに内側のマップが不必要にコピーされていたという問題だ。元のコードではマップをキャッシュから取り出す際に値渡しになっており、意図的な設計ではなくAPIの誤用（const autoで受け取るべきところを参照指定し忘れた類の見落とし）だったとTirmziは指摘している。参照渡しに変えるだけのシンプルなPRで、コーパスサイズに応じて4.5倍〜25.6倍のドラフト高速化を実現した。バグ修正に近い変更で、これだけの効果が出た。
3つの追加最適化
外側マップ → フラットハッシュマップ
std::unordered_mapはチェイニング（連結リストによる衝突解決）を使うためキャッシュ効率が悪いことで知られている。Tirmziは外側のマップをMartin Ankerlのunordered_denseに置き換えた（GoogleのSwiss Tablesも候補だったが、abseilをllama.cppの依存に追加するコストを避けた）。
メモリ使用量の急増を防ぐため、デフォルトのmapではなくsegmented_mapバリアントを採用した点が細かい工夫だ。デフォルト版はベクタが満杯になると2倍に拡張するため、541MBコーパスでは最終的なメモリ使用量がベースラインより1.16倍増加してしまう。segmented_mapは4096バイト単位でセグメントを追加する方式のためピーク使用量を抑えられる。
効果：静的キャッシュのロード時間が1.41〜1.65倍高速化、メモリ使用量が1.07〜1.11倍削減。
内側マップ → ソート済みベクタ + ブランチレス二分探索
WikiText-103から作成した静的キャッシュを分析すると、64%の2-gramは後続トークンが1種類だけだった。そのような小さなマップにstd::unordered_mapを使うのはメモリの無駄だ。
そこでソート済みのstd::vectorに置き換えた。ただし一部の頻出2-gramは数千種類のトークンが後続するため、線形探索では遅すぎる。そこで二分探索（O(log n)）を使うが、ここでさらに一工夫がある。
通常のstd::lower_boundは残り要素数lenがメモリ比較結果に依存するため、CPUがループ継続判定を先読みできない（キャッシュミス時に停滞する）。Tirmziはこれをブランチレス版に書き換えた。なお以下のコードでは、通常版の変数名lenと最適化版のnはどちらも「残り探索範囲の要素数」を指す同一概念であり、表記を統一していない点に注意されたい：
// 通常版：lenが比較結果に依存する
const value_type * first = pairs;
size_t len = n;
while (len != 0) {
const size_t half = len / 2;
const value_type * mid = first + half;
if (mid->first < token) {
first = mid + 1;
len -= half + 1; // 比較結果によってlenが変わる
} else {
len = half;
}
}
// 最適化版：nは比較結果によらず一定量減る
const value_type * base = pairs;
while (n > 1) {
const size_t half = n / 2;
base = base[half].first < token ? base + half : base;
n -= half; // nは常に同じ量減る
}
return (base - pairs) + (base->first < token);
8エントリの探索で「3回または4回」だったイテレーション数が常に「3回」に確定し、CPUの投機実行が効きやすくなる。
Daniel Lemireによる追加最適化（最大140倍へ）
本記事で紹介してきた4つの最適化（参照渡し・フラットハッシュマップ・ソート済みベクタ・ブランチレス二分探索）は、元のllama.cppに対して最大42倍の高速化をもたらすものだ。記事公開後、Daniel Lemire（高速データ処理の研究者として知られる）がPRを送ってきた。Lemireの変更はTirmziの最適化の上にさらに4.2倍の高速化を加え、元のllama.cppからの総合的な高速化は最大140倍に達する。
ベンチマーク結果
評価はWikiText-103コーパスを使い、Apple M4 Pro（14コア、48GBメモリ）上で実施。コーパスサイズ0〜541MBで計測している。
| コーパスサイズ | 元のllama.cpp（µs/トークン） | 最適化後（µs/トークン） |
|---|---|---|
| 0 MB | 8.54 | 0.89 |
| 25 MB | 45.61 | 3.06 |
| 50 MB | 59.73 | 3.25 |
| 100 MB | 83.46 | 3.32 |
| 200 MB | 113.46 | 3.47 |
| 541 MB | 165.48 | 3.98 |
ドラフトの受理率（acceptance rate）は変化していない。アルゴリズム的な変更を一切加えず、純粋に実装レベルの最適化のみで達成した点が重要だ。
コードと全ベンチマーク結果はこのリポジトリで公開されている。
詳細は42x Faster Prompt Lookup Drafting in llama.cppを参照していただきたい。
