- 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
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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
- 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?
- 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?
- 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?
- 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
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.
- 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).
- Search-cost Accounting by Family
| Family | Proposer | Model calls | Tokens (prompt / completion) | Evaluations | Summed inference request latency (h) | Evaluator GPU-hours |
|---|---|---|---|---|---|---|
| TV cell, 20 seeds (replication) | LLM 7B, no fallback | 1,175 | 2,297,062 / 48,020 | 549 of 960 slots | 0.26 H100 | 0 (CPU) |
| LLM 7B, fallback | 1,134 | 2,223,995 / 47,516 | 694 of 960 slots | 0.24 H100 | 0 (CPU) | |
| LLM 1.5B, no fallback | 1,557 | 3,053,303 / 168,584 | 434 of 960 slots | 0.48 H100 | 0 (CPU) | |
| LLM 1.5B, fallback | 1,581 | 3,181,742 / 188,041 | 793 of 960 slots | 0.35 H100 | 0 (CPU) | |
| Recovery, 8 seeds | LLM 27B, full cards | 77 | 431,586 / 38,595 | 64 candidates | 0.18 H100 (6 of 8 seeds) | 2.22 A100/H100 |
| LLM 27B, cards withheld | 78 | 408,207 / 43,786 | 64 candidates | 0.21 H100 (6 of 8 seeds) | 2.37 A100/H100 | |
| LLM 27B, resampling | 67 | 113,728 / 47,371 | 64 candidates | 0.21 H100 (6 of 8 seeds) | 3.73 A100/H100 | |
| LLM 7B, cards withheld | 205 | 1,358,441 / 47,343 | 57 candidates | 0.18 A100 | 3.25 A100 | |
| uniform random, 10 seeds | 0 | -- | 80 candidates | -- | 6.03 A100 | |
| Held-out field | agent session, LLM 27B | 14 agent (33 tool invocations) | 20,002 (agent only) | 25 routed solves | not logged (H100) | ≤ 0.32 (bound: one RTX 4090 for the whole session) |
| operator evolution rerun, LLM 27B | 20 | 61,875 / 372,344 | 20 candidates | 2.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!
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.
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).
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.
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).
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).
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.
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).
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.