acceptodds
Under review as a conference paper at ICLR 2027

Verification as a Budget: Posterior-Separation Scheduling for Self-Evolving Agent Skills

Abstract

Optimizing a natural-language skill document instead of model weights is a low-cost path for adapting frozen LLM-based agents to downstream tasks, and mainstream methods share one outer loop of target-model rollouts, optimizer proposals, validation and accept-or-reject decisions. This paper identifies a structural deficiency in that loop: validation is fixed as a full-scale step. Every candidate is evaluated once on the full validation set and the gate compares that noisy reading against the incumbent's recorded score, a score systematically inflated by selection bias whose raised threshold crowds out genuine late-training gains; rejected candidates cannot be resurrected and their measurements accumulate no evidence. Meanwhile target-model rollouts and optimizer calls, two operations with very different cost structures, are bound at a fixed ratio set by a step counter and insensitive to the current estimation quality. We propose VeriTree, which restructures the outer loop as a skill tree with uncertainty estimates. Each round performs either additional validation or the generation of a new candidate, and the switch is decided in closed loop by a two-arm criterion on posterior separation: validation stops and expansion proceeds once the leading candidate is statistically separated from its strongest competitor, or once separating them would cost more validation than the remaining budget allows. Validation targets are chosen by uncertainty-aware sampling, optimizer calls are subject to data gating, and delivery favors well-evidenced nodes; the whole behavior is controlled by a single parameter set from the task configuration. Across three optimizer–target configurations and five tasks, compared with SkillOpt and GEPA under identical accounting, VeriTree attains comparable or better accuracy, while reducing training cost to 10%–63% of SkillOpt's on every task and under every configuration. The results support the paper's central claim: validation in self-evolving agents should be treated not as a fixed full-scale step but as a scarce budget scheduled by posterior state.

Primary area:
foundation or frontier models, including LLMs
Keywords:
agent skills, skill optimization, prompt optimization, test-time compute allocation, Thompson sampling, tree search, token efficiency, LLM agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_kv95OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of budget allocation during skill self-evolution. It proposes VeriTree, which maintains a posterior state and dynamically decides at each iteration whether to spend additional budget on validating an existing skill candidate or on generating a new skill version. Through comparisons with several representative baselines, the authors report that VeriTree can obtain high-accuracy skills at substantially lower cost.

Critical strengths
  1. Treating verification as a budget is an important research direction, and I strongly agree with this perspective.
  2. VeriTree dynamically chooses between further validating existing candidates and generating new skill versions based on posterior estimates and the remaining budget. I find this adaptive allocation mechanism conceptually interesting.
Critical weaknesses
  1. The current experimental evaluation is insufficient to fully establish the effectiveness and generality of VeriTree. The paper jointly compares accuracy and cost across methods, but VeriTree does not appear to consistently achieve Pareto dominance over the baselines. A more informative evaluation would therefore compare accuracy under a fixed cost budget, or cost required to reach a fixed accuracy level, and ideally report accuracy–cost curves for different methods to characterize their marginal returns as the budget increases. In addition, four of the five evaluated tasks are knowledge-oriented QA tasks, while only one involves a more operational or agentic setting, leaving it unclear whether the method generalizes to broader agent scenarios. The current ablation studies also do not sufficiently explain where the accuracy improvements come from.
  2. The methodological contribution appears relatively incremental and primarily focused on improving efficiency in a specific optimization setting. VeriTree shows a clear relative reduction in optimization cost, but it does not demonstrate a consistent advantage in final task accuracy, and the absolute cost savings in some settings appear modest. As a result, I am not yet convinced that the empirical gains are strong enough to establish a sufficiently substantial contribution. Stronger evidence of generality, larger absolute savings, or a clearer qualitative advantage over existing skill-optimization pipelines would help strengthen the case.
Questions for authors
  1. Given the rapid improvement of foundation-model capabilities, how do the authors view the long-term applicability of skill self-evolution? In particular, do skills optimized by VeriTree transfer effectively to other models, or are they highly specific to the model used during optimization?
  2. Could the authors plot the prompt-token length of the selected skill version over the course of optimization and provide the full text of at least one final optimized skill? This would help clarify whether the gains mainly come from more precise and structured rules, or from accumulating increasingly detailed descriptions of corner cases. This question is also related to my concern about understanding the source of the accuracy gains.
  3. VeriTree appears to provide a substantial cost advantage, but in Configuration 1 on the SSB task, it reduces cost by roughly 90% while achieving an accuracy about 10 percentage points lower than SkillOpt. If the budget allocated to VeriTree is increased, can it continue improving and eventually approach or match the accuracy achieved by SkillOpt?
3 comments

We thank the reviewer for all concrete suggestions.

W1-a: No consistent Pareto dominance; accuracy at fixed cost, cost at fixed accuracy, and accuracy–cost curves.

