制約付きデコーディングと構造化生成

制約付きデコーディングとは「あり得ない候補を禁止する」こと

デコーディング戦略で見たとおり、言語モデルは各ステップで語彙上の確率分布を出し、そこから1トークンを選びます。通常のデコーディングはこの分布をそのまま使うため、出力が JSON として壊れる・列挙にない値を返す・括弧が閉じない、といった形式違反が一定確率で起きます。temperature や top-p をいくら詰めても、低確率で不正トークンが混じる可能性はゼロにはなりません。

制約付きデコーディングは、この問題を後処理やリトライではなく、生成の各ステップで根本的に断ちます。アイデアは単純で、「いまの文脈で文法上あり得ないトークンの確率を、選ばれる前にゼロにする」。これにより、出力は定義した文法・正規表現・JSON スキーマに構造的に必ず適合します。違反を検出して直すのではなく、違反を生成不可能にするのが本質です。

ロジットマスキング：-inf を足して候補を消す

制約の実装は ロジットマスキングです。語彙サイズを V とすると、モデルは各ステップで長さ V のロジットベクトル z を出します。ここに、許されないトークンの位置だけ -inf（実装上は非常に大きな負数）を加算したマスク m を足してから softmax にかけます。

z'_i = z_i + m_i        m_i = 0     （トークン i が許される）
                        m_i = -inf  （トークン i が禁止）

p(token_i) = exp(z'_i) / Σ_j exp(z'_j)

exp(-inf) = 0 なので、禁止トークンの確率は厳密に0になり、再正規化後の分布は許可トークンだけに質量が乗ります。重要なのは、これがサンプリング戦略と直交する点です。マスク後の分布に対して貪欲法でも top-p でもビームサーチでも適用でき、どれを使っても制約は守られます。制約は「候補集合を絞る」層、デコーディング戦略は「絞られた中から選ぶ」層、と分離して考えられます。

各ステップで必要なのは「いま許されるトークンの集合」です。これを文脈ごとに正しく・高速に求めることが、制約付きデコーディングの中心課題になります。

有限状態機械で正規表現を制約する

許可集合を機械的に求める基盤がオートマトンです。制約が正規表現で書けるなら、それは**有限状態機械（FSM, finite state machine）**に変換できます。FSM は状態の集合と、各状態から入力記号による遷移を持ち、現在の状態で「次に受理できる記号」が一意に決まります。

たとえば [0-9]+\.[0-9]+（小数）という制約は、おおよそ次のような状態を持つ FSM になります。

状態 s0: 数字を1つ以上 → s1（数字で自己ループ）
状態 s1: '.' を読む → s2、あるいは数字で s1 に留まる
状態 s2: 数字を1つ以上 → s3（数字で自己ループ）
状態 s3: 受理状態（数字で s3 に留まる）

生成中は現在の FSM 状態を保持し、各ステップで「その状態から遷移可能な記号」だけを許可、それ以外を -inf でマスクします。トークンを1つ生成したら、その文字に従って状態を遷移させます。FSM は事前に決定化（DFA 化）できるため、状態ごとに「許可トークンのマスク」を事前計算してテーブルに持てるのが大きな利点です。実行時はテーブル参照だけで済み、生成のオーバーヘッドをほぼ無視できる水準まで下げられます。これは正規表現や、列挙型・固定フォーマットの制約に向きます。

プッシュダウンオートマトンで再帰的な文法を扱う

FSM には限界があります。入れ子の対応——括弧の開閉、JSON のオブジェクト・配列の任意深度のネスト——は正規言語では表現できません。「開いた括弧と同じ数だけ閉じる」には数を覚える必要があり、有限個の状態では足りないからです。

ここで必要になるのがプッシュダウンオートマトン（PDA, pushdown automaton）、すなわちスタックを持つオートマトンです。PDA は文脈自由文法（CFG）を認識でき、JSON・プログラミング言語・式の文法といった再帰構造を扱えます。

'{' を読む → スタックに「閉じ括弧 } を期待」を push
'[' を読む → スタックに「閉じ括弧 ] を期待」を push
値を読み終える → スタック先頭が } なら ',' か '}' を許可
'}' を読む → スタック先頭の「} を期待」を pop

