PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2607.27652v3cs.CL

TL;DR

RL search agents retain a free-form retrieval interface that can produce different queries with nearly identical evidence, limiting retrieval contrast for optimization. Harness-G replaces it with finite graph-guided evidence or entity actions and adds Structured Non-myopic Credit, achieving the highest average F1 across six QA benchmarks and surpassing Graph-R1 by 10.74 points at 1.5B and 3.98 points at 3B.

  • Problem

    Existing RL search agents retain free-form query generation despite limited evidence that this retrieval interface suits RL optimization.

  • Method

    Harness-G uses a graph-structured environment with finite evidence, entity, and answer actions, alongside Structured Non-myopic Credit for structured step credit.

  • Results

    10.74 points at 1.5B and 3.98 points at 3B: Harness-G achieves the highest average F1 across six QA benchmarks and outperforms Graph-R1.

  • Takeaways & Limitations

    The results support action-space design as a complementary axis to reward design for training search agents.

  • Takeaways & Limitations

    Harness-G remains text-only, leaving extension of its structured actions and SNC to multimodal evidence as future work.

Abstract

from arXiv · show

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.

Introduction

Harness-G argues that free-form query generation creates retrieval-equivalence collapse: surface-diverse queries increasingly yield overlapping evidence, weakening retrieval contrast for RL optimization. It replaces this interface with graph-guided finite action selection and introduces SNC, achieving the highest average F1 across six benchmarks at both evaluated scales.

  • Motivation: RL search agents generate free-form queries and optimize complete multi-turn interaction trajectories using final-answer rewards.The paper notes that existing methods add process, information-gain, or finer-grained credit signals while retaining this retrieval interface.
  • Retrieval-equivalence collapse: Surface-distinct queries can express equivalent retrieval intent, so query-form diversity may remain high while retrieval-outcome diversity collapses.The paper measures query-form diversity among generated queries and retrieval-outcome diversity by clustering trajectories according to their retrieval results.
  • Optimization consequences: Retrieval-equivalence collapse causes vanishing within-group advantages and confounds retrieval credit with downstream reasoning or answer generation.When trajectories gather overlapping evidence, identical answers produce identical returns, while different answers can make return differences reflect later computation rather than retrieval.
  • Harness-G: Harness-G reformulates query generation as graph-guided finite action selection over paragraph–sentence–entity states, with the environment constructing queries and updating retrieval state.The bounded menu lets the policy select a retrieval target or answer through actions such as Select, Lookup, and Answer.
  • Results and credit: 10.74 points at 1.5B and 3.98 points at 3B are Harness-G’s gains over Graph-R1 in average F1 across six multi-hop and open-domain QA benchmarks.The framework combines same-state alternative comparison using a frozen answer scorer with enablement credit that propagates downstream gains to earlier bridge actions.

Related Work

Prior search-agent work trains free-query retrieval with outcome rewards, while graph-based methods support corpus aggregation or discrete navigation. Harness-G differs by combining interactive graph retrieval with finite action selection rather than retaining free-form queries.

  • Free-query RL search and credit assignment: Outcome-reward free-query agents include Search-R1, R1-Searcher, and DeepResearcher, extending earlier query reformulation and browser/tool-coupled generation.Other work adds cold starts, live-web research, or simulated retrieval.
  • Graph retrieval and discrete navigation: GraphRAG systems commonly use LLM-built corpus graphs for one-shot multihop aggregation, whereas Graph-R1 adds interactive end-to-end RL but retains free-form graph queries.The cited graph-retrieval line includes work by Edge et al., Guo et al., Gutiérrez et al., and Luo et al.
  • Graph retrieval and discrete navigation: KGQA path agents select entities or relations on curated schemas, providing finite actions unavailable to open-text free-query agents.This contrast motivates discrete navigation as an alternative retrieval interface.

Method

