← ポータルに戻る

ComBench: A Benchmark for Rigorous Proof Reasoning and Constructive Realization in Olympiad-Level Combinatorics💻 コードあり

Shunkai Zhang, Haoran Zhang, Yun Luo, Qianjia Cheng, Haodi Lei等 · combinatorics, large language models, mathematical reasoning · 2026-06-09 ⭐ 8/10
💡 LLMのオリンピックレベル組み合わせ論における厳密な証明推論と創造的な構成能力を評価・診断するための新しいベンチマーク「ComBench」を提案し、現在のモデルの限界と異なる能力の乖離を明らかにした論文。
🤖 Ayumuより: この論文、LLMがオリンピックレベルの組み合わせ論でどこまでできるか、めっちゃ詳しく評価してるのが面白いね！特に「証明」と「構成」でモデルの得意不得意が違うって発見は、今後のAI開発のヒントになりそう。朋義さんも、AIが数学の難問にどう挑むか、興味あるんじゃない？
combinatorics large language models mathematical reasoning benchmark proof reasoning constructive realization Olympiad-level
1. どんなもの？
  • ポイント1: LLMのオリンピックレベル組み合わせ論的推論能力を評価・診断するための新しいベンチマーク「ComBench」を提案。
  • 詳細: 組み合わせ論は深い離散的推論、創造的な構成、厳密な構造的洞察を必要とし、既存のLLMではまだ不均一な性能を示すため、このギャップを埋めることを目的としている。
  • ポイント2: 100問の人間がアノテーションした競技レベルの問題で構成され、2つの補完的な設定に分類される。
  • 詳細: 「分析中心の問題」（主に厳密な数学的議論を要求）と「構成中心の問題」（明示的な構成と正しさの正当化を要求）に分けられる。
2. 先行研究と比べてどこがすごい？
  • ポイント1: 「厳密な証明推論（Rigorous Proof Reasoning）」と「構成的実現（Constructive Realization）」という、LLMの異なる能力を診断できる特化したベンチマークである点。
  • 詳細: 既存のベンチマークでは捉えきれなかった、組み合わせ論特有の創造性と厳密性の両面を評価できる。
  • ポイント2: 評価プロトコルが、ルーブリックガイド付きの証明採点と決定論的な構成検証を組み合わせている点。
  • 詳細: これにより、単なる正解/不正解だけでなく、証明の質と構成の妥当性が乖離するケースを詳細に診断することが可能。
3. 技術や手法の肝はどこ？
  • ポイント1: ベンチマークの設計と問題分類。
  • 詳細: 100問の競技レベルの組み合わせ論問題を、厳密な証明を求める「分析中心」と、具体的な構成を求める「構成中心」に分類し、それぞれに人間が詳細なアノテーションを付与している。
  • ポイント2: 複合的な評価プロトコル。
  • 詳細: 分析中心問題には人間によるルーブリックガイド付きの証明採点を適用し、構成中心問題には明示的な構成の決定論的検証と、その正当化に対する証明採点を組み合わせることで、多角的な評価を実現している。
4. どうやって有効だと検証した？
  • ポイント1: フロンティアのオープンソースおよびクローズドソースのLLMを用いた実験。
  • 詳細: 最強モデルでも全体平均65.4%、Best@4で75.3%に留まり、ComBenchがまだ飽和状態には程遠いことを示し、今後のLLM開発の余地が大きいことを実証した。
  • ポイント2: モデル間の能力の乖離を明確に示した。
  • 詳細: Kimi-K2.6が分析中心の証明採点ではGPT-5.5に劣るものの、構成中心のBest@4では上回ることを発見し、ベンチマークが異なる能力を診断できることを実証した。また、存在問題と構成問題が特に難しいことも特定した。
5. 議論はある？
  • ポイント1: LLMの数学的推論能力、特に創造性や厳密性に関する現在の限界を浮き彫りにしている。
  • 詳細: ベンチマーク結果は、現在のフロンティアモデルでもオリンピックレベルの組み合わせ論における深い理解と創造的解決能力が不足していることを示唆している。
  • ポイント2: 人間によるアノテーションや採点のコストと主観性の問題。
  • 詳細: 競技レベルの複雑な証明の採点には専門知識が必要であり、そのコストや評価の主観性が課題となる可能性がある。また、「GPT-5.5」というモデル名の表記が、既存モデルの誤記か、将来のモデルを指すのか不明瞭な点も挙げられる。
6. 次に読むべき論文は？
  • ポイント1: LLMの数学的推論能力全般に関するベンチマーク論文。
  • 詳細: MATHベンチマーク、GSM8K、MiniF2Fなど、数学的な問題解決能力を評価する既存の主要ベンチマークに関する論文を読むことで、ComBenchの位置づけや貢献をより深く理解できる。
  • ポイント2: 数学的な証明生成や構成問題解決に特化したLLMアーキテクチャや学習手法に関する論文。
  • 詳細: 例えば、形式的証明検証器と連携するLLMや、競技プログラミングにおけるAI（AlphaCodeなど）の論文は、ComBenchで明らかになった課題へのアプローチを探る上で参考になる。

Abstract (原文)

Combinatorics is central to Olympiad-level mathematical problem solving, requiring deep discrete reasoning, creative constructions, and rigorous structural insight. Recent evidence suggests that even today's strongest frontier models remain uneven on Olympiad combinatorics, revealing a gap in creative mathematical reasoning. We introduce ComBench, an Olympiad-level combinatorics benchmark for evaluating and diagnosing the combinatorial reasoning capabilities of large language models. ComBench contains 100 human-annotated competition-level problems organized around two complementary settings: analysis-centric problems, which primarily require rigorous mathematical arguments, and construction-centric problems, which require explicit constructions in addition to correctness justifications. The evaluation protocol combines rubric-guided proof grading with deterministic construction verification, exposing cases where proof quality and construction validity diverge. Experiments on frontier open- and closed-source models show that ComBench is far from saturated: the strongest model reaches 65.4% overall Avg. and 75.3% overall Best@4. We further find that Rigorous Proof Reasoning and Constructive Realization are distinct capabilities: Kimi-K2.6 trails GPT-5.5 on analysis-centric proof grading but surpasses it on construction-centric Best@4, while Existence and Construction problems remain consistently hardest across representative frontier models.

📄 arxiv ページ 📑 PDF ⭐ GitHub (14 stars)