- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper presents HINTS, an LLM-based framework for generating instance-adaptive MIP warm starts. The LLM generates executable construction heuristics whose solutions are injected into an unchanged MIP solver. A growing experience library records reusable construction strategies and their applicability, with experience selection and updates informed by subsequent solver performance. Experiments cover eight CO-Bench tasks and three solvers, comparing HINTS with solver-only runs and classical heuristic warm starts. The paper also includes component ablations and an evaluation that charges generation and heuristic execution against the same 600-second budget.
Critical strengths
-
A practical interface between LLM-generated heuristics and established MIP solvers. HINTS supplies an external warm start while preserving the solver’s formulation and native search procedures. Evaluating constructions through downstream solver progress, rather than initial solution quality alone, aligns the framework with the eventual optimization objective.
-
Useful empirical support for cross-instance experience reuse. The experiments show average improvements across several problem families and solvers, including under the supplementary accounting that includes generation time. The ablation provides evidence for the experience library’s contribution: removing it increases the average Gurobi gap from 0.121 to 0.185. This supports the value of accumulating construction experience beyond independently prompting an LLM for each instance.
Critical weaknesses
-
The actual LLM overhead is insufficiently characterized. Appendix F is a useful inclusion and shows that benefits remain when generation and heuristic execution are charged against the time budget. However, the paper does not separately report latency distributions, call counts, token consumption, or monetary cost. It is also unclear whether the accounting includes applicability assessment, repair attempts, and amortized library updates. These details matter because the framework invokes the LLM for individual instances, and its practical advantage depends on the complete overhead.
-
Robustness to instance ordering remains unclear. The experience library evolves using feedback from previously processed instances, but the evaluation uses only one instance ordering. The reported gains may therefore depend on how related instance regimes are arranged in the stream. Additional evidence across different orderings would help establish the reliability of the cross-instance adaptation.
Questions for authors
-
Could you provide the complete prompt templates and call protocol, together with per-instance latency statistics, call counts, and token or monetary costs? Please clarify which stages are included in Appendix F, particularly applicability assessment, failed attempts and repairs, and library updates, and how shared update costs are amortized.
-
How was the instance ordering determined? Do the main improvements, particularly the benefit of the experience library, remain stable across multiple randomized orderings?
6 comments
- Response to W2/Q2
W2: Robustness to instance ordering remains unclear. Q2: How was the instance ordering determined? Do the main improvements, particularly the benefit of the experience library, remain stable across multiple randomized orderings?
Thank you for pointing this out. The original experiments followed the dataset’s default instance order. To assess HINTS’s robustness to changes in that order, we reran HINTS with Gurobi on all eight tasks, shuffling the instances within each task. The seeds in the table below specify the shuffle order for each rerun.
Table 2. HINTS performance with Gurobi under three online instance orders, with each metric shown as average gap and auc.
| Instance order | Bin (160) | CDD (70) | Cont. (762) | Flow (120) | Job (80) | Open (60) | Set (87) | TSP (272) | Average |
|---|---|---|---|---|---|---|---|---|---|
| Original order | 0.003 / 0.015 | 0.066 / 0.075 | 0.252 / 0.262 | 0.113 / 0.136 | 0.323 / 0.386 | 0.158 / 0.181 | 0.031 / 0.045 | 0.021 / 0.038 | 0.121 / 0.142 |
| Seed 1109 | 0.003 / 0.018 | 0.051 / 0.058 | 0.250 / 0.258 | 0.113 / 0.136 | 0.313 / 0.345 | 0.155 / 0.177 | 0.033 / 0.057 | 0.025 / 0.044 | 0.118 / 0.137 |
| Seed 1201 | 0.003 / 0.019 | 0.050 / 0.054 | 0.251 / 0.260 | 0.113 / 0.138 | 0.314 / 0.348 | 0.156 / 0.178 | 0.032 / 0.048 | 0.022 / 0.039 | 0.118 / 0.136 |
Shuffling the instances led to only modest changes in HINTS’s performance, with improvements on some tasks. Although HINTS showed some sensitivity to instance order, its gains persisted across the tested sequences. This suggests that the gains extend beyond the original ordering and supports the reliability of HINTS across different sequences of instances.
Apologies for the delayed reply; it’s been a busy week. Thank you for the detailed response and the additional experiments. The cost breakdown and shuffled-order results address my main concerns, and I continue to support acceptance.
I have one clarification about the new metaheuristic baseline. In the row labeled “Meta-Heuristic (30s) → Gurobi (600s),” is the 30-second preparation included in the 600 seconds, or is the total budget 630 seconds? If you already have results with both methods under the same 600-second total budget, I’d be interested to see them. The two average gaps are quite close, so this would help me interpret what is otherwise an encouraging comparison.
Thank you for your questions.
(1) We added the full prompt templates to Appendix D of the revised manuscript.
(2) We added a detailed breakdown of LLM usage and costs to Appendix H, as shown in the table below.
Table 1. Mean LLM usage and estimated cost by task. Token counts include input and output tokens. LLM wait and preparation are measured per instance. All costs are in US dollars.
For each instance, LLM wait time is the sum of the time spent on applicability assessment, heuristic code generation, and repair requests. Preparation time includes this wait and the time spent executing the heuristic code. We allocate an equal share of each wave’s library update call, token usage, and estimated cost to every instance in that wave. We compute per-call averages by dividing total token usage and estimated cost by the total number of calls. The API time for library updates averages less than one second per instance after amortization.
We estimated costs from recorded token usage using public off-peak rates of USD 0.003 per million cached input tokens, USD 0.15 per million uncached input tokens, and USD 0.60 per million output tokens.
(3) We expanded the description in Appendix I (formerly Appendix F). In the main experiments, each run uses a 600-second solver time limit. When warm-start preparation is counted toward the 600-second total budget, we first deduct the time spent on LLM-based applicability assessment, heuristic code generation, code execution, and any LLM repair calls. Code execution time includes failed attempts and reruns of repaired code.We also split the cost of updating the experience library evenly among the instances in each wave.The MIP solver then uses the remaining time.