acceptodds
Under review as a conference paper at ICLR 2027

Distribution-Aware Programming: Learning Specialized Solvers from Experience

Abstract

Many optimization problems are solved repeatedly on instances drawn from the same underlying distribution. In this setting, a system can begin with a general-purpose solver and use experience from previous instances to learn a cheaper way to solve future ones. We formalize this as distribution-aware programming: samples from an unknown deployment distribution are used to produce executable solver code whose quality and runtime generalize to new instances. A simple analysis shows how sample access interpolates between distribution-oblivious and distribution-informed algorithm design, and when the offline cost of specialization is recovered through lower deployment cost. We instantiate this framework with an LLM agent that proposes structural hypotheses, analyzes training instances, and synthesizes specialized solver code; the LLM is used only before deployment. Across \(21\) structured combinatorial-optimization distributions, the synthesized solvers achieve high quality while often replacing generic search or optimization with smaller distribution-specific computations. Against released PACE competition solvers, our method remains competitive while using substantially less runtime: \(75\)–\(125\times\) less on PACE 2025 Dominating Set, \(80\)–\(96\times\) less on Hitting Set, and more than \(34,000\times\) less on the PACE 2024 OCM exact track. More broadly, the results suggest using AI not only to solve optimization problems, but to learn how recurring distributions should be solved.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent systems, agents, llm

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_48eVOpenReview ↗
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
  1. 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
  1. 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.
  2. 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
  1. How robust are the generated solvers when test instances violate the structural patterns discovered during synthesis, and do their fallback mechanisms preserve solution quality?
  2. 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

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:

  • 696 solves: local synthesis computation only.
  • 3,249 solves: local synthesis plus public reference-label generation.
  • 148,441 solves: full recorded synthesis-stage elapsed time, including remote LLM inference and API latency, but excluding reference-label generation.

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:

  • Paired-ribbon TSP: With four examples, all three runs identify the ribbon structure and reach quality 1.000; all zero-sample runs fail.
  • Single-resource MDKP and Gateway-hub MDS: Quality is already high without samples.
  • Decoy-complement MDKP: Examples improve mean quality from 0.251 to about 0.57–0.67, but none of the tested sample sizes yields consistently high quality.

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

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.

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

This paper studies how to generate specialized solvers for combinatorial optimization problems when instances are drawn from a known distribution. The proposed Distribution-Aware Programming framework uses an LLM to analyze sampled instances, identify common structural patterns, and write solver programs. These programs are tested and revised based on validation results. Once a solver is selected, it can be applied to new instances without further LLM calls. The authors also provide a theoretical analysis of sample access and expected running time. The evaluation includes 21 distributions from seven optimization problems and additional PACE benchmarks. The results suggest that the generated solvers can achieve good solution quality with much lower inference-time cost than several existing methods.

Critical strengths

The idea of moving expensive LLM reasoning into an offline synthesis stage is interesting. Generating reusable solver code rather than invoking an LLM for every new instance could be useful for repeated optimization workloads. The experiments cover several optimization problems and include external PACE benchmarks. The reported runtime improvements are substantial, and the comparison with competition solvers is a useful addition.

Critical weaknesses
  1. The contribution of distribution-specific learning is not sufficiently established.

The main idea is closely related to existing work on algorithm configuration, program synthesis, and LLM-based automatic algorithm design. The proposed pipeline combines structural hypothesis generation, code synthesis, validation, and iterative refinement, but it is unclear what fundamentally distinguishes the learning mechanism from existing approaches.

The theoretical contribution is also limited. Proposition 3.1 essentially applies standard finite-class generalization arguments to bounded-runtime programs. More importantly, the analysis assumes a fixed class of correct solvers, while the actual method generates approximate solvers through LLM-guided search. I do not see how this result provides a meaningful guarantee for the proposed synthesis procedure.

The experiments leave similar questions. In Table 21, removing the training instances produces almost identical solution quality across the 12 evaluated targets. While sample access improves runtime on several targets, the result raises questions about how much of the final solver quality actually comes from learning distributional structure. The zero-sample variant also retains validation feedback, making it difficult to isolate the effect of sample access.

The matched hint ablation in Table 12 provides some evidence for explicit structure discovery, but the largest improvements are concentrated in two of the seven evaluated targets. The no-hint variant is also faster on average. I would like to see stronger evidence that the proposed structural learning stage provides consistent benefits beyond ordinary iterative code refinement.

  1. The reported efficiency gains are difficult to interpret, and some synthesized solvers appear surprisingly fragile.

