# GRAIN: Bridging Name and Narrative Shifts in Real-World Graph Reasoning through Invariance-Rewarded Agentic RL

arXiv: https://arxiv.org/abs/2608.27142 · HTML: https://mlsanity.com/paper/2608.27142/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 27 Aug 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)
- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 14 of 14)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning](https://mlsanity.com/paper/2503.09516/) (2025)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration](https://mlsanity.com/paper/2410.18032/) (2024)
- [GCoder: Improving Large Language Model for Generalized Graph Problem Solving](https://mlsanity.com/paper/2410.19084/) (2024)
- [Adaptive Information Control for Search-Augmented LLM Reasoning](https://mlsanity.com/paper/2602.01672/) (2026)
- [LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration](https://mlsanity.com/paper/2411.05844/) (2024)
- [Are Large-Language Models Graph Algorithmic Reasoners?](https://mlsanity.com/paper/2410.22597/) (2024)
- [EGL-SCA: Structural Credit Assignment for Co-Evolving Instructions and Tools in Graph Reasoning Agents](https://mlsanity.com/paper/2605.10366/) (2026)

## Abstract (arXiv)

Despite their potential in standardized graph tasks, Large Language Models (LLMs) remain brittle to real-world shifts in node identifiers and task formulation. While deterministic graph tools are invariant to such shifts, extracting topological structures from noisy text is highly fragile for LLMs, which often overfit to surface patterns. Moreover, mitigating these parsing failures via multi-agent systems incurs prohibitive latency. To address this, we propose GRAIN, a single-agent framework optimized via reinforcement learning. GRAIN models reasoning as a semantic parsing and tool-execution pipeline, guided by a Structure Invariance Reward. By validating extracted intermediate graphs against ground-truth topologies, this reward forces the LLM to learn robust text-to-structure mappings rather than memorizing linguistic artifacts. We also introduce GRIT, a benchmark evaluating sensitivity to such linguistic shifts. GRAIN outperforms multi-agent baselines by 16.45% in accuracy with approximately 24% lower latency. Furthermore, it demonstrates superior structural generalization, halving the out-of-distribution (OOD) gap of SFT models (from 15.77% to 7.80%) and maintaining robustness on large-scale graphs beyond the training distribution.