概要 - フォーミュラワン：競技プログラミングを超えたアルゴリズムの推理の深さを測定

フォーミュラワン：競技プログラミングを超えたアルゴリズムの推理の深さを測定

2025-07-17 17:53:55

{"Gal Beniamini","Yuval Dor","Alon Vinnikov","Shir Granot Peled","Or Weinstein","Or Sharir","Noam Wies","Tomer Nussbaum","Ido Ben Shaul","Tomer Zekharya","Yoav Levine","Shai Shalev-Shwartz","Amnon Shashua"}

{cs.AI,cs.CC,math.LO}

FormulaOneは、AIモデルのアルゴリズム的な推論の深さを測定するための基準で、競争プログラミングの構想されたパズルではなく、現実の研究問題に焦点を当てています。この基準は、グラフ理論、論理、アルゴリズムの交差点に位置し、フロンティアモデルのトレーニング分布内にあります。 データセットには以下の3つの主要な特性があります： 1. 商業的な興味があり、ルーティング、スケジューリング、ネットワーク設計などの実践的な大規模最適化問題に関連しています。 2. グラフ上の高度に表現力のあるモナド第二階（MSO）論理から生成され、スケールの自動問題生成のための道を開いています。 3. 多くの問題は理論情報科学の最先端に関連しており、強い指数時間仮説（SETH）などの主要な仮説と密接に関連しています。 FormulaOneの問題は非常に困難で、多くの推論ステップを必要とし、トポロジカルおよび幾何的な洞察、数学的な知識、組み合わせの考慮、正確な実装などが含まれます。 OpenAIのo3などの最先端モデルは、FormulaOneで完全に失敗し、10回の試行と説明付きの少数ショット例が提供された場合でも、問題の1%未満を解決しています。これにより、これらのモデルが特定の分野における専門家レベルの理解からどれだけ遠いかが明らかになります。 FormulaOneは、モナド第二階（MSO）論理を使用して生成されたグラフ上のさまざまな動的計画問題で構成されており、抽象的な問題解決、多段階の組み合わせ推論、実践的な実装のスキルを測定するために設計されています。 データセットには以下の2つの部分が含まれています： 1. FormulaOne：創造性、洗練度、専門家レベルの推論を評価する120の挑戦的な動的計画問題のデータセット。 2. FormulaOne-Warmup：この困難な設定における研究と評価を促進するための100のより単純な問題を含む補助データセット。 この基準は、動的計画問題の体系的な生成と提案された解決策の検証を可能にする包括的なフレームワークを使用して評価されます。評価には、解決策の有効性の異なる側面を探るためのいくつかの主要なテストスイートが含まれています。 結果によると、最も優れたフロンティア推論モデル、例えばOpenAIのo3でも、FormulaOneデータセットで完全に失敗し、驚くほどの<1%の成功率を達成しています。これは、より高度な複雑さを捉えるためのより深い推論環境とより良い基準が必要であることを示しています。