My main concern is the robustness of the generated solvers. Appendix E.12 shows that simply permuting vertex labels can substantially reduce solution quality, even though the underlying graph remains unchanged. For Geometric-anchor MDS, quality drops from 1.000 to 0.536. For Ring-template Coloring, it drops from 1.000 to 0.772.

These are large changes caused by a representation-level transformation that does not alter the optimization problem. This suggests that some generated solvers rely heavily on vertex ordering or labeling rather than the underlying graph structure. For a method claiming to learn reusable distribution-specific algorithms, I consider this a serious limitation. The paper acknowledges these cases, but does not demonstrate how they can be addressed.

I also find the runtime comparisons somewhat misleading. For example, the reported 34,604× speedup on the PACE 2024 OCM exact track compares solutions with different objective values. The synthesized solver obtains 148,091, while cimat achieves 143,195. This is a quality–runtime tradeoff, not an equivalent-quality speedup.

The method also requires substantial offline computation. Table 9 reports 73.4 hours of recorded synthesis-stage time and over 16 million generated and prompt tokens across the 21 targets. Although excluding offline synthesis from deployment runtime is reasonable, the paper does not provide a sufficiently concrete analysis of how many future instances are needed to recover this cost.

Questions for authors

1/Why does graph relabeling cause such large performance drops on Geometric-anchor MDS and Ring-template Coloring? Would the generated solvers remain effective if the training and validation instances used randomized vertex labels?

2.How much does the structural hypothesis and hint stage contribute beyond iterative code refinement? Can the authors extend the matched no-hint ablation to all 21 distributions?

3.Can the authors provide quality-matched runtime comparisons on the PACE benchmarks, particularly OCM? How many deployment instances are required to amortize the offline synthesis cost?

4.How does Proposition 3.1 relate to the actual LLM-generated solvers, which are approximate and selected from a dynamically generated program space rather than a fixed class of correct algorithms?

2 comments
AuthorsOpenReview ↗

Response, part 1/2

We thank the reviewer for the careful and thoughtful review. It motivated new experiments, clearer distinctions from prior work, and more precise claims. Let us know whether below we addres them all conclusively for you! We are very willing to further work with you to clear up any further question :) Changes are marked in red. In the original submission, Appendix E.12, Table 12, and Table 21 correspond to Appendix E.16, Table 15, and Table 27, respectively, in the revision. All references below use the revised numbering.

(W1.1) Contribution beyond existing algorithm-design methods

The main distinction is what is learned and how instances are used. Algorithm configuration selects among existing solvers. EoH and ReEvo evolve a heuristic function within a fixed, hand-written metaheuristic, using fitness feedback. Our pipeline instead writes the complete solver, jointly proposing a structural hypothesis, an analysis program that examines training instances, and a solver conditioned on the resulting summary. It runs across seven problem classes without a problem-specific heuristic-evolution framework or deployment-time LLM calls.

We now make this distinction explicit in Section 2 and evaluate it directly. EoH reaches higher quality on both supported targets (and ReEvo on TSP), but their heuristics run 4.5–41× slower than ours synthesized with the same LLM (Appendix E.4). Selecting from our classical solver catalog also fails to reproduce the quality–runtime trade-off: the fastest quality-matching catalog selector is 27.9× slower and covers 19/21 targets (Appendix E.6).

(W1.2) Scope of Proposition 3.1

We agree that the proof uses a standard finite-class argument. We do not claim the bound itself is novel or that it guarantees successful LLM synthesis.

Its role is to formalize the computational value of sample access. For a fixed, bounded-description program class, sample-conditioned expected runtime approaches the distribution-informed optimum as the sample size grows. Including offline selection cost yields a condition for when specialization reduces cumulative computation.

LLM-guided search is a practical approximation to this sample-to-solver selection process. The proposition does not guarantee that search discovers a good program or provide a performance guarantee for our generated solvers. The same statistical argument applies to approximate solvers if loss is a bounded combination of runtime and solution quality. We state this scope explicitly in Section 3 and study amortization empirically in Appendix D.5.

(W1.3) What do training instances contribute?

The original zero-sample experiment does not show that samples improve solution quality. Validation feedback remains available, so it isolates direct training-instance access, not all access to the distribution. Appendix E.12, Table 28 now specifies the feedback precisely.

We also reran the comparison with GPT-5.2 at main-experiment scale on four targets (Table 29). Without training instances, quality is equal or higher on all four; with instances, runtime is lower on all four—by 1.8×–227× on three targets and 1,101× in median time on Separator-trap. Two of the four faster solvers also have lower quality.

