GPT-5では出力形式を文脈自由文法で制限できるんだけど、その技術的な説明(使ってるライブラリの解説記事)。

https://guidance-ai.github.io/llguidance/llg-go-brrr

正規表現ベースのレクサとEarleyパーサを組み合わせて、LLMのトークン辞書内の各トークンに対してその場所で出現できるかというのを計算して、出現できないトークンはサンプリング時に出現確率を0にする。

この処理はGPUが計算をしている間にCPUでやるので高速にする必要があるし、初期化作業も高速にする必要がある。

正規表現エンジンはderivativeベースのもので、部分式やderivativeの計算はハッシュテーブルにキャッシュする。

LLMのトークン辞書はトライ木で表す。木を辿りながらレクサ+パーサが各バイトを受け取れるかどうかチェックして、受け取れれば子を辿る。全ての子を辿り終わった後はレクサ+パーサの状態を戻す必要がある(この辺derivativeベースのレクサ+Earleyパーサ(動的計画法ベースで表を作っていく)という構成の相性がよい?)。

パーサの方から次に許されるレクサのトークンの情報をレクサに渡して絞り込む。

荒い正規表現でLLMのトークンを分類しておき、レクサの正規表現がその荒い正規表現を含むときは処理をまとめてスキップする。

その他、トライ木は配列として表現するとか分岐を予測可能にするとかの細かい最適化。