技術要約：推論エージェントを用いた大規模な反例誘導型学習

問題定義

本論文は、大規模言語モデル（LLM）およびエージェントが、フィードバックから効果的に学習し適応できるようにするための課題に取り組んでいる。コーディングエージェント、ツール利用者、パーソナライズされたアシスタントにとってフィードバックは極めて重要であるが、典型的なフィードバックメカニズムは異質性、ドメイン特異性、および制御可能性の欠如があるため、モデルのフィードバック活用能力を測定し向上させることが困難である。

この能力のための制御可能なテストベッドを作成するため、著者らは正規表現（regex）誘導に焦点を当てている。これは古典的な記号学習問題であり、ラベル付けされた文字列の集合（正例と負例）から、ターゲットとなる言語 $L^\star$ を推論することを目的とする。このタスクは本質的に困難である。なぜなら、少数の例に適合する候補となる表現が多数存在し得るため、表面的なパターンへの過学習を招く恐れがあるからである。著者らはこれをオラクル誘導型の記号生成問題として定式化しており、そこではLLM（学習者）が、検証器（教師）からの反例によるフィードバックに基づき、反復的に仮説を洗練させていく。

手法

提案されたフレームワークは、エージェント的ワークフローによって強化された、教師・学習者ループをLLMと統合するものである。システムは以下のコンポーネントを通じて動作する。

1. 教師・学習者反復フレームワーク

• 学習者 (Learner): 現在のラベル付けされた例の集合に基づき、候補となる正規表現を提案するLLM。
• 教師 (Teacher): 候補をターゲット言語に対して検証する。正規言語の等価性は決定可能であるため、教師は候補 $\hat{r}$ とターゲットとの対称差 $L(\hat{r}) \triangle L^\star$ を構築する。
• フィードバック: 候補が誤っている場合、教師は反例（ターゲットに含まれるべきだが含まれていない文字列、またはその逆）を返す。これらは次ラウンドの学習セットに追加される。

2. 反例合成とクラスタリング

（特にクリーネ閉包/ループから生じる）潜在的に無限の反例を管理するために、著者らはクラスタリングされた反例 (Clustered Counterexamples) を導入している。

• 個別の文字列を返す代わりに、教師は最小化された差分オートマトンを分析する。
• 同じ目的地状態に導く出力記号を「スーパー文字」（例：$\{A, \dots, Z, a, \dots, z\}$ を $[A-Za-z]$ として表す）へとグループ化する。
• クラスタリングされた反例は、これらのスーパー文字を用いたオートマトン内のパスであり、共通の失敗モードを共有する具体的な文字列の集合を表す。これにより、エラー領域に関する、より体系的で冗長性の少ないビューが提供される。

3. エージェント的ワークフロー

本フレームワークは、標準的な教師・学習者ループを、2つのループからなるエージェント的ワークフローへと昇華させている。

• 外側ループ (Reflection/内省): LLMは、過去の試行について内省するように促される。モデルは、以前の仮説、その推論プロセス、および新しい反例を受け取る。モデルには、何が失敗したのか、そしてどのように仮説を修正すべきかを説明するよう指示される。
• 内側ループ (Repair/修復): 一貫性を確保するために、システムは修復ループを採用する。システムは、以下の条件を満たす候補を生成するためにLLMを繰り返しクエリする。
  1. 構文チェック: 正規表現が構文的に有効であること。
  2. 充足チェック: 正規表現が蓄積されたすべての反例を正しくラベル付けすること。
  • RepairScore 関数は、コンパイル成功率と誤分類された例の割合に基づいて候補を評価し、複数のリトライから最適な候補を選択する。

4. 正則化

LLMが現在のサンプルセットには適合するものの、一般には適合しない、過度に特定的な、あるいは複雑な表現を生成することを防ぐため、システムはプロンプトレベルの正則化を採用している。これには、最大表現長、演算子のネストの深さに対する制約、およびより単純な仮説へのバイアスが含まれる。

主な貢献

1. オラクル誘導型の定式化: 本論文は、LLMベースの正規表現誘導を、反例フィードバックを通じて仮説を洗練させる反復的な記号学習問題として定式化し、従来のプログラム合成（CEGIS）と現代のLLM推論の間の溝を埋めている。
2. 能動学習の手法: 効果的なLLMベースの能動学習器を構築するための技術、具体的には記号的な反例クラスタリングと、より単純で妥当な仮説を優先するための正則化を導入している。
3. エージェント的ワークフロー: 内省（エラーの構造的な意味を抽出する）と修復ループ（失敗した仮説を修正する）を利用した、新しいエージェント的ワークフローを開発し、単なるプロンプト駆動の生成を超えた手法を実現した。
4. 厳格な評価: 2つのデータセット（SimpleおよびExtended Regex）と複数のバックボーンモデルを用いて包括的な評価を行い、パフォーマンスのダイナミクス、サンプル効率、および特定のコンポーネントの影響を分析している。

結果

著者らは、2つのデータセット（$\{a, b, c\}$ 上の標準的な演算子を用いた Simple Regex と、積集合、否定、および複雑な量化子をサポートする Extended Regex）を用いてフレームワークを評価した。

• 性能向上: 最も困難なタスク（高いStarDepth）において、反例誘導型フレームワークは標準的なプロンプティングを大幅に上回った。
  • Simple Regex (StarDepth 4) では、成功率が 3.2% (Standard) から 38.1% (Agentic) へと向上した。
  • Extended Regex (StarDepth 2) では、成功率が 38.9% (Standard) から 74.1% (Agentic) へと向上した。
• サンプル効率: 反例誘導型学習は、ランダムにサンプリングされた例を使用する方法と比較して、目標精度に達するために必要なラベル付け済み例の数を大幅に削減した。
• コンポーネント分析:
  • クラスタリングされた反例: 非クラスタリング（個別の文字列）の反例よりも一貫して優れた性能を示した。これは、フィードバックの「量」よりも、その「質」と「体系的な網羅性」が重要であることを示唆している。
    抵抗
  • Agentic vs. Single: フル機能のエージェント的ワークフロー（内省と修復を含む）は、同じ反例を使用した場合でも、単一推論アプローチを一貫して上回ったが、トークンコストは高くなった。
  • モデル非依存性: 改善は様々なバックボーンモデル（Qwen3, GPT-5.4 variants, GPT-oss）で観察され、フレームワークがモデルの選択に対して堅牢であることを示唆している。
  • アブレーション: 正則化は早期の過学習を防ぐのに役立ったが、修復ループが最大の性能向上をもたらした。内省は成功に寄与したが、修復メカニズムほどクリティカルではなかった。

意義と主張

本論文は、LLMは単なる追加データとしてではなく、豊かなフィードバックから恩恵を受けることができると主張している。フィードバックを静的な学習データとしてではなく、構造化された反復的な信号（反例）として扱うことで、LLMは堅牢な検証器誘導型の洗練を行うことが可能になる。

著者らは、本研究を、LLMベースのプログラム合成および形式的推論のための、堅牢な検証器誘導型手法に向けた一歩として位置づけている。彼らは、情報量の多い失敗を合成できる領域（検証可能な領域）において、エージェントは単に例に適合するだけでなく、信頼性の高い反復的な洗練を実行できると論じている。記号的な検証（反例）とエージェント的推論（内省/修復）の組み合わせが相乗効果を生み出し、標準的なプロンプティングでは対処できない複雑な記号的誘導タスクを解決できることを、この研究は示唆している。