- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes CHSS for LLM-based combinatorial optimization, where a problem heuristic completes partial solutions and the LLM verifies them in one parallel pass, with illegal moves masked so every solution is feasible. On TSP, JSSP, Knapsack and BinPack, it reaches lower optimality gaps than ACCORD sampling under the same sample budget.
Critical strengths
- A good combination of heuristics and the LLM: the heuristic completes partial solutions cheaply, while the LLM provides the learned distribution and verifies them.
- Low cost: one model sample yields several candidate solutions, and the number of LLM forward passes is reduced.
Critical weaknesses
- No runtime evidence. The paper claims gains in processing time, but there is no wall-clock or GPU-time comparison.
- Limited experimental scale. TSP goes up to 20 cities and JSSP up to 15 jobs. At this scale exact solvers are near-instant, so the results say little about practical value.
- Narrow baselines. The method is only compared with ACCORD sampling. There is no comparison with classical heuristics plus local search, neural constructive solvers, or LLM-based heuristic design methods such as EoH, FunSearch or ReEvo.
- Unclear budget fairness. CHSS evaluates several heuristic completions per model sample (Table 3), yet the budget is stated as “60 samples”. Whether these extra solutions count toward the budget is not stated, and Table 2 shows they contribute a large share of the gain.
- Method not described clearly enough. The rule for accepting or rejecting a speculated move is not given, so it is unclear whether samples follow the model distribution. The claim in the abstract that the policy converges to the constrained model distribution is not proved or tested.
- Table inconsistencies. The “CHSS” row in Table 2 is identical to the “CHSS w/ PA” row in Table 1, but Table 4 reports a different CHSS value for TSP (0.313 vs. a Table 2 mean of about 0.265). Table 4’s PA values for JSSP (0.534) and Knapsack (0.0735) do not match the simple averages of Table 1 (about 0.267 and 0.093), while TSP and BinPack do. The averaging method is not explained.
- Limited novelty. The components largely exist already, and the paper does not clearly separate its own contribution.
Questions for authors
- What are the wall-clock time and number of LLM forward passes of CHSS versus sampling at equal quality?
- Are heuristic solutions counted in the 60-sample budget? What happens if the baseline gets the same number of evaluated candidates?
- How does CHSS compare with EoH-style or other LLM+heuristic methods, and with classical heuristics plus local search?
- Can the method scale to larger instances?
- Could the authors fix and explain the discrepancies between Tables 1, 2 and 4?