AI・テクノロジー

Trie Automata：大規模有限集合に対する制約デコーディングの新境地 — LLMのツール選択・分類タスクを100倍高速化する技術

docker agent

• 15 min read
Share

はじめに：LLMの「構造化出力」とenumの壁

大規模言語モデル（LLM）をプロダクションで運用する際、モデルが出力するテキストを特定の形式に制限したい場面は少なくない。JSONスキーマに従ったデータ抽出、ツール選択時の関数名の指定、分類タスクでのカテゴリ名の出力——これらの要求に応える技術が「制約付きデコーディング（constrained decoding）」である。各トークン生成ステップにおいて、文法やスキーマに合致するトークンのみに候補を絞り込むマスキング処理により、構造化された出力を保証する。

現在、Outlines、XGrammar、SGLangなどの主要な制約デコーディングエンジンは、任意の文脈自由文法やJSONスキーマを処理できる汎用有限状態機械（FSM/DFA）を採用している。これらのエンジンは複雑なネスト構造や再帰的スキーマを扱うには優れているが、単純な有限集合、すなわちenum（列挙型）からの選択に対して同じ汎用パイプラインを適用するのは、本質的なミスマッチを抱えている。

このミスマッチが顕在化するのが、enumの要素数Kが増加した時である。「カーディナリティの壁（cardinality wall）」と呼ばれるこの現象は、FSMのコンパイル時間とマスキングコストがKの増加に伴い超線形に悪化することを指す。実務上の影響は深刻で、OpenAIのStructured Outputsはenumを1,000件に制限し、Google Geminiは約120件、Anthropicに至っては180秒のコンパイルタイムアウトが設定されている。エージェント的ワークフローが普及し、数百〜数千のツールレジストリからの選択が日常的になりつつある現在、この制約は深刻なボトルネックとなっている。

Amazonの研究者らが提案する「Trie Automaton（トライオートマトン）」は、この壁を突破する全く新しいアプローチである。文字レベルのTrie（トライ木）とAho-Corasickマルチパターンマッチングを組み合わせることで、1ステップあたりのマスキングを従来比約7倍に高速化し、vLLM上のバッチスループットでは29倍もの改善を達成する。最大100,000件のenumまで実用的にスケール可能であり、OpenAIの1,000件上限をはるかに超える領域をカバーする。本稿では、このTrie Automatonの技術的詳細、性能評価、そして実タスクでの有効性を解説する。

カーディナリティの壁：なぜ従来手法ではenumが大きくなると使えなくなるのか

制約付きデコーディングの基本原理は単純である。各トークン生成ステップにおいて、モデルが出力する全トークンの中から、現在の制約（スキーマやenum）に合致するものだけを選別する「マスキング」を行う。このマスキングを高速に計算するために、現在の主流エンジン（XGrammar、Outlines、SGLang）は有限状態機械（FSM/DFA）を用いている。FSMは任意の文法を表現できる汎用性を持つが、有限集合（enum）に特化した場合、本質的な非効率が生じる。

FSMベースのアプローチには三つの根本的な問題がある。第一にコンパイルコストの問題である。enumの各文字列をDFAに変換する際、状態数は O(K × Lmax) に比例して増加する。ここでKはenumの要素数、Lmaxは最長の文字列長である。さらに、DFAの遷移テーブルはアルファベットサイズ（バイトレベルで256）を乗じたサイズになるため、K=2,000の場合、1,500万回以上の遷移処理が必要となり、コンパイル時間は単一のツール選択で25〜50秒に達する。

第二に1ステップあたりのマスキングコストの問題がある。LLMの語彙サイズVは32,000〜262,000トークンと巨大である。FSMベースの手法では、毎回この全トークンをDFAで検証し、有効かどうかを判定する必要がある。計算量は O(V × ℓ)（ℓはDFAの深さ）となり、Kが増えるほど各トークンの検証に要するパスも長くなる。XGrammarは語彙パーティショニングと呼ばれる最適化を導入しているが、それでもK=1,000で1ステップあたり5.8μsを要する。

第三にキャッシュミスの問題がある。DFAの遷移テーブルはK=2,000で約47MBに達し、一般的なCPUのL2キャッシュ（通常1MB前後）を大きく超過する。結果として、マスキングのたびにメインメモリへのアクセスが発生し、実効速度は理論値よりもさらに低下する。

