acceptodds
Under review as a conference paper at ICLR 2027

Large Language Model for Combinatorial Optimization by Leveraging Policy Adaptation and Heuristics

Abstract

Many techniques have been used to elicit reasoning within Large Language Models (LLMs), and several methods have been developed to solve NP-hard combinatorial problems (CPs). Certain methods relies on prompting strategies to sample solutions from the LLM, potentially finetuned on previous problems to improve the quality of the samples. If the budget allows it, multiple independent samples are obtained and the best solution is retained. Larger model correlate with higher quality solutions, but are also more costly to sample. Meanwhile, heuristics exists for many problems that generate good enough solutions for combinatorial problems very quickly. We present a method to progressively sample a solution from a finetuned model distribution via a series of heuristic solutions, each analyzed by the model to lead to the next heuristic solution. Furthermore, we show how to use the constraints of the problem to improve the samples as well as progressively build a policy from the solutions to improve the future samples. We demonstrate on various combinatorial problems (Binpack, Knapsack, Vehicle Routing Problem and Job-shop scheduling) and various models that the method improves the solutions that can be obtained by using simple heuristics, and that the method is superior to using the LLM simply as a sampling tool in terms of processing time, number of samples and solution quality. We also show further improvement obtainable by constructing a policy progressively from the previous samples and a the constraints of the problem. We show that the computed policy converges eventually to a distribution equivalent to the model with the constraints of the Combinatorial problem.

Primary area:
generative models
Keywords:
Large Language Models, Combinatorial Optimisation

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.25 over 4 reviews, above 2% of the others.
Reviewer_1NK3OpenReview ↗
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
  1. A good combination of heuristics and the LLM: the heuristic completes partial solutions cheaply, while the LLM provides the learned distribution and verifies them.
  2. Low cost: one model sample yields several candidate solutions, and the number of LLM forward passes is reduced.
Critical weaknesses
  1. No runtime evidence. The paper claims gains in processing time, but there is no wall-clock or GPU-time comparison.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Limited novelty. The components largely exist already, and the paper does not clearly separate its own contribution.
Questions for authors
  1. What are the wall-clock time and number of LLM forward passes of CHSS versus sampling at equal quality?
  2. Are heuristic solutions counted in the 60-sample budget? What happens if the baseline gets the same number of evaluated candidates?
  3. How does CHSS compare with EoH-style or other LLM+heuristic methods, and with classical heuristics plus local search?
  4. Can the method scale to larger instances?
  5. Could the authors fix and explain the discrepancies between Tables 1, 2 and 4?
Reviewer_NT7VOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1(−1)
Read review
Paper summary

This paper presents Constrained Heuristic Speculative Sampling (CHSS), a method that combines speculative decoding with problem-specific heuristics for LLM-based combinatorial optimization. The basic idea is to use heuristics to extend partial solutions and then let the LLM verify the proposed tokens, rather than generating every token autoregressively. The framework also includes constrained decoding, policy caching, and policy adaptation. The authors evaluate CHSS on four optimization problems: TSP, Bin Packing, Knapsack, and Job Shop Scheduling. Experiments with fine-tuned Llama 3.1 and Qwen3 models show improvements in solution quality and feasibility compared to standard LLM sampling. The paper also studies the effects of heuristic speculation and policy adaptation.

Critical strengths

I think combining heuristic completion with speculative decoding is a reasonable idea. For combinatorial optimization, where constructing feasible solutions is often easier than finding high-quality ones, using heuristics to reduce autoregressive generation could be useful. The results also suggest that CHSS handles feasibility better than ordinary LLM sampling, especially as problem size increases. This is a positive aspect of the method.

Critical weaknesses
  1. The evaluation does not convincingly show the advantage of CHSS over existing optimization methods.

My biggest concern is the choice of baselines. Most experiments compare CHSS with standard LLM sampling or constrained decoding variants. However, CHSS itself uses problem-specific heuristics, so I think it is necessary to compare it against stronger traditional optimization algorithms.

