LLMにJSONオブジェクトの生成を依頼すると、最終的に末尾カンマ、文字列内のエスケープされていない改行、あるいはquoted keyがあるべき場所にbare wordが出現する。これはモデルのバグではない。autoregressive samplingの仕組みの帰結である：各ステップで、モデルはvocabulary内のすべてのトークンを候補として見ており、部分出力を構文的にinvalidにするトークンも含まれている。

これは、token vocabulary自体を制約することで修正できる。モデルに3万2000のトークンから選ばせるのではなく、部分parseをvalidな状態に保つサブセットだけを与える。この技術はgrammar-constrained decodingと呼ばれ、LLMを確率的テキストジェネレータから構文認識型コードシンセサイザーに変換する。

プロンプトエンジニアリングが構文妥当性を解決できない理由

ほとんどの開発者は、明らかなアプローチから始める：システムプロンプトに「Output valid JSON only」を追加し、ユーザーメッセージでschemaを繰り返し、期待する。これは助けになるが、保証ではない。

モデルは生成中に自分の出力をparseしない。プロンプトとこれまでに生成されたすべてのものを条件として、vocabulary上の確率分布に基づいて次のトークンを予測する。`、のようなトークンは、閉じ括弧の後に高い確率を持つことがある。なぜなら、トレーニングデータではその位置にカンマが頻繁に現れるからだ。この特定のJSONオブジェクトのこの正確な点で、そのカンマが構文的に合法かどうかは、モデルの意思決定プロセスの一部ではない。

RLHFによるfine-tunedモデルであっても、確率質量を一般的に正しいパターンへシフトするだけだ。invalidなpathを消去しない。保証が必要で、高い確率では不十分な場合は、sampling mechanism自体を変更する必要がある。

文法制約付きデコーディングの仕組み

核心的なアイデアは単純だ：LLMの生成と並行してparser stateを維持し、各トークン位置で、パーサをerror stateに遷移させるすべてのトークンをマスクする。

ステップtで、モデルはvocabulary全体に対するlogitsベクトルを出力する。通常はtemperature scalingを適用してsamplingする。constrained decodingでは、まずgrammar engineに問いかける：これまで生成されたトークンを考慮すると、次に合法なトークンはどれか？engineはvocabulary上のbitmaskを返す。illegalなトークンのlogitsを負の無限大に設定し、残りに対してsoftmaxを実行し、フィルタリングされた分布からsamplingする。

grammar engineは、事後に完全な出力をparseする必要はない。incrementalにparseする。各トークンが受理されるたびに、内部のstate machineを更新する。パーサがaccepting stateに達すると、生成を停止できる。non-accepting stateにある場合、生成は継続する。

つまり、モデルはすべての構文的にvalidな継続の中から自由に選ぶことができる。grammarの内部で創造性を保つ。grammarの外には出られないだけだ。

実装はどのように見えるか

以下は、モダンなパーシングライブラリlarkを使ってgrammar maskを構築する簡略化されたPythonスケッチだ。本番環境では、outlinesやguidance、llama.cppの組み込みGBNFサポートのような高速なengineを使うだろうが、原理は同じだ。

from lark import Lark, Token
from transformers import AutoTokenizer, AutoModelForCausalLM
import torch

# Define a tiny grammar for a simple config DSL.
grammar = r"""
    start: pair+
    pair: KEY "=" VALUE
    KEY: /[a-z_]+/
    VALUE: /"[^"]*"/
"""

parser = Lark(grammar, parser="lalr")
tokenizer = AutoTokenizer.from_pretrained("meta-llama/Llama-2-7b-hf")
model = AutoModelForCausalLM.from_pretrained("meta-llama/Llama-2-7b-hf")

def legal_next_tokens(partial_text: str) -> set[int]:
    """Return token IDs that do not cause a parse error."""
    legal = set()
    for token_id in range(tokenizer.vocab_size):
        candidate = tokenizer.decode([token_id], skip_special_tokens=True)
        try:
            # Try parsing partial_text + candidate as a prefix.
            parser.parse(partial_text + candidate)
            legal.add(token_id)
        except Exception:
            # Some exceptions are expected mid-parse.
            # A production engine tracks parser state, not exceptions.
            pass
    return legal

# Generate one token at a time with grammar masking.
prompt = "Generate a config: "
input_ids = tokenizer.encode(prompt, return_tensors="pt")
generated = input_ids.clone()

for _ in range(50):
    outputs = model(generated)
    logits = outputs.logits[:, -1, :]

    partial = tokenizer.decode(generated[0], skip_special_tokens=True)
    legal_ids = legal_next_tokens(partial)

    mask = torch.full_like(logits, float("-inf"))
    for tid in legal_ids:
        mask[0, tid] = logits[0, tid]

    next_token = torch.argmax(mask, dim=-1).unsqueeze(0)
    generated = torch.cat([generated, next_token], dim=-1)

    # Stop if the parser is in an accepting state.
    if parser.parse(partial):
        break

print(tokenizer.decode(generated[0], skip_special_tokens=True))

これはnaiveな実装だ。実際のシステムは、各ステップでvocabulary全体を反復処理しない。事前にgrammarからfinite-state automatonを構築し、各automaton stateからどのvocabularyトークンがvalidかを事前計算する。生成時には、maskは単一のテーブル参照となる。

bounded contextにおけるconstrained decodingの位置づけ

Domain-Driven Designにおけるbounded contextsは、ubiquitous languageによって定義される。その言語は、小さなDSLとして形式化されることが多い：query syntax、rule grammar、config format、あるいはexpression languageだ。LLMにそのコンテキスト内でアーティファクトを生成または編集するよう依頼する際、正しくその言語を話してほしい。

grammar constraintsは境界を強制する。LLMは、DSLに存在しないfieldを発明できず、mismatched bracketsを出力できず、許可されたenum setの外の値を生成できない。構文はcompile-time guaranteeとなり、runtime prayerではなくなる。

これは特に、LLMの出力が直接パーサやインタプリタに供給される場合に価値がある。DSLがstrictなrecursive descent parserによってparseされる場合、単一のunexpected tokenでパイプライン全体が停止する。constrained decodingはそのfailure modeを除去する。

知っておくべきトレードオフ

constrained decodingは無料ではない。overheadは、grammar engineの実装方法に依存する。

スループット。 各forward passでmaskを構築すると、レイテンシが増加する。outlinesやGBNF対応のllama.cppのような高速engineは、token-to-state mappingを事前計算し、ステップごとのコストを約5〜10%のoverheadに削減する。各候補トークンでre-parseするnaiveな実装は、生成を桁違いに遅くする可能性がある。

grammarの表現力。 すべての構文が、token maskにきれいにマッピングできるgrammarで表現しやすいわけではない。「このidentifierはscope内で以前に宣言されている必要がある」といった文脈依存ルールは、標準的なcontext-free grammarsでは捕捉されない。grammarで構文を制約できる。追加の機構なしに意味を制約することはできない。

モデルの互換性。 一部のinference API、特にホスト型cloud APIは、logitsを公開せず、custom maskingを許可しない。OpenAIのAPIはJSON modeを提供するが、これはJSON専用のhardcoded grammar constraintであり、独自のgrammarを持ち込むことはできない。custom DSLの場合、通常はローカルinference、またはlogitsを公開するフレームワークが必要だ。

部分トークンの問題。 token boundaryは、常にgrammar boundaryと一致するわけではない。grammarがquoted stringを期待していても、次のトークンが"helで、その後にlo"が続く場合がある。grammar engineは、完全なトークンだけでなく、partial token matchesについても推論する必要がある。productionライブラリは、トークンをcharacter prefixesにマッピングし、prefix validityをgrammarに対してチェックすることでこれを処理する。

今日実際に実装する方法

grammar engineをゼロから書く必要はない。いくつかのライブラリが難しい部分を処理する。

outlines はPythonユーザーにとって最も使いやすい。Pydanticモデルまたは正規表現を定義すると、制約を効率的なfinite-state automatonにコンパイルし、Hugging Face transformersやvLLMと統合する。

from outlines import models, generate

model = models.transformers("microsoft/Phi-3-mini-4k-instruct")
generator = generate.regex(model, r'\{[a-z_]+\}')
result = generator("Extract the key: ")

guidance はMicrosoftが提供する、より豊富なテンプレートシステムだ。grammar constraintsをプロンプトテンプレートと組み合わせ、maskingを内部で処理する。

llama.cpp はGBNF（GGML BNF）、BNFに似たgrammar形式をサポートする。inference時に.gbnfファイルを渡すと、engineがC++レベルで強制する。これはローカルinferenceにおける最速の選択肢だ。

jsonformer と instructor は、JSON専用の軽量な代替案だ。grammar-like constraintsを使用するが、JSON schemaに限定される。bounded contextのDSLが偶然JSON-shapedの場合、最も簡単な出発点となる。

constrained decodingが修正しないもの

grammar-constrained LLMでも、意味的に誤った出力を生成しうる。存在しないテーブルを参照するvalidなSQL queryや、無効なポート番号を設定するvalidなconfigを出力できる。構文は必要なguardrailだが、十分なguardrailではない。

LLMの下には、依然としてvalidation layerが必要だ。出力をparseし、domain modelに対してtype-checkし、意味が誤っている場合はrejectまたはretryする。constrained decodingはfailure modeを「構文エラー」から「論理エラー」に削減する。これは大きな改善だが、free passではない。

また、grammar constraintsはモデルをより賢くはしない。grammarがpermissiveすぎると、モデルは無意味だが構文的にvalidな領域に迷い込みうる。grammarがrestrictiveすぎると、モデルに正しい答えを表現するvalidなpathがなく、low-probabilityなゴミや繰り返しloopが生じる。grammarの設計は、エンジニアリング作業の一部だ。

モデルではなく出力フォーマットから始めよ

プロンプトを調整したり、より大きなモデルに切り替える前に、問題が本当にreasoningなのか構文なのかを自問する。LLMが欲しいものを理解しているが、時々フォーマットを誤る場合、grammar constraintsが正しい修正だ。fine-tuningより安く、プロンプトエンジニアリングより信頼でき、samplingだけでは得られない保証を与える。

bounded contextのDSLのgrammarを定義し、constrained decoderに接続し、モデルに線の内側で生成させる。出力は依然として時々驚かせるだろうが、構文エラーになることは決してない。

FAQ

文法制約付きデコーディングとは何ですか？

文法制約付きデコーディングは、形式文法を用いて各生成ステップでLLMの語彙をフィルタリングする技術である。部分出力を構文的にvalidに保つトークンのみが考慮され、最終出力が文法に適合することを保証する。

constrained decodingは出力品質を低下させますか？

構文に束縛されたタスクではそうではない。モデルは、すべての文法的にvalidな継続の中から自由に選ぶ。オープンな創作執筆では、制約が品質を損なう。コード、config、DSL生成では、正確性と信頼性の両方を向上させる。

OpenAIやClaudeのAPIでこれを使えますか？

OpenAIはJSON modeを提供するが、これはJSON専用のビルトインgrammar constraintであり、独自のgrammarを持ち込むことはできない。Anthropicは現在grammar constraintsを公開していない。custom DSLの場合、通常はvLLM、llama.cpp、または同様のengineによるローカルinferenceが必要だ。

どのgrammar形式がサポートされていますか？

一般的な形式には、EBNF、BNF、PEG、GBNFが含まれる。outlinesのようなライブラリは正規表現とPydanticモデルを受け付ける。llama.cppはGBNFを使用する。inference engineがサポートする形式を選ぶこと。