Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems
Authors: Qifan Zhang
Jianhao Ruan
Aochuan Chen
Kang ZENG
Nuo Chen
Jing Tang
Jia Li
Venue: ICLR 2026 Poster (2026)
Keywords: Large Reasoning Models
Graph Algorithm Problems
Large Language Models
Primary area: datasets and benchmarks
TL;DR: We introduce GrAlgoBench, a graph algorithm benchmark across three reasoning dimensions, which exposes LRMs’ key limitations: weak long-context reasoning and ineffective over-thinking.

Abstract: Large Reasoning Models (LRMs) have advanced rapidly, yet existing benchmarks on 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 with longer contexts input—falling below 50% once graphs exceed 120 nodes—driven by frequent execution errors, weak memory, and redundant reasoning. Second, LRMs suffer from an "over-thinking" phenomenon, primarily driven 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://anonymous.4open.science/r/GrAlgoBench-7D17.

Published as a conference paper at ICLR 2026
EXPOSING WEAKNESSES OF LARGE REASONING MOD- ELS THROUGH GRAPH ALGORITHM PROBLEMS
Qifan Zhang" Jianhao Ruan"
Aochuan Chen
Kang Zeng
Nuo Chen
Jing Tang Jia Lit
The Hong Kong University of Science and Technology (Guangzhou)
{gzhang297, bruan189, achen149, kxeng228|@cconnect @connect tkkust-gz.ede chennuo266 www.l.mmmml..oommmmmmmmmm...mmem com, (jingtang, (ust.
ABSTRACT
Large Reasoning Models (LRMs) have advanced rapidly, yet existing benchmarks on 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 GR ALGOBENHH 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 with longer context inputs-falling below 50% once graphs exceed 120 driven by frequent execution errors, weak memory, and redundant reasoning. Second, LRMs suffer from over-thinking phenomenon, primarily driven 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 LRMs. Code available at //gi htggituub.cmm//k/k wttht/l////k/tteee...ococcccceee 999/ 999.aattteeotrreeeeeoeeoeeo
INTRODUCTION
I Large language models (LLMs) have evolved rapidly over the past few years, becoming powerful general-purpose tools with remarkable achievements in natural language processing and complex reasoning. Recently, the emergence of Large Reasoning Models (LRMs), such OpenAI-O1 (Ope- nAI 2025) and DeepSeck-RI (Guo et al. (025), has further pushed the frontier LLM development. By leveraging long chains of thought enriched with human-like cognitive strategies including self-verification, strategy shift, and backtracking.. these models show significant improvements on
challenging reasoning tasks (Qin al. 2024 Min al., 2024 Feng et 2025
Dong et al. 2025)..
Accordingly, evaluating the reasoning capabilities of LRMs and probing their limitations, such as
over-thinking and under-thinking, has become timely research focus (Zheng et al. 2025 Chen et al.
2024d Sun et al. 2025 Yang et al. 2025b c).
Current benchmarks for LRMs, while valuable, exhibit several critical deficiencies when centered on domains like mathematical reasoning (Chen et al., 2024b] Petrov et al., 2025] He et al.
2024
Huang et al. 2024 Gulati al., [024 Glazer al. 2024] Li et al. 2025b] Huang et al. [025
code
generation (Li et al. 2022] Dai et al. 2024 Yang et al. 2025b Yu et al. 2024: Wei et al 2025
He al. 2025b] Zheng et al.) 2025), and common-sense reasoning (White et al. 2024 Suzgun
et al. 2022 Lin et al., 2025). First, they lack long-context input evaluation: existing benchmarks
predominantly use short problem texts, which cannot be easily scaled to assess LRMs' reasoning capabilities over extended contexts. As modern LRMs increasingly support longer inputs, rigorous evaluation of their performance on lengthy, complex reasoning tasks becomes essential. Second,
Equal Contribution
Corresponding author

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of our work with prior benchmarks on graph algorithm problems.
Work
Graph Size (by nodes)
Reasoning Tuxonomy
LRMs' Evaluation
Real-worrd Data
NLGraph Wang et
2023
5-35
X
X
GPT4Grpp
1200 et mi
2025
10:20
x
GraphQA
Phemi
5-20
X
LLMHDy
Ziank 01
A12hb
5-20
X
X
GraphInstuu
[Lio el 3.
20746
5:35
Node, edge, graph level P and NP
X
X
GraphAArea
[ing
4-50
VisionGraph
GinCore Yuahl et
8-30
Graph reasoning and graph understanding Node, odge, graph level
X
GraphOmim
5-30
X
Ours
8-160
Enumeration, Exploration, Intuition
they exhibit inadequate challenge levels: Current benchmarks are no longer sufficiently difficult for LRMs (e.g.. GPT-5 achieving 94.3% on AIME-2025), yet creating more challenging variants requires non-trivial human effort in problem redesign. Third, their answers are not standardized and therefore hard to verify programmatically: In mathematical problems, a single solution can be expressed $. 0.333, or 3 and in code generation, model may pass functional tests while harboring latent logic flaws that are difficult to catch without exhaustive test suites.
These collective limitations motivate a pivotal research question: Can gather family of reasoning tasks that address the concerns above to form a more rigorous benchmarking suite for LRMs?
In this work, posit that graph algorithm problems (Wang et al. 2025b Peng et al. 2025 Zhang
ct al. 2024a Chen et al. 2024a Luo et al.) 2024 Zhang et al. 2025) represent a superior and highly promising choice. They furnish several distinctive advantages: (1) Effective Long-Conteex Input Describing a graph typically requires listing nodes and edges, producing lengthy inputs whose solutions cannot be directly extracted but must be derived through multi-step reasoning. These properties make graph algorithm problems naturally suited for evaluating long-context reasoning. For example, OpenAl employed the Graph (OeeAA 2025) dataset to benchmark the long-context capabilities of GPT-5. (2) Scalable Difficulty Level Control: Task complexity can be precisely modulated by scaling graph parameters like node size, often leading to quadratic or even exponential growth in difficulty. As evidenced in Table 33, model accuracy deteriorates sharply as graph size surpasses 120 nodes. (3) Standardized and Programmatic Evaluation: Outputs typically consist of integers explicit graph elements (e.g., nodes, edges, paths) that has no alternative representations, which permits standardized and programmatic verification.
Reasoning:
Furthermore, graph algorithm problems are both highly extensible and resistant to data contamina- tion, as minor structural perturbations can generate a vast number of new, valid instances at scale. Crucially, graph algorithms are foundational to numerous real-worlle upplications, including social networks (Ceccarello et al. 2024; Oettershagen et al. 2024), transportation systems (Ahmadian et al. 2024 and web mining (Chen et 2004ec] Miyauchi al., 2024 Pang et al. 2024). This practical relevance ensures that such benchmarks are not only rigorous but also grounded by real-world utility.
While several benchmarks have been proposed for evaluating LLMs on graph algorithm prob- lems (Wang et al. [2023] Zhang et al. 2024bb Tang et al., [2024] Yuan et al. 2024), they suffer from three critical limitations (see Table 1). First, prior works focus mainly on non-reasoning LLMs, leaving the behaviors of Ol-like LRMs largely unexplored. Second, their graph sizes are capped 50 nodes, leaving the advantage of scalable difficulty level control unexploited. Third, their task categorizations are often based on ad-hoc criteria such as local vs. global, graph understanding vs. graph reasoning, or vs. NP, rather than grounded in algorithmic design principles that better capture distinct and practically relevant reasoning paradigms.
To address these gaps, we propose GRALGOBENNH, a new benchmark for evaluating LRMs on graph algorithm problems. Figure I presents an overview of our benchmark, which consists of:
Systematic Dataset Construction: We categorize problems into three Categories-Fnumeee Exploration, and Intuition-call containing subproblems with different difficulty levels to probe distinct reasoning capacities. Our dataset comprises 2,700 graphs sampled directly from diverse real-world networks, ranging from 8 to 160 nodes across six scales, which increases diversity and mitigates data contamination risks.
We evaluate not only non-reasoning models but also reasoning models (c.g., Oiklike LRMs). Multiple metrics are adopted, including Pass@k, Cons@k k, Z-score, and outcome efficiency, enabling multi-faceted analysis.
@ Comprehensive Evaluation:
2

---

Published as a conference paper at ICLR 2026
Stage I: Datosst Construction
Stage
World Scanario
liee
RQ LRMs excel ot contect reasening! / memory?
Inference in Long contexts
when solving graph algorithm problems??
RQ2: overthisking
4 0z
"Bu""
Acehmel
Strea
Concolle
Prograc
Lowe
Evalatt
Tasks
Grophd
Reaporue
Enumeration
Poo Segras
Sampling Netheds
061
Enror Andlysis
Algertthm Selection
Algrrtth Executtion
Output Quality
LAMA
Seyventation
Algnntin
Expleration
Datarce-
Groph Type
Alynttte
Wensing Elrear
tyreentii
Zef onfmrnation
Gruph Marsor
Offic oney
LLM
Benget
1
Section 1 [IA]
Seymentstiens
Section 3 [SM)
LAMAl
Parsyroph
Andysia
LUM.
Dataset Construction Pipaline
Reasoning Models
Non- Reasoning Models
VS.
C
DeepSesk-ftt
Goval
Oper
Ligh-21
Quecn
Deepbedk-15
Figure
Benchmark overview.
Novel Research Questions: We systematically investigate: (1) Do LRMs excel at long- reasoning (Section 3.1 (2) What leads to over-thinking of LRMs when solving graph algorithm
problems (Section 3.2
Our experiments reveal two key findings. First, by evaluating LRMs graphs with varying node sizes as well as on fixed graphs with increasingly verbose textual descriptions, we observe a consistent performance decline as context length grows-for instance, most models achieve less than 50% accuracy once the graph size surpasses 120 nodes. This demonstrates that LRMs are particularly weak at long-context reasoning. Through detailed error analysis, identify three primary causes: frequent step-by-step execution errors, poor memory capability, and redundant reasoning patterns. Second, by analyzing how efficiently models reach the correct answer together with the frequency and effectiveness of seff-verification, we find that LRMs engage in extensive yet largely ineffective self-verification, which emerges as the main driver of over-thinking
2 BENCHMARK CONSTRUCTION
Figure illustrates the composition and structure of our dataset. Section 2. taxonomy, followed by task design in Section 2.2 and graph collection in Section 2.3
introduces the reasoning
2.1 GRAPHI REASONING TAXONOMY
Graph algorithm problems encompass diverse reasoning paradigms, providing a comprehensive framework to evaluate LRMss reasoning capabilities across multiple dimensions. Unlike prior approaches that categorize problems based on difficulty levels or by local versus global scopes (Luo) al. 2024, Tang et al., 20244) Yuan et al.) 2024 Xu et al.) (0025.. we propose a taxonomy grounded in the algorithmic nature of reasoning, closely aligned with the major algorithmic design families in Introduction to Algorithms (CLRS) (Cormen et al. 2022). Specifically, graph algorithm problems can be systematically divided into three fundamental classes: Enume cntumeration intion, Explorate maraiiion ion, and Intuition Each class corresponds directly to canonical algorithmic design paradigm in CLRS:
Enumeration (brute-force algorithms): Problems in this category align with the brute- force paradigm in CLRS. They require LRMs systematically generate all possible solu- tions or elements within a set. The canonical example in graph algorithms is brute-force enumeration of subgraphs paths. Beyond graph problems, enumeration manifests in do- mains like mathematics, where LRMs need to enumerate all permutations in a combinatorial problem or all cases in probability calculation.
3

---

Published as a conference paper at ICLR 2026
Exploration (search algorithms): This category corresponds to the search paradigm in CLRS, requiring traversal of a state space with potential backtracking. LRMs must explore multiple paths and recover from dead-ends. Typical graph examples include depth-first search and breadth-first search. Beyond graphs, it appears in tasks such as Sudoku or N-Queens, where candidate moves tried, conflicts detected, and backtracking applied.
Intuition (greedy algorithms): This category corresponds to the greedy paradigm in CLRS, where locally optimal choices made to efficiently approximate or eventually reach global optimum. It tests LRMs' ability to exploit subtle problem-specifie signals for efficient decisions. Representative graph examples include Dijkstra's and Kruskal's algorithms; outside graphs, a classic case is Huffman coding.
Importantly, all three paradigms collectively test complementary reasoning abilities of LRMs: enu- meration probes systematic coverage of a search space, exploration evaluates multi-path search and backtracking, and intuition assesses intuitive and efficient decision making. Beyond these, all graph problems inherently test memory (remembering the graph structure). logical reasoning (deriving consequences from premises, e.g., inferring the existence of cycles), and structural reasoning (rea- soning about relationships among nodes and edges). Owing to this diversity of reasoning paradigms and general cognitive requirements, graph algorithm problems constitute a uniquely challenging and informative benchmark for evaluating the reasoning capabilities of LRMs.
2.2
TASK DESIGN
With the problem taxonomy established, the next challenge lies in classifying graph algorithm problems into these categories. It is important to emphasize that classification cannot be based solely on a single optimal algorithm for solving the problem, as a given problem can be approached using multiple algorithmic strategies. Moreover, we do not know which algorithmic approach an LRM is more likely to employ when tackling specific problem. For example, shortest path problems can be solved using brute-force methods (an Enume ion approach), DFS (an Exploration approach), or Dijkstra's 's algorithm (an Intuite on approach).
To address this, we collect a variety of graph algorithm problems and propose an LLM-as-judge ap- proach for determining the classification of each problem. Specifically, for each gaalem--omprisnng a graph description and a task description expressed natural language- we first generate 300 Erdós- Rényi (ER) graphs (Erdös et al. 1960) to replace the original graph description, creating diverse set of problem instances. We then prompt LRMs with these instances, obtain their responses, and use judge to assign reasoning category (dctailed prompts are provided in Appendix K.I). To validate these labels, three postgraduate students with competitive programming experience manually review subset of instances and reach almost identical judgments to Qwen-2.5-72B. Finally, we select 9 graph tasks in which the algorithms used by LRMs for reasoning are relatively unambiguous, thereby facilitating more straightforward classification. We present in Appendix H. the distribution of algorithms used by representative LRMs across different tasks, illustrating how each task aligns with our proposed reasoning taxonomy.
Qwcn-2.5-72B (Team] 2024 Yang et al. (024)
We now introduce the tasks within each reasoning taxonomy, along with the definition of each task. Based on the optimal time complexity of each task under the corresponding algorithm of the category. we classify the tasks into three levels: easy, medium, and hard. More specified task definitions and the time complexity of the optimal algorithm for each task are given in Appendix F.I
Enumeration: (1) Maximum Degree node (easy): Identify the node with the maximum degree a given undirected graph and output its degree. (2) Maximum Weight Tri angle (medium) : Given an undirected graph where each node is assigned weight, find triangle (a set of three nodes connected to each other) that has the maximum sum of node weights and output weight sum. (3) Maximum Cl Clique Problem (MCP, hard): Given an undirected graph, identify subgraph in which all nodes are pairwise connected, and the subgraph contains the maximum number of nodes. Then, output the size of the subgraph.
Exploration: (1) PathSum (easy): : Given an undirected tree where each edge is assigned a weight, output the number of paths from the root to the leaves for which the sum of the edge weights exceeds a given threshold 7. (2) Distance-k (medium): Given an undirected graph and a specific node v, find all other nodes that are within k-hops from v and output the number of qualified
4

---

Published as a conference paper at ICLR 2026
Enumeration
Exploration
Intuition
Maximum Degree
Distance-A
Maximum
recttd far radd mui somncction to other afrecte
aeteert,
coaltyy duttarse Se thrttn dtriet
indractedd repoeentiigg
You una Oie of indierted smihh rpresating Bans Statatteee atteerts
Atrectr acteork Lirrad avenae Gehhynore fumil
patwork Souller or locd.
pith
Comtrrecciin howe netwerk We Lil Gitari
Beael Iniond memornen and Civ Aer
14rdo R000 dirfticess Read Seadin Rocd
preohect other stratt, prow de the totall usent ontorsattinn fiem.
Pleas fad morimar S-otr the setwert ard potauut
Seass For Hhe straas i dickase 3 froe the streat Southarts
Figure 2: Illustrative problem description.
nodes. (3) Diameter (hard): Identify the longest shortest path between any two nodes in given undirected graph and output the length of this path.
Intuition: (1) Maximum k-core (MKC, easy): Find a subgraph in an undirected graph where each node has a degree of at least and the subgraph contains the maximum number of nodes. Then, output the size of the subgraph. (2) Minimum Spanning Tree (MST, medi um) Given connected, undirected graph with edge weights, find a spanning tree that connects all nodes with the minimum possible total edge weight and output the total edge weight. (3) Di stance Thresho hooll d (hard): Given an undirected graph with positive edge weights, find the node that can reach the smallest number of other nodes via shortest paths of length most a threshold, and output that node.
2.3 GRAPH COLLECTION
To measure the semantic understanding capabilities of LRMs and further avoid data contam- ination, we construct graphs and graph problems using nodes and edges with real-world se- mantics. We collect graph problems from the following five scenarios: (1) DBLP (Ley, 2002): An academic collaboration network consisting of over 1.3 million nodes (au- thors) and 5 million edges (collaborations). (2) Street Network (Boeing, 2025): A collec- tion of city transportation networks worldwide, where nodes represent streets and edges repre- sent intersections between two streets. We use the transportation networks of London (con- taining 36,281 nodes and 83,662 edges, for Distance-k), Sydney (containing 30,291 nodes and 69,126 edges, for Minimum Spanning Tree), Dublin (containing 3,962 nodes and 7,000 edges, for Maximum Degree node), and Rome (containing 14,719 nodes and 28,087 edges, for Maximum k-core). (3) OpenFlight (Open- Flights): An airport network consisting of 3,390 nodes (airports) and 19,166 edges (flight routes) weighted by geographical distance. This graph is assigned to the Distance Threshold task. (4)
This graph is used for the PathSum task.
Table 2: Average graph statistics across groups V: Avg. number of nodes; E: Avg. number of edges; D: Avg. density; X: Avg. edge connectivity.
Group
V
E
D
Level-1
11.55
18.52
0.31
1.23
Level-2
22.49
44.51
0.19
1.02
Level-3
39.60
90.09
0.12
0.87
Level-4
61.69
157.60
0.08
0.83
Level-5
97.83
268.50
0.06
0.82
Level-6 138.95
407.94
0.04
0.81
Wikipedia (Yin et al., 2017): web graph of Wikipedia hyperlinks collected in September 2011, containing 1,791,489 nodes (representing articles) and 28,511,800 edges (representing hyperlinks between articles). This graph is used for the Maximum Weight Triangle and Maximum Clique Problem tasks. (5) DBpedia (Bizer et al. 2009): A knowledge graph subset with over I million nodes (entities) and 7 million edges (relationships). This graph is assigned to Diameter task.
For each task, employ random walk or BFS sampling methods to extract subgraphs of varying sizes from the corresponding real-world graphs. These subgraph sizes are divided into six categories: level-1 (8-15 nodes), level-2 (16-30 nodes), level-3 (31-50 nodes), level-4 (51-80 nodes), level-5 (81-120 nodes), and level-6 (121-160 nodes). In total, the dataset comprises 2,700 problem instances, with each size category containing 50 samples. Examples of problem descriptions for selected tasks while detailed statistics are provided in Table
are presented in Figure 2
3 EVALUATION
In this section, we evaluate the capabilities of LRMs in solving graph algorithm problems and analyze the limitations in their reasoning. Our evaluation focuses two research questions: RQ1: Do LRMs
5

---

Published as a conference paper at ICLR 2026
Table We evaluate models on six graph scales (Level-1 to Level-6). For each size, performance is measured on three task taxonomies: Enumeration, Exploration, and Intuition. The evaluation metrics are cons @ k (c@k) k) and pass@k (p@k), k). We also report per-scale averages across tasks. Results for Level-1 and Level-2 are presented in the Appendix H.2 For each model scale, the best results are highlighted in bold, while the second-best results are underlined.
Level-3 (31-50 nodes)
Level-4 (S1-80 nodes)
Models
Enumeration
Exploration
Intuition
Avg.
Enumeration
Exploration
Intuition
Avg.
cBk
p3k
c8k
płk
c0k
p8k
płk
c@k
p@k
c8k
p8k
c0k
p8k c33 p@k
Skywork-ORI -orook--R1--B---
-7B-Preview
0.58
0.10
0.00
0.03 0.08
0.32
0.44
0.06
0.30
0.01
0.06 0.04 0.27
Light-R1-7B-DS
0.11
0.53
0.07
0.35
0.01
0.08 0.06 0.32
0.08
0.34
0.07
0.30
0.00 0.03 0.05 0.22
Distill-Que Qwen-7B
0.13
0.59
0.05
0.39
0.01
0.13 0.06 0.37
0..12
0.41
0.07
0.39
0.00
0.07 0.06 0.29
Qwen2.5-7B
0.11
0.39
0.10
0.21
0.00
0.03 0.07
0.21
0.09
0.36
0.11
0.29
0.03 0.07 0.08 0.24
OpenThinker-7B
0.19
0.61
0.07
0.43
0.01 0.13 0.09
0.39
0.03
0.41
0.04
0.32
0.01 0.03 0.03 0,25
0.17
0.51
0.11
0.49
0.01
0.10 0.10
0.37
0.12
0.48
0.09
0.34
0.00
0.03 0.07 0,28
Qwen3-8B
0.79
0.99
0.69
0.93
0.40
0.69
0.63
0.87
0.:44
0.83
0.28
0.63
0.09
0.26 0.27 0.58
GPT-OSS-208
0.59
0.78
00.50
0.67
0.39
0.59
0:49
0.68
|0.43
0.54
0.40
0.50
0.31
0.43 0.38 0.49
Light-R1-S22
0.71
0.97
0.64
0.94
0.35
0.59
0.57
0.83
00.43
0.87
0.38
0.76
0.06
0.31 0.29 0.65
Skywork-OR1-32B
0.87
0.99
0.77
0.99
0.51
0.75 0.72
0.91
0.54
0.87
0.51
0.84
0.12
0.42 0.39 0,71
DistillQQeen-32B
0.63
0.89
0,46
0.81
0.21
0.51 0.43
0.74
0.42
0.80
0.23
0.60
0.03
0.31 0.23 0.57
Qwen2.5-32B
0.25
0.61
0.10
0.43
0.04
0.19 0.13 0.41
0.16
0.49
0.06
0.31
0.04
0.13 0.09 0.31
Open//hinker-228
0.97
0.56
0.30
0.57 0.54
0.82
0.31
0.11
0.30 0.29 0.64
QWQ-32B
0.69
0.88
0.69
0.93
0.53
0.73 0.69
0.88
0.68
0.96
0.53
0.84
0.30
0.58
0,50 0.79
Qwen3-32B
0.79
0.99
0.69
0.93
0.40
0.69
0.63
0.87
0.52
0.89
0.51
0.87
0.26
0.59
0.43 0.78
Qwen3-32B-non nothhinkin
0.33
0.69
0.35
0.81
0.02
0.21
0.23
0.57
0.20
0.63
0.16
0.57
0.02
0.16
0.13 0.45
IJama 3.3-705
0.10
0.36
0.13
0.39
0.01
0.04 0.08
0,26
0.00
0.00
0.01
0.16
GPT-OSS-120B
0.76
0.82
0.78
0.88
0.68
0.92 0.74
0.87
0.56
0.74
0.56
0.76
0.52
0.75
0.55 0.75
Qwen3-2380 -a-33-33B---8 22----228-2----- 4228-ihin
0.98
1.00
0.96
1.00
0.96
0.99
0.97
1.00
0.88
0.98
0.89
0.99
0.81
0.92 0.86 0.96
Qwen3-235B-A22 2-----3---BBsBsssus-s
0.91
0.98
0.87
0.97
0.80 0.97 0.86
0.97
0.77
0.97
0.79
0.98
0.66 0.89 0.74 0.95
Level-5 (81-120 nodes)
Level-6 (121-160 nodes)
Models
Enumeration
Exploration
Intuition
Avg.
|Enumeration
Exploration
Intuition
Avg.
c#KK
p8
cBk
pilk
cikk p8k cax pikk
cctk
p8x
CHK
pilk
c0k p8k c& pfk
GPT-OSS-20B
0.51
0.68
0.18
0.33
0.16 0.27 0.28
0.43
0.28
0.48
0.10
0.14
0.04 0.09 0.14 0.24
Light-RI-32B
0.80
0.80
0.45
0.45
0.01 0.07 0.42 0.44
0.22
0.68
0.05
0.23
0.00
0.01 0.09 0.31
Kkywork-OR1-322
0.67
0.67
0.51
0.51
0.00
0.00 0.39
0.39
0.10
0.47
0.03
0.23
0.00
0.00 0.04 0.24
Distil-Qwen-32B
0.45
0.83
0.09
0.37
0.00
0.03 0.18 0.41
0.26
0.77
0.07
0,31
0.00
0.03 0.11 0.37
Qwen2.5-32B
0.15
0.53
0.05
0.22
0.02
0.11 0.07 0.29
0.21
0.48
0.03
0.19
0.01
0.01 0.08 0,23
OpenThinker-32B
0.37
0.76
0.14
0.45
0.02
0.21 0.18 0.47
0.27
0.68
0.07
0.33
0.00
0.02 0.11 0,34
QWQ-32B
0.61
0.95
0.25
0.63
0.09
0.25 0.32
0.61
0.47
0.87
0.13
0.40
0.09
0.21 0,23 0.49
Qwen3-32B
0.21
0.09
0.25
0.59
0.09
0.09
0.19
0.47
0.15
0.61
0.07
0.28
0.01
0.07
0.08
0.32
0.13
0.49
0.07
0.23
0.01
0.07 0.07 0.27
Llama-3,3-700
0.07
0.21
0.01
0.11
0.00
0.02 0.03
0,11
0.02
0.22
0.00
0.07
0.00
0.00 0.01 0,10
GPT-OSS-1208
0,51
0.67
0.41
0,51
0.22
0.28
0.38
0.49
0.37
0.54
0.19
0.33
0.11
0.16
0.22 0.34
0.86
0.96
0.52
0.82
0.37
0.49
0.58
0.76
0.80
0.93
0.28
0.52
0.26
0.36
0.45 0.50
Owen3-235B-A2000 Instruct
0.76
0.92
0.41
0.68
0.26
0.38
0.48
0.66
0..51
0.79
0.28
0.59
0.21
0.26
0.33
0.55
GPTS-mini
0.66
0.72
0.53
0.63
0.02
0.03
0.40
0.46
0.77
0.86
0.36
0.47
0.10
0.18
0.41 0.50
Deepseck-V2 V3
0,56
0.71
0.34
0.54
0.00
0.00
0.30
0.42
0.40
0.54
0.22
0.32
0.00
0.00
0.21
0.29
Deepsock-R1
0.82
0.82
0.69
0.69
0.15
0.15
0.55
0.55
0.79
0.79
0.50
0.50
0.05
0.05
0.45
0.45
Gemini-2.5-pro
0.73
0.90
0.46
0.63
0.17
0.30
0.45
0.61
0.63
0.86
0.37
0.54
0.08
0.1
0.36
0.50
excel at long-contex, reasoning? RQ2: What leads to over-thinking of LRMs when solving graph algorithm problems? Details of the evaluation setup are provided in Appendix
3.1 EXPL.RING LRMs' CONG-CONTEXT REASONING ABILITY (RQ1)
With the rapid extension of context windows in modern LRMs, a central question whether these models can truly perform understanding and reasoning over long contexts. Graph algorithm problems provide an ideal testbed: they allow scalable control over input length, and their solutions cannot be trivially extracted from the problem statement. To systematically explore LRMs' long-context reasoning ability, we design several experiments. First, we vary the number of graph nodes, and alternatively fix the graph structure while extending textual descriptions of nodes, to observe performance changes as input length increases. Second, we collect and analyze erroncous responses to identify the underlying causes of degraded performance in long-context reasoning.

