GRAIN Beats Multi-Agent Graph Reasoning by 16.45% With One Agent and 24% Less Latency

arXiv 2608.27142·medium signalXBlueskyLinkedInCopy link

LLMs are brittle to renamed nodes and reworded task formulations in graph reasoning, and the usual fix, throwing a multi-agent system at the parsing failures, costs prohibitive latency. GRAIN is a single RL-trained agent that models reasoning as semantic parsing plus tool execution, rewarded by a Structure Invariance Reward that validates extracted intermediate graphs against ground-truth topology so the model learns text-to-structure mappings rather than surface artifacts. It outperforms multi-agent baselines by 16.45% accuracy at roughly 24% lower latency and halves the out-of-distribution gap of SFT models from 15.77% to 7.80%, with a companion benchmark GRIT measuring sensitivity to name and narrative shifts.