For TSP, the paper only includes one constructive heuristic as a classical baseline. There are no results against multi-start heuristics, local search, or well-established TSP solvers. The same problem exists for the other tasks. Without these comparisons, I cannot tell how much the LLM actually contributes to finding better solutions. It is possible that a relatively simple heuristic search method could achieve similar or better results at much lower cost.

I also have questions about the computational budget used in the experiments. The authors evaluate 60 samples per instance, but one CHSS sample may involve generating and checking several heuristic completions. This is not necessarily comparable to generating 60 solutions with standard LLM decoding. I would prefer to see comparisons based on wall-clock time rather than just the number of samples.

Another limitation is the scale of the experiments. The TSP instances contain no more than 20 cities, and the JSSP instances are also relatively small. These settings seem too limited to demonstrate the usefulness of the method for more challenging combinatorial optimization problems. Larger instances would be important, particularly given the paper's emphasis on efficiency.

  1. The policy adaptation mechanism is not well justified, and its empirical benefits are unclear.

The authors state that the adapted policy eventually approaches a distribution equivalent to the constrained model distribution. However, I did not find a formal proof establishing this property. Some details of the sampling and policy updates in Algorithm 1 are also not sufficiently explained. I am not sure under what assumptions this convergence claim is expected to hold.

More importantly, the results do not consistently show that policy adaptation is beneficial. In Table 4, for Qwen3-8B, the JSSP optimality gap increases from 0.718 with policy caching to 0.739 with adaptation. A similar result appears on TSP, where the gap increases from 0.242 to 0.266. For Knapsack, adaptation also performs slightly worse than CHSS without caching.

These results make the additional adaptation mechanism difficult to justify. If adaptation is an important contribution, I would expect clearer evidence that it improves performance, or at least some analysis explaining when it helps and when it does not.

The efficiency results are also not fully convincing. Table 3 mainly reports how many heuristic completions are generated per model sample. However, generating more heuristic completions does not automatically mean that the overall method is faster. The LLM still needs to verify tokens, and policy adaptation introduces additional computation. I would like to see actual end-to-end runtime measurements that include all these costs. The experiments do not clearly show which components lead to the reported improvements. It is also unclear whether CHSS can compete with established optimization algorithms.

Questions for authors

1.Why are stronger classical optimization baselines missing? Can the authors compare CHSS with local search or other established heuristics under the same runtime budget, particularly for TSP and JSSP?

2.How is the computational budget controlled across different methods? Since CHSS can evaluate multiple heuristic completions within one sample, I do not think comparing the same number of samples is sufficient. Could the authors report end-to-end runtime results?

3.What supports the claim that the adapted policy converges to the constrained model distribution? Are there specific assumptions required for this result, and can the authors provide either a proof or empirical verification?

4.In Table 4, policy adaptation performs worse than policy caching on several Qwen3-8B tasks. Why does this happen, and what is the main advantage of including adaptation if it does not consistently improve solution quality?

Reviewer_e7AbOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes Constrained Heuristic Speculative Sampling (CHSS), which combines heuristic completions, constrained decoding, and speculative sampling to improve LLM-based combinatorial optimization. It further introduces a prefix-tree cache and constraint-based policy adaptation. Experiments on four problem families report improvements over ACCORD-style LLM sampling.

Critical strengths

Using inexpensive heuristic completions to reduce sequential LLM decoding is a sensible design.

Explicit constraint handling improves the reported feasibility and solution quality over the evaluated LLM baseline.

The evaluation covers multiple problem families and includes component ablations.

Critical weaknesses
  1. Insufficient justification for the LLM backbone.

