新着研究 / LLM / AI Agent
研究論文の定理を証明課題に変え、AIの推論力を測るTCSAlgBench
TCSAlgBench
概要
- 398の定理課題を138論文から作り、前提を残しながら証明の核心を伏せた。
- 著者らの判定器による5回の試行の受理課題率は、モデル比較の最高が23.6％、手順比較の最高が25.4％だった。
- 受理率は自動判定に基づき、手順比較ではトークン使用量にも差がある。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、TCSAlgBenchの仕組み
- 01研究論文の定理
- 02前提と定義を整理
- 03証明課題を作成
- 04証明文を判定
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
TCSAlgBenchは、AIが理論計算機科学の研究水準の定理を証明できるかを測る。ここで定理とは、ある手順が正しく動き、必要なデータ量や計算時間が一定の範囲に収まるといった主張である。
競技問題で正しい答えを出せても、新しい研究の主張を前提から筋道立てて示せるとは限らない。研究支援に使うには、提案した改善がどの条件で成り立つかを人が点検できる形で説明する力が重要になる。
手法
論文の記述から主な定理と、それに必要な定義・仮定を取り出す。論文内だけで通じる記号を補い、問題の条件を保ちながら、答えを示してしまう補題や手順名を除く。たとえば特定の「アルゴリズム1」の性能を証明する文は、同じ性能を持つ方法が存在するかを証明する課題に直す。
解答するシステムには課題文と引用された先行研究を渡し、元論文の証明は渡さない。出力は通常の文章で書いた証明である。引用内容を元の文献と照合した後、別に動く三つの判定器のうち二つ以上が受理すれば、評価上の成功と数える。
新規性
新しい研究論文から、前提と必要な定義を残しながら、証明の核心を伏せた課題を作る工程を整えた。アルゴリズムの発見が課題なら、名前付きの手順を「条件を満たす方法が存在する」という主張へ書き換える。
課題の出典と版を記録し、新たに公開される論文から評価群を追加できる。さらに、同じ398課題を使い、モデルの違いと、証明を進めるエージェントの手順の違いをそれぞれ比較した。
従来手法との違い
競技数学では最終答案の正否を測りやすいが、研究水準の定理では前提を守った証明と計算量の保証まで確かめる必要がある。TCSAlgBenchは理論計算機科学の定理を対象とし、関連する先行研究へのアクセスを与えた上で、自然言語による証明を求める。
手順の比較では、証明と批評を繰り返す方法、補題への分解、木探索、依存関係を計画し直す方法を扱った。同じ基礎モデルとモデル呼び出し機会で比べるが、実際に使うトークン量は異なる。
実験結果
398課題は2026年のSTOCとCOLTに採択された138論文から作られた。著者らは10種類のモデル設定と四つのエージェント手順を、全398課題で評価した。GPT-5.6 Sol maxは10回まで証明と検証を繰り返す設定で、5回の独立試行を合わせた受理課題率が23.6％だった。
別の手順比較では、GPT-5.5 xhighを共通モデルに用い、計画を更新する手順が5回の試行で25.4％と最高だった。ただし、その手順はトークン使用量も多い。課題文61件を人手で確認し、受理証明10件を著者が追加確認したと報告する。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：研究開発部門が新しいアルゴリズム案の理論的な説明を点検する。入力は主張する性能、必要な前提、参照を許す先行研究で、出力は自然言語の証明案と、その中で使う補助的な主張の一覧とする。
担当研究者は、各補助主張が証明されているか、引用元の条件を満たすか、計算量の式が結論に届くかを確認する。ベンチマークの評価形式を内部の検討手順へ応用する案であり、AIの証明をそのまま研究成果として採用できるという報告ではない。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：社内で内容を確認できる定理や性能保証を少数選び、前提、許す参考文献、期待する証明の条件を文書化する。基準は担当研究者による通常の検討とし、AIの直接回答と、証明案を批評して直す手順を同じ課題で比べる。
測る項目は、専門家が正しいと認めた証明の割合、未証明の補助主張、引用の条件違い、所要時間とトークン量とする。判定器の受理だけで終えず、少なくとも採用候補の証明は人が段階ごとに確認する。
限界と課題
著者らの主な結果は、三つの言語モデル判定器の多数決による「受理率」である。10件の受理された証明を著者の一人が確認し、すべて正しかったと報告するが、398課題すべての証明を人が検証したわけではない。221件のLean文は暫定的な定理文で、形式的な証明の完成数ではない。
編集上は、採点器の見逃しや誤判定、課題文が原論文の条件を正確に残すかを継続して監査したい。エージェント間では呼び出し機会を合わせてもトークン使用量が違うため、受理率と計算費用を併記して判断する必要がある。
出典
元のタイトル・要旨を確認する（英語）
TCSAlgBench: Benchmarking Automated Proving for Research-Level Theoretical Computer Science
Large language models perform strongly on competition mathematics, but their research-level reasoning remains difficult to evaluate systematically. Theoretical computer science (TCS) connects algorithm design to explicit guarantees and fundamental limits, providing a setting for evaluating whether models can justify computational improvements with arguments humans can inspect. We introduce TCSAlgBench, a benchmark and reusable pipeline for natural-language proof discovery, comprising 398 theorem-level challenges from 138 STOC and COLT 2026 papers. Expert-designed rules complete paper-specific context, preserve computational assumptions and quantitative guarantees, and withhold constructions when discovering an algorithm is part of the task. For each task, prover systems receive theorem statements and access to cited prior work. The pipeline supports fresh, versioned challenge batches from newly released papers. We evaluate ten model configurations from four families under direct inference and prover-verifier discussion, and compare four agent workflows under matched model-call opportunities. All evaluations use the full benchmark. In the model comparison, GPT-5.6 Sol max achieves the highest five-run verifier-accepted coverage at 23.6% after 10-round discussion. Discussion and repeated sampling improve coverage. In the separate agent comparison using GPT-5.5 xhigh, decomposition improves coverage over discussion, and agentic planning achieves the highest five-run verifier-accepted coverage at 25.4%. TCSAlgBench provides a refreshable testbed for measuring progress in model reasoning and studying how agent workflows support research-level proof discovery.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-09-29