---

Published as a conference paper at ICLR 2026
BwBB
-
Qwen3-233BB
Deepseek-R R1
GPFoss-20b
GPT- 120b
Trisngle Sum
Distanec
Moximum K-oore
Pasviik Accuracy (%)
100
100
100
80
80
80
40
20
20
4k
8k
16k
64x
4%
8k
16k
64k
8k
1ok
32k
64%
Context Length
Context Longth
Context Longth
Figure 3: Models pass@k performance across different context length.
Evaluation by Varying Problem Length. We examine model performance under different input lengths through two complementary settings. First, we increase problem length by scaling the number of nodes and edges within the graphs, and evaluate the resulting performance across varying graph sizes; average accuracy for each reasoning taxonomy is reported in Table Second, decouple the effect of increased task difficulty from larger graph structures, we fix the graph topology and vary token length by modifying the textual descriptions nodes. Specifically, we select three graph Dusks-TRIANGLAA GLE SUM, DISTANCEK, and MAXIMUM K-CORE and construct 50 graphs with 80 nodes and 200 edges each. By adjusting node name length, we generate five datasets with average token lengths of 4k, 8k, 16k, 32k, and 64k. We then evaluate five representative models-Qweell -wen3-32BB @wen3-235B-Thinkinn GPT-oss-20B, GPT-oss- 120B, and MaaaSeek-Rl-uneee these conditions, with results summarized in Figure K
Error Analysis. We examine the types of errors that LRMs commonly make when solving graph algorithm problems. Our methodology begins with establishing taxonomy of error categories (see Appendix H.3), followed by the development of an automated error detection pipeline. Specifically, to support annotation and improve labeling accuracy, paragraphs. Specifically, we collect LRMs' responses with incorrect final answers, segment them by "nn),," and index each paragraph as "(i)." where i is the segment ID. We then to merge paragraphs into sections by summarizing each response into tuples of (start-index, end- index, summary), which define the regrouped structure. Next, 03-mini annotates each section with one or more error categories, from which we compute the error-type distribution. In addition, three postgraduate students with competitive programming experience independently review a subset of annotations and confirm their consistency with the L.-M-based labels. Detailed prompts and the full transformation process are provided in Appendix K. for Qwen3-322 and its non-reasoning counterpart across three taxonomies, with results for other models and detailed case studies in Appendices
reorganize LRM responses into coherent
gwen-2.5-725
and K.2 Figure presents the error distribution
and K.3
① LRMs cannot effectively handle long-context reasoning. Our two complementary experiments consistently reveal the limitations LRMs in processing extended text inputs. As shown Table model accuracy decreases sharply graph size grows. For example, Owen3-32 323 achieves 87. 87.0% pass@k accuracy on graphs with 31-50 nodes, but drops to 59.0% with 81-120 nodes and further to 47.0% beyond 121-160 nodes. Similar drops are observed across all evaluated models. While this decline could be attributed to increased structural complexity, additional experiments disentangle structural difficulty from textual length. By fixing the graph structure while gradually lengthening node descriptions, we observe a comparable pattern: on the TRIANGLE SUM task, DeepSeek-Be R1 achieves 100.0% at 4k tokens but only 22.0% at 64k tokens, while GPT oos-osslll 120B falls from 68.0% to 10.0%. Taken together, these results point to common bottleneck: as context length srreasses-wethhe from more graph nodes or longer textual descriptions LRMs fail to maintain stable reasoning traces, resulting in significant performance degradation.
LRMs' long-context reasoning is constrained by three key bottlenecks: coarse step-by- step execution, weak memory capability, and excessive redundancy. First, LRMs often fail in algorithm execution even after selecting the correct strategy, as Algorithm Execution Errors (ABE) far exceed Algorithm Selection Errors (ASE)-fo for example, shown in Figure Qwen 3-2BB records AEE rates of 35.3% and 48.6% versus ASE rates of only 5.5% and 5.7% in Exploration and Innuition, respectively. The most frequent issues State Update Errors and Omissions, indicating that models grasp high-level plans but falter on procedural details. Second, LRMs struggle to maintain an accurate representation of graph structure, leading to Graph Memorization Errors (GME): while non-reasoning
7

---

Published as a conference paper at ICLR 2026
Major
OKE--Oappi Quality Brse
SClEstat upiaic
saboparal alpettion
vodunaadyy Explocation
Enumeration
Intuition
Fi
Mine
Figure 4: Error type distributions reasoning taxonomies for Qwen3-32B (top) and its non- reasoning variant Qwen3-32BBBB -no----n------iiiinggg (boltom).
variants reach error rates up 42.6%, reasoning models such as 3 -3BB still exhibit more than 21% GME in Exploration and Intuition. Finally, reasoning models frequently introduce excessive redundancy- for instance, Owen3-325 shows 37.7% redundancy errors in Exploration where verbose and repetitive steps inflate reasoning traces without improving accuracy, and sometimes even cause additional confusion. Importantly, such redundancy reflects form over-thinking, which we will further analyze in the next section.
Both reasoning and non-reasoning models achieve the best performance on Enumeration tasks, followed by Exploration, and the worst Intuition. This observation can be explained from two perspectives. First, within each node-size level, almost all models follow the pattern Enumeration Exploration Intuition. For instance, shown Table at Level-3, GPT-OSS- 20B obtains cons@i scores of 0.59, 0.50, and 0.39 on Enumeration, Exploration, and Intuition, respectively. Second, considering how large graph each model handle, find that some remain more robust on Enumeration. For example, at Level-6, GPT-5-mini reaches 0)77 cons @k accuracy on Enumeration, but drops below 0.4 on Exploration and only about 0.1 on Intuition. This indicates that LRMs are relatively competent at systematic, enumeration- based reasoning but struggle substantially with iouuitiondrivend reasoning. To further support this finding, we provide normalized analysis using the Z-score metric in Appendix H.2
3.2 EXPLORING UNDERLYING MECHANISMS OF LRMs' TVER-THINKING (RQ2)
In eтror analysis, we observe that reasoning models often produce substantial redundancy when solving graph problems, with responses containing unnecessary information. This phenomenon is closely related to the over-thinking behavior characteristic of LRMss, where the model inefficiently expends resources by engaging in excessive verification redundant checks even after reaching final answer (Lu et al.) 2025 Chen et al. 2024d). Such over-thinking not only generates superfluous tokens, but also leads to wasted computational resources and longer response times. In this section, investigate LRMs over-thinking phenomenon in graph algorithm problem solving from two perspectives; post-answer generation and selfiverriiicatio.
Response Partitioning via High-Entrone Tokens. To facilitate subsequent evaluation, we parti- tion LRM- -eM-eeeeettedd responses into segments. Our partitioning approach is guided by token-level generation entropy. metric that quantifies the model's uncertainty at each step of the generation process (See Appendix F3 for more details). High entropy values often coincide with moments of self-verification strategy-shifting which may indicate over-thinking (Wang et al. 2025a). By
8

---