許可集合は「現在の状態＋スタック先頭」から決まります。スタックがネストの深さと種類を覚えているので、深さ100の入れ子でも正しく閉じ括弧を要求できます。JSON スキーマの制約は実質的にこの PDA + 各フィールドの型制約（型ごとに小さな FSM）として実装されます。

最大の難所：サブワード境界

ここまでは「文字（または文法記号）単位」でオートマトンを進める前提でした。ところが LLM が選ぶのは文字ではなくトークンです。BPE などのサブワードトークナイザでは、1トークンが複数文字にまたがり、しかも文法記号の境界と一致しません。これが制約付きデコーディング最大の難所です。

具体例として、true というリテラルだけを許す制約を考えます。文字レベルの FSM なら t → r → u → e と進みますが、トークナイザは true を1トークンで持つかもしれず、あるいは tr + ue、t + rue と分割するかもしれません。さらに truse のような不正な文字列の途中まで（tr）を含むトークンが語彙にあると、それを許すかどうかは「そのトークンを足した後、まだ文法を満たし続けられるか」で判断せねばなりません。

問題の構造:
  オートマトンは「文字」で遷移を定義
  モデルが選ぶのは「トークン」（複数文字のかたまり）
  → あるトークンが許されるか = そのトークンの全文字を
     現在の状態から順に食わせて、途中で詰まらないか

つまり各状態で、語彙の全トークンについて「このトークンの文字列を現在状態から受理できるか」を判定し、できるものだけを許可マスクに含める必要があります。素朴にやると毎ステップ V（数万〜十数万）回の判定が走り、生成が大幅に遅くなります。

境界問題を高速に解く：トライと事前計算

この V 回判定を実行時に毎回やるのは現実的でないため、実用エンジンは事前計算で潰します。代表的な工夫は次の通りです。

• トークン語彙をトライ（trie）に格納する。 文字列の共通接頭辞を共有する木構造にすると、オートマトンの1状態から到達可能なトークン集合を、木をたどりながらまとめて判定でき、独立に V 回回すより大幅に速くなります。
• 「状態 → 許可トークンのビットマスク」を前処理で索引化する。 FSM のように状態数が有限で決定的なら、各状態の許可マスクを生成前に1度だけ計算してキャッシュします。生成時はテーブル参照のみです。
• PDA ではスタック先頭ごとにマスクをキャッシュする。 完全な事前計算はできなくても、出現したスタック構成のマスクをメモ化すれば、同型の構成での再計算を避けられます。

これらにより、制約付きデコーディングのステップあたり追加コストを、無制約デコーディングに対してほぼ無視できる水準（百分の数〜数パーセント）まで下げられます。逆に言えば、ここを手を抜くと制約は正しくても遅すぎて使えない、というのが実装上の勘所です。

何が保証され、何が保証されないか

制約付きデコーディングが保証するのは構文（形式）の適合であって、内容の正しさではありません。ここを取り違えると過信につながります。

もう一つの注意は、制約が分布を歪めることです。マスクは確率を再正規化するため、モデルが「本来は別の続きを書きたかった」場面でも無理やり文法内に押し込めます。たとえばモデルが自然には自由文で説明したい局面で JSON を強制すると、内容が痩せたり不自然になったりすることがあります。制約は強力ですが、スキーマ設計とプロンプトでモデルの素の意図と制約を近づけておくほど、品質劣化は小さくなります。

まとめ：制約は候補を絞る独立した層

制約付きデコーディングは、モデルの確率分布に対して「文法上あり得ない候補をマスクで消す」独立した制御層です。デコーディング戦略と直交し、どのサンプリングとも組み合わせられます。

実務では、まず出力したい形を JSON スキーマか正規表現・EBNF で定義し、構造化生成エンジンにオートマトンへコンパイルさせます。形式の保証はエンジンに任せ、自分はスキーマ設計とプロンプトでモデルの意図と制約のズレを縮めることに注力するのが、品質と信頼性を両立させる近道です。出力の選び方そのものを詰めたいときはデコーディング戦略を、なぜ分布から1語を選ぶ余地が生まれるのかはニューラルネットワークの仕組みも合わせて参照してください。