LLM-powered tool-calling agents fulfill user requests by interacting with environments, querying data, and invoking tools in a multi-turn process. Yet, most existing benchmarks evaluate these systems under static environment interfaces, with fixed schemas and toolsets, making it difficult to assess how agents behave as environments evolves -- when capabilities are added, reorganized, or deprecated across successive environment versions. In this paper, we study structured environment evolution as a benchmark-construction problem for tool-calling agents. We propose ProEvolve, a graph-based framework that makes environment evolution programmable. At its core, a typed relational graph provides a unified, explicit representation of the environment - data, tools, and schema. Under this formalism, adding, removing, or modifying capabilities are expressed as graph transformations that coherently propagate updates across tools, schemas, and data access. Building on this, ProEvolve supports (1) automatic generation of evolved executable environments through explicit graph transformations, and (2) graph-grounded construction of task sandboxes via subgraph sampling and instantiation. We validate ProEvolve in two tool-calling domains, e-commerce and airline booking, in terms of quality, implementation validity, and failure modes. Finally, we use the generated benchmark as a downstream diagnostic to study how representative agents behave under structured environment evolution.
Figures & tables
Figure 1: End-to-end workflow of ProEvolve . Starting from a seed tool-calling environment, ProEvolve represents schemas, data entities, and tools as an environment graph, applies semantic evolution intents as graph transformations, and instantiates the transformed graph into executable environment versions. For each version, task sandboxes are generated by sampling task subgraphs, materializing version-specific prerequisites, and producing state-wise user instructions and success criteria, enabling controlled evaluation under structured environment evolution.
Figure 2: Programmed Environment Evolution with two versions The evolution is programmed via graph transformations, expressed as editions on nodes (schemas, e.g., InstallmentPlan ) and edges (tool-enabled transitions, e.g., get_installment_schedule ) that derives evolutions with existing structure.
Figure 3: Context as subgraph expansion in a tool-mediated conversation. At each turn, the environment exposes a reachable context subgraph (gray nodes; dashed arrows for reachable tool transitions), while the agent activates a subset of nodes (green) by executing tools/actions (solid arrows) conditioned on the dialogue. As the conversation progresses, executed transitions expand the active subgraph, enabling retrieval and integration of newly reachable information (e.g., from User.user_id to User.order to Order.order_items and downstream product attributes).
E-com.
Airline
Benchmark Scale
Seed environments
1
1
Evolution trajectories
50
5
Environment variants
200
20
Task sandboxes
3,000
300
Environment Complexity
Table 1: Scale/Quality of evolved environments.
Model
Seed
Δcomp
Δsat
Δdep
GPT-5 [ 15 ]
0.56 / 8.1 / 8.1
0.65 (+0.08) / 10.3 / 12.8
0.77 (+0.21) / 13.2 / 14.9
0.45 (-0.11) / 8.7 / 20.6
Claude-Opus-4.5 [ 2 ]
0.49 / 6.3 / 4.7
0.46 (-0.02) / 5.5 / 4.8
0.62 (+0.14) / 7.3 / 5.9
0.37 (-0.12) / 4.5 / 4.4
DeepSeek-v3.2 [ 9 ]
0.53 / 7.3 / 6.7
0.52 (-0.01) / 7.4 / 6.9
0.49 (-0.04) / 8.5 / 6.7
0.46 (-0.07) / 9.0 / 7.3
Qwen3-235B [ 18 ]
0.59 / 10.4 / 9.5
0.63 (+0.05) / 12.9 / 13.1
0.46 (-0.13) / 9.0 / 8.1
0.36 (-0.22) / 7.6 / 7.4
Gemini-2.5-Pro [ 5 ]
0.43 / 7.3 / 3.6
0.57 (+0.15) / 8.9 / 5.1
0.54 (+0.12) / 8.0 / 3.9
0.45 (+0.03) / 8.1 / 3.9
Table 2: Baseline behavior across e-commerce versions. Each cell reports C(Δ)/Tˉ/Nˉtool (state-wise success / avg turns / avg tool calls).
Figure 4: Efficiency breakdown by task difficulty. We report average tool calls, estimated cost, conversation turns, and reward for each model under varying difficulties.
Figure 5: Performance–efficiency tradeoff under context priors. Each point represents an agent/probe setting, with state-wise success on the y-axis and average tool calls on the x-axis.
Figure 6: Failure-mode breakdown across environment versions. Bars decompose sampled failed trajectories by coarse error type.
Figure 7: Layered topology of evolved airline environments. Grey nodes and edges represent the shared seed environment (V0: 10 databases, 56 nodes, 68 edges, 21 tools). Each colored region represents an independent evolution trajectory extending the base airline schema with new capabilities. Dotted edges denote intra-database connections; solid directed edges denote cross-database tool invocations. Node labels indicate newly added databases; edge labels show tool names introduced by each trajectory.
Figure 8: Layered topology of evolved e-commerce environments. Grey nodes and edges represent the shared seed environment (V0: 7 databases, 64 nodes, 63 edges, 23 tools). Each colored region corresponds to a distinct evolution trajectory that adds new databases, attributes, and tool-mediated relationships to the base schema. Dotted edges denote intra-database attribute connections; solid directed edges denote cross-database tool invocations. Annotations on nodes indicate newly introduced databases; annotations on edges show the corresponding tool names.
Table 3: Per-version defect-free rate and failure criticality distribution. An env-version is defect-free iff it contains zero level-3 (partial-impact) failures.
Failure Category
% of Failures
% of All Tests
Impact on Tool Usage
Test implementation issues
51%
4.7%
None — bug in test, not environment
Corner-case handling
23%
2.1%
Minimal — e.g., invalid-input checks
Real tool issues
10%
0.9%
Affects specific tools
Other
16%
1.5%
Varies
Appendix
Table 4: Breakdown of unit-test failures across all evolved environments. We categorize each failing test by its root cause and downstream impact on tool usage. Only ∼10% of failures (roughly 1% of all tests) affect actual tool behavior.
Sub-criterion
What it checks
Reality. Plausibility of the evolution as a real-world change.
Realism
The evolution reflects a change that could plausibly happen in production (e.g., feature addition, API consolidation, deprecation).
Coherence
The proposal has a clear user story and internally consistent entities/tools.
Complexity
The scope is well-calibrated for a single evolution step—non-trivial yet bounded.
Graph Fidelity. Alignment between implemented code and the specified graph edit.
Completeness
All nodes/edges added or removed by the graph edit appear in the implementation.
Table 7: Diversity comparison between graph-guided ProEvolve and a random-evolution LLM baseline, each run over 50 trajectories from the same e-commerce seed.
Metric
ProEvolve
No-Graph
Δ
Mean pairwise tool Jaccard dist. ↑
0.976
0.867
+0.109
Mean pairwise entity Jaccard dist. ↑
0.979
0.805
+0.174
Unique tool ratio ↑
0.645
0.394
+0.251
Unique entity ratio ↑
0.606
0.336
+0.269
Tool frequency entropy ↑
8.07
7.66
+0.41
Entity frequency entropy ↑
6.18
6.10
+0.07
Appendix
Table 8: Environment diversity comparison. ProEvolve (graph-guided evolution) vs. a non-graph baseline that receives the same seed specifications but proposes and implements evolution without explicit graph transformations. All metrics are computed over the 200 e-commerce environment variants.
Dimension
What it checks
Scenario Coherence. Does the sequence of states form a realistic, logical customer journey?
Narrative arc
States follow a natural progression; no random or disconnected actions.
Transition logic
Each state follows plausibly from its predecessor without forced jumps.
Difficulty Calibration. Does the task complexity match the claimed difficulty level?
Table 9: Scoring rubric for task quality evaluation. Score 5 = fully meets; 3–4 = partially meets; ≤ 2 = does not meet.
Dimension
E-com.
Airline
Scenario Coherence
4.75
4.81
Difficulty Calibration
5.00
5.00
State Transition Feasibility
4.50
4.06
Prerequisite Sufficiency
4.62
4.88
Appendix
Table 10: Task quality scores (1–5 scale) judged by LLM-as-a-Judge across sampled sandboxes.
Evolving Trajectory
G(0)
Δcomp
G(1)
Δsat
G(2)
Δdep
G(3)
Overall
Strategy
C(0)
T
Ntool
C(1)
T
Ntool
C(2)
T
Ntool
C(3)
T
Ntool
μC
T
Ntool
GPT-5
Baseline
0.564
8.1
8.1
0.646
10.3
12.8
0.771
13.2
14.9
0.454
8.7
20.6
0.609
10.1
14.1
Trace Context
0.562
8.9
10.2
0.667
9.4
13.5
0.786
11.6
14.4
0.407
6.5
7.6
0.606
9.1
11.4
Summary Context
0.598
12.3
12.2
0.537
10.1
11.1
0.677
11.8
13.1
0.530
9.2
10.3
0.585
10.9
11.7
Claude-Opus-4.5
Appendix
Table 11: Evolving-trajectory evaluation across environment transformations. We report per-version task success rate C(k) , average turns T , and average tool calls Ntool for a fixed evolving trajectory G(0)→G(1)→G(2)→G(3) generated by applying three evolution strategies (arrows): Δcomp , Δsat , and Δdep . Each block compares adaptation strategies (Baseline, Trace Context, Summary Context) for a given model, and the Overall columns summarize mean completeness μC and average interaction cost aggregated over versions.
Evolving Trajectory
G(0)
Δcomp
G(1)
Δsat
G(2)
Δdep
G(3)
Overall
Strategy
C(0)
T
Ntool
C(1)
T
Ntool
C(2)
T
Ntool
C(3)
T
Ntool
μC
Cost
Claude-Opus-4.5
Baseline
0.58
11
12
0.49
7
9
0.54
9
10
0.27
9
12
0.47
$0.68
Trace Context
0.50
9
18
0.35
7
10
0.58
8
12
0.43
10
11
0.47
$0.70
Summary Context
0.60
11
22
0.29
7
14
0.25
6
14
0.20
9
16
0.34
$1.02
DeepSeek-V3.2
Appendix
Table 12: Airline domain: evolving-trajectory evaluation. We report per-version consecutive success rate C(k) , average turns T , and average tool calls Ntool for a fixed evolving trajectory G(0)→G(1)→G(2)→G(3) generated by applying three evolution strategies: Δcomp , Δsat , and Δdep . The Overall columns report mean success μC and estimated API cost per task.
Failure Mode
Definition
Missed tool discovery
The agent does not know a relevant tool exists. It tells the user “I can’t do that” or “I don’t have access” when an appropriate tool is available. Failure at the discovery/awareness level.
Invalid parameters
The agent identifies and calls the correct tool but passes wrong arguments—wrong entity IDs, malformed field values, or incorrect types. The tool errors out or returns incorrect results.
Missing invocation
The agent understands what needs to happen and knows the tool exists, but does not proactively call it. It waits passively, provides text explanations, or lets the user drive the next step. Failure in initiative/sequencing, not knowledge.
Unrecovered error
A tool call returns an explicit error (e.g., “product not found”), and the agent fails to adapt—it retries with the same bad parameters, gives up entirely, or tells the user to try later instead of attempting an alternative approach.
Infeasible expectation
The expected state requires an action that genuinely cannot be accomplished with the available tool set (e.g., triggering warehouse processing or initiating a live chat). This reflects a benchmark design boundary rather than an agent failure.
Appendix
Table 13: Failure-mode taxonomy for tool-calling agents.
Figure 9: Failure-mode distribution across environment versions and context conditions (agent: Claude-Opus-4.5). Each bar decomposes sampled failed states by root cause. Missing invocation dominates under No Prior Context and Trace Context, while Summary Context shifts failures toward missed tool discovery —indicating that distilled summaries can actively mislead agents about current tool availability. Unrecovered error increases under Δdep , reflecting retry loops on deprecated tools.
Domain
Primitive
Example capability/change
E-commerce
Completion
Competitor price monitoring / alerts
Airline
Completion
Redeem miles for flight upgrade
E-commerce
Saturation
Order refund summary shortcut
Airline
Saturation
Reservation flight status shortcut
E-commerce
Deprecation
Cart service unavailable
Airline
Deprecation
Direct-flight search deprecated
Appendix
Table 14: Representative evolution examples used in Appendix F .
Large language model (LLM) agents have achieved strong performance on a wide range of benchmarks, yet most evaluations assume static environments. In contrast, real-world deployment is inherently dynamic, requiring agents to continually align their knowledge, skills, and behavior with changing environments and updated task conditions. To address this gap, we introduce EvoArena, a benchmark suite that models environment changes as sequences of progressive updates across terminal, software, and social domains. We further propose EvoMem, a patch-based memory paradigm that records memory evolution as structured update histories, enabling agents to reason about environmental evolution through changes in their memory. Experiments show that current agents struggle on EvoArena, achieving an average accuracy of 39.6% across evolving terminal, software, and social-preference domains. EvoMem consistently improves performance, yielding an average gain of 1.5% on EvoArena and also improving standard benchmarks such as GAIA and LoCoMo by 6.1% and 4.8%. Beyond individual tasks, EvoMem further improves chain-level accuracy by 3.7% on EvoArena, where success requires completing a consecutive sequence of related evolutionary subtasks. Mechanistic analysis shows that EvoMem improves evidence capture in the memory, indicating better preservation of complete evolving environment states. Our results highlight the importance of modeling evolution in both evaluation and memory for reliable agent deployment.
Jundong Xu, Qingchuan Li, Jiaying Wu +11
National University of Singapore · Singapore Management University · University of Washington +5
Agent self-evolution in long-horizon LLM systems is largely procedural: useful experience is not merely stored information, but reusable procedures for searching, debugging, and verification. Yet current evaluations do not isolate this form of transfer. Agent benchmarks test single-episode task solving; memory benchmarks target information retention rather than procedural reuse. We introduce EvoAgentBench, a benchmark for agent self-evolution via Ability-guided transfer across four agentic domains: web research, algorithmic reasoning, software engineering, and knowledge work. EvoAgentBench extracts trace-grounded Abilities from agent executions, canonicalizes them into operational units, and builds domain-specific Ability Graphs linking tasks that share procedural overlap. By design, every test task is backed by verified training-side Ability support. Across a 528/267 train/test split, two scaffolds, and three backbones, curated Ability content transfers reliably across model families, but no current automatic method sustains positive gain in all settings. EvoAgentBench shifts self-evolution evaluation from aggregate accuracy comparison to fine-grained diagnosis of experience encoding, routing, and uptake. The benchmark is publicly available at https://huggingface.co/datasets/EverMind-AI/EvoAgentBench.
Xingze Gao, Chuanrui Hu, Hongda Chen +9
1Anhui University · 2EverMind, Shanda Group · 3Southeast University
Static benchmarks for large language model (LLM) agents face saturation and data contamination risks, motivating continual updates to evaluation tasks. However, aggregate scores and success rates offer limited insight into specific problem-solving bottlenecks and provide limited guidance for subsequent task design. We propose EvoProbe, an evaluation-driven benchmark evolution framework that integrates task generation, diagnostic evaluation, and feedback-driven regeneration into a closed loop. It combines verifiable subtask outcome scoring with evidence-supported multi-judge trajectory evaluation and distills phase-level bottlenecks, success patterns, and failure patterns into diagnostic feedback for generating new executable tasks. Across two rounds of cybersecurity experiments, evaluations of eight models on 66 tasks reveal phase-level performance differences and common failure patterns beyond aggregate scores. In a cross-round comparison with the Examiner model set and solver configuration held fixed, all eight models achieve lower Outcome scores on the updated tasks, with relative decreases of 11.8% in mean Outcome and 40.0% in mean Pass\textasciicircum{}3. These results support using fine-grained diagnostics to guide iterative task updates and probe agents' current capabilities and limitations.
Qianhong Guo, Wei Xie, Xiaofang Cai +3
College of Computer Science and Technology, National University of Defense Technology · Institute of Information Engineering, Chinese Academy of Sciences