Published as a conference paper at ICLR 2026
Bilective Raio
6.2 6:12
Graph Tinks (Average)
0.9
Math Troks
043
0.88
0.22
8:77
0.6
0.77
Destin Eicetwence
0.7
6.50 0.0 0u?
Labe
0.4
092
642
80
082
0.7
0.4
057
0.2
M.2
MadD
MKC MCP
Distmne Disaecchellll Thechhld
Tringl
Paiksinn
MST
Dianver
Ditercof
5YAMP MP
SAT AlMO AtME
pooplaadin Mathiron Taa
AIMO Alc
0.0
Patkfan
46T
MRC
Diammer
MFT
Disumer
Distanee Thosfoold
Thingl
AIM ainnss
(a) Outcome efficiency
(b) Proportion of reasoning behaviors
Figure 5: Overthinking analysis of QWQ-32B (See Appendix H.S for more results).
computing this token-level entropy across reasoning traces and visualizing it with a word cloud (Figure T9 in Appendix H.4), we find that tokens such as "wait". "bul", and "so" consistently exhibit high entropy. This observation aligns with prior studies (Li ct al. 2025a Lu et al. (025), which have identified these tokens as typical triggers of over-thinking. Therefore, we adopt these tokens as special partition markers. Formally, let response be a token sequence T = (W1, W2,...., Wm). If special tokens appear at positions i1, 12.2...., bys
then T is partitioned into n + consecutive segments:
T (w1. W;,-1) (Wi++1... W12-1),
(wi,+l..... wm)
Post-Answer Generation. One possible source of over-thinking is post-answer generation. i.c. the model keeps producing tokens even after outputting a correct answer (Sui et al. 2025 Chen et al.
2024d 2025). To quantify this behavior, we adopt the outcome efficiency metric (Chen al. 2024d] the fraction of tokens generated up to the first correct answer relative to the full response length:
N
-o=
T
where N is the number of responses containing the correct answer, Ti the total response length, and 7. the tokens up to the first correct answer. We compute T. by prompting Qwen2. 5-72B with the original problem, the segmented LRM response, and the ground-truth answer, asking it to locate the first correct segment (Prompts can be seen in Appendix K.I. Outcome efficiency of QWQ-32B on graph and math problems is shown in 5
Self- Verification. Another relevant behavior is self-verification, where LRMs attempt to re-check earlier reasoning or conclusions. To analyze this process, we again use Owen2. 5-72B: for each segment i, the model classifies it (given all prior segments) as self-verification, strutegy-shifl, other. labeled as self-verification, the segment is further judged as effective when correctly identifies prior errors. Detailed prompts are listed in Appendix K.I and Figure 5 b) summarizes the distribution of segment types and their effectiveness.
① Frequent yet ineffective seff-verification is primary driver of over-thinking in LRMs when solving graph algorithm problems. As shown in Figure 5 outcome efficiency (a) remains consistently high on graph tasks Laske-above 0.88 in all cases and is higher than math tasks. This indicates that LRMs seldom continue generating tokens long after reaching the correct answer, suggesting that post-answer generation is not the main source of over-thinking in graph reasoning. In contrast, panel (b) shows that self-verification occupies a substantial fraction of reasoning traces across different tasks, yet its effectiveness strikingly low: in most cases fewer than 30% of self- verification attempts successfully detect prior errors. Instead, the majority of these segments simply restate earlier steps or add irrelevant content, inflating response length without improving correctness. These observations together point to frequent but ineffective eeff-veriicattin as the main mechanism underlying the over-thinking phenomenon LRMs when solving graph algorithm problems.
3.3 DISCUSSION
We further discuss aspects: (1) the potential benefits of having LRMs generate code and invoke external tools to solve graph algorithm problems, and (2) the extent to which the insights derived from our benchmark generalize beyond the specific tasks and settings considered in this work.
Solving Graph Algorithms Problems by External Tools. To better understand the impact of tool usage on benchmark, conduct an additional experiment where models are explicitly

---

Published as a conference paper at ICLR 2026
Table 4: Model performance (pass@k/ cons@k (%) with and without code-based tool usage.
Level-5 (81-120 nodes)
Level-6 (121-160 nodes)
Task
Metric
Qwen3-322 B-BB
Gemini-2.. 2.5-p
GPT5-mini
Qwen3-32B
Gemini-2.5-
GPT5-min
Triangle
Base
76.0 66.6
90.0 80.0
56.7 / 50.0
60.0 / 42.2
86.7 / 83.3
86.7 / 70.0
Code
96.0 / 93.3
94.0 92.0
99.0/ / 99.0
92.0 / 88.0
90.0 / 88.0
99.0 99.0
Base
40.0 20.0
43.3 / 30.0
60.0 53.3
36.0/ 10.0
43.3 / 33.3
26.7 / 13.3
DistanceK
Code
98.0 / 96.0
100.0 100.0
100.0 / 100.0
96.7 / 96.7
100.0 / 100.0
100.0 100.0
Base Code
0/0 97.3 94.7
16.6/3
3.3/ 0
0/0 O
0/0
0/0
MST
98.7 98.0
100.0 100.0
88.0 / 84.0
92.0/ / 90.0
100.0 100.0
Speaunddss 0:50
Sparman's - 0.60
Spearmarks p p-7.7
LongDenchhp Score
Shecki-215
Owes3-3338
Qwee
GPQQ Score
Poppocdd
P3
GPT-OS8 Deepceoic
MMLUU- Pro
24 10
14
2W0 32B
2
Delll-Qwer-10
Diaill Qwen 528
GraAlgobench Soore
GraAlgebench Sourc
GraAlgobench Soore
Figure 6: Model-wise correlation with external benchmarks.
instructed to solve problems by writing code and then using code-execution tool (examples are given in appendix G). Concretely, we compare three LRMs of different strengths (Qwen3-32B, Gemini-2.55pm GPT5-mini) on three representative tasks (Triangle. Distancek, MST), at graph size level-5 and level-6. We report pass@k k and cons cons@k with and without tool calls (See Table 4). Across models and tasks, enabling code and tool usage consistently and substantially improves performance,
on the most challenging instances. However, delegating the hardest parts of the problem-sun such as graph memorization and step-by-step algorithmic execution- to external tools no longer directly evaluates the model's s intrinsic reasoning ability. For this reason, we do not adopt the code-generation setting our primary evaluation protocol.
Conclusion Generalization. To verify that our findings generalize beyond graph-specific scenarios, conduct two additional experiments: (1) measure model-wisg correlations between GraAlgoB ench and established benchmarks spanning mang-conext and general reasoning LLongeench-22 (Bai
let al. 2025), GPQA (Rein al. 2024), and MMLU-Pro (Wang al. 2024) (Figure 6 and (2)
vary the graph serialization format (edge lists, adjacency lists, Markdown tables, and numeric node IDs; examples in Appendix (G) and compare performance across formats (Table 6 in Appendix [I]. According to standard guidelines for interpreting correlation coefficients (Mukaka 2012). values in the range 0.50-0.79 indicate moderate to strong association. The observed correlations between GraAlgoBench and GPQA (p 0.77) and between GraAlgoBench and LongBench-v2 (p 0.60) therefore suggest that the complex reasoning skills assessed by our benchmark align closely with those underlying high-level general reasoning and long- long-context understanding. In addition, across graph sizes, models achieve similar performance under all four representation formats, indicating that performance is largely independent of input format and primarily reflects intrinsic reasoning ability rather than superficial properties of the graph encoding.
4 CONCLUSION
We introduced GRALGOBENCI,, a benchmark that leverages graph algorithm problems to probe reasoning in LRMs with effective long-context evaluation, fine-grained difficulty control, and pro- grammatic assessment. Our results highlight two central limitations: accuracy drops substantially context length grows, and tver-thinking emerges from frequent yet ineffective self-verification. By uncovering these challenges, GRALGOBENCH establishes graph algorithms as a practical and rigorous foundation for advancing the robustness and efficiency of future reasoning models.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work is supported by NSFC Grant No.62572418.
REFERENCES
Sandhini Agarwal, Lama Ahmad, Jason Ai, Sam Altman, Andy Applebaum, Edwin Arbus, Rahul K Arora, Yu Bai, Bowen Baker, Haiming Bao, et al. gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508. 10925, 2025.
Sara Ahmadian, Sreenivas Gollapudi, Gregory Hutchins, Kostas Kollias, and Xizhi Tan. Extracting small subgraphs in road networks. In Proceedings of the ACM Web Conference 2024, pp. 493-502, 2024.
Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, et al. Longbench v2: Towards deeper understanding and reasoning on realistic long-context multitasks. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3639-3664, 2025.
Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak, and Sebastian Hellmann. Dbpedia-a crystallization point for the web of data. Journal of web semantics, 7(3):154 16655,, 2009.
Geoff Boeing. Modeling and analyzing urban networks and amenities with osmnx. Geographical Analysis, 2025.
Mattco Ceccarello, Andrea Pietracaprina, and Geppino Pucci. Fast and accurate fair k-center clustering doubling metries. In Proceedings of the ACM Web Conference 2024, pp. 756-767, 2024.
Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An cnstruction-follovine language model for graph computational problems. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 353-364, 2024a.
Nuo Chen, Zinan Zheng, Ning Wu, Ming Gong, Dongmei Zhang, and Jia Li. Breaking language barriers in multilingual mathematical reasoning: Insights and observations. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 7001-7016, 2024b.
Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning era: A survey of long chain-of- thought for reasoning large language models. arXiv preprint arXiv:2503.099 095667 2025.
Xiaolong Chen, Yifan Song, and Jing Tang. Link recommendation to augment influence diffusion with provable guarantees. In Proceedings of the ACM Web Conference 2024, pp. 2509-2518, 2024c.
Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu, Mengfei Zhou, Zhuosheng Zhang, et al. Do not think that much for 2+ 3=? on the overthinking of ol-like 1lms. arXiv preprint arXiv:2412.211877 2024d.
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.0626/ 2025.
Thomas H Cormen, Charles E Leiserson. Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
Jianbo Dai, Jianqiao Lu, Yunlong Feng, Guangtao Zeng, Rongju Ruan, Ming Cheng, Dong Huang, Haochen Tan, and Zhijiang Guo. Mhpp: Exploring the capabilities and limitations of language models beyond basic code generation. arXiv preprint arXiv:2405.17 /430, 2024.
11

---

Published as a conference paper at ICLR 2026
Guanting Dong, Yifei Chen, Xiaoxi Li, Jiajie Jin, Hongjin Qian, Yutao Zhu, Hangyu Mao, Guorui Zhou, Zhicheng Dou, and Ji-Rong Wen. Tool-star: Empowering lim-brained multi-too reasoner via reinforcement learning. arXiv preprint arXiv:2505.16410, 2025.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv e-prinis, pp. arXiv-2407, 2024.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:23 2023.
Jiazhan Feng, Shijue Huang, Xingwei Qu, Ge Zhang, Yujia Qin, Baoquan Zhong, Chengquan Jiang, Jinxin Chi, and Wanjun Zhong. Retool: Reinforcement learning for strategic tool use in llms. arXiv preprint arXiv:2504. 1536, 2025.
Elliot Glazer, Ege Erdil, Tamay Besiroglu, Diego Chicharro, Evan Chen, Alex Gunning, Caroline Falk- man Olsson, StrannStanssls Denain, Anson Ho, Emily de Oliveira Santos, et al. Frontiermath: A benchmark for evaluating advanced mathematical reasoning ai. arXiv preprini arXiv:241..04877 2024.
Aryan Gulati, Brando Miranda, Eric Chen, Emily Xia, Kai Fronsdal, Bruno de Moraes Dumont, and Sanmi Koyejo. Putnam-axiom: A functional & static benchmark for measuring higher level mathematical reasoning in llms. In Forty-second International Conference on Machine Learning, 2024.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseck-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprins arXiv:2501.12245 2025.
Jaayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv preprint arXiv:2305. /5066, 2023.
Chaoqun He, Renjie Luo. Yuzhuo Bai, Shengding Hu. Zhen Leng Thai, Junhao Shen, Jinyi Hu, Xu Han, Yujie Huang, Yuxiang Zhang, et al. Olympiadhench: A challenging benchmark for promoting agi with olympiad-level bilingual multimodal scientific problems. arXiv preprint arXiv:2402. 14008, 2024.
Jujie He, Jiacai Liu, Chris Yuhao Liu, Rui Yan, Chaojie Wang, Peng Cheng, Xiaoyu Zhang, Fuxiang Zhang, Jiacheng Xu, Wei Shen, et Skywork open reasoner technical report. arXiv preprint arXiv:2505.22312. 2025a.
Junda He, Jieke Shi, Terry Yue Zhuo, Christoph Treude, Jiamou Sun, Zhenchang Xing, Xiaoning Du, and David Lo. From code to courtroom: Llms as the new software judges. arXiv preprint arXiv:2503.0 02246, 2025b.
Kaixuan Huang, Jiacheng Guo, Zihao Li, Xiang Ji, Jiawei Ge, Wenzhe Li, Yingqing Guo, Tianle Cai, Hui Yuan, Runzhe Wang, et al. Math-perturb: Benchmarking Ilms' math reasoning abilities against hard perturbations. arXiv preprint arXiv:2502.0644 2025.
Zhen Huang, Zengzhi Wang. Shijie Xia, Xuefeng Li, Haoyang Zou, Ruijic Xu, Run-Ze Fan. Lyuman- shan Ye, Ethan Chern, Yixin Ye, et al. Olympicarena: Benchmarking multi-discipline cognitive reasoning for superintelligent ai. Advances in Neural Information Processing Systems, 37:19209 19253, 2024.
Michael Ley. The dblp computer science bibliography: Evolution, research issues, perspectives. In International symposium string processing and information retrieval, pp. 1-10. Springer, 2002.
Chengpeng Li, Mingfeng Xue, Zhenru Zhang, Jiaxi Yang, Beichen Zhang, Xiang Wang, Bowen Yu, Binyuan Hui, Junyang Lin, and Dayiheng Liu. Start: Self-taught reasoner with tools. arXiv preprint arXiv:2503. 2.X6v22503.04625. 2025a.
12

---

Published as a conference paper at ICLR 2026
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competitionn-evee code generation with alphacode. Science, 378(6624): 1002))):0192000000 1097, 2022.
Yunxin Li, Baotian Hu, Haoyuan Shi, Wei Wang. Longyue Wang. and Min Zhang. Visiongraph: Leveraging large multimodal models for graph theory problems in visual context. arXiv preprint arXiv:2405.04950. 2024.
Zhiyuan Li, Yi Chang, and Yuan Wu. Think-bench: Evaluating thinking efficiency and chain-of- thought quality of large reasoning models. arXiv preprint arXiv:2505.22113, 2025b.
Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark, and Yejin Choi. Zebralogic: On the scaling limits of ilms for logical reasoning. arXiv preprint arXiv:2502.01100, 2025.
Aixin Liu, Bei Feng. Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng. Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412. 194377 2024.
Ximing Lu, Seungju Han, David Acuna, Hyunwoo Kim, Jaehun Jung, Shrimai Prabhumoye, Niklas Muennighoff, Mostofa Patwary, Mohammad Shoeybi, Bryan Catanzaro, et al. Retro-search: Exploring untaken paths for deeper and efficient reasoning. arXiv preprint arXi::2504.04383, 2025.
Zihan Luo, Xiran Song, Hong Huang, Jianxun Lian, Chenhao Zhang, Jinqi Jiang, and Xing Xie. Graphinstruct: Empowering large language models with graph understanding and reasoning capability, arXiv preprint arXiv:2403.044 044483 2024.
Yingqian Min, Zhipeng Chen, Jinhao Jiang, Jie Chen, Jia Deng, Yiwen Hu, Yiru Tang, Jiapeng Wang, Xiaoxue Cheng. Huatong Song, et al. Imitate, explore, and self-improve: A reproduction report on slow-thinking reasoning systems. arXiv preprint arXiv:2412.09413. 2024.
Atsushi Miyauchi, Lorenzo Severini, and Francesco Bonchi. Local centrality minimization with quality guarantees. Proceedings of the ACM Web Conference 2024, pp. 410-421, 2024.
Mavuto M Mukaka. A guide to appropriate use of correlation coefficient in medical research. Malawi medical journal, 24(3):69 71, 2012.
Lutz Oettershagen, Honglian Wang. and Aristides Gionis. Finding densest subgraphs with edge-color constraints. In Proceedings of the ACM Web Conference 2024, pp. 936 947, 2024.
OpenAI. Graphwalks. 2025.
OpenAl. Introducing gpt-5. OpenAl, August 2025. Accessed: 2025-08-07.
OpenAl. Learning to reason with 1lms. learning rettooreaanwwwiiie 1lms/ 2025.
https:// cct.index/
Accessed: 15 March 2025. Referenced on
pp. 1,4,6. 6.
OpenFlights. https://ppentights.org./ Accessed: 2024-05-25.
Jiayang Pang, Chenhao Ma, and Yixiang Fang. similarity-based approach for efficient large quasi-clique detection. In Proceedings of the ACM Web Conference 2024, pp. 401-409, 2024.
Miao Peng, Nuo Chen, Zongrui Suo, and Jia Li. Rewarding graph reasoning process makes 1lms more generalized reasoners. In Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining 2, pp. 2257-2263 2025.
Ivo Petrov, Jasper Dekoninck, Lyuben Baltadzhiev, Maria Drencheva, Kristian Minchev, Mislav Balunović, Nikola Jovanović, and Martin Vechev. Proof or bluff? evaluating Ilms on 2025 usa math olympiad. arXiv preprint arXiv:2503.2/ 2025.
13

---

Published as a conference paper at ICLR 2026
Yiwei Qin, Xuefeng Li, Haoyang Zou, Yixiu Liu, Shijie Xia, Zhen Huang, Yixin Ye, Weizhe Yuan, Hector Liu, Yuanzhi Li, et al. O1 replication journey: A strategic progress report- part 1. arXiv preprint arXiv:2410.18988 2024.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. Gpqa: A graduate-level google-proof q&a benchmark. In First Conference on Language Modeling, 2024.
Yang Sui, Yu-Neng Chuang, Guanchu Wang, Jiamu Zhang, Tianyi Zhang, Jiayi Yuan, Hongyi Liu, Andrew Wen, Shaochen Zhong, Hanjie Chen, et al. Stop overthinking: survey on efficient reasoning for large language models. arXiv preprint arXh::2503 2025.
Haoxiang Sun, Yingqian Min, Zhipeng Chen, Wayne Xin Zhao, Lei Fang. Zheng Liu, Zhongyuan Wang, and Ji- Ro-g Wen. Challenging the boundaries of reasoning: An olympiad- math benchmark for large language models. arXiv preprint arXiv:2503.21388 2025.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung. Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. Challenging big-bench tasks and whether chain-of-thought can solve them, arXiv preprint arXiv:2210.09261, 2022.
Jianheng Tang, Qifan Zhang, Yuhan Li, and Jia Li. Grapharena: Benchmarking large language models graph computational problems. arXiv e-prints, pp. arXiv-2407, 2024.
OpenThoughts Team. Open Thoughts. https:/lpeen-thouhttsaii January 2025a.
Qwen Team. Qwen2.5: A party of foundation models, September 2024. URL hww.n//wnlln
Qwen Team. Qwq-32b: Embracing the power of reinforcement learning, 2025b.
Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov, Can language models solve graph problems in natural language? Advances Neural Information Processing Systems, 36:30840-30861, 2023.
Shenzhi Wang, Le Yu, Chang Gao, Chujie Zheng, Shixuan Liu, Rui Lu, Kai Dang. Xionghui Chen, Jianxin Yang, Zhenru Zhang, et al. Beyond the 80/20 rule: High-entropy minority tokens drive effective reinforcement learning for Ilm reasoning. arXiv preprint M.Xiv:25060019:33 2025a.
Yubo Wang, Xueguang Ma, Ge Zhang. Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Aruiraj, Xuan He, Ziyan Jiang, et al. Mmlu-pro: A more robust and challenging multi- task language understanding benchmark. Advances in Neural Information Processing Systems, 37: 2024.
Yuyao Wang, Bowen Liu, Jianheng Tang, Nuo Chen, Yuhan Li, Qifan Zhang, and Jia Li. Graph-rl: Unleashing Ilm reasoning with np-hard graph problems. arXiv preprint arXiv:2508. 2025b.
Anjiang Wei, Jiannan Cao, Ran Li, Hongyu Chen, Yuhui Zhang, Ziheng Wang, Yuan Liu, Thi- ago SFX Teixeira, Diyi Yang, Ke Wang, et al. Equibench: Benchmarking large language models' understanding of program semanties via equivalence checking, arXiv preprint arXiv:2502.12466, 2025.
Liang Wen, Yunke Cai, Fenrui Xiao, Xin He, Qi An, Zhenyu Duan, Yimin Du, Junchen Liu, Lifu Tang, Xiaowei Lv, et al. Light-rl: Curriculum sft, dpo and for long cot from scratch and beyond. arXiv preprint arXiv:2503. 10460, 2025.
Colin White, Samuel Dooley, Manley Roberts, Arka Pal, Ben Feuer, Siddhartha Jain, Ravid Shwartz- Ziv, Neel Jain, Khalid Saifullah, Sreemanti Dey, et al. Livebench: A challenging, contamination- limited Ilm benchmark. arXiv preprint arXiv:2406.1990 19314, 2024.
Hao Xu, Xiangru Jian, Xinjian Zhao, Wei Pang. Chao Zhang, Suyuchen Wang, Qixin Zhang, Zhengyuan Dong, Joao Monteiro, Bang Liu, et al. Graphomni: A comprehensive and extend- able benchmark framework for large language models on graph-theoretic tasks. arXiv preprint 2504v:2504. 12764, 2025.
14

---

Published as a conference paper at ICLR 2026
An Yang. Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jialong Tang. Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jin Xu, Jingren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang, Mei Li, Mingfeng Xue, Na Ni, Pei Zhang. Peng Wang, Ru Peng, Rui Men, Ruize Gao, Runji Lin, Shijie Wang. Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wenbin Ge, Xiaodong Deng. Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Yang Fan, Yang Yao. Yichang Zhang, Yu Wan, Yunfei Chu, Yugiong Liu, Zeyu Cui, Zhenru Zhang, and Zhihao Fan. Qwen2 technical report. arXiv preprint TrXiv:2407.10677 2024.
An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025a.
Lei Yang, Renren Jin, Ling Shi, Jianxiang Peng, Yue Chen, and Deyi Xiong. Probench: Benchmarking large language models competitive programming. arXiv preprint arXiv:2502.20866; 2025b.
Yue Yang, MingKang Chen, Qihua Liu, Mengkang Hu, Qiguang Chen, Gengrui Zhang, Shuyue Hu, Guangtao Zhai, Yu Qiao, Yu Wang, et al. Truly assessing fluid intelligence of large language models through dynamic reasoning evaluation. arXiv preprint arXiv:2506. 02648, 2025c.
Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 555-564, 2017.
Jifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao, Daniel Zhang-Li, Xin Lv, Hao Peng, Zijun Yao, Xiaohan Zhang, Hanming Li, al. Kola: Carefully benchmarking world knowledge of large language models. arXiv preprint arXiv:2306.0999 09296, 2023.
Zhaojian Yu, Yilun Zhao, Arman Cohan, and Xiao-Ping Zhang. Humaneval pro and mbpp pro: Eval- uating large language models on self-invoking code generation. arXiv preprint arXiv:2412.21199 2024.
Zike Yuan, Ming Liu, Hui Wang, and Bing Qin. Gracore: Benchmarking graph comprehension and complex reasoning in large language models. arXiv preprint arXiv:2407.02936. 2024.
Qifan Zhang, Xiaobin Hong, Jianheng Tang, Nuo Chen, Yuhan Li, Wenzhong Li, Jing Tang, and Jia Li. Gcoder: Improving large language model for generalized graph problem solving, arXiv preprint arXiv:2410.1900 2024a.
Qifan Zhang, Nuo Chen, Zehua Li, Miao Peng, Jing Tang, and Jia Li. Improving Ilms' generalized reasoning abilities by graph problems. arXiv preprint arXiv:2507.17168, 2025.
Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Yijian Qin, and Wenwu Zhu. Llm4dyg: can large language models solve spatial-temporal problems dynamic graphs? In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4361, 2024b.
Zihan Zheng. Zerui Cheng, Zeyu Shen, Shang Zhou, Kaiyuan Liu, Hansen He, Dongruixuan Li, Stanley Wei, Hangyi Hao, Jianzhu Yao, et al. Livecodebench pro: How do olympiad medalists judge lims in competitive programming? arXiv preprint arXiv:2506. / 1928, 2025.
15

---

Published as a conference paper at ICLR 2026
A ETHIC STATEMENT
This work focuses on benchmarking large reasoning models through graph algorithm problems. The study does involve human subjects, personally identifiable information, or sensitive data. All experiments are conducted using publicly available models and synthetic datasets. We have taken care to ensure that the research does not promote harmful applications and intended solely for advancing understanding of reasoning in Al systems.
B REPRODUCTIVITY STATEMENT
We provide detailed task definitions, dataset generation procedures, and evaluation protocols ensure full reproducibility. All experiments are conducted with publicly available models and standard- ized settings, as described in Section [ The complete codebase, including dataset generators and evaluation scripts, is released at the project repository to facilitate replication and future extensions.
C
THE USE OF LARGE LANGUAGE MODELS (LLMs)
During the preparation of this work, we made use of LLMs in several stages of writing and experi- mentation:
Language Refinement: LLMs (such as OpenAl's ChatGPT) were employed to improve the readability and academic style the manuscript, helping to enhance clarity and consistency.
Evaluation Assistance: We employed LLMs as judges help with evaluation. These models supported the assessment process and complemented our programmatic evaluation pipeline.
Programming Support:
The Cursor environment, which incorporates AI assistance, was used for generating, modifying, and refactoring segments of the codebase. This contributed to faster implementation and better code quality.
D RELATED WORKS
Benchmarking LLMs on Graph Algorithm Problems. Graph algorithm problems demand deep understanding of structural information and long-range multi-step reasoning, making them particularly challenging for LLMs. For this reason, they have been widely used in prior studies to evaluate LLM capabilities. NL.rraph (Wang et al. (023), GPT4Graph (Guo et al. (023), and GraphQA (Fatemi al.) 2023) are among the earliest works, assessing LLMs on graph algorithm problems by encoding tasks with LLMs alone or with a GNN-LLM combination. Building on this line of research, LLM4DyG (Zhang et al. 2024b) examines tasks dynamic graphs, while GraphInstruct (Luo et al. 2024) provides a broader benchmark with 21 tasks ranging from node-level graph-level. GraphArena ('lang et al. 2024) evaluates LLMs real-world graphs with more fine-grained metrics, and VisionGiraph (Li et al. 2024) explores their capabilities on image graphs. Most recently, GraCore (Yuan al. 2024) evaluates LLMs from the perspectives of graph reasoning and graph understanding, and GraphOmni (Xu et al. 2025) investigates their performance across diverse graph types, serialization formats, and prompting schemes. However, none of these works evaluate the performance of O1-like large reasoning models (LRMs) or analyze the challenges LRMs face when solving graph algorithm problems, which motivates our study.
Evaluating Large Reasoning Models. The emergence of OI-like models, equipped with long chains of thought and advanced reasoning strategies such as self-verification, strategy-shift, and backtracking. has substantially advanced the reasoning capabilities of LLMs. This progress has motivated extensive efforts to evaluate LRMs across diverse domains (Petrov et al. 2025; He et al.
2024;
Huang et al. 2024 Gulati al. 2024 Glazer al. 2024 Li et al. 2025b Huang et al. 2025
| Yu et al. 2024| Wei et al.) 2025| He et al. 2025b Zheng al. 2025 White al. 2024 Suzgun et al. 2202 Lin
Chen et al. 2024d Wang et al. 2023 Li et al. 2022 Dai et al. 2024 Yang et al. [025b]
ct al.
2025). Among these, mathematics has become the predominant benchmarking arena, yielding
many new insights into the strengths and weaknesses of L.RMs. For instance, Putnam-AXIOM (Gulati
16

---

Published as a conference paper at ICLR 2026
et al., 2024), FrontierMath Gllazer et al. 2024). and OlympiadBench (Sun al. 2025 introduce increasingly challenging problems to probe the reasoning limits of models, while other works (Chen et al. 2024d: Wang et al. 2023) analyze phenomena such over-thinking and under-thinking and explore potential mitigations. However, no prior work has systematically evaluated LRR. on graph algorithm problems, which demand structural reasoning and memory-skie missing from existing benchmarks. To close this gap, we present GRALGOBENCH, the first graph-based benchmark for rigorous and application-relevatl LRMs evaluation.
E EXPERIMENTAL SETUP
Models: We evaluate a broad range of reasoning models as well as non-reasoning models in order to ensure comprehensive coverage. For open-source models, include the Qwen3 series (Yang et al. 2025a), QwQ (Team] 2025b), Qwen-2.5 series (Team, (024), OpenThinker series (Team] 2025a)). Skywork series (He al. 2025aa). Light-RI series (Wen et al. 2025). Llama-3.3 series (Dubey et al. 2024). GPT-OSS series (Agarwal et al. 2025), Deepseek- V3 (Liu et al. 2024), and Deepseek-R series (Guo al. 2025). For closed source models, we evaluate GPT5-mini (OpenAl 2025 and Gemini-2.3-pro (Comanici et al. (025).
Evaluation Metrics. Our evaluation framework is designed in systematic manner. For each problem, we collect 8 responses from every comparison model. For few models (i.e., DeepSeek- V3/R1, GPT-5-mini, Gemini-2.5-pro), we reduce the number responses to due to computational limitations and budget constraints. We adopt two evaluation metrics: Pass @ k and Cons@ k. For the Pass@ metric, a sample is regarded as correct at least one of the k responses generated by the LRM matches the ground-truth answer. For the Cons@) k metric, derive a consensus answer for each problem, and then compute the average accuracy across the dataset. To ensure standardized evaluation, each problem is paired with fixed reference answer, and correctness is assessed through exact string matching. We enforce that LRMss output their final answers in the [boxed format. For decoding hyperparameters, we follow prior work (Guo et al. 2025 Team 2025b). setting t temperate ure, top-p, min.p, and max_token to 0.6, 0.95, O, and 32768. respectively.
apply majority voting to
F DEFINITION AND EXPLANATION
F.1 TASK DEFINITION
(1) Maximum Degree node (easy): Given an undirected graph G = (V,E), the task is to identify the node u E V with the maximum degree and output its degree deg(v) = max.ey deg(u).
Optimal complexity: O(VV + [E|) using a single sean of graph.
(2) Max i mum Weight Triangle (medi um) Given an undirected graph G = (V, E) with positive node weight function w : - RR,, the task is to find a triangle {01, U2 v3 that maximizes the sum of their weights Σ w(;s), and output this maximum sum.
Optimal complexity: O(VV3) by brute-force enumeration of all triples of vertices.
(3) Max maximum Clique Problem (hard): Given undirected graph G = (), the task is to find a subset nodes V C that forms clique (i.e., every pair of nodes in 12 is connected by an edge) with the maximum possible size [ The output is this size.
Optimal complexity: NP-hard. The best known exact exponential -imeieiil---eeeeee algorithms (c.g., branch- and-bound, branch-and-reducee run in about ((1.1996| VI).
(4) PathSum (easy): Given an undirected tree T (V,E) with a root r and edge weights w. : - IR, the task is to count the number paths from the root r to leaf node I such that the sum of edge weights (par)))))(()))) w(u, v) exceeds a given threshold r.
Optimal complexity: O(Vl) using depth-fire first search (DFS).
(5) Distance-k (medium): : Given an undirected graph G = (V,E) and a specific node v E V, the task is find the number of nodes V such that their shortest path distance d(u, u) S k.
17

---

Published as a conference paper at ICLR 2026
Optimal complexity: O(VI + [E]) using BFS.
(6) Diameter (hard): : Given an unweighted undirected graph g = (V,8), the task to find the longest shortest path between any two nodes u, V and output its length, i.c. va d(u, v).
Optimal complexity:
O(VI(V] (E]) using BFS (or DFS) from every node.
(7) Maximum k-core (easy): Given an undirected graph 9 = (V, and integer k. the task to find a subgraph g' = (V', E") where for every node v E V. its degree within the subgraph (v) 2 k. The goal is to find the subgraph with the maximum number of nodes [V] and output this size.
Optimal complexity: O(V + [E]) using the peeling algorithm.
(8) Minimum Spanning Tree (medium) um): Given a connected, undirected graph G (V.8) with positive edge weights that connects all nodes) with the minimum possible total edge weight D(u,)ee w(u, v). The output this minimum total weight.
- RR the task is to find spanning tree (a subset of edges & C &
Optimal complexity: Kruskal's algorithm: O(EE) log [V])-
(9) Distance Threshold (hard): Given an undirected graph g = (V,8) with positive edge weights, the task is find the node v" arg minzey Ku V (v) d(u, S 7)1, where is given threshold, and output the node r".
Optimal complexity: worst O[[]] log [V]) using Dijkstra's algorithm from each node (truncated at distance T).
F.2 ERROR TYPE CLASSIFICATION
We categorize model errors into four major classes:
1. Algorithm Selection Error
These errors capture whether LRMs truly understand how to select appropriate algorithm for given problem.
(I) Incorrect algorithm: The chosen algorithm cannot produce the correct solution for the problem.
(II) Suboptimal algorithm: The algorithm is intuition (not guaranteed to produce the optimal solution) computationally inefficient.
2. Algorithm Execution Error. These errors occur when LRMs make mistakes during the execution of an algorithm.
(I) State update error: Incorrectly updating intermediate results, either by missing necessary information or storing extraneous data.
(II) Missing elements: Failure to include essential steps, such as neglecting to traverse all nodes or edges.
IIII) Condition misjudgment: Errors in conditional checks, e.g., incorrect f-statements or loop conditions.
3. Output Quality Error. In these cases, the model produces the correct answer but with low-quality output. We primarily focus on:
(I) Redundancy: Unnecessary repetition superfluous information in the solution.
4. Information Error. These errors arise when the model fails to capture recall critical problem-specific information. We focus on:
(I) Graph memorization error: Misunderstanding or incorreetly recalling the graph structure, such introducing extra nodes/edges omitting existing ones.
18

---

Published as a conference paper at ICLR 2026
F.3 DEFINITION OF ENTROPY
Formally, we define the entropy H₃ at generation step / as the Shannon entropy of the model's predicted probability distribution its vocabulary:
H₂ = E Po.j log Pt.
(3)
Here, = (Pt.1 vt.v) represents the probability distribution over the entire vocabulary V. This
distribution is produced by the language model, denoted as no. conditioned on the input query g and the preceding token sequence oet- Specifically, is computed by applying temperature-scaled Softmax function to the model's raw output logits z₁:
2t T
Pt = To(- oce) Softmax
(4)
G ADDITIONAL TASKS DESCRIPTION
Problem Description G.1: Diameter
You are required to calculate the diameter of an undirected knowledge graph. The diameter of a graph the greatest shortest-path distance between any two nodes in the graph.
Problem to Solve
Entities this knowledge graph: Seine-et-Marne, Vendrest, Paris, Clickteam, Soignolles- en- en-Brie, Saint-Fiacre Seine-et-Marne, France, Didier Julia
The relationships between these entities are as follows:
Seine-ct-Marne is connected to Vendrest via the relationship department.
Seinn-et-Marne is connected to Saint-Fiacre Seine-et-Maree via the relationship department.
Seine-et-Marne is connected to Didier Julia via the relationship region.
Seine-et-Marne is connected to Soignolles-en-Brie via the relationship department.
Seine-et-Marne is connected to France via the relationship country.
Vendrest is connected to France via the relationship country.
Paris is connected France via the relationship capital.
Paris connected Clickteam via the relationship locationCity.
Paris connected to Didier Julia via the relationship birthPlace.
Soignolles-en-Brés is connected to France via the relationship country.
Saint-Fiacre Seine-et-Marne is connected to France via the relationship country.
France is connected to Didier Julia via the relationship region.
Please determine the diameter of this network and output the diameter in the following format: [boxed(n]
Problem Description G.2: Distance Threshold
You are given an undirected weighted graph representing the airport network, where nodes represent airports (codes: DLY, TAH, HIR, IPA, VLI, BNE, NAN, AKL, LNE, FTA, AWD, EAE, LNB, AUY) and edges represent direct flights between airports. The weight of each edge the distance between two airports.
The list of airports: DLY, TAH, HIR, IPA, VLI, BNE, NAN, AKL, LNE, FTA, AWD, EAE, LNB, AUY
The direct flights (edges) are: [DLY, IPA, 34), [DLY, VLI, 139], [TAH, AUY, 105], [TAH, AND, 461, [TAH, FTA, 105], [TAH, IPA, 64], [TAH, VLI, 217]. [HIR, VLI, 1282], [HIR, BNE, 2126]. [HIR, NAN, 2093], [IPA, VLI, 167], [VLI, NAN, 966], [VLI, AKL,
19

---

Published as a conference paper at ICLR 2026
2238], [VI.T, BNE, 1893], [VI.T, EAE, 671, [VLT, LNB, 1251, [VI.T, LNE, 204], [BNE, AKT, 2295], [BNE, NAN, 27101, [NAN, AKL, 21561, (FTA, AWD, 72]
The distance threshold is 284.
For each airport, the distance to another airport is defined as the sum of the weights (distances) along the shortest path connecting them. Your task is: Return the airport code with the smallest number of other airports that can reached with shortest path distance more than the threshold. If there are multiple such airports, return the one with the lexicographically largest code.
Present your answer in the following format: airport code
The airport code is the airport code.
Problem Description G.3: Maximum Clique Problem
You are required to solve the Maximum Clique Problem for an undirected wikipedia network. In this network, nodes represent wikipedia articles and edges represent hyperlinks between articles. Your objective is to find the largest subset of nodes such that every pair of vertices in this subset connected by edge.
Articles in the network: Eugene Domingo, Philippines, Talk show, David Cook (singer), Live television, BB Gandanghari, Cool Center, Katya Santos, David Archuleta, Sadako, Gladys Guevarra, List of Philippine television shows
Hyperlinks between these articles: Eugene Domingo and Cool Center, Eugene Domingo and Philippines. Philippines and Cool Center, Philippines and Gladys Guevarra, Philip- pines and BB Gandanghari, Philippines and List of Philippine television shows, Philip- pines and David Archuleta, Talk show and Cool Center, David Cook (singer) and Cool Center, David Cook (singer) and David Archuleta, Live television and Cool Center, BB Gandanghari and Cool Center, Cool Center and List of Philippine television shows, Cool Center and Sadako, Cool Center and David Archuleta, Cool Center and Gladys Guevarra, Cool Center and Katya Santos.
Identifly the clique with the maximum number of articles in this network. Present your answer in the following format: \boxed(k) ( J. k is the number of articles of this clique.
Problem Description G.4: Minimum Spanning Tree
You are required to solve the Minimum Spanning Tree Problem for an undirected street network. In this network, nodes represent streets (e.g., street IDs) and edges represent intersections between streets. The weight of each edge is the distance between two streets.
Streets in the network: Mulgray Avenue, Vanessa Avenue, Eames Avenue, Gabrielle Avenue, Justine Avenue, Coronation Road, Turon Avenue, Jasper Road, Louise Avenue, Glanmire Road, Hilda Road, Seven Hills Road
Intersections between these streets: Mulgray Avenue and Coronation Road (weight: 6), Mulgray Avenue and Jasper Road (weight: 3), Vanessa Avenue and Jasper Road (weight: 1), Eames Avenue and Hilda Road (weight: 7), Eames Avenue and Jasper Road (weight: 10), Gabrielle Avenue and Justine Avenue (weight: 6). Gabrielle Avenue and Turon Avenue (weight: 7). Justine Avenue and Jasper Road (weight: 1), Justine Avenue and Turon Avenue (weight: 6), Coronation Road and Jasper Road (weight: 9). Turon Avenue and Jasper Road (weight: 4), Jasper Road and Glanmire Road (weight: 5), Jasper Road
and Hilda Road (weight: 1), Jasper Road and Louise Avenue (weight: 5), Jasper Road and Seven Hills Road (weight: 2), Hilda Road and Seven Hills Road (weight: 1).
Identify the minimum spanning tree of this network. The minimum spanning tree is a subset of edges in a connected, weighted graph that connects all the vertices together with the smallest possible total edge weight and without any cycles.
Present your answer in the following format: Vboxed (n), where is the sum of the weights of the edges in the minimum spanning tree.
20

---

Published as a conference paper at ICLR 2026
Problem Deseription G.5: PathSum
You are given a binary tree representing co-authorship network. Each node is author, and each edge represents a co-authorship relationship, with the edge's weight indicating the number of papers co-authored by the two authors. Find all paths from the root author to any leaf author such that the sum of the edge weights (i.e., the total number of co-authored papers along the path) is greater than the given value.
Authors in the network: Tarkan Tan, Ruud H. Teunter, Hui-Ming Wee, Samuel Yáñez Artus, Po-Chung Yang. Asoke Kumar Bhunia, Anne Barros, Yu-Chung Tsao, Samiran Chattopadhyay, A. K. Bhunia, Michel Roussignol, Mahmood Shafiee, Shib Sankar Sana, Gwo-Ji Sheen
Co-authorship relationships (with number of co-authored papers): Tarkan Tan and Ruud H. Teunter (co-authored 2 papers), Ruud H. Teunter and Hui-Ming Wee (co-authored 4 papers), Ruud H. Teunter and Samuel Yáñez Artus (co-authored papers), Hui-Ming Wee and Po-Chung Yang (co-authored 4 papers), Hui-Ming Wee and Asoke Kumar Bhunia (co-authored 5 papers), Samuel Yáñez. Artus and Anne Barros (co-authored 6 papers), Po-Chung Yang and Yu-Chung Tsao (co- authoredd 4 papers), Asoke Kumar Bhunia and Samiran Chattopadhyay (co-authored 6 papers), Asoke Kumar Bhunia and A. K. Bhunia (co-authored papers), Anne Barros and Michel Roussignol (co-authored papers), Anne Barros and Mahmood Shafiee (co-authored 5 papers), Yu-Chung Tsao and Shib Sankar Sana (co-authored 10 papers), Yu-Chung Tsao and Gwo-Ji Sheen (co-authored papers).
The root of the tree is Tarkan Tan.
The target value is 19.
Present your answer in the following format: \boxed (n). n the number of qualifying paths.
Problem Description G.6: Maximum Weight Triangle
You are required to solve the Maximum Triangle Sum Problem for an undirected wikipedia network. In this network, nodes represent wikipedia articles and edges represent hyperlinks between articles. Each node is assigned a weight. Your objective is find the triangle with the maximum sum of weights of its three nodes.
Articles in the network: Montebelluna (weight: 1), Massimo Mascioletti (weight: 8),
Gianluca Faliva (weight: 4), Eppelheim (weight: 7), United States (weight: 6), Alberto Rebecca (weight: 10), October 15 (weight: 6), Rugby union (weight: 1), Italy (weight:
9). List of football clubs Italy (weight: 9), Manuel Dallan (weight: 8), Brad Johnstone (weight: 1)
Hyperlinks between these articles: Montehelluna and List of football clubs in Italy, Mon- tebelluna and Eppelheim, Montehelluna and Alberto Rebecca, Montehelluna and Italy, Montebelluna and Manuel Dallan, Massimo Mascioletti and Brad Johnstone, Massimo Mascioletti and Gianluca Faliva, Gianluca Faliva and Italy, Gianluca Faliva and Brad Johnstone, Gianluca Faliva and Manuel Dallan, Gianluca Faliva and Rugby union, Eppel- heim and Italy, United States and Italy, United States and October 15, Alberto Rebecca and Italy, October 15 and Italy, October 15 and Manuel Dallan, Rugby union and Manuel Dallan, Italy and Manuel Dallan.
Identify the triangle with the maximum sum of weights of its three nodes in this network. Present your answer in the following format: \boxed n.). n is the maximum sum of weights of its three nodes.
Problem Description G.7: Minimum Spanning Tree (Adjacency List)
You are required to solve the Minimum Spanning Tree Problem for an undirected street network. In this network, nodes represent streets (e.g., street IDs) and edges represent intersections between streets. The weight of each edge is the distance between two streets.
21

---

Published as a conference paper at ICLR 2026
Streets in the network: Maplin Road, Golden Plover Close, Widgeon Close, Downs Court Road, Greyfields Close, Pheasant Close, Coolfin Road, Burrard Road, Freemasons Road, Ethel Road, Partridge Knoll
Adjacency list representation (each street followed by its connected streets); Maplin Road (weight: 5): Freemasons Road (weight: 9), Golden Plover Close (weight: 6), Pheasant Close (weight: 8), Widgeon Close (weight: 7)
Golden Plover Close (weight: 4): Maplin Road (weight: 5), Widgcon Close (weight: 7)
Widgeon Close (weight: 7): Maplin Road (weight: 5), Golden Plover Close (weight: 4)
Downs Court Road (weight: 3): Partridge Knoll (weight: 10)
Greyfields Close (weight: 6): Partridge Knoll (weight: 10)
Pheasant Close (weight: 8): Maplin Road (weight: 5), Partridge Knoll (weight: 10)
Coolfin Road (weight: 2): Freemasons Road (weight: 9)
Burrard Road (weight: 4): Freemasons Road (weight: 9)
Freemasons Road (weight: 9): Maplin Road (weight: 5), Coolfin Road (weight: 2),
Burrard Road (weight: 4), Ethel Road (weight: 3) Ethel Road (weight: 3): Freemasons
Road (weight:
Partridge Knoll (weight: 10): Downs Court Road (weight: 3), Greyfields Close (weight: 6), Pheasant Close (weight:
Identify the minimum spanning tree of this network. The minimum spanning tree is subset of edges in a connected, weighted graph that connects all the vertices together with the smallest possible total edge weight and without any cycles.
Present your answer the following format: \boxed where n is the sum of the weights of the edges in the minimum spanning tree.
Problem Description G.8: Minimum Spanning Tree (Markdown Table)
You are required to solve the Minimum Spanning Tree Problem for an undirected street network. In this network, nodes represent streets (c.g., street IDs) and edges represent intersections between streets. The weight of each edge is the distance between two streets.
Street
Street 2
Weight
Heritage Court
Darcey Road
3
Jordana Place
Darcey Road
Neville Court
Darcey Road
7
Silky Oak Place
Darcey Road
3
Candlebush Crescent
Darcey Road
1
Candlebush Crescent
Henley Close
Candlebush Crescent
Lemenwood Place
10
Candlebush Crescent
Melaleuca Close
Darcey Road
Castlewood Drive
10
Darcey Road
Crane Road
Darcey Road
Henley Close
5
Darcey Road
Jarrah Place
10
Crane Road
Castlewood Drive 8
Find the minimum spanning tree of this street network and output the sum of the weights of the edges the MST. Present your answer in the following format: "n where the sum the weights of the edges in the MST.
22

---

Published as a conference paper at ICLR 2026
Problem Deseription G.9: Minimum Spanning Tree (Numeric ID)
You are given undirected weighted graph with 12 nodes labeled from 0 to 11.
Edges (format: [Nodel, Node2, weight]): [0, s, 3], [1, 61, 12, 5, 71, [3, 31, 14, 11, [4, 6, 4J, [4, 7, 10J. [4, 8, 9]. [5, 11, 10J, [5, 10, 4J, [5, 6, 5], [5, 9, 10), [10, 11, 8]
Find the minimum spanning tree of this graph and output the sum of the weights of the edges in the MST. Present your answer the following format: n the edges in the minimum spanning tree.
where the sum the weights of
Problem Description G.10: Minimum Spanning Tree (Code Version)
You are required to solve the Maximum Triangle Sum Problem for an undirected wikipedia network. In this network, nodes represent wikipedia articles and edges represent hyperlinks between articles. Each node is assigned a weight. Your objective is to find the triangle with the maximum sum of weights of its three nodes.
Streets in the network: Mulgray Avenue, Vanessa Avenue, Eames Avenue, Gabrielle Avenue, Justine Avenue, Coronation Road, Turon Avenue, Jasper Road, Louise Avenue, Glanmire Road, Hilda Road, Seven Hills Road
Intersections between these streets: Mulgray Avenue and Coronation Road (weight: 6).
Mulgray Avenue and Jasper Road (weight: 3). Vanessa Avenue and Jasper Road (weight: 1), Eames Avenue and Hilda Road (weight: 7), Eames Avenue and Jasper Road (weight: 10), Gabrielle Avenue and Justine Avenue (weight: 6), Gabrielle Avenue and Turon Avenue (weight: 7), Justine Avenue and Jasper Road (weight: 1), Justine Avenue and Turon Avenue (weight: 6), Coronation Road and Jasper Road (weight: 9), Turon Avenue and Jasper Road (weight: 4), Jasper Road and Glanmire Road (weight: 5), Jasper Road
and Hilda Road (weight: 1), Jasper Road and Louise Avenue (weight: 5). Jasper Road and Seven Hills Road (weight: 2), Hilda Road and Seven Hills Road (weight: 1).
Identify the minimum spanning tree of this network. The minimum spanning tree is subset of edges in a connected, weighted graph that connects all the vertices together with the smallest possible total edge weight and without any cycles.
Solve this problem using Python code only. Wrap your Python code in the following format:
Your code here
print (") [n)"
Here, 'n' is the sum of the weights of the edges in the minimum spanning tree.
23

---

Published as a conference paper at ICLR 2026
H ADDITIONAL EXERIMENTS RESULTS
H.1 ALGORITHM RATIO CALCULATION
PathSum
DistanceK
Diameter
1.
15
1.0
MKC
MST
1.0
DistanceThreshold
3.5
0.3
0.6
0.4
32
02
3.0
sorth
1990y relneleee
sourc1
grsdyy relynntined
03
Max
Triangle
MCP
1.0
64.
0.3
Datoo
0.
64
12
62
100
erunaraioon
search
gready
mantiooed
64
rel.maarinnd
Figure 7: Algorithm ratio of Qwen3-32B.
Ratto
MКC
3.0
MST
DistanceThreehool
0.0
0.5
0.2
WrrTHrstion inach
greddy
mericced
50
(1900)
Degree
Triangle
MCP
64
02
gredy MELneteee)
50
CANCC
(mndy
sarch
pidd
Figure 8: Algorithm ratio of Gemini-2.5-Pro.
24

---

Published as a conference paper at ICLR 2026
PathSum
DistancelK
Diametar
82100
grendy FsT nwniiood
s4th
gread nst mendaand
aramwaation
640711
1.0
MIC
1.0
MST
DistanceThreshold
6/8
0.0
5ato
0.6
0.2
64
g1443
1.0
Max Degree
10
Triangle
1.0
MCP
6.8
suth
poady
rnlyncetionol
goudy
Figure 9: Algorithm ratio of Llama-3.3-700
25

---

Published as a conference paper at ICLR 2026
H.2 PERFORMANCE ACROSS GRAPH ALGORITHM CATEGORIES (RQ1)
Table 5: Evaluation results of Level-1 and Level-2 groups.
Level-1 (8-15 nodes)
Level-2 (16-30 nodes)
Models
Enumeration
Exploration
Intuition
Avg.
|nuueration
Exploration
Intuition
Avg.
c8k
p8k
c8k
98k
ookk påk cēk
påk
cak
płk
cēk
pēk
cex pêk
cek pêk
Skywork-OR1-7B-
0.50
0.91
0.63
0.31
0.48
0.84
0.67
0.39
0.58
Light-R1-7B-DS
0.37
0.79
0.41
0.82
0.24 0.61 0.34
0.74
0.07
0.48
0.09
0.49
0.04
0.23 0.07 0.40
Distill-Qwen-7B
0,43
0,88
0.47
0.87
0.30 0.68 0,40
0.81 0.17
0.68
0.14
0.63
0.02
0.32 0.11 0.54
Qwen2.5-7B
0.21
0.47
0.29
0.65
0.06 0.20 0.19
0.44
0.12
0.45
0.13
0.29
0.04
0.13 0.10 0.29
OpenThinker-7B
0.57
0.88
0.54
0.91
0.41
0.79 0.51
0.86
0.23
0.83
0.17
0.61
0.10
0.37 0.17 0.60
Qwen3-8B-non -htttnnnnn
0.57
0.85
0.70
0.96
0.30
0.52
0.82
0.35
0.75
0.29
0.55
Qwen3-8B
0.89
0.99
0.77
0.99
0.96
1,00
0.87
0.99
0.63
0.93
0.63
0.93
0.66
0.93 0.64 0.93
Light-R1-a5 R1-38B
0.97
1.00
0.97
1.00
0.95
0.99
0.96
1,00
0.85
0.99
0.89
0.97
0.71
0.93 0.82 0.96
Skywork-OR1-328
0.91
0.99
1.00
1.00
0.89
1.00
0.94
1.00
0.93
0.99
0.97
0.99
0.87
0.98 0.92 0.99
Distill- Saiill-Qwen-32B
0.93
0.99
0.96
0.99
0.96
1.00 0.95
0.99
0.75
0.98
0.73
0.95
0.62
0.89 0.70 0.94
Qwen2.5-32B
0.25
0.73
0.42
0.85
0.36
0.34
0.73
0.11
0.18
0.52
0.39
0.49
OpenThinner-3228
0.97
0.99
0.97
1.00
0.95
1.00
0.96
1,00 0.85
0.98
0.85
0.97
0.62
0.94 0.77 0.96
QWQ-32B
0.98
1,00
1,00
1,00
0.99
1.00
0.99
1.00
0.93
0.99
0.92
0.99
0.91
0.98 0.92 0.99
Qwen3-32B
0.97
0.99
0.98
1.00
0.99
1.00
0.98
1.00
0.89
0.99
0.83
0.98
0.84
0.96
0.85 0.98
Qwen3- 1ee---2B-nnottinie no-thinking
0.77
0.97
0.84
0.97
0.66
0.76
0.94 0.51
0.89
0.19
0.51
0.75
Normalized Analysis. To address the imbalance task difficulty across reasoning taxonomies, we follow prior work (Yuan al., 2024 Yu et al. (2023) and apply normalization procedure reduce the influence task complexity on model performance. Specifically, for each model and task, we compute a z-score of Pass and Cons@ & accuracy and then linearly rescale the scores the range [0, 100J. Specifically, for each model i and each task j, we compute the z-score of its Pass @ k and Cons@r @ i accuracy as follows:
Tij ... PQMM)
o 2 PijM1)
where Tij denotes the Pass@k or Cons@ k accuracy of model i on task j. while u(-) and o(-) denote the mean and standard deviation over all M models on that task.
We then linearly rescale the z-scores into the range [0, 100) to obtain a normalized score:
Fij min(2) max(2) min(2)'
Sij 100
(6)
where min(2) and max(2) are taken over all models the same task.
Figure 10 Figure present the normalized scores different models across reasoning taxonomies and graph sizes. The normalized outcomes preserve the same performance hierarchy observed carlier, highlighting persistent weaknesses of LRMs in intuitive reasoning.
Light-R11 R1-32B Doer3-528-no-tthhiie
Skywork DR1-320 OpenThinier3328
DWQ 32B
Disbil Owen. 329
Qwen3-328
Owen-2.5 5-328
Level-3 (31-50 nodes)
Level-4 (51-80 nodes) Exploration
Level.5 (81-120 nodes) Exploration
Level-6 (121-160 nades) Exploration
Exploration
Eemerraioo
ow mmrattoo
Enumeration
Enumoration
Intultion
Intultion
Intuitian
Intuitton
Figure 10: Normalized pass @k scores of different reasoning taxonomies (32B models).
26

---

Published as a conference paper at ICLR 2026
LightR1-328 128
Skywork-OR1
Distil Distil.Qeen.33 Qwen-2.5-328
Qwer3-328-no-thhieee
OpenThinvee-328
Qwen3-328
nodes)
Levei-4 Exploration
nodes)
Level-5
Level-6 nodes)
Exploration
Exploration
Exploration
ameration
Enimeration
Enumeration
Enameration
Figure 11: Normalized cons@ 7-scores of different reasoning taxonomies (32B models).
Skyworis 001-00--11----11 -revveer Preview Light-A1-78-0S
Distil Ow 73 Qwen2. 5-78
OpenThinicar-8
Qwen3 8B
Qwwn33-88-nothiinknng
Level-1 nodes)
Level-2 (16-30 nodes) Exploration
Level-3 (31-50 nodees) Exploration
Level-4 nodes) Exploration
Cnmmrraioo
Enimerattio
Enumeration
Enameration
Intuition
Intuition
Intuition
Intuition
Figure 12: Normalized pass@ z-scores of different reasoning taxonomies (8B models).
Siyyeri--02--7--rree
Distil Owan, 78 Owen2 5-78
OpanThineur-78 Owen 3-mB--3---tniniing
Qwen3-8E
Light-R1-7B-DS
Level-1 (8-15 nodes) Exploration
Level-2 (16-30 nodes) Exploration
Level-3 (31-50 nodes) Exploration
Level-1 (51-80 nodes) Exploration
Enmmatation
Enemeration
Enumer
Enumeration
Intuition
Intuition
Intuition
Intuition
Figure 13: Normalized cons @k Z-scores of different reasoning taxonomies (8B models).
Die 020
Level-3 3 (31-50 nodes)
Level-4 151-80 nodes)
Level-5 (81-120 nodes)
Level-6 (121-160 nodes)
Desancck
stannce
Distancel
Distancek
cangge
Rlangle
Ttangle
Pochs
FuthSuu
PathSurn
Pathduh
ManDegree
MaiDegree
ManDagree
MasDegies
Dlameter
Diammeerr
Diameber
Diemwber
akapde Thruahold
Thanhhrhreshald
Diskpcethressed
MKC
MKC
MAC
MIT
MST
MST
Figure 14: Cons @k accuracy of different reasoning taxonomies (32B models).
27

---

Published as a conference paper at ICLR 2026
Siywork
ng
QWO
D6siILOweh_328
Level-3 (31-50 nodes)
Level-4 131-80 nodes)
Level-5 (01-120 nodes)
Level-6 (121-160 nodes)
MCP
MCP
MCP
MCP
Distancck
Trangle
PothS
FathSun
Sath
Pathsum
Degree
Degree
MaxDegrne
NadDegree
Diamer
Clamedsr
Diameter
Diameter
DisaodTTrested
stande Threatuld
Thsshel
Distgncehhesseed
MBC
MST
MST
MST
Figure 15: Pass @k accuracy of different reasoning taxonomies (32B models).
OpenTTinon-77 Owend 88 no-minnnnng
Qwen3-B0
R1-78-05
Owen2
Level-1 (0-15 nodes)
Level-2 (16-30 rodes)
Level-3 (31-50 nodes)
Level-4 (51-80 nodes)
Desencak.
Datarcas
Distace
Dietanced.
laggle
Teangle
Thangle
Rangle
RehSs
PalhSrum
Sath
PathSaph
MaiDegnee
KaaDegres
Diameber
Diameber
Dismeber
Diameter
D sbspic Threshold
stapee Thrssholl
WCC
PKC
NKC
MBC
Figure 16: Cons @k accuracy different reasoning taxonomies (8B models).
Skywork-OR2 C-1-1B-Prasiie Ligst 01-181--88 DS
Dat Owin 78
Opanitineer-Fe
Qwen5-BB
Owen2 5-78
Qwand 85 2lnking
Level-1 nodes)
Level-2 116-30 nodes)
Level-3 nodes)
Level-4
WCP
MCP
HC
MCP
Distanca
Datancat.
Distance
DistancaK
oaggc
Toaglec
Taagle:
Fangle
Degres
MaDDagree
MaxD-groc
Degree
Diamcoo
Blamdker
Diameigr
DisneCTTrestel
stapce
DesspceThreshod
VST
MST
HET
MSTT
Figure 17: Pass accuracy of different reasoning taxonomies (8B models).
28

---

Published as a conference paper at ICLR 2026
H.3
ERROR ANALYSIS (RQ1)
Major
Algociltu Exccution Eieor
Algoritum Selection
DOF--Outpi Quality
Minor
concition misjalynnt
graph memorizztlls
IA-ineermnt algonihm
SUEattat updatt crot
SA saboprimal algoritım
KDNC redundancy
OMSN-cmieson
Enumeration
Exploration
Intuition
S
ARk
2VE
15.4%
Rowe
Figure 18: Error type distributions across reasoning taxonomies for Qwen3-8B (top) and its reasoning variant Swven3-8--no-thinkie (bottom).
H.4 HIGH ENTROPY TOKENS (RQ2)
High Entropy Tokens (Distribution)
sono the
edge
are
).
in
ther
node
"
there
e
Wa
with
T
m
road
p
bobum
and
at
is
an
x
path
me
ca
C
r
f
street
of
O
connected
room
list
not
edges S
degree
alll
e
* **
f.o
that distance
be
via
Nodes
s
Figure 19: High-entropy tokens in LRMs inference traces.
H.5 OVERTHINKING ANALYSIS (R (RQ2)
29

---

Published as a conference paper at ICLR 2026
0,77 0.7666 64 654
1.0
3.5
Elfective
94
92
92
Damaaok
MKC
Mellepee
PatiSius
NCT
Diaurtor
NST
Trangge
GSMA
SVAMP
AIMO AMC
coud
SAT
Matk sev
AIMO AIMB
STESI
AIMB83225.11
0.
MST
Medlegee
Padifum
Diemote
Dessmork
MKC
MCF
Distator Thansbel
Trieogle
Dittance /
(a) Outcome efficiency
(b) Proportion of reasoning behaviors
Figure 20: Overthinking analysis of Distill-Qwen-30
1.3
qaa 855
Graph Taska
83
6:00
Label Propeetio
Edfechve
07
6:8
9-4
2.44
610
890
84
64
65
92
PabSSan
Distonce Thrashuld
MRC MCP
Discrnok
Maxheegne
Diamete
Trangl
Mrs
SWAMP
S47
cisM
GSM
AlMO AIME
STEM
2025-122-- 2025-11
Marison
11M821254
AlMO AMC
MaaDlgge
MBT
Hamore
Desnmork
MEC
Padi-am
MCP
Datamse Tamskadd
Thaaado
(a) Outcome efficiency
(b) Proportion of reasoning behaviors
Figure 21: Overthinking analysis Qwen3-3nnB 3-BBB.
30

---

Published as a conference paper at ICLR 2026
1 DISCUSSION
Table 6: Performance (pass@k/ / cons @k (%) of Qwen3-32B under different graph representations.
Level
Task
Edge list
Adjacency list
Markdown table
Numeric IDs
Level-1
DistanceK MST
100.0/ 100.0
100.0/ / 100.0
100.0 100.0
100.0 / 100.0 100.0/ 100.0
(8- 15 nodes)
100.0/ 100.0
100.0/ / 100.0
100.0/ 100.0
Level-2
DistanceK MST
100.0 / 83.3
100.0/96:
96.7 / 86.7
100,0 / 90.0
(16- 30 nodes)
06.7/83.31
100.0 86.7
93.3 83.3
96.7 / 83.3
Level-3 (31-50 nodes)
DistanceK MST
93.3/ 66.7
100.0/ / 100.0
86.7/76,
96.7 / 83.3
23.3/ 13.3
/3.
53.3 13.3
53.3/ 26.7
J OTHER EXPERIMENTS
Table 7: Level-3 (31-50 nodes) results. Each cell reports pass mass@k k cons@k.
Fasy
Mediun
Hard
Model
Max Degree
Puth Sum
MKC
Triangle
Distance-K
MST
MCP
Diameter
Distance Threshold
Distill Owen 32B
0.80
1,0070,74
0.60/0.22
0:90/0.66
0156 0.334
0.20/0.00
0.72 0..36
0.72/0..3 /0.32
0.26/0.24
Lighh-Rl-128
0.90/0.84
0.96 0.90
0.62/00.34
0:94/0:30
0.54:0.50
0.33 /0.07
1.006
0.92 /0.5/
0.56/0.50
1.3mm--33--000
0.32
0.56/0.26
0.05/0.02
0.12/0.00
0.34:0.04
0.00/0.00
0.08 0.08/0.00
0.20/0.02
0.00/0.00
Open 3221
0.76/0.78
0
0.32/0.36
0:58 70.00
0.76/00.4
0.30/0.10
0.50/1.3 0.5470.66
0,60/0.30
QWQQ-3B
0.96
1,00/0.98
0.90/0.64
1.00/0.94
0.88/
0.30/0.50
0.92/0..6
0.90/0.48
0.80/060
Qwen2.5.30
0.40/0.12
0.08/0.00
0.40:0.12
0.82/00.4
0.58//..18
0.00/0.00
0.12/0.00
Quen3-328
/0.76
1.00/0.96
0.76
0.63/0.30
0.90/0:48
Qwen3-32B- dhinking
0.12
0.72/0.32
0.13/0.05
0.5470.20
/1.20
0.24
Skywork-ORI.3 1R11-R
1.00/0.94
1.00/ 1.00
0.90/00.76
1.00/0.92
1.00/0.82
0.67/0.27
0.9870.82
0.04 /0.52
spt ues 20b
0.98 0.99
1,00/ 1.00
0.62/0.66
0.98 1.88/0.88
0.94 0.76
0,53/
0.9670.78
0.58 00:44
0.22/0.22
Table 8: Level-4 (51-80 nodes) results. Each cell reports pass @k k cons@k.
Model
Easy
Medion
Degree
Sum
Triangle
Distance-K
Diameter
Distance Threshold
Distill Owen 32B
0.97
0.67/ 0.33
0.27 /0:07
0.80/0.43
0.40/0.20
0.16/0.06
0.70/0.33
0.60/0.20
0.03/0..3
Light-R1-32B
0.60/0.30
0.50/0.55
0.23 /0:05
0.70/0..7 0.33
1.37
0.30/0.12
0.87/030
/0.23
0,87 0.07
1.mm9-13-700t
0.47/0 0.7/0.13
0. 0.10/0.00
0.03 /0.00
0.13/0.00
0.17:0.00
0.00/0.00
0.10/0000
0.23/0.00
0.00/0.00
Thinkrr
0.30/0.37
0.0000.77
0.13/6.03
0.50/0.50
0.50//0.3
0.36/0.14
0.80/0.0
0.8/00.27
0.13//013
QWQQ32B
1.00/0733
1,00/0.00
0.23/6.10
0.90/0.70
0.63//0433
0.36/0.36
0.90/0.57
0.87/ /0.37
0,70/0,33
Owen2,5.328
0.00
0.00/0.00
0.57 00.20
0.30/0.07
0.20/0.20
0..7
0.20/0.10
Qwen3-32B
0.04/0.40
0.90/0.77
0.30/
0.77/0.47
0.48/0.14
0.83/0.53
0,50/0.33
Qwen3-32H-nn -iti-nittthiing
Skywork-ORI--3
0.93/0.53
0.3/0083
0.37
/0.17
0.80/
0.67/0.37
0.52/0.40
0.80/0.50
0.93/0.30
0.00:0.00
gpt oss 20b
0.57//033
0.80/ 0.67
0.37 00.17
0.30/0.30
0.57 1.47
0.34 0.20
0.67/0.43
0.63 00.3
0.631 0.50
Findings of group problems by computational complexity We re-evaluate model performance by grouping tasks based on theoretical time complexity- (O)n). Medium (O(n²)). and Hard (O(n" (NP-))/PPaaraaaaa whhle controlling for graph size (using Level-3 and Level-4 datasets) to isolate the impact of algorithmic difficulty. Results are shown in Table and g This analysis yields three critical insights. First, within the same reasoning taxonomy, performance generally declines as computational complexity increases; for instance, models like QWQ-32B achieve near-perfect scores on linear-time tasks (e.g., Max Degree) but degrade significantly on NP-hard tasks (e.g.. Distance Threshold), confirming that expanded search spaces pose greater challenges to LRMs. Second, we observe an anomaly in the Exploration category where models frequently outperform on the "Hard" Diameter task compared to the "Medium" " Distance-K task (e.g., QWQ-32B scores 0.87 vs. 0.63 on Level-4), discrepancy we attribute to training data distributions favoring specific classic problems. Third, reasoning taxonomy often outweighs theoretical complexity: models consistently perform better on "Hard" Enumeration tasks than "Easy" Intuition tasks (c.g.. Light-RR- NP-hard MCP but only 0.62 on the linear-time MKC), This suggests that current LRMs are inherently optimized for systematic, step-by-step verification rather than the global heuristic judgments required for intuition- based problems, even when the theoretical complexity suggests the former should be more difficult.
achieves 1.00 on the
31

---

Published as a conference paper at ICLR 2026
K
DETAILS DEMONSTRATION
K.1
PROMPTS
Prompts K.1: LLM Prompts For Categorizing Enumeration Algorithm
SYSTEM PROMPT
You are a graph theory expert. Given a graph problem and an answer to that problem, please determine which of the following approaches is used in the answer:
a) Enumeration (such brute-force methods)
b) Search (such as BFS, DFS)
c) Greedy (such as Dijkstra's 's algorithm)
d) Not mentioned (other algorithmic approaches)
Directly output your choice (a, b, c, or d) with no explanation or additional text.
USER PROMPT
Given the problem and its answer below, identify which of the following approaches was used to derive the solution:
Problem: fquestion}
Answer: (answer)
Prompts K.2: LLM Prompts For Categorizing Exploration Algorithm
SYSTEM PROMPT
You are graph theory expert. Given problem related to finding the shortest path and its corresponding answer, please determine which of the following approaches is used in the answer:
a) Enumeration (such brute-force methods)
b) Search (such BFS, DFS)
c) Greedy (such as Dijkstra's 's algorithm)
d) Not mentioned (other algorithmic approaches)
Directly output your choice (a, b, or d) with no explanation or additional text.
USER PROMPT
Given the problem and its answer below, identify which of the following approaches was used to derive the solution:
Problem: {question}
Answer: (answer)
Prompts K.3: LLM Prompts For Categorizing Intuition Algorithm
SYSTEM PROMPT
You are graph theory expert. Given Maximum K-core (MKC) problem and an answer to that problem, please determine which of the following approaches is used in the answer:
a) Enumeration (such brute-force methods)
b) Search (such BFS, DFS)
c) Greedy (such as Peeling algorithm)
d) Not mentioned (other algorithmic approaches)
Directly output your choice (a, b, d) with no explanation or additional text.
USER PROMPT
Given the problem and its answer below, identify which of the following approaches was used to derive the solution:
32

