PaperlayerView exact revision on arXiv

Source-linked AI summary

Heterogeneous Co-Evolution Learning for Tool-Efficient Search Agents with Zero Labels

Qin-Wen Luo, Sheng Ren, Xiang Chen, Rui Liu, Jun Fang, Naiqiang Tan, Jun Wang, Hua Chai, Sheng-Jun Huang

arXiv:2610.39682v1cs.LGcs.AIcs.IR

TL;DR

Search-agent training must adapt its questions as agents improve and account for the cost of redundant searches, challenges fixed or labeled tasks and outcome-only rewards do not address. ZEST-Search constructs validated tasks from unlabeled questions through heterogeneous proposer–solver co-evolution and role-specific rewards. It improves search-agent performance across seven benchmarks while achieving higher tool efficiency without labeled search-training data or expert trajectories.

  • Problem

    Fixed or labeled task collections do not adapt to improving agents, while outcome-only rewards treat all correct trajectories alike despite redundant searches.

    Source: Introduction · p. 1

  • Method

    ZEST-Search uses heterogeneous proposer–solver co-evolution to generate validated tasks online from unlabeled reference questions and source-supported evidence paths, with rewards for intermediate task difficulty and tool-efficient solving.

    Source: Introduction · p. 2

  • Results

    Across seven benchmarks, ZEST-Search consistently improves search-agent performance and achieves higher tool efficiency without labeled search-training data or expert search trajectories.

    Source: Main Results · p. 5, Conclusion · p. 7

  • Takeaways & Limitations

    The framework improves both base models’ search-augmented reasoning and the performance of agents already trained for search, using unlabeled training questions.

    Source: Main Results · p. 5

Abstract

from arXiv · show

Deep search agents extend language models by interleaving reasoning with external retrieval. However, effective search-agent training requires addressing two challenges beyond final-answer optimization. First, the capability frontier of agents is largely determined by training questions, whereas fixed or labeled task collections cannot adapt as agents improve. Second, outcome-only reinforcement learning treats all successful trajectories equally, even when some correct answers rely on redundant searches, creating an inherent tension between answer accuracy and tool efficiency. To address these issues, we introduce \textsc{ZEST-Search}, a zero-label and tool-efficient framework for search-agent training via heterogeneous co-evolution. Starting from unlabeled reference questions, \textsc{ZEST-Search} constructs validated search tasks online through an answer-first and evidence-path-guided generation process. A heterogeneous proposer adaptively constructs training tasks around the solver's evolving capability boundary, while the solver learns search-augmented reasoning through reinforcement learning. To jointly optimize task difficulty and search efficiency, \textsc{ZEST-Search} employs an intermediate-difficulty reward for the proposer and a task-local tool-aware reward for the solver, encouraging informative tasks and correct answers with fewer redundant searches. Experiments on seven general-domain and multi-hop question answering benchmarks demonstrate that \textsc{ZEST-Search} consistently improves search-agent performance while achieving higher tool efficiency without labeled search-training data or expert search trajectories. Further analyses show that heterogeneous generation, adaptive difficulty control, and tool-aware optimization enable more effective search-agent training.

Introduction

Search-agent training must adapt its questions as solver capabilities change while rewarding efficient evidence-seeking, not just correct answers. ZEST-Search addresses both challenges through zero-label task generation and heterogeneous proposer–solver co-evolution.

