アーカイブ / LLM
グラフ問題で推論モデルを測る：入力が長くなると何が崩れるか
GrAlgoBench
GrAlgoBenchの原論文から掲載した図です。細部はクリックして拡大できます。
原論文の図の説明を読む
Figure 1: Benchmark overview.
概要
- GrAlgoBenchは実世界のネットワークから作った計2,700問で、9種類のグラフ課題を評価する。
- Qwen3-32Bの課題平均pass@kは、31～50点で0.87、121～160点で0.47だった。
- 著者らは、手順の実行ミス、グラフ構造の記憶違い、効果の乏しい自己検証を報告する。
補足：編集した模式図で仕組みを確認する
VISUAL EXPLAINER
図でつかむ、GrAlgoBenchの仕組み
- 01実網の接続データ
- 02部分グラフを抽出
- 03設問を文章化
- 04モデル回答を照合
原論文の説明をもとにした模式図です。処理の細部は省略しています。
研究の背景
GrAlgoBenchは、つながりの多い情報を読ませたとき、推論モデルが計算手順を正しく進められるかを測る。グラフとは対象を「点」、対象間のつながりを「線」で表す構造で、道路網や人物関係などを記述できる。
著者らは、既存の推論評価には長い入力を試しにくく、答えの自動照合も難しいものがあると指摘する。業務で多数の関係を含む情報をAIに扱わせるなら、短い問題での成績だけで判断せず、入力の規模と正答の関係を確かめる必要がある。
手法
著者らは共同研究、道路、航空路線などの実世界のネットワークから、点が8～160個の部分グラフを抽出した。部分グラフとは元のネットワークから取り出した一部の点と線である。9種類の課題について接続関係と設問を文章でモデルに渡し、得られた整数や点などの答えを計算済みの正解と照合する。
例えば道路網を使うDistance-k課題では、指定した道路から一定回数以内の交差で到達できる道路の数を問う。課題は列挙・探索・直観の3群に分ける。点の数を変える試験に加え、接続関係を固定して点の名前だけを長くし、文章量の影響も調べた。
新規性
GrAlgoBenchは、実世界のネットワークから切り出したグラフを使い、点の数を8～160の範囲で変えられる評価用データセットである。答えは整数や特定の点などで表せるため、プログラムで照合できる。
著者らは9課題を、候補を調べ尽くす「列挙」、経路などをたどる「探索」、その場の選択を積み重ねる「直観」に整理した。正答の集計に加え、誤答の過程や、長い自己検証と正答との関係も調べる。
従来手法との違い
著者らは、従来の数学・コード・常識推論の評価では入力を段階的に長くしにくく、答えの表記揺れも自動採点を難しくすると指摘する。本研究ではグラフの点の数や説明文の長さを変え、定まった答えと照合する。
論文の比較表に載る既存のグラフ評価は最大50点で、推論モデルの評価を対象としていない。GrAlgoBenchは最大160点を扱う。ただし、この表は同じモデルを各評価データで解かせた成績比較ではない。
実験結果
著者らは9課題について、点の数を6段階に分けた計2,700問を用意した。表は複数回の回答に基づくpass@kとcons@kを示すが、確認できた本文の範囲ではkの設定は示されていない。Qwen3-32Bの課題平均pass@kは31～50点で0.87、81～120点で0.59、121～160点で0.47だった。
別の試験では、各80点・200線のグラフ50件を使う3課題で、接続関係を固定し、平均入力長を4千～6万4千トークンに変えた。トークンはモデルが文章を処理する際の単位である。著者らによると、Triangle Sum課題でDeepSeek-R1のpass@kは4千トークン時の100％から6万4千時の22％に下がった。
応用の可能性
編集上の応用案 · 論文が実証した用途とは区別しています。
編集上の応用案：道路網の接続関係を文章で受け取るAIに、指定した道路から一定回数の交差を経て到達できる道路の数を答えさせる。入力は道路同士の接続データ、起点となる道路、許容する交差回数とし、出力は条件を満たす道路の数とする。
元の研究で使う道路網は、道路を点、道路同士の交差を線として表す。試行には対象地域の接続データと、既存のグラフ計算で作った正解ラベルが必要だ。道路データをこの表現に変換する作業が要り、実際の経路判断に役立つかは別途確かめる。
応用先の候補からNauhに相談できます。
導入時の検証
導入時の検証案 · 対象データでの再評価が必要です。
導入時の検証案：対象地域の道路接続データを集め、道路を点、交差を線に変換する規則を決める。起点と交差回数を変えた小規模な設問を作り、既存のグラフ計算で正解ラベルを付ける。入力は接続関係の文章であり、この試験に画像・音声センサーは要らない。
同じ設問を検討中のAIと既存のグラフ計算手順で処理し、正答率と回答時間を記録する。点の数を増やす試験と、接続関係を固定して道路名の文章だけを長くする試験を分ける。業務データへの適応は、道路名の表記規則と設問文を整えるところから始める。
限界と課題
著者らは、グラフが大きくなる場合と、構造を固定したまま説明文を長くする場合の双方で成績低下を報告する。誤答の分析では、手順の実行ミス、グラフ構造の記憶違い、冗長な推論を挙げ、長い自己検証も正答の改善につながりにくいと述べる。
編集上の検証事項は、業務の接続データでも同じ傾向が出るか、設問や点の名前の書き方で結果が変わるかである。確認できた本文の範囲では、自己検証を分割して評価する後半の詳細は途切れているため、その手順や効果量までは判断しない。
出典
元のタイトル・要旨を確認する（英語）
Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems
Large Reasoning Models (LRMs) have advanced rapidly; however, existing benchmarks in mathematics, code, and common-sense reasoning remain limited. They lack long-context evaluation, offer insufficient challenge, and provide answers that are difficult to verify programmatically. We introduce GrAlgoBench, a benchmark designed to evaluate LRMs through graph algorithm problems. Such problems are particularly well suited for probing reasoning abilities: they demand long-context reasoning, allow fine-grained control of difficulty levels, and enable standardized, programmatic evaluation. Across nine tasks, our systematic experiments reveal two major weaknesses of current LRMs. First, accuracy deteriorates sharply as context length increases, falling below 50% once graphs exceed 120 nodes. This degradation is driven by frequent execution errors, weak memory, and redundant reasoning. Second, LRMs suffer from an over-thinking phenomenon, primarily caused by extensive yet largely ineffective self-verification, which inflates reasoning traces without improving correctness. By exposing these limitations, GrAlgoBench establishes graph algorithm problems as a rigorous, multidimensional, and practically relevant testbed for advancing the study of reasoning in LRMs. Code is available at https://github.com/Bklight999/GrAlgoBench.
論文本体の取得範囲に基づく解説。AIが作成した未校閲の記事です。性能の数値は著者の評価条件に依存します。応用例と検証計画は編集上の提案です。解説更新：2026-10-01