---

Published as a conference paper at ICLR 2026
Problem:
{question)
Answer: {answer)
Prompts K.4: LLM Prompts for Categorizing Errors In Al-Generated Solutions
You are an intelligent Al assistant.Given a graph problem and an LLM''s response to that problem, analyze the LLM's response to identify any errors it contains. Use the following refined error categories and definitions for your analysis:
OUTPUT QUALITY
redundancy: Unnecessary repetition or superfluous information in the solution.
ALGORITII SELECTION
incorrect algorithm: The chosen algorithm cannot produce the rect solution for the problem. In this task, the correct algorithms are: (correct.algorithme
task]) [args.task]]
suboptimal algorithm: The algorithm used is inefficient or is imple- mented in a less efficient way. In this task, the efficient algorithms are: (efficient algorithm dict [args task]].
INFORMATION ERRORS
graph memorization error: Misunderstanding incorrect memory of the graph struc- ture, such as extra or missing nodes/edges.
ALGORITHM EXECUTION
state update error: During algorithm execution, state variables or data structures are updated incorrectly, causing subsequent steps to operate on erroneous states and compromising overall correctness.
omission: Missing important elements during execution, e.g., failure traverse all nodes or edges.
condition misjudgment: Mistakes in condition checks, such as incorrect if-statement or loop-condition evaluations.
The LLM's response will be segmented into sections labeled as "[Section 1]. content...", "[Section 2], content...", etc.
Instructions:
Your response format should be list of error annotations as: "[section index, error type, detailed error analysis]"
If multiple errors exist in one section, list them separately. Do not output anything other than these error annotations.
Prompts K.5: LLM Prompts For Relormatting The Output
Here is the problem and the response:
You are an intelligent assistant. Given a graph problem and its response, your task review the response, which is divided into multiple parts with each step labeled using tags. After reading through the steps, you should group them into distinct sections, where each section represents complete and logical gobblem-solving attempt process. Specific instructions:
1. Each section should be a standalone and complete problem-solving approach or effort.
2. For each section, include both the starting and ending tags (the ending tag should not be earlier than the starting tag). Additionally, provide brief summary title of the section.
3. Present your output in this format: <<start tag>> <<end tag>> [Briet descri pt on]. The end tag should be the same as or later than the start tag of the section, and the start tag of the next section should follow directly after the end tag of the previous section. \n Do not output any other text or explanation.
33