Introduction

  • Fixed training questions can become a static curriculum that fails to expose new weaknesses, while outcome-only rewards cannot distinguish concise correct searches from redundant ones.Optimizing answer correctness alone may improve accuracy while increasing tool-use costs.Source: Introduction · p. 1
  • Adaptive task generation alone may worsen tool inefficiency when harder questions prompt correctness-only solvers to search extensively despite little marginal value from added queries.The proposed approach therefore pairs difficulty adaptation with tool-aware optimization.Source: Introduction · pp. 1–2
  • ZEST-Search generates validated search tasks from unlabeled reference questions, target entities, and source-supported multi-hop evidence paths without labeled QA pairs or expert trajectories.Lightweight retrieval and NLP components handle validation, path construction, and task filtering without additional LLM inference.Source: Introduction · p. 2
  • Heterogeneous proposer–solver roles let lightweight or cross-family proposers generate complementary tasks around the solver’s evolving capability boundary.This decoupling avoids constraining generation to predefined answer pools and shared knowledge priors.Source: Introduction · pp. 1–2
  • Role-specific rewards steer the proposer toward intermediate-difficulty questions near the solver’s learning frontier and favor correct solver trajectories with fewer redundant searches.This jointly addresses adaptive task difficulty and search efficiency.Source: Introduction · p. 2

Preliminaries

The preliminaries define verifiable-reward learning and group-relative policy optimization, then describe how search agents interact with retrieval during response generation.

Reinforcement Learning with Verifiable Rewards

  • RLVR trains language models with programmatically verifiable outcomes, assigning reward 1 when the generated final answer matches the target and 0 otherwise.The response comprises a reasoning trace and a final answer.Source: Preliminaries · p. 2

Group Relative Policy Optimization

  • GRPO samples K responses for each prompt-target pair and computes group-relative advantages by normalizing their rewards.Its clipped objective includes a trust-region parameter and a reference-policy regularizer.Source: Preliminaries · p. 2

Search-Agent Rollouts

  • A search-agent response alternates policy-generated reasoning or search actions with retrieved observations, which condition later actions but are not policy-generated tokens.Only valid parsed search actions count as tool calls; retrieved observations are masked in the actor objective.Source: Preliminaries · p. 2
  • A valid search action sends its query to the retriever, which returns the top-k observations; a final-answer action terminates the response.A complete response records generated segments and retrieved observations in its trajectory.Source: Preliminaries · p. 2

Methodology

ZEST-Search builds search tasks from unlabeled reference questions, then uses grouped solver rollouts to co-evolve task difficulty and search efficiency. Its five-stage process connects target validation and evidence-grounded question generation to role-specific optimization.

Framework Overview

  • ZEST-Search generates tasks from unlabeled reference questions, retrieves target-centered evidence, and uses grouped search rollouts to optimize proposer and solver rewards.Accepted QA pairs are used for GRPO optimization; the proposer is encouraged to create intermediate-difficulty tasks, while the solver favors correct answers with lower relative search cost.Source: Framework Overview · pp. 2–3, Figure 1 · p. 3

Entity Answer Generation

  • The proposer samples a target entity, and deterministic parsing, entity recognition, and answer-side retrieval checks screen candidates before acceptance.The validated target anchors evidence-path construction and becomes the verification target for the generated task.Source: Entity Answer Generation · p. 3

Evidence-Path Guided Question Generation

  • The framework recursively retrieves documents and retains sentences linking entities, then selects a ranked, source-supported path to condition question generation.Paths with repeated entities, discontinuous transitions, or insufficient evidence are discarded; generated questions conceal the target while preserving relational clues.Source: Evidence-Path Guided Question Generation · pp. 3–4

Tool-Aware Rollouts on Generated QA Pairs

  • For each validated task, the solver samples grouped trajectories that stop at a valid final answer or when the search-turn budget is exhausted.Exact-match outcomes characterize task-level accuracy, while search-call counts quantify tool use and inform role-specific rewards.Source: Tool-Aware Rollouts on Generated QA… · p. 4

Asymmetric Adversarial Rewards

  • The proposer reward peaks at 50% solver accuracy, while the task-local solver reward penalizes search use and lets correct, lower-search trajectories earn higher rewards.The intermediate-difficulty reward gives zero to all-correct or all-wrong groups; multiplying the tool reward by correctness prevents incorrect rollouts from benefiting from fewer searches.Source: Asymmetric Adversarial Rewards · p. 4

Experiments

Experiments report gains across general-domain and multi-hop QA, including for search-specialized solvers, and examine proposer diversity, task difficulty, search cost, and evidence-path generation. The setup constructs training tasks online from unlabeled questions.

