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

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.