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

LLM-powered tool-calling agents fulfill user requests by interacting with environments and invoking tools over multi-turn processes. 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 evolve — 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 schemas — and their dependencies. Under this formalism, adding, removing, or modifying capabilities is 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.