🤖 AI

Accelerating Constrained Decoding with Token Space Compression

本論文は、制約付きデコーディングの計算オーバーヘッドを大幅に削減し、複雑な文脈自由文法における総生成時間を最大 7.5 倍高速化するオフライントークン空間圧縮手法 CFGzip を紹介する。

原著者： Michael Sullivan, Alexander Koller

公開日 2026-05-29

📖 1 分で読めます☕ さくっと読める

原著者： Michael Sullivan, Alexander Koller

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

非常に才能があるが少し無秩序なシェフ（LLM）がいると想像してください。このシェフはほぼ何でも調理できます。しかし、非常に厳格で複雑なレシピ（文脈自由文法またはCFG）に従って料理を用意する必要があります。これは特定のプログラミング言語や正確なデータ形式に相当します。

シェフが間違った材料を推測すると、料理全体が台無しになります。これを防ぐため、厳格な文法エンジン（ヘッドシェフや食品衛生検査員のような役割）を雇い、シェフの隣に立たせます。シェフが材料を追加する前に、検査員は調理台の在庫（パントリー）全体を確認し、そのレシピのこの正確な段階でその特定の材料が許可されているかどうかをチェックします。

問題点：「パントリー」が大きすぎる

問題なのは、シェフのパントリー（トークン語彙）が巨大で、数十万もの異なる材料（単語、記号、コードスニペット）を含んでいることです。

シェフが1 つの材料を追加するたびに、検査員は全体のパントリーを走査して、その特定の項目が有効かどうかを確認しなければなりません。単純なレシピ（JSON データなど）の場合、これは高速です。しかし、複雑なレシピ（C++ コードや「Bython」と呼ばれる架空の言語など）の場合、検査員は圧倒されてしまいます。あまりにも多くの可能性をチェックしなければならないため、調理プロセスが劇的に遅くなります。時には通常の2 倍から 10 倍の時間がかかることもあります。この論文では、これを「処理不可能なほど高いオーバーヘッド」と呼んでいます。

解決策：CFGZIP（「グループ化」のトリック）

著者らは、CFGZIPという新しいツールを紹介しています。これは検査員にパントリー内のすべての単一の材料をチェックさせるのではなく、調理が始まる前にパントリーを再編成します。

以下がアナロジーです：

材料のグループ化：CFGZIP はパントリーを調べ、多くの材料がレシピの目的上、互換性があることに気づきます。例えば、コードレシピの特定の部分では、if、else、while という単語がすべて文法的に同じように振る舞うかもしれません。あるいは、別の文脈では、1、2、3 という数字がすべて有効なプレースホルダーとなるかもしれません。
「代表」バケットの作成：CFGZIP はこれらの互換性のある材料をバケットにグループ化します。各バケットから1 つの「代表」材料（通常は最も短いもの）を選び、そのグループ全体に代わって立たせます。
新しいワークフロー：
- 調理前（オフライン）：システムはパントリーをこれらのバケットに分類する重労働を行います。これは一度行われ、保存されます。
- 調理中（推論）：シェフが材料を選ぶと、システムはそれをバケットからの「代表」に素早く置き換えます。検査員は全体のパントリーではなく、代表のみをレシピに対してチェックすればよくなります。
- 結果：検査員が巨大な元のパントリーではなく、代表の小さなリストをチェックするようになるため、プロセスは驚くほど高速になります。

これが重要である理由

この論文は、CFGZIP をトップクラスの文法エンジン（XGrammar2）と組み合わせることで、劇的な高速化が実現されると主張しています：

レイテンシの削減：ルールをチェックするのにかかる時間は10 倍から 100 倍（2 桁）減少します。
全体の高速化：複雑なタスクにおいて、テキスト生成の全プロセスが7.5 倍高速になります。
品質の低下なし：これは「ロスレス」な圧縮です。最終出力は、高速化なしで得られるものとバイト単位で完全に同一です。シェフは同じ完璧な料理を生み出しますが、そこに至るまでの時間が大幅に短縮されるだけです。

論文からの実世界の結果

研究者らは、3 つの異なる AI モデル（Llama、Qwen、GPT）と 4 つの異なるタスクでこれをテストしました：

JSON & XML：標準的なデータ形式。
C++：複雑なプログラミング言語。
Bython：架空のプログラミング言語（Python に似ているが、スペースの代わりに中括弧とセミコロンを使用）。