これらの問題が複合的に作用することで、「カーディナリティの壁」が生まれる。Kが300を超えるとXGrammarのコンパイル時間はTrie Automatonを上回り始め、K=10,000では239ms（Trieは40ms）、K=100,000では2.7秒に達する。一方、Trie AutomatonはK=100,000でも30〜67msとほぼフラットなコンパイル時間を維持する。この差は、汎用FSMが「任意の文法を扱える」という強みを、単なる文字列の集合という単純な制約に対して過剰な一般性で支払っている代償に他ならない。

次のセクションでは、この壁を突破するTrie Automatonのアルゴリズム的仕組みを詳しく見ていく。

Trie Automatonとは：文字レベルTrie＋Aho-Corasickによる革新的アプローチ

基本アイデア：制約の構造に特化したエンフォーサー

有限集合の文字列が持つ3つの構造的性質——共有プレフィックス（共通接頭辞）、有限深さ（最大文字列長が既知）、既知のカーディナリティ（要素数が事前に確定）——に着目するのがTrie Automatonの出発点である。文字レベルTrie（トライ木）は、これらの性質を最大限に活用するデータ構造だ。2,000件のenumであっても、「get_」「create_」「update_」といった共通の接頭辞は1ノードに統合されるため、木全体のノード数は全文字列の単純合計より大幅に少なくなる。デコードの各ステップでは、現在のTrieノードから子ノードを辿るだけで有効な次の文字をO(1)に近いコストで判定でき、従来の汎用FSMのように全状態遷移テーブルを参照する必要がない。

最大の技術的挑戦：BPEトークンとTrieのアライメント問題

しかし、文字レベルTrieをLLMの制約デコーディングに適用するには、BPE（Byte Pair Encoding）トークンとのアライメント問題を解決しなければならない。LLMの語彙は「medical」のように複数文字からなるトークンで構成されており、7文字それぞれに分割されてTrie上を遷移するわけではない。この問題に対し、GENRE（De Cao et al., 2021）はトークンレベルでTrieを構築することでアライメントを回避したが、トークン数が要素数Kに比例して増加するため、K≈1,000以上で性能が急激に悪化する。本研究はこの問題をAho-Corasick（AC）マルチパターンマッチングを用いて解決する。ACアルゴリズムにより、語彙全体（32K〜262Kトークン）の全トークンを同時に文字レベルTrie上でマッチングし、各TrieノードからどのBPEトークンが有効かを一括計算できる。

Aho-Corasickアルゴリズムの仕組み

ACオートマトンは3つの要素から構成される。Goto関数は文字単位の状態遷移を定義するTrie構造を、Failureリンクはマッチ失敗時にフォールバックする遷移先を、Output関数は各状態で完了するパターンの集合をそれぞれ保持する。

graph TD
    subgraph "ACオートマトンの構成要素"
        R((root)) -- "g" --> G((1))
        R -- "c" --> C((2))
        G -- "e" --> GE((3))
        GE -- "t" --> GET((4))
        C -- "a" --> CA((5))
        CA -- "t" --> CAT((6))
        GET -. "failure→root" .-> R
        CAT -. "failure→root" .-> R
    end
    style R fill:#f9f,stroke:#333,stroke-width:2px
    style GET fill:#bbf,stroke:#333,stroke-width:2px
    style CAT fill:#bbf,stroke:#333,stroke-width:2px

ACオートマトンの重要な特性は、その構築コストが語彙サイズに依存してもenumの要素数Kには依存しない点である。つまり、トークナイザごとに一度ACオートマトンを構築すれば、全てのスキーマで再利用できる。計算量で比較すると、ナイーブな実装がO(Nchars × V × ℓ)（Nchars：enum全文字列の総文字数、V：語彙サイズ、ℓ：最大トークン長）であるのに対し、ACを利用するとO((Nchars + V) × ℓ)に削減される。K=2,000の場合、約1,500万演算（汎用FSM）が約37万演算（Trie）に減少し、40倍以上の差が生じる。この劇的な効率化により、100,000件規模のenumでも実用的な速度での制約デコーディングが初めて可能となった。

実装の詳細：プリコンピューテッドマスクによるステートレスサービング

