$\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning
Authors: Xiaojun Guo
Ang Li
Yifei Wang
Stefanie Jegelka
Yisen Wang
Venue: NeurIPS 2025 poster ()
Keywords: Graph
Large Language Models
Reasoning
Reinforcement Learning
Primary area: deep_learning

Abstract: Although Large Language Models (LLMs) have demonstrated remarkable progress, their proficiency in graph-related tasks remains notably limited, hindering the development of truly general-purpose models. Previous attempts, including pretraining graph foundation models or employing supervised fine-tuning, often face challenges such as the scarcity of large-scale, universally represented graph data. We introduce $\texttt{G1}$, a simple yet effective approach demonstrating that Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale LLMs' graph reasoning abilities. To enable RL training, we curate \erdos, the largest graph reasoning dataset to date comprising 50 diverse graph-theoretic tasks of varying difficulty levels, 100k training data and 5k test data, all drived from real-world graphs. With RL on \erdos, $\texttt{G1}$ obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size). RL-trained models also show strong zero-shot generalization to unseen tasks, domains, and graph encoding schemes, including other graph-theoretic benchmarks as well as real-world node classification and link prediction tasks, without compromising general reasoning abilities. Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks, which combines the strengths of pretrained LLM capabilities with abundant, automatically generated synthetic data, suggesting that LLMs possess graph understanding abilities that RL can elicit successfully. Our implementation is open-sourced at https://github.com/PKU-ML/G1, with models and datasets hosted on Hugging Face collections https://huggingface.co/collections/PKU-ML/g1-683d659e992794fc99618cf2 for broader accessibility.

