💻 computer science

Trie Automata for Constrained Decoding over Large Finite Sets

本論文は、有限集合による制約付きデコーディングのためにAho-Corasickマルチパターンマッチングを活用してトークンマスクを事前計算する特殊なメカニズムであるトライオートマトンを紹介し、XGrammarのような既存のシステムと比較して、100%の出力妥当性を保証しながら最大29倍高いスループットと大幅に高速なコンパイルを実現する。

原著者： Xingzi Xu, Karim Bouyarmane

公開日 2026-08-14

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

CC BY 4.0

原著者： Xingzi Xu, Karim Bouyarmane

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

コンピューターが、非常に才能はあるけれど少し混沌としたシェフのような世界を想像してみてください。彼らは物語を書き、数学の問題を解き、ソフトウェアのコードを書くこともできますが、「作り話」をしてしまうという悪い癖があります。もしあなたが彼らに世界の首都をリストアップするように頼んだら、彼らは自信満々に「ナルニア」という都市を捏造したり、「Paris」の綴りを間違えたりするかもしれません。これを防ぐために、科学者たちは「制約付きデコーディング（constrained decoding）」と呼ばれる技術を使用します。これは、シェフに厳格なレシピ本を与えるようなものです。シェフが宇宙中のあらゆる材料から食材を選ぶのではなく、レシピ本が「使えるのは小麦粉、砂糖、または卵だけです」と指示します。コンピューターは、新しい食材をうっかり発明してしまわないように、書きたい単語の一つひとつをこのリストと照らし合わせてチェックします。

これは、レシピに3つの材料しかないような短いリストの場合はうまく機能します。しかし、もしリストが膨大だったらどうでしょう？例えば、レシピに「世界にある10,000種類の異なるスパイスから選んでもよい」とか、「巨大なワークショップにある50,000種類の道具から選んでもよい」と書いてあったらどうなるでしょうか。3つのアイテムのリストをチェックするのは簡単です。しかし、50,000個ものアイテムがあるリストを毎回チェックするのは、どんどん大きくなっていく巨大な干し草の山の中から特定の針を探し出すようなものです。コンピューターはリストのチェックに手一杯になり、料理を作るのを止めてしまったり、時間がかかりすぎて料理が冷めてしまったりします。これが、研究者たちが解決しようとしている問題です。つまり、禁止リストが膨大な場合でも、いかにコンピューターを高速かつ正確に動作させ続けるかということです。

禁止された言葉の巨大な図書館

この論文では、研究者たちが「トライ・オートマトン（Trie Automaton）」と呼ばれる巧妙で新しいツールを紹介しています。なぜこれがゲームチェンジャーになるのかを理解するために、従来の方法がどのように機能していたかを見てみましょう。コンピューターが巨大な図書館の入り口に立つ警備員だと想像してください。コンピューターが単語を発言しようとするたびに、警備員は長い廊下を走り、巨大で埃をかぶった台帳（10,000個の有効な単語のリスト）をチェックし、その単語が許可されているかどうかを確認しなければなりません。リストが膨大になると、警備員は行き来するだけで時間を使い果たしてしまい、中に入ろうと待っている人々の列（コンピューターの思考）が停滞してしまいます。これが、論文で「カーディナリティの壁（cardinality wall）」と呼ばれている現象です。リストがあまりに大きくなりすぎて、システムがクラッシュしたり、動作が極端に遅くなったりする地点のことです。

研究者たちは、従来の方法がすべてのリストをランダムな単語の集まりとして扱っていたことに気づきました。しかし、現実の世界では、リストはランダムではありません。例えば、ツールの名前のリストを考えてみてください：「aws.create_user」、「aws.delete_user」、「aws.list_user」。これらはすべて「aws.」から始まります。そして、それぞれが「create」、「delete」、「list」を持っています。これらは、木の枝のように、共通の始まりの部分を多く共有しています。従来の警備員はこのことに気づかず、毎回ゼロからすべての単語をチェックしていました。

新しい「トライ・オートマトン」は、図書館の特別な地図を作る超スマートな司書のようなものです。長い廊下の代わりに、司書は木のような形の経路を構築します。

