PaperlayerView exact revision on arXiv

Source-linked AI summary

VeriEvolve: Evaluator-First Evolution for Tool-Using Agents

Yueshen Li, Kamer Ali Yuksel, Gokhan Tur, Dilek Hakkani-Tür, João Pedro Maia

arXiv:2610.29005v1cs.SEcs.AIcs.CL

TL;DR

Realistic stateful tasks lack reliable executable fitness signals for checking the resulting environment state. VeriEvolve synthesizes evaluators before workflow search and refines them from strong–weak execution-state differences. On MCPMark Filesystem tasks, evaluators agreed on most held-out states and guided externally measured success gains, but the approach relies on external calibration.

  • Problem

    Realistic stateful tool-use tasks lack scalable deterministic evaluators for checking instruction-implied properties of final environment states.

    Source: §1 · p. 1

  • Method

    VeriEvolve builds instruction-grounded challenge states and executable evaluators before search, freezes evaluators during workflow evolution, and revises them from strong–weak final-state differences.

    Source: §1 · p. 2

  • Results

    On MCPMark Filesystem tasks, evaluator agreement was 141/141 on generated suites and 113/122 on held-out states; externally verified success rose from 6/30 to 18/30 for GLM-5.2 and from 27/30 to 30/30 for Claude.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Executable evaluators can guide workflow search and be repaired from strong–weak state differences when success is observable and an external verifier is available for calibration.

    Source: §8 · p. 8

    The experiments establish feasibility under external calibration, not that evaluators are reliable or refinement can run autonomously without an independent verifier.

    Source: Limitations · p. 9

Abstract

from arXiv · show

A central obstacle to self-improving agents is the absence of a reliable fitness signal for realistic stateful tasks. We introduce \textsc{VeriEvolve}, an evaluator-first evolution framework that constructs this missing evaluation layer before optimizing the agent. From task instruction, VeriEvolve synthesizes instruction-grounded challenge states and an executable evaluator that checks them. During each round of workflow evolution, the evaluator is frozen and serves as the fitness signal. Between rounds, VeriEvolve revises the evaluator by converting the end states of strong and weak runs into a pair of counterfactual test cases. Across all 30 MCPMark Filesystem tasks, VeriEvolve constructs 30 evaluators with 141 challenge states, achieving 141/141 agreement on the generated suites and 113/122 agreement on held-out states produced by executor agents. Evaluator-guided evolution increases externally verified success from 6/30 to 18/30 for GLM-5.2 and from 27/30 to 30/30 for Claude; refinement removes all three false positives that the weak executor exposes. Cross-environment studies on PostgreSQL, Playwright, Notion, and GitHub further expose complementary limits from observability, state representation, and search/execution capacity. These results show that executable evaluators can be synthesized and used to guide search when task success is observable and an external verifier is available for calibration.

1 Introduction

Realistic stateful tool-use tasks lack the executable fitness signals needed to assess final environment states, while hand-authored verification is costly and semantic judging cannot establish every required property. VeriEvolve builds evaluators before evolving workflows, then uses strong–weak execution-state differences to refine them; its MCPMark study reports evaluator agreement and externally verified workflow gains.

1 Introduction

  • Stateful workflows require checking final-state properties such as artifact existence, content, hierarchy, consistency, preservation, and absence of unintended side effects.Hand-authored scripts are costly, while semantic judges cannot reliably establish that every required property holds.Source: §1 · p. 1
  • The study frames evaluator construction as a feasibility question under observable task success and an independent benchmark verifier used outside search for calibration and measurement.The goal is not perfect reproduction of an expert verifier in one step, but useful initial optimization and later refinement.Source: §1 · pp. 1–2
  • VeriEvolve constructs instruction-grounded challenge states and executable evaluators before workflow search, freezes the evaluator during search, and revises it using strong–weak final-state differences.The external benchmark verifier is kept outside the search loop.Source: §1 · p. 2
  • Across 30 MCPMark Filesystem tasks, evaluators agreed with the external verifier on 141/141 generated challenge states and 113/122 held-out agent-produced states.Success rose from 6/30 to 18/30 for GLM-5.2 and from 27/30 to 30/30 for Claude; refinement eliminated all three exposed false positives.Source: §1 · p. 2
  • Cross-environment studies on PostgreSQL, Playwright, Notion, and GitHub expose complementary limits from observability, state representation, and search or execution capacity.The abstract reports release of framework code and artifacts upon publication, including challenge states, evaluators, labeled states, and evolved workflows.Source: §1 · p. 2