The selected hypotheses explain the difference: with training instances, the system identifies structures such as the two rails in Paired-ribbon TSP. Without them, it chooses less suitable hypotheses and compensates with generic search. Validation feedback can identify high-quality solutions; direct sample access can reveal how to compute them much faster. We now state this narrower conclusion in Section 5.2.

(W1.4) Structural hints versus ordinary refinement

We ran two additional studies on all 21 targets with Gemma 4 and three runs per variant.

Matched hint ablation (Appendix E.5, Table 16): Hints improve quality on 5/6 MDKP and Packing LP targets (mean 0.855 vs. 0.777) but not on the other 15 (0.924 vs. 0.938). The no-hint solvers are faster; we do not claim a uniform advantage.

Token-matched search comparison (Appendix E.3, Table 13): Our pipeline reaches mean quality 0.904 versus 0.826 for a single refinement chain without hypotheses. The gap comes from MDKP and Packing LP (0.855 vs. 0.580); the methods are comparable on the other 15 targets.

These results identify where structural hypothesis search and hint extraction improve over plain refinement, and where they do not.

AuthorsOpenReview ↗

Response, part 2/2

(W2.1) Label dependence and robustness

We identified the causes of the two relabeling failures. Ring-template has a coloring tied to fixed vertex IDs; Geometric-anchor assigns clusters using i mod 3. The selected solvers exploit these conventions. Edge-order shuffling alone has no effect, and the other seven graph targets show little change in mean quality.

We then reran synthesis with randomized vertex IDs in training, validation, and testing (Appendix E.16, Table 35):

  • Geometric-anchor: A label-free solver identifies clusters from graph neighborhoods, reaching quality 0.980 and running 6.2× faster than an exact solver at quality 1.000.
  • Ring-template: The new solver reaches quality 0.861 but is slower than exact. Its original speedup depends on stable vertex IDs.

We also broke the planted structural rules at increasing severity (Appendix E.15). All 4,000 outputs remained feasible. Pattern-dependent solvers fell back to valid solutions, sometimes with substantial quality losses. Section 6 now distinguishes structural from encoding-specific specialization and states the limitations under distribution shift.

(W2.2) PACE speedups and equal-objective comparisons

We agree that 34,604× on OCM is a speed–quality trade-off, not an equal-quality speedup. It compares mean runtimes at different objective values and is influenced by a few long baseline runs. We now state this in the abstract, Section 5.2, and Table 4.

Appendix E.9 adds quality-controlled comparisons, using equal-objective subsets for OCM and fixed-time budgets for Dominating Set and Hitting Set:

  • OCM exact: Our heuristic is optimal on 30/100 instances; on those 30, pingpong and ocmu64 take 7.5× and 6.9× longer.
  • OCM cutwidth: Our solver ties the released solvers on 27/100 instances; on those 27, pingpong and ocmu64 take 10.3× and 3.6× longer.
  • Dominating Set and Hitting Set: The strongest released solver takes roughly 10–30 seconds to match or beat our results on most instances, versus 2.89 and 3.75 seconds for ours.

Thus, the large full-budget ratios reflect speed–quality trade-offs. The equal-objective OCM subset comparisons and the Dominating Set/Hitting Set anytime evaluations still show meaningful runtime savings.

(W2.3) Recovering offline computation

We computed break-even estimates for all 21 targets (Appendix D.5, Table 10), using the fastest classical solver whose mean held-out quality matches or exceeds ours. Our solver is faster on 19/21 targets. Median break-even counts are 696 solves for local synthesis computation, 3,249 including public reference-label generation, and 148,441 for recorded synthesis-stage elapsed time (including remote inference and latency, but excluding reference-label generation).

The last figure is not a measure of LLM compute or dollar cost; token usage is reported separately. Test-label creation and 417 hours of baseline evaluation are benchmark costs and excluded. Two targets have no break-even. Appendix D.5 also discloses the timing-protocol caveat: our solvers were re-timed on an idle machine, whereas comparator times came from earlier parallel evaluations.

(Q1–Q4) Direct answers

Q1 — Randomized labels: Geometric-anchor retains a label-free specialization (quality 0.980, 6.2× faster than exact); Ring-template does not. See W2.1.

Q2 — Structural hints: The 21-target hint ablation and matched-budget refinement comparison establish a benefit concentrated on MDKP and Packing LP. See W1.4.