Trie Automatonの核心は、デコード時の計算を極限まで削減する「プリコンピューテッドマスク」にある。文字レベルTrieの各ノードには、そのノードに到達した時点でLLMが出力可能なBPEトークンのセットが事前に計算されて格納される。デコード時の処理は、現在のTrieノード番号 st をキーに valid[st] から有効トークンマスクをルックアップするだけの単純な操作となる。このルックアップにかかる時間はわずか0.65μsであり、XGrammarの5.8μsと比較して約9分の1に相当する。

プリコンピュートの仕組み

プリコンピュートは以下の2段階で行われる。第1段階では、与えられた有限集合（enum）の全文字列を1文字ずつTrieに挿入し、共有プレフィックスを統合した文字レベルTrieを構築する。第2段階では、Aho-Corasick（AC）オートマトンを用いて語彙全体（32K〜262Kトークン）をこのTrieに一括マッチングする。ACオートマトンは語彙サイズにのみ依存し、enumの要素数Kには依存しないため、トークナイザごとに一度構築すれば全スキーマで再利用可能である。この設計により、プリコンピュート全体の時間はK=10〜10,000の範囲で30〜40msにフラットに保たれる。

ステートレスLogitsProcessorによるvLLM統合

プリコンピュート済みマスクのもう一つの利点は、vLLMのガイド付きデコーディングパイプラインを完全にバイパスできる点にある。従来のFSMベースのアプローチでは、各デコードステップで状態遷移テーブルを参照しながら有効トークンを逐次計算するため、パイプライン全体に複雑な状態管理が必要だった。Trie Automatonでは、LogitsProcessorが valid[st] から既に確定したビットマスクを直接取得し、ロジットに適用するだけでよい。このステートレスな設計により、vLLMの内部パスが大幅に短縮され、バッチサイズ256のエンドツーエンドスループットで219 req/s（XGrammarの7.5 req/sの29倍）という差を生み出している。プリコンピュート済みマスクのメモリ使用量も、100K件のenumで約8MBとコンパクトであり、L2キャッシュに収まるサイズに抑えられている。

出力等価性の理論的保証

プリコンピュートによる高速化は近似やヒューリスティックではない。論文のProposition 1では、Trie Automatonが有限集合の最小DFAと同型であることがMyhill-Nerodeの定理に基づいて証明されている。Trieの各ノードはMyhill-Nerodeの同値類（そのノード以降に有効な文字列集合が等しい状態のグループ）に一対一対応し、FSMと完全に同一の出力を生成することが保証される。つまり、Trie Automatonは「より高速だが時折異なる結果を返す近似手法」ではなく、「同じ結果を桁違いに高速に計算する別のデータ構造」なのである。この理論的保証は、医療コードや法的事案分類など、出力の正確性が重要なユースケースで特に価値を持つ。

パフォーマンス評価：7モデルファミリー×7トークナイザでの検証

Trie Automatonの実用的な性能を検証するため、論文では7種類のモデルファミリー（7種類のトークナイザ）を用いて、コンパイル時間、1ステップあたりのマスキング時間、そしてvLLM上のエンドツーエンドバッチスループットが測定されている。実験環境はA100 GPUとAMD EPYC CPU（96コア、3.3GHz）で、比較対象としてXGrammar（v0.1.11）およびLLGuidance（v1.6.1）が用いられた。

コンパイル時間

enumの要素数Kに対するコンパイル時間の測定結果は、Trie Automatonの最大の強みの一つを示している。Qwen3-8B（語彙サイズ151K）での計測では、K=10からK=10,000の全範囲にわたって、Trieのコンパイル時間は30〜40msでほぼフラットに推移した。この一定値の支配的要因はAho-Corasickオートマトンの構築であり、enumの要素数Kには依存しない。

K（enum要素数） Trie XGrammar LLGuidance
10 30ms 3ms 1ms
300 33ms 30ms 4ms
1,000 35ms 82ms 9ms
5,000 37ms 155ms 17ms
10,000 40ms 239ms 24ms

XGrammarはK=300付近でTrieのコンパイル時間と交差し、それを超えると急激に悪化する。K=10,000では239msに達し、実用的なレイテンシ要件（通常100ms以内）を超える。一方、LLGuidanceはEarleyパーサによる遅延オートマトン構築の特性上、コンパイル自体は最速（1〜24ms）だが、後述のマスキング時間で大きな代償を払うことになる。

