acceptodds
Under review as a conference paper at ICLR 2027

OptEvolve: Hardware-Aware Discovery of Certified Optimization Algorithms

Abstract

Canonical optimization algorithms each excel in distinct regimes, yet identifying the optimal combination of formulation, algorithm, and hardware strategy for a target instance remains non-obvious. While recent algorithmic discovery frameworks utilize LLM-guided evolutionary search, naive source-code mutation fails to provide structural guarantees of mathematical convergence. We introduce OptEvolve, an automated framework for optimization modeling and verified solver synthesis. OptEvolve synthesizes the optimal solver for a target problem instance by co-optimizing mathematical formulations, algorithmic schemes, and hardware-level operator implementations. Solvers are evolved as typed genomes in a monotone-operator calculus, using a symbolic gate to discard invalid candidates prior to compilation while admitting custom operator kernels under strict behavioral contracts. An empirical cost model guides the search across hyperparameters and stopping criteria, while optimizing GPU iteration fusion tiles on target devices. OptEvolve matches or beats domain-specialist solvers on structured problems and outperforms general-purpose baselines where no specialist exists. Furthermore, its targeted CUDA fusion tiles outperform XLA by up to , and the framework generalizes effectively across unseen, held-out QP, LP, and SOCP benchmarks.

Primary area:
optimization
Keywords:
optimization, GPUs, evolutionary search

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

This paper presents OptEvolve, a framework that searches over typed solver designs for convex composite problems, combining splitting schemes, step sizes, constraint reformulations, LLM written projection code, and hardware choices such as fused GPU tiles. A symbolic gate checks textbook convergence conditions before any candidate runs, generated code is screened by finite contract tests, and every returned answer must pass one shared accuracy check on the original problem. The authors conducted experiments on imaging, unmixing, batched quadratic programs, and 28 held out instances report large speedups on several structured families, while also documenting losses to specialists.

Critical strengths
  1. From the reviewer’s point of view, restricting proposals to a typed genome and checking step size conditions before execution is a sensible way to bring correctness into LLM driven search. Invalid proposals cost no solver time, the violated condition is returned to the proposer, and genome search never executes model written code.
  2. The evaluation protocol is a useful contribution in itself. Every solver, including baselines, is graded by the same check on the original problem, and the finest tolerance each solver reaches is reported next to its time, which exposes cases such as the scikit image TV solver that is fast but never accurate.
  3. The comparison field includes structure specific specialists such as celer, skglm, LIBLINEAR, network simplex, and a Frank Wolfe core set method, not only generic solvers, which addresses the weak baseline concern raised in recent literature.
Critical weaknesses
  1. Actually I think the data presentation of this work can be further improved, such as in Table 4, I found it is a little bit hard to follow with elements put together, which I guess would make it more difficult for readers of this work more difficulty to understand. I would suggest adding some visualzation for comparison would enhance the presentation of the statistics of this work.
  2. I would suggest adding proof of the language model's worth. The router without the agent session solves 26 cases with similar or lower geometric mean times; the genome proposer is a 1.5 billion parameter model that reverts to random proposals when it fails; on TV denoising, the LLM and random proposers tie; and in the recovery experiment, a uniform random proposer also assembles the entire method.
  3. The natural baselines are algorithm configuration and selection techniques like SMAC, irace, Bayesian optimization, or learned portfolio selection, none of which are compared, since the typed search space is essentially a configuration space. Without the gate, gene pool, and router, the authors' own weakened arm serves as the only LLM baseline.
  4. Statistical support can be improved. Three held-out patches are used in TV results, nine instances are used in projection ablation, 27 versus 26 solved out of 28 is a one instance difference at a loose tolerance of ten to the minus three, two seeds per arm are used in the recovery experiment, and Tables 4 and 5 show no variance. The caption of Table 5 itself cautions against the 23 times claim for the LLM only arm, which divides geometric means over various instance sets.
  5. I found several numbers reported in the paper that may contradict each other based on my understanding. Within the main text, the abstract states that the fused CUDA tiles outperform XLA by up to 2/7x (page 1), which appears to be a typo, while Section 5.4 reports about 3.25x relative to XLA on the RTX 4090 (page 9). The contributions list and Section 5.1 state that in 3 of the 6 application classes the accuracy check changes the wall clock verdict, but Table 4 shows only 1 class, isotropic TV denoising, where a baseline is faster yet fails the check.
