この論文は、大規模言語モデル（LLM）がコードスニペットやフォーマットされたデータなど、正確な構文規則に準拠した構造化出力を生成することを可能にするという問題について説明します。文法制約復号化（GCD）は、指定された文脈自由文法（CFG）に属さない出力につながるトークンをマスクし、LLM出力がこれらの規則と一致することを保証します。従来のGCDアルゴリズムは、サウンドネスを保証するために、LLMサブワードトークナイザーが特定のCFGのトークンとどのように整列するかを計算し、この情報に基づいてトークンマスクを計算する必要があり、これは非常に非効率的です。本論文は、従来のアプローチよりも17.71倍速いオフライン前処理を提供しながら、オンラインマスク計算の最先端の効率を維持する新しいGCDアルゴリズムと実装を提示します。
