- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper introduces distribution-aware programming, a framework that uses sample problem instances to generate specialized optimization solvers for recurring workloads. A pretrained LLM proposes structural hypotheses, writes analysis programs to extract reusable hints, and synthesizes solver code that is iteratively refined using validation quality and runtime. The resulting solver handles new instances without further LLM calls or model training. The paper also analyzes how sample access can improve solver selection and how repeated deployment can offset the initial synthesis cost.
Critical strengths
- The matched hint ablation and sample-access experiments show that explicit structure discovery can improve solution quality or runtime. This supports the proposed mechanism beyond simply generating and refining code.
Critical weaknesses
- Comparisons with the closest methods are missing. EoH [1] and ReEvo [2] already generate CO heuristics through iterative LLM-based search, but neither is directly evaluated. The internal ablation is useful, yet does not establish the method’s advantage over existing algorithm-discovery systems.
- Offline costs are reported, but the paper does not quantify how many future instances must be solved to recover them. This matters because deployment speedups alone do not establish lower total computational cost.
[1] https://arxiv.org/abs/2401.02051 [2] https://arxiv.org/abs/2402.01145
Questions for authors
- How robust are the generated solvers when test instances violate the structural patterns discovered during synthesis, and do their fallback mechanisms preserve solution quality?
- How does the number of training instances affect solver quality and runtime, and how many samples are needed to consistently identify useful structure?
3 comments
Thank you for the detailed rebuttal and the additional experiments. The robustness and sample-size analyses clarify where the method works well and where it struggles.
My main concerns about efficiency remain. The EoH and ReEvo comparisons show a trade-off between runtime and solution quality on two distributions, but they do not establish a speed advantage at comparable quality. The break-even estimates are informative, but none includes both remote LLM inference and reference-label generation, and the proposed solvers and baselines were timed under different conditions.
These concerns are central to my assessment of the paper’s practical contribution. Therefore, I still want to maintain my score.
We disagree with the characterization of our results. Several of the reviewer's claims are directly contradicted by the experiments in the revised manuscript.
First, the EoH/ReEvo comparisons do not merely demonstrate a quality–runtime trade-off. On Latent-class MDKP, our method achieves higher quality than ReEvo (0.9266 vs. 0.9169) while running 27.3× faster, using the same LLM and held-out instances (Table 14). This is a strict improvement in both quality and runtime.
Second, we explicitly provide quality-controlled comparisons in Appendix E.9. On OCM, our solver achieves the same objective values as the competition solvers on 30 exact-track and 27 cutwidth-track instances, with speedups of approximately 3.6–10.3× against pingpong and ocmu64. We additionally report anytime comparisons on Dominating Set and Hitting Set that establish substantial runtime advantages at comparable solution quality. These experiments directly address the reviewer's concern.
Third, combining remote LLM inference and reference-label generation does not materially change the amortization results. The combined median break-even is 150,666 solves, compared with 148,441 when excluding reference-label generation. All necessary measurements are already reported in Table 10.
Finally, while the different timing conditions of the classical catalog comparisons are an acknowledged limitation, this does not apply to all our comparisons, including the single-core EoH/ReEvo experiments.
We have undertaken substantial additional experiments specifically addressing the reviewer's original concerns. We believe these results should be evaluated on their merits, rather than dismissed on grounds that the new evidence directly addresses or contradicts.
Response
We thank the reviewer for the careful and thoughtful review. We addressed both weaknesses and both questions with new experiments. Changes are marked in red; references use the revised numbering.
(W1) Comparison with EoH and ReEvo
We now compare directly against EoH and ReEvo, using their official code, default search settings, and original prompts (Appendix E.4, Table 14). Their available frameworks cover two of our seven problem classes; we evaluated Clustered Euclidean TSP and Latent-class MDKP with Gemma 4, comparable token budgets, and the same held-out instances.
EoH achieves higher quality on both targets, and ReEvo on TSP; their heuristics nevertheless run 4.5–41× slower than our solvers synthesized with the same LLM, and slower than exact solvers Concorde and Gurobi.
The mechanisms differ: EoH and ReEvo evolve one heuristic inside a hand-written metaheuristic. On TSP, ReEvo's starting heuristic already reaches quality 0.9998 without LLM search. Our pipeline synthesizes the complete solver, using samples to identify reusable computation. The approaches occupy different quality–runtime operating points; neither dominates uniformly.
(W2) Offline cost recovery
We computed per-target break-even estimates against the fastest classical solver whose held-out quality is at least ours (Appendix D.5, Table 10). Our solver is faster on 19/21 targets. The median is:
The final figure is elapsed time, not monetary or LLM compute cost; token use is reported separately. The paper discloses that comparator times came from earlier parallel runs, so the counts are estimates. On the remaining two targets, an exact solver is already faster and no break-even exists.
(Q1) Robustness when learned structure is violated
We tested this directly (Appendix E.15, Table 32). We broke the planted patterns at increasing severities across seven representative targets, evaluating 4,000 instances.
Every output remained feasible. Four of the seven solvers maintained essentially unchanged quality (within 0.006) because they do not depend on a pattern-specific fast path. The other three detected violations and fell back to valid solutions, but quality fell to 0.61–0.97. Their original equal-quality speed advantage therefore did not persist.
Thus, fallback preserves feasibility, not necessarily quality. A rising fallback rate can also signal that the deployment distribution has shifted.
(Q2) How many training samples are needed?
We added a main-scale zero-sample comparison and a sample-size sweep (Appendix E.12, Tables 29–30).
Samples primarily improve speed in the main-scale comparison. With GPT-5.2 on four targets, solvers synthesized with 64 training instances are faster than those without—by 1.8×–227× on three targets and 1,101× in median time on Separator-trap. Yet zero-sample solvers achieve equal or higher quality; two speed gains involve lower solution quality. Validation feedback remains available in the zero-sample setting.
The required sample size depends on the distribution. We swept 0, 1, 4, 16, and 64 examples on four targets, with three Gemma 4 runs per setting:
We do not observe a universal or monotone sample-size threshold.
(Presentation)
We clarified the distinction from prior algorithm-discovery work (Section 2), the scope of the theoretical result (Section 3), and the interpretation of the main comparisons (Section 5.2). Protocols and supporting evidence now appear in focused appendices. We would welcome pointers to any sections that remain difficult to follow.
Please, let us know if we addressed your concerns and questions or we could anything else to further strenghten the manuscript thanks again for all the comments :)
Best,
The authors