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で計測している。

ドラフトの受理率（acceptance rate）は変化していない。アルゴリズム的な変更を一切加えず、純粋に実装レベルの最適化のみで達成した点が重要だ。

コードと全ベンチマーク結果はこのリポジトリで公開されている。

詳細は42x Faster Prompt Lookup Drafting in llama.cppを参照していただきたい。