地図： 彼らは「aws.」への経路を描きます。一度「aws.」の経路に乗れば、再び「aws.」をチェックする必要はありません。ただ次の分岐点を見るだけです。「create」、「delete」、または「list」です。
事前チェック： ここに魔法のトリックがあります。コンピューターが話し始める前に、司書は木の各分岐点でどの単語が許可されているかを正確に計算しておきます。彼らはこれらの答えを小さな付箋に書き込み、それを木の枝に直接貼り付けておきます。
スピード： さて、コンピューターが話したいとき、司書は台帳まで走る必要はありません。現在の枝にある付箋を見るだけです。「ああ、あなたは『aws』の枝にいますね？付箋には、次は『create』、『delete』、または『list』しか言えないと書いてあります」これには一瞬しかかかりません。

結果：カタツムリからロケットへ

研究者たちは、この新しいシステムを、リストの項目数が10から10,000個の範囲で、既存の最善の方法（XGrammarなど）と比較テストしました。結果は劇的でした。

コンパイル速度： 1,000個のアイテムの地図を作成する場合、旧システムは約75ミリ秒（少し待ち時間がある）かかりました。新しいトライ・オートマトンは約33ミリ秒で完了しました。しかし、リストが10,000個に増えると、旧システムは240ミリ秒近くかかったのに対し、新しいものは40ミリ秒とほぼ横ばいでした。それは、旧システムが泥の中を走っている一方で、新しいシステムはどれほど速くなっても負荷が変わらないトレッドミルの上で走っているかのようでした。
「カーディナリティの壁」： 旧システムは、リストが数百を超えると、失敗したり大幅に減速したりし始めました。新しいシステムは、10,000個のアイテムのリストを苦もなく処理し、研究者たちは理論的には100,000個まで対応可能であることを示しました。
バッチ・サービング（真の勝利）： 最大の驚きは、多くのリクエストを同時にテストしたとき（例：256の注文が入っている忙しいレストラン）に起こりました。旧システムは毎秒約7.5件のリクエストしか処理できませんでした。しかし、新しいトライ・オートマトンは毎秒219件のリクエストを処理しました。これは29倍の改善です。

なぜこれほど速かったのでしょうか？それは単に地図があったからではなく、その地図の「使い方」に理由がありました。答えが事前に付箋に書かれていたため、コンピューターは話している間に複雑な思考やチェックを行う必要がありませんでした。付箋を掴んで次に進むだけです。これにより、コンピューターは旧システムが毎回行っていた、多くの低速で複雑なステップをスキップすることができました。

これが意味すること

この論文は、特定の種類のリスト（レジストリからツールを選んだり、医療コードを選んだり、製品カテゴリーを選択したりする場合など）において、従来の「すべてをチェックする」方法が遅すぎることを証明しています。単語の構造（共有された始まりの部分）を利用し、答えを事前計算することで、新しい手法は制制付きデコーディングを再び高速かつ信頼できるものにします。

研究者たちは、この新しい手法がコンピューターを賢くしたり、内容を変えたりするものではないことを非常に慎重に注記しています。それは単に、コンピューターが「言うべきことだけ」を言うようにし、それを信じられないほど速く行うためのものです。彼らはこれを実際のコンピュータチップ上で測定し、新しい手法がルールに従う上で100%正確であり、旧手法と同様に、生成される単語ごとに7倍速いことを発見しました。この速度を、同時に発生する何百ものリクエストに掛け合わせると、その差は計り知れないものになります。

要約すると、この論文は、巨大な干し草の山の中を混沌とゆっくり探索する方法を、あらかじめライトアップされた道を素早く歩く方法へと変える方法を見つけ出したのです。これは「カーディナリティの壁」の問題を解決し、AIが数千のツールやサービスから即座に選択を行う必要があるAIエージェントの未来にとって極めて重要です。

技術要約：大規模有限集合に対する制約付きデコーディングのためのトライ・オートマトン

1. 問題提起：カーディナリティの壁

