💬 NLP

Constrained Adaptive Rejection Sampling

本論文は、制約付き適応的棄却サンプリング（CARS）を導入しており、これは、トライ木を用いて無効な継続を適応的に枝刈りすることで、厳格な制約下における言語モデル生成のサンプル効率を向上させ、既存の強欲な手法や標準的な棄却サンプリングと比較して、元の分布を維持しつつ受理率と多様性を改善する手法である。

原著者： Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

公開日 2026-06-04

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Paweł Parys, Sairam Vaidya, Taylor Berg-Kirkpatrick, Loris D'Antoni

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、非常に才能はあるが少し混沌としたシェフ（言語モデル）に、厳格なレシピ本（制約）に基づいた特定の複雑な料理（有効な出力）を教えていると考えてください。シェフは即興を得意としていますが、しばしばルールを無視して、料理を台無しにしたり、構造的に不可能なものにしたりする食材を加えてしまいます。

この問題を解決するために、CARS（Constrained Adaptive Rejection Sampling：制約付き適応的棄却サンプリング）という新しい手法が提案されています。なぜCARSが特別なのかを理解するために、これまでの2つの古い解決策と、なぜそれらが失敗するのかを見てみましょう。

古いやり方：2つの欠陥のある戦略

1. 「投げ捨てる」方法（棄却サンプリング / Rejection Sampling）
シェフがフルコースの料理を作り終えた後、あなたがレシピを確認し、もし間違っていたら、その鍋ごとゴミ箱に捨てて、最初からやり直させる方法です。

問題点: レシピが非常に厳格な場合（複雑なプログラミング言語など）、シェフが1つの正解に辿り着くまでに、999回の失敗作を作ってしまうかもしれません。あなたは、食べ物を捨て続けることに膨大な時間とエネルギーを浪費します。
利点: 実際に提供される1つの料理は完璧であり、シェフが意図した通りの味になります。

2. 「監視の手」方法（強欲デコーディング / Greedy Decoding）
あなたがシェフの肩越しに立ち会い、シェフがルールを破る食材に手を伸ばすたびに、その手を叩いて退け、別のものを選ぶよう強制する方法です。

問題点: シェフの自然な調理が止まってしまいます。シェフはロボットのようになり、常に「安全な」食材ばかりを選ぶようになります。出来上がった料理は食べられるものではありますが、もはやシェフ独自のスタイル（個性）は失われ、歪んでしまいます。
利点: 無駄がほとんどなく、非常に素早く有効な料理を作ることができます。

新しい解決策：CARS（「賢いメモ作成者」）

著者らは、両者の良いとこ取りをしたCARSを提案しています。これは、シェフの自然なスタイル（忠実度）を維持しながら、不可能な料理に時間を浪費することを防ぎます（効率性）。

CARSがどのように機能するかを、「禁止された経路のライブラリ」という比喩を使って説明します。

調理開始: シェフは、「投げ捨てる」方法と同じように、自然に調理を開始します。
ミス: 例えば、シェフが 0++ という（数学的に無効な）文字列で始まる文章を作ろうとしたとします。システムがこれを検知します。
賢いメモ: その特定の文章をただ捨てるのではなく、システムは**Trie（トライ）**と呼ばれる特殊な木構造のノートを開きます。そこにこう書き込みます。「0++ で始まる料理はすべて不可能である」。
波及効果: 決定的なのは、システムが「0+ の次に + が続く場合、その後の展開はすべて無意味になる」ということも理解することです。システムは、それらのツリーの枝全体を「禁止領域」としてマークします。
次回の調理: 次にシェフが調理を始める際、このノートを参照します。もしシェフが「禁止された」枝へと続く食材を選ぼうとした場合、システムは、シェфが料理全体を完成させて無駄にする前に、優しく進路を逸らします。
結果: シェフは二度と失敗作を作ることがなくなります。行き止まりに時間を浪費することがなくなるため、より速く調理でき、かつ調理した内容は強制された模倣ではなく、依然としてシェフ自身の自然なスタイルを保っています。

ななぜこれが大きなニュースなのか？

論文では、多くの異なる「有効なもの」を生成する必要がある3つの現実世界のシナリオでCARSをテストしました。

プログラム・ファジング（バグの発見）: 数百万通りの異なる入力をソフトウェアに与えて、プログラムを壊そうとする試みです。有効なコードでありながら、システムをクラッシュさせるほど奇妙な入力が必要です。CARSは、従来のメソッドよりも多くのバグ（より多くのコード行をカバー）を発見できました。なぜなら、無効なパスに陥ることなく、有効で多様な入力をより速く生成できたからです。
分子探索（創薬）: 化学者は有効な化学構造を生成する必要があります。CARSは、従来の手法よりもはるかに速く、有効で多様な分子を生成し、膨大な計算資源を節約しました。
Text-to-SQL（質問をデータベースクエリに変換）: データベースに質問をする際、その回答は完璧なSQLクエリである必要があります。CARSは、最も少ない試行回数で、最も正確なクエリを生成しました。