Experimental Setup

  • Evaluation covers three general-domain and four multi-hop QA benchmarks, reporting normalized EM, macro-average EM, and average successfully parsed search actions per example.Training uses unlabeled NQ training questions; target answers and evidence paths are constructed online.Source: Experimental Setup · pp. 4–5

Main Results

  • ZEST-Search improves search-augmented reasoning across seven benchmarks and benefits solvers across scales and model families, including Search-R1 and ZeroSearch.The main comparison is reported in Table 1; the reported gains cover general-domain and multi-hop QA.Source: Table 1 · p. 5, Main Results · p. 5
  • Smaller and cross-family proposers can provide effective training signals, although task quality varies across proposer checkpoints.Qwen3-4B performs comparably to Qwen2.5-7B, while Qwen2.5-3B-Instruct also produces strong gains.Source: Main Results · p. 5

Ablation and Analysis

  • A moderate tool-cost coefficient reduces search calls with minor accuracy loss, while larger coefficients increasingly suppress retrieval and degrade accuracy.The analysis uses 400 training steps; the objective is to balance accuracy and efficiency rather than minimize retrieval.Source: Figure 2 · p. 6, Ablation and Analysis · pp. 6–7

Main Results

  • Accuracy improves while average search calls fall for most solvers; the exception is Qwen2.5-3B-Base, which uses slightly more calls alongside a substantial accuracy gain.The authors attribute the exception to the weak base model initially underusing search.Source: Main Results · p. 6

Ablation and Analysis

  • The intermediate-difficulty reward produces more mixed solver-outcome groups and fewer all-wrong groups than the monotonic adversarial objective, targeting the solver’s learnable boundary.Mixed groups contain both successful and failed trajectories, providing relative signals for policy optimization.Source: Table 2 · p. 6, Ablation and Analysis · p. 6
  • Evidence-path-guided generation produces more multi-hop questions, but initially has lower validity and greater answer leakage than direct answer-retrieval generation.After proposer training, EPG improves validity and leakage control while further increasing the proportion of multi-hop questions.Source: Table 3 · p. 6, Ablation and Analysis · p. 7
  • The case study traces a generated target, Cinderella, through a source-supported path via Kenneth Branagh, Belfast, and Northern Ireland to form a multi-hop question.The example illustrates generating a verifiable task from an unlabeled reference question rather than transforming that question.Source: Figure 3 · p. 7, Ablation and Analysis · p. 7

Related Work

Prior work has developed retrieval-augmented models, search-using agents, and adaptive proposer–solver training. ZEST-Search differs by bringing source-supported task construction and explicit search-efficiency optimization into that process.

Search-Augmented Language Models

  • Retrieval-augmented language models use external knowledge for knowledge-intensive tasks, while later systems integrate retrieval into reasoning and refine answers using evidence.Search-agent RL has also moved from final-answer rewards toward search-cost modeling, retrieval simulation, process supervision, and step-wise feedback.Source: Related Work · p. 7

Proposer–Solver Training for Search Agents

  • Prior search self-play methods adapt generated-task difficulty using solver feedback, with later work adding structured evidence or finer-grained process signals.Examples include knowledge-graph paths for question generation and waypoint rewards, and source-level contribution scores for retrieved evidence.Source: Related Work · p. 7
  • Unlike methods using fixed answer pools or precomputed graph paths, ZEST-Search generates retrieval-supported targets and source-supported textual paths online, coordinating decoupled proposer and solver policies.Its objectives target intermediate task difficulty and trajectory-level search efficiency.Source: Related Work · p. 7

Conclusion

ZEST-Search trains search agents through heterogeneous proposer–solver co-evolution, constructing tasks online without labeled QA pairs. Its experiments report improved accuracy and tool efficiency, including with smaller and cross-family proposers.