xychart-beta
    title "コンパイル時間の比較（K vs 時間）"
    x-axis "enum要素数 K" [10, 100, 300, 1000, 5000, 10000]
    y-axis "コンパイル時間 (ms)" 0 --> 250
    line "Trie" [30, 31, 33, 35, 37, 40]
    line "XGrammar" [3, 10, 30, 82, 155, 239]
    line "LLGuidance" [1, 2, 4, 9, 17, 24]

バッチサービングスループット

コンパイル時間の優位性に加え、Trieは1ステップあたりのマスキング時間でも圧倒的な差を見せている。Trieのマスキングは0.65μs（マイクロ秒）であるのに対し、XGrammarは5.8μs、LLGuidanceに至っては73〜141μsと、Trieの110〜215倍もの時間を要する。この差は、Trieがプリコンピュート済みマスクを用いた単純な配列ルックアップ（O(1)）で処理を完了するのに対し、FSMベースの手法では毎回語彙全体のトークンを検証する必要があることに起因する。

このアルゴリズム的優位性は、vLLM上のエンドツーエンド測定でさらに増幅される。K=1,000、バッチサイズ256の条件下で、Trieは219 req/sを達成した。特筆すべきは、この値が制約なしのデコーディング（104 req/s）を上回っている点である。これはTrieのプリコンピュートマスクがvLLMのガイド付きデコーディングパイプラインを完全にバイパスし、さらに制約による早期終了（EOSトークン到達の高速化）が寄与した結果である。対するXGrammarは7.5 req/sにとどまり、29倍のスループット差が生じている。この差はアルゴリズム的な優位性（約7倍）と、プリコンピュートマスクによる統合パス削減の効果が複合して生まれたものである。

xychart-beta
    title "バッチサイズ vs スループット（K=1,000）"
    x-axis "バッチサイズ" [1, 8, 16, 32, 64, 128, 256]
    y-axis "スループット (req/s)" 0 --> 250
    line "Trie" [42, 85, 120, 155, 185, 205, 219]
    line "XGrammar" [38, 45, 35, 22, 14, 9, 7.5]
    line "制約なし" [45, 72, 88, 98, 102, 103, 104]

バッチサイズの増加に伴い、XGrammarのスループットは低下する（バッチ内の各リクエストに対して独立したFSMシミュレーションが必要となるため）。一方、Trieはバッチサイズの増加とともにスループットが向上し続ける。この特性は、プロダクション環境での同時リクエスト数が多いユースケースほどTrieの利点が際立つことを意味する。

7モデルファミリーでの一般化

Trie Automatonの性能が特定のトークナイザに依存しないことを確認するため、語彙サイズが32Kから262Kまで異なる7種類のモデルで検証が行われている。

モデル トークナイザ 語彙サイズ マスキング時間 (μs)
Mistral 7B SentencePiece 32K 0.60
GPT-2 BPE 50K 0.61
OLMo 3 OLMo tokenizer 100K 0.63
Mistral Small SentencePiece 131K 0.64
Qwen3-8B Qwen tokenizer 151K 0.65
gpt-oss-20b BPE 200K 0.66
Gemma3 12B SentencePiece 262K 0.67

マスキング時間は語彙サイズにほとんど依存せず、0.60〜0.67μsの範囲で一定である。これはTrieのルックアップが語彙サイズではなく、現在のTrieノードに紐づく有効トークンセットのビットマスク参照のみで完了するためである。対照的に、XGrammarのマスキング時間は語彙サイズに比例して増加する（語彙32Kで3.2μs、262Kで9.8μs）。

コンパイル時間に関しても、K=5,000〜10,000の範囲でTrieは3.5〜13.7倍の高速化を全モデルで達成している。Aho-Corasickオートマトンの構築時間はトークナイザごとに一度だけ発生し（全スキーマで再利用可能）、enum要素数の増加によるオーバーヘッドが生じないため、どのような語彙サイズのモデルでも安定したパフォーマンスを発揮する。

実タスクでの有効性：分類ベンチマークでの精度評価

制約付きデコーディングの実務上の価値を測るには、単なるベンチマークスコアだけでなく「出力が有効な選択肢に収まっているか」という有効性（validity）が重要となる。本論文ではTREC（42クラス）、MASSIVE（59）、Banking77（77）、CLINC150（150）の4つのテキスト分類データセットを用いて、Trie Automatonの精度と有効性を評価している。

