Beyond the Capability Boundary: Zeroth-Order Optimization for Self-Evolving LLM Agents

Self-evolving methods improve the capabilities of LLM agents by sampling trajectories from the underlying LLMs and learning from these trajectories. However, these methods struggle to learn beyond the inherent capability boundary of the agents, since the agents cannot sample correct trajectories on difficult examples for further improvements.

The paper provides a formal analysis of this limitation. The gradient of the self-evolution objective decomposes into two parts: a fixed-trajectory gradient and a trajectory-distribution gradient. Given a fixed failed trajectory, a conventional fixed-trajectory first-order update only computes the gradient of the answer loss with respect to the existing failed context, which increases the likelihood of the reference answer under the existing failed context but does not account for how changing θ affects subsequent reasoning decisions, query formulation, tool selection, or environment interaction. For reinforcement learning methods, when all sampled trajectories fail and receive the same correctness reward, the reward equals the baseline, resulting in zero gradient. The paper concludes that existing self-evolving methods restrict the generated trajectories to the model's current capability boundary.

The paper proposes a zeroth-order self-evolution framework that enables agents to learn beyond their capability boundary without annotated trajectories. For each difficult instance, the method attaches instance-specific LoRA modules and optimizes them using zeroth-order estimation. The approach works as follows:

1. Perturbation: Randomly perturb the LoRA parameters, where the perturbed parameters are computed as θ p = θ + (B + σϵ B)(A + σϵ A), with σ controlling the perturbation scale and ϵ being random perturbations.

2. Trajectory sampling: The perturbed policy interacts with the tool environment and generates complete trajectories.

3. Loss computation: Compute final-answer losses under both the original and perturbed parameters.

4. Gradient estimation: Use the loss differences to construct gradient estimates for updating the LoRA modules: ĝ(A) = (1/BK) Σ (l+ i,k − l0 i)/σ · ϵ A i,k, and similarly for B.

5. Self-evolution loop: The agent equipped with the optimized LoRA module generates successful trajectories, which then serve as high-quality data for subsequent supervised fine-tuning (SFT) to push the agent beyond its capability boundary, forming a closed self-evolution loop.

Since this process only relies on answers and requires no annotated trajectories, it enables optimization without process supervision.

To address the challenge that agentic trajectory sampling is highly expensive, the paper designs a parallel perturbation inference mechanism. Since different perturbation branches share the same backbone computation, the expensive backbone output only needs to be computed once, while multiple lightweight LoRA perturbations can be evaluated in parallel. The model output for the k-th perturbation is written as h k = θx + (B + ϵ B k)(A + ϵ A k)x. The backbone computation θx is computed once and shared across all perturbation branches, while the LoRA perturbation terms are computed in parallel. This significantly accelerates zeroth-order optimization with limited extra memory cost.

The paper introduces an adaptive lookup mechanism that caches recent tool-call results and adaptively uses exact or similarity-based matching according to query type. For search, the lookup uses semantic query matching to handle surface-level variations. For visit, it uses stricter matching based on the URL and visit goal. Matched requests are served from the lookup pool, while unmatched requests are executed externally and registered for future reuse. This reduces redundant external interactions without changing the agent rollout format.

To address the challenge that direct final-answer rewards are often noisy and sparse, the paper introduces an answer perplexity loss as a process-level surrogate signal derived only from query and answer pairs. After the model generates a reasoning trajectory, the method conditions on the trajectory to compute the negative log-likelihood of the reference answer: l ans(θ; q, τ, y) = −(1/M) Σ log π θ(y j q, τ, y<j). The loss is computed only on ground-truth answer tokens, not supervising the generated reasoning, actions, or observations. Compared with sparse final-answer rewards, this loss provides smoother and more discriminative feedback for different trajectories, improving optimization stability. A lower loss means that the current trajectory makes the reference answer less surprising to the model, so even an incorrect rollout can still receive useful credit if it retrieves evidence that increases the likelihood of the ground-truth answer.

The method is evaluated on two deep research benchmarks: GAIA and WebWalkerQA. Training data consists of 304 filtered high-quality QA pairs from the open-source WebShaper data (starting from 500 QA pairs). The main model backbones used are Qwen-3-4B and Qwen-3-8B. All controlled methods use the same backbone family and the same system configuration, including the search API, webpage parser, decoding setting, and tool budget. The method is compared with ReAct under controlled settings and with existing deep-research agents including Search-o1, WebThinker, WebDancer, SimpleDeepSearcher, WebSailor, GRPO, and ARPO.

