- 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 comparison edges for 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
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, . The BT reweighting is
When candidates have different task fitness values, selection probabilities are allocated directly using the fitness-and-exploration rule:
Here, and . 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 . Since was preferred over its parent and came from a different branch than , the additional comparison was .
With a uniform reference policy and , the BT fit gives:
| Candidate | Local edges | Plus |
|---|---|---|
| 0.1341 | 0.1265 | |
| 0.0518 | 0.0508 | |
| 0.0595 | 0.0587 | |
| 0.1487 | 0.1466 | |
| 0.1487 | 0.1466 | |
| 0.1101 | 0.1140 | |
| 0.1768 | 0.1293 | |
| 0.1702 | 0.2274 |
The extra edge makes the most promising candidate, increasing its probability from 0.1702 to 0.2274 and reducing from 0.1768 to 0.1293. It therefore directs more search effort toward the currently more promising candidate.
With candidates, the two comparison types require at most approximately 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.
| lambda | Average descendant fitness | Gain over uniform |
|---|---|---|
| Uniform | 0.119 | 0.0% |
| 0.1 | 0.147 | 23.4% |
| 0.3 | 0.168 | 41.2% |
| 1.0 | 0.176 | 47.9% |
| 2.0 | 0.137 | 15.1% |
| 5.0 | 0.124 | 4.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.
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:
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.
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:
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: