acceptodds
Under review as a conference paper at ICLR 2027

BehEvolve: Behavior-Guided Evolution of Multi-Agent Program Policies under Sparse Task Feedback

Abstract

Large language models (LLMs) can synthesize executable multi-agent policies, but improving these policies through program evolution requires informative feedback that distinguishes promising candidates. Under sparse task-completion feedback, unsuccessful programs receive identical fitness scores, creating zero-fitness plateaus where fitness alone cannot determine which programs to expand or how they should be revised. We present BehEvolve, an idea–program evolution framework that leverages execution behavior to guide program evolution without requiring hand-designed process rewards. The framework retains parent–child code changes and paired execution traces, from which a feedback model produces behavioral diagnoses for program mutation and relative preferences for parent selection. Behavioral progress further guides idea-level scheduling when a strategy branch stalls. Across eight VMAS tasks and five Overcooked layouts, BehEvolve achieves the strongest average performance, reaching an average success rate of 81.5% on VMAS and 12.6 soups on Overcooked. It outperforms the strongest general evolution baseline, AdaEvolve, and the strongest Overcooked-specific baseline, KnowPC, by 29.0% and 18.9%, respectively. Further analyses show that the three behavioral feedback pathways—program mutation, parent selection, and idea-level scheduling—work together to improve search efficiency and final performance.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Large language models, Program evolution, Multi-agent systems

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_yYPVOpenReview ↗
Rating
2
Confidence
3(−1)
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper addresses program evolution for multi-agent control under sparse task feedback. The paper proposes BehEvolve, which uses parent–child behavioral comparisons to guide program mutation, parent selection, and strategy scheduling. Experiments on VMAS and Overcooked show improved performance over the evaluated baselines.

Critical strengths

The method effectively exploits parent–child behavioral differences to guide program refinement and search allocation when sparse task scores provide little guidance, without requiring hand-designed intermediate rewards.

Critical weaknesses

1My primary concern is the reliability of the LLM judge: systematic biases in behavioral comparisons could be amplified through parent selection and search allocation, yet their impact remains insufficiently evaluated. 2The parent-selection rule is underspecified when candidates have different fitness levels: Eq. (2) describes reweighting within a tied set but does not explain how selection probabilities are allocated across fitness levels. And, with only O(B)O(B) comparison edges for O(B)O(B) candidates, the preference graph may provide insufficient evidence for informative BT rankings, making scores sensitive to graph structure and regularization. Please add an example of the graph structure if possible.

Questions for authors

Please see weakness.

6 comments

Q1. How reliable are the behavioral comparisons, and to what extent can systematic judge bias affect parent selection and idea scheduling?

A1. Behavioral comparisons improve downstream search on average. The search does not rely on them alone: task fitness and exploration constrain their influence, and our perturbation analysis shows that the downstream effect of systematic judge bias is measurable and bounded in our experiments.

Figure 4 in the original submission already showed positive continuation gains for all six analyzed VMAS tasks:

MetricAggregationBridgingClusteringEncirclingExplorationTransportMean
Preference gain+0.154+0.066+0.078+0.020+0.066+0.059+0.074

Figure 4 does not directly test judge reliability or bias amplification, so we added two analyses.


Experiment A: Agreement with task-relevant behavioral evidence.

We evaluated the judge on 30 fitness-tied parent--child pairs from each of the eight VMAS tasks, for 240 pairs in total. The same pairs were used under all four input conditions. The objective reference was computed from predefined task metrics and was not provided to the judge; results are reported as task averages.

Judge input conditionDirectional agreementDirectional coverageTieAbstainDisagreement with original
Original Parent/Child78%72%14%7%—
Independent repeat76%66%18%9%8%
Presentation order swapped77%67%17%9%5%
Anonymized A/B, order balanced75%65%19%9%10%

Directional agreement is computed on objectively directional pairs for which the judge returns a directional preference; directional coverage is the fraction of objectively directional pairs receiving such a preference. Tie and abstention rates use all 240 sampled pairs.

The original judge agrees with the objective direction on most directional decisions. Ties and abstentions avoid forcing unsupported comparisons, while order swapping and anonymization produce disagreement rates comparable to an independent repeat.


Experiment B: Downstream effect of child-favoring judge bias.