The controlled evaluation shows that on GAIA with Qwen-3-4B, the ReAct baseline achieves 19.6% average accuracy while the proposed method (Ours-SFT) achieves 28.3%. With Qwen-3-8B, ReAct achieves 23.3% while Ours-SFT achieves 47.5%. On WebWalkerQA with Qwen-3-4B, ReAct achieves 19.5% while Ours-SFT achieves 28.2%. With Qwen-3-8B, ReAct achieves 15.5% while Ours-SFT achieves 34.8%.

The paper notes that compared deep-research agents rely on more large-scale models (e.g., GPT) to generate trajectories, making them easier to obtain strong results than self-evolution agents. Despite this disadvantage, the proposed method still outperforms these agents.

The paper compares three loss functions: BERT-based semantic loss, LLM-as-a-Judge loss, and the proposed answer perplexity loss. On easy examples, all three losses decrease during zeroth-order optimization, but the proposed loss achieves a lower final loss value and more stable optimization. On difficult samples, both the LLM-as-a-Judge loss and the BERT-based loss fail to decrease, whereas the proposed loss still converges normally with stable optimization dynamics.

Among the 304 training examples, the baseline model correctly answers only 67 examples under Pass@1 (22.0% success rate). After training with the proposed method, the optimized agent correctly answers 164 examples (53.9% success rate), yielding an improvement of 31.9%. Training on trajectories sampled from the initial model improves over the baseline agent, but the proposed method significantly outperforms both, demonstrating that the method helps sample high-quality trajectories.

The paper evaluates the number of perturbation directions K, perturbation scale σ, LoRA rank r, and learning rate η on 50 difficult examples. The number of successful examples changes only slightly over most tested settings, suggesting that the trajectory-discovery results are not narrowly tuned to a single hyperparameter setting.

The two-sided estimator solves 24 examples and the one-sided estimator solves 23 under the same four-rollout budget per round. Since their performance is comparable, the paper uses the one-sided estimator in the main experiments because it supports more perturbation directions with a shared baseline rollout.

On 50 difficult examples, the fixed-trajectory first-order baseline improves only one additional example over direct sampling (7/50), while RL solves 16 examples, and the proposed method solves 23 examples. The paper also reports that fixed-trajectory FO requires 21–24 GB of GPU memory and 2.5–3.5 hours of wall-clock time, whereas the ZO implementation requires 12–15 GB and 1.7–2.4 hours.

Under matched complete-rollout budgets, the proposed method achieves the highest success rate for every evaluated budget compared to initial-policy sampling, random LoRA perturbation, and answer-conditioned trajectory search. The advantage becomes larger as the budget increases, indicating that iterative loss-guided updates are more effective than additional sampling or unguided perturbation.

The proposed method obtains the best result at every sampling budget (Pass@1 through Pass@8). When matching the full rollout budget of zeroth-order optimization with N total = 45 samples from the unchanged initial policy, the initial policy solves 102 examples while the proposed method solves 194. Among the 97 examples newly solved, only 35 (36.1%) can be recovered by Best-of-N total sampling from the initial policy. The initial-policy result already plateaus at Pass@8, showing that additional sampling alone does not account for the newly discovered trajectories.

For 50 difficult examples, the paper records LoRA parameters and answer loss at every optimization round and projects checkpoints onto a shared PCA basis. On a representative example, the proposed method's trajectory moves along a consistent direction while the answer loss decreases from 4.333 to 0.024, whereas the random baseline ends with a higher loss than its initial value. Across all 50 examples, the proposed method has higher consecutive-direction cosine similarity (0.85 vs. 0.02), higher trajectory efficiency (0.64 vs. 0.27), larger loss decrease (74.8% vs. 13.4%), and more successful examples (23 vs. 5).

On 56 GAIA questions that do not require information retrieval, the initial policy solves 5 examples, the RL baseline solves 11, and the proposed method solves 16 (8.93%, 19.64%, and 28.57% respectively). On 68 examples where the gold answer does not appear verbatim in any retrieved observation, the initial policy solves 7 examples while the proposed method solves 21. On BrowseComp-en and BrowseComp-zh without benchmark-specific zeroth-order trajectory discovery, the proposed method improves over both the initial policy and RL. Results remain consistent across five independent random seeds.

Parallel perturbation inference reduces computational time: with K=2, sequential estimation takes 328s while parallel takes 232s (29.3% reduction); with K=4, sequential takes 656s while parallel takes 305s (53.5% reduction). The adaptive lookup mechanism saves an estimated 408s to 1290s depending on the number of perturbations and optimization rounds, by caching search and visit results.