最も顕著な成果は、制約付きデコーディングの真価が「弱いモデルを実用的にする」点にあることを示したことだ。例えばQwen3-1.7B（17億パラメータの小型モデル）をBanking77で評価した場合、制約なしの生成では分類精度が4.8%（有効性6.6%）とほぼ機能しない。しかしTrie Automatonによる制約を適用すると、精度は24.8%に向上し、出力の100%が有効なクラス名に収まる。これはモデルが「正しいクラス名を完全に暗記する」必要から解放され、部分的な手がかりからでも正解に辿り着けるようになるためである。

さらに「考えてから答える（think-then-answer）」戦略との組み合わせで効果は増幅される。Qwen3-8Bに思考用トークンを先に生成させてから分類させる方式では、TRECデータセットの精度が36.3%から63.1%へと26.8ポイント向上した。思考ステップを設けることでモデルが選択肢間の違いを内部的に整理できるようになり、制約デコーディングの効果を最大限に引き出せる。

強力なモデルに対してもTrieは確実な価値を提供する。Gemma3 12Bのように本来の性能が高いモデルでも、制約なしでは99.5%前後の有効性に留まり、0.5%程度は無効な出力が混入する。Trieを適用すればこれを100%に引き上げられ、プロダクション環境で許容されないエッジケースを完全に排除できる。

カーディナリティが大きい状況での差はさらに顕著となる。K=500〜5,000の高カーディナリティ分類タスクでは、制約なしの有効性が84〜98%に低下するのに対し、Trieは常に100%の有効性を維持する。これは医療コード分類（ICD-10-CM：74,719コード）や大規模製品カテゴリ分類など、数千〜数万クラスの現実的な分類タスクにおいて、Trie Automatonが唯一の実用的な選択肢となることを示している。

Trieが切り開く新たなユースケース

Trie Automatonの最大の価値は、従来の制約付きデコーディングでは現実的に扱えなかった規模の有限集合を、初めて実用域に引き上げた点にある。ここでは、この技術によって可能になる具体的なユースケースを4つ紹介する。

エージェント的ワークフローにおける大規模ツール選択

エージェントAIの普及に伴い、LLMが利用可能なツール（関数・API）のレジストリは急速に拡大している。MCP（Model Context Protocol）エコシステムでは、クライアントが複数のサーバーを束ねることで、容易に500〜5,000以上のツールが列挙される状況が発生する。従来のFSMベースの制約デコーディングでは、2,000件のツールレジストリからの選択に25〜50秒ものコンパイル時間が必要であり、ユーザーを待たせることは現実的ではなかった。Trie Automatonは30〜40msのフラットなコンパイル時間でこれを処理するため、ユーザー操作に対してリアルタイムに応答する対話型エージェントのバックエンドとして初めて実用的な選択肢となる。

ゼロショット分類タスクの大規模化

LLMを分類器として用いるゼロショット分類では、出力トークンをあらかじめ定義されたクラスラベルのみに制約する必要がある。製品カテゴリ分類（Amazonの1,500以上の製品カテゴリ）、医療コード分類（ICD-10-CM：74,719コード）、法的事案種別の判定（10,000以上）など、実務上の分類タスクは数百から数万のクラスを対象とする。Trie Automatonは100,000件のenumまで実用域で動作するため、これらのタスクで初めて制約付きデコーディングを適用可能にする。特に、Qwen3-1.7Bのような軽量モデルでも、制約なしで4.8%だったBanking77の精度がTrie利用で24.8%に向上した事例は、「弱いモデルを実用的にする」という制約デコーディングの真価を示している。

ナレッジベースエンティティリンキング

エンティティリンキング（Entity Linking）は、テキスト中の言及を知識ベース上のエンティティに紐付けるタスクである。大規模ナレッジベースには数万〜数十万のエントリが存在するため、従来は検索ベースの候補絞り込み（retrieve-then-rank）が主流であり、LLMによる直接的な選択は候補数が多すぎて実用的でなかった。Trie Automatonを用いれば、全エンティティをenumとして定義した上で制約付きデコーディングを実行できる。K=100,000でも30〜67msのコンパイル時間で動作するため、検索フェーズを経ずにLLMが直接エンティティを生成するend-to-endのパイプラインが現実味を帯びる。

