💬 NLP

ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

本論文は、LLM の推論トレースを再利用可能でゼロトークンの記号ソルバーにコンパイルするフレームワーク「ReaComp」を提案するものであり、これはプログラム合成ベンチマークにおいて最先端の精度を達成し、LLM と組み合わせた際にトークン使用量を大幅に削減し、さらに実世界の言語タスクへも成功裏に転移する。

原著者： Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

公開日 2026-05-08

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

CC BY 4.0

原著者： Atharva Naik, Yash Mathur, Prakam, Carolyn Rose, David Mortensen

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

以下は、論文「REACOMP」を平易な言葉と日常的な比喩を用いて説明したものです。

大きな問題：「考えすぎ屋」

非常に賢く創造的なアシスタント（AI）がいると想像してください。このアシスタントはパズルを解くのが得意です。しかし、パズルが非常に難しかったり長かったりすると、このアシスタントはパニックに陥ります。彼らは推測し、確認し、再び推測し、巨大で散らかったメモを書き出すことで解決しようとします。最終的に正解にたどり着くことはあっても、それには膨大な量の紙（計算資源）と時間を費やしてしまいます。時には、同じ過ちを何度も繰り返すループに陥ってしまいます。

研究者たちは、これらの AI アシスタントは強力である一方で、複雑な多段階の論理問題（テキストの文字列を書き換えることや、データから規則を見つけることなど）に直面した際、非効率で高価であることを発見しました。

解決策：「レシピ本」（REACOMP）

賢いアシスタントに毎回新しいパズルをゼロから解かせる代わりに、研究者たちはREACOMPと呼ばれる新しい手法を考え出しました。

以下のように考えてみてください：

観察フェーズ：まず、彼らは賢いアシスタントがいくつかの練習パズルを解くのを見ています。アシスタントがどのように考え、どこでつまずき、どのような戦略で成功しているかを見ています。
コンパイルフェーズ：彼らは「コーディングエージェント（専門的な AI プログラマー）」を雇い、これらの練習セッションを見てもらいます。このプログラマーは単に答えをコピーするのではなく、観察したパターンに基づいて永続的なルールブック（記号ソルバー）を作成します。このルールブックは、その種類のパズルを瞬時に解くことができる厳密で論理的な指示のセットです。
実行フェーズ：これで、新しいパズルが入ってきたとき、彼らは賢いアシスタントに考えさせません。パズルをルールブックに渡すだけです。ルールブックは、賢いアシスタントの「思考」パワーを一切使わずに瞬時に解決します。

もしルールブックが非常に奇妙なパズルでつまずいた場合、そのときだけ（そしてその場合のみ）、彼らは助けを求めて賢いアシスタントを呼び出します。

結果：速度、節約、そして賢さ

この論文は、2 種類の難しい論理パズル（PBEBench と SLR-Bench）でこれをテストしました。以下が起きたことです：

「ゼロコスト」の勝利：ルールブック（記号ソルバー）は非常に優れており、最も難しいパズルの84.7% から 91.3%を、賢いアシスタントに全く助けを求めずに解くことができました。これは、これらの問題を解くためのコストが AI の「脳」の使用においてゼロに下がったことを意味します。
巨人たちへの勝利：最も難しいパズルにおいて、ルールブックは、最大限の努力をする（何度も試すことを許された）賢いアシスタントよりも優れていました。ルールブックは、AI 単独が使用する最良の「推測と確認」の方法よりも 16% 正確でした。
ハイブリッドの超能力：彼らはルールブックと賢いアシスタントを組み合わせました（まずルールブックを使用し、バックアップとしてのみアシスタントを使用）。これにより、両者の長所を享受できました。彼らは、AI 単独で使用する場合よりも78% 少ない計算資源（トークン）を使用しながら、これらのテストで記録された最高精度を達成しました。
実世界でのテスト：彼らは、古代言語における音声の変化についての実際の言語パズルでもこれを試しました。この特定のトピックについて教わったことのないルールブックは、練習パズルから学んだ論理を使うだけで、80% の精度でそれを解きました。

重要な教訓

この論文は、新しい問題ごとに AI に「より深く考えさせる」ことを続けるべきではないと主張しています。代わりに、AI に一度だけ学び方を学ばせ、その学びを永続的で再利用可能なツール（ソルバー）に変換し、その後そのツールをすべてに使うべきです。

