llama.cppにおけるプロンプト検索ドラフトの高速化
Faster prompt lookup drafting in llama.cpp (jadidbourbaki.github.io)
要約
llama.cppのプロンプト検索デコーディングにおいて、パフォーマンス最適化によりドラフト作成速度が最大42倍、メモリ使用量が2.6倍削減されました。Daniel Lemire氏の貢献により、さらに速度が向上し、全体で最大140倍の高速化が達成されています。この記事では、n-gramキャッシュの仕組みと、その最適化手法について解説しています。
全文翻訳
llama.cpp におけるプロンプト検索ドラフトの42倍高速化
Hayder Tirmazi
[homepage] [github] [twitter]
この記事は2026年9月26日に公開されました。
TL;DR Daniel Lemire氏とMartin Ankerl氏の作業に基づいたシンプルなパフォーマンス最適化により、llama.cpp におけるプロンプト検索デコーディングのドラフト作成を最大42倍高速化し、メモリ使用量を最大2.6倍削減しました。
更新: Daniel Lemire氏は、私の元の最適化に加えて、プロンプト検索ドラフトを最大4.2倍高速化するPRを送信しました。彼の作業により、全体的な速度向上は最大140倍になります。詳細は後述します。
[画像: コーパスサイズごとのドラフト済みトークンあたりのドラフトレイテンシ。アップストリームのllama.cppは、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ8.54、45.61、59.73、83.46、113.46、165.48 µsかかります。4つの変更をすべて適用すると、ドラフトには0.89、3.06、3.25、3.32、3.47、3.98 µsかかります。]
lama.cppやvllmなどの多くの人気のある推論エンジン、およびHugging FaceのTransformersライブラリのような機械学習ライブラリは、トークン生成を高速化するためにプロンプト検索デコーディング(n-gramスペキュラティブデコーディングとも呼ばれる)をサポートしています。プロンプト検索デコーディングは、技術的にはスペキュラティブデコーディングの特殊なケースであり、非常に単純なドラフトモデル、すなわちn-gramモデルを使用します。プロンプト検索デコーディングが使用される場合、推論エンジンは以下のルールに従って次の $k$ トークンをドラフトします。
モデルの現在のトークンを $x_1, \ldots, x_t$ とします。n-gramとは、連続する $n$ 個のトークンのシーケンスです。例えば、3-gramは $(x_1, x_2, x_3)$ または $(x_2, x_3, x_4)$、一般的には任意の $i \in {1, \ldots, t-2}$ に対して $(x_i, x_{i+1}, x_{i+2})$ となります。n-gramモデルは、前の $n-1$ 個のトークンに基づいて次のトークンを予測する確率モデルです。このアイデアは非常にシンプルです。まず、テキストのコーパスを選択し、それをn-gramに解析します。次に、各n-gramの頻度をカウントします。n-gramモデルが $n-1$ 個のトークンのシーケンスの後に続くトークンを予測する必要がある場合、コーパス内でその $n-1$ 個のトークンのシーケンスに最も頻繁に続くトークンを選択させます。
lama.cppは、3種類のn-gramキャッシュを維持しています。任意のn-gramを $\eta$、任意のトークンを $y$ とします。n-gramキャッシュは、特定のコーパスと語彙において、n-gram $\eta$ の後にトークン $y$ が続く回数 $c(\eta, y)$ を格納するデータ構造です。llama.cppで使用される3つのn-gramキャッシュは、コンテキストキャッシュ、ダイナミックキャッシュ、およびスタティックキャッシュです。
lama.cppのコンテキストキャッシュは、モデルによって処理されている現在のトークン $x_1, \ldots, x_t$ のサイズ1から4までのn-gramを格納します。コンテキストキャッシュは、モデルが新しいトークンを生成するにつれて更新されます。ダイナミックキャッシュは、モデルの以前の実行(例: 以前の会話)からのn-gramのカウントを格納します。最後に、スタティックキャッシュは、llama-lookup-createで構築された静的なテキストコーパスからのサイズ2のn-gramを格納します。それぞれを $c_{\text{ctx}}$、$c_{\text{dyn}}$、$c_{\text{st}}$ と表記します。
lama.cppは、n-gramキャッシュを使用して次のように新しいトークンをドラフトします。モデルによって処理された前の $n$ 個のトークンを $X_n = (x_{t-n+1}, \ldots, x_t)$ とします。語彙内のすべてのトークン $y$ について、llama.cppは以下の式を使用してスコアを計算します。
$$s_n^{f}(y) = f(X_n, y) \cdot w(y) ,, \text{ここで} ,, 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}$$
ここで、$f$ はコンテキストキャッシュ $c_{\text{ctx}}$ またはダイナミックキャッシュ $c_{\text{dyn}}$ のいずれかです。重み $w(y)$ は、スタティックキャッシュとも一致するトークンを優先することに注意してください。スタティックキャッシュがない場合、$w(y) = 1$ です。各 $n$ について、llama.cppは最もスコアの高いトークン $y^* = \arg\max_y s_n^{f}(y)$ を選択します。$F(X_n) = \sum_y f(X_n, y)$ を $X_n$ が後続のトークンと共に現れた回数とします。llama.cppは、2つの設定可能な閾値 $a_n$ と $p_n$ に基づいて、次のように $y^*$ をドラフトします。
$$F(X_n) \ge a_n ,, \text{and} ,, f(X_n, y^*) \ge p_n , F(X_n)$$
言い換えれば、$X_n$ は少なくとも $a_n$ 回出現し、トークン $y^$ がこれらの出現の少なくとも $p_n$ の割合で $X_n$ に続いた場合に、$y^$ がドラフトトークンとして受け入れられます。llama.cppのリリースb11182の時点では、閾値は次のようにハードコードされています。コンテキストキャッシュの場合、$(a_1, a_2, a_3, a_4) = (2, 2, 1, 1)$ および $(p_1, p_2, p_3, p_4) = (0.66, 0.5, 0.5, 0.5)$ です。ダイナミックキャッシュの場合、$(a_1, a_2, a_3, a_4) = (4, 3, 2, 2)$ および $(p_1, p_2, p_3, p_4) = (0.75, 0.66, 0.66, 0.66)$ です。llama.cppは $n = 4, 3, 2, 1$ の順に試行し、上記の条件を満たす最初の $y^*$ をドラフトします。まず $c_{\text{ctx}}$ でスコアリングします。次に $c_{\text{ctx}}$ から候補がどの $n$ に対してもパスしない場合にのみ $c_{\text{dyn}}$ でスコアリングします。$c_{\text{dyn}}$ からも候補がパスしない場合、llama.cppはスタティックキャッシュのみに頼るようフォールバックします(他のキャッシュの候補を再重み付けするためだけにそれを使用するのではなく)。余談ですが、llama.cppにおけるスタティックキャッシュの閾値は、対応する $n$、すなわち $n=2$ についてのコンテキストキャッシュの閾値と同じ値です。$C_{\text{st}}(X_2) = \sum_y c_{\text{st}}(X_2, y)$ とします。llama.cppは $C_{\text{st}}(X_2) \ge a_2 = 2$ かつ $c_{\text{st}}(X_2, y) \ge p_2 , C_{\text{st}}(X_2) = 0.5 , C_{\text{st}}(X_2)$ を満たす $c_{\text{st}}(X_2, y)$ が最大のトークン $y$ を選択し、それをドラフトします。スタティックキャッシュも失敗した場合、llama.cppは次のトークンをドラフトしません。
実験セットアップ
lama.cppのリポジトリには、ここにプロンプト検索デコーディングの例が含まれています。私が使用する2つのツールが含まれています: コーパスからスタティックキャッシュを構築するための llama-lookup-create と、プロンプト検索デコーディングのベンチマークを行うための llama-lookup-stats です。llama-lookup-stats は基本的にファイルを読み込み、ファイルのトークンをモデルの出力として扱います。llama.cppのドラフティングループをシミュレートされた「モデル出力」(すなわちファイル)上で実行し、ドラフトされたトークンのうちいくつがファイルと一致したか、ドラフトにかかった時間、スタティックn-gramキャッシュのロードにかかった時間を記録します。
WikiText-103 を使用して llama-lookup-create でスタティックキャッシュを構築し、次にWikiText-103のテストテキストを llama-lookup-stats でリプレイします。この評価方法は、llama.cppにスタティックn-gramキャッシュを追加した@JohannesGaessler氏のPRから借用しました。なお、llama.cppにおけるプロンプト検索デコーディングのアルゴリズムを変更していないため、データセットは主に受け入れ率に影響しますが、私の変更はそれを変更しません。念のため、私の変更が元の実装とほぼ同じ受け入れ率を維持していることを確認しました。ここで実際に変化する重要なメトリクスは、1) トークンあたりのレイテンシ、2) スタティックキャッシュのロード時間、3) スタティックキャッシュのメモリ使用量です。
また、スタティックn-gramキャッシュの異なるコーパスサイズでパフォーマンスがどのように変化するかを観察したかったため、約541MBのWikiText-103のフルコーパスを評価するのに加えて、WikiText-103のトレーニングテキストの最初の25MB、50MB、100MB、200MBからスタティックキャッシュを構築しました。図中のコーパスサイズ0は、スタティックキャッシュなしで実行した場合を示しており、コンテキストキャッシュとダイナミックキャッシュのみを測定します。この作業のすべての結果について、3回の実行の中央値を報告し、エラーバーは実行の最小値と最大値を示します。前述のllama.cpp PRに従い、モデルコンテキストサイズを4096トークンと仮定してベンチマークも行います。すべての実験は、14コア、48GBメモリのApple M4 Proで実行しました。私のコードと結果はすべてこのリポジトリにあります。
マップのコピーをやめる
lama.cppのn-gramキャッシュは現在、ネストされたstd::unordered_mapとして実装されています。外側のマップは各n-gramを、それに続くトークンとそのカウントのマップにマッピングします。これは最適化というよりはバグ修正に近いものです。内側のマップがドラフトステップごとに複数の場所で不必要にコピーされているのを発見しました。これを参照で読み取るためのシンプルなPRを作成しました。これにより、コーパスサイズに応じて4.5倍から25.6倍高速になり、ドラフト作成が速くなりました(下の図を参照)。レイテンシは、ドラフトされたトークンあたりの平均時間です。
[画像: コーパスサイズごとのドラフト済みトークンあたりのドラフトレイテンシ。ベースラインは、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ8.54、45.61、59.73、83.46、113.46、165.48 µsかかります。PRを適用すると、レイテンシは1.89、4.12、4.42、4.64、5.62、6.47 µsになります。] [画像: コーパスサイズごとのスタティックキャッシュロード時間。ベースラインは、コーパスサイズ25、50、100、200、541 MBに対してそれぞれ0.44、0.90、1.33、2.46、5.49秒かかります。PRを適用すると、ロード時間は0.47、0.85、1.30、2.52、5.28秒になります。] [画像: コーパスサイズごとのピークメモリ使用量。ベースラインは、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ0.89、1.11、1.29、1.60、2.11、3.47 GBのピークを示します。PRを適用すると、ピークメモリは0.90、1.15、1.35、1.64、2.18、3.55 GBになります。]
外側マップ -> フラットハッシュマップ
lama.cppはn-gramキャッシュをマップのマップとして実装しています。
typedef std::unordered_map<common_ngram, common_ngram_cache_part,
common_ngram_hash_function> common_ngram_cache;
外側のマップ common_ngram_cache は、各n-gramを、それに続く各トークンとそのカウントを格納する内側のマップ common_ngram_cache_part にマッピングします。例えば、「of the」が「city」に6回、「war」に3回、「year」に1回続いた場合、n-gramキャッシュは次のようになります。
common_ngram_cache
("of", "the") -> common_ngram_cache_part { "city": 6, "war": 3, "year": 1 }
("in", "the") -> common_ngram_cache_part { ... }
....
lama.cppは現在、外側と内側の両方のマップを std::unordered_map として実装しています。しかし、標準ライブラリの std::unordered_map の実装は、衝突解決に連鎖を使用し、バケットとしてリンクリストを使用するため、キャッシュ効率が悪く、非常に遅いことが知られています。GoogleのSwiss Tables(最近Golangにも追加されました)やMartin Ankerl氏のunordered_dense mapsなど、多くの優れた代替手段があります。ankerl::unordered_dense を選択したのは、1) その設計とパフォーマンスが非常に気に入ったこと、2) llama.cppにabseil全体を依存関係として追加しようとするよりも手間がかからないためです。
私の変更は、このPRにあります。これにより、1) スタティックn-gramキャッシュのロードがコーパスサイズに応じて1.41倍から1.65倍高速になり、2) 新しいトークンのドラフトが1.02倍から1.13倍高速になり、3) スタティックキャッシュの使用メモリが1.07倍から1.11倍削減されます。下の図を参照してください。デフォルトの map バリアントではなく、ankerl::unordered_dense の segmented_map バリアントを使用しています。デフォルトの map バリアントは、すべてのエントリを1つのベクトルに保持し、それが満杯になると倍増します。541MBのフルコーパスで map バリアントを実験したところ、ベクトルの最終的な倍増により、スタティックキャッシュがベースラインよりも1.16倍多くのメモリを使用しました。ここでベースラインとは、不要なマップコピーを削除した私の以前のPRのことです。segmented_map バリアントは、4096バイトのセグメントでマップを成長させることでこの問題を回避し、ピークメモリ使用量を削減します。
[画像: コーパスサイズごとのドラフト済みトークンあたりのドラフトレイテンシ。コピー修正前は、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ1.89、4.12、4.42、4.64、5.62、6.47 µsかかります。PR適用後は、1.72、3.94、4.11、4.55、4.96、5.81 µsになります。] [画像: コーパスサイズごとのスタティックキャッシュロード時間。コピー修正前は、コーパスサイズ25、50、100、200、541 MBに対してそれぞれ0.47、0.85、1.30、2.52、5.28秒かかります。PR適用後は、0.29、0.53、0.92、1.65、3.51秒になります。] [画像: コーパスサイズごとのピークメモリ使用量。コピー修正前は、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ0.90、1.15、1.35、1.64、2.18、3.55 GBのピークを示します。PR適用後は、0.88、1.11、1.29、1.56、2.07、3.36 GBになります。]
内側マップ -> ソート済みベクトル
前のセクションでは、外側のマップを ankerl::unordered_dense::segmented_map に置き換えました。内側のマップはまだ古い std::unordered_map のままです。ほとんどのn-gramはフォロワーが非常に少ないため、各内側マップに std::unordered_map やその他のハッシュマップを用意するのはメモリの点で非常に無駄が多いことに注意してください。WikiText-103から作成されたスタティックキャッシュで簡単な計算をすると、次のCDFが得られます。
[画像: 2-gramおよび(2-gram, トークン)ペアの累積シェアを、2-gramあたりの異なるフォロワー数(対数スケールで1から22,349)で示します。64%の2-gramは1つのフォロワーを持ち、99%以上は最大100のフォロワーを持ちます。ペアはゆっくりと増加し、最大の2-gramでようやく1に達します。]
重要な観察結果は、スタティックn-gramキャッシュのドラフトに使用される2-gramの64%が1つのフォロワーしか持たないため、単純に std::vector を使用する方が、ハッシュマップを維持するよりもメモリ効率がはるかに高いということです。しかし、分布はかなり裾が重いです。頻繁な2-gramの一部は、語彙からの数千の異なるトークンに続いており、図が $10^4$ までしか伸びず、その後テールが $\to 1$ に収束する理由です。そのため、単純な std::vector を使用すると、テールのn-gramの検索レイテンシが爆発的に増加します。そこで、代わりにソート済み std::vector を使用して、検索をテールのn-gramに対して $\mathcal{O}(\log n)$ に保ちました。
私の最初のバージョンでは、単純に std::lower_bound をソート済み std::vector で使用しました。しかし、このアプローチはドラフト速度をわずかに低下させ、ベースライン(外側のマップを ankerl::unordered_dense::segmented_map に置き換えた前の最適化)の0.89倍の速度になりました。追加時間のほとんどは、数千のエントリを持つ可能性のある頻繁な2-gramのフォロワーの検索に費やされます。libc++での std::lower_bound のループは、(トークン、カウント)ペアのベクトルに簡略化すると、次のようになります。
const value_type * first = pairs;
size_t len = n;
while (len != 0) { // 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;
}
}
return first - pairs;
残りの長さ len は各比較の結果に依存し、反復回数も同様です。8エントリの検索は、トークンに応じて3回または4回の反復で完了します。CPUは、現在の反復のエントリがメモリから到着するまで(数千エントリを持つベクトルではキャッシュミスが多い)、len != 0 を評価できません。
私のバージョンでは、長さを比較から分離しています。
const value_type * base = pairs;
while (n > 1) { // nが1になるまでループ
const size_t half = n / 2;
base = base[half].first < token ? base + half : base; // baseのみがエントリに依存
n -= half; // nはどのエントリにも依存しない
}
return (base - pairs) + (base->first < token);
ここでは、比較の結果に関わらず n は同じ量だけ減少します。8エントリの検索は常に3回の反復で完了し、n は8から4、2、1へと変化します。CPUはど のエントリも待たずに n > 1 を評価できるため、現在の検索の読み込みが完了する間に次の候補トークンの検索に進むことができます。
私の変更は、このPRにあります。フラットハッシュマップと比較して、スタティックキャッシュがない場合はドラフトが2.09倍、スタティックキャッシュがある場合は1.19倍から1.25倍高速になります。このPRは、ピークメモリも最大1.97倍削減します。スタティックキャッシュのロード時間はほぼ同じです。
[画像: コーパスサイズごとのドラフト済みトークンあたりのドラフトレイテンシ。フラットハッシュマップは、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ1.72、3.94、4.11、4.55、4.96、5.81 µsかかります。PR適用後は、0.82、3.31、3.46、3.68、3.95、4.78 µsになります。] [画像: コーパスサイズごとのスタティックキャッシュロード時間。フラットハッシュマップは、コーパスサイズ25、50、100、200、541 MBに対してそれぞれ0.29、0.53、0.92、1.65、3.51秒かかります。PR適用後は、0.23、0.48、0.87、1.65、3.76秒になります。] [画像: コーパスサイズごとのピークメモリ使用量。フラットハッシュマップは、コーパスサイズ0、25、50、100、200、541 MBに対してそれぞれ0.88、1.11、1.29、1.56、2.07、3.36 GBのピークを示します。PR適用後は、0.85、0.94、1.02、1.10、1.30、1.71 GBになります。]
スタティックキャッシュ -> constmap
Daniel Lemire氏は最近、binary fuse filtersに基づいた、文字列から64ビット整数への不変マップの最適化された実装であるconstmapを発表しました。
[画像: Daniel Lemire氏 (@lemire) による9月24日の投稿: この夏、constmapデータ構造を発表しました。Python、C、Rust、Goで利用可能です。(相互運用性もあります!)大規模で変更されない文字列から整数へのマップがある場合は、試してみてください。これは機械学習でよくある問題です。最も単純なバージョンでは、すべてのクエリがセット内にあると期待します。検証済みバージョンでは、キーがセット内にあることを(わずかな追加コストで)チェックします。最新バージョンでは、「paired verified」と呼ばれるバリアントを導入しました。これは以前の検証済みバリアントよりも約20%高速です。また、複数のキーを一度にクエリしたい場合(パフォーマンス向上のため)に「get_many」バリアントも追加しました。Pythonでは、dictよりもメモリ使用量が少なく、はるかに高速です...ディスクに保存して、Go、Rust、C、C++を使用している友人と共有することもできます...]
lama.cppはスタティックキャッシュをロード後に変更しないため、これはconstmapの完璧なユースケースです。スタティックキャッシュの外側のマップを検証済みconstmapに置き換えました。私の実装では、スタティックn-gramキャッシュの2-gramを(トークン、カウント)ペアの連続した配列にパックします。前の例(「of the」が「city」に6回、「war」に3回、「year」に1回続く場合)を使用すると、constmapは次のものを格納します。
pairs
...
[1000] ("city", 6)
[1001] ("war", 3)
[1002] ("year", 1)
...
constmap
("of", "the") -> (1000, 3)
("in", "the") -> ...
「of the」のフォロワーは配列の1000番目の位置から始まります。3つあります。constmapは位置1000とカウント3を合わせて1つの64ビット値として格納します。位置は値の高位40ビットを占め、カウントは低位24ビットを占めます。スタティックキャッシュファイルは、小さなヘッダー、ペアの配列、およびシリアル化されたconstmapを連続して格納します。ロード時には、ファイル全体を1つのバッファに読み込み、そのバッファ内のconstmapを fcm_verified_constmap_view で開きます。ルックアップはconstmapを1回クエリし、配列へのポインタとペアの数を返します。
common_ngram_cache_static_part common_ngram_cache_static_find(
const common_ngram_cache_static & nc_static,
const common_ngram & ngram) {
const char * key = reinterpret_cast<const char *>(ngram.tokens);
const uint64_t value = fcm_verified_constmap_lookup(
nc_static.map.get(), key, STATIC_KEY_SIZE);
if (value == FCM_NOT_FOUND) {
return {};
}
const uint64_t position = value >> STATIC_LEN_BITS;
const size_t count = value & STATIC_LEN_MASK;
return { nc_static.entries + position, count };
}
ペア自体(例: (