2 Related Work

Prior self-improving systems often use supplied objectives, benchmarks, or trusted verifiers, while evaluation of stateful tool use checks resulting artifacts or environment states. VeriEvolve instead synthesizes and revises evaluators for final environment states from task instructions and initial states.

2 Related Work

  • FunSearch and AlphaEvolve optimize automatically computed objectives, while Darwin, Huxley Gödel Machines, and HyperAgents use supplied benchmarks or utilities (Novikov et al., 2025; Zhang et al., 2026b).Related work also includes co-evolving or changing evaluation criteria, but retains external validation (Iacob et al., 2026; Li et al., 2026; Wang et al., 2026a).Source: §2 · pp. 2–3
  • Stateful-agent benchmarks programmatically check artifacts or environment state because semantic LLM judgments cannot establish every required state invariant (Jimenez et al., 2024; Yao et al., 2025; Xie et al., 2024; El Hattami et al., 2025; Wu et al., 2026).MCPMark reports several hours of expert effort per task and verifier (Wu et al., 2026).Source: §2 · p. 3
  • VeriEvolve differs by synthesizing evaluators of final environment states from task instructions and initial states, then revising them with agent-produced states.Prior test-generation work uses source code, formal specifications, or agent traces as inputs (Wang et al., 2025; Cunha and Macedo, 2026; Kohl et al., 2026).Source: §2 · p. 3

3 Problem Setting

The paper formalizes stateful tool-use tasks around an instruction, initial environment state, and read-only observation interface. Evaluators score observable final states, while refinement uses strong and weak execution states to add instruction-grounded distinctions.

3 Problem Setting

  • A stateful tool-use task is τ = (x, s0, O): an instruction, initial environment state, and read-only interface exposing state available for evaluation.Correctness depends on instruction-implied constraints such as artifact existence, content, structure, consistency, and preservation.Source: §3 · p. 3
  • An evaluator deterministically maps observations to a verdict, partial score, and check-level evidence, and workflow search maximizes that score while the evaluator is fixed.Internal convergence occurs when the evaluator accepts the workflow's final state.Source: §3 · p. 3
  • Refinement compares a strong-executor reference state with an accepted weak-executor state, turns observable differences into labeled challenge states, and revises the evaluator.The reference is a high-confidence valid execution, not a ground-truth oracle; revisions add only instruction-grounded distinctions and preserve earlier verdicts.Source: §3 · p. 3

4 VeriEvolve Framework

VeriEvolve separates evaluator construction, workflow search under a frozen evaluator, and execution-state refinement between search runs. Its refinement loop creates paired counterfactual cases from instruction-grounded differences and promotes only regression-checked revisions.

4 VeriEvolve Framework

  • The framework separates model-backed proposals from deterministic execution, gating, state-difference computation, and artifact versioning; evaluators remain frozen within each workflow-search run.Figure 1 depicts these roles and persisted artifacts across the three stages.Source: §4 · p. 3, Figure 1 · p. 4

4.1 Evaluator Construction

  • The Test-Suite Generator derives positive, clean-negative, and adversarial cases from the instruction and observable initial state, and adapters materialize labeled executable states.The Verifier Evolver tests candidates on those states and freezes a candidate after it passes the construction gate.Source: §4.1 · pp. 3–4

4.2 Workflow Evolution under Frozen Evaluation

  • Five workflow nodes handle task understanding, planning, ReAct execution, artifact inspection, and post-processing, each retaining alternative behaviors for candidate paths.The frozen evaluator provides partial fitness and check-level evidence; alternatives are appended and recombined rather than overwritten.Source: §4.2 · p. 4