まとめ

CARSは、一種の**「学習フィルター」**だと考えてください。

古い手法は、失敗作を投げ捨てることで時間を浪費するか（棄却サンプリング）、あるいはAIをあまりに硬直的に強制することで品質を損なう（強欲デコーディング）かのどちらかでした。
CARSは、あらゆるミスから学びます。それは「行き止まり」の地図を作成することで、AIが二度とその道を通らないようにします。これにより、完全に有効な結果が得られ、かつAI本来の自然な声（スタイル）を維持したまま、無効なパスにエネルギーを浪費することなくより速く結果を得ることができるのです。

論文は、これがこのような厳格なタスクにおいて、**正確さ（Exact）と効率性（Efficient）**の両立を実現した初めての手法であると主張しています。

技術要約: 制約付き適応型棄却サンプリング (Constrained Adaptive Rejection Sampling: CARS)

1. 問題提起

言語モデル（LM）は、生成される出力が厳格な意味的または構文的な制約（例：構文的に正しいコードの生成、データスキーマへの準拠、化学構造の生成など）を満たす必要があるアプリケーションにおいて、ますます活用されています。制約付き生成における核心的な課題は、以下の2つの相反する要求のバランスを取ることです。

忠実度 (Fidelity): サンプルが近似値ではなく、制約を与えられたLMの真の条件付き分布（ $P_L$ ）に従う必要がある。
効率性 (Efficiency): 有効なサンプルを生成するために必要なLMのフォワードパスの回数を最小限に抑える必要がある。

既存のアプローチは3つのカテゴリに分類されますが、いずれもこれら両方の基準を同時に満たすことはできません。

正確だが非効率的 (Exact but Inefficient): 標準的な棄却サンプリング (Rejection Sampling: RS) は、真の制約付き分布から不偏なサンプルを生成しますが、構造化されたドメイン（例：受理率が1%未満）では大多数の候補を破棄するため、計算コストが膨大になります。
効率的だが偏りがある (Efficient but Biased): 貪欲法による制約付きデコーディング (Greedy Constrained Decoding: GCD) は、生成中に無効なトークンをマスキングすることで妥当性を強制します。効率的ではありますが、LMの条件付き分布を本質的に歪めてしまうことが証明されており、ダウンストリームの性能を低下させたり、終了に失敗したりする可能性があります。
漸近的に正確だが不安定 (Asymptotically Exact but Unstable): MCMCや逐次モンテカルロ法 (Sequential Monte Carlo: SMC) などの手法は、極限において正しい分布に収束しますが、原理的な停止ルールを持ちません。初期のサンプルは任意に偏る可能性があり、効率性はハイパーパラメータのチューニングや安定化に必要な反復回数に大きく依存します。

本論文は、プログラムのファジングや分子探索のように多様な有効サンプルを必要とするドメインにおいて、正確（真の分布を保持する）かつ償却効率的（忠実度を犠牲にすることなく、時間の経過とともに効率を向上させる）なアルゴリズムの欠如を指摘しています。

2. 手法: 制約付き適応型棄却サンプリング (CARS)

CARSは、棄却サンプリングの忠実度と適応型枝刈りの効率性を組み合わせた、正確なサンプリングアルゴリズムです。これは適応型棄却サンプリング (Adaptive Rejection Sampling: ARS) に基づいて構築されていますが、制約の構造を利用して、単に拒絶されたサンプルだけでなく、無効な継続（continuation）の全集合を枝刈りするように拡張されています。

コアメカニズム

アルゴリズムは、サンプリングプロセス中に発見された無効な接頭辞 ( $W$ ) の集合を保持します。これらの接頭辞を保存するために**Trie（トライ）**データ構造を使用し、それらを回避するようにサンプリング分布 ( $R_W$ ) を動的に再形成します。

初期化: アルゴリズムは、空の無効な接頭辞集合 ( $W = \emptyset$ ) から開始します。
サンプリング: 各イテレーションにおいて、アルゴリズムは再重み付けされた分布 $R_W$ $R_{W}$ からシーケンスをサンプリングします。この分布は、元のLM分布 $P$ $P$ から、 $W$ $W$ 内のいかなる接頭辞も拡張しないシーケンスに基づいて正規化することで導出されます。
- 形式的には、接頭辞 $u$ に対して、それを有効なシーケンスへと拡張する確率を $p_u$ として追跡します。もし $u$ が既知の無効な接頭辞を拡張している場合、 $p_u = 0$ となります。
- トークン $a$ の接頭辞 $u$ におけるサンプリング確率は、 $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$ として調整されます。
適応型枝刈り (主要な革新点): シーケンスが生成されると、CARSは単に拒絶された文字列を記録するだけではありません（標準的なARSの場合とは異なります）。代わりに、生成されたシーケンスのすべての接頭辞のうち、制約に違反するものを特定し、さらにそのすべての無効な継続を特定します。
- 具体的には、シーケンス $w$ が生成された場合、CARSは、有効な言語 $L$ に含まれない $w$ の最短の接頭辞 $u$ を $W$ に追加します。
- 決定的なのは、 $u$ のすべての拡張 $ua $（ここで$ a $はトークン）についても、$ ua \notin prefix(L) $であるならば$ W$ に追加することです。
- このプロセスにより、将来の描画から無効なサブツリー全体の確率質量を効果的に「差し引く」ことができます。
更新: Trieは新しい無効な接頭辞を反映するように更新され、確率値 ( $p_u$ ) が上方へ伝播されます。これにより、将来のサンプルがこれらの無効なパスを再訪することがなくなり、受理率が単調に増加します。