G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning
Xiaojun Guo
Ang Li
Yifei Wang
Stefanie Jegelka4.3
Yisen Wang!.1
State Key Lab of General Artificial Intelligence,
School of Intelligence Science and Technology. Peking University 2 Institute for Artificial Intelligence, Peking University
MIT
'TUM
Abstract
Although Large Language Models (LLMs) have demonstrated remarkable progress, their proficiency in graph-related tasks remains notably limited, hindering the development of truly ceneral-purpose models. Previous attempts, including pre- training graph foundation models or employing supervised fine-tuning, often face challenges such as the scarcity of large-scale, universally represented graph data. We introduce G1, a simple yet effective approach demonstrating that Reinforcement Learning (RL) on synthetic graph-theoreti tasks can significantly scale LLMs' graph reasoning abilities. To enable RL training, we curate Erdös, the largest graph reasoning dataset to date, comprising 50 diverse graph-theoree difficulty levels, 100k training data and 5k test data, all drived from real-world graphs. With RL on Erdös, G1 obtains substantial improvements in graph reason- ing, where finetuned 3B model even outperforms Qwen2.5-72BB -nnttttrutttt (24x size). RL-trained models also show strong zero-shot generalization to unseen tasks, domains, and graph encoding schemes, including other graph-theoreti bench- marks as well as real-world node classification and link prediction tasks, without compromising general reasoning abilities. Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph- theoretic tasks, which combines the strengths of pretrained LLM capabilities with abundant, automatically generated synthetic data, suggesting that LLMs possess graph understanding abilities that RL can clicit successfully. Our implementation is open-sourced at wtthttt::/// /et/tggttbbb com/PKU-M//G1 with models and datasets hosted on Hugging Face collections PKU-ML/TT for broader accessibility.
tasks of varying
Introduction
Large Language Models (LLMMs) have achieved widespread success 2 13 but exhibit notable limitations in reasoning about graph-structured data, a critical capability for achieving general- purpose intelligence. Proficient graph reasoning is essential for numerous applications, yet even state-of-the-art LLMs like OpenAI's ol (3) demonstrate significant deficiencies, with reported
accuracies as low as 58.49 .99% on graph connectivity tests (55).
Initial efforts to enhance LLMs' graph understanding explored various natural language encoding schemes 5 but these yielded only modest improvements. Alternative strategies have involved
'Equal Contribution.
Coorespponding Author: Yisen Wang (yisen. wang @ @ww..ddu.u............
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Table An overview of 50 graph-theoretic tasks in our dataset Erdös (100k train, 5k test), alongside with the difficulty distribution, and the accuracy of the base model Qwen2.557BB-nnstrue and our RL-trained G1-7B model. A complete description of tasks are in Appendix K.2
Difficulty
Tasks
Ratio
Base Model Acc G1 Ace
Node Number, Dominating Set, Common Neighbur, Edge Num- her, Neighbor, BFS, Has Cycle, DFS, Minimum Spanning Tree, Edge Existence, Regular, Degree, Is Tournument, Densily
Easy
29.16%
57.16%
95.07%
Adamic Adar Index, Clustering Coefficient, Connected Compo- nent Number, Bipartite Maximum Matching. Local Connectivity, Jaccard Coefficient, Min Edge Covering, Is Eularian, Degree Centrality, Is Bipartite, Resource Allocation Index
Medium
22.91%
42.55%
88.91 %
Max Weight Matching, Closeness Centrality, Traveling Sales- man Problem, Strongly Connected Number. Shortest Path, Cen- ter, Diameter, Burycenier, Radius, Topological Sort, Periphery, Betweenness Centrality. Triangles, Average Neighbor Degree,
Hard
33.33%
18.87%
50.44%
Harmonic Centrality, Bridges
Isomophic Mapping. Global Efficiency, Maximal Independent Sel, Maximum Flow, Wiener Index, Hamiltonian Path, Min Ver-
Challenging
14.58%
3.29%
23.57 %
tcx Cover
instruction tuning 27 53 or preference tuning 3 42 on curated graph datasets. Others attempted
to build specialized graph foundation models through pretraining [28 21 26]: however, these often limited by the lack of large-scale, universal graph representations suitable for diverse graph types. Different from prior work, we believe LLMs pretrained on Internet-scale data already possess graph reasoning ability, and we can elicit it through their own trial and error without human data.
In this work, we are the first to explore the use of Reinforcement Learning (RL) to solve graph reasoning tasks. We chose graph-theoretic problems as testhed they allow direct verification of generated answers to produce based rewards for RL training, which is shown to be key for the success of DeepSeek R1 in math and coding problems [13]. We collect the largest-to-datt graph- theoretic problem set, Erdös, with either groundtruth answers or automatic verification programs. As illustrated in Table T these tasks span wide spectrum of difficulty levels, from basic graph properties like node counting to NP-hard problems such as finding the maximal independent set. Another advantage of adopting graph-theorets tasks is its circumvention of scarce numan-annotatee data; the model learns through exploration and reinforcement on synthetic tasks where ground-truth outcomes provide direct reward signals, similar to the AlphaGo-Za Zeroo paradigm [37]. Besides data construction, we also study various aspects of the training process, such as the influence of data mixture, supervised initialization, and the use of chain-of- with synthetic graph-theoretic task is powerful and scalable approach to improving graph reasoning abilities of L.LMs.
[45]. Our results confirm that RL
Our work makes the following key contributions:
We are the first to apply reinforcement learning (RL) framework to improving LLMs on graph reasoning tasks. The resulting model G1 significantly enhances the graph reasoning abilities of LLMs across a diverse set of synthetic tasks, demonstrating that appropriately finetuned LLMs can become stronger graph reasoners.
We introduce Erdös, the largest-scale and most comprehensive graph-theoretic dataset that comprises 50 distinct tasks of varying complexities, uniquely constructed from diverse real-world graphs, providing a reliable platform for training and evaluating graph reasoning.
We empirically demonstrate that G1 achieves substantial performance improvements on our Erdös benchmark, with gains of up to 46% over baseline models. Notably, our fintuned G1-7B model attains competitive performance with state-of-the-ant reasoning models like OpenAl's o3-mini and G1-3B easily rivals Qwen2.5-72B I-Intruucct by noticeable margins.
G1 models exhibit strong zero-shot generalization unseen graph tasks and domains, improving base models' performance on other graph-theoretic benchmarks (Graph Wiz and GraphArena) and real-world graphs (Cora and PubMed) without deteriorating general reasoning ability (GSM8K, MATH, and MMLU-pro), indicating a synergetic improvement of LLMs' graph reasoning abilities through RL.

---

G1 charts a data-efficient and scalable course for developing LLMs with strong graph reasoning. By demonstrating that RL can unlock latent graph understanding within general-purposs LLMs using synthetic data, our work suggests a possible paradigm shift away from reliance on heterogeneous real-world graphs build graph foundation models. This paves the way for more versatile Al systems capable of sophisticated reasoning across diverse data modalities.
2 Related Work
Graph Reasoning. Graph reasoning problems fall into two categories: domain-specific, which require understanding both graph structures and node/link attributes, e.g., node classification, link prediction, and sowledge-based QA 15 56 18]; and tomain-agnostic also called graph-theorers problems, which focus solely on structural reasoning but find a lot of practical uses in various domains, egg., shortest paths, Hamiltonian paths, graph isomorphism [50] 35]. For the latter problems that we study in this paper. people have studied the use of RL [29 40 or unsupervised learning [19], often in
conjunction with Graph Neural Networks (GNNs) 20 that align with the solution structure [51]
Yet these models are often built to solve each problem alone. Recently, Sanford et al. 34 prove and validate the priority of the transformer models compared to GNNs on complex graph reasoning tasks requiring long-range dependencies. In this work, we focus on building general general-purpose purpose graph reasoners that could solve a range of graph-theoretic problems by exploiting the strength of LLM pretraining, and find that the ability also generalizes to the former domain-specific graph tasks.
Benchmarking LLMs on Graph Reasoning. There is growing interest in evaluating LLMs' graph reasoning abilities. NI.rrahh [4]] evaluate L.LMs on graph-theoretic tasks and discover preliminary yet brittle reasoning abilities in the face of spurious correlations and large graphs. Later, GraphArena [8 and GraCoRe [55] include a broader task coverage and recently released LLMs, finding that even OpenAl ol-min- struggles a lot with complex tasks. Moreover, GraphEval2000 [46) and ProGraph [23] emphasize code-oriented problem solving using library-basee prompts, and GraphOmni [48] unify varying graph types, encodings, and prompt styles for a comprehensive evaluation. Overall, these benchmarks suggest that LLMs overall demonstrate moderate success on simple tasks but struggle with abstraction, generalization, and larger or more complex graph instances. Nevertheless, these datasets are either too small (e.g.. thousands of examples) or not diverse enough (e.g.. 8 tasks in NLGraph) for training general-purpose graph reasoners, which motivates the design of Erdōs.
Improving LLMs on Graph Reasoning. A major concern when using LLMs for graph tasks is the mismatch of data structure: L.LMs take text sequences as input, while graphs have natural order. Fatemi et al. [T analyzed different graph encoding schemes for LLMs, such as adjacency lists and real-name networks, revealing that no single strategy proved universally optimal across all tasks and models. Subsequent explorations with different linearization orders [. graph embeddings [31], or input modalities [9 have generally resulted in only modest improvements. Another thread of research proposes post-training L.MSs using instruction tuning 27 53 or preference tuning S 39 on
curated datasets of graph problems. However, the creation of diverse, high-quality instruction datasets scale is challenging and expensive and requires extra supervision. Furthermore, models trained via distillation may only learn to memorize patterns and overfit to graph tasks 4: in Section 5.2, we
show that previous instruction-tuncl models exhibit dramatic failures when generalizing to other data formats and reasoning tasks, while our RL training yields consistently better performance.
Reinforcement Learning for LLMs Reasoning. Recent advances have demonstrated that LLMs can attain strong reasoning abilities in math and coding domains through RL, with representative work like OpenAl ol [30] and DeepSeek R1 [13.. However, as discussed above, even ol struggles a lot with graph reasoning tasks (55) and it is thus yet unclear whether RL can reliably and scalably improve LLMs' graph reasoning abilities. Our findings on G1 first confirm the effectiveness of RI. on graph reasoning as well and suggest that applying RL to diverse graph-theoretic tasks with verifiable rewards is a scalable path for eliciting generalizable graph reasoning abilities of LLMs.
3 Erdōs: A Comprehensive Collection of Graph-theoretic Reasoning Tasks on Real-world Graphs
To facilitate rule-based Reinforcement Learning of LLMs (aka. Reinforcement Learning from Verifi- able Rewards (RLVR)) on graphs, we construct a diverse, large-scale collection of graph-thcoree reasoning tasks. We name it Erdōs to remember Paul Erdós, seminal figure with diverse contribu-
3

---

tions to graph theory. Compared to real-world graph tasks, these graph-theoretic tasks allow clear rule-based determination of rewards for the answers sampled from LLMs. We categorize these tasks into Easy, Medium, Hard, and Challenging, based on their inherent problem complexity as well as current L.MMs' ability solve them (see full list in Table D. For the training split, there are total of 100,000 question-answer pairs, evenly distributed across tasks with 2,000 examples each. We also reserve 5,000 test pairs with different questions for evaluation. We include detailed comparison of Erdös with other graph reasoning benchmarks in Appendix [.. Erdōs can serve as a dataset for training LLMs as well as benchmark for evaluating LLMs graph-theoretic tasks. We will release all task prompts, problems, chain-of ofuth exemplars, and solution verification programs for public use. Below is more detailed description of the data collection process.
Graph-theoretic Tasks. We curate 50 graph-theoretic reasoning tasks available on NetworkX [14). one of the most widely used library for graph processing, and construct, as we know, the most comprehensive collection so far. In the difficulty level, the tasks vary from easy determination of graph attributes like node number counting, to well-known NP-hard problems like the traveling salesman problem. This collection includes both tasks for general graphs and tasks specific to directed graphs or weighted graphs, and covers a wide range of answer types including boolean, integer, float, node list, edge list, and node mapping.
Answer Generation. To generate the golden answer for each problem, utilize the default solvers of NetworkX to automatically solve the problem. If there are multiple solutions to each question, we use NetworkX-bars programs to verify the correctness of each generated solution. The procedure ensures rigorous rewarding attribution, avoiding both costly human labeling and potential bias and hacking brought by LLM judges.
Graph Sources.
Most previous graph-theoretic datasets benchmarks 41
27 3 consider random
graphs, following Erdós-Rényi model [10] or Barabási-Alun model 1 However, these random graph models are often far from graphs encountered in real-world practice. To mitigate this gap, utilize the real-world graphs from the Network Repository [3], the largest network repository with thousands of donations in 30+ domains. As these graphs can be very large and infeasible for LLMs, we downsample the graphs by random walk with a restart strategy, generating subgraphs with sizes from 5 to 35 nodes, following common settings in previous work [4] 55 38).
Language Encoding. There are multiple ways to translate the graph structure into languages that LLMs can understand. Previous works explore serialized formats such as adjacency matrix, edge list, or graph embeddings [I] & [53] but fail to find a consistently good method. Here, choose to describe the graph structure in unified edge list format, e.g. (1,2), (2, .)..... In later experiments of Section [52 we show that our model trained on single graph description method can even positively transfer to other formats.
4 Training LLMs to Reason on Graphs
In this section, we introduce the training pipeline that we explored for training G1. We design proper rule-based rewards for different graph tasks, while intentionally keeping the RL algorithm general and consistent with previous work. Similar to DeepSeek R1 [3]. the training of is very simple: consists of Reinforcement Learning phase for rewarding correct rollouts with the GRPO algorithm [36), and an optional SFT phase for warming up the model in the beginning (without which we call G1-Zero). We find that the SFT phase is generally beneficial for learning more challenging tasks, whose initial accuracy with the base model is close to zero
4.1 Reinforcement Learning of LLMs on Graphs
Rule-based Rewards on Graphs. We design the following rule-based outcome reward model (ORM) for our training on graph-theoretic tasks, with a combination of value match, set matching, and algorithmic verification for different problems:
Strict value matching. For tasks that have a unique ground truth value, e.g., node counting, the policy receives a reward of +1 only when the generated answer is identical to the ground truth in terms of numerical value, e.g., 0.5 and 1/2, otherwise it receives a reward of 0.
Jaccard Index for set matching. For problems whose answer is not a single value & but an unordered set, e.g., common neighbors of two nodes, the reward is defined as the Jaccard

---

Index between the generated set è and the ground truth s, i.e., Is /] š]. In this way, the model can receive intermediate rewards for imperfect solutions.
Algorithmic verification. Lastly, for problems that have multiple correct solutions (e.g.. shortest paths) and not feasible to enumerate all of them, we implement algorithmic verifiers to check correctness of the proposed solutions. For instance, we determine the validness of Hamiltonian path proposed by the policy by checking whether all the edges in the path exist and each node is visited exactly once.
RL Algorithm. Following common practice 131, we use the Group Relative Policy Optimization (GRPO) [36] algorithm for RL training. Specifically, for each question P(Q) drawn from the training set, GRPO first samples set of responses {o from the policy model. The responses receive rewards {r:);=1> which enables calculating the group relative advantages {AA))=
Ft mean (ri, (2,, ... ,ra))
A
(1)
std((ri, (2, .. .ra))
Next, the policy model Tyy is updated by maximizing the following objective:
(O)
TT(()19) Ad, clip To (oilg)
To(o: Toaa (0:10)
e, +e A1) -BiKL (TTa (
E [ )
min
where the expectation is taken over q ~ P(Q) and {o:] T (0 reference policy The (base model) prevents large deviation from the pretrained model and circumvents severe overfitting. Besides, c controls the clipping range of the probability ratios.
q). The KI. divergence the
4.2 Optional Warm-up with Supervised Fine-tuning
During RL training. we have noticed that for some challenging tasks like isomorphic mapping (see Table []. the initial accuracy of the base model is often so low that frequently end up with only incorrect rollouts, producing no useful signal for RL training. This issue can be mitigated by using stronger base model with higher initial performance; for example, R1 uses DeepSeek V3 (671B parameters) as base model, although this inevitably increases compute cost, We find that introducing a short warm-up phase with supervised fine-tuning, aimed at teaching the model basic reasoning skills before the RL phase, effectively improves overall learning efficiency. Specifically, in this paper we consider two types of supervised fine-tuning.
The first is direct supervised fine-tuning question-answer pairs (g. a), where q is the textual description of the problem and is the final answer without any intermediate reasoning steps. As discussed above, for graph-theoretic tasks, these question-ana answerr pairs can often be synthesized by programming. However, this approach does not include the reasoning steps leading to the answers, meaning we cannot use it to explicitly teach the model reasoning processes.
Direct-SFT.
CoT-SFT. Secondly, we can collect reasoning trajectories via sampling (g, e, a) triplets from another model S5 where represents the Chain-of-Though (CoT) reasoning steps natural language that lead to the final answer and use them to fine-tune the base model. Specifically, we instruct a base model to generate potential solutions for each question q, and only keep the correct responses that pass verification. This process is also called Rejection Sampling Fine-tuning (RFT) [54]. In practice, we use Qwen2.5-32BB 5-2.55----B-Intrre [32). a more capable model for generating candidate solutions more reliably, ending up with around 4,500 training examples for the SFT phase.
Experiments
5.1
Benchmarking G1 Graph-theoretic Reasoning Tasks
Setup. As shown in Table in the interest of academic compute budgets, we focus on comparing relatively small models. We include strong proprietary models (of unknown sizes) like GPT-4o-mini (non-reasoning) and OpenAl o3-mini (state-of-the-e) reasoning), open-source instruction models like Inestut-Instrruct series (3B, 7B. 72B) [32). Owen2.5-Math Matts-trttt [52), LLaMA-3 series (3B, 8B,
5

---

Table Test accuracy (%) comparison of different LLMs of varying sizes on our Erdös benchmark tasks. In all experiments we use Qwen2.5-Instre models as our base model (marked below). We report the average accuracy across all tasks in the Average column, and full results for each task provided in Appendix| I.4
Model
Fasy
Medium
Hard
Challenging
Average
Proprietary (Unknown Parameters)
GPT-4o-mini
76.20
72.07
28.81
3.34
47.60
OpenAl 03-mini (w/ tool use)
74.83
83,49
59.28
43,22
64.90
3B Parameters
Llama-3.2-388 1rmma-3.2-3B-Instruu
36.50
21.45
6.81
1.14
17.32
Qwen2,5-3B --nnn-----Is (base model)
45.71
30.18
9.44
1.29
22.72
Direct-SPT-3B (Ouns)
74.43
75.27
14.43
53.78
CoT-SFT-3B (Ours)
65.57
67.64
29.44
4.57
43.56
G1-3B (Ours)
94.86
84,64
41.25
7.57
59.76 (+37.04)
7B Parameters
Llarna-31 3arma-3,1-8B-mie -nS--nrruutt
49. 21
30.45
13.69
1.43
25.10
1enn2.5-7B-Instrrae (base model)
57.36
42.55
18.87
3.29
32.06
Owen2.5-Math-777 In-struuct
$2.79
14.82
28.94
DeepSeck-R1 ---tstill-------il------------
71.79
73.73
39.12
16.57
51.64
GraphWiz-7B-RFT
14.57
13.73
1.38
0.47
7.70
GraphWiz-7B-DPO
20.36
19.09
1.44
0.78
10.59
Direct-SPT-7B (Ours)
73.57
75.91
39.12
10.71
51.76
CoT-SFT-7B (Ours)
72.57
75.73
38.50
11.00
51.34
G1-7B (Ours)
95.07
88.91
50.44
23.57
66.16
(+34.10)
70B Parameters
Llama-3: (ammu-3.117700 1-170--Insttuc
68.07
55.45
31.87
4.44
42.28
Owen2.5-72B-Inssee
71.71
67.81
33.37
8.22
47.16
7OB) [1]. and a strong baseline PeepSeck-RI-Distil--eee
[3] that is distilled from DeepSeek RI with 67 BB parameters. Additionally, for reference, we incorporate previous training strategies for graph reasoning tasks such as GraphWiz-RFT and GraphWiz-DDP
3. We finetune our model from Qwen2.5- Instruct models (3B and 7B) for 300 steps with batch size 512 on cluster of 8 A800 GPUs, using our dataset Erdös. More experimental details can be found in Appendix
Performance. As shown in Table our proposed model G1-7B consistently outperforms most proprietary. open-source, and graph training counterparts by significant margins across all difficulty levels. With a notable average accuracy of 16%, G1-7B outperforms GPT-4o-mini (47.60% by 18.56%, reaching competitive performance to a cutting-edge reasoning model like o3-min (64.90%) that underwent much heavier training. Notably, our small variant G1-3B, delivers a strong average performance of 59.76%. surpassing open-source models including Qwen2.5-72B ---2t-Innttrctt (47.16%) and 1.0-....-----ttrrrree (42.28%) with 20x parameters. We also evaluate the GPT-4o model on a randomly sampled subset of Erdös due to the cost budget. As shown in Appendix Table 14] G1-7B surpasses GPT-4o across all difficulty levels, exceeding it by over 10% on average (65.29% vs. 55.13%), further validating the strong graph reasoning capabilities of the G1 models.
Remark on SFT baselines. Interestingly, Direct-SFT emerges surprisingly strong baseline in Table 2 The 3B and 7B versions of Direct-SFT both outperform larger open-source models with 53.78% and 51.76% accuracy, suggesting that LLMs can discover some effective patterns by directly fitting targets. However, we also observe that with Direct-SFT, the 7B model yields no extra gain over the 3B model, while CoT-SFT and G1 (initialized with CoT--FF) performance scales with larger models. This indicates that even though the CoT-SFT performance may appear low compared to Direct-SFT (possibly because of limited data size with about 100 examples per task), CoT-SFT could have better scaling and generalization properties.
Robustness Analysis. To rigorously evaluate robustness, we conducted 32 repeated runs with different random seeds. The results in Appendix Table 17 demonstrate consistently small standard deviations (<1% across all models and difficulty levels), confirming the stability of our method against potential randomness in LLM outputs. For prompt robustness, we rigorously test prompt sensitivity by having GPT-4o generate three semantically equivalent prompt variants. Appendix Table 18 shows minimal performance variance (<1,50 15.5% standard deviation) across all models and difficulty levels, confirming benchmark's stability to phrasing changes.

---

Scaling G1 to 32B. To demonstrate the scalability of our approach, we extended the training method- ology to develop 21-Zero-32B from Qwen2.5-32B-Instee Instruct.. shown in Table B G1-Zero-32B achieves a 27.96% improvement in average accuracy (from 47.10% to 75.06%). with particularly notable gains in harder categories: +31.87% Hard problems and +26.43% Challenging prob- lems. Furthermore, Appendix Table [ [e]dmmtststte that G1-Zem--22 not only preserves but slightly enhances mathematical performance standard benchmarks, which shows modest improvements both GSM8K (+0.08%) and MATH (+4.00%).
Table 3: Test accuracy (%) of G1 C1-Zero-32B and Owen2.5-33B-Insttee on Erdös.
Easy
Medium
Hard
Challenging
Average
Qwen2.5-32B-Insee
70.57
68.73
33.38
9.00
47.10)
G1-Zero-32B
97.79
93.00
65.25
35.43
75.06
Scaling G1 to larger graphs. To verify the transferability of G1 to larger graphs. we construct a new test set of 5,000 graphs with 36-10 100 nodes, with other settings kept the same, which ensures there is no overlap between training and test data. Yable(4shows that both G1-3B and G1-7B achieve strong zero- shot generalization to these larger graphs without additional training, significantly outperforming the baselines across difficulty levels. These results demonstrate our method's 's effective scalability beyond the original training distribution. For larger graphs with thousands of nodes, G1 is bottle-necked by the context window limit of underlying LLMs, detailed Appendix D
Table 4: Zero-shot generalization (accuracy in percentage) of G1 to larger graphs with 36- 100 nodes.
Easy
Medium
Hard
Challenging
Average
Qwen2.5-3B-Instin
27.98
28.53
5.26
0.29
16.74
G1-3B
79.39
65.66
18.46
3.74
44.29
Qwen2,5-7B-Inss
37.86
41.56
9.17
1.17
23.94
G1-7B
76.65
70.67
23.16
5.22
46.46
5.2
Transferability of G1 to Unseen Tasks and Domains
In this section, we evaluate zero-shot generalization of to unseen domains, tasks, and data formats. Detailed benchmark description and complete evaluation setups are provided in Appendix B
5.2.1 G1's Transferability Other Graph Reasoning Benchmarks
Setup. We consider two additional graph reasoning benchmarks, GraphWiz (3] and GraphArena 38 which bring three major shifts that challenge our model: 1) different distributions of the underlying graphs 2) tasks unseen during training 3) unfamiliar graph encoding formats, c.g., the GraphArena benchmark represents nodes with human names instead of integers.
Results. The performance across models is reported in Table 5 and Table o On the Graph Wiz benchmark, G1-7B achieves the highest overall accuracy (57.1 %) among all models, outperforming PeepSeek-R1-iistllll Qwen-7B 7B (51.86%) and even models specifically trained on Graph data such as GraphWiz- (49.61 %). The smaller variant G1-3B also achieves comparable performance with
Similar results can be found on the GraphArena benchmark (Table ()) with a different graph encoding scheme. These results demonstrate that G1 has strong zero-shot generalization ability to unseen graph encoding methods, graph distributions, and graph tasks. Full results for GraphWiz and GraphArena shown in Appendix [.] and Appendix L3
5.2.2 G1 on Real-world, toh-grip Graph-reasoning Tasks
Baseline. For real-world graph tasks, we consider two standard problems: node classification and link prediction. We adopt the benchmarks introduced by Wang et al. (44), which constructed by subsampling from the widely used Cora and PubMed citation graphs. Each instance includes a description of the target node (or node pair) containing the paper ID and title, along with the textual
7

---

Table 5: Test accuracy (%) by computational com- plexity on the GraphWiz benchmark.
Table Test accuracy (%) by computational complexity on the GraphArena benchmark.
Model
Linear
Poly
NP-Complete
Avg.
Model
Poly-Time
NP-Complete
Avg.
LJama33 3.2 3-3--nsttret
3,00
Easy
Hard
Dasy
Hand
Qwen2.5 5- 1--8--Innrrctt (buse)
40.55
9.58
69.12
26.46
Llama 3.2 3B Instruct
22.25
6.75
8.00
0.66
5.40
G1-38
58,06
26.75
59.08
Qwen2.5 3B Instruct (base)
31.50
14.50
17.33
1.50
14:85
G1-38
$7.50
26.75
24.66
Llama 3.1 1-88-Instratt
$4.00
5.67
32.12
33.03
1 1-88-Instracl
47,00
31.25
22.00
2.16
DeepSock-R RRi---iilll-ae Divill-Qwen-77
$7.69
31 42
70,88
$1.86
DeepSeek RI Disull--pwen-8
66.0
22.75
$4.83
1.30
28.05
GraphWiz-BB B-FFT
29.83
Grgh Wie 7B-RFT
2.25
0.75
0.83
0.00
0.85
GrapWWe-BB-DPS
61.88
36.25
39,50
49.25
Groph Wiz DPO
0.25
1.00
0.66
0.16
0.49
Qwen2.5 Instract (base)
17.92
76.12
44.69
Qwen2.5-788 lastssre (hase)
62,00
35.75
28.83
2.16
28.84
G1-7B
32
72.62
57.11
GL-7B
77.50
44.25
47.33
8.50
41.10
Table 7: Test accuracy (%) on Node Classification and Link Prediction benchmarks.
Table 8: Test accuracy (%) on reasoning bench- marks beyond graph-related tasks.
Model
Node
Link
Arg.
Model
MATH
MMLLUppr
Cora
PubMed
Cora
PubMed
Lhma- 3.2-3B --B-nnituc
71.03
42.40
13.50
Llama: 3.2 Instruct
68.77
75,20
60.40
57.60
64.79
Qwen2 5-3-2n5--- (basc)
81.95
62.20
38,53
Qwen2.5 Instrctt (base)
70:83
62.15
58.38
CoT-SFT-38
75.36
$6.00
34,85
CoTl SFT
25.97
$1.47
25.70
71.32
25.12
G1-38
79.30
61.80
37.11
G1-38
77.25
$3.88
78.97
69.75
75.16
Lhma 3.1-80 Instruct
74,45
44.80
32.02
Llama Instruct
70.90
75,00
50.00
46.10
59.53
DeepSeck Qwen
76.50
78.72
DeepScel-RR RI 1-Disrill-quen-77
86,03
87.20
37.21
Qwen2.5 5 7B Instrctt (base)
79.30
55.38
88.22
88.62
$5.50
Qwen2 5-78- Instract (buse)
86.27
69.89 30
45.75
CoT SFT-7B
73.20
$3.25
64.70
68.12
73.17
COI-SFI-7B
G1-7B
79.20
$6.30
87.98
91.88
$7.29
G1-78
87.49
71.30
48.56
and structural information of neighboring nodes. These benchmarks emphasize the model's ability to leverage both local graph structure and textual attributes for effective prediction.
Results. As shown in Table 7 our model G1 significantly outperforms both open-source and distilled baselines across tasks and model sizes. In the 3B model category, G1-3B surpasses the base model by a large margin-espeecille
in link prediction on Cora (+16.8222 6.%%) and node classification on PubMed (+8.8%). In the 7B model category, G1-7B achieves the highest average score of 87. 77.2%% ranking first on PubMed dataset in both node classification and link prediction tasks. Overall, G1 consistently demonstrates strong generalization across real-world graph tasks where graph-text reasoning is required.
Jowen225-3B-Instuune
5.2.3 G1's Reasoning Ability beyond Graphs
Setup. We next extend our investigations of G1 's abilities beyond graph-based tasks. We consider two mathematics benchmarks, GSM8K (7) and MATH [16]. Additionally, we include MML.U-Po 43] which is a massive multi-task benchmark covering disciplines such as chemistry, economics, and computer science. We believe the three benchmarks collectively provide a comprehensive assessment of G1's reasoning capabilities.
Results. In table 8 we first notice that the COT-SFT training on graph reasoning trajectories leads to a negligglle degradation in general abilities, which could be attributed to the fact that SFT memorizes pattern instead of incentivizing truly generalizable skills 4. Remarkably, the subsequent reinforcement learning stage stage-despite being trained exclusively on graph musks-restores the reasoning abilities of both the 3B and the 7B model. G1-7B even surpasses the performance of the initial Qwen-7B checkpoint in all of the three benchmarks (87.49% v.s. 86.27% for GSM8K, 45.75% for MMLU-pro). Interestingly, G1-7B also on several non-STEM tasks like Economy (68. v.s. 46.87), which
72.8% v.S. 69.8% for MATH, and 48.56% outperforms Beren-7--Insteee intuitively less related to graph reasoning (see Appendix [.2 for full MMLU-Pro results). We further provide detailed analysis on the transfcrability G1 to mathematics tasks in Appendix H showing G1 mainly improves the numerical calculation and utilization of known information.
8

---

5.3 Training Analysis
In this section, further analyze the influence of two training factors on G1's reasoning performance.
Data Mixture. In Table 2 we observe that although G1-3B achieves strong overall performance, it is outperformed by Direct-SFT-3B on the Hard and Challenging subsets. We hypothesize that this gap arises from imbalanced reward signals across different difficulty levels during RL training. Since correct rollouts are much easier to obtain on simpler tasks, the policy tends to allocate more of its constrained probability ratios as well as KL budget to optimize for Easy and Medium tasks, thereby maximizing the overall rewrad. To test this hypothesis, we introduce G1- G1-Hard-3B, which is trained exclusively Hard and Challenging tasks during RI.. As shown in Table this model achieves the highest accuracy on Hard (48.50%) and Challenging (17.45 43%% tasks, surpassing both G1 and Direct-SFT. These results support our claim, suggesting that the suboptimal performance of G1-3B on challenging tasks is a natural consequence of the uniformly weighted reward function, rather than shortcoming of G1 training pipeline. Notably, despite being trained only hard tasks, G1-Hard-3B also generalizes to Easy and Medium tasks (69.36% and 70.64%), ), far exceeding the baseline Qwen2.5-3B I-Istruuct.. This indicates that learning to solve difficult tasks confers transferable reasoning skills that benefit performance on simpler problems. To better balance the optimization process across difficulty levels, we further explore reward- weightingg strategies in Appendix !
Table 9: Test accuracy (%) on our benchmark. * denotes the tasks are excluded in model training. G1-Hard-3B is only RL-trained on Hard and Challenging tasks.
Category
Model
Fasy
Medium
Hard
Challenging
Average
Base Model Qwen2.5-3B-Inne
45.71
30.18
9.44
1.29
22.72
Direct-SFT-3B
74.43
75.27
43.69
14.43
53.78
Ours
C1-3B
94.86
84.64
41.25
7.57
59.76
G1-Hard-3B
69.36*
70.64*
48.50
17.43
53.30
SFT Warmup. We study the role of SFT as a cold- start mechanism for RI, evaluating its impact on both
54.5
Owen2.5 38
performance and response behavior. To isolate the effect of SFT, we compare two variants: G1-Zero-3B that is directly trained from the base model Qwen2.5-
G1-Zero-38
Accuracy (%6
61 3B
3B-Instruct with RL, and G1-3B that initializes RL from the CoT-SFT checkpoint. As shown in Figure [ training RL directly from the base model achieves surprisingly strong performance, aligning with re- cent findings in Deepseek-RR RI--------eer [T]. Meanwhile, initializing RL with CoT-SFT provides clear and con- sistent improvements across all difficulty levels, with an average accuracy of 59.8% compared to 50.1 % of -1-Zero-3B.. Besides, we notice that relative improve- ments become larger as the difficulty increases. In addition to performance gains, we also observe that models initialized by CoT-SFT present more precise reasoning patterns, illustrated by the case study the following section.
40
42.7
412
20-
2.
Essy
Medium
Hand
whggingg
Average
Difficllty Level
Figure 1: Test accuracy comparison of G1- 3B and G1-Zero-3B our benchmark. We include results for -7B in Appendix C
5.4 Understanding the Benefits of RL Training for Graph Reasoning
To understand how RL training helps graph reasoning, we take shortest path (a Hard task) as a case study. Specifically, we study the behaviors of three models: Owen2.5-3B-Instreee (base), G1-Zero-3B (RL only), and G1-3B (SFT & RL).
We identify three primary approaches adopted by the models to solve the problem: 1) Freadth-First Search (BFS), 2) Dijkstra's 's algorithm, and 3) Intuitive deductions. Figure shows the distribution of these approaches alongside their corresponding accuracies for Qween.553BB-Instreeee graphs, BFS is the most efficient method and yields the highest performance. In contrast, Dijkstra's algorithm is best suited for weighted graphs, where correctly accounts for edge costs. However, its reliance on min-priorriy queue and a distance list introduces computational complexity, which appears to challenge Qwen2.5-3B I-Intrruct and results in its lowest observed accuracy. For example, as shown in Figure 2 (left), the model falsely states that node 4 has edges (node 4 is connected
On unweighted

---

The task determine the shortest path between nodes. Here undirected containing nodes from What the shortest path between node and node 4?
3),
(3, 7). (5. 21, 4). Question:
Ground Truth: 3, 7,4)
Question
Graph
Oijkctr aiporitinn find lesi Lade atart inttaeiziing disbencee node to
detiermine shorlest between
in given undirected graph, we graph trivencal method euch frrncthheiint Search (SIS))
other sodica and setting the distance to the star ling node
(nodie distance to other modica initully set
rodes their corncctions:
infirity
Nidd connected nodes
Let's represent the graph odjocency fist for eacerr v vnualiationn kods connected to 6,
start from mode path which
Distance
reach
Starting from node ft we will perform BPS find the shorteat path nodi
Distanice to 7:
noot
2. Befect the node with the small distance (rodi 4) and updnte the distances to its neightore:
Node is connected nodio &, and
Initaalon the qumue with the starting node 6. Keep track walted nodes avord royorling. to the abort node
Shooe we are already alnode we con try reach
seiggttoon....
there.
a. defect the neot emallest dietance node (node update
let's
comnections
Lat's sanculn RFS:
Start Loinods 6.
Since we hawe reached node and the diettanc io
New, let's look at the connections from
Esprare neighbors already vialledh....
neightor
neightorrs: (but
Stinc von atimadyy modis
muchh nodds
From node to node distance (edge 17. 4))
direeitly from here.
neightbors:
So, the path from noded node Ie 41
The shor test path from 0 node ia: 7.4)
(
path
Thansfore, the final answeer in: Sthoandjjs 5, 2, 3. 4188
Thenstore, the final anower (bosedijj 7.4B7
Therefore, the answer Siocoodj 1, 475
G1-Zero-38 38
61-38
Figure 2:
An intuitive illustration of the differences in solution strategies employed by Qwen2.5-3B- Instruct, G1 G1-Zero-3B, and G1-3B for shortest path problem.
to node 7) while updating the distance list. Interestingly, intuitive approaches where the model attempts to visually estimate or heuristically trace paths can also produce correct answers by noticeable accuracy, particularly on small graphs.
We proceed by observing that RL training significantly reshapes the models' graph reasoning strategies: RL-trained models largely abandon Dijkstra and prefer a com-
10
ars Casara
21.55
Actursyy
bination of BFS and intuitive search. As
shown in Figure 3b and Figure 2 (middle), G1-Zero-3B navigates the graph in man- ner akin to human heuristics- seuristics-ssquenntllly checking neighbors and adjusting paths dy- namically. G1-3B primarily adopts a neat BFS-style algorithm as in Figure 3b and Figure ( (right), executing it with high pre- cision, occasionally resorting to intuitive strategies for simple graphs. To conclude, our case study highlights how RL training enhances graph reasoning by guiding LLMs toward more model-aware strategies that are adaptive to their inherent capabilities [47].
8F5
Dikkrr
Inte
Gwen2.5
G1:Zen
(a) The accuracy of different graph reasoning patterns for shortest path on Qwen2.5- 3B Instrucct.
(b) Frequency of different graph reasoning pattems for Qwen2.5-3B-Instrue G1- Zero-3B and G1-3B.
Figure 3: Reasoning patterns for the shortest path task.
6 Discussion
In this paper, we explored the use of Reinforcement Learning improve LLMs' reasoning abilities on graph reasoning and demonstrate significant improvements across a spectrum of tasks with various difficulty levels, showing that graph reasoning of LLMs can be elicited via RL training (even with only 300 steps). We also comprehensively evaluate the transferability of RL-trained models to unseen graph reasoning tasks, real-world graph tasks, and general reasoning tasks, observing strong zero-shot generalization. These results support our hypothesis that training LLMs on diverse synthetic graph-theoretic tasks via RL offers scalable, generalizable path toward robust graph reasoning. As a first step, this approach may guide the development of efficient, general- -prrpoee graph reasoners.
In future work, we aim to explore dynamic difficulty scheduling during RL training to address the sample inefficiency issue. On a broader scale, we also plan extend our approach to the following scenarios: (1) Handling larger graphs with thousands of nodes, aligning with the long-context reasoning challenges. (2) Incorporating visual inputs (e.g., images depicting graphs) to enhance real-world applicability. (3) Adapting G1 to more practical domains such as logistics, knowledge graph reasoning, and tabular moblem-solvingg where structured reasoning is critical.
10

---

7 Limitations
While demonstrates significant improvements in graph reasoning through RL training, it inherits GRPO's sample inefficiency and requires extensive rollouts for challenging tasks (e.g., NP-hard problems), which might be solved with dynamic difficulty scheduling during training. Although G1 demonstrates strong generalization to real-world graph tasks, e.g. node classification and link predic- tion, its generalization to highly and other structured data (e.g,, tabular, time-series) remains untested.
applications (e.g., molecular property prediction)
Social Impacts
G1's graph reasoning capabilities offer practical benefits for education (e.g., adaptive graph theory tutoring) and scientific research. While the technology could amplify existing biases in training data, these risks can be mitigated through careful dataset design and human oversight. When developed responsibly, G1 has the potential to support human experts in solving complex graph problems.
Acknowledgement
Yisen Wang was supported by Beijing Natural Science Foundation (L.257007), Beijing Major Science and Technology Project under Contract no. Z251 100008425006, National Natural Science Foundation of China (92370129, 62376010), Beijing Nova Program (20230484344, 20240484642), and State Key Laboratory of General Artificial Intelligence. Yifei Wang and Stefanie Jegelka were supported in part by the NSF AI Institute TILOS (NSF CCF-21 12662) and an Alexander von Humboldt Professorship.
References
[1] Barabási, A.-L. and Albert, Emergence of scaling in random networks. Science, 286(5439): 509-512, 1999.
[2] Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A.,
Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, and Amodei, D. Language models are few-shot learners. In NeurlPS, 2020.
[3] Chen, N., Li, Y., Tang, J., and Li, J. Graphwiz: An instruction-follooiin language model for graph computational problems. In SIGKDD, 2024.
[4] Chu, T., Zhai, Y., Yang, J., Tong, S., Xie, S., Schuurmans, D., Le, Q. V., Levine, S., and Ma, Y. Sft memorizes, rl generalizes: A comparative study of foundation model post-training. arXiv preprint arXiv:2501.171611 2025.
[5] Chu, X., Xue, H., Tan, Z., Wang, B., Mo, T., and Li, W. Graphsos: Graph sampling and order selection to help llms understand graphs better. arXiv preprint arXiv:2501.14422 2025.
[6] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L.,, Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. arXiv preprint arXiv:2110.1416 140.18 2021.
[7] Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint wwXiv:2110.14166 2021.
[8] Dai, X., Qu, H., Shen, Y., Zhang, B., Wen, Q., Fan, W., Li, D., Tang, J., and Shan, C. How do large language models understand graph patterns? benchmark for graph pattern comprehension. ICLR, 2025.
[9] Das, D., Gupta, I., Srivastava, J., and Kang, D. Which modality should use-text, motif, or image?: Understanding graphs with large language models. In NAACL, 2024.
[10] Erdös, P. Erdös-rényi model. Publ. Math. Debrecen, pp. 290-297, 1959.
11

---

[11] Fatemi, B., Halcrow, J., and Perozzi, B. Talk like a graph: Encoding graphs for large language models, arXiv preprint arXiv:2310.04566 2023.
[12] Grattafiori, A., Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Vaughan, A., Yang, A., Fan, A., Goyal, A., Hartshorn A., Yang. A., Mitra, A.,
Sravankumar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson,
A., Spataru, A., Roziere, B., Biron, B., Tang, B., Chern, B., Caucheteux, C., Nayak, C., Bi, C.,, Marra, C., McConnell, C., Keller, C., Touret, C., Wu, C., Wong, C., Ferrer, C. Nikolaidis, C., Allonsius, D., Song, D., Pintz, D., Livshits, D., Wyatt, D., Esiobu, D., Choudhary, D., Mahajan. D., Garcia-Olano, D.. Perino, D., Hupkes, D., Lakomkin, E., AlBadawy, E., Lobanova, E., Dinan, E., Smith, E. M.. Radenovic, F., Guzmán, F., Zhang, F., Synnaevnee G., Lee, G., Anderson, G. L., Thattai, G., Nail, G., Mialon, G., Pang. G., Cucurell, G., Nguyen, H., Korevaar, H., Xu, H., Touvron, H., Zarov, I., Ibarra, I. A., Kloumann, I., Misra, I., Evtimov, I., Zhang, J., Copet, J., Lee, J., Geffert, J.. Vranes, J.. Park, J., Mahadeokar, J., Shah, J.. van der Linde, J., Billock, J., J., J., Fu, J., Chi, J.. Huang. J.. Liu, J., Wang. J.. Yu, J.,, Bitton, J.. Spisak. J., Park, J., Rocca, Johnstun, J., Saxe, J.. Jia. J., Alwala, K. V., Prasad, K.. Upasami, K. Plawiak, K., Li, K., Heafield. K., Stone, K., El-Arini, K., Iyer, K., Malik, K., Chiu. K., Bhalla, K., Lakhotia, K., (Rantala-Yeary, L., van der Maaten, L., Chen, L., Tan, L., Jenkins, L.. Martin, L., Madaan, L.. L..Malo. L., Blecher, L.., Landzzat, L.., de Oliveira, L.., Muzzi, M.. Pasupuleti, M., Singh, M., Paluri, M., Kardas, M., Tsimpoukelli, M., Oldham, M., Rita, M., Pavlova, M., Kambadur, M., Lewis, M., Si, M. Singh, M. K. Hassan, M., Goyal, N., Torabi, N., Bashlykov, N.. Bogoychev, N., Chatterji, N., Zhang. N., Duchenne. O., Çelebi, O., Alrassy, P., Zhang. P., Li. P., Vasic, P., Weng. P., Bhargava, P., Dubal, P., Krishnan, P., Koura, P. S., Xu, P., He, Q., Dong, Q. Srinivasan, R., Ganapathy, R., Calderer. R., Cabral, R. S., Stojnic, R., Raileanu, R., Maheswari, R., Girdhar, R., Patel, R. Sauvestre, R., Polidoro, R., Sunbaly, R., Taylor, R., Silva, R., Hou, R., Wang, R., Hosseini, S., Chennabasappa. S., Singh, S., Bell, S., Kim, S. S., Edunov, S., Nie, S., S.Nang,, S., Raparthy, S., Shen, S.. Wan. S., Bhosale, S., Zhang. S., Vandenhende, S., Batra, S., Whitman, S., Sootla, S., Collot, S., Gururangan, S., Borodinsky, S.. Herman, T., Fowler, T., Sheasha, T., Georgiou, T., Scialom, T., Speckbacher, T., Mihaylov, T., Xiao, T., Karn, U., Goswami, V., Gupta, V. Ramanathan, V., Kerkez, V., Gonguet, V., Do. V., Vogeti, V., Albiero, V., Petrovic, V., Chu, W., Xiong, W., Fu, W., Meers, W., Martinet, X., Wang, X., Wang. X., Tan, X. E.,, Xia, X., Xie, X., Jia, X., Wang. X., Goldschlag, Y., Gaur, Y., Babaci, Y., Wen, Y., Song, Y., Zhang, Y., Li, Y., Mao. Y., Coudert, Z. D., Yan, Z., Chen, Z.. Papakipos, Z., Singh, A., Srivastava, A., Jain, A., Kelsey, A., Shajnfeld, A., Gangidi, A., Victoria, A., Goldstand, A., Menon, A., Sharma, A., Boesenberg, A., Baevski, A., Feinstein, A., Kallet, A., Sangani, A., Teo, A., Yunus, A., Lupu, A., Alvarado, A., Caples, A., Gu, A., Ho, A., Poulton, A., Ryan, A., Ramchandani, A., Dong, A., Franco, A., Goyal, A., Saraf, A., Chowdhury, A., Gabriel, A., Bharambe, A., Eisenman, A., Yazdan, A., James, B., Maurer, B., Leonhardi, B., Huang, B., Loyd, B., Paola, B. D., Paranjape. B., Liu, B., Wu, B., Ni, B., Hancock, B., Wasti, B., Spence, B., Stojkovic, B., Gamido, B., Montalvo, B., Parker, C., Burton, C., Mejia, C., Liu, C., Wang, C., Kim, C., Zhou, C., Hu, C., Chu, C.-H., Cai, C., Tindal, C., Feichennhofer, C., Gao, C., Civin, D., Beaty, D., Kreymer, D., Li, D., Adkins, D., Xu, D., Testuggine, D., David, D., Parikh, D., Liskovich, D., Foss, D., Wang, D., Le, D., Holland. D.. Dowling, E., Jamil, E.. Montgomery, E., Presani, E.. Hahn, E., Wood, E.. Le, E., Brinkman, E., Arcaute, E., Dunbar, E., Smothers, E., Sun, F. Kreuk, F., Tian, F., Kokkinos, F., Ozgenel, F., Caggioni, F., Kanayet, F., Seide, F,, Florez, G. Schwarz, G., Badeer, G., Swee, G., Halpem, G., Herman, G., Sizov, G., Guangyi, Zhang, Lakshminarayanan, G., Inan, H., Shojanazeri,, H., Zou, H., Wang, H., Zha H., Habeeb, H., Rudolph, H., Suk, H., Aspegren, H., Goldman. H., Zhan, H., Damlaj, I., Molybog. I., Tufanov, I. Leontiadis, I., Veliche, I.-E., Gat, I., Weissman, J., Geboski, J., Kohli, J., Lam, J., Asher, J., Gaya, J.-B., Marcus, J., Tang. J., Chan, J.. Zhen, J.. Reizenstein, J., Teboul, J., Zhong, J.. Jin, J.. Yang, J., Cummings, J., Carvill, J., Shepard, J., McPhie, J., Torres, J., Ginsburg, J., Wang, J., Wu, K., U, K. H., Saxena, K., Khandelwal, K., Zand, K., Matosich, K., Veeraraghavan, K., Michelena, K., Li, K., Jagadeesh, K., Huang. K., Chawla, K., Huang. K., Chen, L., Garg. L., A, SiIva, L.. Bell, L., Zhang, L., Guo, L., Yu, L., Moshkovich, L., Wehrstedt, L., Khabsa, M., Avalani, M., Bhatt, M., Mankus, M., Hasson, M., Lennie, M., Reso, M., Groshev, M., Naumov, M., Lathi, M., Keneally, M., Liu, M., Seltzer, M. L., Valko, M., Restrepo, M., Patel, M., Vyatskov, M., Samvelyan, M., Clark, M., Macey, M., Wang, M., Hermoso, M. Metanat, M., Rastegari, M., Bansal, M., Santhanam, N., Parks, N., White, N., Bawa, N., Singhal, N., Egebo. N., Usunier, N., Mehta, N., Laptev, N. P., Dong, N., Cheng, N., Chernoguz, O., Hart, O., Salpekar, O., Kalinli, O., Kent, P., Parekh, P., Saab, P., Balaji. P., Rittner, P., Bontrager, P., Roux, P., Dollar, P., Zvyagina, P., Ratanchandani, P., Yuvraj, P., Liang, Q., Alao, R., Rodriguez, R.,
12

---

Ayub, R., Murthy, R., Nayani, R., Mitra, R., Parthasarathy, R., Li, R., Hogan. R., Battey, R.,
Wang, R., Howes, R., Rinott, R., Mehta. S., Siby, S., Bondu, S. J., Datta, S., Chugh, S., Hunt, S., Dhillon, S., Sidorov, S.. Pan. S., Mahajan, S.. Verma, S., Yamamoto. S., Ramaswamy, S., I Lindsay, S., Lindsay, S., Feng. S., Lin, S., 7ha, S. C., Patil, S., Shankar, S., Zhang, S., Zhang, S., Wang. S., Agarwal, S., Sajuyigbe,, S., Chintala, S., Max, S., Chen, S., Kehoe, S., Satterfield, S., Govindaprasad, S., Gupta, S., Deng. S., Cho, S., Virk, S., Subramanian, S., Choudhury, S., Goldman, S., Remez, T., Glaser, T., Best, T., Koehler, T., Robinson, T., Li, T., Zhang, T., Matthews, T., Chou, T., Shaked, T. Vontimitta, V., Ajayi, V., Montanez, V., Mohan, V., Kumar, V. S., Mangla, V. Ionescu. V., Poenaru, V., Mihailescu, V. T., Ivanov, V., Li, W. Wang, W. Jiang. W., Bouaziz, W. Constable, W., Tang, X., Wu, X., Wang. X., Wu, X., Gao, X., Kleinman, Y., Chen, Y., Hu, Y., Jia, Y. Qi, Y., Li, Y., Zhang. Y., Zhang, Y., Adi, Y., Nam, Y., Yu, Wang. Zhao, Y., Hao, Y., Qian, Y., Li, Y., He, Y., Rait, Z., Vito, Z., Rosnbrick, Z., Wen, Z.,, Yang. Z., Zhao, Z., and Ma, Z. The llama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
[13] Guo, D., Yang. D., Zhang. H., Song, J., Zhang. R., Xu, R., Zhu, Q. Ma, S., Wang. P., Bi, X., et al. Deepseek-rl: Incentivizing reasoning capability in ilms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
[14] Hagberg, A. A., Schult, D. A., and Swart, P. J. Exploring network structure, dynamics, and function using networkx. In SciPy, 2008.
[15] Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning large graphs. In NeurlPS, 2017.
[16] Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardr, J. Measuring mathematical problem solving with the math dataset. In NeurlPS, 2021.
[17] Hsich, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F., Zhang, Y., and Ginsburg. B. Ruler: What's ' the real context size of your long-context language models? arXiv preprint arXiv:2404.066 240440664 2024.
[18] Huang, X., Zhang, J., Li, D., and Li, Knowledge graph embedding based question answering. In WSDM, 2019.
[19] Karalias, N. and Loukas, A. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In NeurIPS, 2020.
[20] Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.000 1609.02907 2016.
[21] Kong. L., Feng, J., Liu, H., Huang, C., Huang, J., Chen, Y., and Zhang, M. Gofa: A generative one-for-all model for joint graph language modeling. In ICLR, 2025.
[22] Kwon, W., Li, Z-, Zhuang, S., Sheng, Y., Zheng, I.,, Yu, C. H., Gonzalez, J. E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In SIGOPS, 2023.
[23] Li, X., Chen, W., Chu, Q., Li, H., Sun, Z., R., Qian, C., Wei, Y., Shi, C., Liu, Z., et al. Can large language models analyze graphs like professionals? benchmark, datasets and models. In NeurlPS, 2024.
[24] Li. Y., Pan, Z., Lin, H., Sun, M., He. C., and Wu, L. Can one domain help others? a data-centric study on multi-domain reasoning via reinforcement learning. arXiv preprint arXiv:2507.17512. 2025.
[25] Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprint arXivv2305.20050, 2023.
[26] Liu, H., Feng, J.. Kong, L., Liang, N., Tao, D., Chen, Y., and Zhang, M. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024.
[27] Luo, Z., Song, X., Huang, H., Lian, J., Zhang, C., Jiang, J., and Xie, X. Graphinstruct: Empowering large language models with graph undcrstanding and reasoning capability. arXiv preprint arXiv:2403.044 044804483, 2024.
13

---

[28] Mao, H., Chen, Z., Tang, W.. Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In ICML, 2024.
[29] Mirhoseini, A., Goldie, A., Yazgan, M., Jiang. J. W., Songhori. E., Wang, S., Lee, Johnson, E... Pathak, O., Nova, A., et al. A graph placement methodology for fast chip design. Nature, (0447862))207-2222 2021.
[30] OpenAl, Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Carney, A., Iftimie, A., Karpenko, A., Passos, A. T., Neitz, A.,
Prokofiev, A., Wei, A., Tam, A., Bennett, A., Kumar, A., Saraiva, A., Vallone, A., Duberstein,
A., Kondrich, A., Mishchenko, A., Applebaum, A., Jiang, A., Nair, A., Zoph, B., Ghorbani, B., Rossen, B., Sokolowsky, B., Barak, B., McGrew, B., Minaiev, B., Hao, B., Baker, B., Houghton, B., McKinzie, B., Eastman, B., Lugaresi, C., Bassin, C., Hudson, C., Li, C. M., de Bourcy, C., Voss, C., Shen, C., Zhang, C., Koch, C., Orsinger. C., Hesse, C. Fischer. C., Chan, C., Roberts, D., Kappler, D.. Levy, D., Selsam, D., Dohan, D., Farhi, D., Mely. D., ReRRRobissoo,, D.. Tsipras, D., Li, D., Oprica, D., Freeman, E.,, Zhang, E., Wong, E., Proehl, E., Cheung, E., Mitchell, E.. Wallace, E., Ritter, E., Mays, E., Wang, F., Such, F. P., Raso, F., Leoni, F., Tsimpourlas, F. Song. F., von Lohmann, F., Sulit, F., Salmon, G., Parascandolo. G., Chabot, G., Zhao, G., Brockman, G., Leclerc, G., Salman, H., Bao, H., Sheng. H., Andrin, H., Bagherinezhad, H., Ren, H., Lightman, H., Chung, H. W. Kivlichan, I., O'Connell, I., Osband, I., Gilaberte, I. C., Akkaya, I., Kostrikov, I., Sutskever, L., Kofman, I., Pachocki, J.. Lennon, J., Wei. J., Harb, J., Twore, J., Feng. J.. Yu, J., Weng, J.. Tang, J., Yu, J., Candela, J. Q.. Palermo, J., Parish, J. Heidecke, J.. Hallman, J., Rizzo, J., Gordon, J., Uesato, J., Ward, J., Huizinga, J., Wang, J.. Chen, K. Xiao, K., Singhal, K., Nguyen, K., Cobbe, K., Shi, K., Wood, K., Rimbach, K., Gu-Lemberg, K., Liu, K., Lu, K., Stone, K., Yu, K., Ahmad, L.., Yang. L.., Liu, L.., Maksin, L.., Ho, L., Fedus, L.., Weng, I.., Li, L., McCallum, L., Held, I.,, Kuhn, L.., Kondraciuk, L., Kaiser, L., Metz, L.,, Boyd, M., Trebacz, M., Joglekar, M., Chen, M., Tintor, M., Meyer, M., Jones, M., Kaufer, M., Schwarzer, M., Shah, M.. Yatbaz, M., Guan, M. Y. Xu, M., Yan, M., Glaese, M., Chen, M., Lampe, M., Malek, M., Wang. M., Fradin, M., McClay, M., Pavlov, M.. Wang, M., Wang, M., Murati, M., Bavarian, M., Rohaninejad, M., McAleese, N., Chowdhury, N., Chowdhury, N., Ryder, N., Tezak, N., Brown, N., Nachum, O., Boiko, O., Murk, O., Watkins, O., Chao, P., Asshoume, P., Izmailov, P., Zhokhov, P., Dias, R., Arora, R., Lin, R., Lopes, R. G., Gaon, R., Miyara, R., Leike, R., Hwang, R., Garg, R., Brown, R., James, R., Shu, R., Cheu, R., Greene, R., Jain, S., Altman, S., Toizer, S., Toyer, S., Miserendino, S., Agarwal, S., Hernandez, S., Baker, S., McKinney, S., Yan, S., Zhao, S., Hu, S., Santurkar, S., Chaudhuri, S. R., Zhang, S., Fu, S. Papay, S., Lin, S., Balaji, S., Sanjeev, S., Sidor, S., Broda, T., Clark, A., Wang. T., Gordon, T., Sanders, T., Patwardhan, T., Sottiaux, T., Degry. T., Dimson, T., Zheng, T., Garipov, T. Stasi, T., Bansal, T., Creech, T. Peterson. T., Eloundou, T., Qi, V.. Kosaraju. V., Monaco, V.. Pong, V., Fomenko, V.. Zheng. W., Zhou, W., McCabe, W., Zaremba. W., Dubois, Y., Lu, Y., Chen, Y., Cha, Y., Bai, Y., He, Y., Zhang, Y.. Wang, Y., Shao, Z., and Li, Z. Openai ol system 2024.
card. arXiv preprint arXi::2412.1677
[31] Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R., and Halcrow, J. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862. 2024.
[32] Owen, :, Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., Lin, H., Yang, J., Tu, J., Zhang, J., Yang, J., Yang, J., Zhou, J., Lin, J., Dang, K., Lu, K., Bao, K., Yang, K., Yu, L., Li, M., Xue. M. Zhang, P., Zhu, Q.. Men, R., Lin, R., Li, T., Tang, T., Xia, T., Ren, X., Ren, X., Fan, Y., Su, Y., Zhang, Y., Wan, Y., Liu, Y., Cui, Z., Zhang, Z., and Qiu, Z. Qwen2.5 technical report. arXiv preprini 24Xiv:2412.151155 2025.
[33] Rossi, R. A. and Ahmed, N. K. The network data repository with interactive graph analytics and visualization. In AAAI, 2015.
[34] Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V. Understanding transformer reasoning capabilities via graph algorithms. In NeurlPS, 2024.
[35] Sato, R., Yamada, M., and Kashima, H. Approximation ratios of graph neural networks for combinatorial problems. In NeurlPS, 2019.
14

---

[36] Shao. Z., Wang, P. Zhu, Q. Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y., Wu, Y., et al. Deepseekmath: Pushing the limits of mathematical reasoning open language models, arXiv preprint arXiv:2402.03330, 2024.
[37] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap. T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T.. and Hassabis, D. Mastering the game of go without human knowledge. Nature, 550(7676):34--35) 2017.
[38] Tang, J., Zhang, Q., Li, Y., and Li. Grapharena: Benchmarking large language models on graph computational problems. In ICLR, 2025.
[39] Veličković, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. Neural execution of graph algorithms. In ICLR, 2020.
[40] Wang, H., Wang, K., Yang, J., Shen, L., Sun, N., Lee, H.-S., and Han, S. Gen-rl eircuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning. In DAC, 2020.
[41] Wang, H., Feng. S., He, T., Tan, Z., Han, X., and Tsvetkov, Y. Can language models solve graph problems in natural language? In NeurlPS, 2023.
[42] Wang, J., Wu, J., Hou, Y., Liu, Y., Gao, M., and McAuley, J. Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. In ACL, 2024.
[43] Wang, Y., Ma, X., Zhang, G., Ni, Y., Chandra, A., Guo, S., Ren, W., Arulraj, A., He, X., Jiang, Z., Li, T., Ku, M., Wang, K., Zhuang, A., Fan, R., Yue, X., and Chen, W. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. arXiv preprint arXiv:2406.01574 2024.
[44] Wang, Y., Dai, X., Fan, W., and Ma. Y. Exploring graph tasks with pure llms: A comprehensive benchmark and investigation. arXiv preprint arXiv:2502.18771 2025.
[45] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., al. thain-of-thought prompting elicits reasoning in large language models. In NeurlPS, 2022.
[46] Wu, Q., Chen, Z., Corcoran, W., Sra, M., and Singh, A. K. Grapheval2000: Benchmarking and improving large language models on graph datasets. arXiv preprint arXiv:2406. 21t.::2000.667766, 2024.
[47] Wu, Y., Wang, Y., Du, T., Jegelka, S., and Wang, When more less: Understanding -fain-of-thought length in llms. arXiv preprint arXiv:2502.07266, 2025.
[48] Xu, H., Jian, X., Zhao, X., Pang, W., Zhang, C., Wang, S., Zhang, Q. Monteiro, J., Sun, Q. and Yu, T. Graphomni: comprehensive and extendable benchmark framework for large language models on graph-theorete tasks. arXiv preprint arXiv:2504. 12764, 2025.
[49] Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arXiv: 1810.00826, 2018
[50] Xu, K., Hu, W., Leskover, J., and Jegelka, How powerful are graph neural networks? In ICLR, 2019.
[51] Xu, K., J., Zhang, M.. Du S. S., Kawarabayashi, K.-i., and Jegelka, S. What can neural networks reason about? arXiv preprint arXiv: 1905. 13211, 2019.
[52] Yang, A., Zhang, B., Hui, B., Gao, B., Yu, B., Li, C., Liu, D., Tu, J., Zhou, J., Lin, J., Lu, K., Xue, M., Lin, R., Liu, T., Ren, X., and Zhang, Z. Qwen2.5-math technical report: Toward mathematical expert model via self-improvement. arXiv preprint arXiv:2409. 12/22, 2024.
[53] Ye, R., Zhang, C., Wang, R., Xu, S., and Zhang, Y. Language is all a graph needs. In ECAL, 2024.
[54] Yuan, Z., Yuan, H., Li, C., Dong, G.. Lu, K., Tan, C., Zhou, C., and Zhou, J. Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint 2.0.0020... 2023.
15

---

[55] Yuan, Z., Liu, M., Wang, H., and Qin, B. Gracore: Benchmarking graph comprehension and complex reasoning in large language models. In COLING, 2025.
[56] Zhang, M. and Chen, Y. Link prediction based on graph neural networks. In NeurlPS, 2018.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: See the contributions stated in our introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See the statement of results our experiments.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:[NA]
Justification:
The paper does not include theoretical results.
17

---

Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 4.1 and implementation details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We will release our models and datasets later for public use.
18

---

Guidelines:
reproducible, they The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submíssion guidelines (kttps://nips.ce cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips. //nips.cc/pusll wwtpccpbwccgg.uddeeaeeeeeppeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix A for implementation details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experiments follow common settings of related works, where the random- ness in the evaluation negligible.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
19

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: See the setup of Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymenn of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
20

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The paper cites the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
We will release our datasets and models with documents later for public use.
21

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/code//model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve any crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration LLM usage
Does the paper describe the usage of LLMss if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our core methodology, scientific rigorousness, or originality of the research does not involve the usage of LLMs.
Guidelines:
22

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, or non non-standard components.
Please refer to our LLM policy httt:p///eaariig..e////oooeerr/s for what should or should not be described.
23

---

A Training Details
A.1 Rejection Sampling
We randomly extract subset with 100 examples per task from the training dataset, and Qwen2.55 32B-Instrrct to sample on the subset for = times with temperature of 1.0. We filter the responses by keeping the reasoning steps that lead to the right answer. If the task difficult and the filtered responses are insufficient, we resample the subset with a different random seed and repeat the process above. In the end, we obtain around 4,500 training examples (~90 per task) for the SFT phase.
A.2 Supervised Fine-tuning
The detailed training configurations of Naive SFT and RFT are presented in Table T0
Table 10: Training configurations of Naive-SFT and RFT. In this table, batch size is abbreviated to BSZ, Max-Length refers to the maximum response length during training and Data Num. reports the number of training examples.
Setting
Weight Decay
BSZ.
Max-Length
Data Num.
Epoch
Naive-SFT
le-5 w/ 1% warm-up
le-2
64
512
98.7k
1
RFT
le-5 w/ 1% warm-up
le-2
64
3072
4.4k
2
A.3
Reinforcement Learning
Configurations for training and evaluation. Our experiments primarily adopt Qwen-2.5-3B/77 Instruct [32] for their moderate sizes and strong reasoning performance. For GRPO training, we set to be 0.02. 8 to be 0,001, group size G to be 5, and context length to be 4096 unless otherwise specified. We additionally incorporate an entropy loss of weight 0.001 encourage the policy to explore. Lastly, we train the models on Ax00 GPUs with batch size of 512. During evaluation, Dea-See--R--iitill--Weeee
set the the vL.LM (22 engine for efficient inference. For DeepSeek-R 1-Distilll-Ce Swaill--wen-BB,, which maximum token generation length to 4096 tokens except for
extended to 30768 for its prolonged thinking process. Sampling is configured with temperature of 0.6, top-p 0.95, and top-k of 30.
The detailed RL training configurations are presented in Table
Table 11: Training configurations for Naive-SFT and RFT. For abbreviation, we refer the coefficient for entropy loss as Ent. in this table. We report (batch (number of gradient accumulation steps) in the BSZ column, and the temperature for on policy sampling T.
Model RL-3B
LR
|G]
8
T
Ent.
BSZ
Max- Max-Length
Data Num.
Steps
le-6
0.2
5
le-3
1.0
1.0
le-3
512/4
4096
98.7k
300
SFT-RL-33
le-6
0.2
5
le-3
1.0
1.0
le-3
512/4
4096
98.7k
300
SFT-RL-Hard-3B
le-6
0.2
5e.4
1.0
1.0
5e-4
512/8
8192
49.3k
150
SFT-RL-7B
le-6
0.2
le-3
1.0
1.0
le-3
512/8
4096
98.7k
300
B Evaluation Details
B.1 Benchmark Introduction
GraphWiz Wiz (3). GraphWiz employs the Erdōs-Rényi (ER) model generate random graphs and describe graphs in the edge-list formation like (u, v). The tasks include four linear complexity tasks, Connectivity, Cycle Detection, Bipartite Graph Checking, and Topological Sort; three polynomial complexity tasks, Shortest Path, Maximum Triangle Sum, and Maximum Flow; and two NP-Complete tasks: Hamilton Path and Subgraph Matching. A prompt example is shown in the following:

---

Maximum Triangle Sum Example in GraphWiz
Find the maximum sum of the weights of three interconnected nodes. In undirected graph, [i, k] means that node has the weight k. (i.j) means that node and node j are connected with undirected edge. Given graph, you need output the maximum sum of the weights of three interconnected nodes. Q: The nodes are numbered from 4, weights of nodes are: [0, 8] [1, 5] [2, 3] [3, 6] [4, 3], and the edges are: (0, 4) (0, 3) (0, 1) (1, 3) (1, 2) (3, 4). What the maximum sum the weights of three nodes?
We adopt the benchmarks introduced by Wang et al. 44]. which are constructed by subsampling from the widely used Cora and PubMed citation graphs. Each instance includes description of the target node (or node pair) containing the paper ID and title, along with the textual and structural information consider two cases that the description includes the attributes of the target node and those of its 2-hop neighbors, with without labels. For link prediction, we consider two cases where target nodes are described using their own node attributes along with those of their 2-hop neighbors (excluding the other targeting node), with without titles. For each task, we randomly sample 2,000 examples per case from the benchmark and report the average performance. A representative example for node classification is shown below:
Node Classification and Link Prediction 44
neighboring nodes. For node classification, we
Node Classification Example
You a good graph reasoner. Give you graph language that deseribes a graph structure and node information from pubmed dataset. You need to understand the graph and the task definition and answer the question.
## Target node: Paper id: 10695 Title: Haplotype structures and large-scale association testing the 5' AMP-activated protein kinase genes PRKAA2, PRKAB1, and PRKAB2 [corrected] with type 2 diabetes.
Known neighbor papers at hop 1 (partial, may be incomplete): Paper id: 1155 Title: Computational discase gene identification: concert of methods prioritizes type diabetes and obesity candidate genes. Label: Type 2 diabetes
Known neighbor papers at hop 2 (partial, may be incomplete):
Paper id: 9816 Title: Mitochondrial dysfunction and type diabetes. Label: Type 2 diabetes Paper id: 1683 Title: A genome-wide search for type II diabetes susceptibility genes in
Chinese Hans. Label: Type 2 diabetes
Paper id: 9916 Title: Genomewide search for type diabetes- suseppii- genes in French whites: evidence for novel susceptibility locus for early-onset diabetes on chromosome 3q27-qter and independent replication of type 2-diabetes locus on chromosome 1Q21. Paper id: 3793 Title: Association of amino acid variants in the activating transcription factor
gene (ATF6) on q221-q23 with type 2 diabetes in Pima Indians. Label: Type 2 diabetes Paper id: 4788 Title: Altered glycolytic and oxidative capacities skeletal muscle contribute
insulin resistance in NIDDM. Label: Type 2 diabetes
Please predict the most likely type of the Target node. Your answer should be chosen from: Type diabetes Type 2 diabetes Experimentally induced diabetes
GraphArena 38 GraphArena samples subgraphs from real-world graphs, including knowledge graphs, social networks, and molecular structures. The tasks include four polynomial-tine tasks, Common Neighbor. Shortest Distance, Connected Component, Graph Diameler, and six NP-complete tasks, Maximum Clique Problem (MCP). Maximum Independent Set (MIS) Minimum Vertex Cover (MVC), Maximum Common Subgraph (MCS), Graph Edit Distance (GED), and Traveling Salesman Problem (TSP). Each problem is contextualized within the woal-world setting of the graph with an example presented below:
25

---

Connected Component Example in Arenh
You required identify all connected components in the given social network and output one representative node from each component. Within a connected component, any node be reached from any other node through the edges in the graph. Different connected components are isolated from each other.
**Problem to Solve
Names in the network: Veronica Garcia, Katherine Brennan, Angel Chavez, Steven Martin, Brett Johnson, Megan Banks, Julia Dominguez, Rachel Mitchell Fiendship connections: Veronica Garcia to Brett Johnson, Veronica Garcia to Megan Banks, Katherine Brennan to Katherine Brennan to Megan Banks, Angel Chavez to Megan Banks, Angel Chavez to Rachel Mitchell, Steven Martin to Megan Banks, Brett Johnson to Megan Banks, Megan Banks to Julia Dominguez, Megan Banks Rachel Mitchell.
Brett Johnson,
Identify all connected components in this network. Note that for each connected component, you should only output one of its nodes. Present your answer in the following format: [UserA, UserB, UserC, UserD, ...]
GSM8K is a dataset of 8.5K high quality linguistically diverse grade school math word problems created by human problem writers. We report the accuracies on the 1K test problems and the dataset is downloaded via https: http///hhggggagcee//e co co/patasstssoppeaaaa////o/aa/a/a
GSM8K 6
Example in GSMSK
Natalia sold clips 48 of her friends in April, and then she sold half as many clips in May. How many clips did Natalia sell altogether April and May?
MATH500. The dataset contains a subset of 500 problems from the MATH benchmark that OpenAI created in their Let's Verify Step by Step paper (25). We download the dataset via Ihtpps: // huggingface co http:////...../.iggggggggga////a
Example in MATH500
Let = 2 + v2 (3 + 3/2),, and let c = 2 - 3i. Let w be the result when is rotated around e by _ counter-clockwise. [asy]
unitsize(0.6.cm) cm);
pair C, W. Z:
Z= sqrt(2), -3- 3*srr(()));
(2.33)));
W = rotate(45,)))
draw(Z-C-W);
dot("c", C, N);
dot("w". W. SE);
dot("2", Z. S);
label(" E" C (0.6.-1)); [/asy]
Find
MMLU-Pro. MMLU-Pro is enhanced version of the Massive Multitask Language Understanding benchmark. It covers wide range of disciplines, including Math, Law, Engineering, Health, Phycology, etc. We download the dataset via wttthhtps::/// / co wttpeeecctaaaattteeeeeeeeeee.eee MMLU- Ptt. http:/veeeee/eeeeeeeee http:://///oeeeeeeatt///et//aaaa
26