4.3 Execution-State Refinement

  • Refinement clusters observable strong–weak state differences and selects only instruction-grounded ones, then creates paired counterfactual states whose targeted difference is added or removed.Label-consistency and coverage gates reject invalid pairs; revisions are promoted only after regression checks preserve prior verdicts, accept the reference, and reject prior false positives.Source: §4.3 · pp. 4–5
  • Further refinement requires a novel actionable difference, and the experiments use external verdicts to admit evaluators and trigger false-positive refinement; verifier-free triggering and reference selection are not evaluated.Search or refinement budgets can also end the process.Source: §4.3 · p. 5

5 Experimental Setup

The study tests evaluator construction, workflow evolution, and execution-state refinement across MCPMark environments. Filesystem is the primary controlled study; other environments serve as stress tests, with model roles and budgets specified for the experiments.

5.1 Evaluation Questions and Scope

  • The study asks whether VeriEvolve can construct evaluators, guide workflow search, and reveal missing evaluator constraints from strong–weak execution-state differences.Filesystem is the primary controlled study; the remaining environments are cross-environment stress tests.Source: §5.1 · p. 5

5.2 Models and Experimental Budgets

  • Stage 1 construction ran in interactive Claude Code sessions; other model-backed roles use Claude Sonnet except the GLM-5.2 weak executor, with external verdicts reserved for post-hoc measurement.Stage 2 includes evaluators with at least 0.85 post-hoc external agreement; runs use up to 15 rounds and three refinement rounds, with stated path and timeout exceptions.Source: §5.2 · p. 5

6 Results

Workflow evolution improves externally verified success on Filesystem and helps weak PostgreSQL runs, while evaluators show high—but incomplete—agreement with external labels. Strong–weak state comparisons repair three exposed false positives, though search and executor limits remain.

6.1 RQ1: Constructing Evaluators

  • 30/30 Filesystem evaluators agreed on 141 generated challenge states, and frozen evaluators agreed on 113/122 distinct held-out states; PostgreSQL evaluators agreed on 115/120 calibration states.The held-out Filesystem pool over-represents internally high-scoring states and is not an independent sample.Source: §6.1 · pp. 5–6, Table 1 · p. 6, Table 2 · p. 6

6.2 RQ2: Guiding Workflow Evolution

  • 6/30 to 18/30 weak-executor and 27/30 to 30/30 strong-executor externally verified Filesystem successes followed workflow evolution; 12/15 admitted PostgreSQL tasks remained unsolved.On PostgreSQL, both executors solved the same three tasks; the strong executor solved them at round 0.Source: Table 3 · p. 6, §6.2 · pp. 6–7

6.4 Cost and Repair Effort

  • 64K tokens—under 1% of Stage 3 tokens—went to evaluator-repair calls; the remaining search included 49 rounds and 3.36M executor tokens, including an excluded structure_mirror round.The reported cost was $2.60 of evolver cost for each Filesystem task gained through evolution.Source: Table 4 · p. 7, §6.4 · p. 8

6.3 RQ3: Refining Evaluators from Execution States

  • 3/3 exposed Filesystem evaluator gaps were repaired from strong–weak state differences, and no false positive survived primary refinement; only structure_mirror was solved by rerunning weak-executor search under its revised evaluator.The refinement strategy repaired exact text and terminal-newline fidelity, a required code pattern, and missing nested directories and placeholders; PostgreSQL yielded no agent-produced false positive to refine.Source: §6.3 · p. 7

7 Discussion

A calibrated evaluator is necessary but not sufficient: search and execution can become the bottlenecks. Refinement also depends on reaching an accepted state that exposes a gap, and making a verifier-free trigger precise remains open.

7 Discussion

  • Neither executor converges on 12 of the 15 admitted PostgreSQL tasks, showing that a usable fitness signal does not guarantee task completion.On the three solved tasks, only the weak executor needs evolution.Source: §7 · p. 8
  • Refinement starts only when search reaches an evaluator-accepted state that exposes a gap; in these experiments, the external verifier supplied that trigger.A verifier-free alternative caught all three false positives retrospectively but also flagged 10 of 18 correct states, so making the trigger precise remains open.Source: §7 · p. 8

