推論系統
Trie Automataがtoken maskを事前計算、vLLMの有限選択肢デコーディングでXGrammarの29倍のスループット
新手法は、数千から1万個の有効な文字列に対してtrieの状態とtoken maskを事前構築し、汎用文法コンパイルにおけるカーディナリティのボトルネックを回避する。著者らの測定では、バッチサイズ256で毎秒219リクエストを処理した。ただし実装はまだ公開されておらず、この数値には既存のguided decoding経路を迂回する統合上の効果も含まれる。
ツール呼び出し、商品検索、分類APIでは、モデルの出力を所定の名前の集合だけに制限することが多い。既存のサービスは通常、選択肢を文法へコンパイルし、デコードの各ステップで有効なtokenを計算する。8月12日に投稿され、[COLM 2026の採択論文](https://colm.eventhosts.cc/Conferences/2026/AcceptedPapers)に掲載された研究によると、有効値が数千個に増えると、汎用コンパイラは「カーディナリティの壁」に直面する。各選択肢が短い文字列にすぎなくても、コンパイル処理とステップごとの状態更新は急速に肥大化する。
[Trie Automata](https://arxiv.org/abs/2608.12574)はまず、すべての有効な文字列を共有prefixに基づいてtrieへまとめ、続いてAho–Corasickの複数パターンマッチングを用い、各ノードで受理可能なtoken maskを事前計算する。推論時には現在のノードに対応するmaskを取り出すだけでよく、コストは選択肢数が増えても増加しない。著者らは、語彙サイズが32Kから262Kまでの7種類のtokenizerで評価し、候補値が1万個あっても100ミリ秒以内にコンパイルでき、出力が有効な集合に完全に属することを保証できたとしている。
比較対象は、vLLM、SGLang、TensorRT-LLMに統合済みの汎用[XGrammar](https://github.com/mlc-ai/xgrammar)である。論文によると、ステップごとの有効token計算はtrieが0.65マイクロ秒、XGrammarが5.8マイクロ秒だった。候補数が300以上の場合、コンパイルは2～6.5倍高速だった。vLLMでバッチサイズ256を用いたエンドツーエンドテストでは、スループットが毎秒7.5リクエストから219リクエストへ向上した。
この29倍という値を、automaton自体が29倍高速になったと直接解釈することはできない。改善には、maskの事前計算に加え、汎用guided decodingパイプラインを迂回できるステートレスな統合の効果も含まれる。また、この手法が適用できるのは、既知かつ有限の文字列集合に限られ、XGrammarが提供するJSON Schema、正規表現、context-free grammarのサポートを代替するものではない。エンジニアリングチームは今後、著者らがvLLMへの変更を公開するかどうか、メモリ使用量、マルチテナント環境でのキャッシュ戦略に注目し、実際の選択肢の長さとバッチ分布を用いて結果を再現する必要がある。