Tsinghua's Graph-S³ Retrieves 89% Fewer Triples While Beating Every Baseline
A new framework teaches LLM agents to walk knowledge graphs step by step, using synthetic golden subgraphs as dense rewards instead of sparse answer signals.
Takeaways
- Graph-S³ trains an LLM retriever with stepwise rewards from offline golden subgraphs instead of sparse answer signals. Paper
- Retriever uses three actions: Explore Entity, Choose Relation, and Finish, over textual (head, relation, tail) triples.
- Two-stage training: SFT on raw GPT-4o trajectories, then GRPO with graded per-step rewards on refined trajectories.
- Beats seven baselines on WebQSP, CWQ, and MetaQA with the largest gains on 2-hop and 3-hop questions.
- Retrieves only 11.44% of the triples used by G-Retriever while producing higher accuracy answers.
- Trajectory refinement, which prunes redundant steps before RL, is the single most important ingredient in ablations.
Getting large language models to reason over structured knowledge graphs sounds straightforward until you hit the retrieval problem. The graph is usually far too large to stuff into a context window, and picking the right subgraph is where most systems fall apart. A team from Tsinghua's Institute for AI Industry Research, together with collaborators from Peking University, Renmin University, and others, has proposed Graph-S³, an agentic retrieval framework that trains the retriever with step-by-step rewards derived from synthetically distilled golden subgraphs.
Why sparse rewards break graph agents
Textual graphs, which store facts as (head, relation, tail) triples, are the backbone of question-answering systems that need multi-hop reasoning. Existing retrieval methods either lean on shallow embedding similarity or on interactive policies trained with outcome-based supervision, which provides only coarse feedback and limits stable multi-hop reasoning.
The core problem with outcome rewards is credit assignment. The action space in real-world textual graphs is too vast for efficient exploration, and outcome-based rewards are sparse and noisy. Redundant or erroneous retrieval steps may coincidentally lead to the correct final answer, rendering outcome supervision unreliable for assessing reasoning quality. If the agent stumbles into the right answer through a chain of bad decisions, standard RL will happily reinforce those bad decisions.