---

Health Example in MMI.U-pro
Food supplements, including trace minerals and vitamins frequently advertised with promising health benefits. Which of the following substance could be consumed in excess, Lee. well above the recommended daily requirement?
Question:
Options:
"Vitammin C",
"Vitamin D", "Zinc", "Vitamin A")
B.2
Inference Configuration
For inference, we adopt the vLLMM framework [22] set the temperature to 0.06 and the context window to be 4096 for our evaluations unless otherwise specified.
B.3 Prompt and Answer Extraction
To facilitate answer extraction, we adopt the prompt shown in B.3 to guide the models to reason step by step and place their answers within \boxed(). We extract the last \boxed ) shown in the model responses and do necessary format normalizations to retrieve the answer, which includes operations like converting LaTeX-style fraction numbers to float numbers.
Problem Instructions
QQuestion Description)
Approach the problem methodically. Ensure all conclusions based on precise calculations and logical deductions. Feel free to explore various solution methods and cross-check results for consistency. Maintain dynamic thinking and always verify each step of your reasoning. Present the final answer in \boxed| format, like this: Slboxed ANSWER where ANSWER is the final result or expression.
Think carefully and break down the problem step by step.
C Comparison between G1-Zero-7B and G1-7B
In Section 5.3
we study the role of SFT cold-start mechanism for RL by comparing two variants: G1-
Qown2 5-78-instract
Zero-3B that is directly trained from the base model Qwen2.5-3B Instruct with RL, and G1-3B that initial- izes RL from the CoT-SFT checkpoint. We observe that G1-Zero-3B already achieves surprisingly strong performance, while G1-3B presents clear and consis- tent improvements across all difficulty levels. Here, we provide additional results for comparing G1-Zero- 7B and G1-7B. As shown in Figure 4 for Easy and Medium tasks, the benefit brought by CoT-SFT initial- ization is marginal, with G1-Zero-7B (96.9%) even surpassing G1-7B (95. %) on Easy tasks. However, on Hard and Challenging tasks, CoT-SFT as preliminary step has definite benefits by improving G1-Zero-7B from 13.7% 23.6% on Challenging tasks. This observation agrees with the case in -3B. Moreover, the average gap between G1-Zero-7B and G1-7B is less than -3B case, indicating G1-7B can possibly be further improved with CoT-SFT generated by stronger teacher model rather than Dowen..5-3B-IIntmree We leave this exploration for further work.
01-2wro-78
Accuracy (95)
G1-78
Difficulty
Figure 4: Test accuracy comparison of G1-7B and G1-Zero-7B our benchmark.
D Transferability of G1 to Larger Graphs
To verify the transferability of G1 to larger graphs, we construct a new test set of 5,000 graphs with 36- 100 nodes, with other settings kept the same, which ensures there is no overlap between training and test data. Table 12 shows that both G1-3B and G1-7B achieve strong zero-shot generalization to these larger graphs without additional training, significantly outperforming the baselines across
27