これは、毎回ゼロから数学の問題を解くために天才を雇うこと（高くつくし遅い）と、一度だけ天才を雇って電卓アプリを書かせ、そのアプリを永久に使うこと（安価で速く、信頼性が高い）の違いです。

主張の要約

効率性：AI の推論痕跡を、AI を再度必要とせずに問題を解決する再利用可能なツールに変換できます。
性能：これらのツールは、困難で長いタスクにおいて、AI 自体よりも優れていることが多いです。
コスト：この手法は、AI システムを実行するために必要な資金とエネルギーを劇的に削減します。
汎用性：これらのツールは、再トレーニングを必要とせずに、新しい実世界のタスク（言語学など）に適用できます。

技術概要：REACOMP

問題定義

大規模言語モデル（LLM）は、特にプログラミング・バイ・エクサンプル（PBE）パラダイム内において、プログラム合成タスクで能力を示しています。しかし、大規模な組み合わせ探索を必要とする困難なインスタンスにおいては、重大な非効率性と信頼性の欠如に悩まされています。分析によると、より困難なインスタンスは、構成的一般化の失敗や非効率的な探索戦略（例：ループ、冗長な探索）に起因する失敗により、不釣り合いに高いトークン使用量と複数の試行を引き起こします。既存のアプローチは、学習済みライブラリやツールを LLM に付加しようとするものの、これらの手法は推論時の反復的推論とツールの呼び出しに依存することが多く、計算予算に対して敏感であり、インスタンス間で学習された構造を一貫して再利用できずにいます。その結果、LLM は依然として解空間に対して主に非構造化された探索を行い、解の長さが増加するにつれて計算の無駄が生じています。

手法：REACOMP

著者は、推論時の推論を直接改善するのではなく、LLM の推論トレースを再利用可能な記号ソルバーにコンパイルするフレームワークREACOMPを提案します。このアプローチは、2 つの明確な段階から構成されます。

1. オフラインソルバー誘導

これは、コーディングエージェントが LLM の推論トレースから反復する戦略と失敗モードを蒸留し、制約付きドメイン固有言語（DSL）上で動作するスタンドアロンの記号プログラム合成器へと変換する、一回限りの手順です。

トレースデータセット: LLM（例：gpt-oss-120b）がベンチマークタスクの小さなサブセットを解決する際に生成された推論トレースのデータセットを構築します。これらのトレースには、中間ステップ、候補プログラム、結果が含まれており、難易度と成功/失敗のバランスが取れています。
コーディングエージェント誘導: コーディングエージェント（例：Claude Code または Qwen + OpenHands）が、トレースデータセットと読み取り専用の検証器を含むサンドボックス環境内で動作します。エージェントは、ソルバーの実装（例：SOLVER.py）を構築するためにワークスペースを反復的に編集します。
プロセス: エージェントはコードの編集を提案し、実行し、トレースデータセット上のパフォーマンスに基づいてソルバーを改善します。エージェントはテスト時に利用可能な入力 - 出力例のみを観察するため、誘導されたソルバーは推論中に LLM 呼び出しを必要としないスタンドアロンシステムとなります。
出力: スタンドアロンの Python ソルバーとアルゴリズム記述ファイル。

2. 効率的なハイブリッド推論

テスト時には、効率性と精度のバランスを取るために 2 パス戦略を採用します。

記号ファーストパス: 誘導された記号ソルバー（ $S_\phi$ ）が、与えられたタスク $D$ に対して一連の候補を提案します。候補が完全な報酬（ $R=1$ ）を達成した場合、ゼロの LLM 推論コストで即座に返されます。
LLM フォールバック: 記号ソルバーが完全な解を見つけられない場合、システムは残りの「困難な」ケースを解決するために、標準的な LLM 探索手順（Best-of-K サンプリングまたは直接フィードバックによる反復改善）にフォールバックします。

この構造は、ソルバーの小さな一回限りの構築コストを、多くのゼロトークン実行にわたって償却し、高価な LLM 推論を残留ケースのみに限定します。

主要な貢献