Harness-G replaces free-form query generation with finite, stateful graph navigation in which the environment constructs and validates discrete retrieval actions. Its SNC mechanism compares actions against same-state alternatives and propagates downstream information gains to earlier enabling steps.

  • Graph construction and navigation: The state tracks the question, committed evidence, visible candidates, visited entities, and history, while discrete operators replace arbitrary query strings.The policy selects an action id from the environment’s menu rather than emitting a natural-language query.
  • Graph construction and navigation: Harness-G builds a paragraph–sentence–entity graph offline, then exposes a finite, deduplicated menu of Select, Lookup, and Answer actions online.The environment maintains retrieval state and deterministically constructs retrieval queries, leaving the policy to choose which evidence or entity to pursue.
  • Graph construction and navigation: Lookup actions target entities rather than generated strings, and menu filtering removes committed sentences, duplicate retrievals, visited entities, and low-value targets.This makes distinct Lookups pursue distinct targets by construction and bounds the available action set.
  • Structured Non-myopic Credit: SNC uses a frozen answerer and read-only previews to compute frontier-relative gains, assigning positive credit only when an action outperforms feasible same-state alternatives.Re-surfacing already observed text receives exactly zero gain, reducing reinforcement for superficial choices.
  • Structured Non-myopic Credit: SNC propagates downstream gains backward over acyclic provenance edges, crediting early hops that enable later retrieval through bridge entities.The resulting step credit is placed on the response tokens of the action that produced the enabling evidence or entity.

Experiments

Harness-G achieves the strongest average F1 at both model scales, with especially large gains on multi-hop QA and smaller models. Ablations and transfer analyses attribute performance to structured action menus, SNC, stable optimization, and robust out-of-distribution generalization.

  • Main Results: 55.24 average F1 at 3B surpasses Graph-R1 by 3.98 points, with gains of 7.97, 9.12, and 5.95 on 2Wiki, HotpotQA, and MuSiQue.Harness-G also improves average R-S from 60.19 to 64.55 and achieves higher G-E on all six datasets, but trails Graph-R1 by 1.84 F1 on NQ.
  • Main Results: 10.74 points is Harness-G’s average-F1 improvement over Graph-R1 at 1.5B, where it outperforms Graph-R1 on every dataset.Average F1 rises from 40.09 to 50.83; R1-Searcher scores higher only on NQ, 36.86 versus 35.81.
  • Interface and Credit Ablations: More than 17 F1 points separate the action-menu and free-query interfaces under both credit regimes, while Menu+SNC performs best on all three multi-hop datasets.Under outcome-only training, the menu advantage exceeds 35 points on MuSiQue; free-query rollouts also collapse into fewer retrieval-equivalence classes.
  • Optimization Stability: 23% is Harness-G’s minimum zero-advantage-group rate near step 10, followed by a rebound driven by all-correct rather than all-wrong groups.This pattern indicates convergence after diverse exploration, unlike Search-R1’s early retrieval-diversity collapse.
  • Interface and Credit Ablations: 3.08, 4.55, and 2.88 F1 points are lost on 2Wiki, HotpotQA, and MuSiQue when both SNC terms are removed.Full SNC is best on every multi-hop dataset, and removing either term also hurts.
  • Generalization: +3.29 mean O.O.D. F1 marks Harness-G’s transfer gain, rising from 44.10 to 47.38 while winning 21 of 30 pairs.The menu policy remains stable across source-target pairs, with larger gains on multi-hop than single-hop targets.

Conclusion … C Baseline Details

The conclusion presents Harness-G as an action-space redesign that addresses retrieval-equivalence collapse by replacing free-form queries with structured graph-based selections. The appendices document evaluation datasets, baselines, metrics, training procedures, robustness analyses, and retrieval-equivalence diagnostics, while noting multimodal extension as future work.

  • Conclusion: Harness-G reframes retrieval in RL search agents by replacing aliased free-form query generation with finite evidence-sentence and entity selections over a programmatically induced graph.The paper identifies retrieval-equivalence collapse as surface-level query diversity masking nearly identical evidence and weakening group-relative learning.
  • Conclusion: Harness-G remains text-only, making extension of its structured actions and SNC to multimodal evidence a key next step.
  • A Appendix Overview: The appendix covers six evaluation datasets, baseline descriptions, evaluation metrics, training hyperparameters, optimization, training dynamics, robustness, and retrieval-equivalence diagnostics.
  • B Dataset Details: Harness-G is evaluated on six widely used RAG benchmarks spanning multihop and single-hop question answering.
  • B Dataset Details: The benchmarks include 2WikiMultiHopQA, HotpotQA, MuSiQue, Natural Questions, PopQA, and TriviaQA, covering compositional, bridge, comparison, entity-centric, and trivia questions.
  • B Dataset Details: Each dataset contains 5,120 training and 128 held-out questions, with final checkpoints evaluated on held-out splits and no held-out question used for checkpoint selection.The protocol matches Graph-R1, and the paper emphasizes large, consistent cross-dataset trends because each held-out split is small.
  • C Baseline Details: Baselines are grouped into prompt-only and Qwen2.5-based trained methods, while Table 1 distinguishes knowledge interfaces from knowledge-construction regimes.LLM-based construction requires generative-LLM corpus extraction or structural organization; named-entity recognizers and dense encoders alone do not qualify.
  • C Baseline Details: The comparison includes Naive Generation, Standard RAG, graph-based retrieval methods, SFT, R1, Search-R1, IGPO, and Harness-G under defined interface and construction regimes.Harness-G uses programmatic, LLM-free graph construction; published Graph-R1 values are cross-stack references, while interface and credit variants are matched only in the RQ2 ablation.