---

Published as a conference paper at ICLR 2026
Problem: {question}
Response: fanswer)
Present your output in this format: <<start tag>> <<end tag>> (Brief description]. The end tag should be the same as or later than the start tag of the sec- tion, and the start tag of the next section should follow directly after the end tag of the previous section. Do not output any other text or explanation.
Prompts K.6: LLM Prompts For Detecting The First Correct Answer
You are precise analysis assistant for graph theory problems. Your task is strictly judge whether the provided reasoning segment contains an explicitly stated final answer that matches the given final answer. Given the following graph problem, segment of reasoning process, and the final answer that was ultimately provided, please determine whether this segment already contains the final answer.
The final answer is: {final.answer, Problem: {question} Reasoning segment: (segment}
Only output YES the final answer is explicitly presented and clearly identified in this segment (e.g., by phrases like "the answer is." "thus," "therefore." "in conclusion," etc.), not just mentioned as part of intermediate reasoning. If the final answer is not explicitly stated as conclusion in this segment, output NO. Do not provide any explanation.
Prompts K.7: LLM Prompts For Categorizing Response Segments
You are an expert in analyzing text relationships and functions. Your task is to strictly classify the function of Segment B in relation to Segment A, according the provided definitions. Always output only the corresponding option without any additional explanation or commentary.
Given two text segments, A and B, determine the function of B in relation to A. There are three possible options:
1. I.Self-reflection: B serves to evaluate verify the correctness of A. 2.Strategy shift: B serves to alter or adjust the strategy presented in A.
3.None: B has clear functional relationship to A, serves a different purpose not covered by the above categories.
Output only one the following options without any explanation: Self-reflection, Strategy shift, None.
Segment A: (segment_a]
Segment B: {segment.bl
Prompts K.8: LLM Prompts For Identifying The Conclusive Answer Segment
Given two text segments, and B, where is labeled as "[label}", determine if B is an effective addition to A.
For a segment to be effective:
If labeled as "Self-reflection":: should effectively evaluate or verify the correctness of
If labeled as "Strategy shift"": B should effectively alter adjust the strategy presented in
A
If labeled "None": B has clear functional relationship A, serves different purpose not covered by the above categories.
Please analyze the relationship between and B and determine:
1. Is B effective addition to A given its label? (Yes/No)
2. What your confidence in this judgment? (High/Mediuum/Lox)
34

---

Published as a conference paper at ICLR 2026
Output your judgment in the following format:
Effectiveness: [Yes/No] Confidence: [High//eeium//Low)
Segment A: {segment_a]
Segment B: (segment.b)
K.2 RESPONSE REFORMATION
Original Response
Reformatted Response
To desermite the steet with the "Feaximmm number ccmmationn" we need to court how many "t each arer imelvedi in. wikk Strp-hy-stgr
contactiona"
We am givee lot of enate and lie imtmociinss (which neprosan connectunee hawween drcct))
Sep--by-tep.
obke Stcca:
of (shich
Antonto Garhsoas
Giovanii Aldici
Giaseppe Begaera (Oniited)
other luness ecious (contections bet steets::
Va Cretaacn
Vix Artoala Galbase and Giovanii Aldie
Aldai
Via Artono Garbasse and Guseeppe Begnera
Via Baggon (Omittal)
Vis Artonio Garfasse and Onio Cortiao (Ohmite))
Intencctions
wlkk comrecttiin per
Garfesso Giovarn A'ini
**iiu Amiznio Cerbaaa
Vis Astorio Garhonuo and Via Gisoppe Vi Assorio Gerbonoo and Vos Ona Maro Cerhino
Imnreeete Girvanni Akimi, Via Gitaczpe Bagren, Via
(Omined)
ccemoctious**
[Sccin 2p Counting Connectiom for Each Street des Couzt connetions per scratret: 1. VVa Arienio Garbaaa"
Mactliao,
Francesso Grandd, Cardano
lngesecta wal.. Via Giovanzi Aldri, Via Giuicype Bigners, Via Ose Mario Cerbano
Glaseppe Begnesa**
**3 coltections*
2. -eViia Giovani Giovani Aldin!
Invemiets with: Vis Amonio Gurbasen, Vla Dumiano Maciiioo, Via Pranzora Grimaaii, Via Cunobrre-Crnbos
"*4cnctccioone" (Ommied)
connection**
[Sectiu H:: Concluiion and Fizal Asenur d4s Cunclasim:
Ausear
The steets wilk the *Puuainaus sumber of consoctiuzs" are **Via Francssoo Ginald)* and **Via Gerolano Cariano" each will connectinn""
(boxed(6)
net Fual Answer:
(oaee
Figure 22: Example of Response Reformation.
35

---

Published as a conference paper at ICLR 2026
K.3
CASE STUDIES
Case Study K.1: Response of Qwen3-32B on a DistanceK Task
Problem:
You are given an undirected graph representing the London street network, where nodes represent streets and edges represent intersections. The distance between two directly connected nodes is 1. Given a street Westwell Road Approach, find all streets that are exactly distance away from the street.
Streets in the network: Cleveland Road, Colmer Road, Danbrook Road, Streatham High Road, Penistone Road, Arragon Gardens, Ellison Road, Tankerville Road, Westwell Road, Westwell Road Approach, Buckleigh Road, Greyhound Lane, Guildersfield Road, Kempshott Road, Northanger Road Intersections in the network: Cleveland Road and Ellison Road, Colmer Road and Danbrook Road, Colmer Road and Ellison Road, Colmer Road and Streatham High Road, Danbrook Road and Ellison Road, Streatham High Road and Arragon Gardens, Streatham High Road and Greyhound Lane, Streatham High Road and Guildersfield Road, Streatham High Road and Kempshott Road, Streatham High Road and Penistone Road, Streatham High Road and Westwell Road Approach, Penistone Road and Guildersfield Road, Arragon Gardens and Ellison Road, Ellison Road and Greyhound Lane, Ellison Road and Guildersfield Road, Ellison Road and Kempshott Road, Tankerville Road and Greyhound Lane, Tankerville Road and Guildersfield Road, Tankerville Road and Kempshott Road, Westwell Road and Greyhound Lane, Westwell Road and Northanger Road, Westwell Road and Westwell Road Approach, Buckleigh Road and Greyhound Lane, Buckleigh Road and Guildersfield Road, Buckleigh Road and Kempshott Road, Buckleigh Road and Northanger Road, Greyhound Lane and Northanger Road Please find the streets in distance 4 from the street Westwell Road Approach and output the number of these streets. Present your answer in the following format: \boxed in). n is the number of these streets
Response:
[Section 1]: Initial Understanding and Setup
The task is to find all streets exactly 4 units of distance from Westwell Road Approach in the given undirected graph, where each intersection represents an edge of distance 1. An adjacency list is helpful way to represent the graph structure. Westwell Road Approach is the starting point (level 0). Based on the intersection list, Westwell Road Approach is directly connected to Streatham High Road and Westwell Road, making them the streets at distance (level 1).
[Section 2]: BFS Traversal to Identify Level 3 Nodes
To find the nodes at distance 2, we find the neighbors of the level 1 nodes. The neighbors of Streatham High Road are Colmer Road, Penistone Road, Guildersfield Road, Greyhound Lane, Kempshott Road, and Arragon Gardens. The neighbors of Westwell Road are Greyhound Lane and Northanger Road. The unique set of these neighbors forms level 2: Colmer Road, Penistone Road, Guildersfield Road, Greyhound Lane, Kempshott Road, Arragon Gardens, and Northanger Road. To find level 3, we find the neighbors of all level 2 nodes that have not been visited. This process yields unique set of new nodes for level 3: Danbrook Road, Ellison Road, Tankerville Road, and Buckleigh Road.
[Section 3]: Re-examination of Level 3 and 4 Nodes Now, to find level 4, we must find the neighbors of the level 3 nodes (Danbrook Road, Ellison Road, Tankerville Road, Buckleigh Road) that have not already been assigned level. The neighbors of Danbrook Road are Colmer Road (level 2) and Ellison Road (level 3), so no new nodes are found. The neighbors of Tankerville Road are Greyhound Lane, Guildersfield Road, and Kempshott Road, all of which are in level 2. The neighbors of Buckleigh Road are Greyhound Lane, Guildersfield Road, Kempshott Road, and Northanger Road, all of which are in level 2. For Ellison Road, we must check its intersections. Ellison Road is connected to: Colmer Road and Ellison Road, Danbrook Road and Ellison Road, Arragon Gardens and Ellison Road, Ellison Road and Greyhound Lane, Ellison Road and Guildersfield Road, Ellison Road and Kempshott Road. (This list of Ellison Road's neighbors incomplete; it omits the intersection with Cleveland Road, which is explicitly provided in the problem description. graph memorization error)
All of the listed neighbors for Ellison Road are in either level 2 or level 3. So no new nodes here. So indeed, no new nodes. That would mean that level 4 is empty.
(This conclusion is incorrect because the algorithm failed to process the edge between Ellison
36

---

Published as a conference paper at ICLR 2026
Road (level 3) and Cleveland Road. This failure to traverse valid edge results in Cleveland Road being missed. - omission) [Section 4]: Final Verification and Conclusion
The analysis incorrectly concludes that since all neighbors of level 3 nodes are already in levels 2 or 3, there are no nodes at distance The response attempts to manually trace paths but fails to find a path of length 4 due to the previously forgotten graph connection. Therefore, there are no nodes at distance 4. So the answer is O.
(This final judgment is incorrect. The BFS algorithm executed on incomplete graph, leading to the false conclusion that level 4 is empty when actually contains one node, Cleveland Road. condition misjudgment)
Case Study K.2: Response of Qwen3-32B on a Minimum Spanning Tree Task
Problem:
You are required to solve the Minimum Spanning Tree Problem for an undirected street network. In this network, nodes represent streets (e.g., street IDs) and edges represent intersections between streets. The weight of each edge is the distance between two streets.
Streets in the network: Carbeen Road, Eucalyptus Drive, Erawar Close, Nicholson Avenue, Howes Close, Fairy Dell Close, Elouera Road, Booleroo Place, Higgins Place, Keys Close, Russell Crescent, Coppsleigh Close, Gundy Place, Boree Place, Brigalow Place, Baroona Road, Eastview Road, Mason Lane, Phillips Lane, Ulric Lane, Coral Heath Avenue, Brushtail Court, Hibbertia Place, Corang Road, Honeycup Close, Rocklily Avenue, Billarga Road, Pittwater Road, Apanie Place, Duneba Drive, Silver Crescent, Colin Place, Kimba Close, Western Crescent, Old Glenfield Road, Warrigal Drive, Coora Road, Namoi Road, Nulgarra Street, Strathallen Avenue, Settlers Way, Euroka Road, Bottle Brush Road, Gum Blossom Drive, Barkala Place, Quarter Sessions Road, Dryden Avenue, De Saxe Close, Lynrob Place, Timbarra Road Intersections between these streets: Carbeen Road and Duneba Drive (weight: 3). Carbeen Road and Elouera Road (weight: 3), Eucalyptus Drive and Billarga Road (weight: 3), Eucalyptus Drive and Boree Place (weight: 9). Fucalyptus Drive and Corang Road (weight: 3), Eucalyptus Drive and Flouera Road (weight: 9), Erawar Close and Quarter Sessions Road (weight: 4), Nicholson Avenue and Quarter Sessions Road (weight: 6). Howes Close and Quarter Sessions Road (weight: 1), Fairy Dell Close and Quarter Sessions Road (weight: 5), Elouera Road and Duneba Drive (weight: 5), Booleroo Place and Corang Road (weight: 6). Higgins Place and Keys Close (weight: 3), Higgins Place and Quarter Sessions Road (weight: 4). Higgins Place and Russell Crescent (weight: 9). Russell Crescent and Quarter Sessions Road (weight: 6), Coppsleigh Close and Corang Road (weight: 2), Gundy Place and Duneba Drive (weight: 10), Boree Place and Duneba Drive (weight: 1), Brigalow Place and Duneba Drive (weight: 1), Baroona Road and Eastview
Road (weight: 2). Baroona Road and Mason Lane (weight: 2). Baroona Road and Namoi Road
(weight: 8). Baroona Road and Nulgarra Street (weight: 4), Baroona Road and Phillips Lane
(weight: 7), Baroona Road and Pittwater Road (weight: 9), Baroona Road and Quarter Sessions
Road (weight: 9), Baroona Road and Strathallen Avenue (weight: 5), Baroona Road and Ulric Lane (weight: 1), Eastview Road and Pittwater Road (weight: 3), Eastview Road and Quarter Sessions Road (weight: 2), Mason Lane and Namoi Road (weight: 2), Coral Heath Avenue and Hibbertia Place (weight: 6), Coral Heath Avenue and Honeycup Close (weight: 7), Coral Heath Avenue and Quarter Sessions Road (weight: 1), Coral Heath Avenue and Rocklily Avenue (weight: 1), Brushtail Court and Old Glenfield Road (weight: 5), Brushtail Court and Quarter Sessions Road (weight: 3), Corang Road and Billarga Road (weight: 6), Corang Road and Kimba Close (weight: 5), Corang Road and Quarter Sessions Road (weight: 4), Pittwater Road and Quarter Sessions Road (weight: 6), Apanic Place and Duneba Drive (weight: 10), Duneba Drive and Euroka Road (weight: 6), Duneba Drive and Quarter Sessions Road (weight: 7), Silver Crescent and Coora Road (weight: 6). Silver Crescent and Quarter Sessions Road (weight: 1), Colin Place and Dryden Avenue (weight: 9), Colin Place and Quarter Sessions Road (weight: 10), Western Crescent and Quarter Sessions Road (weight: 5), Old Glenfield Road and Quarter Sessions Road (weight: 6), Warrigal Drive and Quarter Sessions Road (weight: 7), Coora Road and Barkala Place (weight: 9), Settlers Way and Quarter Sessions Road (weight: 10), Bottle Brush Road and Gum Blossom Drive (weight: 7), Bottle Brush Road and Quarter Sessions Road (weight: 4), Gum Blossom Drive and Quarter Sessions Road (weight: 10), Barkala Place and Quarter Sessions Road (weight: 7), Quarter Sessions Road and De Saxe Close (weight: 5), Quarter Sessions Road and Lynrob Place (weight: 5), Quarter Sessions Road and Timbarra Road
37

---

Published as a conference paper at ICLR 2026
(weight: 6), De Saxe Close and Lynrob Place (weight: 1), De Saxe Close and Timbarra Road (weight: 4). Identify the minimum spanning tree of this network. The minimum spanning tree is a subset of edges in connected, weighted graph that connects all the vertices together with the smallest possible total edge weight and without any cycles. Present your answer in the following format: \boxed [n), where is the sum of the weights of the edges in the minimum spanning tree.
Response:
[Section I]: Initial Thoughts and Edge Listing
To solve this Minimum Spanning Tree (MST) problem, will use Kruskal's algorithm, which involves sorting all edges by weight and adding them to the tree if they do not form a cycle. I will begin by listing and sorting the edges based on their weights. The edges with a weight of are: Boree Place Duneba Drive, Brigalow Place Duneba Drive, Howes Close Quarter Sessions Road, Baroona Road- UIric Lane, Coral Heath Avenue Rocklily Avenue, Coral Heath Avenue Quarter Sessions Road, Silver Crescent Quarter Sessions Road, and De Saxe Close Lynrob Place. The edges with weight of 2 are: Coppsleigh Close Corang Road, Baroona Road- Fastview Road, Baroona Road- Mason Lane, Fastview Road- - Quarter Sessions Road, and Mason Lane - Namoi Road.
[Section 2]: First Attempt at MST Calculation
I will now apply Kruskal's algorithm. First, select all edges with weight 1, which can all be added without creating cycles. Next, I process the five edges with weight 2, all of which are safe to add. The total weight so far is 16. I then add all six edges with weight 3, bringing the total weight to 34. Next, I process edges with weight 4. So total weight 4 edges: 4 edges? (This count is incorrect. The algorithm fails to include all edges of weight 4 from the problem description, specifically missing Higgins Place- QSR and De Saxe Close Timbarra Road. graph memorization error) I add the four identified edges, bringing the total weight to 50. I then process the edges with weight So all six weight edges can be added. (This count also incorrect. The algorithm misses the edge Fairy Dell Close QSR (weight 5). omission) This brings the total weight to 80.
Next, process the edges with weight 6. So seven edges with weight 6. (This count is incorrect. The algorithm fails to identify all edges with a weight of 6. missing several connections to Quarter Sessions Road and others. - graph memorization error) correctly determine that the edge Corang Road Billarga Road should be skipped as it forms cycle. However, I incorrectly determine that the edge Old Glenfield Road- QSR also creates a cycle based on a faulty state. So from the seven weight 6 edges, we can add Russell Crescent QSR, Piutaatr Road- QSR, Duneba Drive- Euroka Road, Silver Crescent- - Coora Road, Warrigal Drive - QSR. (This step contains multiple errors. The list of weight 6 edges is incomplete, and the cycle detection for Old Glenfield Road- QSR is based on a flawed understanding of the current graph state. state update error) This adds 30 the total, making it 110. The process continues in this manner, with accumulating errors. [Section 3]: Identifying and Correcting Mistakes in Weight 6 Edges
now recognize that my previous analysis was flawed. I missed the edge Fairy Dell Close QSR (weight 5). So during the weight 5 step. I should have added seven edges instead of six. (This section demonstrates the algorithm's 's confusion and repeated errors. While correctly identifies one missed edge, its subsequent recalculations remain flawed, leading to more incorrect states. This repetitive and confusing correction process is a form of redundancy. - redundancy) then re-evaluate the weight 6 edges and realize I also missed Booleroo Place Corang Road, Quarter Sessions Road- Timbarra Road, and Coral Heath Avenue - Hibbertia Place. Ah, here's another mistake! (The repeated self-correction and recalculation indicate persistent failure to maintain correct state of the graph's 's connected components. state update error) After several rounds of corrections, I still have an incomplete and inaccurate picture of the graph. [Section 4]: Final MST Calculation and Verification
After realizing multiple oversights, I will restart the calculation. Weight edges) + Weight 2 (5 edges) + Weight 3 (6 edges)= 34. Next are the weight 4 edges. Weight 4 edges: 5+4=20 -ttta 54. (This is incorrect. There are six edges with weight 4 in the graph. The algorithm omits the edge De Saxe Close- Timbarra Road (weight 4). graph memorization error) Next are the weight edges. There are seven, which are all added, for a total of 35, bringing the sum to 89. Next are the weight 6 edges. Weight 6 edges: 9*6=54 total 143. (This step contains two errors. First, the algorithm incorrectly includes the edge Warrigal Drive QSR, which has a weight of 7, not 6. graph memorization error) (Second, this incorrect inclusion leads to faulty sum for this step and an incorrect running total. - state update error) Next are the weight 7 edges.
38

---

Published as a conference paper at ICLR 2026
Finally, to connect the remaining components, add edges with weights 9 and 10. Total sum: 6+ 6+10--18--00+33554-355----3 217.
Case Study K.3: Response of Qwen3-32B on Maximum Triangle Sum Task
Problem:
You required to solve the Maximum Triangle Sum Problem for an undirected wikipedia network. In this network, nodes represent wikipedia articles and edges represent hyperlinks between articles. Each node is assigned weight. Your objective is to find the triangle with the maximum sum of weights of its three nodes.
Articles in the network: Montehelluna (weight: 1), Massimo Mascioletti (weight: 8), Gianluca Faliva (weight: 4), Eppelheim (weight: 7), United States (weight: 6), Alberto Rebecca (weight: 10), October 15 (weight: 6). Rugby union (weight: 1), Italy (weight: 9). List of football clubs in Italy (weight: 9). Manuel Dallan (weight: 8), Brad Johnstone (weight: 1) Hyperlinks between these articles: Montebelluna and List of football clubs in Italy, Montebelluna and Eppelheim, Montebelluna and Alberto Rebecca, Montebelluna and Italy, Montebelluna and Manuel Dallan, Massimo Mascioletti and Brad Johnstone, Massimo Mascioletti and Gianluca Faliva, Gianluca Falíva and Italy, Gianluca Faliva and Brad Johnstone, Gianluca Faliva and Manuel Dallan, Gianluca Faliva and Rugby union, Eppelheim and Italy, United States and Italy, United States and October 15, Alberto Rebecca and Italy, October 15 and Italy, October 15 and Manuel Dallan, Rugby union and Manuel Dallan, Italy and Manuel Dallan. Identify the triangle with the maximum sum of weights of its three nodes in this network. Present your answer in the following format: \boxed n.. n is the maximum sum of weights of the triangle.
Response:
[Section 1]: Initial Setup and Problem Understanding
Okay, let's 's try to solve this problem. The task is to find the triangle (a set of three nodes all connected to each other) in the given undirected graph that has the maximum sum of their node weights. The nodes are Wikipedia articles with specific weights, and the edges are hyperlinks between them. First, I need to list out all the nodes and their weights to have a clear view. Let me jot them down: Montebelluna: 1, Massimo Mascioletti: 8, Gianluca Faliva: 4, Eppelheim: 7, United States: 6, Alberto Rebecca: 10, October 15: 6, Rugby union: 1, Italy: 9, List of football clubs in Italy: 9, Manuel Dallan: 8, Brad Johnstone: 1. Now, the edges (hyperlinks)
given. Let me list them out to see which nodes are connected. Each edge connects two nodes, and for a triangle, each pair in the three-node set must be connected. The edges provided are: Montebelluna List of football clubs in Italy, Montebelluna Eppelheim, Montebelluna Alberto Rebecca, Montebelluna Italy, Montebelluna Manuel Dallan, Massimo Mascioletti Brad Johnstone, Massimo Mascioletti Gianluca Faliva, Gianluca Faliva- - Italy, Gianluca Faliva Brad Johnstone, Gianluca Faliva Manuel Dallan, Gianluca Faliva- Rughy union, Eppelheim Italy, United States Italy, United States- October 15, Alberto Rebecca- Italy, October 15 Italy, October 15 Manuel Dallan, Rugby union- Manuel Dallan, Italy- Manuel Dallan.
[Section 2]: Identifying High-Weight Nodes and Initial Triangle Candidates
Now, need to find possible triangles. A triangle three nodes where each pair connected by an edge. So, for each set of three nodes, check if all three possible edges exist between them. But since there are 12 nodes, checking all combinations might be tedious, but maybe we can focus nodes with higher weights because we want the maximum sum. High-weight nodes more likely to be part of the maximum triangle. Looking at the weights, the highest are: Alherto Rebecca: 10, Italy: List of football clubs in Italy: 9, Manuel Dallan: 8, Massimo Mascioletti: 8, United States: 6 (but lower than others), Others are 6, 4, 1, etc. So let's look for triangles involving Alberto Rebecca (10) and Italy (9) since those are high. Looking at the edges connected to Alberto Rebecca. From the edges, there's an edge between Montebelluna and Alberto Rebecca (edge 3), and edge 15: Alberto Rebecca Italy. So there's 's an edge between Montebelluna and Italy, then Montebelluna, Alberto Rebecca, Italy would form triangle. Looking at edge 4: Montebelluna Italy. Yes! So Montebelluna, Alberto Rebecca, Italy form a triangle. Their weights are 1 + 10 + 9 20. Is there a better one? Another high-weight node is Italy (9). Let's check other nodes connected to Italy. Italy is connected to: Montebelluna (cdge 4), Gianluca Faliva (edge 8), Eppelheim (edge 12), Alberto Rebecca (edge 15), United States (edge 13), Manuel Dallan (edge 19). So any triangle involving Italy and two other nodes connected to Italy. Let's s see. For example, if there's 's a node
39

---

Published as a conference paper at ICLR 2026
connected to both Italy and another node connected to Italy. Let's check combinations. Take Gianluca Faliva (4) connected to Italy (edge 8). What other nodes connected to Italy are connected to Gianluca Faliva? Looking at Gianluca Faliva's edges: Edges connected to Gianluca Faliva: 7 (Massimo Mascioletti), 8 (Italy), 9 (Brad Johnstone), 10 (Manuel Dallan), 11 (Rugby union). So connected to Italy and Manuel Dallan, Brad Johnstone, etc. Now, is there a connection between Italy and Manuel Dallan? Yes, edge 19. Also, is there a connection between Gianluca Faliva and Italy (edge 8) and between Gianluca Faliva and Manuel Dallan (edge 10), and between Italy and Manuel Dallan (edge 19). So the triangle Gianluca Faliva, Italy, Manuel Dallan. Their weights: 4
-9+ + 8 = 21. That's higher than 20.
[Section 3]: Checking Other High-Weight Node Combinations for Better Triangles
Another candidate: Italy, United States, and October 15. The edges are United States Italy (edge 13), United States October 15 (edge 14), and Italy October 15 (edge 16). So that's a triangle. Their weights: 6 (US) 9 (Italy) + 6 (October 15) = 21. Same as the previous 21. So same sum. Now, what about the triangle Gianluca Faliva, Italy, Manuel Dallan (sum 21) and the triangle United States, Italy, October 15 (sum 21). Are there any triangles with higher sums? Let's check other high-weight nodes. For example, Manuel Dallan (8) and Massimo Mascioletti (8). Are they connected? Let me check. Massimo Mascioletti is connected to Brad Johnstone (edge 6) and Gianluca Faliva (edge 7). Gianluca Faliva is connected to Manuel Dallan (edge 10). But is there a direct connection between Massimo Mascioletti and Manuel Dallan? Not that can see. So no triangle there. What about Massimo Mascioletti (8), Gianluca Faliva (4), Brad Johnstone (1). They form a triangle? Let's check edges: Massimo Mascioletti is connected to Gianluca Faliva (edge7) and Brad Johnstone (edge6). Gianluca Faliva is connected to Brad Johnstone (edge9). So yes, triangle Massimo Mascioletti, Gianluca Faliva, Brad Johnstone. Sum is 8 + 4 + 1= 13. Not better. Another weight node is List of football clubs in Italy (9). Let's check it's part of a triangle. The only edge connected to it is Montebelluna (edgel). 1). Are there other edges? Let me check. The given edges don't 't show any other connections for List of football clubs Italy. So unless Montehelluna is connected to another node that's is connected to List of football clubs in Italy, but since Montebelluna is connected to List of football clubs in Italy and to Italy, but Italy isn't connected to List of football clubs in Italy? Let me check. The edges don't 't mention an edge between Italy and List of football clubs in Italy. So the triangle would need Montebelluna, List of football clubs in Italy, and another node connected to both. But since List of football clubs in Italy is only connected to Montebelluna, no triangle possible here. What about the triangle involving Alberto Rebecca (10), Italy (9), and someone else. For example, Alberto Rebecca is connected Montebelluna (edge3) and Italy (edge15). If Montebelluna is connected to Italy (edge4), which it is. So that triangle is already considered (sum 20). Are there others? For example, Alberto Rebecca connected to someone else who's connected to Italy. Let's see. Suppose Alberto Rebecca is connected another node connected Italy. But in the edges given, Alberto Rebecca is only connected to Montebelluna and Italy. So no other connections. So no other triangles involving Alberto Rebecca except with Montebelluna and Italy. Another candidate: Manuel Dallan (8), Italy (9), and someone else. Let's see. For example, if there's s node connected to both Manuel Dallan and Italy. Let's check. October 15 is connected to Italy (edge16) and to Manuel Dallan (edge So the triangle Italy, Manuel Dallan, October 15. Which Rugby union is connected to Manuel Dallan (8)ge18). but is Rugby union connected to Italy? No. So no triangle there. What about other combinations? Let's check if there's a triangle with higher than 21. Let's think about nodes with high weights. The highest weights are 10, 9, 9, 8, 8. Let's see if there's a triangle with two 9s and an 8. For example, Italy (9), List of football clubs in Italy (9), and someone connected to both. Are they connected? The edges don't mention a direct link between Italy and List of football clubs in Italy. So unless there's 's another node connected both. Let's see. Montebelluna is connected to both List of football clubs in Italy (edgel) I) and to Italy (edge4). So the triangle would be Montebelluna (1), Italy (9), List of football clubs in Italy (9). (This is incorrect. The response correctly identifies that Montebelluna is connected to both Italy and List of football clubs in Italy, but it fails to verify the third required edge between Italy and List of football clubs in Italy before declaring it triangle. This is a graph memorization error).
already considered (sum 21). Also,
Sum is 1 + 9 + 9 19, which is less than 21.
[Section 4]: Exhaustive Search for All Possible Triangles and Verification of Maximum Sum What about the triangle between Italy (9), Eppelheim (7), and someone else? For example, Eppelheim is connected to Italy (edge12) and to Montebelluna (edge2). But Montebelluna isn't connected to Italy except through edge4. Wait, Montebelluna is connected to Italy (edge4), so
40

---

Published as a conference paper at ICLR 2026
the triangle would be Montebelluna (1), Eppelheim (7). Italy (9). Sum is 1+7+9=17. Not better. Another candidate: United States (6), Italy (9), and someone else. The only other connection is October 15 (edge14 and 16). So the triangle is already considered. Is there a triangle with three high-weight nodes? For example, Italy (9), List of football clubs in Italy (9), and someone else. But they aren't connected. So no. What about Manuel Dallan (8), List of football clubs in Italy (9), and someone connected to both? List of football clubs in Italy is only connected to Montebelluna (1), and Manuel Dallan is connected to Montebelluna (edge5). So the triangle would be Montehelluna (1), List of football clubs in Italy (9), Manuel Dallan (8). (This is incorrect. The response finds that Montebelluna is common neighbor to both 'List of football clubs in Italy' and 'Manuel Dallan' but incorrectly assumes this forms a triangle without verifying the missing third edge between 'List of football clubs in Italy' and 'Manuel Dallan' graph memorization error). Sum is 149+8=18. Not better. Another possibility: Is there a triangle involving Alberto Rebecca (10), Manuel Dallan (8), and someone else? Let's see. Alberto Rebecca is connected to Montebelluna (1) and Italy (9). Manuel Dallan is connected to Italy. But there's no direct edge between Alberto Rebecca and Manuel Dallan. So no triangle there. What about the triangle between Gianluca Faliva (4), Manuel Dallan (8), and Rugby union (1)? They are connected via edges 10 and 18. But is there an edge between Gianluca Faliva and Rugby union? Yes (edge I I). And between Rugby union and Manuel Dallan? Yes (edge18), And between Gianluca Faliva and Manuel Dallan (edge10). So the triangle is Gianluca Faliva (4), Manuel Dallan (8), Rugby union (1). Sum is 4+8+1=13. Not better. Another check: Are there any other triangles with high sums? Let's think. For example, United States (6), Italy (9), and someone else. The only other connection is October 15 (6). So that's the triangle we already have. Sum 21. there a triangle with two 8s? For example, Massimo Mascioletti (8) and Manuel Dallan (8). But they aren't 't connected. What about Manuel Dallan (8) and someone else? Let's see. The only other node with 8 is Massimo Mascioletti (8). But no connection. So no triangle with two 8s. What about the triangle between Manuel Dallan (8), Italy (9), and another node with 8? For example, if there's s node connected to both Manuel Dallan and Italy. But the only such node is Gianluca Faliva (4) or October (6). So no. So far, the maximum sum is 21, achieved by two different triangles: (Gianluca Faliva, Italy, Manuel Dallan) and (United States, Italy, October 15). Are there any other triangles with sum 21 or higher? Let me check another angle. Let's look for all triangles and compute their sums. First, list all possible triangles. Since this is time-consuming, but maybe can find all possible triangles by looking at each node's connections. Starting with Italy (9), since it's connected to many nodes. Let's check all pairs of nodes connected Italy and see if they are connected to each other. Italy is connected to: Montehelluna (M), Gianluca Faliva (G), Eppelheim (E), Alberto Rebecca (A), United States (US), October 15 (O), Manuel
Dallan (D). So for each pair among these, check if they are connected. Check pairs: M and G: Are Montebelluna and Gianluca Faliva connected? No. The edges connected to Montebelluna are List of football clubs in Italy, Eppelheim, Alberto Rebecca, Italy, and Manuel Dallan. So no direct edge between M and G. M and E: Montebelluna and Eppelheim are connected (edge2). So the triangle M, E, Italy. Sum is 1+7+9=17. M and A: Montebelluna and Alberto Rebecca are connected (edge3). So triangle M, A, Italy. Sum 1+ 10+9=20. M and US: Are Montebelluna and United States connected? No. So no triangle. M and O: No connection between Montebelluna and October 15. M and D: Montebelluna and D are connected (edge5). So triangle M. D, Italy. Sum 1 1+8+9=18. G and E: Are Gianluca Faliva and Eppelheim connected? No. So triangle. G and A: Gianluca Faliva and Alberto Rebecca? No. No edge between them. G and US: Gianluca Faliva and United States? No. G and O: Gianluca Faliva and October 15? No. G and D: Gianluca Faliva and D are connected (edge 10). So triangle G. D, Italy. Sum 4+8+9=21. This is one of the candidates. E and A: Eppelheim and Alberto Rebecca? No. No edge between them. E and US: Eppelheim and US? No. E and O: No. E and D: No. A and US: Alberto Rebecca and US? No. A and O: No. A and D: No. US and O: Yes, connected via edge 14. Also, US and Italy (edge13), O and Italy (edge 16). So triangle US, O. Italy. Sum 6+6+9=21. US and D: Are US and D connected? No. So no triangle. O and D: Yes, connected via 1d So triangle O, D, Italy (already considered). So from Italy's connections, the triangles with sum 21 are: G (4), D (8), Italy (9): sum 21, US (6), (6), Italy (9): sum 21, Now check other nodes not connected to Italy. For example, check if there are triangles among other nodes. For example, check Gianluca Faliva's connections. He is connected to Massimo Mascioletti (Masc), Brad Johnstone (B), Manuel Dallan (D), Rugby union (R), and Italy (I). Check pairs among these: Masc and B: connected via edge6? Yes. Masc and Gianluca (edge7), B and Gianluca (edge9). Also, Mase and B are connected (edge6). So triangle
41

---

Published as a conference paper at ICLR 2026
Masc, B, Gianluca. Sum 8+1+4=13. Masc and D: Are they connected? No. Masc is connected to Gianluca and B, but not directly D. So no. Masc and R: No. B and D: connected via edge9 (B and Gianluca) and edge 10 (Gianluca and D). But B and D? No. So no triangle. B and R: No. D and R: connected via edge18 18 (D and R). But Gianluca and R are connected (edgel1). So triangle Gianluca (4), D (8), R (1). Sum 4=8+ Other combinations? No. Check Manuel Dallan's ' connections: Italy, October 15, Rugby union, Montebelluna. Check any of those form triangles not involving Italy. For example, October 15 and Rugby union? No. October 15 and Rugby union are not connected. So no. Check October 15's connections: United States, Italy, Manuel Dallan. already considered. Check other nodes. For example, Massimo
The triangle US-Italy-O15 Mascioletti (8) connected to Brad Johnstone (1) and Gianluca (4). No other connections. No triangles. Alberto Rebecca (10) connected Montebelluna (1) and Italy (9). No other connections. So no other triangles. List of football clubs in Italy is only connected to Montebelluna. So no triangles. Eppelheim is connected Montebelluna and Italy. No other connections. So other triangles. United States is connected to Italy and October 15. No other connections except those. Rugby union is connected to Gianluca and Manuel Dallan, No other connections. all possible triangles have been checked. The maximum sum is 21.
42


Reviews:
[{"review_id": "PQWA0wxJFz", "reviewer": "Reviewer_vGuw", "summary": "The paper introduces **GRALGOBENCH**, a benchmark of nine graph-algorithm tasks spanning three “reasoning” categories Enumeration, Exploration, and Intuition and scales them across six graph sizes to stress LRMs’ long-context abilities. The headline claims are: (i) accuracy collapses as graphs grow (below ~50% beyond 120 nodes), and (ii) LRMs “over-think,” producing long, redundant traces; the authors analyze this by partitioning traces via high-entropy tokens like *wait*, *but*, *so*.", "questions": "* Line 241: **“Minimum Spinning Tree” → “Minimum *Spanning* Tree”** \n* **Acronym not introduced**: Figures use **MCP**; earlier text spells out *Maximum Clique Problem* without defining “(MCP)”. Define on first use.  \n* **Awkward phrasing**: “We enforce LRMs to output their final answers in the \\boxed{} format.” → “We enforce that LRMs output…” (stylistic).", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The nine tasks are precisely specified (with optimal algorithms/complexities in the appendix), and the dataset scales graph sizes systematically (Level-1…Level-6), which is valuable for probing context-length effects in a controlled way.", "weaknesses": "1. The core taxonomy (Enumeration / Exploration / Intuition) is *empirically* assigned by first generating 100 ER instances per problem, collecting LRM responses, and then asking **Qwen-2.5-72B** to classify which algorithmic family the *responses* reflect; the team then picks 9 tasks whose “algorithms are relatively unambiguous.” This risks circularity (taxonomy depends on current LRM behaviors) and injects judge-model bias into the ground truth of the benchmark’s conceptual framing. It also undermines generality, since task selection is contingent on that filter. \n\n2. In the MST case study, nodes are *streets* and edges are *intersections* then the text states “the weight of each edge is the distance between two streets,” which is a confusing physical interpretation (intersections don’t have lengths, and “distance between streets” is ill-defined if nodes are streets). This muddles the mapping from the real network to its graph abstraction and invites ambiguity about what the algorithm is actually optimizing. \n\n3. The paper enforces a `\\boxed{}` final answer format, but some tasks (e.g., Distance Threshold) ask for a *node identifier* rather than a numeric value; exact-string matching on natural-language street names is brittle without strict canonicalization rules. The paper specifies decoding hyperparameters but does not detail robustness checks against case/spacing variants, which weakens the claim that graph tasks “enable standardized programmatic evaluation.” (Suggestion: emit canonical IDs alongside text and evaluate on IDs.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m4cCQqstLc", "reviewer": "Reviewer_8MVa", "summary": "This work introduces a new benchmark for evaluating LLM reasoning capabilities under long-context scenarios and conducts careful error analysis to study the underlying mechanism of reasoning failure in this setting. The paper's methodology involves building prompts with controllable length that each contain a problem as an instance of one of 9 algorithmic graph tasks (maximum degree node, maximum clique problem, path sum, etc.) plus a graph instance from real-world graph datasets, alongside an interesting taxonomy to categorize the required reasoning into enumeration, exploration, and intuition labels. The length is controlled either by graph size (number of nodes) or by using fixed graphs with varying node names as an alternative way of controlling the input prompt length.\n\nBy careful evaluation of their introduced dataset, alongside error analysis on generated responses, this work reveals some key findings. Both increasing the number of nodes and node name token length resulted in degraded performance consistently across a range of frontier open- and closed-source reasoning models. The error analysis contains a taxonomy of common issues found in incorrect model responses, and it identifies algorithmic execution error, graph memorization error, and excessive redundancies as the key failure modes. Moreover, their error analysis shows that intuition-driven reasoning (the greedy subset of the prompts) degrades the most as input context length grows.\n\nTo fully understand the excessive redundancies issue, the paper designs an experiment to segment the output response based on “aha moment” signals (slicing the response after finding high-entropy tokens such as “wait”, “but”, “so”). Then, it classifies these segments, concluding that most of these segments are unsuccessful attempts at self-verification that fail to detect the error in prior segments. Hence, the paper argues that unsuccessful self-verification is the main driver of the \"overthinking\" (the observed redundancy in reasoning traces).", "questions": "1.  How much can we trust the validity of Qwen-2.5-72B's responses for prompts I.4 and I.5, especially since they are also given a very long context input (possibly even larger than the input for the graph-solving problems)?\n2. Could you provide an argument for the real-world use cases of this benchmark, especially in light of the fact that these graph problems could be solved with tool calls?\n3.  Could you elaborate more on the segmentation using high-entropy tokens? How is the threshold for detecting high-entropy tokens tuned?\n\n\n\n\n**References:**\n\n[1] Tang, Jianheng, et al. \"Grapharena: Evaluating and exploring large language models on graph computation.\" arXiv preprint arXiv:2407.00379 (2024).\n\n[2] Xu, Hao, et al. \"GraphOmni: A Comprehensive and Extendable Benchmark Framework for Large Language Models on Graph-theoretic Tasks.\" arXiv preprint arXiv:2504.12764 (2025).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-written and clear, and the experiments are designed carefully (e.g., a diverse selection of open- and closed-source frontier models, a strong qualitative study, and error analysis). Moreover, the code is available, which aids in the reproducibility of the work.\n\n* **Task design:** The reasoning taxonomy is well-designed and well-motivated, categorizing reasoning types into enumeration, exploration, and intuition, which appears to be a strong differentiator compared to prior work like [1]. More importantly, the usage of an LLM-as-judge to classify the reasoning traces of models for an initial 100 graph samples is a clever design decision to assign each task to one of the reasoning labels.\n* **The evaluation error analysis reveals some impactful findings:**\n    1.  Quantifying the reasoning failure modes under long-context settings, and attributing them mainly to Algorithm Execution Errors (AEE), Graph Memorization Errors (GME), and excessive redundancy is a strong contribution.\n    2.  Identifying high-entropy tokens and using them to segment reasoning traces for detecting reasoning shifts is an interesting methodology. The key findings of this experiment are that self-verification fails most of the time to progress smoothly past errors and is highly redundant. This finding is impactful as it reveals one possible underlying failure mechanism of reasoning models, especially under highly long-context inputs.\n* While the data collection and controlled-length problem synthesis share similarities with GraphArena[1] (e.g., sharing tasks and the methodology to sample real-world graphs), and while a key finding (that increasing input length leads to performance degradation) has also been studied in [1, 2], this paper provides a key differentiation. GraphArena[1] has a very limited focus on dedicated reasoning models and only considers input graph node counts up to 50. This paper correctly indicates this is a setting where good reasoning models have already reached near-saturated performance; hence, its usage of **up to 160 nodes** is well-designed to study the limits of frontier reasoning models.\n* Using such graph problems as evaluation benchmarks is an impactful direction and is aligned with frontier labs' evaluations on long-context reasoning (e.g., OpenAI GraphWalks).", "weaknesses": "* One minor weakness is that the **fixed assignments of Enumeration, Exploration, and Intuition reasoning labels** to tasks might be slightly misleading, as models might sometimes use different reasoning to solve a task (e.g., doing Exploration instead of Intuition). While Appendix H.1 does a great job showing this issue would be rare, it also shows such an issue exists. Furthermore, these ablations are done by using an LLM-as-judge on 100 problem instances that seem to differ from the wide range of task complexity used in the final proposed dataset. Hence, the algorithm ratio as defined in Appendix H.1 might show a more uniform distribution in the actual dataset, especially for weaker and smaller open-source models.\n* While evaluating the long-context input scenario for reasoning problems is an important benchmark, the proposed evaluation seems to **slightly diverge from the realistic use case of frontier models**. It seems that all tasks in this evaluation could be handled much better with tool calls (writing code and receiving code execution results). Having extremely sophisticated short-context inputs that require a large amount of reasoning token generation (like olympiad competitions) is an alternative way of measuring long-context reasoning while keeping the input tokens fixed. Thus, I would suggest a discussion on this matter and perhaps a refinement of the introductory claim (lines 47-49) that \"First, they lack long-context evaluation: existing benchmarks predominantly use short problem texts, which cannot be easily scaled to assess LRMs’ reasoning capabilities over extended contexts.\"\n* As mentioned in this paper, as input context length grows, the performance of models degrades noticeably in correctly solving the graph problems. However, in the evaluation workflow, there are multiple LLM-as-judge calls using Qwen-2.5-72B (such as prompt I.4 for error analysis and prompt I.5 for reformatting) that seem to need to operate and reason over a potentially much larger input context compared to the original graph-solving task. Hence, **the quality of the output responses from Qwen-2.5-72B when using prompts I.4 and I.5 on an already large, long-context input problem is questionable.**\n* More discussion and illustration are needed on **how high-entropy tokens are being used for segmentation and what their failure modes are**. How likely is it that the main finding—that “ineffective self-verification is a primary driver of over-thinking in LRMs”—is the result of incorrect segmentation?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XCyoePeYId", "reviewer": "Reviewer_dfQZ", "summary": "The authors propose a new benchmark named GRALGOBENCH to evaluate the long-context reasoning ability of Large Reasoning Models (LRMs) through graph algorithm problems. Specifically, this benchmark includes three major categories of problems: Enumeration, Exploration, and Intuition. Each category is further classified into three difficulty levels: easy, medium, and hard (3*3=9 tasks), and each task is set with 6 levels based on the number of nodes and edges. Based on this benchmark, the authors conducted systematic experiments to explore the long-text reasoning ability of the current LRMs. In summary, the accuracy of LRMs in long contexts has dropped sharply. Secondly, LRMs are plagued by the phenomenon of overthinking, which is mainly caused by frequent and ineffective self-verification.", "questions": "1.\tHow consistent are the error labels across judges? It might be good to  report a human-checked agreement rate on subset samples, stratified by taxonomy/level.\n\n2.\tIn the verbosity experiments, how are node names expanded and how is the added text distributed across the prompt (e.g., per-node descriptors vs. preamble)? Can you share a few full prompts at each length?\n\n3.\tHave you tried a token-budget cap (e.g., limiting self-verification tokens) to quantify over-thinking’s cost-benefit? The efficiency plots suggest diminishing returns; an intervention study would be valuable.\n\n4.\tIn Figure 3, several curves appear to run at or below zero. Maybe tightening the y-axis limits and/or adding clipping can avoid visual ambiguity.\n\n5.\tOn transfer/generalization beyond graphs. Can you provide transfer evidence that performance and observed phenomena on this benchmark relate to broader “general reasoning” tasks? For example:\n\n(i) model-wise correlations between GRALGOBENCH scores and external benchmarks targeting long-context/general reasoning (e.g., LongBench, Needle-in-a-Haystack variants, BIG-bench Hard, GPQA, MMLU-Pro, long-form GSM8K),\n\n(ii) an intervention study showing that a method which improves GRALGOBENCH (prompting, memory limits, self-verification caps) also improves one or more non-graph long-context tasks, and/or\n\n(iii) an ablation that rephrases graph instances into equivalent textual narratives or table/tree forms to test whether the observed failures stem from graph structure per se versus generic context-length effects. If these are out of scope, please temper the generality of your conclusions accordingly.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tWell-motivated benchmark & taxonomy. The bridge from CLRS-style algorithmic families to the Enumeration / Exploration / Intuition taxonomy is clear and useful for reasoning analysis.\n\n2.\tReal-world graph sources & scaling. Instances are derived from DBLP, street networks (multiple cities), OpenFlights, Wikipedia, and DBpedia; each task is generated across six scales to modulate difficulty, supporting long-context evaluation without synthetic toy artifacts.\n\n3.\tComprehensive evaluation & clear trends. Results across both reasoning and non-reasoning models show consistent degradation with context length and with graph size, and reveal a robust hierarchy of task difficulty.\n\n4.\tThoughtful error analysis. The paper proposes a structured error taxonomy (algorithm selection vs. execution vs. output quality vs. information/memorization) and demonstrates where LRMs fail.\n\n5.\tOver-thinking analysis. The segmentation of traces with high-entropy tokens and labeling of self-reflection/strategy-shift provides evidence that “self-verification” often inflates tokens with little gain; the “outcome efficiency” plots are compelling.", "weaknesses": "1.\tLLM-as-judge dependence. Error categorization and over-thinking judgments rely on LLM pipelines. The paper would benefit from reporting inter-annotator agreement with humans on a stratified subset to quantify labeling reliability and possible bias.\n\n2.\tOn line 72 you note that GraphWalks is intended to benchmark LRMs’ long-context capabilities. Please clarify how your benchmark compares to GraphWalks in scope, task design, evaluation protocol, and key findings. In particular, explain what is novel or complementary (e.g., task families, graph sources, scaling, automatic judging, contamination checks, tool-use assumptions) and, where feasible, include a side-by-side quantitative comparison to justify the need for a new benchmark.\n\n3.\tTool-use / code execution. Many LRMs now include tool-use or code-execution modes. The benchmark fixes models to text-only. That is fair for isolating intrinsic reasoning, but the paper should discuss how results might differ under code-execution assistance and whether GRALGOBENCH can evaluate that regime.\n\n4.\tExternal validity and scope. The benchmark focuses exclusively on deterministic graph-algorithm tasks. While this is a valuable slice of reasoning, it omits other long-context regimes. Without evidence of cross-task transfer, it’s unclear whether conclusions about long-context brittleness and over-thinking generalize beyond graph-structured problems, other data modalities (tables, trees, sequences), or multilingual settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yvOSCjxDn2", "reviewer": "Reviewer_c193", "summary": "The paper proposes a benchmark for Large Reasoning Models (LRMs) that consists of questions instantiated from various graph algorithm problems. The benchmark reveals two shortcomings of state-of-the-art LRMs: poor scalability to long contexts and overthinking.", "questions": "- Can the numbers in Table 3 provide additional insights if they are grouped by computational complexity rather than graph size?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Despite the abundance of graph-based reasoning benchmarks in the literature, the idea of challenging LRMs with graph algorithm problems of varying complexity seems novel to me.", "weaknesses": "- The evaluation of the paper measures the difficulty of questions primarily by the size of their underlying graphs rather than the computational complexity of their underlying graph algorithm problems. Since the novelty of the paper lies primarily in its graph algorithm perspective, its evaluation should focus on the impact of computational complexity rather than graph size.\n- Some of the graph algorithm problems, e.g. minimum spanning tree, may not resemble questions in real life.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)