誘導手法: コーディングエージェントを用いて LLM の推論トレースから再利用可能な記号ソルバーを誘導する新規手法。非構造化された探索トレースを構造化されたスタンドアロン合成器へと変換します。
強力なスタンドアロン性能: 誘導されたソルバーが強力なスタンドアロンシステムとして機能し、LLM のテスト時スケーリングを困難なインスタンス（例：PBEBench-Hard）において凌駕し、タスクごとの LLM 推論コストをゼロで実現することを示す証拠。
パレート支配的なハイブリッドパイプライン: トークン使用量を最大 78% 削減しながら最先端の結果を達成するニューロ記号ハイブリッドパイプライン。各タスクに直接コーディングエージェントを適用するアプローチを実質的に支配します。
ゼロショット一般化: 誘導されたソルバーの多くが、音韻変化の前方再構成に関する歴史的言語学のケーススタディにおいて、実世界の分布に対してゼロショットで一般化することを示す実証。

実験結果

著者は、PBEBench（文字列変換）とSLR-Bench（帰納的論理プログラミング）において REACOMP を評価しました。

PBEBench-Lite: 記号ソルバーのアンサンブルは**91.3%**の精度を達成し、LLM ベースラインと同等かそれ以上の性能を示しました。ハイブリッド推論（記号 + LLM フォールバック）は、ピーク精度（93.9%）を維持しながらトークン使用量を 36% 削減しました。
PBEBench-Hard: 長期的なカスケード合成において、LLM のテスト時スケーリング（Best-of-K）は 68.4% の精度を達成しました。誘導された記号ソルバーはこれを大幅に上回り、「All Symbolic」アンサンブルはゼロの LLM 推論コストで**84.7%の精度（+16.3 パーセントポイントの向上）に達しました。ハイブリッド推論はこれをさらに85.8%まで向上させ、LLM のみのベースラインと比較してトークン使用量を78%**削減しました。
SLR-Bench: 最難易度ティアにおいて、CC 記号ソルバーは**46.8%の精度を達成し、最先端モデル（o3、GPT-5）と同等の性能をゼロ推論コストで実現しました。ハイブリッドアプローチ（DF + CC）は、難易度ティアの精度を58.0%まで引き上げ、これまでに報告されたすべてのベースラインを上回りました。最良のハイブリッド（DF + CC + QO）は、最先端モデルのコストのほんの一部で、全体精度86.7%**に達しました。
効率性: 記号ソルバーは非常に効率的であり、純粋な Python で 1,000 以上のタスクの推論を 5 分未満で完了します（LLM ベースの手法では約 2 日かかるのに対し）。
実世界への転移: 歴史的言語学の前方再構成タスク（音韻変化の予測）において、誘導されたソルバーはアンサンブル下で**80.1%**の精度を達成し、再トレーニングなしで妥当な言語規則を回復しました。

意義と主張

本論文は、REACOMP がドメイン一般のソルバー誘導へのスケーラブルな経路を実証していると主張しています。推論トレースを再利用可能な記号構造にコンパイルすることで、このアプローチは、独立した LLM サンプリングと長期的な構成的タスクの間の根本的なミスマッチに対処します。著者は以下を論じています。

飽和状態における効率性: LLM の精度が飽和に近い領域では、ソルバー誘導は精度よりも効率性において主要な利益を提供します。
困難なタスクにおける相補性: 困難で長期的なタスクにおいて、記号ソルバーは構造化された探索により LLM が失敗する領域で卓越し、LLM は残りのタスクをカバーすることで、相補的なハイブリッドシステムを形成します。
償却: このアプローチは、小さな一回限りの構築コストを多くのゼロトークン実行にわたって償却し、インスタンスごとにコーディングエージェントを適用するよりも実質的にパレート効率的です。
一般化: ソルバーが未見の分布（例：実世界の言語データ）に対してゼロショットで転移する能力は、誘導されたアルゴリズムが単なる暗記ではなく、一般化可能な構造的洞察を捉えていることを示唆しています。

著者は、ソルバーの品質がコーディングエージェントの能力と使用される DSL の特定の性質に敏感であるという限界を指摘しています。また、ソルバーが妥当な規則を回復する一方で、時としてコンパクトで一般化可能な構造よりも検証器を満たす解を好む傾向があり、報酬関数の整合性とソルバー誘導の探索戦略に関する今後の研究が必要であることを観察しています。