8 Conclusion

VeriEvolve constructs challenge states and executable evaluators before optimizing tool-use workflows. On observable MCPMark tasks, the evaluators guide externally measured improvement, but their calibration and repair still rely on an external verifier.

8 Conclusion

  • VeriEvolve constructs challenge states and executable evaluators before optimizing tool-use workflows.The external verifier admits evaluators and exposes their errors; removing that dependence is identified as the main step toward agents that construct their own fitness signals.Source: §8 · p. 8
  • On MCPMark tasks with success observable through environment state, evaluators agree on their challenge states and most held-out agent-produced states, guide workflow improvement, and can be repaired from strong–weak state differences after a false positive is identified.The external verifier remains the reference for admission and error detection.Source: §8 · p. 8

Limitations

The limitations qualify feasibility claims: evaluator reliability and refinement remain dependent on external calibration, finite and selected test states, uneven cross-environment coverage, and execution capacity. The supplied appendix passages also describe study scope, model invocation, workflow search, and one task-specific evaluator.

Limitations

  • The results establish feasibility under external calibration, not evaluator reliability or autonomous refinement without an independent verifier.External agreement admits evaluators, external verdicts identify false positives for refinement, and reference states are externally accepted.Source: Limitations · p. 9
  • Finite challenge suites do not guarantee coverage; generated tests and evaluators share Claude as author, while held-out states are selected as each round’s best state.Initial Stage 1 construction used a procedural verifier-information boundary; stronger packet-level technical isolation applies to Stage 3.Source: Limitations · p. 9
  • Filesystem alone has complete Stage 1 and Stage 2 coverage plus execution-state refinement; other environments have narrower or incomplete evidence and representation constraints.PostgreSQL evaluates 15 Stage 2 tasks, but only three are solved, with no false-positive state to trigger Stage 3.Source: Limitations · p. 9
  • Each Filesystem condition ran once and lacked a budget-matched search baseline, so repeated sampling may explain part of the measured gain.A usable signal does not ensure convergence; repeated workflow execution and refinement are computationally expensive.Source: Limitations · p. 9

A.1 Audited Experimental Scope

  • Table 5 reports audited task scope, separating historical, diagnostic, and incomplete pilot results from standardized matched pairs.Formal exclusions are not counted as task failures, and infrastructure-invalid runs are excluded from semantic results.Source: §A.1 · p. 10, Table 5 · p. 11

B.1 Model Roles and Invocation Modes

  • Stage 1 used one interactive Claude Code session for test generation and verifier evolution; Stage 3 resumed retained packet-restricted sessions, while the Workflow Evolver was stateless across rounds.The orchestration code supplied the Workflow Evolver’s alternatives, score history, failed checks, and execution diagnosis on each call.Source: §B.1 · p. 11

B.2 Persistent Multi-Alternative Workflow

  • Stage 2 uses persistent alternatives across five workflow nodes, with score-weighted selection, forced exploration for new alternatives, and eviction at node caps.The evaluator remains frozen throughout this process; the five active nodes are task understanding, planning, ReAct execution, artifact inspection, and post-processing.Source: §B.2 · p. 11

A.2 Explicitly Checkable and Implicit Stateful Requirements

  • Task difficulty varies: some instructions translate nearly directly into checks, while others distribute correctness across interacting final-state properties.VeriEvolve targets structured-state tasks without a complete executable evaluation specification.Source: §A.2 · p. 11, Table 6 · p. 12

C.2 False-Positive Exposure

Across Filesystem, the study traces how challenge-state gaps produced evaluator false positives, how paired strong–weak differences enabled a one-round repair, and how the broader campaigns performed. It also distinguishes a synchronization artifact from a genuine failure and reports construction, held-out, and lineage evidence.

C.2 False-Positive Exposure

  • The weak state exposed a false positive because E(0) checked only five listed leaf directories and missed three directories without placeholders, including project/src/main/resources.The original challenge states missed this gap because their negative case omitted every placeholder, which the five checked paths already detected.Source: §C.2 · pp. 12–13