大規模言語モデル（LLM）は、定義済みのスキーマに従った構造化出力（例：ツール名、医療コード、製品タクソノミーなどの既知の有限集合からの文字列選択）をますます必要としています。XGrammarやOutlinesといった現在の制約付きデコーディングシステムは、これらの制約を汎用的なオートマトン（有限状態マシン、プッシュダウン・オートマトン、またはアーレイ・パーサー）にコンパイルすることで処理しています。

これらは複雑な文法には効果的ですが、単純な有限集合の制約に対しては、この汎用的なアプローチが「カーディナリティの壁」を生み出します。有効な文字列の数（ $K$ ）が数千に増えると、コンパイル時間とステップごとのデコーディング・レイテンシが著しく増大します。既存のプロバイダーは厳格な制限を課しており（例：OpenAIは1,000個の列挙型、Google Geminiは約120個）、これは標準的なコンパイル・パイプラインが $K$ に対してスケーリングが悪いためです。核心となる問題は、根本的なミスマッチにあります。つまり、単純な制約（文字列の有限な和集合）に対して、複雑で汎用的なエンジンが適用されていることです。これらの制約は、活用可能な構造（共有接頭辞、限定された深さ、既知のカーディナリティ）を持っています。

2. 手法：トライ・オートマトン

著者らは、汎用的なFSMレイヤーを置き換える、有限集合の制約に特化したバックエンドであるトライ・オートマトンを導入しています。この手法は、制約セットの構造を利用することで、劣線形なコンパイルと定数時間のステップごとのマスキングを実現します。

コアメカニズム

文字レベルのトライ構築： トークンレベルのトライ（トークンの境界をまたいで接頭辞を共有できないもの）や一般的なDFAではなく、有効な文字列の集合から直接、文字レベルのトライを構築します。これにより共有接頭辞が統合され、ノード数は $O(K \cdot L_{max})$ から $O(N_{chars})$ （ $N_{chars}$ は総文字数）へと削減されます。
Aho-CorasickによるBPE-Trieのアライメント： 文字レベルのトライをモデルのByte-Pair Encoding（BPE）語彙と整列させることは中心的な課題です。単一のBPEトークンは複数のトライのエッジにまたがる可能性があります。著者らは、この問題をマルチパターン文字列照合の問題に帰着させることで解決しました。語彙トークンからAho-Corasick（AC）オートマトンを構築し、トライのすべてのノード $n$ に対して有効なBPEトークンの集合（valid[n]）を事前計算します。
事前計算されたマスク： コンパイル中に、システムはすべてのノード $n$ について valid[n] を計算します。デコード時には、マスキングは直接的な $O(1)$ ルックアップへと簡略化されます： $A(s_t) = valid[s_t]$ 。これにより、全語彙を走査したり、ステップごとにトークンの遷移をシミュレートしたりする必要がなくなります。

計算量の利点

コンパイル： コストは語彙のACオートマトン構築によって支配されますが、これは $O((N_{chars} + V) \cdot \ell)$ です（ $V$ は語彙サイズ、 $\ell$ は最大トークン長）。決定的なのは、ACオートマトンが構築された後は $K$ にほとんど依存せず、結果として $K=10,000$ であってもほぼ平坦なコンパイル時間（30–67ms）をもたらすことです。
ステップごとのデコーディング： コストは $O(V \cdot \ell)$ （全トークンの走査）から $O(|valid[s_t]|)$ へと低下します。有効な集合はトライの深さとともに指数関数的に減少するため（通常、3〜4文字後に10〜100トークン）、実効コストは定数であり、極めて低くなります（0.65µs）。
ステートレス・サービング： マスクが事前計算されているため、トライはステートレスな LogitsProcessor として動作でき、FSMベースのアプローチで必要とされるガイド付きデコーディング・パイプラインの状態管理やスケジューリングのオーバーヘッドを回避できます。

3. 主な貢献

