Technical Summary: Harness-G

Problem: Retrieval-Equivalence Collapse in RL Search Agents

Reinforcement learning (RL) search agents, such as Search-R1, typically model retrieval as the generation of free-form natural language queries. These agents optimize multi-turn interaction trajectories using final-answer rewards (e.g., F1 or Exact Match). While recent studies attempt to improve training via denser credit signals (e.g., information gain, process rewards), they retain the fundamental interface where the policy generates a string and the environment maps it to retrieved evidence.

The authors identify a critical failure mode in this setup termed retrieval-equivalence collapse. During training, the policy generates diverse surface-level query strings (high query-form diversity), yet these queries often map to nearly identical sets of retrieved evidence (low retrieval-outcome diversity). As training progresses, trajectories for the same question converge into a single retrieval-equivalence class. This collapse creates two optimization problems for group-relative methods like GRPO:

1. Vanishing Advantages: If multiple trajectories retrieve the same evidence and produce the same answer, their returns are identical, causing within-group advantages to vanish.
2. Confounded Retrieval Credit: If trajectories retrieve the same evidence but produce different answers, the return differences reflect downstream reasoning rather than retrieval quality, making it impossible to attribute success or failure to specific retrieval actions.

Consequently, the "exploration" provided by diverse query strings is often illusory, failing to provide effective contrast for learning better retrieval strategies.

Methodology: Harness-G

To address this, the authors propose Harness-G, a graph-structured retrieval framework that redesigns the policy-environment interface. Instead of generating free-form queries, the policy performs finite action selection over a structured evidence space.

1. Graph-Structured Environment

Harness-G constructs a lightweight, programmatic tripartite graph offline from the corpus, consisting of:

• Paragraph nodes: Document contexts.
• Sentence nodes: The minimal evidence units.
• Entity nodes: Bridging cross-sentence and cross-document hops.
  Edges connect paragraphs to sentences, sentences to entities (via mentions), adjacent sentences, and identical/similar entities (via surface normalization and embedding neighbors). This graph is built without generative LLMs, relying on sentence splitting, NER, and dense encoding.

2. The Action Menu Interface

At each step, the environment exposes a bounded, finite action menu ($M_t$) to the policy. The policy selects an action ID from this menu rather than generating a text string. The actions are:

• Select(s): Commit a visible sentence $s$ as evidence.
• Lookup(e): Retrieve information around a specific entity $e$. The environment deterministically constructs the query (concatenating the question and committed evidence) and returns top-$K$ sentences.
• Answer / Answer_With: Terminate retrieval and generate an answer (optionally committing visible sentences in one step).

This design ensures that:

• Finiteness: The action space is bounded.
• Verifiability: Invalid actions are blocked before execution.
• Previewability: The environment can deterministically simulate (preview) the outcome of any candidate action without mutating state.

3. Structured Non-Myopic Credit (SNC)

Leveraging the previewable action frontier, Harness-G introduces Structured Non-Myopic Credit (SNC) to assign step-level rewards without requiring extra agent rollouts or external reward models. SNC consists of two terms:

• Frontier-Relative Advantage ($r^{fr}_t$): A frozen answer scorer evaluates the gold-answer probability given the current context. For an information-acquisition action, it calculates the marginal gain of the selected action versus the mean gain of a "frontier" of alternative feasible actions at the same state. This provides a local, same-state comparison unavailable in open query spaces.
• Enablement Credit ($r^{en}_t$): To address the non-myopic nature of multi-hop reasoning (where an early "bridge" action enables a later high-value retrieval), SNC propagates downstream gains back along a provenance graph. If step $u$ consumes an entity produced by step $t$, credit flows from $u$ to $t$ in reverse topological order.

The total step advantage is combined with the standard outcome reward in the GRPO objective: $\hat{A}_i = \hat{A}^{out}_i + \lambda \hat{A}^{SNC}_i$.

Key Contributions

1. Identification of Retrieval-Equivalence Collapse: The paper empirically demonstrates that free-form query interfaces in RL search agents lead to a collapse in retrieval diversity, rendering group-relative optimization ineffective.
2. Interface Redesign (Harness-G): It reformulates multi-hop retrieval as finite action selection over a graph-structured environment, replacing open-string generation with a verifiable, previewable menu.
3. Structured Non-Myopic Credit (SNC): It introduces a credit assignment mechanism that utilizes the action menu's previewability to compute same-state relative advantages and propagate delayed credit for enabling actions, all without additional rollouts.
4. Empirical Validation: Extensive experiments across six QA benchmarks (including multi-hop datasets like 2Wiki, HotpotQA, and MuSiQue) show that Harness-G significantly outperforms strong baselines, particularly in multi-hop scenarios and with smaller model scales.

Results

Evaluated on six benchmarks using Qwen2.5-1.5B and Qwen2.5-3B models:

• Performance: Harness-G achieves the highest average F1 at both model scales.
  • At 1.5B, it outperforms the strongest baseline (Graph-R1) by 10.74 points in average F1.
  • At 3B, it outperforms Graph-R1 by 3.98 points.
• Ablation Studies:
  • Replacing the free-query interface with the action menu alone improves F1 by over 17 points on average, with gains exceeding 35 points on MuSiQue.
  • Adding SNC further improves performance, particularly on multi-hop tasks where delayed credit is crucial.
• Stability and Efficiency: Harness-G exhibits stable training dynamics with bounded gradient norms. It requires no extra agent rollouts for credit assignment (only read-only previews) and incurs minimal overhead (~9–11% wall-clock time per step). It also demonstrates stronger out-of-distribution (O.O.D.) transfer capabilities compared to Graph-R1.

Significance and Claims

The paper claims that action-space design is a complementary and critical axis to reward design for training search agents. The authors argue that simply densifying rewards (e.g., via process rewards or information gain) within a free-form query interface cannot fundamentally solve the problem of retrieval-equivalence collapse because the interface itself allows for many-to-one mappings from queries to evidence.

By redefining the retrieval interface to be discrete, verifiable, and previewable, Harness-G enables:

1. Genuine Exploration: Ensuring that different actions lead to genuinely different retrieval outcomes.
2. Precise Credit Assignment: Allowing the agent to learn which specific evidence or entity choices are superior to alternatives at the same decision state.
3. Non-Myopic Learning: Effectively teaching the agent to perform necessary "bridge" steps that do not immediately yield high rewards but are essential for later success.

The work concludes that while Harness-G is currently text-only, its structured approach to action spaces and credit assignment offers a robust framework for training search agents, suggesting that future work could extend these principles to multimodal evidence.