Graph aware reasoning improves multi step question answering accuracy
GraphEvoResearcher: Graph-Aware Training-Free Self-Reflective Reasoning for Cost-Bounded Multi-Hop Question Answering
Artificial Intelligence
Summary
Answering questions that need multiple steps often requires figuring out how each step connects. The authors present a new way to keep track of these steps and how they relate to each other using a graph. This method helps the system know when to rethink parts, stop early, or trust certain answers better. Their tests show this approach works especially well when the questions are really hard and usual single-step methods struggle.
What this means in practice
- •For natural language processing teams: Improve multi-step question answering in AI assistants by tracking intermediate reasoning with graphs to boost accuracy on complex questions.
- •For automated math tutoring platforms: Enhance step-by-step problem solving explanations by recognizing when reasoning paths converge or need revision, reducing errors in generated solutions.
Authors
Suxing Liu
Abstract
Multi-hop question answering (QA) requires models to chain intermediate conclusions while remaining cost-aware. Existing training-free self-reflective protocols (generate -> critique -> revise) improve accuracy but operate on a flat token stream: revisions cannot identify which prior step is unreliable, and early stopping cannot exploit structural convergence. We introduce GraphEvoResearcher, a training-free protocol that lifts EvoResearcher's self-reflective meta-reward onto an explicit reasoning graph - nodes are intermediate conclusions/evidence and edges encode support, contradict, and depends_on. A graph-aware meta-reward combines correctness, efficiency, reflection, diversity, and four structural signals (connectivity, acyclicity, branch coverage, path convergence) to decide whether to revise, backtrack, or stop. A graph-convergence early-stop terminates when evidence branches converge on a single conclusion. On a real LLM (DeepSeek), over GSM8K, MATH, and BBH (n=50 each), GraphEvoResearcher reaches 98%, 92%, and 82% respectively, the highest of all baselines, with the largest gains on the hardest set (MATH: +24 pp over single-shot, +12 pp over flat reflection), while keeping construction cost bounded at ~2 steps / 4.5-5 nodes. Our results indicate the structural signal of a reasoning graph is most valuable exactly where single-step reasoning is unreliable.