C.3 One Refinement Round

  • One refinement round added three missing placeholder paths, and cumulative regression verified acceptance of the strong state, rejection of the weak state, and preservation of 11 earlier verdicts.The refined workflow then reached a state accepted by the external verifier.Source: §C.3 · p. 13

C.4 An Artifact-Triggered Second Round

  • A second refinement round triggered by a synchronization-created directory was excluded after reverification showed all evaluator versions accepted the archived state.The resulting E(2) and its weak state are reported only for completeness.Source: §C.4 · p. 13

C.5 Separate Controlled Run

  • A separate controlled run found a genuine extra-structure failure: eleven extra placeholder files and a directory remained in a weak state accepted by E(1) but rejected externally.Its E(2) added checks for the extra structure, after which the weak executor produced an internally and externally accepted state.Source: §C.5 · pp. 13–14

D.1 Filesystem Stage 1 Results

  • 30/30 Filesystem evaluators covered 141 challenge states, including 62 adversarial near-misses, and all 141 labels agreed with the external verifier.Per-task Verifier-Evolver iteration counts were not recorded consistently.Source: §D.1 · p. 14

D.2 Filesystem Stage 2 Results

  • 18/30 GLM-5.2 and 30/30 Claude externally verified successes follow workflow evolution, compared with seed results of 6/30 and 27/30, respectively.The audited weak-executor campaign reached 21/30 internal successes; the strong campaign reached 30/30 internal and external successes.Source: §D.2 · p. 14

D.3 Held-Out Evaluation on Agent-Produced States

  • Of 320 retained snapshots, 258 were valid campaign states; the three false positives were final GLM-5.2 states of uppercase, debugging, and structure_mirror.Six distinct false negatives were also identified: three Claude gradebased_score states, one Claude file_arrangement state, one Claude requirements_completion state, and one GLM-5.2 requirements_writing state.Source: §D.3 · pp. 14–15

D.4 Filesystem Stage 3 Lineage

  • The Stage 3 ledger separates primary refinement runs from development, diagnostic, and case-study trajectories; primary claims use only the three primary runs and explicitly separated exposure and controlled runs.This provenance distinction prevents non-primary trajectories from being pooled into the main refinement claims.Source: §D.4 · p. 15

D.5 Cross-Environment Results

Cross-environment results show that evaluator construction and workflow evolution have different limits across settings, including observation, state representation, and search capacity. Additional analyses qualify the Filesystem comparisons, refinement triggers, and reference-state assumptions.

D.5 Cross-Environment Results

  • On 15 eligible PostgreSQL tasks, both executors solved the same three; neither converged on the other 12, and every internally accepted final state passed external verification.The strong executor solved the three at round 0; the weak executor required 11, 2, and 7 evolution rounds and 5–32× the strong executor’s tokens.Source: §D.5 · p. 15

E.1 Workflow Representation and Evolution

  • The historical Claude campaign improved external success from 17/30 to 30/30, but differences in campaign components prevent attributing the comparison solely to the five-node representation.The campaigns also differed in seed, source version, and evolver invocation.Source: §E.1 · p. 17

E.2 Weak-Executor Context and Model Tier

  • Without context truncation, GLM-5.2 converged internally on 21/30 tasks rather than 7/18 completed tasks in the truncated campaign, though the denominators differ.A separate model-tier comparison under identical evaluators reports GLM-4.5 at 9/30 internal and 7/30 external successes, versus GLM-5.2 at 21/30 and 18/30.Source: §E.2 · p. 17

E.3 Paired Contrasts and Localized Evaluator Repair

  • On debugging, unaided evaluator regeneration failed in four attempts, while a positive–negative contrast and localized patch constraint produced the required check in two to three attempts.The resulting design uses factual paired contrasts and minimal changes checked by cumulative regression.Source: §E.3 · p. 18

E.4 Stagnation and Redundant Refinement

  • Two of three additional uppercase refinement rounds added no evaluator capability, and the stagnation gate stopped all three primary refinement runs when differences were already covered.A cap-three replay produced identical later weak states and content-identical evaluator revisions.Source: §E.4 · p. 18