Q3 — PACE and amortization: We added quality-controlled PACE comparisons and per-target break-even estimates. See W2.2–W2.3.

Q4 — Proposition 3.1: It characterizes the potential value of sample-conditioned selection within a fixed class; it does not guarantee successful LLM search. See W1.2.

Please, we are very willing to work further to clear your concerns :) let us know if we addressed them and we satisfactorily answered all your questions or we could anything else to further strenghten the manuscript! thanks again for all the comments :)

Best,

The authors

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

The paper studies learning executable solvers for recurring optimization-instance distributions. An LLM agent proposes structural hypotheses, analyzes training instances, and refines solver code using validation feedback. The deployed solver uses the new instance and a reusable summary, without an LLM call. The formal framework compares distribution-oblivious, distribution-known, and sample-informed solver selection. Proposition 3.1 gives an expected-runtime guarantee for a fixed, description-bounded class of correct programs with uniformly bounded runtime. This is a statistical existence result, not a guarantee that the practical synthesis procedure finds an optimal program or that its heuristic outputs are optimal.

Experiments cover 21 structured distributions and released private PACE benchmarks. The controlled suite uses 64 training, 32 validation, and 500 held-out instances per distribution. The paper reports high average quality and low deployment runtime, with additional catalog-selection, hint, repeated-synthesis, and relabeling studies. The PACE results are speed–quality trade-offs: in particular, the method is not an exact solver merely because it is evaluated on the OCM exact-track dataset.

Critical strengths
  1. The paper evaluates the idea beyond a few convenient synthesis examples. The 21-distribution suite is backed by external PACE instances and several strong comparisons. The fastest catalog selector that matches the method’s validation quality is 27.9× slower and covers 19/21 targets, which is more persuasive than comparing only against a generic solver with a large time limit. The paper also acknowledges cases where KaMIS or one-shot synthesis is better. This makes the empirical contribution credible without implying universal dominance.

  2. The information-access formulation and executable deployment are a useful combination. Proposition 3.1 cleanly expresses what samples can buy for program selection, while the practical system compiles experience into code rather than paying for an LLM on every instance. The appendix examines hints, shortcuts, fallbacks, synthesis variability, and per-distribution computations. These analyses help explain what the generated solvers actually do.

Critical weaknesses
  1. Some of the strongest specializations depend heavily on vertex-label conventions. Appendix E.12 is an important diagnostic: random relabeling drops Ring-template quality from 1.000 to 0.772 and Geometric-anchor from 1.000 to 0.536, although the underlying graph problem is unchanged. This is not train/test leakage, and exploiting labels can be legitimate when the deployment distribution preserves them. However, it limits the interpretation that the system has discovered an efficient solver for the underlying structural family. The paper should distinguish reusable problem structure from reusable encoding conventions, especially when using these examples to explain the broader paradigm.

  2. The benefit of the synthesis procedure is not fully separated from its offline search budget. The controlled-suite synthesis uses 463 successful calls and about 16.11 million tokens, whereas important agent comparisons use one-shot or best-of-five generation. The hint and sample-count ablations are useful and should not be discounted, but they do not establish whether the proposed search is better than another synthesis strategy at comparable resources. This matters because the paper’s practical advantage is reduced cumulative computation, not deployment time alone. The cost tables disclose substantial preparation work, yet the formal amortization condition is not turned into a representative empirical break-even calculation.

Questions for authors
  1. What remains of the major speedups if graph labels are randomized during both training and testing? For deployments where ordering is meaningful, what representation convention is assumed to remain stable? This would clarify whether the affected examples are structural shortcuts or encoding-specific shortcuts.

  2. Under a comparable total synthesis budget, how does the procedure compare with repeated independent generation or another refinement strategy? Please provide the exact search settings and clarify what validation feedback remains available in the “zero-sample” condition.

  3. For one or two representative distributions, how many future solves are required to recover synthesis and training-sample analysis costs? Please distinguish the preparation that is intrinsic to the method from the much larger benchmark-construction and baseline-evaluation costs.

2 comments
AuthorsOpenReview ↗

Response, part 1/2

We thank the reviewer for the careful and thoughtful review. We addressed both weaknesses with controlled experiments and a per-target amortization analysis. Changes are marked in red; references use the revised numbering (former Appendix E.12 is now E.16).

(W1) Dependence on vertex-label conventions

