Harness-G: A Graph-Structured Harness for Search Agents

Yan-Ning Hou Hao-Yuan Chen Si-Hang Zhou Xiao-Shu Chen Xirui Liu Duan-Yang Yuan Lingyuan Meng Siwei Wang Quan Liu Jian Huang

Jul 2026 · arXiv.org · Vol abs/2607.27652 · 0 citations · 49 references

Computer Science

TL;DR

Harness-G, a graph-structured retrieval framework that reformulates free-form query generation as finite action selection, and introduces 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.

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.

DOI arXiv Semantic Scholar

View source

Similar papers

Preprint Jul 2026

SLMs as Multi-Agent Routers: A Progressive SFT and Reinforcement Learning Approach

A small language model is trained via supervised fine-tuning followed by reinforcement learning to jointly perform agent selection and structured parameter generation for downstream tool calls, using a hierarchical reward function grounded in retrieval relevance along with query-agent topic alignment to learn task-depe...

Gayathri V Kondapalli, Alexander Ng, Hirsh Pithadia et al. · 0 citations

Preprint Aug 2026

Search-GRT: Guided Retrieval Training of Search Agents to Optimize for Complex Question Answering

Guided Retrieval Training (GRT) is introduced, a novel method that improves the performance of a search agent by restricting the retrieval process during RL training using ground truth information, and enhances training efficiency by achieving better QA performance with fewer training steps.

Aounon Kumar, Sudipta Paul, Vivek Kulkarni et al. · 0 citations

#natural language process... Preprint Sep 2026

It Takes Two to Match: Co-Evolving Generative Retriever with Reinforcement Learning

CoGR is introduced, a retrieval framework that instead trains LLMs to directly construct retrieval representations on both query and item sides, and shows stable co-evolution and increasingly aligned query--item keyword spaces over training.

Runpeng Dai, Kai-Li Huang, Chang-Sung Kang et al. · 2 citations

#reinforcement learning Book Open access Aug 2026

NaviRAG: Learning to Navigate Knowledge Graphs for Retrieval-Augmented Generation

Retrieval-Augmented Generation (RAG) has become a fundamental paradigm for enhancing Large Language Models (LLMs) with external knowledge. However, while recent structure-augmented approaches organize documents into graphs to improve information access, their retrieval strategies remain largely static, relying on simil...

Jinghong Lei, Wang Kun, Zhigang Chen et al. · Proceedings of the 32nd ACM... · 0 citations

Jul 2026

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL), which surpasses every frozen frontier-LLM system in their comparison and posts the strongest results on CWQ of any system the authors compare against.

J. Sun, Hao Yu, Fengran Mo et al. · arXiv.org · 1 citation · ⚡1

#machine learning Preprint Aug 2026

GTA-RAG: Graph-Trajectory-Augmented Reinforcement Learning for Multi-Turn Retrieval-Augmented Reasoning

This work presents \textsc{GTA-RAG}, a graph-trajectory-augmented RL framework for multi-turn retrieval-augmented reasoning that consistently outperforms RL-based RAG baselines with both Qwen2.5-3B and Qwen2.5-7B backbones, while substantially improving evidence-chain coverage.

Jun Chen, Yongchao Liu, Pengyu Qiu et al. · 0 citations