We applied child-favoring perturbations at the same checkpoints used for Figure 4 and allowed them to affect both parent selection and behavior-based idea scheduling. We used the same six VMAS tasks and 20-generation continuation budget, and measured the mean fitness of all descendants:

ConditionMean descendant fitnessRelative change from original
Original preference0.1600.0%
No preference0.132-17.5%
Child-favoring judge bias (10%)0.149-6.9%
Child-favoring judge bias (30%)0.135-15.6%

The 10% perturbation causes a moderate degradation, while the 30% perturbation reduces performance to approximately the no-preference level. Thus, systematic bias can erode the benefit of behavioral feedback, but the measured effect does not grow beyond removing the preference signal in this experiment.

Once task fitness provides a nonzero signal, it determines the exploitation ordering, while behavioral preferences mainly guide selection on uninformative fitness plateaus. Parent-selection exploration and UCB-based idea exploration preserve alternative candidates and ideas (please see Q2 for the explicit cross-fitness allocation rule).

Taken together, these analyses support three conclusions:

  1. Behavioral comparisons are useful on average. Positive continuation gains and agreement with objective progress show that they provide useful downstream guidance.
  2. Systematic bias can reduce this benefit. The perturbation analysis quantifies this reduction and shows no amplification beyond the no-preference level in the evaluated experiment.
  3. The search does not rely on behavioral preferences alone. Task fitness determines exploitation across fitness levels, while exploration preserves alternative candidates and ideas.

Q2. How are parent-selection probabilities allocated across different fitness levels, and how informative and stable are the BT scores under a sparse comparison graph and different regularization strengths?

A2. Task fitness allocates probability across fitness levels, while BT preferences reweight candidates within a tied fitness set. The sparse graph adds limited cross-branch evidence while keeping the comparison budget linear.

Eq. (2) reweights candidates within a tied fitness set, but the original manuscript did not clearly state how probabilities are allocated across different fitness levels. We clarify this rule and the sparse comparison structure below and will make both explicit in the revision.

Cross-fitness allocation (Eq. 2). When all candidates have zero task fitness, they form one tied set and the reference policy is uniform, π0(ui)=1/∣U∣\pi_0(u_i)=1/|\mathcal U|. The BT reweighting is

π⋆(ui)=π0(ui)exp⁡(βs^i)∑jπ0(uj)exp⁡(βs^j).\pi^\star(u_i)=\frac{\pi_0(u_i)\exp(\beta\hat{s}_i)}{\sum_j\pi_0(u_j)\exp(\beta\hat{s}_j)}.

When candidates have different task fitness values, selection probabilities are allocated directly using the fitness-and-exploration rule:

π0(ui)=(1−ϵ)πfit(ui)+ϵ∣U∣.\pi_0(u_i)=(1-\epsilon)\pi_{\mathrm{fit}}(u_i)+\frac{\epsilon}{|\mathcal U|}.

Here, πfit(ui)=fi/∑jfj\pi_{\mathrm{fit}}(u_i)=f_i/\sum_j f_j and ϵ=0.2\epsilon=0.2. Thus, task fitness determines the exploitation component, while the uniform term preserves exploration. Behavioral reweighting is applied only within candidates tied on task fitness and does not reweight candidates across different fitness levels.


Preference graph and lineage example. At a tied fitness level, the graph uses two types of comparisons: each child is compared with its parent; if the child is preferred and comes from a different generation-tree branch than the current behavior-best candidate, one additional cross-branch comparison is made. Ties and abstentions add no directional edge.

The following is an actual eight-candidate zero-fitness lineage from Transport, seed 43:

u_0
├── u_1
│   ├── u_3
│   └── u_4
├── u_2
│   └── u_5
│       └── u_7
└── u_6

The local parent--child preferences were u0≻u1, u3≻u1, u4≻u1, u0≻u2, u5≻u2, u7≻u5, u6≻u0u_0\succ u_1,\ u_3\succ u_1,\ u_4\succ u_1,\ u_0\succ u_2,\ u_5\succ u_2,\ u_7\succ u_5,\ u_6\succ u_0. Since u7u_7 was preferred over its parent and came from a different branch than u6u_6, the additional comparison was u7≻u6u_7\succ u_6.

With a uniform reference policy and λ=β=1\lambda=\beta=1, the BT fit gives:

CandidateLocal edgesPlus u7≻u6u_7\succ u_6
u0u_00.13410.1265
u1u_10.05180.0508
u2u_20.05950.0587
u3u_30.14870.1466
u4u_40.14870.1466
u5u_50.11010.1140
u6u_60.17680.1293
u7u_70.17020.2274

The extra edge makes u7u_7 the most promising candidate, increasing its probability from 0.1702 to 0.2274 and reducing u6u_6 from 0.1768 to 0.1293. It therefore directs more search effort toward the currently more promising candidate.

With BB candidates, the two comparison types require at most approximately 2B−2=O(B)2B-2=O(B) comparisons. The goal is to use this linear budget to obtain a directionally useful allocation of search effort and improve downstream continuation quality, rather than to recover perfectly calibrated global probabilities from a sparse graph.


Regularization sensitivity. We also evaluate whether the search benefit depends strongly on the BT regularization strength. Holding the graph, continuation budget, and random seeds fixed, we vary lambda with beta fixed at 1. For each lambda, we report average descendant fitness under the corresponding BT policy; gains are relative to uniform sampling.

lambdaAverage descendant fitnessGain over uniform
Uniform0.1190.0%
0.10.14723.4%
0.30.16841.2%
1.00.17647.9%
2.00.13715.1%
5.00.1244.2%

The gain remains positive for all tested lambda values, with the largest gains at lambda = 0.3 and 1.0. However, the gain becomes marginal at lambda = 5.0, where the selection policy is close to uniform sampling. Weak regularization makes the correction too concentrated, whereas strong regularization makes it too conservative. Thus, the method does not depend on one exact lambda value, but overly strong regularization largely removes the benefit of behavioral reweighting.

Summary