Conclusion

  • ZEST-Search constructs validated tasks online using answer-first generation and source-supported multi-hop evidence paths rather than predefined answer pools or labeled QA pairs.Lightweight non-generative components handle target validation, path construction, and task filtering without additional LLM inference.Source: Conclusion · p. 7
  • Decoupled proposer and solver roles allow lightweight, instruction-tuned, and cross-family proposers to generate complementary tasks around the solver’s evolving capability boundary.Role-specific objectives steer the proposer toward intermediate difficulty and reward correct solver trajectories with lower relative search costs.Source: Conclusion · p. 7
  • Experiments show improved answer accuracy and tool efficiency without labeled search-training data, and analyses support the reward design and task-generation approach.The framework remains effective with smaller and cross-family proposers.Source: Conclusion · p. 7

Appendix A: Implementation details

Appendix A summarizes training configurations and follows Search-R1 for default search-related settings. Appendix B introduces additional analyses of frozen proposers, multi-hop task construction, and existing self-play approaches.

Appendix A: Implementation details

  • Search-R1 provides the default search-related configurations, including the retriever and search protocol.The section covers general model-training and method-specific parameters.Source: Appendix A · p. 10
  • Table 4 is identified as the source for training, generation, and retrieval configurations.Source: Table 4 · p. 10
  • Figure 4 reports training-time test accuracy with a frozen Qwen2.5-3B-Base proposer and solver.Source: Figure 4 · p. 10

Appendix B: Additional Analyses

  • Appendix B presents additional results on frozen proposers, multi-hop question construction, and comparisons with existing self-play approaches.Source: Appendix B · p. 10

B.1 Additional Ablation Study

The ablations examine proposer–solver co-evolution and increased multi-hop task complexity. The reported results favor co-evolution and show larger gains from higher-hop tasks on multi-hop QA than on general QA.

Frozen-Proposer Control

  • Without co-evolution, a fixed proposer can produce limited gains or performance degradation as its tasks fail to track the solver’s evolving capability boundary.The text notes that this constraint is more pronounced for a frozen base model with weaker instruction-following ability, where low-quality tasks may accumulate under lightweight NLP validation.Source: §B.1 · p. 10
  • Co-evolution is effective and necessary for generating effective training tasks, adapting to the solver’s evolving capability, and improving search-agent training.Source: §B.1 · p. 10

Ablation on Multi-Hop Task Complexity

  • The higher-complexity setting raises the maximum target-path length and search-turn budget to four, isolating the effect of longer evidence paths and more demanding supervision.Source: §B.1 · p. 10
  • Higher-hop tasks yield more substantial gains on multi-hop QA than on general QA benchmarks.The study increases the maximum evidence-path length and search turns to four while keeping other training and evaluation configurations unchanged.Source: Table 5 · p. 11, §B.1 · p. 11

B.2 EPG Runtime

EPG accepts 60.4% of generated tasks in the reported analysis and constructs evidence paths without additional LLM-based verification or inference. Evidence-path construction is also faster than target and question generation in the reported runtime breakdown.

Efficiency and Acceptance Analysis of EPG

  • 82.2% of generated target entities pass target validation; 302 questions remain after static QA verification, yielding a 60.4% overall task acceptance rate.Source: §B.2 · p. 11
  • Evidence-path construction takes 59.24 seconds, substantially less than target generation (142.53 seconds) and question generation (111.15 seconds); EPG uses lightweight retrieval and NLP components to validate generated questions.Source: §B.2 · p. 11
  • EPG uses lightweight retrieval and NLP components rather than an LLM judge or additional reasoning calls to validate generated questions.The passage says this avoids extra LLM inference and reduces validation overhead while preserving source-supported evidence for multi-hop question generation.Source: §B.2 · p. 11

B.3 Reward Dynamics

The solver reward rises early and stabilizes, while the proposer reward eventually settles in a positive range. The proposer’s declining reward reflects tasks becoming easier as the solver improves, not degraded proposer performance.

