HyperGraphPro Beats Graph-R1 on Multi-Hop Reasoning With Smarter RL
A new framework combines structure-aware hypergraph retrieval with step-level rewards to push multi-hop QA accuracy past Graph-R1 baselines.
ProTakeaways
- HyperGraphPro adds structure-aware retrieval and step-level rewards to Graph-R1-style agentic GraphRAG.
- Rescores hyperedges by combining semantic similarity with query-conditioned entity distinctiveness in the hypergraph.
- Replaces sparse outcome rewards with dense step-progress, connectivity, and answer-reachness signals.
- Beats Graph-R1 by 4.67 F1 on Qwen2.5-3B and 3.44 F1 on Qwen2.5-7B averaged across four QA benchmarks.
- Reaches higher accuracy in fewer reasoning turns despite not rewarding brevity directly.
- Read the full paper on arXiv; no public code release yet.
Graph Retrieval-Augmented Generation has become the go-to trick for getting language models to reason across scattered facts. Instead of dumping raw text chunks into the context window, you organize knowledge as a graph of entities and relations, then let the model walk it. A new paper, HyperGraphPro, argues that current reinforcement learning recipes for training graph-walking agents leave a lot of accuracy on the table, and proposes two fixes that push multi-hop QA scores meaningfully above the Graph-R1 baseline.
Where current GraphRAG agents break down
The authors identify two tightly coupled failures in RL-based GraphRAG systems like Graph-R1. Retrieval is driven almost entirely by semantic similarity between the query and candidate nodes, which ignores the underlying graph topology that multi-hop reasoning actually depends on. Training then uses sparse outcome-level rewards, so the agent only learns whether the final answer was right, with no signal about which intermediate retrieval steps helped or hurt.
These issues compound each other. Without structure-aware retrieval the agent wanders into noisy or disconnected evidence, and with only a final-answer reward it never learns which step in that wandering trajectory was the mistake. Credit assignment in a multi-hop setting is brutal when your only feedback comes at the end.
Rescoring hyperedges with structural distinctiveness
HyperGraphPro represents external knowledge as a hypergraph, where a single hyperedge can link more than two entities at once, capturing n-ary relations that ordinary graphs flatten. Given a query at reasoning step t, the agent extracts query entities and retrieves candidate hyperedges based on both semantic relevance and structural distinctiveness.