RAGによる動的enum生成

検索拡張生成（RAG）の文脈では、クエリごとに有効な選択肢の集合が動的に変化する。例えば、ユーザーの質問に応じて検索された上位k件の文書タイトルやIDを選択肢としたい場合、その集合はリクエストごとに異なる。このような動的enumは、従来のFSMアプローチではリクエストごとにコンパイルが必要であり、実用的なレイテンシを達成できなかった。Trie Automatonの30〜40msというコンパイル時間は、動的enumのオンザフライ構築を許容する。ACオートマトンの構築（語彙サイズに依存）は一度だけ行い、enumのTrie構築のみをリクエストごとに実行する設計により、全体のオーバーヘッドを最小限に抑えられる。これにより、検索結果の上位候補からLLMに選択させる「RAG × 制約デコーディング」のハイブリッドアプローチが初めて実用的となる。

これらのユースケースに共通するのは、「選択肢の数が多いこと」が従来はボトルネックであり、Trie Automatonがその壁を突破したという点である。特に、エージェント的ワークフローとゼロショット分類は、プロダクション導入の需要が高く、即座に恩恵を受けられる領域といえる。

制約と今後の展望

Trie Automatonは有限集合に対する制約デコーディングを劇的に高速化するが、万能な解決策ではない。最大の制約は適用範囲である。Trieはあくまで「フラットな有限集合（enum）」に特化した専用エンフォーサーであり、JSONスキーマのようなネスト構造や再帰的スキーマは処理できない。このため、実際のプロダクション環境では「enumフィールドはTrieに、構造的制約は既存のFSMバックエンドにルーティングする」というハイブリッド構成が現実的な選択肢となる。論文でも、両者を振り分けるディスパッチャのオーバーヘッドは1ms未満と報告されており、実用上の問題は生じない。

既存手法との住み分けも明確にしておくべき点である。LLGuidanceはEarleyパーサベースでコンパイルが1〜3msと最速であり、カーディナリティKが500未満かつスキーマが動的に変化するユースケースではTrieより有利な場面がある。Kが小さければFSMベースのコンパイルコストも十分許容範囲に収まるため、「K=500を閾値にTrieとLLGuidanceを切り替える」という戦略が合理的である。Trieは「FSMの完全な代替」ではなく、制約の種類と規模に応じて適切なエンフォーサーを選択する「constraint-aware dispatch」の一構成要素と捉えるべきである。

GPUマスキングの進展も将来の議論として重要である。現在の制約デコーディングはCPU上でマスキングベクトルを計算し、GPUに転送するアーキテクチャが一般的だが、将来的にマスキング処理そのものがGPU上で実行されるようになれば、CPU上の速度優位性は相対化される可能性がある。しかし、Trieのプリコンピュートマスクはビットマスク表現でコンパクトにエンコードされており、100K件のenumでも約8MBに収まる。一方、FSMの遷移テーブルは同じ規模で約2GBに達するため、GPUの限られたVRAMへの転送という観点ではTrieに分がある。

今後の拡張方向性としては、日付/時刻フォーマット、数値範囲、特定パターンの正規表現サブクラスなど、他の構造化制約に対しても同様の「制約タイプ別専用エンフォーサー」を設計するアプローチが考えられる。制約の種類ごとに最適なデータ構造を選択するこのパラダイムは、LLMサービングインフラの標準設計となる可能性を秘めている。

よくある質問

Trie Automatonは既存のLLMサービングシステムに簡単に統合できる？

はい。Trie AutomatonはvLLMのLogitsProcessorとして実装されており、既存のパイプラインに最小限の変更で組み込める。混合スキーマ（enumフィールドと構造的制約が混在するJSONスキーマ）では、enumフィールドをTrieに、構造的制約を既存のFSMバックエンドにルーティングするディスパッチャが1ms未満のオーバーヘッドで動作する。Rust実装＋Pythonバインディング（PyO3）で提供されるため、呼び出し元のコード変更は数行で完了する。

XGrammarと比べて具体的にどのくらい速いのか？