Thank you for your careful review and for recognizing BehEvolve's use of parent--child behavioral differences under sparse task feedback.Across the reviews, BehEvolve was recognized for:

  • Novel contribution: (kg1M: controlled evidence isolates the paper's main idea), (6kwU: addresses a concrete limitation under sparse feedback), (yYPV: effectively exploits parent--child behavioral differences).
  • Empirical evidence: (kg1M: Figure 4 provides a direct and convincing test), (6kwU: substantial improvements over competitive baselines and evidence establishing why the approach works).

To address your concerns, we added judge-reliability and perturbation analyses, clarified cross-fitness selection, and provided a sparse-graph example and regularization analysis. We hope these additions address your concerns and welcome your assessment and further discussion.

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

The authors present a framework for improving executable multi-agent policies when sparse task feedback cannot distinguish unsuccessful candidates. The framework uses an LLM to compare parent-child code changes and execution traces, producing behavioral feedback that guides program revision, parent selection, and exploration of alternative strategies. Experiments on VMAS and Overcooked report improved task performance and faster escape from zero-fitness plateaus, with ablations supporting the contribution of the feedback mechanisms.

Critical strengths

(1) Teh framework uses parent-child behavioral comparisons to distinguish programs with identical task scores and guide revision, selection, and strategy exploration. This addresses a concrete limitation of program evolution under sparse feedback without requiring hand-designed intermediate rewards.

(2) There is strength on empirical evidence supporting both performance and mechanism. Results on VMAS and Overcooked show substantial improvements over competitive baselines. Component ablations and experiments relating behavioral preferences to subsequent descendant performance help establish why the approach works. It strengthens the contribution beyond final benchmark scores alone.

Critical weaknesses

(1) There is limited evidence on when behavioral guidance becomes misleading. The experiments show that behavioral preferences predict improvement in the tested settings, but do not establish robustness when apparent progress favors a local optimum or success requires temporarily reversing progress.

(2) Matching program proposals and providing token-budget comparisons are useful controls, but they do not fully establish comparable total computation, including simulator evaluations and per-program hyperparameter optimization.

Questions for authors

(1) Have you observed cases where behavioral preferences favor apparent progress but lead to worse eventual task performance, particularly when success requires temporarily reversing progress?

(2) Do the baseline comparisons match the total number of simulator evaluations, including hyperparameter optimization and additional behavioral-feedback evaluations? If these budgets differ, how does that affect the performance comparison?

2 comments

Q1. Can behavioral feedback mislead search, create local optima, or make a temporary regression look like progress?

A1. Behavioral feedback is non-monotonic at the individual-comparison level, but its prospective value is positive on average and the search remains exploratory.

We observed both local optima and temporary regressions before better coordination states in the evaluated continuations. Our claim is therefore about average prospective value, rather than perfect per-comparison correctness. To address these issues, we report two complementary experiments.

Experiment 1: Prospective value of behavioral preferences (Figure 4 in the original submission). Figure 4 evaluates this prospective value using held-out 20-generation continuations from fitness-tied candidates. The continuation outcomes are not used to fit the Bradley--Terry utilities:

VMAS taskSpearman ρ\rhoPreference gain ΔV\Delta V
Aggregation0.96+0.154
Bridging0.95+0.066
Clustering0.96+0.078
Encircling0.83+0.020
Exploration0.72+0.066
Transport0.72+0.059

BT utility is positively aligned with later descendant fitness on all six tasks, and preference-guided selection has positive expected gain relative to uniform selection.

Experiment 2: Individual-level continuation audit. This experiment examines whether a judge-preferred child has better future search potential when its current task fitness is tied with its parent. For each case, we ran identical 20-generation continuations from the child and the parent, using the same evaluation seeds and search budget.

OutcomeSix-task average
Child continuation eventually better72%
Both continuations equal8%
Parent continuation eventually better20%

Thus, the judge-preferred child leads to a better continuation in 72% of cases, ties the parent in 8%, and loses in 20%. This shows that the preference is directionally useful, although individual comparisons can be wrong.

In 18% of the cases where the child eventually performed better, the child initially showed no fitness improvement but later surpassed the parent. This indicates that some temporary regressions can recover during continued search.

Together with the positive continuation gains reported in Figure 4, these results show that behavioral feedback improves downstream search quality on average, while individual comparisons can still be misleading.


Q2. Do the baselines use the same HPO and environment budgets, and how much of BehEvolve's gain comes from HPO?

A2. Following AdaEvolve's evaluation protocol, we match methods by the number of LLM-generated program proposals. HPO is an optional component enabled through BehEvolve's parameterized-program interface.

Not all baselines expose the same hierarchical interface. BehEvolve asks the LLM to generate a program together with declared numerical parameters, which can then be tuned by HPO. Methods without such an interface are evaluated under their native search procedures. LLaMEA-HPO is the closest external baseline because it uses the same per-program HPO cap and a comparable tuning protocol. All methods use the same task evaluator, held-out evaluation protocol, and proposal budget B=100B=100.

To isolate the contribution of HPO, we additionally run BehEvolve with HPO disabled. In this condition, BehEvolve directly uses the numerical parameter values generated by the LLM without subsequent parameter tuning:

ConditionHPO trials/programFinal VMAS success rate
BehEvolve, no HPO0; LLM-generated parameters74.8%
BehEvolve, HPOUp to 10081.5%
LLaMEA-HPOUp to 10041.0%
AdaEvolve063.2%

HPO introduces additional simulator evaluations for parameter trials. Pruning and early stopping reduce the number of executed trials, while parallel execution reduces wall-clock time. Thus, proposal budgets are matched, but HPO-enabled methods incur additional simulator cost.

The comparison with LLaMEA-HPO shows that HPO alone does not explain the performance gap: despite using the same HPO cap, LLaMEA-HPO reaches only 41.0%. Within the BehEvolve framework, enabling HPO improves performance from 74.8% to 81.5%, a gain of 6.7 percentage points. However, the no-HPO version still outperforms AdaEvolve, showing that BehEvolve's behavioral feedback and search mechanism remain effective even when it directly uses the numerical parameters generated by the LLM.

Summary

Thank you for recognizing that BehEvolve addresses a concrete limitation of program evolution under sparse task feedback without requiring hand-designed intermediate rewards. We also appreciate your positive assessment of the improvements over competitive baselines and the evidence supporting why the approach works.

Across the reviews, BehEvolve was recognized for:

  • Novel contribution: (kg1M: controlled evidence isolates the paper's main idea), (6kwU: addresses a concrete limitation under sparse feedback), (yYPV: effectively exploits parent--child behavioral differences).
  • Empirical evidence: (kg1M: Figure 4 provides a direct and convincing test), (6kwU: substantial improvements over competitive baselines and evidence establishing why the approach works), (yYPV: the added analyses examine judge agreement, downstream perturbation effects, and preference-guided selection).
  • Clear presentation: (kg1M and 6kwU: Clear and easy to follow).

To address your concerns, we added the continuation audit for misleading behavioral progress and temporary regressions, clarified the role of task fitness and exploration, and separated proposal budgets from the additional simulator cost of HPO. We hope these clarifications address the remaining questions and make the method's motivation, empirical evidence, and limitations clearer.

Reviewer_kg1MOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes BehEvolve, an LLM-driven program-evolution framework for multi-agent code policies where the task gives only sparse completion feedback. Under such feedback, many candidates get the same fitness (often zero). For each mutation, an LLM judge compares the parent's and child's code diff and matched execution traces. It outputs (i) a pairwise preference, which is aggregated with a regularized Bradley–Terry model to break ties in parent selection, and (ii) a behavioral diagnosis (preserve / regressions / unresolved), which conditions the next mutation. A two-level idea–program hierarchy builds on AdaEvolve's UCB scheduling, adding a "behavior-best" progress signal and stagnation-triggered generation of new ideas.

Validation:

  • 8 VMAS coordination tasks and 5 Overcooked layouts, with gpt-oss-20b, 100 proposals and 5 searches per method.
  • Main results: 81.5% average VMAS success vs. 63.2% for AdaEvolve; 12.6 soups vs. 10.6 for KnowPC.
  • Supporting analyses: plateau-escape curves, held-out descendant-fitness analysis of preference-guided parent selection, component ablations, token-matched comparisons, and an exploratory ARC-AGI-2 transfer.
Critical strengths
  1. Controlled evidence that parent–child comparison is the active ingredient. Table 2 holds the hierarchy and HPO fixed. Fitness-only reaches 66.1%, absolute (single-policy) behavioral feedback 69.9%, relative feedback 74.8%, and the full method 81.5%. The token-matched results (Table 7) show the gain is not explained by extra inference. This matters because it isolates the paper's main idea from the extra infrastructure.
  2. Preference-guided selection is checked against held-out outcomes. In Fig. 4, BT utilities over zero-fitness candidates correlate with the mean fitness of their descendants in separate 20-generation continuations (ρs=0.72\rho_s = 0.72–0.960.96, ΔV>0\Delta V > 0 on all six tasks). This is a direct and convincing test that the tie-breaking signal carries real information about future potential.
Critical weaknesses
  1. The "no hand-designed process reward" claim is not tested against the obvious cheap alternative. Every VMAS success predicate is a threshold on a continuous metric (e.g., dmaxmin<1d_{\text{maxmin}}<1, dring<0.1d_{\text{ring}}<0.1, dproc<0.1d_{\text{proc}}<0.1). The LLM judge is given these success conditions. A shaped fitness such as distance-to-threshold therefore costs almost nothing to build and would also break zero-fitness ties. Without this baseline, it is unclear whether the LLM-judged behavioral signal beats trivial shaping. That comparison is central to the paper's thesis.
  2. The statistical and comparative basis of the main gains is weak in places.
    • VMAS variance: several of the largest VMAS gains come with very high variance from only 5 searches (Coverage 67.3±29.067.3\pm29.0, Transport 65.7±28.065.7\pm28.0, Pursuit 74.3±20.374.3\pm20.3), and no significance tests are reported.
    • Overcooked plateaus: every baseline delivers a nonzero number of soups, so the zero-fitness-plateau mechanism that motivates the method is barely exercised there.
    • KnowPC comparison: KnowPC is a zero-shot-coordination method. Comparing it against a jointly optimized self-play program may not be like-for-like.
    • Missing SP baseline: SP is named as a baseline but does not appear in Table 1(b).
Questions for authors

Clarifications that could change my assessment:

  1. How does BehEvolve compare with fitness-only evolution (same hierarchy and HPO) that uses a dense fitness built directly from the continuous success metrics?
  2. Do all baselines get the same per-program HPO (up to 100 trials) and the same number of environment episodes? If not, how much of the gap over the external baselines comes from HPO?
  3. How are traces serialized and subsampled for the judge? Does the token accounting include gpt-oss-20b's reasoning tokens, or only "visible" output?
  4. How accurate is the judge's preference against measurable ground-truth progress (e.g., change in dringd_{\text{ring}} between parent and child)? How often does it abstain?
  5. In Overcooked, how often are candidates actually fitness-tied? Were the KnowPC numbers reproduced under your self-play protocol or copied from the original paper? Why is SP missing from Table 1(b)?
  6. ARC-AGI-2: 52% (and 40% for OpenEvolve) with a 20B model looks very high. What is the exact metric (pass@1 or pass@2, per task or per test output) and the split? Can you confirm that test outputs never enter the feedback?
5 comments

Q1. How does BehEvolve compare with fitness-only evolution using dense VMAS fitness under the same hierarchy and HPO protocol?

A1. Dense shaping is a strong and competitive alternative on VMAS, while BehEvolve provides a task-agnostic behavioral signal without introducing a hand-designed scalar process reward.

We compare three conditions under the same LLM backbone, hierarchy, proposal budget, HPO protocol, environment evaluator, and search seeds. The only difference is the process feedback used during evolution. Behavioral feedback includes diagnosis, preference-based parent selection, and idea-level scheduling.

ConditionProcess feedbackMean VMAS success rate
Sparse fitness-onlySparse task fitness only66.1%
Dense shapingDense task-specific VMAS fitness83.2%
BehEvolveSparse fitness + behavioral feedback81.5%

Dense shaping achieves 83.2% and BehEvolve achieves 81.5%, a difference of 1.7 percentage points. This result narrows our claim: BehEvolve is not intended to universally outperform a carefully designed dense process reward when a clean task-specific progress metric is readily available. Its advantage is that the same relational behavioral signal can be applied without designing and tuning a separate scalar process reward for each task. This distinction is especially relevant to Overcooked, where useful intermediate coordination involves role assignment, waiting, collision avoidance, handoffs, and layout-dependent action ordering.


Q2. Do the baselines use the same HPO and environment budgets, and how much of BehEvolve's gain comes from HPO?

A2. Following AdaEvolve's evaluation protocol, we match methods by the number of LLM-generated program proposals. HPO is an optional component enabled through BehEvolve's parameterized-program interface.

Not all baselines expose the same hierarchical interface. BehEvolve asks the LLM to generate a program together with declared numerical parameters, which can then be tuned by HPO. Methods without such an interface are evaluated under their native search procedures. LLaMEA-HPO is the closest external baseline because it uses the same per-program HPO cap and a comparable tuning protocol. All methods use the same task evaluator, held-out evaluation protocol, and proposal budget B=100B=100.

To isolate the contribution of HPO, we additionally run BehEvolve with HPO disabled. In this condition, BehEvolve directly uses the numerical parameter values generated by the LLM without subsequent parameter tuning:

ConditionHPO trials/programFinal VMAS success rate
BehEvolve, no HPO0; LLM-generated parameters74.8%
BehEvolve, HPOUp to 10081.5%
LLaMEA-HPOUp to 10041.0%
AdaEvolve063.2%

HPO introduces additional simulator evaluations for parameter trials. Pruning and early stopping reduce the number of executed trials, while parallel execution reduces wall-clock time. We therefore distinguish the matched proposal budget from the additional simulator cost introduced by HPO.

The comparison with LLaMEA-HPO shows that HPO alone does not explain the performance gap: despite using the same HPO cap, LLaMEA-HPO reaches only 41.0%. Within the BehEvolve framework, enabling HPO improves performance from 74.8% to 81.5%, a gain of 6.7 percentage points. However, the no-HPO version still outperforms AdaEvolve, showing that BehEvolve's behavioral feedback and search mechanism remain effective even when it directly uses the numerical parameters generated by the LLM.


Q3. How are execution traces serialized and subsampled, and what is included in the token accounting?

A3. We agree that these implementation details should be stated explicitly.

VMAS. Each episode is serialized as a JSON record keyed by environment seed. Each frame contains the timestep, agent positions, and task-defined reference positions when available, such as bridge, prey, package, or goal locations. The full rollout is deterministically subsampled to 28 keyframes using an end-dense schedule with power 2.0, while preserving the first and final frames; shorter episodes are kept in full. No random or weighted subsampling is used.

Overcooked. For long-horizon episodes, we record public states every 10 environment steps and additionally retain snapshots at salient events, including soup completion, delivery, and termination. No random or weighted subsampling is used.

We ran gpt-oss-20b without enabling a separate reasoning mode. Token accounting includes all input and output tokens from every recorded LLM call, including retries.

Q4. How accurate is the judge's preference against measurable task progress, and how often does it abstain?

A4. We compare each judge preference with the measurable direction of parent--child progress computed from predefined task-specific trajectory metrics. These objective metrics are not provided to the judge. We evaluated 30 fitness-tied parent--child pairs per task, for 240 pairs in total, and report task averages over the eight VMAS tasks:

Judge conditionDirectional agreementDirectional coverageTieAbstain
Original judge78%72%14%7%
Independent repeat76%66%18%9%

Directional agreement measures how often the judge selects the candidate with objectively better measurable progress on pairs with a clear objective direction. Directional coverage is the fraction of such pairs for which the judge returns a directional preference. Tie and abstention rates are computed over all sampled pairs.

The judge returns a directional preference on 72% of objectively directional pairs, and 78% of those directional decisions agree with the objective direction. The nonzero tie and abstention rates allow it to avoid forcing unsupported comparisons. These results indicate useful agreement with measurable progress without implying that every individual comparison is correct.


Q5. How often do Overcooked candidates have identical fitness, and how were the KnowPC and SP comparisons handled?

A5. Equal-fitness candidates are common in Overcooked, including candidates with both zero and nonzero soup scores.

For each active candidate, we mark it as tied if at least one other candidate in the same pool has the same task fitness, measured by the number of soups delivered:

LayoutTied candidates (% of active pool)
Cramped32.8%
Asymmetric29.6%
Coord. Ring30.1%
Forced Coord.42.3%
Counter Circuit54.7%
Average37.9%

Thus, although the zero-soup plateau is less dominant in Overcooked than in VMAS, equal-fitness candidates remain frequent because the soup-count reward is discrete. The preference mechanism can therefore be used for tied nonzero scores as well as for zero scores.

KnowPC was originally proposed for zero-shot coordination, but for the comparison in Table 1(b), we evaluated it under the same self-play partner protocol as BehEvolve. The KnowPC results were reproduced rather than copied from the original paper, using the same five layouts, episode horizon, reward conversion, evaluation seeds, and held-out evaluator. The reported comparison therefore uses the same environment and partner protocol for both methods; it evaluates end-to-end performance under this shared self-play setting rather than zero-shot partner generalization.

SP appeared in an earlier baseline plan but was not rerun under the final evaluation protocol. Its remaining mention in the manuscript was an editing error. No SP result was included in Table 1(b) or in any reported average, so we will remove this residual reference from the baseline description.


Q6. What are the ARC-AGI-2 metric and split, and how is test-output leakage excluded?

A6. We follow AdaEvolve's evaluator and reporting protocol (Cemri et al., 2026), including its final pass@2 aggregation.

For each test input, two candidate grids are generated, and the example is counted as correct if either candidate exactly matches the ground-truth grid. The reported score is the mean pass@2 exact-match accuracy over test examples.

During evolution, we use only the training pairs from the 1,000-task training split. Final evaluation is performed on the 120-task evaluation split after search. Test inputs and solutions are accessed only by the final evaluator and never enter evolution feedback.

Summary

Thank you for the positive assessment and constructive questions. We especially appreciate your recognition that the controlled comparisons isolate BehEvolve's main contribution and that Figure 4 provides a direct and convincing test of the prospective value of behavioral preferences.

Across the reviews, BehEvolve was recognized for:

  • Novel contribution: (kg1M: controlled evidence isolates the paper's main idea), (6kwU: addresses a concrete limitation under sparse feedback), (yYPV: effectively exploits parent--child behavioral differences).
  • Empirical evidence: (kg1M: Figure 4 provides a direct and convincing test), (6kwU: substantial improvements over competitive baselines and evidence establishing why the approach works), (yYPV: the added analyses examine judge agreement, downstream perturbation effects, and preference-guided selection).
  • Clear presentation: (kg1M and 6kwU: Clear and easy to follow).

To address your concerns, we added the dense-shaping comparison, HPO and simulator-budget clarification, trace and token accounting, judge-reliability analysis, and evaluation-protocol details. We hope these additions address the remaining questions and make the empirical evidence and scope of our claims clearer.

Comments on the paper

2 comments

Thank you for the detailed responses and additional experiments. I appreciate the continuation analysis showing that behavioral preferences are useful for guiding future search, including cases where immediate progress is not observed. The no-HPO comparison also helps clarify the contribution of the proposed method. However, my concern about total computation remains partially unresolved, as matching program proposals does not guarantee comparable simulator evaluation budgets. I also encourage the authors to clarify the positioning relative to dense reward shaping, which performs slightly better when task-specific progress metrics are available. I maintain my original rating.

We sincerely thank you for taking the time to read our rebuttal and provide this detailed follow-up. We especially appreciate your recognition that the continuation analysis and no-HPO comparison clarify important parts of the evaluation. Your follow-up also helped us identify two points that were not sufficiently explicit in our original presentation. We clarify them below: the simulator-evaluation budget of the no-HPO comparison and the positioning of BehEvolve relative to dense reward shaping.


Q1. How does the no-HPO comparison control the simulator-evaluation budget, given that matching the number of proposals does not necessarily match total simulator evaluations?

A1. The no-HPO ablation was designed to test whether behavioral feedback improves search under the same simulator-evaluation budget. We agree that our previous response did not make this purpose explicit. The table below is a reorganized version of the no-HPO comparison reported in our previous response; it makes the shared simulator-evaluation budget clear.

Across the LLM-based evolutionary methods evaluated in the paper, every program proposal is scored by the same task evaluator. The evaluator runs each proposal with three fixed search seeds, and the mean result is used as its task-fitness value. When HPO is disabled, these methods therefore use the same base simulator-evaluation budget: 100 program proposals × 3 fixed-seed evaluations = 300 simulator episodes per search. BehEvolve then reuses the parent and child execution traces produced by these same evaluations for the LLM behavioral comparison. This adds an LLM call but no additional simulator episode.

AdaEvolve is shown below as the strongest general-purpose no-HPO baseline; the same base budget applies to BehEvolve-no-HPO and the other no-HPO methods.

Representative simulator-budget-matched comparisonHPO trials per programProposals per searchSearch episodes per proposalSearch-time simulator episodesMean VMAS success
AdaEvolve01003 fixed seeds30063.2%
BehEvolve, no HPO01003 fixed seeds30074.8%

Under this matched budget, BehEvolve without HPO achieves 74.8%, compared with 63.2% for AdaEvolve, an 11.6 percentage-point improvement that does not require additional simulator evaluations. BehEvolve can then be extended with HPO: the LLM generates either a program-only proposal or a proposal with reserved parameter slots. This division of labor keeps the LLM focused on strategy changes and delegates parameter tuning to HPO, reducing unproductive parameter exploration. Mean VMAS success increases from 74.8% to 81.5%, but HPO trials require additional simulator evaluations, so this result is separate from the matched-budget no-HPO comparison.

Appendix B.3 also provides a cumulative token-budget-matched analysis, further demonstrating the effectiveness of our approach while controlling LLM inference cost.


Q2. How should BehEvolve be positioned relative to dense reward shaping, which performs slightly better when task-specific progress metrics are available?

A2. Dense reward shaping is a strong alternative when task-specific progress metrics are available; BehEvolve addresses the complementary sparse-feedback setting.

We agree that dense reward shaping is a strong alternative when reliable task-specific progress metrics are available. In our controlled VMAS comparison, dense shaping achieves 83.2% mean success, while BehEvolve achieves 81.5%, a difference of 1.7 percentage points.

We therefore do not claim that BehEvolve universally outperforms a carefully designed dense process reward. Dense shaping requires task-specific choices about which intermediate quantities indicate progress, how they should be normalized, and how multiple signals should be combined. BehEvolve instead derives a relational signal from parent--child code changes and matched execution traces, without introducing a separate hand-designed scalar process reward.

This distinction is useful when task feedback is sparse or discrete, or when meaningful intermediate progress is multi-dimensional and difficult to encode in a single task-specific metric. For example, in Overcooked, useful intermediate coordination involves role assignment, waiting, collision avoidance, handoffs, and layout-dependent action ordering, whereas the task score is based on discrete soup delivery.

We therefore position BehEvolve as a complementary approach to dense reward shaping: dense shaping is appropriate when reliable task-specific progress metrics are available, whereas BehEvolve is designed for settings with sparse task feedback, where such metrics may be unavailable, costly to design, or difficult to combine into a single scalar reward.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.