D Evaluation Details

Evaluation uses the Graph-R1 suite, reporting metrics on a 0–100 scale. It measures answer matching, token overlap, evidence agreement, and GPT-4o-mini-scored generation quality, with averages computed across six datasets.

  • All evaluation metrics use the Graph-R1 suite and are reported on a 0–100 scale.
  • Exact Match lowercases predictions, removes articles and punctuation, canonicalizes whitespace, and checks matches against accepted answer aliases.
  • Token F1 computes maximum normalized token-overlap F1 against the gold answer aliases.
  • Retrieval Similarity measures semantic agreement between retrieved evidence and gold evidence using the Graph-R1 metric encoder.
  • Generation Evaluation uses GPT-4o-mini to score responses from 0 to 10 across seven dimensions, then maps results to 0–100; dataset averages are unweighted across six datasets.The seven dimensions are comprehensiveness, knowledgeability, correctness, relevance, diversity, logical coherence, and factuality. Per-dataset Table 1 columns report F1 and G-E, while Avg. columns cover EM, F1, R-S, and G-E without pooling questions.

E Implementation Details

Harness-G trains a single Qwen2.5-3B policy to select retrieval actions and generate answers, using verl on eight NVIDIA A100 GPUs. Training masks environment-injected tokens, keeps SNC’s answerer frozen, and constructs retrieval graphs from document structure and entity mentions.

  • Configuration: A single policy model selects menu actions and generates the final answer, trained with verl on eight NVIDIA A100 GPUs.Under the Table 7 batch configuration, 120 optimizer steps correspond to approximately three passes over the training set.
  • Training objective and masking: Environment-injected observation and retrieval tokens are excluded from policy loss, so GRPO and SNC update only model-generated tokens.SNC uses the initial reference checkpoint as a frozen answerer throughout training.
  • Harness-G rollout and training: Each rollout initializes retrieval, renders committed evidence and visible menu sentences, samples an action, previews and executes it, then generates an answer and computes rewards.The rollout terminates when the selected action is Answer.
  • Graph construction: The retrieval graph preserves paragraph–sentence context, records sentence–entity mentions, and canonicalizes entity surface forms through normalization and junk filtering.Entities are extracted with spaCy en_core_web_sm across the listed entity categories, while paragraphs are split using abbreviation- and initial-safe rules.

F Training Dynamics and Robustness Details

Harness-G shows stable optimization across six Qwen2.5-3B runs, transfers across backbone families, and remains compatible with multiple RL algorithms. Training-batch F1 improves without persistent late-stage collapse under the reported settings.

  • Stable optimization across datasets: 0.36–0.62 training-batch F1 rise across six Qwen2.5-3B runs occurs without persistent late-stage collapse.Gradient norms are bounded by 12.7 and are typically below 9 late in training.
  • Backbone transfer: 63.4–67.5 F1 is achieved by Qwen2.5-3B, Qwen3.5-4B, and Llama-3.2-3B under a fixed HotpotQA dataset and 120-step budget.Qwen3.5-4B is best overall, while Llama-3.2-3B remains within a 2.5-point F1 band of the default.
  • Compatibility with multiple RL algorithms: 4 RL algorithms show rapidly rising, stable training-batch F1 through optimization with Qwen2.5-3B and a fixed 120-step budget.GRPO performs best overall, slightly ahead of DAPO, while REINFORCE++ and PPO show similarly stable training.

G Additional Evaluation Protocols

