The World Won't Stay Still: Programmable Evolution for Agent Benchmarks

Guangrui Li; Yaochen Xie; Yi Liu; Ziwei Dong; Xingyuan Pan; Tianqi Zheng; Jason Choi; Michael J. Morais

cs.AIMar 6, 2026

The World Won't Stay Still: Programmable Evolution for Agent Benchmarks

Authors: Guangrui Li, Yaochen Xie, Yi Liu, Ziwei Dong, Xingyuan Pan, Tianqi Zheng, Jason Choi, Michael J. Morais,

Organizations: Amazon · UC Berkeley

Abstract

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	$\Delta^{\text{comp}}$	$\Delta^{\text{sat}}$	$\Delta^{\text{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

\mathcal{C}(\Delta)/\bar{T}/\bar{N}_{\mathrm{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.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Version	Defect-free	Cat-1 (no impact)	Cat-2 (corner)	Cat-3 (defect)
E-commerce (50 trajectories $\times$ 3 versions = 150 env-versions)
V1 (completion)	46/50 (92%)	118	298	46
V2 (saturation)	50/50 (100%)	80	77	0
V3 (deprecation)	48/50 (96%)	94	95	2
All	144/150 (96.0%)	292	470	48
Airline (5 trajectories $\times$ 3 versions = 15 env-versions)

Appendix

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

{\sim}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.

Appendix

Table 5: Scoring rubric for semantic fidelity.

	E-commerce			Airline
Sub-criterion	Mean	Meet	Partial	Mean	Meet	Partial
Realism	4.87	90%	10%	5.00	100%	0%
Coherence	4.80	83%	17%	4.93	93%	7%
Complexity	4.60	57%	43%	4.40	40%	60%
Graph completeness	4.40	47%	53%	4.40	47%	53%
Graph correctness	4.77	80%	20%	4.80	80%	20%

Appendix

Table 6: Per-sub-criterion LLM-as-Judge results. E-commerce: 10 trajectories

\times

3 versions (30 evaluations). Airline: 5 trajectories

\times

3 versions (15 evaluations).

Metric	ProEvolve	Random LLM	$\Delta$
Tool diversity
Pairwise Jaccard distance $\uparrow$	0.976	0.867	$+0.109$
Unique tool ratio $\uparrow$	0.645	0.394	$+0.251$
Tool-frequency entropy (bits) $\uparrow$	8.07	7.66	$+0.41$
Avg. new tools per trajectory	10.8	21.0	—
Entity diversity

Appendix

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	$\Delta$
Mean pairwise tool Jaccard dist. $\uparrow$	0.976	0.867	+0.109
Mean pairwise entity Jaccard dist. $\uparrow$	0.979	0.805	+0.174
Unique tool ratio $\uparrow$	0.645	0.394	+0.251
Unique entity ratio $\uparrow$	0.606	0.336	+0.269
Tool frequency entropy $\uparrow$	8.07	7.66	+0.41
Entity frequency entropy $\uparrow$	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?
State count	Easy: 5–6 states; medium: 6–8; hard: 8–10.
Operation mix	Easy: mostly reads; medium: reads + simple writes; hard: multi-entity read/write chains.

Appendix

Table 9: Scoring rubric for task quality evaluation. Score 5 = fully meets; 3–4 = partially meets;

\leq

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		$\mathcal{G}^{(0)}$	$\xrightarrow{\Delta^{\text{comp}}}$		$\mathcal{G}^{(1)}$	$\xrightarrow{\Delta^{\text{sat}}}$		$\mathcal{G}^{(2)}$	$\xrightarrow{\Delta^{\text{dep}}}$		$\mathcal{G}^{(3)}$		Overall
Strategy	$\mathcal{C}^{(0)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(1)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(2)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(3)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mu_{C}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$
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

\mathcal{C}^{(k)}

, average turns

\overline{T}

, and average tool calls

\overline{N}_{\text{tool}}

for a fixed evolving trajectory

\mathcal{G}^{(0)}\!\rightarrow\!\mathcal{G}^{(1)}\!\rightarrow\!\mathcal{G}^{(2)}\!\rightarrow\!\mathcal{G}^{(3)}

generated by applying three evolution strategies (arrows):

\Delta^{\mathrm{comp}}

\Delta^{\mathrm{sat}}

, and

\Delta^{\mathrm{dep}}

. Each block compares adaptation strategies (Baseline, Trace Context, Summary Context) for a given model, and the Overall columns summarize mean completeness

\mu_{\mathcal{C}}

and average interaction cost aggregated over versions.

Evolving Trajectory		$\mathcal{G}^{(0)}$	$\xrightarrow{\Delta^{\text{comp}}}$		$\mathcal{G}^{(1)}$	$\xrightarrow{\Delta^{\text{sat}}}$		$\mathcal{G}^{(2)}$	$\xrightarrow{\Delta^{\text{dep}}}$		$\mathcal{G}^{(3)}$		Overall
Strategy	$\mathcal{C}^{(0)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(1)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(2)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mathcal{C}^{(3)}$	$\overline{T}$	$\overline{N}_{\mathrm{tool}}$	$\mu_{\mathcal{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

\mathcal{C}^{(k)}

, average turns

\overline{T}

, and average tool calls

\overline{N}_{\text{tool}}

for a fixed evolving trajectory

\mathcal{G}^{(0)}\!\rightarrow\!\mathcal{G}^{(1)}\!\rightarrow\!\mathcal{G}^{(2)}\!\rightarrow\!\mathcal{G}^{(3)}

generated by applying three evolution strategies:

\Delta^{\mathrm{comp}}

\Delta^{\mathrm{sat}}

, and

\Delta^{\mathrm{dep}}

. The Overall columns report mean success

\mu_{\mathcal{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

\Delta^{\text{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 .

AI Agent Benchmarks

AI agent benchmarks measure how reliably autonomous systems plan, use tools, interact, and complete tasks across controlled and real-world settings.

See all 1,494 papers

EvoArena: Tracking Memory Evolution for Robust LLM Agents in Dynamic Environments
Jun 11, 2026Jundong Xu, Qingchuan Li, Jiaying Wu +11Benchmark Design Long-Horizon Agent Evaluation
National University of Singapore · Singapore Management University · University of Washington +5
EvoAgentBench: Benchmarking Agent Self-Evolution via Ability Transfer
Jul 6, 2026Xingze Gao, Chuanrui Hu, Hongda Chen +9LLM Agent Self-Improvement AI Agent Benchmarks
1Anhui University · 2EverMind, Shanda Group · 3Southeast University
EvoProbe: Evaluation-Driven Benchmark Evolution for LLM Agents
Oct 14, 2026Qianhong Guo, Wei Xie, Xiaofang Cai +3LLM Agent Evaluation AI Agent Benchmarks
College of Computer Science and Technology, National University of Defense Technology · Institute of Information Engineering, Chinese Academy of Sciences

Jun 11, 2026J/K move · Enter open · S save

EvoArena: Tracking Memory Evolution for Robust LLM Agents in Dynamic Environments

Jundong Xu, Qingchuan Li, Jiaying Wu, Yihuai Lan+10

National University of Singapore · Singapore Management University · University of Washington+5

Benchmark Design Long-Horizon Agent Evaluation AI Agent Benchmarks Agent Memory Management Memory-Augmented Language Model Agents

Open paper AskPDF arXiv

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.

Abstract

AI Agent Benchmarks

Explore similar work

EvoArena: Tracking Memory Evolution for Robust LLM Agents in Dynamic Environments

EvoAgentBench: Benchmarking Agent Self-Evolution via Ability Transfer

EvoProbe: Evaluation-Driven Benchmark Evolution for LLM Agents