---

difficulty levels. These results demonstrate our method's effective scalability beyond the original training distribution.
Currently, we limit our analysis to smaller graphs because of the context window limit of underlying LLMs (e.g., Qwven.5--BBInstrreen As shown T3] 200-node graph often exceeds 32k tokens, surpassing the maximum effective context window of many open-source LLMs [7]. Long-context understanding is actively studied in the LLM literature, and there are some sutting-edge proprietary variants (e.g.. OpenAl's GPT-4.1) I) supporting imputs of over IM tokens (though graphs of 2000 nodes need 4M). Due to computational constraints (demanding huge GPU memory), it hard for us evaluate on a very long context. We believe our approach can be scaled to larger graphs with the rapid progress of long-context studies.
The token count scales quadratically with the number of nodes.
Table 12: Zero-shot generalization (accuracy in percentage) of G1 to larger graphs with 36- 100 nodes.
Easy
Medium
Hard
Challenging
Average
Qwen2.5-3B-Inse
27.98
28.53
5.26
0.29
16.74
G1-3B
79.39
65.66
18.46
3.74
44.29
Qwen2.5-7B-Imm IB-ssuuctt
37.86
41.56
9.17
1.17
23.94
G1-7B
76.65
70.67
23.16
5.22
46.46
Table 13: Token numbers of graph with different node sizes. We generate random graphs by Erdös-Rényi model with an edge probability of 0.2. For each node number, we generate 10 graphs and report the mean of the token numbers. For tokenization, we utilize the tokenizer of Qwen2.5- Instruct.
Node Number
30
50
100
200
500
1000
2000
Token Number
641.4
1941.5
7842.8
~35k
~~30
~ 1M <4M
E
GPT-4o Results on Erdös
Due to the cost budget, we randomly sample 20 examples per task from Erdös's 's evaluation set to construct subset of 1,000 samples. As shown in Table [4] G1-3B performs comparably GPT-4o on average (57.37% vs. 55. 55.13%), while G1-7B surpasses GPT-4o across all difficulty levels, exceeding it by over 10% average. This comparison further validates the strong graph reasoning capabilities of the G1 models.
Table 14: Test accuracy%) of GPT-4o and G1 variants on a subset of Erdós.
Easy
Medium
Hard
Challenging
Average
GPT-40-2024-11-20
82,50
81.82
44.06
12.14
55.13
G1-3B
96.43
85.45
41.88
5.71
57.37
G1-7B
96.43
88.64
52.50
23.57
65.29
F Results of G1-Zero-32B
To demonstrate the scalability of our approach, extended training methodology to develop G1-Zero-32B from Swven.5-332B-Inttie The results showcase substantial improvements across all difficulty levels while maintaining computational efficiency. As shown in Table 15 G1 G1-Zero-32B demonstrates remarkable improvements on the Erdösbenchmark across all diffiulty categories. The model achieves 27.96% improvement in average accuracy (from 40.10% to 75.06%). with particularly notable gains harder categories: +31.87 points on Hard problems and +26.43 points on Challenging problems. These results indicate that our method scales effectively to larger models while maintaining consistent performance improvements across varying problem complexities.
Furthermore, Table 16 demonstrates that G1-Zero-322 B2B not only preserves but slightly enhances mathematical performance standard benchmarks. The model shows modest improvements both
28

---

