Enhancing Agentic Textual Graph Retrieval with Synthetic Stepwise Supervision

Integrating textual graphs into Large Language Models (LLMs) is promising for complex graph-based QA. However, a key bottleneck is retrieving informative yet compact subgraphs that fit the LLM context. Existing retrievers often struggle, relying either on shallow embedding similarity or costly interactive policies that require excessive supervision. To address these challenges, we introduce Graph-S 3 , an agentic textual graph reasoning framework featuring an LLM-based retriever trained with synthetic stepwise supervision. Rather than relying on final answer rewards-which often yield sparse and unstable signals-we optimize the retriever by evaluating each step against offlineextracted golden subgraphs. Our approach distills golden subgraphs via a specialized data synthesis pipeline to formulate dense rewards, facilitating a two-stage training scheme that effectively learns the interactive graph exploration policy. Based on extensive experiments on three common datasets in comparison with several strong baselines, our approach achieves an average improvement of 15.6% in accuracy and 17.2% in F 1 score. The advantage is even higher in more complicated multi-hop reasoning tasks.