発見事項：

標準的な形式（JSON）の場合、ルールが元々単純であるため、高速化は良好でしたが革命的ではありませんでした。
複雑で未知の言語（C++ や Bython など）の場合、差は巨大でした。CFGZIP がなければ、文法エンジンが非常に遅く、これらのタスクにおいて AI は実質的に使用不能でした。CFGZIP を使用すると、AI は複雑なコードを迅速かつ正確に生成できました。
興味深いことに、AI が一度も見たことのない「Bython」タスクにおいて、この制約付きの方法を使用することで、AI の動作するコードを記述する能力が（1 つのモデルにおいて）**2.3% から 46.9%**に向上しました。これは、タスクが難しい場合、厳格なルールが AI を支援することを証明しています。

注意点（限界）

この論文は、主な限界の 1 つとして準備時間を挙げています。
パントリーをバケットに分類すること（「オフラインの事前計算」）には時間がかかります。

一度きりの迅速なタスクとして JSON ファイルを生成する必要がある場合、パントリーを分類するのにかかる時間は、通常通りタスクを行う時間よりも長くなる可能性があります。
しかし、大規模なコード生成を行っている場合、または同じ複雑なルールを繰り返し使用している場合、初期設定時間は価値があります。なぜなら、調理（生成）が非常に高速になるからです。

まとめ

CFGZIPは、あなたが到着する前に巨大な図書館を「トピックバケット」に再編成する賢い司書のようなものです。正しい本を見つけるためにすべての本を検索する代わりに、司書は単に「トピックバケット」の代表を指し示します。これにより、正しい情報を見つけること（この場合は正しいコードを生成すること）が劇的に速くなりますが、1 冊の本も失われたり、物語が変わったりすることはありません。

技術的サマリー：トークン空間圧縮による制約付きデコーディングの高速化（CFGZIP）

問題提起

大規模言語モデル（LLM）は、JSON、XML、またはドメイン固有のプログラミング言語など、特定の構造に準拠したテキストの生成を頻繁に要求されます。LLM は訓練データに含まれる一般的な形式では良好に機能しますが、新規または複雑な形式では困難に直面します。構文の正しさを保証するために、制約付きデコーディングエンジンが採用されます。これらのエンジンは、文脈自由文法（CFG）を用いて、各生成ステップで無効なトークンをマスクします。

しかし、現在の最先端（SoTA）の文法エンジン（例：XGrammar2）は、重大なパフォーマンスのボトルネックに直面しています。最適化されているにもかかわらず、これらは各デコーディングステップで、トークン語彙全体に対してトークンの妥当性を検証する必要があります。複雑な CFG（例：C++ やカスタム言語）の場合、これにより過大なオーバーヘッドが生じ、制約なしの生成と比較して推論レイテンシが2 倍から 10 倍に増加します。このレイテンシにより、複雑な文法を伴う大規模アプリケーションにおける制約付きデコーディングは実行不可能となります。

手法：CFGZIP

著者は、トークン探索空間を圧縮し、正しさを犠牲にすることなく文法エンジンのステップごとの実行時間を削減するように設計されたオフライン手法であるCFGZIPを導入します。

中核概念：同値クラス

CFGZIP の基本的な洞察は、語彙内の多くのトークンが、特定の CFG に関して交換可能であるという点です。2 つのトークン $t$ と $u$ が「構文的に合同」である場合、それらは言語 $L(G)$ の任意の妥当な文字列内で、妥当性に影響を与えることなく入れ替えることができます。したがって、文法エンジンは、個々のトークンすべてではなく、同値クラスごとの代表トークンの妥当性のみを検証すれば十分です。

パイプライン

