LLM の長時間タスク対応に「Progressive Point Matching」手法を提案

Preston Fu (https://www.prestonfu.com/) **2026 年 9 月

現在の大規模言語モデル（LLM）は、数時間から数日にわたって継続して実行される極めて長期のタスクを処理できるようになりました。人間が数日や数週間を要するタスクには、数百万、あるいは将来的には数十億トークンに及ぶ言語モデルの軌道（trajectories）が必要になる可能性があります。

こうした能力は、大規模な強化学習（RL）によって実現されました。標準的なアプローチでは、完全な軌道をサンプリングし、その成功・不成功に応じて 0 または 1 のスパースな結果報酬を割り当てます。経験則として、この単純な手法はスケーラブルに安定した性能向上を示してきました。なぜなら、最適方策には*不偏（unbiased）*の目的関数が備わっているからです。つまり、タスク成功の尤度を最大化するように学習されるのです。

しかし、より長時間実行されるタスクへとスケールを進めるにつれ、スパースな結果報酬は次第に非効率になっていきます。例えば、数十のサブタスクで進捗を示しながら最終段階で失敗した軌道も、全く進展しなかった軌道と同じ報酬しか得られません。理論的に示す通り、スパースな結果報酬を用いると、信号対雑音比がタスクの時間範囲（horizon）に対して*指数関数的に*劣化する方策勾配が生じます。

学習された価値関数、プロセス報酬、自己蒸留など多様な手法が、漸近的なバイアスをもたらしてきました。ここで言うバイアスとは、代理目的関数における最適方策が、最終的な成果報酬においては最適ではない可能性を指します。例えば、軌道の各段階で「論理的正しさ」に報酬を与えるプロセス報酬は、最終的なタスク成功には無関係な論理的に正しい発言を行うことを誘発する可能性があります。

私たちは、部分的な信用（Partial Credit）を付与するためのシンプルかつ漸近的にバイアスのないフレームワークである Progressive Point Matching (PPM) を提案します。

図 1. 部分的な信用を付与する手法は、スパースな成果報酬に比べて収束が指数関数的に速くなります。プロセス報酬のようなバイアスのかかった部分信用手法では、最適ではない方策へ収束してしまう可能性があります。

フレームワーク

我々の重要な洞察は、推論問題を解くことは、マルコフ状態空間内を探索する経路を発見することとみなせる点にあります。

推論の軌跡は長くなる傾向があり、過去の推論結果を中間成果として圧縮して保存できます。例えば定理証明では、途中の補題を証明する必要がある場合があります。一度補題が提示され証明されれば、その後の推論はその補題を前提条件とするだけで、証明の詳細まで遡る必要はありません。こうした中間成果を「推論ポイント」と呼びます。

実際には、人間が書いた証明のような参照軌跡から推論ポイントを抽出します。圧縮の性質上、参照軌跡から推論ポイントを抽出するのはコストがかかりませんが、その逆方向は容易ではなく、場合によっては補題の証明自体が必要になります。つまり、完全な言語モデルによる推論トレースを必要としないということです。

したがって、推論軌跡はコンパクトな状態表現を持ち得ます。それは「現在の軌跡プレフィックスが訪れた推論ポイントの集合」です。推論軌跡は、ゴール到達のための「推論 MDP」と呼ばれる状態空間内を移動する経路と見なせます。ここでゴール状態には、最終的な答えなどのゴールポイントが含まれている必要があります。各アクションは、この集合に新しい推論ポイントを追加することを意味します。

この設定から導かれる重要な帰結の一つは、推論ポイントの集合が時間とともに縮小しないことです。つまり、構成上「進捗は決して取り消せない」のです。ここでいう進歩とは、この集合のサイズを指します。例えば、軌跡が誤った方向に進んだとしても、その推論状態は変化せず、補題まで遡って戻ることは依然として可能です。

しかし、問題があります。参照軌道とは全く異なる戦略でゴールに到達する成功した軌道を考えてみましょう。定義によれば、これは進捗が非常に低いと評価されてしまいます。一方、ゴールには到達できないものの参照軌道にほぼ沿った失敗した軌道は、高い進捗として評価される可能性があります。その結果、単純に進捗の最適化を行うことはバイアスを含んでしまうのです。

これを解決するには、ショートカット（shortcutting）メカニズムを導入します。ある点が到達済みとみなされるのは、その点に依存するすべての点がすでに到達済みとなっている場合です。これにより、成功した軌道には必ず満点の報酬が与えられます。[2] 図1で示唆している通り、ショートカットを採用することで、参照軌道とは異なる戦略も学習可能になります。これは pass@k の向上にとって極めて重要です。論文では、ショートカットを用いることで結果報酬に対して最適な方策を学習できることを示しています。

PPM は長期推論タスクにスケーラブル

タスクの時間軸（ホライズン）の影響を単独で評価するため、合成タスクを用います。これにより、(i) サブタスクの数と (ii) 推論 MDP の「形状」を自在に制御できます。

直感的には、PPM に代表されるようなクレジットアサインメント手法は、各サブ問題が独立している場合、あるいは言い換えれば推論ポイント間に依存関係がない場合に最も高い性能を発揮します。この設定では、各サブタスクごとに独立した方策勾配（policy gradients）を得ることが可能になります。その結果、サブ問題の数 n を増やしていくと、標準的な GRPO に対する実用的な学習速度の向上が、n に対して指数関数的に拡大することが明らかになりました。

*Figure 3. 各サブタスクが独立した合成タスクにおいて、タスクの時間軸（ホライズン）が長くなるほど、PPM はスパースな結果報酬に対して指数関数的に学習効率を向上させます。

論文には、軸 (ii) を探求するための追加実験も多数含まれています。例えば、各サブ問題が前のサブ問題の正解に基づいてのみ解決できる、はるかに困難な MDP を検討しました。この場合、到達ポイント同士が強く相関し、理論的に示した通り方策勾配の信号対雑音比（signal-to-noise）が低下します。また、これらの二つの極端なケースの中間に位置する合成推論タスクも検討しています。

興味のある方は、our paper をぜひご覧ください！

PPM は、ほぼ不可能な数学的推論タスクの学習を可能にする

アルゴリズムをより長いホライズンのタスクにスケールさせるにつれ、数百万トークンにも及ぶ trajactory（軌道）データを直接トレーニング対象とすることは現実的ではありません。そのため、実用的な RL システムは、これらのタスクを小規模なトークン予算で「シミュレート」したバージョンを用いて学習を行い、テスト時に大幅に大きなトークン予算を確保した際の性能向上を目指します。

最近の取り組みとして、Claude Code の /effort ultracode モードのように、極めて大規模なテスト時予算における性能向上を実現するために、ハネスやマルチエージェントワークフローを設計する動きもあります。しかし、こうしたアプローチは不十分であり、フラウンティアモデルにおいて予算を増やしてもパフォーマンスが不安定になるという結果をもたらしています。つまり、現在の RL アルゴリズムは、依然としてテスト時予算へのスケーラビリティにボトルネックを抱えています。

この状況では、トレーニング時のトークン予算内でタスクが解決されることは稀です。このような状況を表す一つの指標として、極めて困難な数学問題からなるデータセットがあります。ここではベースポリシーが得られる結果報酬はほぼ常にゼロとなります。このような環境で、スパースな結果報酬を用いて GRPO で学習することはほぼ不可能です。実際に 24 時間試みましたが、トレーニングバッチを一つ埋めるのに十分な trajactory をサンプリングできませんでした。

このデータセットで学習を行うと、PPM は次点の手法を大きく上回る結果となりました。しかし、より驚くべき発見は、4K の長さで学習したモデルが 8K で学習した場合と比較して同等か、それ以上に優れた性能を示すことです。

図 4. 極めて困難な数学的推論データセットで学習を行った際、テスト時のトークン予算を大きく増やした場合（成功率または pass@8 の観点から測定）、PPM は次点の手法（POPE）を大幅に上回ります。データのフィルタリングにより、GRPO は何ら進展を見せませんでした。

なぜこのような現象が起きるのでしょうか。その原因は出力長さの崩壊にあります。8K で学習されたポリシーは、答えを貪欲に推測して推論プロセスを早期に終了させてしまう傾向があります。一方、4K で学習されたポリシーは、トレーニング時のトークン予算内で成功することが不可能なため、部分的な進捗に対して最適化を行うことになります。つまり、こうしたタスクにおいては、より短いシーケンス長で学習することが有益となる領域が存在するのです。詳細については 論文 をご覧ください。

今後の展望

我々の手法は、以下の 2 つの重要な要件に基づいて設計されました。

• この手法はバイアスがありません。PPM における最適ポリシーが、成果報酬に基づく最適ポリシーと一致するためです。
• 報酬は目標への部分的な進捗に比例して付与されます。「部分的な進捗」とは、現在の（推論）状態から開始した場合の期待される最終的なリターンを指します。

論文で示した通り、PPM は望ましい性質 (1) を満たします。また、図 2 や図 3 に示されるような最小限の設定では、推論ポイントを「参照経路に沿った到達点」として定義するか、「明確に範囲が定められた中間サブタスクの解決」を指すように定義すれば、PPM は望ましい性質 (2) も満たします。

しかし、一般的な推論タスクには、サブタスクへのきれいな分割が自動的に用意されているわけではありません。実際には、既存の LLM を用いて推論ポイントを生成していますが、予測された進捗とモンテカルロリターンとの間に強い相関を生み出すためには、多くの試行錯誤が必要でした。論文で示した通り、提案する推論ポイント評価に基づけば、PPM は単純なルブリック評価ベースラインを上回る性能を発揮します。

これにより、以下のような多様な研究の方向性が開かれます：

• PPM は、複数の参照経路が与えられる設定にもよく拡張できます。各経路ごとのグラフを結合して推論グラフを構築すればよいからです。ただし、グラフが大きくなると、サンプリングされた経路の評価にかかるコストやばらつきが増大します。「メタグラフ」を効率的に構築したり、新しい報酬関数を設計したりすることは可能でしょうか？

• PPM は模倣学習の近似とみなすことができます。この場合、参照経路上の推論ポイントを任意の順序で訪れる自由が得られます。その結果生じる素晴らしい性質の一つは、「ゴール到達タスク」すべてを、参照経路と十分に優れた評価者だけで決定できる点です。つまり、このフレームワークは検証不可能な環境においても同様の恩恵を受けられる可能性があります。

実際、PPM の学習ダイナミクスを理解し、データ分布やトレーニングトークンの予算、軌道セグメンテーションの手順といった要因との関係を把握することは、模倣ベースのアプローチを極めて長い時間スケールのタスクに拡張する上で極めて重要です。手法の簡素さを保つため、標準的な GRPO からハイパーパラメータを引き継ぎましたが、学習をさらに安定化させる追加の工夫が存在する可能性もあります。

このように模倣学習と強化学習をつなぐ新しい手法の領域について非常に興奮しており、困難で長い時間スケールのドメインに取り組む新たなアプローチが現れることを楽しみにしています！

謝辞

本記事に対する有益なフィードバックをいただいた Aviral（https://aviralkumar2907.github.io/）、Kevin（https://kvfrans.com/）、Oleg（https://olehrybkin.com/）に感謝いたします。

引用

@misc{fu2026longhorizonlanguagemodelreinforcement,
      title={Long-Horizon Language Model Reinforcement Learning via Progressive Point Matching},
      author={Preston Fu and Kevin Frans and Oleh Rybkin and Sergey Levine and Aviral Kumar},
      year={2026},
      eprint={2609.07303},
      archivePrefix={arXiv},
      primaryClass={cs.LG},
      url={https://arxiv.org/abs/2609.07303},
}