This section defines diagnostics and controlled evaluation protocols for distinguishing query diversity from retrieval diversity, measuring zero-advantage groups, isolating interface and credit effects, and assessing cross-dataset generalization.

  • Retrieval-equivalence diagnostics: Retrieval-equivalence classes group same-question rollouts by evidence-overlap cluster assignments, enabling within-group analysis of retrieval outcomes.Equivalence is defined within each same-question rollout group, not globally across unrelated questions.
  • Retrieval-equivalence diagnostics: Retrieval-equivalence collapse is diagnosed when Dret approaches zero and N_eq approaches one while Dquery remains high, indicating illusory exploration.Dquery measures query-form diversity; Dret and N_eq measure retrieval-outcome diversity.
  • Zero-advantage diagnostics: 10^-6 defines the within-group reward-standard-deviation threshold for zero-advantage groups, which are stratified into all-wrong and all-correct classes.Groups require Ng ≥2; all-correct means every rollout has strictly positive answer F1. Figure 7 compares Search-R1 and Harness-G on 2Wiki with matched Qwen2.5-3B and group size 8.
  • Transition-matched interface comparison: Matched interface runs fix reachable states and retrieval substrate, testing finite target selection against an open string-to-target mapping.The protocols match data order, random seeds, budgets, corpora, graph indices, checkpoints, and answer-F1 outcome rewards.
  • Factorial credit control: SNC is evaluated only with enumerable action menus, so its gain over Menu+IGPO measures the value of structured frontier and provenance-based enablement.Outcome-only arms receive no additional step advantage, while IGPO uses policy-belief information gain, turn-level normalization, cumulative turn advantage, and reward scaling.
  • Cross-dataset generalization: Cross-dataset generalization evaluates each source-dataset policy on held-out splits of all six target datasets across 30 off-diagonal train–test pairs.The reported O.O.D. mean follows the protocol of Table 1.

H Additional Generalization Results … K Invalid-Target Filter

The appendix reports stronger cross-dataset and zero-shot generalization for Harness-G, while detailing SNC computation and the progressive simplification and constraint-screening of its action interface. The final design separates policy-selected information targets from environment-executed retrieval mechanisms and deterministically filters invalid targets.

  • H Additional Generalization Results: 21 of 30 off-diagonal pairs favor Harness-G, raising mean O.O.D. F1 from 44.10 to 47.38 (+3.29), with larger gains on multi-hop targets.The margin is +6.45 F1 on 2Wiki, HotpotQA, and MuSiQue versus +0.12 on NQ, PopQA, and TriviaQA.
  • H Additional Generalization Results: Harness-G achieves the highest average F1 across I.I.D., single-O.O.D., and combined training regimes, with smaller gaps between regimes than free-query agents.The regime ordering remains I.I.D. best, combined second, and single-O.O.D. worst.
  • H Additional Generalization Results: 3.16 average F1 separates Harness-G from Graph-R1, while 3.69 separates it from HyperGraphRAG in zero-shot specialized-domain evaluation.The evaluation covers Medicine, Agriculture, CS, Legal, and Mix without training data from those domains.
  • I SNC Computation per Trajectory: SNC combines same-state comparisons against feasible frontier actions with reverse credit propagation over a provenance graph using read-only deterministic previews.A frozen answerer scores the selected action and alternatives, while reverse propagation credits direct producers of later-consumed evidence.
  • J Action-Space and Constraint Screening: The final Harness-G interface exposes Select, Lookup, Answer_With, and Answer, while environment-side constraints remain outside the policy menu.The design is evaluated on 2WikiMultiHopQA with F1, EM, and mean interaction turns under a matched Qwen2.5-3B-Instruct budget.
  • J.1 Action-menu evolution: The menu evolves by removing free-query access, dropping Open_Context, merging Expand_Entity and Bridge_Entity into Lookup, and adding Answer_With.These changes shift the policy toward selecting information targets while the environment executes retrieval mechanisms.
  • J.2 Environment constraints: Environment constraints restrict navigation anchors and repeated lookup keys before or during menu construction, reducing weak-anchor hops and no-op turns without becoming policy actions.Junk and bad-target filtering removes typed literals and malformed surfaces from Lookup while preserving their sentence mentions for Select and answering.
  • K Invalid-Target Filter: The invalid-target filter changes only the feasible Lookup menu by excluding typed mentions, malformed surfaces, and nationality or ethnic adjectives identified deterministically.Original mentions remain visible in sentence text and can still support answer generation.

L Knowledge-Construction and Query Cost · M Extended Related Work · N Illustrative Trajectories

