acceptodds
Under review as a conference paper at ICLR 2027

CAP-evolve: constraint-aware adaptive penalties for LLM-guided evolutionary search

Abstract

Large language model-guided evolutionary search (LLM-ES) has shown promise for scientific and engineering optimization, yet existing approaches to constraint handling are either coarse or rely on task-specific designs, leaving general-purpose constraint handling for LLM-ES underdeveloped. We propose Constraint-aware Adaptive Penalty (CAP) to address this gap: it augments scalar program fitness with explicit constraint handling while preserving the underlying evolutionary search. Concretely, CAP retains informative infeasible programs and adapts penalties from signed violations and the evolving feasible frontier. Under idealized oracle assumptions, we establish convergence of CAP to a constrained optimum. For finite-budget search, we develop CAP-Evolve, which augments CAP with violation normalization and alpha-relaxed frontier updates and operates with an LLM-ES procedure as its inner search. Using AdaEvolve as this component, we evaluate CAP-Evolve on four explicitly constrained program-optimization tasks against representative constraint-handling baselines. CAP-Evolve attains the best mean result in six of seven task configurations, and its multi-constraint variants outperform all corresponding baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
LLM, evolutionary computation, constraint optimization

Reviews

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

This paper proposes CAP, an adaptive penalty method for handling constraints in LLM-guided evolutionary search. Rather than discarding infeasible programs, it retains them and adjusts penalty weights using their constraint violations and the best feasible solution found so far. Its practical implementation, CAP-Evolve, builds on AdaEvolve with violation normalization and relaxed penalty updates that encourage exploration early in search. The paper establishes convergence under idealized oracle assumptions and evaluates the method on four constrained optimization tasks, reporting the best mean performance in six of seven configurations.

Critical strengths
  1. I think the paper addresses a meaningful problem with a clear and intuitive approach. The method uses the constraint violations of infeasible programs, together with the best feasible solution found so far, to adapt its penalty weights. I think another key strength is that the approach can be added to an existing evolutionary search system without requiring a major redesign.

  2. I also appreciate the detail provided in the evaluation. Keeping the core experimental setup consistent makes the comparisons easier to interpret. The ablations and individual-run results are particularly helpful for judging which design choices matter and how consistent the improvements are.

Critical weaknesses
  1. My main concern is the missing fixed-penalty baseline in the multi-constraint experiments, where CAP-Evolve shows some of its strongest results. I understand that tuning a separate weight for every constraint would be expensive. However, using one tuned scalar coefficient on the sum of the same normalized violations, λ∥u~1/2(x)∥1\lambda\|\tilde{u}_{1/2}(x)\|_1, would only require a one-dimensional sweep. I think without this comparison, it is hard to tell how much the adaptive weights help compared with a simpler penalty using the same constraint information and normalization.

  2. I am also not fully convinced that the reported gains over tuned fixed penalties are reliable across runs and parameter choices. In the single-constraint settings, several improvements are small compared with the reported standard deviations. For example, Circle Packing improves from 0.99598±0.003540.99598 \pm 0.00354 to 0.99647±0.003080.99647 \pm 0.00308 over five runs. CAP-Evolve also uses a task-specific α0\alpha_0, selected from {0.25,0.5,0.75}\{0.25,0.5,0.75\}, and it is unclear whether the reported evaluation runs were separate from those used to make this choice. Table H.2 suggests that the choice actually matters on Tokamak Control, α0=0.5\alpha_0=0.5 and 0.750.75 give mean errors of 0.067790.06779 and 0.071700.07170, compared with 0.065260.06526 for the fixed-penalty baseline. The fixed-penalty baseline is also tuned, so tuning itself is not unique to CAP-Evolve. Still, I would like to see how well the method works with a common default setting.

Questions for authors
  1. Section 5.2 says that the methods share a task prompt and generation template. Could you clarify what changes in the instructions and feedback given to the LLM? In particular, do all methods show the model the raw objective and constraint violations? An example prompt for each method would help make the differences clear.

  2. I noticed that violating an additional constraint can sometimes lead to a smaller penalty after normalization. For example, with the same objective value and weights of (1,1)(1,1), violations of (1,0)(1,0) give a penalty of 11, while (1,0.01)(1,0.01) gives approximately 0.7140.714. Is this intentional, and have you checked how it affects candidate selection in practice?

7 comments

Thank you for recognizing the motivation, modular integration, consistent evaluation setup, and individual-run reporting. We have completed 60 additional full runs for the normalized multi-constraint fixed scalar penalty you suggested. Below, we address the two main weaknesses and both questions.

Weakness 1

