Generalizable LLM Learning of Graph Synthetic Data with Reinforcement Learning

Yizhuo Zhang Heng Wang Shangbin Feng Zhaoxuan Tan Xinyun Liu Yulia Tsvetkov · 2025

Read Generalizable LLM Learning of Graph Synthetic Data with Reinforcement Learning by Yizhuo Zhang Heng Wang Shangbin Feng Zhaoxuan Tan Xinyun Liu Yulia Tsvetkov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00845.txt.

Introduction

Six researchers test whether alignment training on synthetic graph problems teaches language models reasoning that transfers to real tasks, in a 2025 paper. Fine-tuning on made-up graph data makes models good at graph puzzles, but the world needs the underlying skill on tasks where graphs hide inside other problems. Their recipe rewards both final answers and the reasoning process on synthetic problems. Standard alignment methods then tune the models with those rewards.

Across five datasets, the aligned models improved by about thirteen percent on average over baseline setups. Process rewards beat answer-only rewards on synthetic tasks, though not on real-world ones. Multi-hop questions and structured planning were among the transfer tests. The authors flag composition and explainable steps as open challenges. They argue alignment, not memorization, is what unlocks generalizable graph learning.

Catalog record

CREATORYizhuo Zhang Heng Wang Shangbin Feng Zhaoxuan Tan Xinyun Liu Yulia Tsvetkov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-00845

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Generalizable LLM Learning of Graph Synthetic Data with Reinforcement Learning Yizhuo Zhang Heng Wang Shangbin Feng Zhaoxuan Tan Xinyun Liu Yulia Tsvetkov Abstract Previous research has sought to enhance the graph reasoning capabilities of LLMs by supervised fine-tuning on synthetic graph data. While these led to specialized LLMs better at solving graph algorithm problems, we don’t need LLMs for shortest path: we need generalization from synthetic graph data to real-world tasks with implicit graph structures. In this work, we propose to unlock generalizable learning of graph synthetic data with reinforcement learning. We first design solution-based and process-based rewards for synthetic graph problems: instead of rigid memorizing response patterns in direct fine-tuning, we posit that RL would help LLMs grasp the essentials underlying graph reasoning and alleviate overfitting. We employ RL algorithms such as GRPO and DPO, aligning both off-the-shelf LLMs and LLMs fine-tuned on synthetic graph data. We then compare them against existing settings on both in-domain synthetic tasks and out-of-domain real-world tasks with implicit graph structures such as multi-hop QA, structured planning, and more. Extensive experiments demonstrate that our RL recipe leads to statistically significant improvement on 5 datasets, with an average gain of 12.9% over baseline settings. Further analysis reveals that process-based rewards consistently outperform solution-based rewards, mixing synthetic and real-world task data yields potential gains, while compositionality and explainable intermediate steps remains a critical challenge even after RL. 1 1 1 Experimental code and results are publicly available at https://anonymous.4open.science/r/Graph_RL-BF08/readme.md 1 Introduction Going beyond language processing tasks, large language models (LLMs) are increasingly adopted for tasks with implicit graphical structures, such as commonsense reasoning [ 63 , 62 ] , multi-hop QA [ 32 , 17 , 20 ] , and planning [ 80 , 56 ] . Existing research focuses on evaluating LLMs on the underlying graph problems such as connectivity and shortest path, revealing that LLMs do have preliminary graph reasoning capabilities [ 84 ] while suffering from limitations such as robustness and hallucination [ 84 , 100 , 25 ] . Recent works seek to further improve LLM graph reasoning, mostly through supervised fine-tuning (SFT) on graph synthetic data [ 30 , 57 ] : these techniques demonstrate substantial improvement in LLMs’ ability to tackle graph algorithm problems. However, we don’t need LLMs to solve synthetic graph problems such as shortest path and topological sort: we already have algorithms (e.g., Dijkstra and Ford-Fulkerson) that are 100% accurate and much more efficient than calling an LLM. The goal of leveraging synthetic graph data should thus be learning from the structured reasoning data and generalizing from synthetic graph problems to real-world tasks with implicit structures. Unfortunately, existing SFT recipes are not improving real-world performance [ 100 ] , even leading to a 12.5% drop for tasks such as Proscript [ 63 ] . To this end, we propose to unlock the power of synthetic graph data with reinforcement learning (RL). Instead of directly memorizing reasoning chains of synthetic problems through SFT, we posit that RL would help LLMs learn the underlying objectives of graph reasoning and mitigate excessive over-fitting to synthetic problems. We design two types of rewards for synthetic graph problems: solution-based , where only the final answer is considered; process-based , where varying weights are given to the soundness of intermediate steps and the final answer. We then align LLMs, both off-the-shelf and fine-tuned on synthetic graph problems, with RL algorithms (e.g., GRPO [ 67 ] and DPO [ 60 ] ) using these reward models. We then compare these RL models against existing settings (off-the-shelf models, SFT, etc.) on 1) in-domain synthetic tasks such as connectivity and shortest path; and more importantly, 2) out-of-domain real-world graph problems such as multi-hop QA [ 20 , 17 ] and structured commonsense reasoning [ 62 , 63 ] . Extensive experiments with two LLMs and 8 task settings demonstrate that our proposed RL recipes outperform baselines across tasks and models on both synthetic and real-world graph problems. For synthetic problems, RL models improve by 25% on average for the connectivity task. More importantly, for real-world graph problems, our recipe provides statistically significant improvements on 5 task settings, with an average improvement of 13%. Our experiments also offer insights into the RL recipe: the on-policy algorithm GRPO outperforms the off-policy DPO by 5% on average; process-based rewards offer finer-grained signals for models to learn from when using GRPO, outperforming solution-based by 24% on average on synthetic tasks, while there is no significant edge of process-based synthetic rewards on real-world tasks. Further analysis reveals that mixing a fraction of real-world task data yields potential gains, while the main bottlenecks for RL models are twofold: the compositionality gap from correct single-step results to a correct multi-step solution, and an explainable and hallucination-free intermediate single-step to multi-step reasoning path. Figure 1: The overall pipeline of our work. We first perform an optional SFT stage (left), followed by RL stage (middle) with two rule-based reward designs. Both SFT and RL training use purely synthetic graph tasks. At last, we evaluate models on both synthetic and real-world tasks (right). 2 Methdology Initial Dataset For synthetic graph datasets, we follow Wang et al. 2023 and Zhang et al. 2024b to choose connectivity and shortest path problems. We choose these two tasks since reasoning behind connectivity and shortest path can represent a range of real-world graph problems, including comparing if two ideas are similar or not (if those two ideas are connected) [ 62 ] , solving an implicit knowledge graph question (where the model will try to reason through the shortest path between two entities) [ 17 ] . On the other hand, it is easy and straightforward to verify the correctness of model responses on these two tasks with a Python program. Overall Pipeline Our approach follows a three-stage pipeline leveraging synthetic graph data for training and evaluation. We begin with an off-the-shelf model (base model in the following sections) and optionally perform supervised fine-tuning (SFT) on a set of synthetic graph problems. This SFT stage provides the model with exemplars of graph reasoning (including structured reasoning steps and final solutions) in a supervised manner, priming it with domain-specific patterns before reinforcement learning. After SFT (or directly from the base model if SFT is skipped), we further tune the model with reinforcement learning (RL) on synthetic graph tasks. Finally, we evaluate the resulting model on both held-out synthetic problems and real-world graph problems to assess reasoning generalization. This end-to-end pipeline – from base model, to optional synthetic SFT, to RL optimization – is designed to better understand the model’s capabilities of learning and generalizing reasoning on synthetic data to real-world problems. Reward Design Our training data only contains synthetic tasks of connectivity and shortest path, whose answers can be easily verified using Python programs, so we design rule-based rewards for each task. For a more straightforward extraction of certain parts of the model’s completion, we specify a special format for the response, which contains three parts: think , response and answer , which are enclosed by “ <think>...</think> ”, “ <response>...</response> ” and “ <answer>...</answer> ” respectively. For response and answer parts, we also specify a given format of solving synthetic problems.

Read the complete text