The appendices quantify Harness-G’s construction and training costs, position it against related retrieval and credit paradigms, and illustrate how finite validated menus support typed, non-myopic exploration. Qualitative trajectories show recurring patterns including same-state alternatives, minimal evidence sets, and task-specific bridge, comparison, and composition behaviors.

  • L Knowledge-Construction and Query Cost: Harness-G’s construction pipeline uses no generative LLM, so construction time is dominated by sentence splitting, entity recognition, and dense encoding; overhead scales with the bounded preview frontier.Table 6 reports TP1KT, CP1MT, graph size, TPQ, and CP1KQ on 2Wiki.
  • L Knowledge-Construction and Query Cost: A full 3B run costs about 170 GPU·h on 8×A100, while SNC is training-only and adds no model calls at inference.Rollout generation and policy optimization account for the main training hours; SNC performs read-only previews and frozen-answerer scoring.
  • M Extended Related Work: The related-work discussion organizes prior systems by retrieval action, knowledge structure, and training signal before contrasting Harness-G along each axis.The appendix expands the main paper’s related-work discussion.
  • M Extended Related Work: Prior free-form RL search agents optimize recall or answer quality with natural-language rewrites, while WebGPT, ReAct, IR-CoT, and FLARE interleave generation with external retrieval actions.The cited systems represent free-form query reformulation, typed browser commands, reasoning-action interleaving, and repeated retrieval.
  • M Extended Related Work: Dense-reward and multi-turn-credit methods address brittle sparse terminal rewards by redistributing delayed returns, diagnosing vanishing within-group advantages, or measuring per-turn information gain.The passage cites classical hindsight credit methods, RAGEN, and IGPO.
  • M Extended Related Work: Graph-structured retrieval systems reorganize corpora into entity-, path-, or community-structured indices, but many invoke generative LLMs for extraction, relation labeling, or summaries.The passage contrasts Chunk RAG with GraphRAG, LightRAG, PathRAG, HyperGraphRAG, and HippoRAG variants.
  • M Extended Related Work: Harness-G combines an open-corpus graph with a finite, verifiable, previewable menu, importing discrete navigation into open documents where sentences are evidence units and entities are bridge nodes.Curated-KG systems benefit from finiteness and often verifiability but do not address open-text corpora or a cheaply induced evidence graph for free-form RAG agents.
  • N Illustrative Trajectories: Held-out Menu+SNC Qwen2.5-3B trajectories cover bridge retrieval, film-year comparison, multi-hop composition, birth-date comparison, and boolean country comparison.The cases track typed targets, same-state alternatives, and minimal committed sets; bridge retrieval is reused for free-query contrast and SNC panels, while comparison and composition cases stress early stopping, distractors, and join-entity co-mention.

N.1 Menu Navigation: Process and Effectiveness · N.2 Interface Contrast: Free Query vs. Menu

Harness-G’s finite menus support efficient, verifiable multi-hop navigation: policies select typed evidence, ignore distractors, stop when comparisons are closed, and avoid unnecessary lookup. Compared with free-form querying, the menu avoids near-duplicate retrieval classes that can mix distractors and produce an incorrect answer.

  • N.1 Menu Navigation: Process and Effectiveness: The bridge trajectory selects the film’s director, then looks up Caroline Leaf before answering with the relevant birth-date evidence.The opening menu contains 16 typed actions, including unrelated director biographies; the policy explicitly chooses Caroline Leaf rather than Franz Kafka or the film title.
  • N.1 Menu Navigation: Process and Effectiveness: When both comparison operands are visible, the policy commits them, ignores residual lookups and a near-name distractor, and stops without extra search.The film-year comparison uses The Frozen Child (1921) and Naadody (1992), while Frozen (2010) remains unselected.
  • N.1 Menu Navigation: Process and Effectiveness: The menu supports multi-hop composition by combining a bridge sentence with an answer sentence and answering without an additional search step.In the MuSiQue example, period-mismatched trade sentences, residual lookups, and distractor selects are left uncommitted.
  • N.1 Menu Navigation: Process and Effectiveness: The menu also resolves birth-date and Boolean country comparisons by selecting both required operands or predicates while rejecting plausible name-based distractors.The birth-date case compares Winderstein (1856) and Ličina (1991); the Boolean case commits British Early Opera Company and American Beggars’ Guild evidence, issues no Lookup, and answers No.
  • N.1 Menu Navigation: Process and Effectiveness: The menu makes relational decisions operational: with both dates visible, the policy determines who is younger rather than issuing a free-form date query.This separates recognizing a closed comparison from fetching missing evidence and makes the decision an explicit identity choice.
  • N.1 Menu Navigation: Process and Effectiveness: Cross-case analysis shows menus provide finiteness, verifiability, and previewability through bounded action ids, explicit competing actions, and deterministic alternative expansion.Opening menus contain roughly 10–16 actions, and SNC can expand rejected alternatives read-only during training even though inference-time policies do not call the scorer.
  • N.2 Interface Contrast: Free Query vs. Menu: Under free-form querying, surface rewrites fall into near-duplicate retrieval classes that mix distractor biographies and lead to an incorrect birth date from Satyajit Ray.The menu reparameterizes the same corpus evidence as typed Select, Lookup, and Answer_With decisions.