E.5 Strong-Executor Reliability

  • A usable strong-executor reference was available for all 30 Filesystem tasks but only 3 of 15 admitted PostgreSQL tasks; the effect of a wrong reference remains untested.All references used in the experiments were externally accepted, although one of 36 internally accepted strong states was rejected externally.Source: §E.5 · p. 18

E.6 A Verifier-Free Refinement Trigger

  • A verifier-free trigger based on any weak–strong state difference caught all three false positives, but also flagged ten of 18 correct states that differed.Whether the Stage 3 filters would dismiss these false alarms or over-tighten the evaluator was not tested; the analysis uses only three positive cases.Source: §E.6 · pp. 18–19

F Compute, Cost, and Runtime

The appendices qualify compute costs and document the information boundaries, provenance, and schemas used to make the experiments auditable. They also specify role inputs and artifacts across evaluator construction, workflow evolution, and refinement.

F Compute, Cost, and Runtime

  • The weak Filesystem campaign used approximately 58× the executor tokens of the strong campaign, while Stage 3 revisions each triggered another five-path, up-to-15-round search.The expanded PostgreSQL campaign required approximately 46.9M executor tokens across 15 eligible tasks, most of which still ended without internal convergence; Stage 1 costs were not recorded.Source: F Compute, Cost, and Runtime · pp. 19–20

G.1 External-Verifier Information Boundary

  • The external verifier never supplies optimization feedback; its post-run verdicts are used for evaluator admission, selecting false positives for refinement, and confirming reference states.Stage 2 and Stage 3 add technical input and tool restrictions, while initial interactive Stage 1 relies on a documented procedural boundary.Source: §G.1 · p. 20, Table 25 · p. 23

G.2 Stage 3 Packet Isolation; G.4 Run Classification and Intervention Policy

  • Stage 3 model calls receive an allowlisted packet, and attempts to access material outside it abort the run; no such violation occurred in the primary campaign.Run classification separates infrastructure failures from semantic outcomes and retains development and diagnostic runs outside primary totals.Source: §G.2 · pp. 20–21, §G.4 · p. 21

G.3 Provenance and Immutable Artifacts

  • Immutable run records preserve evaluator and workflow hashes, state archives, telemetry, and cumulative regression results; independent searches also reproduced evaluator and state artifacts.The uppercase E(1) evaluator was byte-identical across three independent searches, and the structure_mirror accepted-state hash recurred across primary and controlled runs.Source: §G.3 · p. 21

H.1 Prompt Availability

  • Exact rendered prompts from interactive Stage 1 sessions were not recorded, so the paper reports role contracts, visible inputs, tools, and output schemas instead.Stage 2 and Stage 3 templates are retained, though campaign-era Stage 2 hashes were not recorded for every early run.Source: §H.1 · p. 21

H.2 Role Contracts; H.3 Challenge-State Schema; H.5 Workflow-Alternative Schema

  • The role contracts assign instruction-grounded challenge generation and evaluator writing to separate roles, while workflow evolution proposes alternatives for a five-node task workflow.Challenge states are declarative mutations materialized by deterministic adapters; the workflow executor returns a final state and execution trace.Source: §H.2 · pp. 21–22, §H.3 · p. 23

H.4 Evaluator Schema

  • Evaluators expose a sandboxed verify function with an overall verdict and per-check evidence; the Filesystem context permits read-only inspection operations.Imports, direct file opening, code evaluation, subprocesses, network access, and filesystem writes are prohibited.Source: §H.4 · p. 23

H.6 State-Difference and Counterfactual Schemas; H.7 Cumulative Regression and Loop State

  • Refinement pairs a negative case reproducing one state difference with a positive control that removes only that difference, then records cumulative cases and evaluator lineage.Coverage and label-consistency gates validate the pair; loop state tracks seen and covered clusters, stagnation decisions, and terminal reason.Source: §H.6 · p. 23, §H.7 · p. 24

Related papers

Loading 2610.29005v1…