The paper presents representative trajectories showing that the baseline agent often fails due to wrong reasoning and tool calls, while the optimized agent makes more purposeful tool calls, reformulates insufficient queries, and grounds its final answer more explicitly in retrieved evidence. For example, in a case about shared model type in Kashyap's and Fader's customer-retention studies, the baseline agent relies on prior belief and selects Markov model too early, while the optimized agent treats beta geometric as the key candidate from retrieved evidence, verifies it, and answers correctly.

The paper presents a zeroth-order optimization method for self-evolving LLM agents that enables agents to learn beyond their capability boundaries by perturbing LLM parameters to fit difficult examples. The method computes losses under both perturbed and original parameters, uses loss differences to estimate gradients, and updates parameters accordingly. The updated LLM agent is then used to sample trajectories for supervised fine-tuning, forming a closed self-evolution loop. The introduced adaptive lookup mechanism and parallel perturbation inference mechanism reduce time cost, while the answer perplexity loss provides smooth and stable loss values for zeroth-order gradient estimation. Experiments on multiple deep research benchmarks demonstrate that the method obtains substantially more successful trajectories and consistently outperforms strong baselines, breaking through the inherent capability boundary of the agent itself.

Improvements to AI systems:

1. Beyond-capability self-evolution: AI systems can now iteratively improve themselves on tasks they currently fail, without needing labeled trajectories or human demonstrations. The system can discover successful strategies by perturbing its own parameters, sampling diverse trajectories, and using zeroth-order gradient estimates to guide exploration—enabling it to solve problems that were previously outside its ability distribution.

2. Efficient zeroth-order optimization for agentic tasks: The system can optimize its behavior using only final-answer correctness signals (no process supervision), with a parallel perturbation inference mechanism that shares backbone computation across multiple perturbed LoRA branches. This reduces GPU memory (12–15 GB vs 21–24 GB) and wall-clock time (1.7–2.4 h vs 2.5–3.5 h) compared to first-order methods, making self-improvement feasible on commodity hardware.

3. Robust reward surrogate via answer perplexity: Instead of sparse binary rewards, the system uses a dense, smooth loss computed as the negative log-likelihood of the ground-truth answer tokens conditioned on the generated trajectory. This provides discriminative feedback even for incorrect rollouts—if a trajectory retrieves relevant evidence that makes the answer more likely, it still receives useful credit, stabilizing optimization on hard examples where other losses fail to converge.

4. Adaptive tool-call caching: The system reduces redundant external interactions (search/visit calls) by caching recent results and using query-type-aware matching—semantic similarity for search queries, stricter URL+goal matching for visits. This cuts runtime by 408–1290 seconds per optimization round, enabling more iterations within a fixed budget.

5. Closed-loop self-evolution with SFT: After zeroth-order optimization discovers successful trajectories on difficult instances, the system uses these trajectories as high-quality supervised fine-tuning data. This creates a positive feedback loop: the improved agent can then sample even better trajectories, pushing the capability boundary further with each cycle.

6. Memory-efficient fine-tuning: By attaching instance-specific LoRA modules during exploration and discarding them after trajectory collection, the system avoids storing large gradient histories or full model copies, keeping memory overhead low while still enabling effective parameter updates.

What the improved AI system can do:

• Solve deep research tasks (e.g., GAIA, WebWalkerQA) that require multi-step reasoning, web search, and tool use, improving from 19.6% to 28.3% (4B) and from 23.3% to 47.5% (8B) on GAIA—a 2× improvement over strong ReAct baselines, and outperforming prior deep-research agents that rely on larger GPT-based teachers.

• Break through its own capability ceiling: On 304 training QA pairs, the system improves from 67 to 164 correctly solved examples (22% → 53.9% success rate), including 97 examples that were previously unsolvable even with 45 sampled rollouts from the initial policy—demonstrating that it learns genuinely new strategies, not just better sampling.

• Generalize to unseen benchmarks (BrowseComp-en/zh) without any benchmark-specific trajectory discovery, showing that the learned self-evolution loop transfers to new task distributions.

• Operate efficiently in real-time: With parallel perturbation inference and adaptive lookup, the system can perform multiple optimization rounds within minutes, making it practical for interactive research assistants, automated data curation, and continual learning in production environments.

• Provide stable optimization on hard examples: Unlike LLM-as-a-judge or BERT-based losses that fail to converge on difficult queries, the answer perplexity loss decreases consistently (from 4.33 to 0.02 on a representative case), enabling reliable improvement even when initial success rate is near zero.