オフライン事前計算:
- 近似: 任意の CFG に対する正確な構文の合同性は決定不能であるため、CFGZIP は変位同値（ $\sim_{L(G)}$ ）と呼ばれる扱いやすい近似を計算します。
- メカニズム: CFG をグライバッハ標準形（GNF）に変換してプッシュダウンオートマトン（PDA）を利用します。各トークンについて、そのトークンが PDA 上で誘発する入力/出力スタック遷移の集合として定義される「変位」 $\Delta_G(t)$ を計算します。同一の変位集合を持つトークンは、同じ同値クラスにグループ化されます。
- 最適化: この計算を実行可能にするため、著者は事前計算されたスタック隣接関係を使用してスタックのバックトラック操作を制限し、大規模な文法におけるメモリ爆発を防ぎます。
- キャッシング: システムはトークン ID をクラス ID にマッピングし、各クラスに対してバイト単位の最短トークンを「代表」として選択します。これらのマッピングはディスクにキャッシュされます。
推論時操作:
- 語彙削減: 文法エンジンは、完全なトークン語彙ではなく、同値クラスの代表の語彙で初期化されます。
- トークンマッピング: LLM がトークンをサンプリングすると、CFGZIP はそれをそのクラスの代表にマッピングし、この代表を文法エンジンに渡してパーサの状態を更新します。
- マスク生成: 文法エンジンは、より小さな代表集合に対して妥当性マスクを生成します。このマスクはその後「収集（gather）」され、元の LLM のロジットに適用されます。この操作は GPU 上で並列化可能であり、最小限のオーバーヘッドしか発生しません。

主要な特性

ロスレス: 圧縮は証明可能なロスレスであり、CFGZIP 搭載エンジンの出力は、元のエンジンの出力とバイト単位で同一です。
エンジン非依存: 理論的には任意の文法エンジンと互換性がありますが、本論文は XGrammar2 に焦点を当てています。
オフライン: 重たい計算は、トークナイザ/CFG のペアごとに一度だけ実行され、推論中は実質的にオーバーヘッドが発生しません。

実験結果

著者は、CFGZIP を XGrammar2 と組み合わせて、Llama-3.2-3B、Qwen3-4B、gpt-oss-20B において、JSON スキーマ、XML、C++、およびBython（カスタムの波括弧ベースの Python 変種）の 4 つのタスクで評価しました。

レイテンシ削減: CFGZIP は、文法エンジンのオーバーヘッドを1〜2 桁削減しました。
- **C++**の場合、総推論時間はほぼ半分になりました。
- Bython（複雑でリソースの少ない言語）の場合、総制約付き生成時間は約 7.5 倍削減されました。
正しさ: CFGZIP は100% の構文正しさを維持しました（ベースラインエンジンとバイト単位で同一）。
- 機能的正しさ: 制約付きデコーディングは、機能的正しさを大幅に改善しました。特に Bython タスクでは、制約なしモデルが苦労していたため（例：GPT-20B は機能的正しさが 10.8% から 46.9% に改善）。
圧縮率: この手法は、Llama-3B/C++ の40:1から GPT-20B/JSON の800:1までの圧縮率を達成し、エンジンが処理しなければならない語彙サイズを劇的に削減しました。

意義と主張

本論文は、CFGZIP が複雑な CFG に対する大規模な制約付きデコーディングを実行可能にすると主張しています。

ギャップの埋め合わせ: 最先端のエンジンは JSON のような単純な文法では効率的ですが、C++ のような複雑な文法では処理不可能なレイテンシを導入します。CFGZIP はこのオーバーヘッドをほぼ無視できるレベルまで縮小し、これらの困難なケースにおける制約付きデコーディングのパフォーマンス上の利点を解放します。
費用対効果: 結果は、より小さく安価なモデルにとって、高い機能的正しさを達成するために大規模モデルを使用する代わりに、制約付きデコーディングが viable な選択肢となり得ることを示唆しています。
実用性: 重労働をオフラインの事前計算フェーズに分離することで、CFGZIP は速度を犠牲にすることなく、複雑なドメイン固有言語への厳密な準拠を必要とするリアルタイムアプリケーションを可能にします。

限界

著者は、CFGZIP がすべてのシナリオに対する万能な解決策ではないと指摘しています。

動的コンテキスト: 事前計算時間（数秒から数分）のため、llguidance のようなエンジンがすでに高度に最適化されている、動的な単回使用の CFG（例：アドホックな JSON スキーマや関数呼び出し）にはあまり適していません。
エンジン互換性: 理論的にはエンジン非依存ですが、現在の実装は Python ベースであり、XGrammar2 と統合されています。Python バインディングが欠如している llama.cpp のような C++ 専用エンジンや、使用される特定の CFG（例：transformers-cfg における左再帰文法）をサポートしていないエンジンとは互換性がありません。
範囲: この手法は、コード生成などで使用されるような、静的で大規模かつ複雑な CFG に最も適しています。