Search papers, labs, and topics across Lattice.
This paper introduces GRAIN, a single-agent reinforcement learning framework designed to enhance Large Language Models' (LLMs) robustness against real-world shifts in node identifiers and task formulations in graph reasoning. By employing a Structure Invariance Reward, GRAIN encourages LLMs to focus on learning accurate text-to-structure mappings rather than overfitting to surface patterns, leading to significant improvements in accuracy and latency compared to multi-agent systems. The framework not only achieves a 16.45% accuracy increase but also reduces the out-of-distribution gap for structural generalization, demonstrating its effectiveness in handling large-scale graphs beyond training distributions.
GRAIN boosts LLM accuracy by over 16% while cutting latency, revolutionizing how we handle real-world graph reasoning challenges.
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.