GSM8K (+0.08 points) and MATH (+4.00 points), confirming that our reasoning foccused training does not compromise existing mathematical capabilities and may even provide synergistic benefits. The training process is completed in 40 hours on 32xA 100 GPUs, demonstrating the practical feasibility of scaling our approach to larger model architectures without prohibitive computational costs.
Table 15: Test accuracy (%) of G1 G1-Zero-32B and Qwen2.5-32B-Instmne on Erdös.
Easy
Medium
Hard
Challenging
Average
Qwen2.5-32B Instruct
70.57
68.73
33.38
9.00
47.10
G1-Zero-32B
97.79
93.00
65.25
35,43
75.06
Table 16: Test accuracy (%)
G1-Zero-32B and Q on math tasks.
GSM8K
MATH
Qwen2.5-32B Instrucct
90.67
76.80
G1-Zero-32B
90.75
80.80
G Experiments for Robustness Verification
G.1 Multi-runs Robustness
To rigorously evaluate robustness, we conducted 32 repeated runs with different random seeds. The results in Table T demonstrate consistently small standard deviations (<1% across all models and difficulty levels), confirming the stability of our method against potential randomness LLM outputs.
Table 17: Test accuracy (%) for 32 runs with different random seeds.
Easy
Medium
Hard
Challenging
Qwen2.5-3B -nS-truutctt
45.65 = 0.51
30.88
0.36
10.36 + 0.21
1.54 1: 0.29
G1-3B
94.96 0.32
83.22
0.24
41.48 = 0.40
7.96 + 0.64
Dwwn2.55-7B-Innstie
57.50 = 0.13
44.92 + 0.03
19.90 = 0.31
3.45 + 0.22
G1-7B
95.66 0.12
88.89 1 0.16
50.76 = 0.53
24.46 0.84
G.2 Prompt Robustness
For prompt robustness, we rigorously test prompt sensitivity by having GPT-4o generate three semantically equivalent prompt variants. 'aable T8 shows minimal performance variance (<1.5% standard deviation) across all models and difficulty levels, confirming our benchmark's stability to phrasing changes.
H Analysis of G1's Transferbility to Mathematics Tasks
We compare the generation results G1-7B and Owen2.55-7B-Instrud on the math benchmarks case by case. As a summary, G1-7B improves over Owee2.55-7B-Instruus on more accurate numerical calculation (Instance 1) and more comprehensive utilization of the given information (Instance 2). It's reasonable since the training of G1 includes complex numerical calculations (e.g., shortest path) and careful processing of questions (e.g., traversing the whole graph descriptions to find key edges).
In fact, the transferability between different reasoning domains has also been observed in other works and is actively under research. For example, Chu et al. [5] demonstrates that reinforcement learning exhibits strong generalization robust, mask-agnostic reasoning strategies rather than overfitting to surface-level patterns. Additionally, RL training has been shown to foster mutual reinforeement across seemingly distinct tasks, e.g., optimizing on puzzles can help reasoning on math (24). Similarly, due to the similarity between math and graph problems, they would also require similar reasoning skills (such as guessing, backtracking,
under distribution shifts, it encourages models to learn
29

---

Table 18: Test accuracy (%) on different prompts, mean and standard deviation reported.
Easy
Medium
Hard
Challenging
Qwen2.5-
Swwen.5-3B-Instruet Instruct
44.26 = 0.63
30.52
1.08
10.71 = 0.41
1.24 + 0.07
G1-3B
94.86 0.69
83.03 + 0.42
41.08 = 1.35
9.67 + 1.05
Qwen2.5-7B-Insse In-Inrrcct
56.48 = 1.17
56.48 1.17
18.81 = 0.79
3.10 + 0.18
G1-7B
95.48 0.18
88.39 + 0.67
51.27 = 0.13
25.14 1.04
and verification). Therefore, solving graph problems could have positive transferability math domains.
Instance (Calculation Correctness)
Question:
Toula went to the bakery and bought various types of pastries. She bought 3 dozen donuts, which cost 68 dollars per dozen, dozen mini cupcakes, which cost 80 dollars per dozen, and dozen mini cheesecakes for 55 dollars per dozen. How much was the total cost?
Ground Truth: 694
Calculate the of the donuts: Toula bought 3 dozen donuts. The cost per dozen donuts is 68 dollars. Therefore, the total cost for the donuts is: 3 dozen x 68 dollars/dozen 180 dollars.
Answer of Qwen2.5-7B-Instreee
Calculate the total cost: Add the costs of the donuts, mini cupcakes, and mini cheesecakes: 180 dollars 160 dollars + 330 dollars 670 dollars.
Answer of G1-7B: Cost of Donuts: Toula bought 3 dozen donuts. The cost per dozen donuts is 68 dollars. Therefore, the total cost for the donuts is: 3 dozen x 68 per dozen 68 204. Now, we add up the costs of all the pastries to find the total cost: $204 (donuts) + $160 (mini cupcakes) + $330 (mini cheesecakes) = $694.
Instance (Utilization of Known Conditions)
Question: On Mondays, Wednesdays, and Fridays, college student Kimo has three 1-hour classes each day. On Tuesdays and Thursdays, he has two 2-hour classes each day. In one semester, there are weeks of school. In one semester, how many hours does Kimo spend attending classes?
Ground Truth: 272
Answer of Qwen2..57B-Instruut. Calculate the number of hours Kimo spends in classes each week: On Mondays, Wednesdays, and Fridays, Kimo has 3 classes, each lasting hour. 3 classes X 1 hour/class lasting 2 hours. 2 classes x 2 hours/class = 4 hours. Therefore, the total number of hours Kimo spends in classes each week is: 3 hours + hours 7 hours. Calculate the number of hours Kimo spends in classes in one semester: There are 16 weeks in the semester. The total number of hours Kimo spends in classes in one semester is: 7 hours/weekx 16 weeks = 112 hours.
3 hours. On Tuesdays and Thursdays, Kimo has 2 classes, each
Answer of G1-7B: Step 1: Calculate Weekly Class Hours. Mondays, Wednesdays, and Fridays: Each day, Kimo has classes, each lasting hour. Therefore, for each of these days, the total class time is: 3 classes/day x 1 hour/class = hours/day. Since there are 3 days days
(Monday, Wednesday, Friday): 3 hours/day
hours. Tuesdays and Thursdays: Each day, Kimo has 2 classes, each lasting 2 hours. Therefore, for each of these days, the total hours/class
class time is: 2 classes/day Thursday) 4 hours/day 2 days = 8 hours. - Total Weekly Class Hours: Adding the hours from all the days: 9 hours + 8 hours 17 hours/week. Step 2: Calculate Total Class Hours in One Semester. There are weeks in the semester. Therefore, the total class hours one semester is: 17 hours/week x 16 weeks = 272 hours.
4 hours/day. Since there are 2 days (Tuesday,
30

---

I Detailed Experimental Results
L.1 Detailed Results for GraphWiz
We present the test accuracy for each task in the GraphWir Wiz benchmark in Table 19 G1-7B achieves the highest overall accuracy (57.1 11) among all models and reaches the top in 5/7 tasks. It outperforms (51.66) and even models specifically trained on GraphWiz data (49.61%). Moreover, the smaller variant G1-3B ranks first all tasks
-rbbeckk-I--istlllll
such GraphWiz-7B-RR among models of similar parameters, surpassing the base model on average and achieves comparable performance with DeepSeek- R -isttill-ween- The results in the GraphWiz benchmark verify the strong zero-shot generalization ability of our G1 models.
Inntstuccc) by 13.64%
Table 19; Test accuracy (%) on the Graph Wiz benchmark.
connect
bipariite
topology
shortest
triangle
hamilton
subgraphh
cycle
flow
Model
32,00
53.75
25.75
7,50
2.75
3.75
2.50
38.25
12.00
19.80
Qwen2.5-3B -nn-struct (base)
58.00
60.50
38.50
4.00
5.75
15.50
7.50
75.00
63.25
36.44
G1-3B (Ours)
91.00
64.00
64,25
13.00
14,00
23.25
43.00
96.00
42.25
50.08
GriphWiz-RFTS
88.00
90.25
72.25
19.75
28.00
36.75
24.75
2,50
84.25
49.61
GraphWiz-POO-E
86.50
82.25
71.75
15.00
26.75
37,00
45.00
0.00
79.00
49.25
Llama-33 Instruct
64.75
81.00
58.75
11,50
3.50
4.25
9.25
19.25
33.03
SepsScc-RR--issill-eeeeee
87,00
90.00
42.75
11.00
18.25
36,00
40.00
84.75
57.00
51.86
Qwea2.5-7B -nsstruct (base)
79.00
72.25
40.75
4.25
13.50
28.75
11.50
91.25
61.00
44.69
G1-7B (Ours)
92.(0)
80.00
75.75
24.25
21.00
29.50
46.25
95.25
50.00
57.11
1.2 Detailed Results for MMLU-Pro
We present the detailed results for our evaluations on MMLU-Pro in Table 20 We first notice that although G1 models share close accuracies with their base model on average, they excel at notably different disciplines: G1-3B does the best Physies (56.18% while G1-7B is good CS (53.32%). Interestingly, RL training on graph problems in some cases improves Glover Qwen on non-STEM subjects such Health (53.0% v.s. 37.65% for 3B models and Business (62.76% v.s. 53.91%) for 7B models.
Table 20: Test accuracy (%) on the MML.U-Pro benchmark.
Physics
Other
Wistery
Healhh
1Jama-33 In-smee
14:79
15:91
13.30
6.50
13.89
18.54
11.28
23.91
13.25
9.71
|3:51
Qwer2.5 B-3-BBnestueee (hase)
38.49
31.18
46.21
37.34
58.92
31.06
31.23
45.25
46.24
18.07
19:40
37.65
41.22
54.25
38.54
CBT-SPT-3B
35.70
13.99
32.25
38.72
53.29
34.41
25.65
30.04
18.15
42.71
28.08
39.23
36.34
46.03
34:23
G1-3B (Ouns)
56.18
42.46
16.26
43.73
37.78
44.55
36.10
31,80
41.46
20.95
34.42
53.00
28.86
30.18
37.12
Llama 3.1 SB Instruct
28.79
17.13
33.96
34.03
32.28
41.83
24.91
18.80
43.89
66.45
35.28
36.10
31.75
28.26
/3202
DeepSeck RI Distill Qwen 7B
29.75
11.72
19.20
49.81
40.80
19.95
23.35
25.65
47.39
30.30
72.76
36.54
34.39
49.51
33:21
Qwes2.5 78 Instruct (base)
44.17
48.53
46.87
55.89
65.
21.44
54.53
53.91
27.04
49.50
42.64
53.66
33.27
33.96
44.75
CuT-SPT-77
44.36
55.51
44.61
29.82
51.08
64.84
45.97
41,45
46,42
37.01
33.87
45.61
21.44
52.01
66.54
GL-7B (Ouns)
46.43
51.19
68.76
40.91
47.70
53,90
32.40
62.76
25.61
49.88
51.50
51.71
53.32
36.07
48.56
1.3 Detailed Results for GraphArena
We report the detailed results for evaluations on the easy/hard problems from GraphArena in Table 21 and Table [2 respectively. We observe that G1 models perform equally or better compared to the other models on all tasks but Distance, in which G1 performs slightly worse than the Qwen models.
1.4
Detailed Results for Erdös
In Table 23
we show the performance for each task in Erdösfor our models and baselines in detail.
31

---

Table 21: Test accuracy (%) on the easy problems from the GraphArena benchmark.
Connected
Diameter
Distance
Neightur
GED
TSP
MCP
MCS
MIS
MVC
Model
-lamm-3.2-3B-Insste
8.00
16.00
15.00
50.00
9.00
2.00
15.00
10.00
7.00
5.00
Been2.5-3B-Instruuu (base)
20.00
11.00
47,00
48.00
37,00
17.00
3.00
41.00
4.00
2.00
G1-3B (Ours)
52.00
42.00
47.00
89.00
30.00
17.00
27.00
20.00
32.00
22.00
LLaMA2-7B-RFT
0.00
7,00
1.00
1.00
4.00
0.00
0.00
1.00
0.00
0.00
LLaMA2-7B
0.00
1.00
0.00
0.00
3.00
0.00
0.00
1.00
0.00
0.00
33.00
29.00
45.00
81.00
24.00
14.00
32.00
18.00
24.00
20.00
DeepSeek-R Desssil--wee--BB
77.00
41.00
64.00
82.00
22.00
30.00
44.00
40.00
56.00
17.00
Qwen2.5-7B Instruct (Ours)
79.00
15.00
84.00
22.00
22.00
39.00
41.00
28.00
21.00
G1-7B (Ours)
86.00
63.00
62.00
99.00
30.00
38.00
52.00
51.00
50.00
63.00
Table 22: Test accuracy (%)
the hard problems from the GraphArena benchmark.
Connected
Diameter
Distance
Neighbor
GED
TSP
MCP
MCS
MIS
MVC
Model
Llama-3.2-3B-Innse
0.00
1.00
7.00
19.00
3.00
0.00
0.00
0.00
0.00
1.00
Qwen2.5-33 3---2..--B-Insstucc (base)
4.00
4.00
28.00
22.00
7.00
1.00
0.00
1.00
G1-3B (Ours)
19.00
12.00
25.00
51.00
3.00
0.00
0.00
1.00
7.00
LLaMA2-7B-RFT
0.00
2.00
0.00
0.00
0.00
LLaMA2-7B-DPO
0.00
3.00
1.00
0.00
0.00
1omma-3.1-8B-Imaaee
4.00
3.00
DeepSeck-RI --iit--R------------- Distill-Qeen-7B
18.00
4.00
33.00
36.00
1.00
0.00
1.00
Qwen2.5-77 5-B--ruttt (base)
27.00
4.00
68.00
2.00
G1-7B (Ours)
31.00
27.00
35.00
84.00
3.00
0.00
6.00
39.00
32

---

Qwen 728
100.00
522000
80.00
66.00
53.00
52.00
49.00
39.00
100.00
100.00
82.00
94.00
62.00
69.00
66. 66,00
57.00
69 69.00
93.00
15.00
80.00
67.00
75.00
26,00
43.00
10.00
60.00
41.18
0.06
17.61
1.00
74.00
47.70
4000
55.00 55.00
64.00
29 79-02
1.00
3,00
13:00
10.00
7.00
12.00
21.00
L.amss 700
00
91 52
72.00
25.00
64.00
29.00
28.00
98.00
99:00
94.00
99.00
51.90
52.00
49.00
64.00
77.00
87.00
16:00
90,00
49.00
62.00
36.00
24.00
47.00
9.00
62.00
3.00
53.71
3.00
23.00
7.00
43.00
62.00
7.00
28.55
1.00
1.00
7.00
4.98
7.00
5.00
10.00
G1-78
100.00
99.00
93.00
97.00
98.00
98.00
99.00
66.00
103.80
100.00
99:00
99.00
98.00
88.00
92.00
96.90
100.00
50000
97.00
97.99
50.00
92.00
43.00
11.90
51.00
59.00
70:00
35,00
49.00
47.00
68:00
78.00
31.90
39.00
79.00
82.00
30.00
23.90
12.00
2.00
79.00
9.98
13.00
5.00
42,00
CSPF-75
100,000
68.00
80.11
34,00
44.00
93.00
50.00
97.00
09.00
82.00
100.00
25.00
66.00
$1.00
98.00
76.00
17.00
93.00
901
80.0
25.00
5.00
20.00
55.00
78.00
25.00
39.00
50.00
58.00
21.00
37.00
40.00
36.00
7.00
40.00
11.00
4.00
24,00
3.00
10.00
18.00
DSPT-79
100.00
74. 10.00
76.00
39.00 09.00
43.00
95.00
52.00
65.00
98. 00
99 00
88 00
100.00
76.00
62.00
80.00
76.00
97.00
78 73.00
18:00
93.00
80:00
13.00
77.00
25.00
25.00
55.00
77.00
41.00
40
00
03.00
74.00
38 00
42.00
31,00
11.00
4 4.00
6:00
10.00
10.00
GWi-D
0.00
28.00
(1.00
0.00
0.00
83,00
0.00
56.00
58.00
0.00
58,00
1.00
10.00
0.00
66.00
5.00
0.00
0.00
67.00
2.00
0.00
0.00
1.00
0.00
0.00
0.09
4.00
101
200
5000
0.00
2,00
0.00
6.00
2.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
GWiz-R
34.00
11000
0.00
65.00
0.00
52.00
27.00
0.00
22.00
3.00
6.00
0.00
53,00
3.00
0.00
51.0
2.00
0.00
3,00
0.00
3.00
0.00
3000
101
100
600
1.00
0.00
3.00
0.00
0.00
0.00
0.00
0.00
0.00
Table 23: Accuracy comparison models across tasks
R R1-78
27.00
79.08
74.00
12.00
83.00
23.00
46.00
103.00
995.00
96.00
100.00
82.00
65.00
79.00
42.00
52.00
95.00
37.00
92.00
57.00
76.00
86000
40.00
14.00
62.00
35.00
62.00
26,00
39.00
29.00
52.00
64.00
25.00
6.00
54.00
58.00
37.00
5.00
1.00
11:00
31.00
12.00
22.00
3.00
21,00
Math-78
27 10
48.0
38,00
9.00
54,00
10.00
14.00
52.00
99 00
79 79.00
22.0
36.00
30.00
3.00
79.00
70.00
1.00
89
89.00
43.0
40.00
2.00
41.00
7.00
11.00
27.00
11.11
35.00
21.00
6.00
5.00
21.00
29.00
1.00
0.00
2.00
3,00
4,00
1.09
6,00
Qwen-7P
90,00
27 10
52.00
58 88.00
12.00
55.00
27 77.00
15 15.00
96.00
96 10
86 86,00
89.0
44.00
24.00
77.00
1.00
81 01.00
8.00
52.0
45.00
12.00
41 41.00
11.00
8.00
31 31,00
22.00
34 00000
25 25.00
1.00
30,00
30 30,00
3,00
0.00
0.00
2.00
6.00
4.00
2.00
9.00
27
35.
35
99.00
57.000
56.00
16.00
5.00
45.00
12,000
17.00
73.00
92.00
72,00
80.00
42.00
12.00
25.00
34,00
53,00
44,00
0.00
4,00
55.00
15.00
7,00
17.00
3,00
31,00
6.00
14,00
20.00
26.00
25,000
24.000
12,000
26,00
0.80
1.00
0.00
0.00
1.00
3,00
I.aamo-88
G1-38
1000000
99 00
91.00 (0
96.00
95.00
89.00 90.00
100.00 00
81.00
100.00
190.00
95.00 50
99.
94000
82.00
79.00
82.00
90.00
95.00
51.00
98
89
20
92.00
24.00
4300
58.00
62.00
25.00
46.00
39000
56.00
67.00
22.00
39:00
67.00
68.00 .0
19.00
16.00
1.00
1.00
1300
8.00
2,00
21,00
CSF7-38
97.00
31 00
71 (0)
59.00
30.00
00
50
17.00
97.00
58. 00
53 00
09.00
89 00
00
63.00
47.00
86.00
84.00 00
17.00
79.00
55. 00
00
22.00
40.00
24.00
51.00
13.00
31.00
00
47.00
30.00
30.00 00
48 00
55.00
15.00
9.00
0.00
3.00
2.00
6.000
3.00
8.00
DSPT- 1-
100,00
72.00
71. 71.0M
31 10.00
52.00
98.00
6 0.000
100.00
98.00
94 00
99. 99.00
74.00
21.00
85.0
53.00
93.00
83 $1.00
23
95
51.00
92.0
80.00
25. 35.00
29.00
63.00
74.00
25
55 55,00
06
66.00
76.00
33,00
38.00
54.00
36.00
17.00
44.00
10.00
10.00
8.00
14.00
11.00
22. 22.00
Qwen- 38
94.00
23.000
44,00
31.00
3.00
51.00
9.00
8:00
80.00
95.00 25.000
58,00
75.00
6.000
31,00
27.00
62.00
48.00
2.00
81.00
7.00
39.200
10.00
3,00
24,00
5.00
19.00
8.00
8:00
15.00
23,00
14,00
4.00
4,00
17,00
0.30
0.00
1.00
1.000
1.00
3,00
57 00
23 0.0
9.00
0.00
33.00
0.00
5.00
60.00
88 00
26 00
47 07.00
1.00
13.000
9.00
57.00
23 30
1.00
0..00
09
2.00
2.00
0
3,00
4.00
11 3.00
1.00
12.00
9.00
12 00
10.00
1.00
4.00
13.00
16.00
1.00
0.00
0.00
2,00
5.00
0.00
0.00
1.00
1.aemo-33
83
78
63-min
64.71
73.08
77.78
17.39
100.00
33.33
42.86
100.00
95.00
100.00
88-46
94
82.61
100.00
100.00
31.58
93.45
83.71
92.M
100.00
27.78
31.58
89.47
23.33
38.46
9412
69.23
87.50
48.00
50.00
58.82
61.11
9.09
4.00
71.43
55,56
73.68
4.76
60.87
28.
GPF-40
100,00
-1-11
3.68
72.22
52.17
60.00
73.33
100.00
100.00
95-45
100.00
92.31
72.22
60.87
40.74
96.15
109.00
10.53
71433
68:00
94.12
11.11
0.00
56.84
13.33
69.23
17.55
7.69
68.75
60.00
18.18
35.29
66.67
7.69
0.00
0.00
4,76
5.56
0.00
0.90
0.00
13.04
connected, componcnt number
bipurtiic maximumm cacammmmmmmaiiiie matching
invelligg salesman, problem
strongly connected number
resource allocation lndex
commnn neighhor number
minimunn spanning
adumni odar index
clastriin snefficient
local connctivity
Succrdd aecard__eelleeee coellicten
min odge coveting
degree contrality
weight. masdingin
dovenexs, conmanty
neweeeines centrality
wrg.neige neighter degree
hurmonic, contralay
ionnophic mapping
global globl__ effeceec
andependont
harritooian path
cover
Bode pomber
dominating set
odge odge exitictoos
Joummmen
sioettol pulhs
maximim flww
wiener Index
Taok
neighbor
biss
has, cycle
dis
segullar
degree
donsity
colleia
hiparite
dianster
baryenner
rnduns
topolegical,
perphery
mangles
teilges
33

---

Discussion on Reward Weighting
In Section 5.3
we analyze the factor of data mixture by introducing model G1-Hard-3B trained exclusively on Hard and Challenging tasks. We observe that G1-Hard-3B effectively improves performance on hard tasks, while easier tasks still lags behind G1-3B (Table[4).
In this section, we further explore soft data mixture strategy that scales the reward for each task according to its difficulty. In detail, we fix the scaling factor as 0.2, 0.4, 0.6, and 0.8 for Easy, Medium, Hard and Challenging tasks, respectively, and name the resulting model as G1-Soft-3B. As shown in Table 24 G1-Soft-3B achieves a balance between G1-3B and G1-Hard-3BB. On easy tasks, G1-Soft-3B largely surpasses G1-Hard-3B and on par with G1-3B which applies uniform scaling across all tasks. For hard tasks, G1-Soft-3B outperforms G1-3B (e.g., 11.71% % v.s 7.57% for Challenging tasks), but there is still gap to G1-Hard-3B. The results show the soft scaling method take effects, but the RL optimization remains dominated by easy tasks. This suggests that further reducing the reward scaling factor for easy tasks dynamic weighting strategy could be beneficial a direction we leave for future work.
Table 24: Test accuracy (%) our benchmark. denotes the tasks excluded in model training. G1-Hard-3B is only RL-trained on Hard and Challenging tasks, G1-Soft-3B is trained on all tasks but with different reward scaling factors based on the task difficulty.
Category
Model
Easy
Medium
Hard
Challenging
Average
Base Model
Qwen2.5-3B- L-n-intt-ttt
45.71
30.18
9.44
1.29
22.72
Direct-SFT-3B
74.43
75.27
43.69
14.43
53.78
G1-3B
94.86
84.64
41.25
7.57
59.76
Ours
C1-Hard-3B
69.36*
70.64*
48.50
17.43
53.30
G1-Soft-3B
96.07
83.55
40.88
11.71
60.38
K
Detailed Description of Erdös
K.1
Comparing Erdös with Other Graph Reasoning Benchmarks for LLMs
There is growing interest in evaluating LLMs' graph reasoning abilities. NLGraph 41 evaluate LLMs on graph- theh--the tasks and discover preliminary yet brittle reasoning abilities in the face of spurious correlations and large graphs. Later, GraphArena [38] and GraCoRe (55) include a broader task coverage and recently released LLMs, finding that even OpenAl ol-mini struggles lot with complex tasks. Moreover, GraphEva12000 [46] and ProGraph (23 emphasize code-oriented problem solving using library-based prompts, and GraphOmni [48] unify varying graph types, encodings,
and prompt styles for a comprehensive evaluation. Overall, these benchmarks suggest that L.MMs overall demonstrate moderate success simple tasks but struggle with abstraction, generalization, and larger or more complex graph instances. Nevertheless, these datasets are either too small (c.g.. thousands of examples) not diverse enough (c.g., 8 tasks in NLGraph) for training general-purposs graph reasoners, which motivates the design of Erdös. We show the detailed comparison of existing graph reasoning benchmarks for LLM with our Erdösin Table 25
Table 25: Comparison of existing graph-theoretic reasoning benchmarks for LLM with our Erdös.
Benchmark
#Tasks
# Q-A Samples
Graph Types
Node Size
NLGraph
41
8
5,902
Synthetic
5 35
GraphWiz
9
3,600
Synthetic
2 to 100
GraphArena
38
10
10,000
Real-world
4 to 50
GraCoRe
55
19
5,140
Synthetic & Real-world
8 to 30
GraphOmni
48
6
241,726
Synthetic
5 to 30
Erdōs(ours)
50
100,000
Real-world
5 to 35
34

---

K.2
Full list of tasks in Erdös
Table 26: Benchmark exmaples
Task adamic adar
Prompt
Answer 1.5859
The task is to determine the Adamic-Adat index of two nodes in graph.
index
The Adamic-Adar index is the sum of the inverse logarithm of the degrees of the common neighbors of the two nodes.
The input graph is guaranteed be undirected.
Here is an undirected graph containing nodes from 1 to 9. The edges are: (1, 5), (1, 4), (1, 8), (1, 2), (1, 3), (1, 7), (5, 2). (5.3), (5, 4), (5, 9). (5, 6). (4, 8), (4, 9), (4, 7), (8, 2), (8, 3), (8, 6). (8, 7), (8, 9), (2, 3), (2, 7), (2, 6), (), (3, 7), (7, 6). (7, 9). Question: What is the Adamic-Ade index between node 4 and node 6?
You need to format your answer as a float number.
avg neighbor
The task is to determine the average degree of the neighbors of 1.5 node in the graph.
degree
Here is undirected graph containing nodes from to 8. The
edges are: (1, 7), (1, 8), (1, 4), (7, 8), (8, 5), (2, 3), (2, 6), (3, 5). Question: What is the average neighbor degree of node 2 in the graph?
You need to format your answer float number.
barycenter
The task is to determine the barycenter of a graph.
[1. 11,2.6 6, 7]
The barycenter of graph is also called the median. It includes the node that minimizes the sum of shortest path lengths to all other nodes.
The input graph is guaranteed to be connected.
Here is an undirected graph containing nodes from 1 to 7. The edges are: (1, 2), (1, 6), (1. 5), (1, 7). (1, 4). (2, 6). (2, 5), (2, 7), (2, 4), (6, 4). (6, 5), (6, 7), (7, 3). (7. 4).
Question: What is the barycenter of the graph?
You need to format your answer as a list of nodes in ascending order, e.g., [node-1, node-2, ... node-n].
betweenness centrality
The task is to determine the betweenness centrality of a node in 0.0679 the graph.
Betweenness centrality of node *u" is the sum of the fraction of all-pairs shortest paths that pass through *u*
Here is an undirected graph containing nodes from to 9. The edges are: (1, 6). (1, 4), (1, 8), (1, 9), (6. 2), (6, 7), (4, 7), (4. 5), (8, 3), (8, 5), (8. 7), (9, 3), (9, 5), (2. 7).
Question: What is the betweenness centrality of node 5 in the graph?
You need to format your answer as float number.
bfs
The task is to determine the breadth-first search (BFS) traversal
[(1,2). (1.
order given a starting node.
5). (2,
Stop when the BFS cannot be continued.
(2, (),4), (4.
Here is an undirected graph containing nodes from 1 to 7. The edges are: (1, 2), (1, 5), (2, 3), (2, 4). (5, 3). (5, 4), (3, 4), (4. 7), (7,6). 6).
7), (7.
Question: What is the breadth-firs. search (BFS) traversal order for the starting node 1?
You need to format your answer list of edges, e.g., [(ul, vl),
(u2, v2), ... (un, vn)].
35

---

Continuing table 26
Task
Prompt
Answer
bipartite
The task is determine the maximal matching in bipartite graph.
[(I, 3), (2,
maximum matching
4)]
The input graph is guaranteed to be bipartite graph. Here is an undirected graph containing nodes from to 4. The edges are: (1, 3), (1, 4), (2. 3), (2, 4).
Question: What is the bipartite maximal matching of the bipar- tite graph?
You need to format your answer as a list of edges ascending dictionary order, c.g., [(ul, v1), (u2, v2). (un, vn)].
bridges
The task is to find all bridges of graph.
A bridge is an edge in graph whose removal increases the number of connected components.
The input graph is guaranteed to be undirected.
Here is an undirected graph containing nodes from to 5. The edges are: (1, 2). (1, 3), (1. 4). (2, 3), (2, 4), (2, 5), (3, 4), (3, 5). Question: What the bridges of the graph?
You need to format your answer as a list of edges in ascending
dictionary order, e.g., [(u1, v1). (u2, v2), ..., (un, vn)].
center
The task is to determine the center of graph.
[2. 6]
The center of graph includes the node that minimizes the maxi- mum distance to any other nodes in the graph.
The input graph is guaranteed to be connected.
Here is an undirected graph containing nodes from to The edges are: (1, 5). (5, 2). (2, 6), (6, 4), (3,4).
Question: What the center of the graph?
You need to format your answer as a list of nodes in ascending order, e.g., [node-1, node-2, ... node-n]. The task is to determine the closeness centrality of a node in the graph.
closeness cen- trality
0.4667
For a node *u* closeness centrality is the reciprocal of the average shortest path distance *u* over all #n-1* reachable nodes. For directed graphs, it computes the incoming distance *u*
Here is an undirected graph containing nodes from to 8. The edges are: (1, 3), (3, 6), (2, 8), (2, 6). (8. 6), (8, 7), (4, 7), (7, 5). Question: What is the closeness centrality of node in the graph?
You need to format your answer as a float number.
clustering coefficient
The task is to compute the clustering coefficient for a given node.
1.0
For unweighted graphs, the clustering of node is the fraction of possible triangles through that node that exist.
Here is an undirected graph containing nodes from 1 to 7. The edges are: (1, 4), (1, 5). (1, 3), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (5, 2), (5, 3), (5, 6). (5, 7), (2, 6), (2, 7), (6. 7). Question: What is the clustering coefficient of node 6?
You need to format your answer as a float number.
common neighbor
The task is to determine common neighbors between two nodes in the graph.
[7]
The input graph is guaranteed be undirected. Here is an undirected graph containing nodes from I to 7. The edges are: (1, 7), (1, 6), (1, 4), (1, 5), (7, 2). (7. (6. 2), (4, 3), (5,
Question: What are the common neighbors between node 2 and node 3?
You need to format your answer as a list of nodes in ascending order, e.g., [node-1, node-2, ... node-n].
36

---

Continuing table 26
Task connected component number
Prompt
Answer
The task is determine the number of connected components in an undirected graph.
A connected component is subgraph where any two nodes are connected to each other by paths.
Here is an undirected graph containing nodes from 1 to 10. The edges are: (1, (1, 7), (1, 5), (1, 9), (1. 10), (1, 6). (1, 2), (4, 2), (4, 3), (4, 8), (4, (), (4, 9), (4, 10), (7, (7, (7,
8). (7, 9). (5, 2), (5, (), (5, 8), (5, 9), (5, 10), (9, 2),
(9, 8). (9, 10), (10, 2), (10, 3), (10, 8), (6. 2), (6, 3), (6, 8), (2.
(2, 3).
Question: How many connected components are there in the
graph?
Your answer should be an integer.
degree
The task is to determine the degree of a node in the graph. For the undirected graph, you should count the edge between two nodes only once.
2
Here is an undirected graph containing nodes from 1 to 6. The edges are: (1, 6). (6, 5), (2, 3), (2, 4), (3. 5).
Question: What is the degree of node 6 in the graph? Your answer should be integer.
degree cen-
The task is to determine the degree centrality of a node in the graph.
0.5
trality
Degree centrality for a node the fraction of nodes is con- nected to.
Here is an undirected graph containing nodes from to 7. The edges are: (1, 2). (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (2, 6), (4, 3),
(4, 5), (4, 7), (5, 3).
Question: What is the degree centrality of node 3 in the graph?
You need to format your answer float number.
density
The task is to determine the density of the graph.
0.7
Density is defined as the ratio of the number of edges in the
graph to the number of possible edges.
Here is undirected graph containing nodes from 1 to 5. The
edges are: (1. 2). (1, 3). (2, 3), (2, 4), (2. 5), (3, 4), (4, 5).
Question: What is the density of the graph?
You need to format your answer as a float number.
df's
The task is to determine the depth-first search (DFS) traversal
((I,2), (I,
order given a starting node.
3), (3, 9),
Stop when the DFS cannot be continued.
(1, 6)]
Here is an undirected graph containing nodes from to The
edges are: (1, 2). (1, 3), (1, 6), (3, 9), (4, 8), (4, 5), (8, 7). Question: What is the depth-first search (DFS) traversal order for the starting node 1?
You need to format your answer list of edges, e.g., [(ul, vl), (u2, v2), (un, vn)].
diameter
The task is to determine the diameter of a graph.
5
The diameter of a graph is the longest shortest path between any nodes in the graph.
The input graph is guaranteed to be connected.
Here is undirected graph containing nodes from 1 to 7. The edges are: (1. 5), (1. 7). (I, 4), (5, 6), (2. 6), (2, 3).
Question: What is the diameter of the graph?
You need to format your answer as a float number.
37

---

Continuing table 26
Task
Prompt
Answer [1 4]
dominating set
The task is to determine the dominating set of graph. A dominating set is a subset of nodes such that every node in the graph is either in the set adjacent to node in the set. For directed graphs, any node not in the dominating set must be successor of node within the set.
Here an undirected graph containing nodes from to The edges are: (1, 2). (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (5, 6), (7, (7, 4).
Question: What is the dominating set of the graph?
You need format your answer as a list of nodes in ascending order, c.g., [node-1, node-2, ... node-n].
edge exis-
The task is determine there an edge connecting two nodes.
No
tence
For an undirected graph, determine if there is edge between nodes *u and *y*, For directed graph, determine if there is edge from *u* to *y*.
Here is an undirected graph containing nodes from to The edges are: (1, 2), (1, 6), (3, 8), (3, 4), (8, 4). (8, 5), (8, 7), (4, 7),
(4, 5), (7. 5).
Question: Is there edge between node 5 and node 3? Your answer should be Yes or No.
edge number
The task is to determine the number of edges in the graph. For the undirected graph, you should count the edge between two nodes only once.
12
Here is an undirected graph containing nodes from 1 to 10. The edges are: (1, 10), (1, 8). (10, 7), (8, 6), (2, 5), (2, 4), (2, 6), (5,
4), (5, 9). 3), (4. 9), (3, 7).
Question: How many edges are there in the graph?
Your answer should be integer.
global effi- ciency
The task is to determine the global efficiency of a graph.
0.5310
Global efficiency the average efficiency of all pairs of nodes.
The efficiency of a pair of nodes is the multiplicative inverse of the shortest path distance between the nodes.
The input graph is guaranteed to be undirected.
Here is undirected graph containing nodes from 1 to 7. The edges are: (1, 5). (1, 4), (5, 2), (2, 7), (7, 3), (3, 6).
Question: What is the global efficiency of the graph?
You need to format your answer as float number.
hamiltonian
The task is to return Hamiltonian path in a directed graph. A Hamiltonian path is path directed graph that visits each vertex exactly once.
[2, 1, 3, 8, 7,
path
The input graph is guaranteed be directed and tournable.
Here is a directed graph containing nodes from 1 to 8. The
edges are: (2, (2, 4), (2, 5), (2, 6), (2, 7), (1, 3), (1, 4), (1, 7), (3, 2), (3, 7), (3, 8), (4, 3), (4, 5), (4, 7), (5, 1), (5, 3). (5, 8), (6, 1), (6, 3), (6, 4), (6. 5), (7. (7, 6), (8. 1), (8. (8, 4), (8, 6),
(8, 7).
Question: Return Hamiltonian path in the graph. You need to format your answer as a list of nodes, e.g., [node-1, node-2, ... node-n].
38

---

graph vertices within the same Continuing table 26
Task
Prompt
Answer
harmonic centrality
The task is to determine the harmonic centrality of node in the graph.
1.0
Harmonic centrality of node *u is the sum of the reciprocal of the shortest path distances from all other nodes to u.
Here is a directed graph containing nodes from I to 8. The edges are: (6, 2), (6, 1), (6. 4), (6, 5), (6. 3), (7,8) 8).
Question: What is the harmonic centrality of node 3 in the graph?
You need to format your answer as float number.
has cycle
The task is to determine if the graph has a cycle.
Yes
Here is an undirected graph containing nodes from 1 to 9. The edges are: (1, 2), (1, 4), (1, 5), (2, 4), (2, 5), (4, 9), (5, 3), (3, 6), (3, 8), (6, 8), (9, 7).
Question: Does the graph have cycle?
Your answer should be Yes or No.
is bipartite
The task is to determine if the graph bipartite.
Yes
A bipartite graph is a graph whose nodes can be divided into disjoint sets such that set are adjacent.
Here is undirected graph containing nodes from I to 6. The edges are: (1. 4). (4, 3). (2, 5), (2, 3), (5, 6), (3, 6).
Question: Is the graph bipartite? Your answer should be Yes or No.
is eularian
The task is to determine if the graph is Eulerian. An Eulerian graph is a graph that contains an Eulerian circuit, which is cycle that visits every edge exactly once.
Yes
Here is an undirected graph containing nodes from to The edges are: (1, 5), (1, 3), (1, 2), (1, 4), (5, 2), (3, 2), (3, 4), (3, 6),
(2, 4), (4, 6).
Question: Is the graph Eulerian?
Your answer should be Yes or No.
is regular
The task is to determine if the graph is regular.
No
A regular graph a graph where every node has the same de- gree.
Here is undirected graph containing nodes from 1 to 10. The edges are: (1, 5), (1, 7), (1, 10), (5, 2), (5, 10), (7, 8), (7, 10), (3, 9). (3, 8), (3, 4), (9, 4). (4. 6).
Question: Is the graph regular? Your answer should be Yes or No.
is tournament
The task is to determine if the graph is a tournament.
No
A tournament is directed graph where every pair of nodes is connected by a single directed edge.
The input graph is guaranteed to be directed.
Here is a directed graph containing nodes from to 10. The edges are: (1, 2), (,, 1), (2, 4), (4, 2). (4, 3), (3, 1), (5, 2), (5, 4), (6, 2). (6. 5). (7, 8), (8, 6), (9, 7). (10, 7).
Question: Is the graph a tournamen??
Your answer should be Yes or No.
39

---

Continuing table 26
Task
Prompt
Answer
isomophic mapping
Given pair of isomorphic graphs, determine the node corre- spondence between the two graphs.
(0: 102,
3: 101,
The first graph is: G describes undirected graph among 0,
2: 105,
2, 3, 4, 5, and 6. this graph: Node 0 is connected to nodes 6,
4: 103,
100, 3, 4. Node is connected nodes 4, 5, 6. Node 2 is connected
1: 106,
to nodes 3, 4. Node is connected to nodes 0, 2, Node
connected to nodes 0, 1, 2. Node 5 is connected to nodes 1, 3. Node connected to nodes 0, 1.
104)
The second graph is: G describes an undirected graph among 102, 106, 105, 101, 103, 100, and 104. In this graph: Node 100 is connected to nodes 106, 101. Node 101 is connected to nodes 102, 105, 100. Node 102 is connected nodes 104, 101, 103. Node 103 is connected to nodes 102, 106, 105. Node 104 is connected nodes 102, 106. Node 105 is connected to nodes 101, 103. Node 106 is connected to nodes 103, 100, 104.
Provide node matching dictionary such as { |Graphl #Nodel: Graph2 #Nodel, Graph I #Node2: Graph2 #Node2, ...)
jaccard coeffi- cient
The task is determine the Jaccard coefficient of two nodes in a graph.
0.3333
The Jaccard coefficient is the size of the intersection divided by the size of the union of the neighbors of the two nodes.
The input graph is guaranteed to be undirected.
Here is an undirected graph containing nodes from to 5. The edges are: (1, 2), (1, 3). (2. 5), (2, 3), (3, 5), (5, 4).
Question: What is the Jaccard coefficient between node and node 4?
You need to format your answer float number.
local connec- tivity
The task is to determine the local connectivity of two nodes in the graph.
No
Local connectivity is whether there exists at least one path be- tween the two nodes.
Here is a directed graph containing nodes from to The edges are: (1, 7). (7, 6). (3, 1), (4, 3), (5, 4), (6, 2).
Question: What is the local connectivity between node and node 4 in the graph?
Your answer should be Yes or No.
max weight matching
The task is to determine the maximum weight matching of graph.
[(2, 4), (5, 7). (6, 3)1
A matching is a set of edges without common vertices. A max- imal matching cannot add more edges and still be matching.
The weight of a matching is the sum of the weights of its edges. If not specified, all edges have equal edge weights. The input graph is guaranteed to be undirected. Here is an undirected graph containing nodes from 1 to 7. The edges are: (1. 7). (7, 5), (2, 4), (2, 5), (4, 3), (3, 6).
Question: What is the maximum weight matching of the graph? You need to format your answer as a list of edges ascending
dictionary order, e.g., [(ul, v1), (u2, v2), ... (un, vn)].
40

---

Continuing table 26
Task maximal in- dependent set
Prompt
Answer
The task is determine the maximal independent set guaran- teed to contain given node in the graph.
[3, 6]
An independent set is set of nodes such that the subgraph induced by these nodes contains no edges. maximal indepen- dent set is independent set such that it is not possible to add new node and still get an independent set. The input graph is guaranteed to be undirected. Here is an undirected graph containing nodes from to The edges are: (1. 2). (1. 6). (1. 3), (2, 3), (2. 4), (2, 5), (3, 5), (4, 5). Question: What is the maximal independent set that includes node 4 of the graph?
You need format your answer as a list of nodes in ascending order, e.g.. [node-1, node-2, node-n].
maximum flow
The task is determine the value of the maximum flow for the given source node and sink node.
0.0
The maximum flow is the greatest amount of flow that can be sent from the source to the sink without violating capacity con- straints.
Here is a directed graph containing nodes from to 5. The
edges are: (2, 5, 8). (3, 1, 9), (3, 5, 3). (4, 2, 4). (u .v. w) denotes the edge from node *u* to node *y* has a capacity of #w*
Question: What is the value of the maximum flow from node 3 to node 2?
You need to format your answer as float number.
min edge cov- ering
The task is to determine the minimum edge covering of a graph.
[(2, 1),
An edge cover is set of edges such that every vertex in the graph incident to at least one edge in the set. The minimum edge cover is the edge cover with the smallest number of edges. The input graph is guaranteed be undirected.
2). (7, 4) (8, 3), (9,
6)]
Here is an undirected graph containing nodes from 1 to 9. The edges are: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4). (2, 5). (3, 4), (3, 6), (3, 7), (3, 8). (3, 5). (4, 7). (4, 8), (5, 6), (5. 7), (6, 7), (6, 9), (7, 9).
Question: What the minimum edge covering of the graph? You need to format your answer as a list of edges in ascending dictionary order, c.g., [(ul, v1). (u2, v2). .... (un, vn)].
min vertex
The task is to determine the minimum vertex cover of graph. A vertex cover is a set of nodes such that every edge in the graph is incident to at least one node in the set.
[2, 5]
cover
Here is an undirected graph containing nodes from to 5. The edges are: (1, 2), (2, 3), (3. 5), (5, 4).
Question: What is the minimum vertex cover of the graph? You need to format your answer as a list of nodes in ascending order, e.g.. [node- 1, node-2, ... node-n].
minimum spanning tree
The task is to determine the minimum spanning tree of a graph. A minimum spanning tree is subset of the edges that connects all vertices in the graph with the minimum possible total edge weight. If not specified, all edges have equal edge weights. The input graph is guaranteed to be undirected and connected. Here is an undirected graph containing nodes from I to 9. The edges are: (1, 2), (1, 8), (1, 5). (1, 6), (1, 4), (1, 7), (1, 9), (2, 5), (2, 6), (2, 4). (2, 7), (2, 3), (8, 3). (8, 4), (8, 6), (8, 7), (5, 3), (5, (5, 6) (5, 7), (5, 9). (6. 3), (6. 4), (6. 7). (6, 9), (4, 3), (4, 7), 9), (7, 9), (9, 3).
(1,,2)
(1,5),
61,
(1,
91,
3)]
Question: What is the minimum spanning tree of the graph? You need to format your answer as a list of edges in ascending dictionary order, e.g., [(ul, v1). (u2, v2), .... (un, vn)].
41

---

Continuing table 26
Task neighbor
Prompt
Answer [3. 10]
The task is to determine the neighbors of node in the graph. For directed graph, you should return the successors of the node.
Here is an undirected graph containing nodes from 1 to 10. The edges are: (1, 3), (1. 9), (1, 6). (1, 7), (3, 2). (3, 8), (3, 9), (6. 7), (2, 10), (10, 8), (4, 5).
Question: What are the neighbors of node 2 in the graph?
You need to format your answer as a list of nodes in ascending order, c.g.. [node- node-2, ... node-n].
node number
The task is to determine the number nodes in the graph.
10
Here is an undirected graph containing nodes from 1 to 10. The edges are: (1, 10), (1, 3), (10, 6). (10, 8), (3, 7), (3, 4), (2, 7), (2, 5), (2, 9), (5, 9), (5, 8), (9, 4), (8, 6).
Question: How many nodes are there in the graph?
Your answer should be an integer.
periphery
The task is to determine the periphery of a graph.
[1. 4, 6]
The periphery of graph is the set of nodes with the maximum eccentricity. The eccentricity of node is the maximum distance from this node to all other nodes in the graph.
The input graph is guaranteed to be connected.
Here is an undirected graph containing nodes from 1 to 6. The edges are: (1, 3), (3, 2), (3, 4), (3, 5), (3. 6).
Question: What the periphery
the graph?
You need to format your answer as a list of nodes in ascending order, e.g.. [node- 1, node-2, node-n].
radius
The task is to determine the radius of graph.
2
The radius of a graph is the minimum eccentricity of any node in the graph. The eccentricity of a node is the maximum dis- tance from this node all other nodes the graph.
The input graph is guaranteed to be connected.
Here is undirected graph containing nodes from to 5. The edges are: (1, 2), (2, 3), (3, 4), (3, 5), (4, 5).
Question: What is the radius of the graph?
You need to format your answer as a float number.
resource allo-
The task is determine the resource allocation index of two nodes graph.
0.25
cation index
The resource allocation index of two nodes is the sum of the inverse the degrees of the common neighbors of the two nodes.
The input graph is guaranteed be undirected.
Here is an undirected graph containing nodes from 1 to 5. The edges are: (1, 2). (1, 3), (2, 3), (3, 4), (3, 5), (4, 5).
Question: What is the resource allocation index between node and node 4?
You need to format your answer as a float number.
shortest path
The task to determine the shortest path between two nodes.
[1. 4.
The input nodes are guaranteed to be connected.
6)
Here is undirected graph containing nodes from to 6. The edges are: (1, 2), (1, 3). (2, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 6). Question: What is the shortest path between node and node 6? You need to format your answer as a list of nodes, e.g., [node-1, node-2, ... node-n].
42

---

Continuing table 26
Task strongly con-
Prompt
Answer
The task is determine the number of strongly connected com- ponents in a directed graph.
6
nected num- ber
A strongly connected component is maximal subgraph where every node is reachable from every other node. Here is a directed graph containing nodes from I to 6. The edges are: (2, 5). (5, 1). (3, 4), (6, 2).
Question: How many strongly connected components are there in the graph?
Your answer should be an integer.
topological sort
The task is to determine the topological sort of a directed acyclic graph (DAG).
4,
3, 21
Here is a directed graph containing nodes from to The
edges are: (1, 6), (1, 5). (1, 4), (1, 3), (1, 2).
Question: What is the topological sort of the directed acyclic graph (DAG)?
You need to format your answer a list of nodes, e.g.. [node-1,
node-2, .... node-n].
traveling salesman problem
The task is to determine the minimal cost of the Traveling Sales- man Problem (TSP).
27.0
The Traveling Salesman Problem asks for the shortest possible route that visits each vertex exactly once and returns to the starting vertex.
The input graph is guaranteed be a complete graph. Here is an undirected graph containing nodes from 1 to 8. The
edges are: (1, 2, 9), (1, 3, 3), (1, 4, 6), 51 8), (1, 6, 7), (1, 7, 4), (1, 8, 9), (2, 3, 10), (2, 4, 11), (2, 5, 5, (2. 6. 11), (2, 7, 1), (2, 8, 9), (3, 4, 11), (3, 1), 6, 9), (3. 8, (4, 5, 8), (4, 6, 3). (4, 7, 4), (4, 8, 8), (5, 6, 3), (5, 3,, (5, 8, 10), (6, 8), (6, 8, I), (7, 10). (u w) denotes the edge from node *u*
node *y* has a weight of *w*
Question: What is the minimal cost of the Traveling Salesman Problem on the graph?
You need to format your answer as float number.
triangles
The task is to find the number of triangles that include a specific node one vertex.
A triangle is a set of three nodes that are all connected to each other.
The input graph is guaranteed be undirected. Here is an undirected graph containing nodes from 1 to 8. The
edges are: (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2. 3), (2, 4), (2, 5) (2. 6), (2. 7), (2, 8), (3, (3, (3, 6). (3, 7), (3, (6. (6, 8),
8). (4, 5) (4, 6), (4, 7), (4. (5, 6), (5, 7).
(7, 8).
Question: How many triangles include node in the graph?
Your answer should be an integer.
43

---

Continuing table 26
Task weighted min-
Prompt
Answer [(I, 4), (2,
The task is determine the minimum spanning tree of weighted graph.
imum span- ning tree
3), (3.4).
A minimum spanning tree is subset of the edges that connects all vertices in the graph with the minimum possible total edge weights. If not specified, all edges have equal edge weights. The input graph guaranteed be undirected and connected. Here is an undirected graph containing nodes from 1 to 5. The edges are: (1, 4, 5), (2, 4, 11), (2, 3, 10), (3, 4, 2), (3, 2). (u . w) denotes the edge from node *u* to node *y* has a weight of *w*
(3,
Question: What is the minimum spanning tree of the weighted graph?
You need to format your answer as a list of edges in ascending dictionary order, e.g., [(ul, v1), (u2, v2), ..., (un, vn)].
weighted shortest path
The task is to determine the shortest path between two nodes of weighted graph.
[1. 4, 6, 5]
The input nodes are guaranteed to be connected.
Here is directed graph containing nodes from to 8. The
edges are: (1, 2, 5), (1, 4, 3), (1, 7, 9), (2, 3, 10), (2, 4, 10), (3, 1, 11), (3, 4, 2). (3,
1, (4, (4) 8, 2), (5, 1, 7), 2, 11), (5, (5,
11), 3)4). (6, I), (.)
(6. 6),
8, 3). (8, 1, 11). (8, 7), (8, 4), 5). .v, w) denotes the edge from node *u* to node *y has weight of *w*
Question: What the shortest path between node and node 5? You need to format your answer as a list of nodes, e.g., [node-1, node-2, .... node-n].
wiener index
The task is to determine the Wiener index of a connected graph. The Wiener index of graph is the sum of the shortest-path distances between each pair of reachable nodes. For pairs of nodes in undirected graphs, only one orientation of the pair is counted.
15.0
In the input graph, all node pairs are guaranteed to be reachable. Here an undirected graph containing nodes from to The edges are: (1, 2), (1, 4), (2, 3), (4, 5), ().
Question: What the Wiener index the graph?
You need to format your answer as a float number.
44


Reviews:
[{"review_id": "XVPI0YTvUS", "reviewer": "Reviewer_WDtd", "summary": "This work first compiles a large-scale graph-theoretic dataset Erdős, which includes 50 graph-theoretic reasoning tasks from NetworkX, totaling 100k/2k training/evaluation question-answer pairs. Answers are automatically solved by NetworkX solvers. Graph data is downsampled from real-world datasets to 5-35 nodes, and graph structures are represented using a unified edge list format. The work then proposes applying a reinforcement learning (RL) framework to graph reasoning tasks for large language models (LLMs), designing rule-based rewards for different graph reasoning tasks and using Group Relative Policy Optimization (GRPO) for RL training. Finally, RL training on Erdős significantly improves the performance of baseline models on the Erdős benchmark.", "questions": "1)\tMy main concern is whether it is appropriate to use LLM to solve graph-theoretic problems without semantic information. Intuitively, the advantage of LLM lies in its ability to understand the textual attributes of nodes, so it is naturally suitable for scenarios such as text-attributed graphs. However, for pure graph structure problems addressed in the paper, isn't it more efficient to use pure GNN reasoning? On the other hand, tasks in Erdős all have clear optimization objectives, so wouldn't it be more efficient to solve them directly with algorithms? If the authors can provide sufficient reasons for using LLM, I am willing to raise my score.\n2)\tCorresponding to Question 1, it is hoped that the authors can supplement the experiments with comparisons of some other methods for solving graph-theoretic problems.\n3)\tPossibly due to limited space and rich content, Erdős is a newly proposed graph reasoning dataset by the authors, but it lacks analysis, such as whether it should be compared with existing other graph reasoning datasets.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1)\tHeavy workload. This work includes three main contributions: organizing the dataset, migrating the rule-based reward GRPO to the field of graph reasoning, and training the graph reasoning model.\n2)\tNovel theme. Improving the reasoning ability of LLMs on graphs is a relatively less explored field.\n\nWeakness:\n\n1)\tThe work mainly focuses on migrating GRPO to the graph reasoning field of large models, and the innovation of the work itself is relatively limited.\n2)\tThere is a lack of comparison with other methods, such as directly using graph neural networks to solve graph reasoning problems, such as https://arxiv.org/abs/2209.11142\n3)\tThe evaluation of the trained model is limited to Erdős, lacking assessment on other graph reasoning datasets.", "was_revised": true, "final_justification": "Thanks for author's detailed responses, which addressed most of my concerns. I keep my positive score.", "rebuttal": "We thank Reviewer WDtd for recognizing our work's substantial contributions and for highlighting the novelty of our research theme in a less-explored field. We shall address your concerns point by point in the discussion below.\n\n----\n\n**Q1.** My main concern is whether it is appropriate to use LLM to solve graph-theoretic problems without semantic information.\n> Intuitively, the advantage of LLM lies in its ability to understand the textual attributes of nodes, so it is naturally suitable for scenarios such as text-attributed graphs. However, for pure graph structure problems addressed in the paper, isn't it more efficient to use pure GNN reasoning [1]? On the other hand, tasks in Erdős all have clear optimization objectives, so wouldn't it be more efficient to solve them directly with algorithms? If the authors can provide sufficient reasons for using LLM, I am willing to raise my score.\n\n**A1.** Thanks for sharing your insightful thoughts! Indeed, for very standard, structural graph problems like those in Erdős, domain-specific solutions like GNNs are very compelling and efficient. In fact, the ultimate goal of this work is NOT to use LLMs to directly solve these problems, but by training on these graph-theoretic tasks, we want to improve **LLMs' general graph reasoning ability** for more real-world scenarios that involve graphs. In this way, we can leverage the power of LLMs to build ***general-purpose foundation models* capable of dealing with graphs.** \n\n**Why this is important** (and requires more than specialized GNNs) is that many real-world graph-related applications require sophisticated skills beyond domain-specific GNNs. For example, with a citation network, one may want to find out the top 10 influential people, and summarize their institutions in an Excel spreadsheet. This task is graph-related since the model needs to understand the graph well, but meanwhile, it's very hard for current GNNs that are only tasked to solve the graph part (and we need to train a model specifically for that particular task). With a graph-aware LLM, we can solve this with a simple instruction and release the potential of LLMs to expand their capability to more graph-related problems. \n\nIn the paper, we benchmark this general graph understanding ability on common node/link prediction benchmarks to make it more standardized. We believe that this generic reasoning ability of G1 could unlock LLMs' potential for solving more graph-related tasks beyond standard ones. And training with synthetic graph-theoretic tasks is an effective recipe, as demonstrated by G1, to reliably enhance this capability. This is the vision that we share about this work and hope this clarify your question. Please let me know if there is more to clarify.\n\n**An Illustrative Example**\n\nBelow, we use a concrete example in _GraphArena_ benchmark to illustrate the differences between graph-enhanced LLMs and GNNs. For this connected-components problem, a GNN-solver demands manual reformatting and coding of each variable, with delicate design for ambiguous descriptions like \"representative node\". Moreover, if the question shifts slightly —from \"output one representative node from each component\" to \"output the component containing Angel Chavez\"—the entire process must restart from scratch. By contrast, graph-enhanced LLMs (G1) unify these steps into a single question-answering framework, handling diverse problems without task-specific engineering while achieving strong performance (see Table 4). This flexibility, paired with LLMs' emergent reasoning, makes our direction promising for broader applications.\n\n*An illustrative example in GraphArena benchmark:*\n> You are required to identify all connected components in the given social network and output one representative node from each component.\n> \n> Problem to Solve: - Names in the network: Veronica Garcia, Katherine Brennan, Angel Chavez, Steven Martin, Brett Johnson, Megan Banks, Julia Dominguez, Rachel Mitchell - Fiendship connections: Veronica Garcia to Brett Johnson, Veronica Garcia to Megan Banks, Katherine Brennan to Brett Johnson, Katherine Brennan to Megan Banks, Angel Chavez to Megan Banks, Angel Chavez to Rachel Mitchell, Steven Martin to Megan Banks, Brett Johnson to Megan Banks, Megan Banks to Julia Dominguez, Megan Banks to Rachel Mitchell.\n\n[1]. Ibarz, Borja, et al. \"A generalist neural algorithmic learner.\" LoG, 2022.\n\n[2]. Veličković, Petar, et al. \"The clrs algorithmic reasoning benchmark.\" ICML, 2022.\n\n---------------\n\n **Q2.**  There is a lack of comparison with methods such as directly using GNNs to solve graph reasoning problems [1]. It is hoped that the authors can supplement the experiments with comparisons of some other methods for solving graph-theoretic problems. \n\n**A2.** Indeed, it would be more complete to include GNN results as well. Following your advice, we evaluate our models on the CLRS benchmark [1]. The benchmark only provides feature embeddings for the input, output, and hidden variables of each algorithm, which are specific for GNNs but not compatible with LLMs. Therefore, we sample a subset of the benchmark and translate feature embeddings into natural language descriptions. As seen in **Table R1**,  our G1-7B significantly outperforms GNN baselines on DFS (95.08% vs. 47.79%) and remains competitive on the shortest path task (98.19% vs. 85.71%). These results highlight G1-7B’s capability **as a general model** for solving graph-theoretic problems.\n\n*Table R1. Micro-F1 scores of G1-7B and GNN baselines on the CLRS benchmark (32 samples per task). GNN results are from [1].*\n| ~ | DFS |  DAG Shortest Paths |\n|---|-----|-----------|\n| Triplet-GMPNN [1] | _47.79_ | **98.19** |\n| Memnet [2] | 13.36 | 66.15 |\n| MPNN [3]   |  6.54 | 96.24 |\n| PGN [4]    |  8.71 | 96.94 |\n| Qwen2.5-7B-Instruct | 0.00 |  51.16  |\n| **G1-7B (Ours)** | **95.08** | _85.71_ |\n\n[1]. Ibarz, Borja, et al. \"A generalist neural algorithmic learner.\" LoG, 2022.\n\n[2]. Sukhbaatar, Sainbayar, Jason Weston, and Rob Fergus. \"End-to-end memory networks.\" NeurIPS, 2015.\n\n[3]. Gilmer, Justin, et al. \"Neural message passing for quantum chemistry.\" ICML, 2017.\n\n[4]. Veličković, Petar, et al. \"Pointer graph networks.\" NeurIPS, 2020.\n\n-----------\n\n**Q3.** The work mainly focuses on migrating GRPO to the graph reasoning field of large models, and the innovation of the work itself is relatively limited.\n\n**A3.** We understand the reviewer’s concern that we did not design a specific training objective (_e.g._, a GRPO variant) for the graph domain. However, this was intentional—we aimed to minimize graph-specific tweaks so that the G1 training recipe could easily align with the generic RL recipe for LLM training. Our results demonstrate a valuable insight:  **one does not need _extensive_ graph-specific tweaks to attain significant improvements of LLMs' graph reasoning ability**, which might be a surprise to years of graph research that emphasizes the need for domain-specific engineering on architectures or training objectives.\n\nMoreover, integrating graph reasoning into the current RL framework for LLMs is  **not a trivial task**. To ensure compatibility with our tasks, we carefully designed graph-specific rewards:\n- For tasks with unordered-set answers (_Section 4.1_), we replace strict value matching with **flexible set matching**, granting intermediate rewards for partially correct solutions. \n- For non-unique solutions, we implement **task-specific verification algorithms** to rigorously assess correctness. \n-  We also apply a  _soft_  data mixture strategy dynamically **reweighting rewards by task difficulty**, yielding better average performance than G1-3B ( _Appendix D_). \n \nThese new technical designs systematically address graph reasoning’s unique challenges while remaining aligned with the generic RL framework. Thus, we believe that this approach might be a more generic and scalable way to build graph-aware foundation models.\n\n---\n\n**Q4.** The evaluation of the trained model is limited to Erdős, lacking assessment on other graph reasoning datasets.\n\n**A4.** In **Section 5.2.1**, we have further evaluated G1 on two additional benchmarks - **GraphWiz** and **GraphArena** that have different graph structures, unseen reasoning tasks, and unfamiliar graph encoding formats. **Tables 3–4** show that G1 achieves strong zero-shot performance compared to other graph reasoning benchmarks, confirming its robustness to unseen graph types, tasks, and representations. This underscores our core claim: RL-incentivized reasoning generalizes beyond synthetic training environments.\n\n---\n\n**Q5.** Possibly due to limited space and rich content, Erdős is a newly proposed graph reasoning dataset by the authors, but it lacks analysis, such as whether it should be compared with existing other graph reasoning datasets.\n\n**A5.**  Due to space constraints, we've included a comprehensive comparison of Erdős with existing graph reasoning benchmarks in **Appendix E.1**, covering: (1) task design and counts, (2) instance counts, (3) graph types, and (4) node sizes. Please let us know if you have some other aspects that might need further elaboration.\n\n-----\nThanks for your comments and hope our answers could address your concerns. Please let us know if there is more to clarify. We are happy to address them during the discussion stage."}, {"review_id": "Gcg4cIHwX9", "reviewer": "Reviewer_R7SY", "summary": "This paper introduces a novel dataset covering more than 50 graph-theoretic tasks with varying levels of difficulty. Leveraging this dataset, they present G1, the first large language model trained with reinforcement learning for graph computational problems. G1 demonstrates superior performance compared to existing graph-focused language models on graph-related tasks, and exhibits zero-shot generalization abilities to non-graph domains such as mathematics.", "questions": "1. In the reward design, the authors mainly discuss outcome-based rewards. Have the authors considered designing format rewards or intermediate-step rewards, or assigning different weights to various types of rewards? Would such modifications lead to improved performance?\n2. Could the authors provide a plot showing the relationship between RL training steps and response length? This would offer insights into the learning dynamics and solution complexity.\n3. In the generalization experiments (e.g., mathematics), does G1 exhibit longer chain-of-thought (CoT) responses or changes in reasoning patterns, such as increased stepwise thinking? Some analysis or examples would be helpful to understand the model's behavior in out-of-domain tasks.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. This paper is the first to employ reinforcement learning (RL) to train large language models (LLMs) for solving graph computational problems, and demonstrates performance that surpasses previous graph-focused LLMs.\n2. The authors propose a dataset that covers a wide range of graph-theoretic tasks with clearly defined difficulty levels, offering a valuable resource for both training and evaluation.\n3. The presented G1 model exhibits impressive zero-shot generalization capabilities, not only across unseen graph tasks but also in non-graph domains such as mathematics.\n\n**Weaknesses:**\n\n1. The experiments are limited to graphs with a maximum of 35 nodes, which is relatively small. It would be more convincing to see results on graphs with at least 60 nodes to better assess scalability.\n2. The paper lacks any analysis or statistics regarding the number of output tokens generated by the model, which could be important for understanding efficiency and solution complexity.\n3. The technical novelty appears somewhat limited. The reward design focuses solely on outcome-based rewards, which is relatively naïve; more sophisticated reward structures could be explored.", "was_revised": true, "final_justification": "The further response has addressed my concerns in some extent. I am neutral to this work.", "rebuttal": "We thank Reviewer R7SY for recognizing our work as a pioneering effort that surpasses previous models, for acknowledging the value of our comprehensive dataset, and for highlighting our model's impressive zero-shot generalization capabilities. Below is our response to your comments.\n\n-------\n\n**Q1.** The experiments are limited to graphs with a maximum of 35 nodes, which is relatively small. It would be more convincing to see results on graphs with at least 60 nodes to better assess scalability.\n\n**A1.** That is a very good point! Follow your suggestion, we construct a new test set of 5,000 graphs with 36-100 nodes, with other settings kept the same, which ensures there is no overlap between training and test data. **Table R1** below shows that both G1-3B and G1-7B achieve strong zero-shot generalization to these larger graphs **without additional training**, significantly outperforming the baselines across difficulty levels. These results demonstrate our method's effective scalability beyond the original training distribution.\n\n*Table R1. Zero-shot generalization (accuracy in percentage) of G1 to larger graphs with **36-100 nodes**.*\n|        ~        |   Easy    |   Medium  |    Hard   | Challenging |  Average  |\n|----------------|-----------|-----------|-----------|-------------|-----------|\n| Qwen2.5-3B-Instruct |  27.98   |   28.53   |    5.26    |    0.29   |   16.74   |\n|        G1-3B        | **79.39** | **65.66** | **18.46** | **3.74**  | **44.29** |\n| Qwen2.5-7B-Instruct |   37.86   |   41.56   |    9.17   |   1.17    |   23.94   |\n|        G1-7B        | **76.65** | **70.67** | **23.16** |  **5.22** | **46.46** |\n\n---\n\n**Q2.** The paper lacks any analysis or statistics regarding the number of output tokens generated by the model, which could be important for understanding efficiency and solution complexity. Could the authors provide a plot showing the relationship between RL training steps and response length? This would offer insights into the learning dynamics and solution complexity.\n\n**A2.** Thanks for your suggestion. While we cannot add a plot per the NeurIPS rebuttal constraint, we provide the average response lengths across different steps in **Table R2**. The data shows relatively stable response lengths throughout training (813-962 tokens), suggesting consistent solution complexity and stable generation behavior. We'll include a complete plot in the paper. \n\n*Table R2. Average response length across the RL training steps on Erdős.*\n|  Step |   1   |  50  |  100   |   150   |  200   |   250   |   300   |\n|--------|-------|--------|--------|--------|--------|-------|--------|\n| Average response Length  | 813 | 869 | 883 | 854 | 889 | 962 | 933 | 956 |\n\n---\n\n**Q3.** The technical novelty appears somewhat limited. The reward design focuses solely on outcome-based rewards, which is relatively naïve; more sophisticated reward structures could be explored. In the reward design, the authors mainly discuss outcome-based rewards. Have the authors considered designing format rewards or intermediate-step rewards, or assigning different weights to various types of rewards? Would such modifications lead to improved performance?\n\n**A3.** We understand the reviewer’s concern regarding the absence of sophisticated rewards (_e.g._, intermediate-step rewards). However, to integrate graph reasoning into the current RL framework, we carefully designed **graph-specific rewards** that go beyond the original GRPO’s scope—which was tailored for math tasks with unique solutions.\n\nOur paper introduces graph task-specific rewards with three key innovations: \n- For tasks with unordered-set answers (_Section 4.1_), we replace strict value matching with **flexible set matching**, granting intermediate rewards for partially correct solutions. \n- For non-unique solutions, we implement **task-specific verification algorithms** to rigorously assess correctness.\n- As detailed in  _Appendix D_, we apply a  _soft_  data mixture strategy dynamically **reweights rewards by task difficulty**, yielding better average performance than G1-3B.\n\nAdditionally, we adopt PRIME [1]—an intermediate-reward-based RL method that calculates token-level dense rewards to estimate advantages. As shown in **Table R3**, G1-PRIME-3B exhibits consistent improvement over the Qwen2.5 baseline, however, it still lags slightly behind the G1-3B (55.94% vs. 59.76% on average), indicating the effectiveness of our paper’s reward design.\n\n*Table R3. Test performance (%)  on Erdős benchmark.*\n|     ~    |   Easy   |   Medium  |   Hard   | Challenging |  Average  |\n|----------|----------|-----------|----------|-------------|-----------|\n| Qwen2.5-3B-Instruct |  45.71  |  30.18  |   9.44  |  1.29  |  22.72  |\n|      G1-PRIME-3B    |  88.79  |  78.73  |  38.12  |  8.57  |  55.94  |\n|        G1-3B        |**94.86**|**84.64**|**41.25**|**7.57**|**59.76**|\n\n[1]. Cui, Ganqu, et al. \"Process reinforcement through implicit rewards.\" arXiv preprint arXiv:2502.01456 (2025).\n\n---\n\n**Q4.** In the generalization experiments (e.g., mathematics), does G1 exhibit longer chain-of-thought (CoT) responses or changes in reasoning patterns, such as increased stepwise thinking? Some analysis or examples would be helpful to understand the model's behavior in out-of-domain tasks.\n\n**A4.** Thanks for your insightful question! Following your suggesstion, we calculate the average response length on the MATH dataset. As shown in **Table R4**, G1 does not exhibit significant length variation compared to baselines, suggesting that its generalization to non-graph tasks (e.g., GSM8K and MATH) stems not from longer chains of thought (CoT). We reckon the improvement, e.g., in the G1-7B case, is caused by the inherent similarity between math problems and graph problems --in broad terms, graph-theoretic problems are math problems as well. Therefore, learning to solve graph problems can teach the models effective techniques to solve math problems as well.\n\n\n*Table R4. Average response length on MATH dataset.*\n| Model | Average response length | \n|--------|------------------------|\n| Qwen-3B-Instruct | 612 |\n|  G1-3B | 663 |\n| Qwen-7B-Instruct | 646 | \n| G1-7B  | 586 | \n\n-----\n\nWe appreciate your time in reviewing our work and hope these responses resolve your queries. Please let us know if there are any other points you wish to discuss."}, {"review_id": "fbLJl4Y9Q2", "reviewer": "Reviewer_muF5", "summary": "This paper presents G1, using reinforcement learning to teach LLMs to solve graph theoretic problems. First, a new dataset collection is constructed called Erdos (I love this name by the way), which provides an amount of graph-related tasks serving various reasoning tasks. The RL procedure follows commonly used GRPO. From the results G1 is very strong and could even beat larger models by reinforcing a small model.", "questions": "Q1. Do you think there is any unique graph-specific things that can be leverages to improve the design of GRPO training on graphs?\n\nQ2. I love the name of the new dataset, but let's be careful. Graph theory and graph-theoretic reasoning is different. Some clarifications could be made here (not affecting the quality of the paper).", "limitations": "N/A. No remarkable negative societal impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength: Very recent R1 technique on graphs with exciting results. The presentation is clear. It is shown that G1 can even be generalized beyond graphs.\n\nW1. Line 32 \"Different from prior work, we believe LLMs pretrained on Internet-scale data already possess graph reasoning ability.\" Dangerous! This is a very strong claim without any supporting evidence in these two lines.\n\nW2. The ending of introduction is inspiring yet not very clear. I would suggest more discussions on how to leverage G1 to build graph foundation models. This paper presents a grand position on graph foundation model (that there could be a paradigm shift with RL) but lacks supporting evidence and discussions.\n\nW3. A new dataset is presented, but only reported some details and the scales. The presented dataset, however, is not evaluated. I just have no idea of what the constructed dataset looks like, and if different prompt choice would affect evaluating the LLMs. In other words, how good and robust is the constructed dataset?\n\nW4. The proposed reinforcement learning technique is a data-centric method from my perspective. The most important thing is an amount of available graph-theoretic data with correct labels/ground-truth. The training is a mimic of GRPO, which means G1 could suffer from draw backs of GRPO, such as sampling inefficiency and optimizing instability. I don't see (or maybe I missed) study on these in 5.3 training analysis or appendix.\n\nW5. I just cannot intuitively understand how conducting G1 on graph theoretic reasoning tasks could improve beyond graphs, such as GSM8K and MATH. Given the distribution shift in the training data and test data, I would assume the performance to degrade, which is not the case. More discusion/clarification here is needed (would be better with some discussion also on non-graph-theoretic task generalizations).\n\nW6. Why don't you compare with GPT-4o or other SOTA LLMs? It's ok if not outperforming those models as they might have a very large number of parameters, but it would provide more evidence of how good G1-7B is achieving. \n\nW7. Nothing on efficiency, such as training time, is reported.", "was_revised": true, "final_justification": "The authors are able to address all my concerns, and I feel confident to recommend an acceptance for this manuscript. It may not possess much real-world impact at this time (and that's why I'm not confident to recommend a strong accept), but this manuscript should possess great academic potential to inspire future works as long as everything is made open-sourced and transparent.", "rebuttal": "We are grateful to the reviewer for acknowledging our recent technique and its exciting results, for finding the presentation clear, and for highlighting our model's impressive generalization beyond the graph domain. Below, we present a detailed response to each of your concerns.\n\n-----\n\n**Q1.** Line 32 \"Different from prior work, we believe LLMs pretrained on Internet-scale data already possess graph reasoning ability.\" Dangerous! This is a very strong claim without any supporting evidence in these two lines.\n\n**A1.** Thanks for bringing it to our attention! Indeed, this is a strong claim that is hard to exactly verify. We will tune it down following your advice, e.g., \"we **reckon** LLMs pretrained on Internet-scale data **might** already possess graph reasoning ability.\"  Meanwhile, we do observe some supportive evidence for this speculation. As shown in **Table R1** below, the graph-learning reward can improve by 51% in just 50 steps (0.350→0.529), which is rarely possible if the pretrained model has not learned relevant knowledge at all. We will add this discussion in the revision.\n\n*Table R1. The tendency of rewards across the RL training steps.*\n\n|  Step  |   1   |  50   |  100  |  150  |  200  |  250  |   300  |\n|--------|-------|-------|-------|-------|-------|-------|--------|\n| Reward | 0.350 | 0.529 | 0.598 | 0.643 | 0.660 | 0.686 |  0.700 |\n\n---\n\n**Q2.** The ending of introduction is inspiring yet not very clear. I would suggest more discussions on how to leverage G1 to build graph foundation models. This paper presents a grand position on graph foundation model (that there could be a paradigm shift with RL) but lacks supporting evidence and discussions.\n\n**A2.** Thanks for bringing it up. Through the final paragraph, we want to show that G1 itself demonstrates a new path for building graph foundation models via RL training of LLMs. More concretely, it consists of the following three key model choices:\n-   **Pretraining:**  Rather than training specific graph models (e.g., GNNs) from scratch with graph data, we can leverage LLMs pretrained with Internet-scale data and capable of general-purpose problem solving.\n-   **RL training:**  Instead of direct supervised finetuning on graph data, we use RL to incentivize reasoning processes via LLMs themselves for solving graph tasks.\n-   **Synthetic Graph Tasks:** Due to the limited amount of graph data, we can adopt diverse synthetic graph tasks (such as those in Erdős) for RL training of LLMs, which not only overcomes data scarcity but also gives rigorous learning rewards.\n\nThe success of R1 demonstrates the effectiveness and scalability of this approach and thus we believe that it can be adopted for further building powerful graph foundation models. We will add this discussion to the paper.\n\n---\n\n**Q3.** A new dataset is presented, but only reported some details and the scales. The presented dataset, however, is not evaluated. I just have no idea of what the constructed dataset looks like, and if a different prompt choice would affect evaluating the LLMs. In other words, how good and robust is the constructed dataset?\n\n**A3.** We want to note that due to the limit of space, we have included some details in the appendix.  Specifically, for  **dataset composition**, _Appendix E.2_ provides a complete task list in Erdős, with representative prompts and solutions for each task type. We hope this table can help readers to have an overall grasp of the dataset and will publicly release the datasets later. For **prompt robustness**, we rigorously test prompt sensitivity by having GPT-4o generate three semantically equivalent prompt variants. _Table R2_ shows minimal performance variance (<1.5% standard deviation) across all models and difficulty levels, confirming our benchmark’s stability to phrasing changes. We will also include these results in the paper for completeness following your advice.\n\n*Table R2. Test accuracy (%) on different prompts, mean and standard deviation reported.*\n|           ~     |   Easy    |   Medium  |    Hard   | Challenging | \n|----------------|-----------|-----------|-----------|-------------|\n| Qwen2.5-3B-Instruct |44.26 +- 0.63|30.52 +- 1.08|10.71 +- 0.41|1.24 +- 0.07|\n|        G1-3B        |94.86 +- 0.69|83.03 +- 0.42|41.08 +- 1.35|9.67 +- 1.05|\n| Qwen2.5-7B-Instruct |56.48 +- 1.17|56.48 +- 1.17|18.81 +- 0.79|3.10 +- 0.18|\n|        G1-7B        |95.48 +- 0.18|88.39 +- 0.67|51.27 +- 0.13|25.14 +- 1.04|\n\n----\n\n**Q4.** The proposed reinforcement learning technique is a data-centric method from my perspective. The most important thing is an amount of available graph-theoretic data with correct labels/ground-truth. The training is a mimic of GRPO, which means G1 could suffer from drawbacks of GRPO, such as sampling inefficiency and optimizing instability. I don't see (or maybe I missed) study on these in 5.3 training analysis or appendix.\n\n**A4.** For **sampling inefficiency,** G1 encounters the issue on tasks with **challenging** difficulty (*e.g.,* NP-hard problem), where initially sampling a correct reasoning path is hard. Despite million-scale rollouts, G1-7B achieves less than 25% accuracy on these tasks on average. We hypothesize that adaptive difficulty scheduling during training could help mitigate this issue. For **optimizing instability**, shown in _Table R3_, G1 exhibits stable RL training. There is a consistent 51% reward improvement within 50 epochs and a monotonic progression to 0.700.  Full reward trajectory plots will be provided in the paper. We will include these discussions in our paper, and we believe further development of better RL training algorithms on resolving these issues could also benefit G1 training as well.\n\n*Table R3. The tendency of rewards across the RL training steps.*\n\n|  Step  |   1   |  50   |  100  |  150  |  200  |  250  |   300  |\n|--------|-------|-------|-------|-------|-------|-------|--------|\n| Reward | 0.350 | 0.529 | 0.598 | 0.643 | 0.660 | 0.686 |  0.700 |\n\n----\n\n**Q5.** I just cannot intuitively understand how conducting G1 on graph theoretic reasoning tasks could improve beyond graphs, such as GSM8K and MATH. Given the distribution shift in the training data and test data, I would assume the performance to degrade, which is not the case. More discussion/clarification here is needed (would be better with some discussion also on non-graph-theoretic task generalizations).\n\n**A5.** This is a very interesting question! In fact, the transferability between different reasoning domains has also been observed in other works and been actively under research. For example, [1] demonstrates that reinforcement learning exhibits strong generalization even under distribution shifts, as it encourages models to learn robust, task-agnostic reasoning strategies rather than overfitting to surface-level patterns. Additionally, RL training has been shown to foster mutual reinforcement across seemingly distinct tasks, *e.g.*, optimizing on puzzles can help reasoning on math [2]. Similarly, due to the similarity between math and graph problems, they would also require similar reasoning skills (such as guessing, backtracking, verification). Therefore, solving graph problems could have positive transferability to math domains.\n\n[1]. Chu, Tianzhe, et al. \"Sft memorizes, rl generalizes: A comparative study of foundation model post-training.\" arXiv preprint arXiv:2501.17161 (2025).\n\n[2]. Li, Yu, et al. \"Can One Domain Help Others? A Data-Centric Study on Multi-Domain Reasoning via Reinforcement Learning\" arXiv preprint arXiv:2507.17512 (2025).\n\n---\n\n**Q6.** Why don't you compare with GPT-4o or other SOTA LLMs? It's ok if not outperforming those models as they might have a very large number of parameters, but it would provide more evidence of how good G1-7B is achieving.\n\n**A6.** We did not include GPT-4o as comparison for its high cost on API calling. As an alternative,  we include **OpenAI o3-mini**, that, according to [official OpenAI reports](https://openai.com/zh-Hans-CN/index/openai-o3-mini/), significantly outperforms GPT-4o on **reasoning benchmarks**. Our comparison with OpenAI o3-mini on graph reasoning tasks (_Table 2_) demonstrates that G1-7B achieves competitive performance despite its smaller scale.\n\n---\n\n**Q7.** Nothing on efficiency, such as training time, is reported.\n\n**A7.** Thank you for raising this point. G1-7B was trained in approximately **40 hours on 8×A100 GPUs**, while G1-3B required around **35 hours on 4×A100 GPUs**. We will include these details in the paper.\n\n---\n\n**Q8.** Do you think there is any unique graph-specific things that can be leveraged to improve the design of GRPO training on graphs?\n\n**A8.** While graph structural priors could be explicitly incorporated into the LLM architecture, this might compromise its generality. Instead, we implicitly encode these priors through **reward design**. Specifically, graph-theoretic tasks offer unique advantages for GRPO training, particularly in  **controllable difficulty scaling**. Unlike traditional math reasoning benchmarks—where difficulty is often subjective and requires complex data curation—graph problems allow precise difficulty adjustment in two key ways: (1) theoretical complexity: we can select problems across complexity classes (e.g., linear-time vs. NP-hard) to create a structured curriculum, and (2) graph size: even within the same task, difficulty can be tuned by varying the number of nodes/edges. This flexibility enables more dynamic training strategies, such as  **reward reweighting**, which we have studied in _Appendix D_, and  **adaptive difficulty scheduling**, which can be explored in future study."}, {"review_id": "hPMnWVhwLp", "reviewer": "Reviewer_2Hnx", "summary": "The paper provides a new LLM approach training with reinforcement learning to reason on graph tasks. The authors conduct extensive experiments on multiple datasets including synthetic and real-world datasets, comparing to other state-of-the-art comparable LLMs. The method achieves better performance on various graph tasks compared to baselines even though it uses less number of parameters.", "questions": "1. How can this model scale with it is being trained with very large number of parameters? Can you provide the running times of the current model? Can you provide some insights on what would happen if the method has much more parameters (e.g., 100B)?\n2. What are the future directions of this particular research? Can you provide a section that discusses limitations and future directions?\n3. Can you provide the robustness/correctness of the method by running the same questions multiple times on some tasks?", "limitations": "Limitations and societal impacts are not clear. I suggest authors to make them clear. They mentioned that the limitations are in experiment section, which I don't see them. Societal impacts are supposed to be in appendix, again I don't see them. Can authors make them clearer, maybe in a separate section? They can be included with future directions that I already suggested to add.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is very well written and structured. It is easy to follow and read.\n2. The paper contributes to the research community by promising to share the code and all tasks that are used to train.\n3. The paper conducts many experiments on multiple different graph tasks, and each tasks and experiments are explained really well.\n4. The paper provides multiple versions of their methods which are serving as ablation study. They compare each method in training analysis and show the differences between the methods.\n\nWeakness:\n1. The method is only compared with methods with small parameters (there are some unknown methods and they may achieve better performance in some cases.) \n2. The method uses only 7B parameters. How would the method scale if we want to build the larger model?\n3. The paper does not really discuss the future directions, which is needed for the research paper.\n4. All the experiments are run only once. The authors mentioned that randomness is negligible. LLMs are known to give different answers based on the questions. So ML practice suggests that multiple run is needed.", "was_revised": true, "final_justification": "The paper quality is very strong and the authors made a great rebuttal, addressing all of my concerns and comments, regarding the following points: (1) Scalability of the method, (2) Experimental setting, (3) Future directions, (4) Limitations and societal aspect. That's why I'm increasing my score to strong accept.", "rebuttal": "We are grateful for Reviewer 2Hnx's positive feedback on our paper's clear writing and structure, the thoroughness of our experiments and ablation studies, and our contribution to the research community. We will address the remaining concerns in the discussion below.\n\n-----\n\n**Q1.** The method is only compared with methods with small parameters (there are some unknown methods and they may achieve better performance in some cases.)\n\n**A1.** In **Table 2**, we provide comparisons with several large-scale models, including Qwen2.5-72B-Instruct and Llama3.1-70B-Instruct (72B parameters). Notably, our G1-3B model achieves competitive performance against these 72B-parameter models while using only about 1/20 of their parameters. This demonstrates the effectiveness of our approach in achieving strong performance at a much smaller scale.\n\n---\n\n**Q2.** The method uses only 7B parameters. How would the method scale if we want to build a larger model? How can this model scale with it is being trained with very large number of parameters? Can you provide the running times of the current model? Can you provide some insights on what would happen if the method has much more parameters (e.g., 100B)?\n\n**A2.** For **current models**, G1-7B was trained in approximately 40 hours on 8×A100 GPUs, while G1-3B required around 35 hours on 4×A100 GPUs. We will include these details in the paper. To demonstrate scalability, we further trained **G1-Zero-32B** from Qwen2.5-32B-Instruct using the same method.  G1-Zero-32B achieves significant average improvement on Erdős (_Table R1_) while maintaining strong math performance (_Table R2_), The training is completed in 40h on 32×A100 GPUs. Scaling to **100B parameters** would likely require 1024×A100 GPUs, which is currently beyond our capacity, but prior work (like DeepSeek-R1 with 671B parameters) suggests GRPO can effectively scale. The consistent gains from 3B to 32B models indicate our approach maintains effectiveness with increasing scale.\n\n*Table R1. Test accuracy (%) of 32B models on Erdős.*\n\n|                      |    Easy   |   Medium  |   Hard    | Challenging |  Average  |\n|----------------------|-----------|-----------|-----------|-------------|-----------|\n| Qwen2.5-32B-Instruct |   70.57   |   68.73   |   33.38   |     9.00    |   47.10   |\n|      G1-Zero-32B     | **97.79** | **93.00** | **65.25** |  **35.43**  | **75.06** |\n\n\n*Table R2. Test accuracy (%) of 32B models on math tasks.*\n\n|                      |   GSM8K   |    MATH   |\n|----------------------|-----------|-----------|\n| Qwen2.5-32B-Instruct |   90.67   |   76.80   |\n|      G1-Zero-32B     | **90.75** | **80.80** |\n\n---\n\n**Q3.** All the experiments are run only once. The authors mentioned that randomness is negligible. LLMs are known to give different answers based on the questions. So ML practice suggests that multiple run is needed. Can you provide the robustness/correctness of the method by running the same questions multiple times on some tasks?\n\n**A3.**  To rigorously evaluate robustness, we conducted 32 repeated runs with different random seeds. The results in **Table R3** demonstrate consistently small standard deviations (<1% across all models and difficulty levels), confirming the stability of our method against potential randomness in LLM outputs. This empirical validation supports our claim about the method's reliability, and we will add the experiments in our paper.\n\n*Table R3.  Test accuracy (%) for 32 runs with different random seeds.*\n|                |   Easy    |   Medium  |    Hard   | Challenging | \n|----------------|-----------|-----------|-----------|-------------|\n| Qwen2.5-3B-Instruct |45.65 +- 0.51| 30.88 +- 0.36 | 10.36 +- 0.21 | 1.54 +- 0.29 |\n|        G1-3B        |94.96 +- 0.32| 83.22 +- 0.24 | 41.48 +- 0.40 | 7.96 +- 0.64 |\n| Qwen2.5-7B-Instruct |57.50 +- 0.13| 44.92 +- 0.03 | 19.90 +- 0.31 | 3.45 +- 0.22 | \n|        G1-7B        |95.66 +- 0.12| 88.89 +- 0.16 | 50.76 +- 0.53 | 24.46 +- 0.84|\n\n---\n\n**Q4.** The paper does not really discuss the future directions, which is needed for the research paper. What are the future directions of this particular research?\n\n**A4.** Thanks for highlighting this important aspect. Below we provide the future directions and will add them to the paper.\n\nIn future work, we aim to explore dynamic difficulty scheduling during RL training to address the sample inefficiency issue. On a broader scale, we also plan to extend our approach to the following scenarios:\n- Handling larger graphs with thousands of nodes, aligning with the long-context reasoning challenges;\n- Incorporating visual inputs (*e.g.* images depicting graphs)  to enhance real-world applicability;\n- Adapting G1 to more practical domains such as logistics, knowledge graph reasoning, and tabular problem-solving, where structured reasoning is critical.\n\n\n---\n\n**Q5.** Limitations and societal impacts are not clear. I suggest authors make them clear. They mentioned that the limitations are in experiment section, which I don't see them. Societal impacts are supposed to be in appendix, again I don't see them. Can authors make them clearer, maybe in a separate section? They can be included with future directions that I already suggested to add.\n\n**A5.**  We appreciate the reviewer’s suggestion to clarify limitations and societal impacts. Below we provide a dedicated discussion and will add it to the paper.\n\n**Limitations:**  While G1 demonstrates significant improvements in graph reasoning through RL training, it inherits GRPO's sample inefficiency and requires extensive rollouts for challenging tasks (_e.g._, NP-hard problems), which might be solved by dynamic difficulty scheduling during training.  Although G1 demonstrates strong generalization to real-world graph tasks, _e.g._, node classification and link prediction, its generalization to highly domain-specific applications (_e.g._, molecular property prediction) and other structured data (_e.g._, tabular, time-series) remains untested.\n\n**Social Impacts:** G1’s graph reasoning capabilities offer practical benefits for education (e.g., adaptive graph theory tutoring) and scientific research. While the technology could amplify existing biases in training data, these risks can be mitigated through careful dataset design and human oversight. When developed responsibly, G1 has the potential to support human experts in solving complex graph problems.\n\n-----\nThanks for your comments and hope our answers could address your concerns. Please let us know if there is more to clarify. We are happy to address them during the discussion stage."}]

Author rebuttal:

Meta-review: This work propose a novel method to integrate graph reasoning reward with GRPO-like RL based training schemes. While the authors use a rather heavy experiments workload to prove there point, the technical contribution and application is limited. To be specific, the practical concerns raised by some reviewer regarding the scalability of the proposed method is a major limitation. Since all of the reviewers agree on accepting this work, I will recommend to accep this work as a poster.
Decision: Accept (poster)