The framework primarily requires an autoregressive action distribution, a feasibility checker, and a heuristic completion procedure; these components do not inherently require language pretraining. The experiments involve standard, formally specified optimization problems and still require task-specific fine-tuning and vocabulary expansion. No clear advantage in language understanding, data efficiency, or transfer is demonstrated. Consequently, the paper establishes improvements within an LLM pipeline without sufficiently explaining why an 8B language model is an appropriate choice over a dedicated NCO policy.

  1. Limited novelty and positioning relative to neural–heuristic optimization.

Heuristic-generated supervision and hybrid neural–heuristic search have already been explored in learning-based combinatorial optimization, including Neural Large Neighborhood Search and Learning to Delegate. Although inference-time speculative proposals differ from heuristic supervision, the paper does not adequately position this distinction or establish its incremental value. The contribution largely combines existing decoding and constraint-handling mechanisms, while the policy adaptation gains are modest and inconsistent in Table 4. Stronger analysis is needed to establish the significance of the proposed combination.

  1. Missing competitive baselines and incomplete cost comparisons.

The evaluation lacks comparisons against compact, task-specific NCO networks trained end to end. RSLoRA reduces trainable parameters, but this alone does not demonstrate a favorable trade-off relative to training and deploying a smaller neural solver. Comparisons should include solution quality, training/adaptation cost, inference latency, and memory consumption. Furthermore, allocating 60 model samples does not equalize computational effort: CHSS evaluates additional heuristic completions that also contribute to the best solution. Matched wall-clock comparisons and a backbone ablation retaining the same heuristic and constraint components are needed to establish where the gains come from.

Questions for authors

See weaknesses.

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

The paper proposes Constrained Heuristic Speculative Sampling (CHSS), which uses classical heuristics to complete partial solutions and an LLM to evaluate these proposals through speculative sampling. It enforces feasibility constraints, caches decision probabilities, and adapts the cached policy using grammar-aligned decoding. Experiments on four combinatorial optimization problems report improved feasibility and solution quality over direct LLM sampling.

Critical strengths
  1. Using inexpensive optimization heuristics as speculative proposals is a promising idea. Separating deterministic structural/calculation tokens from decision tokens also addresses an identifiable inefficiency in LLM-based optimization.
  2. The experiments cover four problem families and two model backbones. Table 2 shows benefits beyond constraint enforcement alone: on TSP-20, the reported gap decreases from 4.21% with constrained sampling to 1.38% with CHSS.
Critical weaknesses
  1. The evaluation does not adequately establish efficiency or isolate the contributions. Although each method receives 60 samples, CHSS evaluates multiple heuristic candidates per completed model sample, so equal sample counts do not imply equal computational budgets. The claimed 156× speedup lacks supporting runtime tables and sufficient implementation details. Moreover, constrained-sampling ablations are limited to TSP, and the heuristic baseline uses only one heuristic call. Comparisons against repeated heuristic search and conventional solvers under matched runtime budgets are needed. Policy adaptation also provides inconsistent gains: for Qwen3, it performs worse than caching alone on both TSP and JSSP.

  2. The algorithm and its theoretical guarantee are insufficiently specified. Algorithm 1 leaves the policy update and speculative acceptance/rejection procedures largely undefined. Although the abstract claims convergence to the constrained model distribution, the paper provides neither a proof nor a precise explanation of why the cited GAD result applies to the proposed combination. In particular, forcing structural and calculation tokens to probability one requires clarifying whether the target is the original LLM conditioned on feasibility or a modified decision-level distribution.

Questions for authors
  1. What exactly counts toward the 60-sample budget? Can you provide quality-versus-runtime comparisons and the measurements supporting the 156× speedup?
  2. Can you specify the complete policy-update and speculative-sampling equations, define the target distribution, and justify the convergence claim?
  3. Can you reconcile the tables? Table 1’s JSSP gaps for CHSS with policy adaptation are all at most 0.49%, while Table 4 reports an aggregate of 0.534%. Also, Table 2’s “CHSS” row reproduces the TSP results labeled “CHSS with Policy Adaptation” in Table 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.