My main concern is the missing fixed-penalty baseline in the multi-constraint experiments, where CAP-Evolve shows some of its strongest results. I understand that tuning a separate weight for every constraint would be expensive. However, using one tuned scalar coefficient on the sum of the same normalized violations, (\lambda|\tilde{u}_{1/2}(x)|_1), would only require a one-dimensional sweep. I think without this comparison, it is hard to tell how much the adaptive weights help compared with a simpler penalty using the same constraint information and normalization.

Answer. In the original K=1K=1 experiments, the evaluator exposes the maximum of the underlying constraint residuals. The fixed penalty therefore already corresponds to an infinity-norm penalty, λ[max⁡kvk(x)]+=λ∥[v(x)]+∥∞\lambda[\max_k v_k(x)]_+=\lambda\|[\mathbf v(x)]_+\|_\infty, on the same underlying constraints.

We complemented this maximum-based baseline with the requested fixed scalar penalty on the sum of the same normalized violations used by CAP-Evolve:

=f(x)-\lambda \frac{\sum_{k=1}^{K}[v_k(x)]_+} {\sqrt{\max\{1,\#\{k:v_k(x)>0\}\}}}.$$ The initial program, evaluator, LLM, prompt/context pipeline, retention mechanism, and search budget match CAP-Evolve. Both methods thus have the same mechanisms for using infeasible candidates and constraint feedback. Holding these mechanisms and normalization consistent makes the comparison directly relevant to whether adaptive calibration adds value. We evaluated four coefficients in each setting, with five independent 100-iteration runs per coefficient, adding 60 full runs. CAP uses its existing $\alpha_0=0.5$ results throughout. Entries report search-stage best-feasible scores as mean $\pm$ sample standard deviation ($\mathrm{ddof}=1$). Higher is better. Circle scores are radius sums divided by $2.635$; trajectory scores are the normalized negative acceleration objective. | Method | Circle Packing $K=3$ | Circle Packing $K=26$ | | --- | ---: | ---: | | Fixed $\lambda=1$ | $0.995859 \pm 0.002017$ | $0.990698 \pm 0.009762$ | | Fixed $\lambda=10$ | $0.995669 \pm 0.002539$ | $0.991590 \pm 0.008532$ | | Fixed $\lambda=100$ | $0.996997 \pm 0.003953$ | $0.996297 \pm 0.003786$ | | Fixed $\lambda=1000$ | $0.996729 \pm 0.002429$ | $0.993480 \pm 0.005734$ | | CAP-Evolve, $\alpha_0=0.5$ | $0.995615 \pm 0.00451$ | $0.998478 \pm 0.00090$ | | Method | Trajectory Optimization $K=5$ | | --- | ---: | | Fixed $\lambda=100$ | $-1.359549 \pm 0.001207$ | | Fixed $\lambda=1000$ | $-1.357929 \pm 0.003890$ | | Fixed $\lambda=10000$ | $-1.356539 \pm 0.006375$ | | Fixed $\lambda=100000$ | $-1.360670 \pm 0.000227$ | | CAP-Evolve, $\alpha_0=0.5$ | $-1.354939 \pm 0.00583$ | The new control sharpens the empirical conclusion. CAP improves the mean over the best scanned fixed coefficient by $0.002181$ at Circle $K=26$, with substantially lower observed variability, and by $0.001600$ at Trajectory $K=5$. Circle $K=3$ favors fixed penalty by approximately $0.001382$. Adaptive calibration is therefore useful in the high-dimensional Circle representation and yields a smaller trajectory improvement, while a tuned fixed scalar works better in the lower-dimensional Circle setting.

Weakness 2

I am also not fully convinced that the reported gains over tuned fixed penalties are reliable across runs and parameter choices. In the single-constraint settings, several improvements are small compared with the reported standard deviations. For example, Circle Packing improves from (0.99598 \pm 0.00354) to (0.99647 \pm 0.00308) over five runs. CAP-Evolve also uses a task-specific (\alpha_0), selected from ({0.25,0.5,0.75}), and it is unclear whether the reported evaluation runs were separate from those used to make this choice. Table H.2 suggests that the choice actually matters on Tokamak Control, (\alpha_0=0.5) and (0.75) give mean errors of (0.06779) and (0.07170), compared with (0.06526) for the fixed-penalty baseline. The fixed-penalty baseline is also tuned, so tuning itself is not unique to CAP-Evolve. Still, I would like to see how well the method works with a common default setting.

Answer. Hard rejection is our primary comparison because it is the standard way existing LLM-ES systems handle feasibility. The main practical question is how much search improves when infeasible programs are retained and used to guide subsequent proposals. The tuned fixed-penalty comparison then asks whether adapting the penalty adds value when both methods can use those programs.

Circle Packing puts the gains in context. At K=26K=26, CAP-Evolve increases the mean radius sum by approximately 0.03270.0327 over hard rejection and 0.005750.00575 over the best tuned fixed penalty in the new sweep. On the same benchmark, AlphaEvolve reports improving the best radius sum from roughly 2.6342.634 to 2.6352.635, and AdaEvolve reports a further best-construction gain of about 0.000120.00012. These published gains put the size of the improvement in perspective: the mean gain over hard rejection is substantial, and the gain over tuned fixed penalty is also appreciable on this benchmark. The K=26K=26 comparison uses five independent runs per method, and CAP-Evolve also has a lower sample standard deviation than tuned fixed penalty (0.000900.00090 versus 0.0037860.003786 in normalized score).

The two methods also differ in what tuning requires. CAP-Evolve searches three specified values of the initial relaxation fraction, α0∈{0.25,0.5,0.75}\alpha_0\in\{0.25,0.5,0.75\}. A fixed penalty has no prescribed search range: a useful coefficient depends on the relative magnitudes of objectives and violations. The best coefficients we found for Circle Packing and Trajectory Optimization were 100100 and 1000010000, respectively. That two-order-of-magnitude difference shows why finding a useful range is itself part of tuning fixed penalty.

A default-to-default comparison therefore requires a cross-task fixed coefficient with no clear basis for choosing its scale. A single value could make the penalty too weak on one task and too strong on another. We instead use a common α0=0.5\alpha_0=0.5 for CAP-Evolve in all three added settings and compare it with the best fixed coefficient found for each setting. The existing sensitivity results show how other choices affect CAP-Evolve, including the weaker Tokamak Control results at α0=0.5\alpha_0=0.5 and 0.750.75.

For the configurations reported as tuned, we used the same runs to select and report both α0\alpha_0 and fixed λ\lambda. The sensitivity analysis in the original submission and the fixed-penalty sweep above show how performance varies across the tested values. We have not independently estimated the effect of selection on the reported means.

Question 1

Section 5.2 says that the methods share a task prompt and generation template. Could you clarify what changes in the instructions and feedback given to the LLM? In particular, do all methods show the model the raw objective and constraint violations? An example prompt for each method would help make the differences clear.

Answer. The task description, evaluator-metric feedback format, and AdaEvolve generation template are shared. Method-specific instructions explain how constraints affect fitness and competition: hard rejection excludes infeasible candidates, fixed penalty uses fixed coefficients, and T–Y and CAP use their adaptive scores. The resulting scores guide the existing parent/context selection, so different methods can select different programs while exposing the same kinds of information.

The common structure is:

SYSTEM
  Task description, program interface, constraints, and task guidance.
  Method-specific constraint-handling instructions.

USER
  # Current Solution Information
    combined_score and evaluator metrics
  # Program Generation History
    previous attempts, where available
  ## Other Context Solutions
    selected programs, scores, metric breakdowns, and code
  # Current Solution
    parent-selection context, parent metrics, and parent code
  # Task
    generation instructions and required edit format

For Circle Packing, objective quality is visible as sum_radii and target_ratio, the search score as combined_score, and constraint feedback as feasibility, geometric residuals, and violation-count summaries. The complete internal 2626-component vector is used in constraint handling; prompt feedback displays its diagnostic summaries.

An actual CAP context entry illustrates how these information types are shown together, excerpted and line-broken for readability:

### Program 1 (combined_score: -2.5444)
Score breakdown:
  sum_radii: 3.1768
  target_ratio: 1.2056
  constraint_satisfied: 0.0000
  max_geometry_violation: 0.2500
  boundary_violation: 0.2500
  overlap_violation: -0.0000
  violated_shape_count: 9.0000

[The candidate's Python source follows.]

The model can therefore distinguish a candidate's high objective from its infeasibility and penalized score. Hard rejection limits which candidates reach normal competition; both CAP and the new fixed control can retain infeasible programs through the same pipeline. The new comparison consequently tests adaptive calibration with this information access shared. Complete system and user prompts and further examples are available in the supplementary materials uploaded with the original submission.

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

This paper proposes CAP-Evolve, a constraint-handling method for LLM-guided evolutionary search. CAP adapts penalty coefficients using the current best feasible solution and observed constraint violations, with the coefficients obtained by solving a quadratic program. The practical algorithm further introduces violation normalization, island-specific penalties, and a relaxation schedule. The authors evaluate CAP-Evolve on four constrained program-optimization tasks, comparing it with hard rejection, fixed penalties, and the Tessema–Yen adaptive penalty method. They also provide theoretical analysis under idealized oracle assumptions and conduct ablations to examine the practical design choices.

Critical strengths

The paper addresses a practical problem in LLM-guided evolutionary search. In constrained optimization, simply rejecting infeasible candidates can discard potentially useful solutions, while fixed penalty coefficients can be difficult to tune, especially when several constraints have different scales. CAP offers a concrete alternative by adapting the penalties based on the current feasible frontier rather than relying entirely on manually chosen weights. Another strength is that the authors evaluate the method on several different constrained optimization tasks, including multi-constraint problems. The comparisons with hard rejection, fixed penalties, and an existing adaptive penalty method provide an initial assessment of the approach. The paper also examines the effects of several implementation choices, which helps explain how the practical algorithm behaves beyond the main performance results.

Critical weaknesses
  1. The improvement over existing constraint-handling methods is not fully clear. CAP adjusts penalty weights by solving a QP based on the best feasible solution and observed infeasible candidates. This is a reasonable approach, but adaptive penalty methods have been studied extensively in evolutionary optimization. The comparison with Tessema–Yen does not fully establish what the proposed QP-based update offers beyond existing methods. The theoretical results also rely on idealized search assumptions that are not enforced by practical CAP-Evolve, which uses finite-budget LLM-generated candidates and periodic penalty updates. As a result, it remains unclear both how much the proposed formulation advances existing constraint-handling methods and how much the theoretical analysis tells us about the behavior of the practical algorithm.

  2. The experimental comparison is limited, particularly for the multi-constraint tasks that motivate the method. CAP-Evolve is compared with hard rejection, Tessema–Yen adaptive penalties, and fixed penalties, but fixed penalties are evaluated only on single-constraint tasks. This makes it difficult to determine whether CAP is more effective than other established approaches to handling multiple constraints. Comparisons with alternatives such as feasibility-based rules or stochastic ranking would provide a stronger assessment. In addition, the initial relaxation parameter is selected based on the mean best-feasible result, but the paper does not clearly explain whether this selection is independent of the runs used for final evaluation. If the same runs are used for both, the reported results could be optimistic.

Questions for authors

Q1. How does CAP fundamentally differ from existing adaptive penalty methods, particularly Tessema–Yen? What specific limitation of these methods does the QP-based update address, and what evidence shows that this formulation provides an advantage beyond adapting penalty weights based on observed constraint violations? Q2. Why is the fixed-penalty baseline evaluated only on single-constraint tasks? Since the main claimed advantage of CAP-Evolve is in multi-constraint optimization, could the authors compare it with at least one representative alternative, such as Deb's feasibility rules or stochastic ranking, under the same LLM, search framework, and evaluation budget? Such a comparison would help determine whether the reported gains extend beyond the particular baselines currently considered. Q3. The initial relaxation parameter is selected from several candidate values based on the mean best-feasible result. Are the runs used for this selection separate from those used to report the final results? If the same runs are used for both, how do the authors account for the potential selection bias, and how much might this choice affect the reported performance? Q4. The theoretical analysis relies on idealized search assumptions that are not guaranteed to hold in practical CAP-Evolve. What properties of the analysis are expected to carry over to finite-budget LLM-guided search, and what guarantees, if any, can be established for the practical algorithm?

3 comments

Thank you for recognizing the practical motivation, consistent evaluation setup, and component analysis. We have completed 60 additional full runs for the requested multi-constraint fixed scalar penalty. We address the two sets of related concerns together.

Weakness 1 / Questions 1 and 4

Weakness 1

The improvement over existing constraint-handling methods is not fully clear. CAP adjusts penalty weights by solving a QP based on the best feasible solution and observed infeasible candidates. This is a reasonable approach, but adaptive penalty methods have been studied extensively in evolutionary optimization. The comparison with Tessema–Yen does not fully establish what the proposed QP-based update offers beyond existing methods. The theoretical results also rely on idealized search assumptions that are not enforced by practical CAP-Evolve, which uses finite-budget LLM-generated candidates and periodic penalty updates. As a result, it remains unclear both how much the proposed formulation advances existing constraint-handling methods and how much the theoretical analysis tells us about the behavior of the practical algorithm.

Question 1

Q1. How does CAP fundamentally differ from existing adaptive penalty methods, particularly Tessema–Yen? What specific limitation of these methods does the QP-based update address, and what evidence shows that this formulation provides an advantage beyond adapting penalty weights based on observed constraint violations?

Question 4

Q4. The theoretical analysis relies on idealized search assumptions that are not guaranteed to hold in practical CAP-Evolve. What properties of the analysis are expected to carry over to finite-budget LLM-guided search, and what guarantees, if any, can be established for the practical algorithm?

Answer. CAP calibrates the penalty against a specific target: an observed infeasible candidate that outperforms the feasible frontier in raw objective should receive scalar fitness no greater than that frontier's. For the current feasible reference xsafex^{\mathrm{safe}} and the set RR of counterexamples included in the update, CAP-Evolve solves

\min_{\boldsymbol\lambda\geq\mathbf0}\quad& \tfrac12\|\boldsymbol\lambda\|_2^2\\ \text{subject to}\quad& \boldsymbol\lambda^\top\tilde{\mathbf u}(y) \geq f(y)-f(x^{\mathrm{safe}}), \qquad y\in R. \end{aligned}$$ The objective gap sets the correction required for each candidate, and the violation vector determines which penalty coefficients can supply it. The QP satisfies these requirements jointly and uses minimum norm to set the coefficient scale. Tessema–Yen (T–Y) uses population normalization and the feasible fraction to construct an adaptive score. CAP's distinguishing feature is that each competitive infeasible candidate imposes a quantitative requirement tied to the best feasible result observed so far. This matters in LLM-ES because model calls and evaluations limit the number of proposals, and the LLM sees numerical feedback that can differ even when candidate rankings agree. The QP can respond directly to new evidence at the next update and sets the penalty scale from that evidence. The T–Y comparison tests CAP against a classical adaptive score; the matched fixed-penalty comparison below tests whether updating the penalty adds value when normalization and access to infeasible candidates are held fixed. CAP has a higher mean in two of the three added settings, with the clearest gain at Circle Packing $K=26$, while the tuned fixed penalty gives a higher mean at $K=3$. The property that carries over to practical CAP-Evolve follows from the QP itself. After each successful update, every included counterexample is at or below the current feasible frontier in scalar fitness, and the nonnegative penalty has minimum Euclidean norm among vectors satisfying those inequalities, up to solver accuracy. This applies to the normalized rows retained for that island after alpha relaxation, regardless of how the LLM generated them. The oracle analysis addresses the separate question of whether repeated corrections lead to a constrained optimum. Its global convergence conclusions require the stated assumptions; the controlled experiments assess finite-budget search.

Weakness 2 / Questions 2 and 3

Weakness 2

The experimental comparison is limited, particularly for the multi-constraint tasks that motivate the method. CAP-Evolve is compared with hard rejection, Tessema–Yen adaptive penalties, and fixed penalties, but fixed penalties are evaluated only on single-constraint tasks. This makes it difficult to determine whether CAP is more effective than other established approaches to handling multiple constraints. Comparisons with alternatives such as feasibility-based rules or stochastic ranking would provide a stronger assessment. In addition, the initial relaxation parameter is selected based on the mean best-feasible result, but the paper does not clearly explain whether this selection is independent of the runs used for final evaluation. If the same runs are used for both, the reported results could be optimistic.

Question 2

Q2. Why is the fixed-penalty baseline evaluated only on single-constraint tasks? Since the main claimed advantage of CAP-Evolve is in multi-constraint optimization, could the authors compare it with at least one representative alternative, such as Deb's feasibility rules or stochastic ranking, under the same LLM, search framework, and evaluation budget? Such a comparison would help determine whether the reported gains extend beyond the particular baselines currently considered.

Question 3

Q3. The initial relaxation parameter is selected from several candidate values based on the mean best-feasible result. Are the runs used for this selection separate from those used to report the final results? If the same runs are used for both, how do the authors account for the potential selection bias, and how much might this choice affect the reported performance?

Answer. The original K=1K=1 fixed penalty already uses the maximum underlying violation, equivalent to an ℓ∞\ell_\infty penalty. We added a fixed scalar λ\lambda on the sum of CAP-Evolve's normalized violations. Both methods use the same LLM, evaluator, initialization, retention, and prompt pipeline, so the comparison tests adaptation with access to infeasible candidates held fixed. We ran four coefficients per setting, five times each, for 60 new 100-iteration runs. CAP-Evolve uses its existing α0=0.5\alpha_0=0.5 results throughout.

Search-stage best feasible scores (mean ±\pm sample SD, higher is better):

Fixed λ\lambdaCircle K=3K=3Circle K=26K=26Trajectory K=5K=5
10.995859±0.0020170.995859 \pm 0.0020170.990698±0.0097620.990698 \pm 0.009762—
100.995669±0.0025390.995669 \pm 0.0025390.991590±0.0085320.991590 \pm 0.008532—
1000.996997±0.0039530.996997 \pm 0.0039530.996297±0.0037860.996297 \pm 0.003786−1.359549±0.001207-1.359549 \pm 0.001207
10000.996729±0.0024290.996729 \pm 0.0024290.993480±0.0057340.993480 \pm 0.005734−1.357929±0.003890-1.357929 \pm 0.003890
10000——−1.356539±0.006375-1.356539 \pm 0.006375
100000——−1.360670±0.000227-1.360670 \pm 0.000227
CAP-Evolve0.995615±0.004510.995615 \pm 0.004510.998478±0.000900.998478 \pm 0.00090−1.354939±0.00583-1.354939 \pm 0.00583

CAP-Evolve leads the best scanned fixed penalty by 0.0021810.002181 at Circle K=26K=26, with lower variability, and by 0.0016000.001600 on Trajectory. Fixed penalty leads by 0.0013820.001382 at Circle K=3K=3.

We prioritized the matched sweep because it tests adaptation within the existing scalar feedback pipeline. Large penalties approach Deb's feasibility-first ordering on a fixed candidate set. In all three settings, performance falls beyond the best scanned λ\lambda, suggesting that stronger feasibility priority can limit exploration. Stochastic ranking would require additional design for numerical feedback and selection.

We used the same runs for tuning and reporting α0\alpha_0 and fixed λ\lambda. The submitted sensitivity analysis and the sweep above show how performance varies with the setting; selection optimism was not independently estimated. CAP's three α0\alpha_0 choices are specified in advance, whereas the best fixed coefficients for Circle and Trajectory differ by two orders of magnitude.

References cited in this response

  • Deb (2000), An efficient constraint handling method for genetic algorithms: DOI.
  • Tessema and Yen (2006), A Self Adaptive Penalty Function Based Algorithm for Constrained Optimization: DOI.
  • Runarsson and Yao (2000), Stochastic Ranking for Constrained Evolutionary Optimization.
Reviewer_h4D9OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes CAP, an adaptive penalty for constrained LLM-guided evolutionary search. The best feasible archive member defines a frontier; the penalty vector λ is the minimum-norm nonnegative vector that scores every infeasible archive member with a higher raw objective below that frontier (a small QP). Under oracle assumptions, the authors prove finite-time discovery (Thm 1) and asymptotic optimality (Thm 2). The practical version, CAP-Evolve, adds island-local penalties, square-root active-count normalization, updates every 5 iterations, and alpha relaxation inside AdaEvolve. Four constrained program-optimization tasks are evaluated against hard rejection, a swept fixed penalty, and the Tessema–Yen penalty (5 runs × 100 iterations, gpt-oss-20b).

Critical strengths
  • Addresses a real gap: most LLM-ES systems discard infeasible programs; the Figure 1 motivation is convincing.
  • The CAP update is simple, parameter-light, cleanly formalized (Def. 1), and drops into any scalar-fitness LLM-ES.
  • Controlled protocol (shared initial program, LLM, prompt template, wall-clock limit) and full run-level reporting in the appendix.
  • Ablations in Table 2 isolate the three practical components.
  • Clear writing.
Critical weaknesses
  • Gains are mostly within noise (n=5, no significance tests). Circle Packing K=1, Spectral Shape, and Tokamak are within one std of the fixed penalty; Trajectory K=1 is worse than hard rejection. Only Circle Packing K=26 (and modestly Trajectory K=5) show a clear win. "Best in six of seven" overstates this.
  • The multi-constraint claim relies on a missing baseline: fixed penalty is not run for K>1. A single scalar λ on an aggregate (‖ũ‖₁ or max_k u_k) is trivially applicable and is the natural comparison.
  • Penalty vs. prompt-context confound: CAP-Evolve keeps infeasible programs in the archive (and presumably in prompts); hard rejection does not. No ablation separates "LLM sees near-feasible programs" from "adaptive penalty."
  • Novelty is understated relative to classical constraint handling: feasibility-first rules (Powell & Skolnick 1993; Deb 2000), ε-constrained method, stochastic ranking are neither discussed nor compared. T–Y (2006) is a weak representative of adaptive penalties.
  • Theory does not cover the evaluated algorithm. Thms 1–2 need an oracle global maximizer of a nonconvex penalized objective (harder than the original problem), give no rate, and "asymptotic direction coverage" (Def. 2) is an assumption on the algorithm's own λ sequence, not on the problem; for K≥2 it fails whenever some constraint is never violated by counterexamples. Table D.1 concedes CAP-Evolve drops this condition along with raw violations and full-archive updates.
  • Both baseline λ and α₀ are selected post hoc on the reported metric; Table H.2 shows α₀ sensitivity on Tokamak is noisy, and Table 2 shows "no normalization" beats the sqrt default at K=3.
  • Narrow scope: one 20B model, 100 iterations, four tasks, for a method pitched as general-purpose.
Questions for authors
  1. Can you add a fixed scalar penalty on an aggregated violation for K=3, 26 and K=5?
  2. Do baseline prompts include infeasible programs and violation vectors? If not, can you run hard rejection with infeasible programs kept in context?
  3. Under what conditions on (f, v) does the min-norm QP satisfy direction coverage? Does lambda_init = 5.0 act as a floor in practice?
  4. Several Circle Packing runs exceed target ratio 1.0; since the 10⁻⁶ tolerance relaxes feasibility, were final packings verified with a strict evaluator?
  5. Minor: Sec. F.1 attributes the AdaEvolve suite to Novikov et al. (2025); Table H.1 labels K=1 rows "None" while Table 2 says "Sqrt."
8 comments

Thank you for the detailed review and for recognizing the motivation, modular integration, controlled protocol, and component ablations. We have completed 60 additional full search runs to evaluate the requested multi-constraint fixed scalar penalty. Below, we address each weakness and question in the order of your review.

Weakness 1

Gains are mostly within noise (n=5, no significance tests). Circle Packing K=1, Spectral Shape, and Tokamak are within one std of the fixed penalty; Trajectory K=1 is worse than hard rejection. Only Circle Packing K=26 (and modestly Trajectory K=5) show a clear win. "Best in six of seven" overstates this.

Answer. Hard rejection is our primary practical reference because it is commonly used in existing LLM-ES systems. Our first contribution to this practice is to show that retaining infeasible programs and calibrating their fitness can substantially improve the resulting search. Comparisons with fixed and adaptive penalties then test how effectively CAP realizes this improvement relative to other constraint-handling choices. Both comparisons are therefore important: the former measures progress over established LLM-ES practice, and the latter assesses the proposed way of achieving that progress.

Circle Packing, a benchmark shared with related LLM-ES work, makes the scale of this progress concrete. At K=26K=26, CAP's mean score is 0.9984780.998478, compared with approximately 0.986060.98606 for hard rejection and 0.9962970.996297 for the best scanned coefficient in the added fixed-penalty experiment. Converting these differences to radius sums gives mean improvements of approximately 0.03270.0327 and 0.005750.00575, respectively. For context, AlphaEvolve reports a radius-sum improvement from approximately 2.6342.634 to 2.6352.635, while AdaEvolve reports improving the best construction from 2.635862762.63586276 to 2.635983082.63598308, an increment of approximately 0.000120320.00012032. These published best-construction improvements show the scale of progress valued on this benchmark: our mean gain is substantial against hard rejection and remains appreciable against tuned fixed penalty. This is why small-looking differences in normalized scores can represent meaningful optimization improvements.

These gains are supported by five independent runs per configuration and complete run-level reporting. AdaEvolve's main protocol and component study use three runs; AlphaEvolve's Figure 8 also uses three-run ablations for matrix multiplication and kissing numbers. Our additional repetitions provide a broader empirical basis for estimating the mean and variability. In the new Circle K=26K=26 comparison, CAP also has a lower sample standard deviation than tuned fixed penalty, 0.000900.00090 versus 0.0037860.003786, so the higher mean is accompanied by more consistent observed outcomes. With the new fixed-penalty results included in the comparison, CAP-Evolve achieves the highest mean in five of seven settings.

Weaknesses 2 and 3 / Question 1

Weakness 2

The multi-constraint claim relies on a missing baseline: fixed penalty is not run for K>1. A single scalar λ on an aggregate (‖ũ‖₁ or max_k u_k) is trivially applicable and is the natural comparison.

Weakness 3

Penalty vs. prompt-context confound: CAP-Evolve keeps infeasible programs in the archive (and presumably in prompts); hard rejection does not. No ablation separates "LLM sees near-feasible programs" from "adaptive penalty."

Question 1

Can you add a fixed scalar penalty on an aggregated violation for K=3, 26 and K=5?

Answer. The original K=1K=1 experiments already include a fixed scalar penalty on aggregated violations. For Circle Packing and Trajectory Optimization, the single-constraint evaluator returns the maximum of the underlying residuals, so this baseline corresponds to penalizing the infinity norm of the positive violation vector. Thus, the original comparison includes the maximum-based aggregation suggested in the review; K=1K=1 describes the exposed feedback representation, while the underlying feasibility conditions remain the same.

We have now complemented this comparison with a fixed scalar penalty on the sum of CAP's normalized multi-constraint violations. This single control addresses both concerns: it supplies the requested multi-constraint fixed baseline and shares CAP's mechanisms for retaining infeasible programs and exposing their code and feedback to the LLM. The normalization, candidate-retention and context-selection mechanisms, prompting pipeline, initial program, evaluator, LLM, and search budget are shared. The comparison therefore tests whether CAP's adaptive penalty mechanism adds value when both methods can use the same types of fine-grained constraint feedback and infeasible context.

We scanned four coefficients in each of the three settings, with five independent 100-iteration runs per coefficient, adding 60 full runs. CAP uses its existing α0=0.5\alpha_0=0.5 results throughout. Results follow the main paper's presentation and report means ±\pm sample standard deviations.

MethodCircle Packing K=3K=3Circle Packing K=26K=26
Fixed λ=1\lambda=10.995859±0.0020170.995859 \pm 0.0020170.990698±0.0097620.990698 \pm 0.009762
Fixed λ=10\lambda=100.995669±0.0025390.995669 \pm 0.0025390.991590±0.0085320.991590 \pm 0.008532
Fixed λ=100\lambda=1000.996997±0.0039530.996997 \pm 0.0039530.996297±0.0037860.996297 \pm 0.003786
Fixed λ=1000\lambda=10000.996729±0.0024290.996729 \pm 0.0024290.993480±0.0057340.993480 \pm 0.005734
CAP-Evolve, α0=0.5\alpha_0=0.50.995615±0.004510.995615 \pm 0.004510.998478±0.000900.998478 \pm 0.00090
MethodTrajectory Optimization K=5K=5
Fixed λ=100\lambda=1001.359549±0.0012071.359549 \pm 0.001207
Fixed λ=1000\lambda=10001.357929±0.0038901.357929 \pm 0.003890
Fixed λ=10000\lambda=100001.356539±0.0063751.356539 \pm 0.006375
Fixed λ=100000\lambda=1000001.360670±0.0002271.360670 \pm 0.000227
CAP-Evolve, α0=0.5\alpha_0=0.51.354939±0.005831.354939 \pm 0.00583

The best scanned fixed coefficient is λ=100\lambda=100 for both Circle representations and λ=10000\lambda=10000 for Trajectory. Relative to these tuned baselines, CAP improves the Circle K=26K=26 target ratio by 0.0021810.002181 and reduces the Trajectory K=5K=5 objective by 0.0016000.001600, while Circle K=3K=3 favors fixed penalty by approximately 0.0013820.001382. CAP's strongest gain therefore persists after matching normalization, detailed constraint feedback, and the mechanisms for using infeasible context. This supports an additional benefit from adaptive calibration, beyond making infeasible programs available, while identifying a lower-dimensional setting where a tuned fixed scalar performs better.

This control also preserves the intended plug-in design. Adding rejected programs only as context to hard rejection would require an additional storage and context-selection mechanism separate from its feasible parent pool. Fixed penalty instead enables infeasible information through the existing scalar-fitness interface and gives those programs a tuned, violation-aware score. That scoring is important: allowing infeasible programs to compete using raw objective alone can favor high-objective, highly infeasible candidates, as the weak-penalty behavior in Figure 4(a) illustrates. The added sweep thus tests adaptive calibration against an informed use of infeasible programs within the same underlying search pipeline.

Weakness 4

Novelty is understated relative to classical constraint handling: feasibility-first rules (Powell & Skolnick 1993; Deb 2000), ε-constrained method, stochastic ranking are neither discussed nor compared. T–Y (2006) is a weak representative of adaptive penalties.

Answer. Our baseline selection targets the constraint-handling decisions relevant to a scalar-fitness LLM-ES: hard rejection represents common practice, fixed penalty tests whether a tuned constant is sufficient, and T–Y provides a classical population-dependent adaptive score. We selected T–Y because it retains the objective–violation trade-off among infeasible candidates, adapts its feedback to the population, and requires no manually specified penalty coefficient. It therefore offers a directly applicable classical comparison for CAP's adaptive scalar feedback.

For Deb-style feasibility rules, the fixed-penalty sweep also provides a useful reason for our experimental priority. Deb ranks feasible candidates ahead of infeasible ones, uses objective values among feasible candidates, and violation among infeasible candidates. On a fixed finite candidate set, sufficiently large fixed coefficients on the same aggregate violation induce a similar ordering, apart from ties. The sweep therefore explores an increasingly strong feasibility preference. In all three added settings, performance falls when the coefficient is increased beyond its best scanned value. This trend gives us reason to expect that strict feasibility-first selection may also restrict useful exploration in this LLM-ES setting. It motivated prioritizing a sweep across penalty strengths to study the trade-off underlying such rules. This is a mechanism-based expectation; Deb's numerical feedback and resulting search trajectory may differ.

Stochastic ranking and epsilon-level comparison methods raise a different integration question. Their comparison rules do not, by themselves, determine the numerical feedback that our LLM-ES uses in prompts and score-dependent selection. A rank-to-score mapping can preserve an ordering, but its numerical scale still needs to be chosen, and different choices give the LLM different feedback. Evaluating these methods would therefore entail designing and assessing an additional adaptation of the underlying search pipeline. We instead prioritized the shared-pipeline fixed sweep, which directly tests adaptive calibration while preserving the mechanisms for candidate retention, context selection, and numerical feedback. This is why the additional experiments focus on the requested scalar-penalty control rather than new ranking-based adaptations.

CAP's contribution within this interface is to give that numerical calibration an explicit target: each competitive infeasible candidate supplies its objective excess over the feasible frontier and its violation vector, and the QP selects the minimum-norm nonnegative penalty satisfying those frontier requirements. T–Y constructs its score from population normalization and feasible fraction; CAP responds to candidate-level frontier inequalities. The existing T–Y comparison and the added fixed sweep consequently address two relevant alternatives: a classical adaptive scalar construction and a tuned fixed penalty under shared information access.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.