First, from the existing Table 1: since VeriTree has the lowest cost in all 15 cells, it is Pareto non-dominated in 15 of 15 cells. It strictly dominates (higher or equal accuracy at lower cost) SkillOpt in 9 of 15 cells and GEPA in 8 of 15 cells, and no baseline dominates VeriTree in any cell.

Second, following the reviewer's suggestion, we added:

  • Accuracy at fixed cost: at VeriTree's cost, VeriTree is the most accurate method on 3 of 5 tasks in Config. 1 and within 1.2 pp on the other two.
  • Cost at fixed accuracy: on Oly (Config. 1), VeriTree reaches SkillOpt's final accuracy at 12.1 RMB, i.e., 17% of SkillOpt's 72.52 RMB. On SSB (Config. 1), where SkillOpt is strongest, VeriTree reaches SkillOpt's 0.5857 at about 20.1 RMB, i.e., 85% of SkillOpt's cost.

W1-b: Four of the five tasks are knowledge QA; generality to agentic settings.

We added two multi-step agentic tasks under Config. 2 (target model Qwen3.6-35B-A3B): ALFWorld (embodied text navigation and manipulation) and τ2\tau^2-bench retail (multi-turn tool use with a simulated user). The task-success signal is binary, so VeriTree's Beta posterior applies unchanged.

MethodALFWorld success (Δ)Cost (RMB)τ2\tau^2-retail pass^1 (Δ)Cost (RMB)
S0S_00.612–0.482–
SkillOpt0.701 (+8.9)186.40.539 (+5.7)212.5
GEPA0.687 (+7.5)92.30.531 (+4.9)104.8
VeriTree0.716 (+10.4)58.70.548 (+6.6)71.2

Agentic rollouts are long and expensive, so the evaluation budget matters even more. VeriTree's relative cost (31% and 34% of SkillOpt's) is in line with the main results.

W1-c: The ablations do not explain where the accuracy comes from.

Table R1 in the General Response decomposes the gain on the same tree and budget: retaining versions contributes +1.1 to +3.8 pp over the chain, the posterior-separation switching rule adds a further +0.5 to +1.8 pp over the best hand-tuned fixed ratio, and both arms are necessary.

W2: Incremental contribution; no consistent accuracy advantage; limited absolute savings.

  • Accuracy. Across the 15 cells of Table 1, VeriTree has the highest average gain over S0S_0 (+6.36 pp vs. +5.85 pp for GEPA and +5.41 pp for SkillOpt), has no negative cell (unlike SkillOpt, which falls 5.05 pp below S0S_0 on GPQA in Config. 1), and has the lowest seed variance (Table R2). We view its main qualitative advantage as reliability: the delivered node is backed by accumulated evidence (e.g., 224 questions on Oly, Table 2) rather than by a single noisy reading.
  • Absolute savings. Per-run savings are bounded by the task size, but they accumulate. On the five tasks of Config. 2 alone, SkillOpt costs 1284.8 RMB and 180.8M tokens, whereas VeriTree costs 498.2 RMB and 77.5M tokens, a saving of 786.7 RMB (61%) for a single sweep. In practice, skills are re-optimized per task, per target model and per model update, and the saving grows with rollout length.
  • Scope. The scheduler is orthogonal to the proposer and applies to any outer loop of the form rollout–proposal–validation; we will make this framing explicit.

Q1: Long-term value of skill self-evolution; do skills transfer across models?

As base models improve, generic gains on high-baseline tasks shrink, but skills increasingly encode what models cannot know a priori: tool conventions, organization-specific procedures and recurring failure modes. Moreover, stronger target models make each rollout more expensive, which makes budget-aware verification more relevant, not less. We applied skills optimized in Config. 2 (target Qwen3.6-35B-A3B) zero-shot to the two other targets; Δ is relative to each target's own S0S_0.

Source → targetMethodOly ΔSQA ΔGPQA Δ
Qwen3.6-35B → Qwen3.5-4BSkillOpt+1.72+6.12−0.51
Qwen3.6-35B → Qwen3.5-4BVeriTree+2.34+7.86+1.01
Qwen3.6-35B → MiMo-v2.5SkillOpt+1.25+5.14−1.52
Qwen3.6-35B → MiMo-v2.5VeriTree+1.88+5.93+0.51

Transferred VeriTree skills retain roughly 60–80% of the in-model gain and transfer at least as well as SkillOpt's skills.

Q2: SSB in Config. 1 — can VeriTree approach SkillOpt with a larger budget?

Yes. SSB has a pool of only 120 questions and T=12T=12 rounds, so the default budget is very small. We increased the number of epochs EE (δ\delta is unchanged, since Beff=min⁡(UE,2U)B_{\mathrm{eff}} = \min(UE, 2U) is already capped at 2U2U):

VeriTree budgetRounds TTTest acc.Cost (RMB)
1× (E=4E=4, paper)120.48212.72
2× (E=8E=8)240.53575.31
4× (E=16E=16)480.571410.90
8× (E=32E=32)960.589321.62
SkillOpt (paper)–0.585723.71

Accuracy increases monotonically with the budget and matches SkillOpt at a slightly lower cost. We also note that SkillOpt's +23.93 pp gain in this cell has a high seed variance (0.5643 ± 0.0255, Table R2) and does not recur in Config. 2 (+1.79 pp).

We thank the reviewer again for the thoughtful suggestions, which have substantially strengthened our evaluation. We hope the new matched-budget analyses, agentic tasks and transfer results address the soundness concerns, and we would be grateful if the reviewer would reconsider the score.

Thank you for the additional experiments and for sharing the results. As a follow-up to Q2 in my original review, could you plot the prompt token count of the selected skill at each optimization iteration and share the full text of one final optimized skill?

Reviewer_5gkQOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes VeriTree, a budget-aware framework for self-evolving LLM agent skills. It maintains skill candidates in a tree with Beta posteriors and dynamically decides whether to validate existing candidates or generate new ones based on posterior separation and the remaining budget. Experiments across five tasks and three model configurations show competitive accuracy with substantially lower training costs than SkillOpt and GEPA.

Critical strengths
  1. Practical motivation. The paper highlights important limitations of noisy validation scores and fixed evaluation schedules. The analysis of validation noise and selection bias provides a useful motivation for the proposed approach.

  2. Promising efficiency. VeriTree achieves competitive accuracy with lower training costs across all evaluated settings. The paper also reports token-level costs, making the efficiency comparison more informative.

Critical weaknesses
  1. Limited novelty and insufficient ablations. Several components, including Thompson sampling, best-arm identification, and uncertainty-based selection, are well established. Related work on budget-aware prompt optimization, such as ProTeGi and TRIPLE, is not sufficiently discussed. Moreover, the paper lacks comparisons with simpler adaptive evaluation strategies, making it difficult to isolate the contribution of the proposed scheduling criterion.

  2. Insufficient experimental validation. The experiments use only one training seed, without reporting variance across independent optimization runs. In addition, the methods use different data splits, and accuracy–cost comparisons under matched budgets are missing. These limitations make it difficult to establish the robustness and fairness of the reported improvements.

Questions for authors
  1. How does VeriTree compare with simpler scheduling strategies, such as fixed schedules or Successive Halving, under the same computational budget?

  2. Are the accuracy and cost improvements consistent across multiple training seeds?

  3. Can the authors clarify the data splits and budget settings for each baseline, and whether the results hold under matched conditions?

  4. Can the authors confirm that the GPQA training pool does not overlap with the GPQA-Diamond test set?

Reviewer_9xBNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In the outer loop of agent skill optimization, running a full validation after every revision is expensive, and a single noisy score can mislead the accept/reject gate. VeriTree keeps different skill versions in a tree, maintains a Beta posterior estimate for each version, and updates them incrementally. A two-arm criterion based on posterior separation and remaining budget decides each round whether to continue validating or to generate a new candidate. The paper compares VeriTree with SkillOpt and GEPA on 5 tasks and 3 model configurations, reporting lower training cost across all settings.

Critical strengths

S1. The repeated evaluation of the same skill makes the noise problem concrete and motivates the need to rethink how validation budget is spent.

s2. VeriTree retain all skill versions and allows follow-up validation, so candidates that scored low early on still have a chance to be re-evaluated and selected.

S3. Experiments cover 5 tasks and 3 model configurations. VeriTree is cheaper than both baselines.

Critical weaknesses

C1. The method is primarily composed of existing techniques: Beta posterior estimation, Thompson sampling, and lower-quantile selection. The switching rule between validation and expansion, which the authors highlight as the core contribution, is only evaluated through a parameter sweep over delta. There is no comparison against a fixed-ratio schedule, nor an ablation that removes each of the two triggering conditions separately.

C2. The paper argues that existing methods incorrectly reject candidates that actually improve skill quality in later training stages. But the main evidence is that scores fluctuate when the same skill is evaluated repeatedly. It would be better if authors can show some rejected candidates. VeriTree retains these candidates, yet the paper does not demonstrate whether follow-up validation ever recovered an initially underestimated skill, or how much such recoveries contributed to the final result.

Questions for authors

Q1: How much of the improvement comes from retaining multiple skill versions, and how much from the posterior-separation switching rule? If validation and expansion budgets were allocated at a fixed ratio on the same tree, how much worse would the results be?

Q2: Did the delivered node ever rank low early on and recover through later validation? If it led from the start, the comeback mechanism was not exercised in these experiments.

Q3: The final skill is selected by the 1% posterior quantile, but the decision to stop validating is based on the probability of being the best skill. If these two criteria point to different nodes, could the switch to expansion happen too early?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.