1ステップあたりの有効トークン計算で比較すると、Trie Automatonは0.65μs、XGrammarは5.8μsであり、約9倍の差がある。この差は主に、Trieがプリコンピュート済みマスクをルックアップするだけで済むのに対し、XGrammarは毎回語彙全体をFSMで検証する必要があることに起因する。さらに、vLLM上でバッチサイズ256・K=1,000のエンドツーエンド測定では、Trieが219 req/sを達成したのに対しXGrammarは7.5 req/sと、29倍のスループット差が生じている。この追加の差は、プリコンピュートマスクによりvLLMのガイド付きデコーディングパイプラインを完全バイパスできる点に由来する。

なぜOpenAIはenumを1,000件に制限しているのか？

OpenAIのStructured Outputsは、XGrammarと類似した汎用FSM（有限状態機械）ベースの制約デコーディングを使用していると推測される。FSMのコンパイルコストはenumの要素数Kの増加に伴い超線形に悪化するため、実用的な上限として1,000件が設定されている。実際、XGrammarではK=10,000で239msのコンパイル時間を要するのに対し、Trie Automatonでは30〜40msでフラットなままである。Trie Automatonを採用すれば、同じ出力品質を保ちながら100,000件以上のenumまで実用的に扱える可能性がある。

トークンレベルのTrie（GENRE）ではダメなのか？

GENREスタイルのトークンレベルTrieは、K=100の小規模enumでは4.5msと高速にコンパイルできる。しかし、Kの増加とともにコンパイル時間が線形に悪化するため、K≈1,000で文字レベルTrie＋Aho-Corasickにクロスオーバーされ、K=10,000では約7倍の速度差が生じる。加えて、トークンレベルTrieは各トークナイザに固有の実装が必要となるのに対し、文字レベルTrieはトークナイザに依存せず、同一のアルゴリズムでMistral（32K語彙）からGemma3（262K語彙）までシームレスに動作する。

この技術はすでにプロダクションで利用可能か？

論文執筆時点（2026年8月）ではコード公開準備中であり、vLLMおよびSGLangとの統合が想定されている。実装はRust（aho-corasick crate v1.1使用）＋Pythonバインディング（PyO3）で構成されており、Rayonによる並列化にも対応している。特に、Aho-Corasickオートマトンはトークナイザごとに一度構築すれば全スキーマで再利用可能なため、プロダクション導入時の初期化オーバーヘッドは最小限である。現在のXGrammarユーザーであれば、enumフィールドのみをTrieに置き換える形で段階的に導入できる。

まとめ

本稿で紹介したTrie Automatonは、LLMの制約付きデコーディング領域において「制約の種類に応じた専用エンフォーサー」という設計思想の重要性を明確に示している。従来の汎用FSM（有限状態機械）アプローチは任意の文法を扱える柔軟性を持つ反面、有限集合（enum）という単純な制約に対しては過剰な汎用性が仇となり、カーディナリティの増加に伴うコンパイルコストの爆発的増大——「カーディナリティの壁」——を引き起こしていた。

Trie Automatonは、有限集合が持つ「共有プレフィックス」「有限深さ」「既知のカーディナリティ」という3つの構造的性質を最大限に活用することで、この壁を突破した。文字レベルTrieとAho-Corasickマルチパターンマッチングの組み合わせにより、BPEトークンと文字レベルのアライメント問題を解決し、プリコンピュートマスクによるステートレスなサービングパスを実現。結果として、XGrammar比で1ステップあたりのマスキングが約9倍（0.65μs vs 5.8μs）、vLLM上のバッチスループットが29倍（219 req/s vs 7.5 req/s）という飛躍的な性能向上を達成した。しかも、出力等価性の証明により近似ではなく完全に同一の出力を保証し、K=100,000件以上のenumでも実用的に動作する。

エージェントAIの急速な普及に伴い、MCP（Model Context Protocol）エコシステムの拡大やツールレジストリの大規模化は避けられない。OpenAIの1,000件、Geminiの約120件といった現在のenum上限は、近い将来に深刻なボトルネックとなるだろう。Trie Automatonのような「制約の構造を理解し、適切なアルゴリズムを選択する」constraint-aware dispatchの考え方は、LLMインフラの今後の標準パラダイムとなる可能性を秘めている。汎用FSMと専用エンフォーサーを状況に応じて切り替えるこのアプローチは、日付/時刻フォーマットや数値範囲など他の構造化制約への拡張も視野に入っており、制約付きデコーディングの次なる進化の方向性を示すものと言える。

参考資料

一次資料

関連研究

プロダクトドキュメント

データセット

関連記事