理論的特性

正確性 (Exactness): CARSは、ターゲットとなる制約付き分布 $P_L$ から正確にサンプルを生成します。再重み付けにより、確率質量が有効なシーケンス間で正しく再分配されます。
単調性 (Monotonicity): $W$ が増加するにつれて、受理率は単調に改善されます。
収穫逓減 (Diminishing Returns): 1回のサンプルあたりに除去される期待確率質量は非増加です。これは実用的なヒューリスティックを示唆しています。つまり、Trieが無効な確率質量を削除しなくなった段階では、効率を大きく損なうことなく、後続のサンプリングのために分布を「凍結」することができます。

3. 主な貢献

アルゴリズム設計: 無効な接頭辞の継続を枝刈りするために制約の構造を活用することで、正確性と実用的な効率性を両立させた、新しい制約付きLM生成アルゴリズムであるCARSの導入。
理論的保証: CARSが真の制約付き分布からサンプリングすること、およびその適応的な更新が有効なサンプルを得る確率を単調に増加させることの証明。
実証的検証: 複数のドメインにおいて、サンプリング効率（有効なサンプルあたりのLMフォワードパス回数）とサンプル多様性の両面で、既存の手法を凌駕することを実証。

4. 実験結果

著者らは、4つのモデル（Llama-3.1-8B/70B, Qwen2.5-7B/14B）を用い、3つの異なるドメインでCARSを評価しました。

A. 文法ベースのファジング (Grammar-Based Fuzzing)

タスク: ファザーのコードカバレッジを最大化するために、多様で有効なプログラムシード（JSON, SQL, XML）を生成すること。
結果: CARSは、RS、ARS、RSFTよりも大幅に少ない生成回数で、目標とする100個の有効なサンプルを達成しました。例えば、文法プロンプトなしのXML生成において、CARSは約440回の生成を必要としたのに対し、RS/ARSは2,000回以上を要しました（RS/ARSは目標に到達できませんでした）。
影響: CARSによって生成されたシードは、GCD（~~7,115）やMCMC（~~7,965）と比較して高い行カバレッジ（~7,985行）を実現しました。これは、分布の忠実度がダウンストリームの性能向上に直結することを示しています。

B. 分子合成 (Molecular Synthesis)

タスク: 特定の化学クラス（アクリレート、鎖状延長剤、イソシアネート）に対して有効なSMILES文字列を生成すること。
結果: 100個の有効な分子を生成するために、CARSはRSよりも4.3倍、ARSよりも1.3倍少ないサンプルを必要としました。また、正確な手法の中で最高の妥当性と多様性のスコアを達成しました。
忠実度: CARSのKLダイバージェンスは、MCMCより1.5倍、AWRSより1.8倍低く、真の分布への優れた追従性を示しました。

C. Text-to-SQL 生成

タスク: 自然言語の質問からSQLクエリを生成すること（Spiderデータセット）。
結果: CARSは、すべての手法の中で最高の実行精度（0.578）を達成しました。RSより1.85倍、ARSより1.28倍少ないサンプルを必要としました。
比較: GCDのような近似的手法はより高速（1.00 サンプル/クエリ）でしたが、精度（0.525）が低下しました。CARSは、GCDのわずか1.1倍のサンプル数でありながら、精度においてGCDを上回るという、最良のトレードオフを提供しました。

5. 意義と主張

本論文は、CARSがLMの正確な制約付き分布からサンプリングするための新しい最先端（State-of-the-art）を確立すると主張しています。その意義は、正確性と効率性の間の根本的なトレードオフを解決したことにあります。

RSとは異なり、CARSは実用面で償却効率的であり、多数の多様なサンプルを必要とするタスクに適しています。
GCDやその他の近似的手法とは異なり、CARSは真のLM分布を保持するため、分布の歪みによるダウンストリームの性能（ファジングのカバレッジ、化学的多様性、SQL実行精度など）の低下を招きません。

著者らは、CARSは制約が接頭辞としてチェック可能であり、枝刈りに非常に有益な情報を提供する（例：文脈自由文法）場合に最も効果的であると述べています。無効な入力の空間が、共有された接頭辞を持たない独立した低確率のサブスペースの集まりであるシナリオでは、ARSに対する利得は限定的となり、近似的な手法が実用的な代替案となる可能性があります。しかし、ほとんどの構造化生成タスクにおいて、CARSは原理的、正確、かつ効率的なソリューションを提供します。