Questions for authors
  1. As mentioned in W2, what fraction of language model proposals were rejected by the gate, failed to parse, or fell back to the random proposer, and how does the LLM arm perform if fallbacks are excluded?
  2. In addition to the performance, I am also curious about the efficiency. What was the total search cost per family in model calls, tokens, evaluations, and GPU hours, and how many repeat solves are needed to amortize it?
  3. Appendix G.2 says the LLM and random runs shared a proposal stream. Could you please further clarify this, and are the two arms independent?
  4. Could you clarify the statistical inconsistency mentioned in W5, is this a typo or there is something that can be further clarified not mentioned in the paper that caused misunderstanding?
3 comments

Thank you for your insightful review, which has greatly strengthened this work! In response to your feedback, we have added new evaluations spanning 67 instances, 20 seeds, new SMAC baselines, and strive to address all concerns point-by-point below.

  1. Data Presentation

The revision now includes Fig 2 & 4 to visualize the six application classes, distinguishing accuracy passes, failures, and extrapolated timings. Fig 5 adds recovery confidence intervals, coverage over repeated passes, and operator-transfer results (https://postimg.cc/zVQsWGzy ; https://postimg.cc/LJZrVF59).

  1. Value of the LM

New experiments (Section 5.2, App. F.4–G) show the symbolic gate guarantees convergence while the LLM's value is in operator synthesis and method assembly, not parameter tuning. We have added a Controlled Ablation section in the revised Appendix.

  • Method assembly (Fig 5A) shows that with 8 candidates per seed, the 27B model recovers the full method in 8 of 8 seeds. With cards withheld, it succeeds in 5 of 8. Uniform random succeeds in 1 of 10. The 95% intervals for the 27B model and random search do not overlap.

  • Held-out Coverage (Fig 5B, Table 5): Five repeated passes revealed the original 27 vs. 26 margin was a result of a compile-timing race, which is now corrected. The full system stably accepts 27 of 28 instances in all five passes. The router alone solves 27 in 4 of 5 passes. A handwritten library also solves 27, demonstrating that coverage comes from the certified router. The LLM contributes speed and reliability, as deployed operators succeed on 32 of 32 unseen instances and run up to 1.53x faster than specialized code.

  • The revision now includes a Certified Execution Mode (App B.4). The theoretical guarantee now reaches generated implementations at runtime via a certified mode that bounds the numerical error of every update.

  1. Baselines & TV Cell (Table 18)

On the TV cell (20 seeds, 20 patient-disjoint test crops, 48 charged evaluations), SMAC3 and Optuna TPE dominate parametric search, reaching 0.0199 s and 0.0284 s median test SGM vs. 0.0551 s for matched-menu random and 0.2334 s for the default. We agree configurators are superior here and now explicitly recommend them for parameter search, versus the LLM for code synthesis (we did not run irace as it cannot fold the symbolic gate into its elimination rule).

  1. Statistical Rigour

Every requested point has now been formally replicated, and we have scaled the projection ablation from 9 to 67 instances and the TV cell to 20 seeds/crops with bootstrap intervals. The revised Appendix F.4 titled Statistical Support seeks to directly address this point.

  • TV Cell is scaled to 20 patient-disjoint test crops and 20 seeds/arm with bootstrap intervals (Table 18).

  • Projection Ablation is scaled from 9 to 67 instances. On 32 decidable instances, the two deployed operators succeed on 32/32, while the uncertified black-box operator solves 20/32. We added 29 clause groups, which successfully rejects the candidates that previously failed out-of-domain.

  • Table 5 now reports 5-pass medians; we removed the 23x cross-set ratio (on the 18 jointly solved instances, repeat speedup is 16.6x).

  1. Efficiency of Framework

Additional Table 19 now details costs. A 7B TV run uses ~57 calls and 134,000 prompt tokens in 86–98 s. Against the shipped default, a configurator champion repays its search cost in ~480–500 solves and the LLM repays in ~580. The held-out system's 1,904 s search is repaid after ~1,400 solves of the arithmetic workload.

  1. Fallback Accounting

In the original 1.5B run, 60/128 calls failed the gate and 27/80 slots (33.75%) fell back to the random arm's seeded RNG. New runs remove this shared stream (Table 18): without fallback, 1.5B fails to certify on 9/20 seeds (0.0902 s SGM), whereas 7B certifies on 20/20 seeds with zero fallbacks (0.0673 s SGM, 403/1,216 gate rejections).

  1. Presentation

We apologize for the typos, and have corrected this. The 2/7x was a typo for 2.74x (the H100 fused tile vs XLA). The 3.25x reported in Section 5.4 is for the RTX 4090 from a separate sweep. In two classes a faster baseline fails the accuracy check. In a third class the failing baseline is slower so the check turns a finite margin into a lower bound.

Briefly our main contributions include:

  • Convergent-by-Construction Design: Automates hardware-efficient solver design while preserving convergence guarantees via Theorem 1's symbolic gate for exact splitting schemes and relaxations. Comprehensive comparisons show OptEvolve excels where no packaged specialist exists (Table 4).

  • Theory–Application Link: Certified execution mode bounds floating-point errors via per-call witnesses (App. B); certified Nesterov acceleration (App. H) is at 1.2–4.4× shipped wall time on four tested routes.

  • OptEvolve-Bench: An open-source benchmark with a unified original-problem acceptance check across 14 engines and 806 records.

Reviewer_Ko6bOpenReview ↗

Reply to authors' response

Thank you for your response. I found the authors have partially addressed my questions and concerns. However, some points may still need further clarification such as: (1) a separate parse failure rate to help readers understand why LLM proposals fail and (2) a full breakdown of model calls, token counts, evaluations, and GPU-hours for each problem family which I find especially important for assessing search costs and the method's practical effectiveness. In this case, I'm inclined to keep my current score.

Thank you for your response! In order to address your remaining concerns, we present the separate parse failure details and the 4 new metrics per family as requested.

  1. Separate Parse Failure Rate
  • We replicated the TV-cell proposer runs with the same models, prompts, parser, gate, budget, seeds and splits, now logging every model call. A parse failure is a returned response that the parser cannot turn into a valid genome (invalid JSON or JSON that breaks the genome schema). For the no-fallback and fallback arms respectively, the rate is 0.3% and 0.9% for the 7B model (4/1,175 and 10/1,134) and 20.8% and 21.4% for the 1.5B model (324/1,557 and 338/1,581). Zero requests failed in transport (added Table 28, App J).
  • The 1.5B model writes valid JSON with the wrong genome schema (658 of its 662 parse failures), and its gate rejections are mostly genes that do not apply to the problem. The 7B model almost never fails to parse, and 92% and 87% of its gate rejections (no-fallback and fallback arms) are the step-size condition of Theorem 1 (added Tables 28 and 29, App J).
  • In the recovery experiment, over the 171 calls pooled across the three 27B arms (six newly logged seeds each), the 27B model's 9 failures are all responses truncated at the length limit. The 7B control's main failure is repetition: 148 of its 205 proposals repeat an evaluated design (added Table 31, App J).
  1. Search-cost Accounting by Family
FamilyProposerModel callsTokens (prompt / completion)EvaluationsSummed inference request latency (h)Evaluator GPU-hours
TV cell, 20 seeds (replication)LLM 7B, no fallback1,1752,297,062 / 48,020549 of 960 slots0.26 H1000 (CPU)
LLM 7B, fallback1,1342,223,995 / 47,516694 of 960 slots0.24 H1000 (CPU)
LLM 1.5B, no fallback1,5573,053,303 / 168,584434 of 960 slots0.48 H1000 (CPU)
LLM 1.5B, fallback1,5813,181,742 / 188,041793 of 960 slots0.35 H1000 (CPU)
Recovery, 8 seedsLLM 27B, full cards77431,586 / 38,59564 candidates0.18 H100 (6 of 8 seeds)2.22 A100/H100
LLM 27B, cards withheld78408,207 / 43,78664 candidates0.21 H100 (6 of 8 seeds)2.37 A100/H100
LLM 27B, resampling67113,728 / 47,37164 candidates0.21 H100 (6 of 8 seeds)3.73 A100/H100
LLM 7B, cards withheld2051,358,441 / 47,34357 candidates0.18 A1003.25 A100
uniform random, 10 seeds0--80 candidates--6.03 A100
Held-out fieldagent session, LLM 27B14 agent (33 tool invocations)20,002 (agent only)25 routed solvesnot logged (H100)≤ 0.32 (bound: one RTX 4090 for the whole session)
operator evolution rerun, LLM 27B2061,875 / 372,34420 candidates2.39 H100 (0.38 h wall)0.05 H100
  • Request latency is summed over requests, not device time, so overlapping requests on one server are counted separately (the evolution rerun ran 8 at a time and took 0.38 h of wall time). Evaluations count distinct solver evaluations per seed, summed over seeds, and a duplicate fills one of the 48 charged slots per run without a new evaluation. On recovery, the 27B arm with full cards uses about 0.3 evaluation GPU-hours per seed on its five A100 seeds (8/8 seeds recovered) versus 0.6 for uniform random (1/10 seeds). The TV costs are those of the new replication, which evaluated on CPU. The held-out session took 1,152 s (0.32 h) of wall time including its 534 s evolution, whose tokens were not logged, so we reran that evolution with the same seed program, configuration and specification (added Tables 30 and 32, App J, revised App F.5 "Proposers, search cost and tuned baselines").
  • Auditing the held-out session corrected two numbers: its agent used 20,002 tokens, not 40,004, and it cost 1,152 s, not 1,904 s, which had added a separate comparison run. Recomputed from the arithmetic time saved per solve, the session is repaid after about 830 held-out solves. This compares the full system with Clarabel on the jointly solved instances and excludes the earlier cost of building the operator library (revised Table 19, and App F.5).

We hope these additions transparently clarify why proposals fail, what each search costs, and when that cost is recovered.

In light of the new visualizations, the 8-seed recovery controls for the model's contribution, the new SMAC3 and Optuna TPE baselines, the 67-instance transfer test and 20-seed proposer comparisons, the five-pass replication of the held-out field, the independent fallback-free arms, the separate parse failure rate, 4 new breakdown metrics per family including resource accounting, and the additional fallback accounting section, we would be grateful if you would consider raising your score.

We remain vigilant and happy to address any further questions/concerns you might have in these final hours of the discussion period. Thank you!

Reviewer_H7gsOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents OptEvolve, which uses LLM-guided search to build solvers for composite convex problems. It chooses suitable formulations, splitting methods and implementations for the target hardware. Convergence conditions are checked for exact iterations, while the code is tested separately. The experiments show speedups over existing solvers on several workloads.

Critical strengths

1.The paper is well motivated by the practical challenge of designing convex optimization solvers that are efficient on target hardware while preserving convergence guarantees for their underlying iterations.

2.Jointly considering problem formulations, algorithmic choices, and implementation costs provides a useful perspective on automated solver design.

Critical weaknesses

1.The convergence guarantee does not extend to the synthesized numerical operators used by the system.

2.The theory assumes exact proximal maps, whereas generated projections are admitted through finite contract tests. These tests do not establish that implementation errors satisfy conditions sufficient to preserve convergence. Although the paper explicitly acknowledges this boundary, it limits the guarantee provided for the generated solver implementations.

Questions for authors
  1. For the reformulations in Table 9, how are the recovery maps and operator-norm bounds obtained and checked? Which steps are automatic, and which require user input?
  2. In Table 5, do the full system and the router without an agent session start with the same gene pool and cost measurements? For instances solved only by the full system, what changes did the agent make?
  3. Could the abstract and introduction explicitly state that the framework targets composite convex optimization problems, as specified in Sections 3–4?
2 comments

Thank you for your valuable review. We are glad you find the problem to be well motivated, and we have given deep thought to closing the gap between theory and implementation. In response, we have added a Certified Execution Mode connecting supported generated projections to checked numerical-error bounds, with guarantees that distinguish summable errors from fixed-precision execution. The revised Appendix B expresses the logic, and we include a quick graphic here for your convenience: https://postimg.cc/CnDXGWw2 .

Below, we address your questions and concerns point-by-point:

  1. Convergence Guarantees
  • For supported primal–dual routes, Eq. (10) combines projection witnesses with gradient, linear-map, and rounding errors to build ∥ek∥HG≤ηk\lVert e_k\rVert_{H_G}\leq\eta_k for the complete update. The new Appendix I states floating-point accounting to specifically for binary64 assumptions and arithmetic enclosures required for such guarantees.
  • Corollary 2 proves convergence when ∑kηk<∞\sum_k \eta_k < \infty. Fixed-precision runs receive finite-run residual bounds, and part (iii) gives a computable fixed-point residual bound. Eq. (12) now links this to the KKT residual at the exact update. Across the four relocated routes (8,000 replayed calls), every route reaches the 10−610^{-6} target with checks enabled at 1.2–4.4× shipped wall time (Tables 6–8).
  • Revised Appendix H now extends the analysis to accelerated momentum using feasible projection repair and proximal/gradient-error accounting, thus yielding a finite-run accelerated guarantee (Corollary 3).
  1. On Inexact Implementation and Scope
  • For supported box–hyperplane projections and slab reductions, the rounding-aware multiplier-bracket check gives ∥p^−ΠC(v)∥2≤ϵeval+∥a∥2(λ+−λ−)/2\lVert\widehat p-\Pi_C(v)\rVert_{2} \leq\epsilon_{\mathrm{eval}}+\lVert a\rVert_{2}(\lambda_{+}-\lambda_-)/2 (Proposition 3, Appendix B.1). Here λ±\lambda_\pm are checked bracket endpoints and ϵeval\epsilon_{\mathrm{eval}} bounds evaluation error. Therefore, the witness bounds error on the actual input of each checked call.
  • Rejected generated calls are replaced by checked bisection. Precision-floor cases keep their larger recorded bounds in the accumulated error sums.
  • Holding the same screened operator, formulation, stepsizes, and arithmetic fixed on four known failing Maros–Mészáros instances, 0/4 passed with enforcement disabled versus 4/4 with runtime witness enforcement and checked fallback (Appendix G.1, Table 21). This control aims to isolate the effect.
  1. Reformulations, Recovery maps, and Norm bounds
  • For the supported routes, users supply problem data and the planner constructs recovery maps and checks structural preconditions automatically (Appendix F.3, Table 15). Ruiz scaling uses x=Dzx=Dz, relocation uses an inverse permutation, and cone relocation composes permutation and diagonal scaling.
  • The two-map condition (Eq. 14) then transfers minimizers and bounds approximate objective gaps. Returned points are also checked directly on the original problem data.
  • The default shipped mode uses power iteration with a 2% heuristic margin (not a certified upper bound). Certified mode uses the smallest available outward-evaluated sound bound from Gram, Frobenius, and induced-norm bounds, also bounds smoothness, and checks the gate inequality conservatively on the transformed problem (Appendix I).
  1. Full System and Agent Ablation
  • Both arms share the initial nine handwritten contract-tested operators, formulation rules, cost model, and visible-workload evidence, with no held-out evidence. The full arm receives three session-evolved operators and their lessons, with no new formulation or planner rule (Appendix F.4).
  • The submitted 27-versus-26 difference was due to first-visit exploration timing. We withdraw attributing greater coverage to the agent. On the knapsack instance, both operators reach acceptance after 2,560 iterations, with routed times of 0.98 and 1.00 s.
  • After revising exploration accounting, the full system solves 27/28 in all five passes and the router alone in four, giving both median coverage 27/28, versus 26/28 for the existing-engine oracle.
  • The session's measurable benefit is a 9% improvement on the 6,000-variable SVM dual, from 0.143 to 0.13 s across all five passes. If else, times differ by at most 2%.
  1. Presentation
  • The Abstract and Introduction to now explicitly state that OptEvolve targets composite convex optimization problems.

The revision now connects supported numerical executions to explicit error guarantees while making conditional convergence, fixed-precision bounds, and empirical acceptance explicit. We thank you again for your meaningful feedback, and remain happy to answer any further questions or concerns!

The authors fix most of my concerns

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

This work presents OptEvolve, a framework for automated solver design for composite convex optimization. It combines evolutionary search over typed solver representations with a symbolic gate that checks sufficient convergence conditions for five classical splitting schemes and their relaxations. The framework also searches solution-preserving formulations, projection implementations, and hardware configurations, and routes instances using measured computational costs.

Critical strengths
  1. Incorporating convergence conditions into the search representation is a useful approach to making automated optimization algorithm search more reliable.
  2. Jointly considering mathematical formulations and hardware execution is practically valuable.
Critical weaknesses
  1. My main concern is the trade-off between convergence guarantees and the expressiveness of algorithm discovery. As specified in Section 4, the certified grammar supports five predefined splitting schemes and relaxation. These classical methods cover many useful applications, but the demonstrated search primarily configures and combines established components within a restricted design space. This limits the evidence for discovering substantially new optimization methods that improve both computational efficiency and convergence behavior. The TV experiment further illustrates this uncertainty: LLM-guided and random search achieve the same held-out runtime (Section 5.2 and Table 7).
  2. Although the paper includes several ablations, the individual contributions of important components remain insufficiently isolated. The LLM-only comparison simultaneously removes the scheme gate, gene pool, and router, so its performance gap cannot be attributed to any particular component (Section 5.4).
  3. Comparing against solvers at shipped defaults is reasonable for evaluating out-of-the-box performance, as the paper explicitly acknowledges. However, allowing baseline solvers to use problem-family-specific hyperparameters would provide a stronger assessment of the proposed method’s algorithmic advantages. OptEvolve searches formulations, stepsizes, relaxation, and execution settings, so the current comparisons do not fully separate improvements in solver design from configuration advantages. Tuning competitive baselines on training instances and evaluating them on the same held-out problems would help establish whether the gains extend beyond automating solver selection and tuning.
Questions for authors

see weakness

1 comment

Thank you for your careful review of our paper and for your insightful comments! We have clarified the scope of algorithm discovery, added controlled component comparisons, and hyperparameter tuned baselines. We strive to address each concern to your satisfaction below.

  1. Convergence and Expressiveness
  • We kindly note that for a broad range of practical applications, the optimal decisions of many optimization algorithms, fusion of algorithms to targeted problem structure, projection, hardware kernel fusion, and convergence is a non-trivial endeavor. For example, relocating constraints changes the linear operator applied at each iteration and exposes a specialized projection for synthesis. In this work we aim to take a step towards this end-to-end execution, and we now extend future work in the revision.

  • The revised Sec 3–4 now specifies that the scope of our contribution is automated solver synthesis jointly over solution-preserving formulations, admissible iterations, numerical implementations, and hardware-aware execution. Experiments establish efficient solver construction within it, without claiming a new base splitting scheme or convergence rate.

  • New empirical results in the revision includes the 20-seed, 48-eval comparison supports configurators for this parametric task: SMAC3/TPE achieve median test times of 0.0199/0.0284 s vs 0.0551 s for matched-menu random (App F.5, Tab 18). We now recommend configurators for parameters and evaluate the LLM separately on method assembly and code synthesis.

  • We’d like to kindly note, App H includes a separately certified Nesterov route using feasible projection repair and error accounting. Its finite-run accelerated guarantee (Cor 3) extends the framework beyond the original base grammar through an explicit additional certificate.

  1. Ablations
  • Additional 8 candidates per seed: The 27B proposer recovers the known unmixing method in 8/8 seeds with expert cards and 5/8 with cards withheld, versus 1/10 for uniform random. These results measure assembly within the supplied menu under a fixed judge (App F.4, Tab 17, Fig. 5A).
  • Holding formulation, precision, acceptance target, and 9,300 iterations fixed, replacing handwritten Newton/breakpoint code with the generated projection gives 1.35× faster end-to-end solves on RTX 4090 and 1.53× on RTX 5090, with near parity on A100 (App G.2, Tab 22).
  • Holding the screened operator, formulation, stepsizes, and arithmetic fixed on four known failing instances, enabling witness enforcement and checked fallback changes acceptance from 0/4 to 4/4 (App G.1, Tab 21), now isolates runtime enforcement.
  • Agent-session: Both arms start with the same nine operators, formulation rules, and cost evidence; the session adds three operators and lessons. After correcting exploration accounting, both achieve median coverage 27/28. The session improves one SVM instance by 9% across five passes, with other times within 2%; we withdraw the earlier coverage attribution (App F.4).
  1. Tuned Baselines
  • We have added grid searches over exposed Clarabel and PIQP settings, selecting configurations on visible instances within each family and evaluating them on held-out instances. Tab 20 covers five QP family groups at 10−310^{-3}. On the comparison host, selected settings change family geometric-mean runtime by −5% to +4%, with no change in solved counts (App F.5).

  • On budget-constrained least squares at n=12,000n=12{,}000, relocation with a handwritten projection is already 3.7× faster than the best engine at shipped defaults at 10−410^{-4}. Swapping only the projection gives a further 1.16–1.29× cold-solve improvement across tested tolerances (App F.2). This quantifies the additional benefit of generated code within the chosen formulation. The tuning study tests the selected settings and families (App F.5).

In order to further extend the convergence to implementation framework, we have additionally added a Certified Execution Mode connecting supported generated projections to checked numerical-error bounds through a 4-step chain. The revised App B expresses the detailed logic, and we include a quick graphic here for your convenience: https://postimg.cc/CnDXGWw2 .

  • Witness: A checked scalar bracket bounds the output distance to the exact projection (Sec B.1, Proposition 3).
  • Step Error: This links to a per-call error calculation that translates the projection bound into the overall step error in the certificate's metric (Sec B.2, Eq. 10).
  • Guarantee: These step errors feed into a theoretical guarantee providing convergence under summable errors or finite-run KKT residual bounds (Sec B.3, Cor 2).
  • Measurement: This is then a runtime measured mode that actively enforces these bounds and triggers bisection fallbacks on every execution call (Sec B.4).

Thank you again for the extremely rewarding feedback, which has substantially strengthened this work! We remain happy to address any further questions or concerns.

Comments on the paper

2 comments

Dear Reviewers,

The authors have submitted their rebuttal. Please review it and share your comments. If anything is unclear or requires clarification, please let the authors know as soon as possible. The author–reviewer discussion period ends on 18 November.

Best regards,

AC

AuthorsOpenReview ↗

Closing Remarks

We would like to sincerely thank the Area Chair and all the reviewers for overseeing our submission. Below, we briefly synthesize the discussion period and provide an overview of the revision.

  1. Theory-implementation gap (H7gs): We have added a Certified Execution Mode for supported primal-dual solvers that use generated projections (App. B). It bounds the numerical error of each update at runtime and uses a provable upper bound on the reformulated operator norm. Summable error bounds guarantee convergence, and at fixed precision the new corollary bounds the finite-run residual. All four tested routes reached the original-problem target of 10⁻⁶ with runtime checks enabled. The revision includes:
  • A rounding-aware multiplier bracket that bounds each generated projection's error.
  • Calls that exceed the error budget fall back to checked bisection.
  • Same screened operator, same settings: 0/4 solved with checks off, 4/4 with enforcement (Table 21).
  • 29 added test groups for inputs the original screen missed.
  1. Convergence guarantees vs expressiveness (jWVY): Momentum on an eliminated formulation needs 1.3x to 20x fewer iterations than the paper's route, and the witness bracket certifies it (App. H). Both rules are now in the router, with coverage unchanged at 27/28 and parity in time (Table 27). The accelerated route is 1.26x faster than the receipt-bearing route on one instance and slower on three (Table 23), hence we report it as a route-cost comparison, not a speedup.

  2. Additional ablations and hyperparameters (Ko6b, jWVY): Additional SMAC3 and Optuna TPE baselines on the TV cell at 20 seeds per arm: configurators beat random, which beats the LLM (Table 18). Recovery controls at 8 seeds per arm: 8/8 with expert cards, 5/8 withheld, 1/10 at random (Table 17). Five-pass replication of the held-out field: the full system certifies 27/28 in every pass (Table 5). Tuned Clarabel and PIQP change held-out times by -5% to +4% and no solved count (Table 20). The projection ablation grew from 9 to 67 instances (32/32 decidable for deployed operators against 20/32 unchecked). Generated projections beat handwritten controls by 1.35x to 1.53x on the RTX 4090/5090, while a handwritten library also covers 27/28, so coverage comes from the certified router and the model contributes speed (Table 22).

  3. Clarified accounting details (Ko6b): Additional figures now visualize Table 4 for better clarity. Parse failures are separated from gate rejections and fallbacks (Table 28), with rejection reasons (Table 29) and a per-family ledger of calls, tokens, evaluations and GPU-hours (Tables 30 to 32, App. J). Comprehensive controls including: the 67-instance transfer test and 20-seed proposer comparisons, the five-pass replication of the held-out field, the independent fallback-free arms, the separate parse failure rate, 4 new breakdown metrics per family including resource accounting, and the additional fallback accounting details section, are provided in our point-by-point response below.

Contributions

  • To the best of our knowledge, OptEvolve is the first certified-by-construction discovery system for composite convex optimization algorithms. Restricting proposals to a typed genome and checking convergence conditions before execution brings correctness into LLM-driven search: invalid proposals cost no solver time, the violated condition is returned to the proposer, and the genome search never executes model-written code.

  • Joint solver and HW search: formulation, iteration, operator, precision and device are co-optimized by measured cost, relevant to a broad range of applications, including hyperspectral unmixing, cell-type deconvolution, TV imaging, batched QP layers, LPs and SOCPs.

  • We present a unified theoretical contribution, from the gate's convergence certificate to the certified execution mode that carries the guarantee to generated code, with an evaluation protocol that grades every solver, including specialists, by the same original-problem check.

  • Demonstrated efficacy against existing solvers, especially where no specialist exists: on budget-constrained least squares at n = 48,000, OptEvolve is 25x faster than the fastest accepted general engine, and it solves 27 of 28 held-out instances against 26 for the best-per-instance oracle over existing engines.

As automated discovery scales, bridging formal verification and generated numerical correctness has become a timely and central challenge. Our goal is to take a meaningful step and present a novel approach via principled, certified methods. We are excited about the directions this presents for future work, including richer LLM integration and broader certificate families.

Thank you once again to all the reviewers for your insightful questions and comments. We have thoroughly appreciated incorporating these revisions which greatly strengthen our paper, and look forward to addressing any further questions!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.