acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
datasets and benchmarks
Keywords:
Environment Evolution, Tool-calling agent, Large Language Models

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_GJg8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes ProEvolve, a graph-based framework for automatically constructing evolving benchmarks for tool-calling agents, addressing the limitations of existing benchmarks with static environments. By representing schemas, data entities, tools, and their dependencies as a unified graph, ProEvolve enables structured environment evolution through graph transformations and generates corresponding executable task sandboxes via subgraph sampling. Experiments in e-commerce and airline booking evaluate the validity, quality, and diversity of the generated environments and investigate agent behavior under environment evolution.

Critical strengths
  1. The idea of dynamically evolving environments through graph transformation is interesting.

  2. The proposed three explicitly defined evolution strategies makes the environment evolution controllable.

Critical weaknesses
  1. The changing graph and environment seem cannot guarantee the behavioral correctness of the evolved envirionments. The proposed graph formalism primarily captures schema elements and tool dependencies, but does not explicitly model behavioral semantics such as preconditions, postconditions, and state-changing effects. Consequently, structurally valid graph transformations do not necessarily produce functionally correct environments. Moreover, since unit tests and oracle trajectories are derived from the generated specifications, the validation pipeline may fail to detect semantic errors already present in those specifications.

  2. Oracle-solvable tasks are not necessarily representative of real-world scenarios. The proposed task generation process relies on subgraph sampling and random walks to construct executable trajectories, but such trajectories do not necessarily correspond to realistic user needs or natural workflows. Although oracle replay verifies task solvability, it does not guarantee that the generated tasks reflect meaningful real-world scenarios, potentially limiting the benchmark's practical relevance.

  3. Limited evidence that graph-guided evolution improves downstream benchmark quality. Although ProEvolve achieves higher tool and entity diversity than the free-form baseline, these structural metrics do not necessarily translate into more diverse or challenging benchmark tasks. The paper lacks a direct comparison of the generated tasks and their evaluation utility against the baseline, making it difficult to assess the practical benefits of graph-guided evolution beyond structural diversity.

  4. Poor representation. The paper especially experiment section relegates too many important details and empirical findings to the appendix, often leaving only brief descriptions in the main text, which makes the results difficult to follow and interpret. Additionally, the appendix suffers from inconsistent formatting and inefficient use of space. For example, page 26 contains only a short paragraph and a small table, leaving most of the page blank. On page 29, several text overflow beyond the boundaries of boxes.

