Harness-G: A Graph-Structured Harness for Search Agents
Yanning Hou, Haoyuan Chen, Sihang Zhou, Xiaoshu Chen, Xirui Liu, Duanyang Yuan, Lingyuan Meng, Siwei Wang, Quan Liu, Jian Huang
cs.CL
Submitted: 2026-07-30
Comments: Code:https://github.com/7HHHHH/Harness-G
Code: https://github.com/7HHHHH/Harness-G
License: http://creativecommons.org/licenses/by/4.0/
The gist: Reinforcement learning (RL) search agents commonly model retrieval as free-form natural-language query generation and optimize multi-turn interactions using final-answer rewards.
Terminology
Abstract
Reinforcement learning (RL) search agents commonly model retrieval as free-form natural-language query generation and optimize multi-turn interactions using final-answer rewards. Current studies mainly improve training with denser or more structured credit signals, but rarely examine whether retrieval is properly formulated at the policy-environment interface. We observe pronounced retrieval aliasing during Search-R1 training: rollouts for the same question continue to generate distinct query strings, yet their accumulated evidence sets increasingly overlap. We call this phenomenon retrieval-equivalence collapse; in this regime, trajectories approach utility equivalence with respect to retrieval decisions, leaving within-group returns with little effective retrieval contrast. To address this problem, we propose Harness-G, a graph-structured retrieval framework that redesigns this interface. It reformulates free-form query generation as finite action selection: the policy selects an evidence sentence or entity, or chooses to answer, while the environment constructs the menu, tracks retrieval state, and validates and executes each choice. This interface reduces linguistic aliasing and makes same-state alternatives directly comparable. Building on this interface, we introduce Structured Non-myopic Credit (SNC), which uses a frozen answer scorer to compare the selected action with its alternatives and assigns downstream gains to the earlier actions that enabled them. Across six QA benchmarks, Harness-G achieves the highest average F1 at both evaluated model scales, outperforming the strongest baseline, Graph-R1, by 10.74 points at 1.5B and 3.98 points at 3B.
Sources
- PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths
- ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- From Local to Global: A Graph RAG Approach to Query-Focused Summarization
- Group-in-Group Policy Optimization for LLM Agent Training
- LightRAG: Simple and Fast Retrieval-Augmented Generation
- From RAG to Memory: Non-Parametric Continual Learning for Large Language Models
- AtomicRAG: Atom-Entity Graphs for Retrieval-Augmented Generation
- REINFORCE++: Stabilizing Critic-Free Policy Optimization with Global Advantage Normalization
- Tree Search for LLM Agent Reinforcement Learning
- Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning
- Turn-PPO: Turn-Level Advantage Estimation with PPO for Improved Multi-Turn RL in Agentic LLMs
- Search-o1: Agentic Search-Enhanced Large Reasoning Models
- WebThinker: Empowering Large Reasoning Models with Deep Research Capability
- Efficient and Transferable Agentic Knowledge Graph RAG via Reinforcement Learning
- Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning
- HyperGraphRAG: Retrieval-Augmented Generation via Hypergraph-Structured Knowledge Representation
- Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation
- WebGPT: Browser-assisted question-answering with human feedback
- Proximal Policy Optimization Algorithms
Related papers
- Exploring Solution Divergence and Its Effect on Large Language Model Problem Solving
- Ishigaki-IDS-Bench: A Benchmark for Generating Information Delivery Specification from BIM Information Requirements
- Subliminal Steering: Stronger Encoding of Hidden Signals
- MedStruct-S: A Benchmark for Key Discovery, Key-Conditioned QA and Semi-Structured Extraction from OCR Clinical Reports
- The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architectures
- Untangling the Mechanisms of Misleading Context in Medical Question Answering