We agree that structural specialization must be distinguished from encoding-specific shortcuts. The two affected generators attach planted structure to fixed vertex IDs. With randomized labels throughout synthesis and testing, Geometric-anchor retains quality 0.980 and a 6.2× speed advantage over an exact solver at quality 1.000, whereas Ring-template loses its speed advantage. The other seven graph targets show little change in mean quality under relabeling. We make the distinction explicit in Section 6 and Appendix E.16; details follow under Q1.

(W2) Search budget and amortization

We added both requested analyses. At matched recorded token budgets across 21 targets, our Gemma 4 pipeline achieves 0.904 mean quality, compared with 0.815 for independent generation and 0.826 for a single refinement chain (Appendix E.3). Against the fastest classical solver with at least our held-out quality, our solver is faster on 19/21 targets. Median break-even counts are 3,249 solves including public reference-label generation, or 148,441 when counting recorded synthesis-stage elapsed time instead (Appendix D.5). Details follow under Q2–Q3.

(Q1) What survives randomized labels?

We identified the causes: Ring-template plants the same vertex-to-color template across instances; Geometric-anchor assigns vertex i to cluster i mod 3. Their selected solvers exploit those conventions. Shuffling edge order alone does not produce the drops.

The deployment assumptions differ. Ring-template needs consistent vertex IDs across instances: re-running its analysis program under a different but consistent numbering restores quality 1.000 without an LLM call. Geometric-anchor hard-codes the original numbering.

We then reran synthesis with independently randomized labels on every training, validation, and test instance (Appendix E.16, Table 35):

  • Geometric-anchor: The new solver identifies three clusters from vertex neighborhoods, reaches quality 0.980, and is 6.2× faster than the exact solver (quality 1.000).
  • Ring-template: The new solver reaches quality 0.861, but runs in 99.4 ms versus 17.5 ms for the exact solver.

Thus, Geometric-anchor supports a label-free structural specialization; the original Ring-template speedup depends on stable vertex identities.

(Q2) How does search compare at matched budgets?

We ran three Gemma 4 replicates on each of 21 targets, matching the recorded per-target token budget of our pipeline (Appendix E.3, Table 13):

Synthesis strategyMean quality
Our pipeline0.904
Independent generation0.815
Single refinement chain, no hypotheses0.826
Independent generation, all attempts (at least 1.5× the recorded budget)0.831

The advantage is concentrated on MDKP and Packing LP (0.855 versus 0.580 for the single chain); methods are comparable on the other 15 targets. Because retried calls are not fully reflected in our logs, recorded token usage is a lower bound on actual pipeline usage.

Search settings (Appendix C): three rounds, beam width three, three candidates per round—nine candidates and at most 27 LLM calls per target; 64 training and 32 validation instances.

Zero-sample feedback (Appendix E.12, Table 28): Only direct access to training instances is removed. Validation scores still select candidates; refinement receives aggregate scores and up to three failure cases. Each case includes an instance ID, objective, normalized quality, and solution prefix, but not the instance. Objective and quality can reveal its optimal value. We now disclose this in Section 5.1.

AuthorsOpenReview ↗

Response, part 2/2

(Q3) When are offline costs recovered?

Appendix D.5 (Table 10) gives break-even counts against the fastest classical catalog solver whose mean held-out quality is at least ours:

TargetLocal synthesis onlyLocal synthesis + public labelsRecorded synthesis-stage time*
Latent-class MDKP141,1681,841
Overlapping-palette Coloring56583,548166,322
Median (19 targets with savings)6963,249148,441

*The final column includes remote LLM inference and API latency but excludes public reference-label generation; it measures recorded elapsed time, not LLM compute cost. LLM usage averages 22 calls and 767K tokens per target. Held-out test labels and 417 hours of baseline evaluation are benchmark costs and excluded. Two targets have no break-even because a quality-matching exact solver is already faster. These are empirical estimates; the appendix discloses that our solvers were re-timed on an idle machine while comparator times came from earlier parallel runs.

(Paper summary) Interpretation of PACE exact-track results

We agree. Our OCM solver is a heuristic evaluated on exact-track instances, not an exact solver. The 34,604× runtime ratio compares different objective values and is now explicitly identified as a speed–quality trade-off in the abstract, Section 5.2, and Table 4.

Our solver reaches the optimum on 30/100 exact-track instances. On those 30, pingpong and ocmu64 run 7.5× and 6.9× longer, respectively. Quality-controlled comparisons across the PACE tracks appear in Appendix E.9.

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

Comments on the paper

1 comment

Dear reviewers,

As the authors have posted their responses, I would encourage you to actively parcitipate in the dicussion.

Thank you.

Best,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.