Questions for authors
  1. It seems that the parities tool Jaccard metric unreasonable? The paper reported this metric as 0.976m but all evolved environments share the same seed containing 51 tools (If I don't misunderstood) with about 10.8 new tools added per trajectory on average. If so, how can the jaccard diversity be so high?

  2. Figure 4(c–d) shows highly model-dependent results, with trace context providing only marginal improvements and summary context improving some agents while substantially degrading others. The paper seemingly lacks a systematic analysis of these inconsistent effects, when and why prior-version experience helps or harms performance under different environment changes.

Some other concerns listed in weakness part

4 comments
AuthorsOpenReview ↗

Response to reviewer GJg8 [part 1 of 2]

Thank you for the detailed feedback. We address validation, task relevance, downstream utility, and presentation below.

W1. Behavioral correctness and shared-specification errors

ProEvolve assesses functional behavior and semantic alignment separately from graph structural validity. Table 1 distinguishes executable checks from environment-edit judgments:

  • Executable behavior: tests check outputs, error conditions, database updates, and cross-entity effects (Appendices A.1 and G.2.2), rather than inferring correctness from graph structure.
  • Proposal validity: Plausibility assesses the evolution proposal's realism, internal coherence, and scope (Appendix A.2, Table 4).
  • Implementation fidelity: Graph Fidelity and Code Fidelity assess whether the implementation realizes the intended edit, including fields, cardinalities, tool placement, signatures, and cross-entity relations.

Thus, specification-derived tests assess implementation conformance; the proposal itself is assessed separately, not validated by those test results. The graph makes the intended changes explicit and inspectable across these stages.

We will make this hierarchy explicit in Sections 4.2 and 5.2 through a construction–evaluation map beside Table 1, identifying each assessment's target, reference, and timing.

W2. Are oracle-solvable tasks meaningful user scenarios?

Workflow coherence is assessed separately from oracle solvability. Table 1 and Appendix A.4, Tables 8–9 evaluate whether tasks form realistic customer journeys with natural progression rather than disconnected actions. In the reported sandbox sample, scenario coherence averages 4.75/4.81 and state-transition feasibility 4.50/4.06 for e-commerce/airline, respectively (1–5 scale).

A new study with 48 ProEvolve-generated tasks and four blinded annotators finds Sonnet-4.5–human agreement of κ = .76 for scenario coherence and .79 for state-transition feasibility, providing a separate check of these judgments.

The benchmark targets controlled diagnostic scenarios, complementing real usage logs and domain-specific evaluations rather than exhaustively reproducing real-world requests (Section 4.2; Appendix C). We will clarify the distinction between executability and workflow coherence beside Table 1 and summarize the new agreement results in Section 5.2, with the protocol in Appendix A.5.

W3. Does graph guidance improve downstream benchmark quality?

Our new task-level comparison shows significantly greater difficulty separation with graph-guided construction than with label-only free-form generation. Graph-path and operation constraints make difficulty targets operational. We evaluate both generators' tasks with GPT-5 under the same agent-evaluation setup.

Task constructionEasyMediumHardEasy − hard
Graph-guided (ProEvolve).73 ± .04.61 ± .06.45 ± .04.28 ± .06
Free-form.86 ± .06.89 ± .08.75 ± .10.11 ± .11
Graph − free-form−.13 ± .07−.28 ± .10−.30 ± .11.17 ± .13

Entries report GPT-5 state-wise success rates CC and their differences. ± denotes 95% CI half-widths; z uses SE = half-width/1.96 on unrounded values. The between-generator difference in easy–hard gaps is .17 ± .13 (z = 2.62, p ≈ .009).

Graph-guided tasks show a monotonic easy-to-hard decline and a larger gap (.28 versus .11), linking explicit difficulty controls to differentiated agent performance beyond structural diversity. We will clarify how typed evolution edits connect to version-grounded task construction in Sections 4.1–4.3 and add this comparison to Section 5.2, with the protocol in the appendix.

W4. Main-text detail and appendix layout

We will move the essential construction and evaluation details into the main text: the graph's cross-stage role in Sections 4.1–4.3, the evaluation hierarchy and key experimental details in Sections 5.1–5.2, and the diagnostic interpretation in Section 5.3.

We will shorten repetitive appendix material, remove the unnecessary page break on page 26, fix the overflowing example box on page 29, and align the validation descriptions and Jaccard labels across the text and tables.

AuthorsOpenReview ↗

Response to reviewer GJg8 [part 2 of 2]

Q1. Why is Jaccard distance so high despite the shared seed?

The high Jaccard distance reflects low overlap among newly added tools, not among complete tool inventories. We compare the added-tool sets from 50 V0→V1 evolution trajectories, excluding the shared seed tools. For each trajectory pair, Jaccard distance measures the fraction of their combined additions that is not shared. Each trajectory introduces relatively few tools, while the high unique-tool ratio indicates that these additions span many distinct tool names across trajectories. These observations are consistent with little pairwise overlap and hence an average distance close to 1, despite all trajectories starting from the same seed.

We will clarify the added-tool set definition and its relationship to the other diversity metrics in Appendix A.3/Table 7, and align the corresponding labels in the main text.

Q2. When and why does prior-version context help or hurt?

This analysis addresses Q3: “Utility: Do evolved environments induce meaningful agent-behavior differences?” Figure 4(c–d) reveals model-specific patterns: Summary Context improves DeepSeek-V3.2, while Claude-Opus-4.5 makes more tool calls without a corresponding performance gain.

We hypothesize that prior experience helps when its assumptions remain relevant but interferes when they become stale. One observed pattern in Appendix B.6 is missed tool discovery under Summary Context for Opus-4.5, including claims that an available tool is unavailable. We will distinguish this observation from the hypothesis in Section 5.3: the analysis demonstrates diagnostic utility, having a more comprehensive discussion in the revision.

I also share some of the other reviewers’ concerns about the graph representation. Although differ, both question whether the graph adequately captures relevant domain constraints. The construction and interaction distinction is useful, but does not explain how omissions or semantic errors in the construction specification are detected.

About my concern, the response remains insufficiently substantiated. Specification-derived tests establish conformance, while plausibility judgments do not necessarily establish behavioral correctness. A targeted case study would help substantiate.

AuthorsOpenReview ↗

Response to Reviewer GJg8: Specification errors and a targeted case study

We sincerely thank the reviewer for this helpful suggestion. We agree that conformance to the specification and correctness of the specification are distinct properties, and that a targeted case study is the right way to substantiate the latter.

We therefore complement the specification-derived tests with an intent–edit consistency audit. It compares each generated graph edit with its original evolution intent and preceding graph, without access to implementation code. We then trace the flagged cases through execution.

1. Case study: service-down deprecation

StageEvidence
RequirementTake ExchangeReturnRequest offline; deprecate track_refund, list_user_exchange_return_requests and get_order_return_items.
Generated editRemoves the entity, but keeps the three tools on Order relationships (e.g. Order.order_id → Order.payment_history). Structural validation passes.
AuditBoth judges flag the same requirement and name the three tools.
ExecutionThe three calls succeed in the preceding version. In the evolved version, all three raise SystemMaintenanceError, as required.
Task generationOf 10 walks forced to include a deprecated tool, 0 produce a task (9 stop at that call). Of 10 control walks, 8 produce a task.

The discrepancy is confined to the specification; the implementation behaves as required. Comparing the edit with the requirement identifies it, complementing structural validation and specification-derived tests.

A saturation case shows the same pattern. The shortcut get_order_return_requests is not attached to the direct Order.order_id → ExchangeReturnRequest.request_id relationship in the graph, but the implemented tool matches an independent multi-hop database query on 5/5 orders.

2. Audit of released transitions

Two judges from different model families (Claude Sonnet 4.6 and GPT-6 Astra) audited 30 released transitions, 10 per primitive. Each judge checks primitive-specific requirements: required elements are present, nothing outside the deprecation's scope is removed, and shortcuts connect the intended endpoints. For every violation it cites the requirement and the edit element.

  • The judges agree on 28/30 transitions (κ = 0.83).
  • Neither judge flags a violation in 21/30.
  • Both flag 7/30. In 6 of these they name the same element, and we confirmed all 6 manually:
    • 4 deprecations, where removal at the relationship level leaves a deprecated tool annotated, or removes a co-located tool that was not deprecated;
    • 2 saturations, where the shortcut is attached to intermediate hops.
  • In 5 of the 6, executing the implementation shows it follows the intent.

3. What the judges can detect

On mutations that keep the graph structurally valid but violate the intent:

Sonnet 4.6GPT-6 Astra
Tool- and field-level mutations detected53/5555/55
Relational mutations detected (foreign key, cardinality, shortcut endpoint)13/4018/40
Valid optional-field additions accepted9/109/10
Alternative designs accepted20/2520/25

The judges are most sensitive to tool- and field-level errors. For relational errors, the audit counts should be read as conservative.

Given the tight timeline, we use LLM audit: two independent judges from different model families, validated on the controlled mutations above, with every jointly flagged case verified manually. In the final version, we will add human audit for those transitions.

4. Task executability

Tasks are sampled from each version's executable tool contracts, and every reference-trajectory state is executed; a task is kept only if all states succeed. In a set of 200 tasks generated by this pipeline, all reference trajectories executed successfully. Sixteen of these tasks belong to versions with deprecated tools, and none calls a deprecated tool.

5. Manuscript changes

We will separate three assessment targets in Sections 4.2 and 5.2:

  1. Intent–edit consistency of the graph specification;
  2. Targeted behavioral correctness against explicit references;
  3. Task executability.

We will also add the audit protocol, the judge assessment and both case studies to Appendix A.2, marked as additional assessments.

Reviewer_ABBYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ProEvolve, a framework for automatically constructing evolving environments to evaluate LLM tool-calling agents. ProEvolve represents an environment as a typed relational graph and supports three types of evolution: capability addition, access-path reorganization , and capability removal. The author conduct experiments on e-commerce and airline booking.

Critical strengths
  1. The setting of evaluating agents under evolving tools is interesting and practically meaningful.
  2. The experiments seem to be solid, with multiple total evolved environment candidates and 3,300 task sandboxes. The evaluation includes both human audits and LLM-as-a-judge consistency checks.
Critical weaknesses
  1. One concern is the framework is evaluated using only three predefined evolutions (Completion, Saturation, and Deprecation), but real-world environments includes more changes. It is unclear whether the proposed approach can effectively handlemore complex evolution patterns.

  2. The paper includes a tedious appendix, so whether the main context is complete and consistent is questionable.

  3. More ablation studies are needed to establish whether the graph-based formulation improves environment correctness or task quality.

Questions for authors

see weakness

2 comments
AuthorsOpenReview ↗

Response to reviewer ABBY

Thank you for recognizing the practical value of evolving tool-calling environments. We address composition, main-text clarity, and the role of graph guidance below.

W1. Can the three primitives support more complex evolution?

The benchmark already includes composed evolution, and the framework's objective is scalable, controllable change rather than an exhaustive taxonomy of real-world updates. Section 3 defines this objective through scalable coherence and controlled versioned dynamics; Section 4.2 explicitly states that the three primitives are not intended to cover all possible changes.

Our evaluated compositions are Completion → Saturation → Deprecation across 50 e-commerce and five airline trajectories (Section 5.1). Each edit operates on its evolved predecessor: capability additions alter the structure available for subsequent access-path reorganization and removal. Tables 2 and 16 evaluate agents along these cumulative lineages. The evaluated setting therefore includes successive, interacting changes, not only isolated primitive applications.

We will emphasize this cumulative composition in Section 4.2 and connect it explicitly to the evaluated version trajectories in Section 5.1.

W2. Tedious appendix, questions regarding completeness and consistency

The appendix already includes a Table of Contents indexing the evaluation protocols, supplementary results, examples, and implementation details. To further shorten it, we will remove code-level implementation details already provided in the accompanying code, while retaining the protocols and evidence needed to interpret and reproduce the results.

We would appreciate pointers to any passages or missing details that raised concerns about completeness or consistency, so that we can address them more precisely.

W3. Does graph guidance improve correctness or task quality?

The graph enables scalable, controllable evolution by explicitly representing capability changes and linking environment implementation to version-grounded task construction. It also provides an explicit reference for implementation-fidelity assessment. Functional behavior and task quality are evaluated through execution checks and semantic rubrics; these assessments are distinct from structural graph validity.

Construction requirementGraph-guided mechanismFree-form generation without explicit dependency/edit machinery
Version-linked capability changesTyped edits identify affected schemas, tools, and dependenciesNatural-language intent expresses the change; structured bookkeeping requires an additional mechanism
Linking implementation and assessmentThe graph diff specifies intended structural changes against which implementation fidelity can be assessedEquivalent traceability requires mapping intended changes to code and checks
Version-grounded tasksTask subgraphs and relational materialization use the evolved graphEquivalent grounding requires task-to-version mapping and dependency resolution
Difficulty controlGraph-path and operation constraints operationalize difficulty targetsDifficulty labels convey the requested level

The new task-level comparison links this controllability to significantly greater difficulty separation. Graph-guided construction turns difficulty targets into explicit path and operation constraints. Evaluating the resulting tasks with GPT-5 under the same agent-evaluation setup, state-wise success rates CC decrease monotonically from .73 to .61 to .45, compared with .86, .89, and .75 for free-form generation prompted with easy/medium/hard labels. The easy–hard gap is .28 ± .06 versus .11 ± .11, with a between-generator gap difference of .17 ± .13 (z = 2.62, p ≈ .009). ± denotes 95% CI half-widths; z uses SE = half-width/1.96 on unrounded values. Mean success across the three levels is .60 versus .83. This provides downstream evidence for explicit difficulty control: the graph-guided workload exhibits a clearer gradient and greater performance separation across the intended difficulty levels.

The graph makes version-specific schemas, tools, and dependencies explicit; executable tool logic implements behavioral conditions, while executable checks and semantic assessments evaluate the resulting environments and tasks (Table 1).

We will clarify the graph's cross-stage mechanism and its relationship to these assessments in Sections 4.1–4.3, and add the difficulty comparison to Section 5.2.

Dear reviewer ABBY,

We are grateful for the useful comments provided by you. We hope that our answers have addressed your concerns. If you have any further concerns, please let us know. We are looking forward to hearing from you.

Best, All authors

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

The authors target an interesting problem of how the agent benchmark should evolve as the agents themselves evolve. The overall motivation is clear and reasonable. The authors model the environment evolution as a typed relational graph, and propose ProEvolve, which evolves tasks in a controllable manner and samples subgraphs for task construction. The authors conduct analyses to verify the validity, quality and utility of the evolved tasks.

Critical strengths

(1) The research question the paper aims to address is novel and practical. Evolving agent benchmarks to simulate the real-world scenario is a big topic and has broader impact in multiple domains, especially where environment updates are critical and a matter of life and deaths, such as clinical environments.

(2) The paper’s strategy of modeling the environment updates in a controllable manner as edits over a relational graph is reasonable. The paper introduces multiple pipeline components to guarantee the validity, quality and utility of task evolution. Extensive empirical experiments are conducted to demonstrate the effectiveness of ProEvolve.

Critical weaknesses

(1) To my point of view, modeling the environment as a graph is a formulation which might limit the application of the proposed method. In some domains, there are no clearly defined graphs, where relations among nodes are ambiguous, such as biology and medicine. For example, the entities might be only partially observed, and their relations might be uncertain and context dependent. The authors should clarify how the framework could handle missing nodes or incorrectly specified edges.

(2) Over the same graph, some tasks might be trivial and some tasks are critical. Uniform sampling over the entire graph doesn’t make sense as it places overly large attention on trivial tasks. I would recommend the authors clearly state how the random subsampling is conducted, and verify how different sampling strategies affect the ultimate outcome.

(3) Although the authors verify the validity, quality and utility of the evolved tasks, an important question is ignored behind these changes: whether the evolution really leads to an improved capability of agent systems? I recommend the authors clearly discuss that and define the limitations of the current framework in the discussion section.

(4) The paper uses the rubric-based judge as a secondary check. However, I think that cannot replace human verification. A small study on a randomly sampled subset of the correlations between LLM judge and human verification could be very helpful.

Questions for authors

(1) Given this work, how would the co-evolution between agent harnesses and environments happen? How could the update in the environment affect the evolution of the harness? More discussion would strengthen the conceptual contribution of the paper.

(2) How does the proposed method handle complicated scenarios where one interaction might involve more than two entities, e.g., the hypergraphs. Some discussions about that would be helpful.

4 comments
AuthorsOpenReview ↗

Response to reviewer 3Xzp [Part 1 /2]

Thank you for recognizing the importance of controllable environment evolution. We address information access, task sampling, co-evolution, and human verification below.

W1. Partial observation, uncertain relations, missing nodes, and incorrect edges

An explicit construction graph does not require complete information on the agent's side. The constructor specifies task-relevant schemas, tools, and dependencies; the agent discovers information through dialogue and tool use. Section 4.3 and Figure 3 describe context as a subgraph that expands during interaction.

ConcernEnvironment-construction viewAgent-interaction view
Partial observationSpecifies task-relevant entities and access pathsInitially hidden facts are obtained through interaction
Uncertain relationsSpecifies underlying relations and admissible conditionsQueries or clarification resolve which entity or relation is intended
Context dependenceRepresents relevant records and conditionsThe target depends on dialogue context and observed state
Missing nodesOmitted concepts require extending the specificationUndisclosed entities become known through dialogue or tool outputs
Incorrect edgesSemantic errors require domain-grounded specification checksIncorrect prior associations can be checked against the current environment

Applicability therefore depends on identifying and modeling the relevant domain structure, as discussed in Appendix C. Less structured or higher-stakes domains additionally require domain expertise, assumptions, and validation. We will clarify the construction–interaction distinction in Sections 4.1 and 4.3 and the domain requirements in Appendix C.

W2. How task sampling affects the final benchmark

Task construction combines version-grounded sampling, difficulty targets, prerequisite materialization, and reference execution; uniform sampling is an adjustable choice. Two comparisons examine difficulty control and final task selection.

1. Construction is more than uniform graph sampling. Section 4.3 samples a connected subgraph and synthesizes its goal and scenario, materializes prerequisite entities and cross-references, and executes a reference traversal to produce state-wise instructions and success criteria. Appendix D illustrates this with a product-exchange task. Section 5.1 balances easy, medium, and hard tasks equally, using state count and operation mix to characterize difficulty (Appendix A.4, Table 8). We will clarify how these targets guide construction, separately from the sampling distribution.

2. Explicit difficulty controls yield clearer performance separation. Graph-path and operation constraints operationalize difficulty targets. We compare ProEvolve with free-form generation prompted with easy/medium/hard labels, evaluating both with GPT-5 under the same agent-evaluation setup.

Task generatorEasyMediumHardEasy − hard
Graph-guided.73 ± .04.61 ± .06.45 ± .04.28 ± .06
Free-form.86 ± .06.89 ± .08.75 ± .10.11 ± .11
Graph − free-form−.13 ± .07−.28 ± .10−.30 ± .11.17 ± .13

Entries report GPT-5 state-wise success rates CC and their differences. ± denotes 95% CI half-widths; z uses SE = half-width/1.96 on unrounded values. The between-generator difference in easy–hard gaps is .17 ± .13 (z = 2.62, p ≈ .009).

Graph-guided tasks show a monotonic decline and better easy–hard separation (.28 versus .11); mean success across levels is .60 versus .83. This links explicit construction controls to task-level difficulty separation.

  1. Selection can further target structure or agent capability. From a common auxiliary pool of 179 tasks passing this experiment's executability and agent-information-access checks**, we select 30 tasks per strategy, holding environment quotas fixed:
  • Uniform: random selection within each environment quota.
  • Structural criticality: weighted sampling using reference-trajectory write count and coverage of evolution-added tools.
  • Capability-conditioned: prioritizing failures from one Opus-4.5 calibration rollout per candidate, filling quota shortages with the lowest-reward successes.

Both models receive two fresh evaluation rollouts per selected task; DeepSeek-V3.2 does not participate in selection.

MetricUniformStructural criticalityCapability-conditioned
DeepSeek-V3.2 state-wise success CC.50.43.33
Opus-4.5 state-wise success CC.75.53.23

Capability-conditioned selection yields lower observed success for both models, including the model not used for selection. These descriptive results on small, overlapping sets show how selection can adjust the benchmark's challenge.

We will expand task construction in Section 4.3, summarize both comparisons in Section 5.2.

AuthorsOpenReview ↗

Response to reviewer 3Xzp [Part 2 /2]

W3 & Q1. Environment evolution as a foundation for agent–environment co-evolution

We agree that co-evolution is a promising direction; ProEvolve provides its scalable, controllable environment-development foundation. Version-linked edits specify capability changes, task construction grounds the workload in each version, and capability-conditioned selection responds to agent feedback, as demonstrated in W2.

Together, these mechanisms support the loop:

compose evolved environments and tasks → select challenges based on current agent capabilities → improve the agent → recalibrate and generate/select the next workload.

This allows a curriculum to evolve in both environment capabilities and agent-relative challenge, rather than only adding harder tasks to an unchanged environment. Agent improvements would be evaluated on held-out evolution lineages, separate from development and calibration tasks.

Our experiments establish environment evolution, diagnostic utility, and capability-conditioned selection; iterative agent updates are the next step. We will clarify this demonstrated foundation and the prospective co-evolution loop in the Conclusion and Appendix C.

W4. Human verification and judge–human agreement

Four annotators independently blind-rated 48 ProEvolve-generated tasks. Agreement between Sonnet-4.5 and aggregated human judgments is:

Evaluation dimensionJudge–human κ
Scenario coherence.76
State-transition feasibility.79
Prerequisite sufficiency.67

Individual-annotator κ ranges are .66–.76 for coherence and .68–.75 for feasibility; prerequisite sufficiency shows more moderate agreement. This provides a dimension-specific human check, distinct from the submission's two-annotator audit.

We will summarize the results in Section 5.2 and document sampling, annotation, and per-dimension agreement in Appendix A.5.

Q2. Interactions involving more than two entities

Pairwise dependency edges do not restrict a tool invocation to two entities. The tool-design specification supports multi-input/multi-output tools (Appendix G.1.2), and sandbox construction jointly materializes prerequisite entities and cross-references (Section 4.3). Appendix D's exchange scenario combines a user, an order, a product variant, and an exchange-eligible order state.

The graph records dependencies and access paths; tool signatures and executable logic specify joint input requirements and behavioral conditions. Graph reachability alone does not establish all invocation preconditions. Hyperedges or operation nodes could represent joint dependencies, while checking behavioral conditions would additionally require explicit contracts and validation.

We will clarify this distinction in Section 4.1, illustrate joint prerequisites in Section 4.3, and state the graph-level behavioral-modeling boundary in the limitations discussion.

Thanks for the detailed responses. The response to W2 has addressed my concerns. However, my main concerns about W1 still hold because the graph doesn't seem critical to benchmark evolution. And because the main innovation in this paper is introducing the use of a graph, this increases my doubt about whether the work possesses sufficient technical depth to be published. I tend to keep my rating as it is.

AuthorsOpenReview ↗

Response to Reviewer 3XZp (follow-up): the role of the graph

Thank you for the follow-up. We are glad the W2 response addressed your concern, and we appreciate the chance to clarify the role of the graph.

The graph is not the core contribution of this paper. Our contribution is a framework that turns static agent benchmarks into evolving ones: environments, tasks and evaluation change together across versions. The graph is the representation that makes this evolution possible under the two properties the framework requires:

  • scalability: many coherent versions, not repeated variations of the same change;
  • controllability: benchmark properties such as difficulty can be set explicitly.

We compared graph-guided generation with free-form generation on both properties, and the graph gives a superior advantage on each.

Scalability: diversity of evolution (Section 5.2, Appendix G). From the same seed environment, with the same model, we generated 50 evolution proposals per method.

MetricGraph-guidedFree-form
Pairwise tool Jaccard distance ↑.976.867
Unique-tool ratio ↑.645.394
Pairwise entity Jaccard distance ↑.979.805
Unique-entity ratio ↑.606.336

All differences are significant (permutation test, p = .001). Free-form proposals repeatedly converge on similar features. Graph-guided proposals are derived from the current structure, so successive evolutions keep introducing different capabilities.

Controllability: task difficulty (Section 5.2, Appendix A.4). With GPT-5 as the agent, success on graph-guided tasks falls from .73 to .61 to .45 across easy, medium and hard. On free-form tasks prompted with the same difficulty labels, success is .86, .89 and .75, so the easy–hard gap is .28 versus .11.

We replicated the comparison with two further agents, Opus 4.5 and DeepSeek-V3.2, scored by state-wise completion. The easy–hard gap is .20 for graph-guided tasks and .06 for free-form tasks. The difference, .14 (95% CI [.06, .22], p < .001), shows that the graph makes difficulty an explicit, controllable property rather than a label the generator may not realize.

Why this matters. Most agent benchmarks today are static snapshots, and existing methods do not evolve the environment itself in a controlled way. ProEvolve makes the environment, its tasks and their evaluation evolve together. We agree that the current approach cannot cover every domain: it applies to environments whose state and tool dependencies can be specified, and less structured domains will need further work (Appendix C). We nevertheless believe that controllable, scalable environment evolution is an important first step toward benchmarks that keep pace with agents. We will state the contribution and the role of the graph in these terms in Section 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.