N.3 SNC: Frontier, Enablement, and Credit Comparison … A. Free-query search agent

Harness-G couples finite, typed menu decisions with SNC, which rewards same-state superiority and propagates delayed gains to enabling hops. Its inspectable trajectories show both successful composition and localized failures, while free-query retrieval remains noisy and aliased.

  • N.3 SNC: Frontier, Enablement, and Credit Comparison: SNC assigns +0.59 frontier-relative credit when an action beats feasible same-state alternatives, rather than rewarding retrieval generically.Caroline Leaf yields pt=+0.61, while competing lookups have near-zero gain.
  • N.3 SNC: Frontier, Enablement, and Credit Comparison: SNC propagates +0.61 enablement credit from the later attribute lookup to the earlier bridge hop that exposed its entity.Without enablement, the necessary bridge receives near-zero local credit despite enabling gold-attribute retrieval.
  • N.3 SNC: Frontier, Enablement, and Credit Comparison: Compared with outcome-only and myopic credit, SNC moves process credit onto the enabling hop while concentrating it on the uniquely good same-state alternative.The comparison describes a “bridge, then attribute” pattern and identifies frontier and enablement as complementary terms.
  • N.4 Additional Failure Cases: Held-out failure traces remain inspectable under typed menus, with errors arising from attribute-matched distractors, missing visible gold candidates, or answer-string composition.One case answers Arjen Robben from an explicit 1984 cue; another selects a coherent but incorrect bridge, yielding EM = 0, F1 = 0.
  • N.5 Synthesis: The synthesis presents interface reparameterization and structured non-myopic credit as coupled mechanisms whose effects appear in individual successful and unsuccessful decisions.The menu controls finite typed choices and adaptive depth, while SNC handles delayed payoffs through frontier and enablement credit.
  • N.5 Synthesis: A held-out country comparison terminates after two typed nationality commits with zero lookups because both predicates are already visible and sufficient.The policy avoids lookup and stops once the evidence is sufficient.
  • O Environment Protocol and Prompts: At each step, the environment renders committed evidence, visible sentences, exposed entities, and an executable action menu requiring exactly one action id instead of a natural-language query.Lookup construction, candidate retrieval, validation, duplicate merging, and removal of previously used choices are environment-controlled.
  • A. Free-query search agent: In the free-query interface, the first surface query retrieves Caroline Leaf alongside unrelated directors, leaving evidence noisy and without a typed commit.The example asks for the director’s birth date and shows that the initial natural-language query does not impose a committed evidence structure.

B. Menu+SNC (this paper)

Menu+SNC replaces free-form retrieval with typed, finite action menus and uses SNC to compare same-state alternatives while propagating downstream gains to enabling earlier actions. The bridge example shows why this matters: early selections may enable successful lookups without immediately improving the answer score, while open-string spaces cannot enumerate the relevant baseline.

  • Menu interface: Typed Select menus expose discrete evidence targets, letting the policy choose a bridge entity such as Caroline Leaf rather than generate an open-ended query.Distractor director sentences remain selectable but are not the same action as the bridge commit.
  • Menu interface: After selecting S1, the menu offers typed Lookup, residual Select, and premature Answer actions; only information-acquiring Lookups enter the retrieval frontier.The frozen answerer scores the gold answer August 12, 1946 conditional on the question and observed evidence.
  • Structured Non-myopic Credit: +0.61 is the gain for Lookup Caroline Leaf, compared with +0.03 for Lookup The Metamorphosis and +0.02 for Lookup Franz Kafka’s among same-state alternatives.SNC ranks the selected lookup against alternatives at the same frontier state.
  • Structured Non-myopic Credit: SNC sends downstream lookup gains back along provenance edges to the earlier Select that produced the enabling entity, without extra rollouts.This addresses myopic credit, which can assign near-zero process credit to necessary early hops that do not immediately raise the frozen answer score.
  • Failure cases: EM = 0 in the held-out HotpotQA attribute-matched distractor case, where a birth-year-matched candidate appears on the menu but the gold scorer does not.The failure illustrates that Menu+SNC can answer prematurely when the opening menu lacks the required bridge evidence.
Loading 2607.27652v3…