トライ・オートマトン： 文字レベルのトライ、Aho-Corasickマルチパターン照合、および事前計算されたトークンマスクを組み合わせた、特殊な制約付きデコーディング・バックエンド。これは $O(V \cdot \ell)$ のコストを持つ一般的なFSMアプローチに対し、 $O(|valid[s_t]|)$ のステップごとのマスキングを実現します。
BPE-Trieアライメント問題の解決： 著者らは、文字レベルのトライのパスをBPEトークンと整列させるという、これまで未解決であった課題に対処しました。これをマルチパターン照合に帰着させることで、多様なトークナイザー・ファミリーにおいて $K=10,000$ まで100ms未満のコンパイルを実現しました。
カーディナリティの壁の経験的特性評価： 著者らは、制約構造にエンフォースメント（強制）メカニズムを適合させることが、スケーリングのボトルネックを克服することを実証しました。事前計算されたマスクが、FSMアプローチでは利用できないステートレスなサービングパスを可能にすることを明らかにしました。

4. 実験結果

実験は、Qwen3-8B、Mistral、Gemma3を含むモデルと、7つのトークナイザー・ファミリー（32K–262K 語彙）を用いて、NVIDIA A100 GPU上で実施されました。

コンパイル速度： トライ・オートマトンは、 $K \ge 300$ においてXGrammarよりも 2–6.5倍高速 なコンパイルを実現しました。XGrammarのコンパイルは $K$ に対して線形にスケールしますが（ $K=100,000$ で2.7秒に達する）、トライは~30–67msで平坦なままです。
ステップごとのレイテンシ： トライは有効トークンマスクの計算に 0.65µs を要し、これはXGrammarの 5.8µs（7倍の高速化）およびLLGuidanceの 73–141µs（110–215倍遅い）と比較して極めて高速です。
エンドツーエンドのスループット： バッチ・サービング（vLLM）において、この優位性は累積します。バッチサイズ256において、トライは 219 req/s を達成し、これはXGrammarの 7.5 req/s に対し 29倍の向上 です。この利得は、7倍のアルゴリズム的高速化と、ガイド付きデコーディング・パイプラインのオーバーヘッドの排除の両方に由来します。
妥当性と精度： トライは 100%の出力妥当性 を保証します。分類ベンチマーク（TREC, MASSIVE, Banking77, CLINC150）において、制約付きデコーディングは非制約時と同等以上の精度を示しつつ、ハルシネーションを排除しました。特に性能の低いモデルにおいて、トライはBanking77での精度を4.8%から24.8%へと向上させる重要なエンブラー（実現要素）として機能しました。
スケーラビリティ： 本手法は、 $K=10,000$ 以上においてもサブ100msのコンパイルと平坦なステップごとのコストを維持し、実用的な列挙型の限界を従来の約1,000から約100,000へと拡大しました。

5. 意義と主張

本論文は、トライ・オートマトンが、単純で構造化された制約に対して汎用的なオートマトンを適用するという、制約付きデコーディングにおける根本的な非効率性を解決することを主張しています。有限集合の特定の構造（共有接前辞）を利用することで、著者らは以下を実証しました：

アルゴリズムの効率性： トライは、有限集合上の各状態におけるマスクを事前計算するための効率的なアルゴリズムであり、FSMベースの事前計算と比較してコンパイル時間で 196倍 上回る性能を発揮します。
システムへの影響： マスクの事前計算能力は、ガイド付きデコーディング・パイプラインを回避するステートレスなサービングパスを可能にします。これは、事前計算されたマスクのみが可能とする恩恵です。これにより、制約付きデコーディングは、バッチ・サービングにおけるボトルネックから無視できる程度のオーバーヘッドへと変貌します。
汎用性： 制約の構造（例：固定フォーマットに対する文字位置マスク）にエンフォースメント・メカニズムを一致させるという原則は、有限集合に限らず、活用可能な規則性を持つあらゆる制約に対して大幅な高速化をもたらします。

著者らは、トライ・オートマトンをFSMベースのデコーディングの近似ではなく、有限集合に対する正確かつ同型な代替手段として位置づけており、高カーディナリティのシナリオにおいて、100%の妥当性と桁違いのパフォーマンス向上を提供します。