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 ZEST-Search, a zero-label and tool-efficient framework for search-agent training via heterogeneous co-evolution. Starting from unlabeled reference questions, 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, 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 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.
Figures & tables
Figure 1: Overview of ZEST-Search . From left to right, an unlabeled reference question provides a semantic template for target-entity generation; retrieved evidence is organized into a source-supported path for generating a new question; and a heterogeneous solver produces grouped search rollouts that yield role-specific rewards for proposer–solver co-evolution.
GeneralQA
Multi-HopQA
Proposer / Solver
Method
NQ
TriviaQA
PopQA
HotpotQA
2Wiki
MuSiQue
Bamboogle
Avg (↑)
Queries (↓)
Zero-Label Training from Base Models
Qwen2.5-3B-Instruct /
Solver Base
16.7
30.7
17.8
12.4
7.2
2.3
6.4
13.4
0.85
Qwen2.5-3B-Base
Ours
36.0
57.0
38.2
26.0
25.4
5.3
7.2
27.9 (+14.5)
1.01 ( +0.16 )
Qwen2.5-7B-Base /
Solver Base
25.8
43.3
28.3
15.8
9.2
6.4
24.1
21.8
1.59
Qwen2.5-7B-Base
Ours
37.1
61.9
40.3
34.7
31.8
11.7
32.0
35.6 (+13.8)
1.17 (-0.42)
Table 1: Main experimental results. Results above the base model are in bold, while those below it are underlined.
Figure 2: Training and efficiency analyses. (a) The training dynamics of proposers with different scales. (b) Question-generation quality during the training process. (c) Accuracy–efficiency trade-off under different tool-cost coefficients.
Reward Type
4Acc[1−Acc]
1−Acc
Valid QA Distribution (%)
Mixed Questions ↑
21.63
12.81
All-Wrong Questions ↓
43.80
83.95
All-Right Questions
34.57
3.24
Performance
Avg. Accuracy ↑
37.59
36.00
Table 2: Effect of proposer rewards on generated task difficulty and solver performance.
Metric
Answer Retrieval
EPG
EPG + RL
Question Quality (%)
Answer leakage ↓
9.6
21.2
2.0
Valid question ↑
29.2
27.6
42.4
Hop Distribution among Valid Questions (%)
1-hop
95.2
71.7
54.7
2-hop
4.8
26.1
37.7
Table 3: Comparison of question quality under answer-retrieval and evidence-path guided (EPG) generation.
Figure 3: A case study of evidence-path guided generation.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Parameter
Value
(A) General model-training parameters
Actor learning rate
3×10−7
Proposer KL
0.005
Solver KL
0.001
Train batch
128
Rollout nums
5
Appendix
Table 4: Training, generation, and retrieval configurations.
GeneralQA
Multi-HopQA
Proposer / Solver
Method
NQ
TriviaQA
PopQA
HotpotQA
2Wiki
MuSiQue
Bamboogle
Avg (↑)
Queries (↓)
Training Solvers with Different Proposer Configurations
Qwen2.5-7B-Instruct /
Solver Base
25.8
43.3
28.3
15.8
9.2
6.4
24.1
21.8
1.59
Qwen2.5-7B-Base
Ours (3-Hops)
40.2
64.5
43.8
36.3
35.4
12.0
35.2
38.2 (+16.4)
1.16 (-0.43)
Qwen2.5-7B-Instruct/
Solver Base
25.8
43.3
28.3
15.8
9.2
6.4
24.1
21.8
1.59
Qwen2.5-7B-Base
Frozen
40.5
61.5
42.6
32.8
29.4
9.1
20.0
33.7 (+11.9)
1.48 (-0.11)
Appendix
Table 5: Additional experiment results. Parenthesized numbers are training steps. Results above the base model are in bold. The results below the base model or below our method are in gray and underlined.
Figure 4: Training-time test accuracy of ZEST-Search with a frozen Qwen2.5-3B-Base proposer and a Qwen2.5-3B-Base solver
Stage
Accepted
Rate (%)
Target format and entity filtering
486/500
97.2
Retrieval-support verification
411/486
84.6
Overall target validation
411/500
82.2
Evidence-path construction
411/411
100.0 *
Static QA verification
302/411
73.5
Final task acceptance
302/500
60.4
Appendix
Table 6: Acceptance rates across the EPG filtering stages. * Path construction is evaluated only on targets that pass retrieval-support verification.
Stage
Total (s)
Per Task (s)
Target generation and validation
142.53
0.472
Evidence-path construction
59.24
0.196
Question generation and static verification
111.15
0.368
Full pipeline
312.92
1.036
Appendix
Table 7: Runtime breakdown of EPG over 500 reference questions. Per-task runtime is amortized over 302 accepted tasks with a generation batch size of 64.
Figure 5: Training reward dynamics of the Qwen2.5-7B-Instruct proposer and Qwen2.5-7B-Base solver.
Criterion
Requirement
Endpoint
The final node corresponds to the target answer a⋆ .
Continuity
Adjacent edges have consistent entity endpoints.
Acyclicity
No entity identifier is repeated within a path.
Evidence grounding
Each supporting sentence occurs verbatim in its source document.
Entity support
Each evidence sentence contains both edge endpoints.
Relation validity
Each edge satisfies the specified lexical relation constraints.