Reward Dynamics

  • The solver reward rises rapidly early in training and then stabilizes at a high level, while the proposer reward first rises and then settles in a positive range.The passage associates these dynamics with progressively maintained correct, tool-efficient solver behavior and continued generation of useful frontier tasks.Source: §B.3 · pp. 11–12
  • A declining proposer reward reflects initially informative questions becoming easier as the solver improves, shifting preferred tasks toward its evolving capability boundary.Because the roles use different reward definitions, their absolute reward values are not directly comparable; the passage also reports stable solver reward despite adaptive task generation.Source: §B.3 · p. 12

B.4 Comparison with Self-Play Methods.

ZEST-Search compares favorably with reported self-play results, though differing task sources, verification, and search protocols prevent a strictly controlled comparison. Its task-generation pipeline uses deterministic validation and retrieval-supported targets.

B.4 Comparison with Self-Play Methods.

  • The default 3-hop setting raises average score from 37.2 to 38.2 versus Dr. Zero, and four hops reaches 39.3, exceeding it on all seven benchmarks.The comparison is indicative rather than fully controlled because task sources, validation mechanisms, and search protocols differ.Source: §B.4 · p. 12

C.2 Retrieval-based Target Verification

  • The pipeline generates a searchable target entity from a reference question, verifies its corpus support, constructs an evidence path, then generates and validates a question.The target is a different entity of a similar semantic category, or an entity or topic anchoring numerical or temporal answers.Source: §C.1 · p. 12, §C.2 · pp. 12–13

C.1 Overview

  • Validation combines retrieval grounding, entity-level consistency, and deterministic rules instead of an additional language-model or NLI-based verifier.The authors say this reduces verification overhead while maintaining reliable control over the generated training distribution.Source: §C.1 · p. 12

C.3 Evidence Path Construction

The evidence-path pipeline builds local, corpus-grounded entity chains to guide question generation, then applies static checks before solver rollouts. Its evidence stage takes less wall-clock time than either LLM-generation stage.

C.3 Evidence Path Construction

  • The evidence graph is a local set of entity associations from retrieved passages, not a complete knowledge graph; its nodes are normalized mentions and edges use co-mention and lexical cues.The graph supplies controllable generation context, and entity normalization stays within the corpus rather than relying on external knowledge bases.Source: §C.3 · p. 13, Entity Extraction and Normalization · p. 13
  • Edge ranking uses deterministic lexical signals, prioritizing explicit relations over weaker co-occurrence patterns and ranking candidates by support and retrieval signals.This avoids an additional learned relation-extraction model.Source: Evidence Edge Construction · p. 13
  • Sampling-based expansion limits path enumeration; the hop budget is an upper bound, so shorter paths are retained when no reliable frontier entity can be expanded.At each step, the highest-ranked candidate is preserved and one additional candidate is sampled; default branching width is two.Source: Path Sampling and Certification · p. 13

C.4 Evidence-path Guided Question Generation

  • The selected entity chain, bridge entities, evidence sentences, and source details condition question generation; multiple evidence steps are encouraged when supported, but shorter questions are allowed.The complete path serves as a controllable generation signal, while evidence consistency is prompted but not separately verified by an entailment model or LLM judge.Source: §C.4 · p. 14

C.5 Static Question Validation

  • Static validation checks question form, non-empty evidence materials, and direct target leakage, but does not establish entailment, answer uniqueness, factual correctness, or multi-hop necessity.The validator rejects a question if a normalized target-answer form appears in its text.Source: §C.5 · p. 14

C.6 Computational Efficiency

  • 59.24 seconds for evidence-path construction over 500 reference questions, versus 142.53 seconds for target generation and validation and 111.15 seconds for question generation and static verification.The evidence construction and validation stages add no LLM inference beyond the two proposer calls.Source: §C.6 · p. 14
  • Static checks precede solver-based evaluation, so candidates violating inexpensive deterministic constraints are removed before solver rollouts are spent on them.Solver evaluation supplies dynamic correctness, difficulty, and tool-use signals only after acceptance.Source: §C.6 · p. 14

Related papers

Loading 2610.39682v1…