acceptodds
Under review as a conference paper at ICLR 2027

Learning to Solve Combinatorial Optimization Problems Turns LLMs into Multi-Paradigm Optimization Models

Abstract

Large language models (LLMs) are increasingly used for optimization through distinct paradigms, including optimization modeling, heuristic discovery, and direct text reasoning. However, these paradigms are typically developed and post-trained in isolation, leaving open whether capabilities learned under one paradigm can transfer to fundamentally different ways of problem-solving. We study this question through *cross-paradigm transfer*. We introduce *Reasoning-to-Code Optimization (R2CO)*, a source post-training setting where an LLM reasons about the structure of a combinatorial optimization problem, derives a solution strategy, and implements it as a self-contained executable program. To strengthen strategy-level learning, we further develop reflective reinforcement learning, which uses previously evaluated reasoning trajectories and verifier-derived diagnostic feedback to refine solution strategies. Despite being trained exclusively under R2CO, the resulting model consistently transfers to optimization modeling, heuristic discovery, and direct text reasoning tasks. Diagnostic evaluations further reveal improvements in constraint reasoning, planning, procedural reasoning, and multi-step mathematical reasoning. In contrast, alternative solver-grounded optimization post-training yields weaker transfer. These results suggest that cross-paradigm generalization is not an automatic consequence of optimization post-training, but depends on whether the training setting strengthens reusable reasoning capabilities that transcend a particular solution representation or interface, offering a new perspective on how LLMs can be trained for broader optimization competence.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language models, Combinatorial Optimization, Reinforcement Learning, Generalization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Ub4JOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the cross-paradigm generalization capabilities of large language models on combinatorial optimization tasks. The authors introduce Reasoning-to-Code Optimization (R2CO), a training setting that requires the model to first design a solution strategy and then implement it as an executable Python program. Building on this, the authors propose Reflective RL, which uses historical successful or failed reasoning trajectories and verifier feedback to generate new rollouts. Through context relabeling and GRPO, the model is trained to generate effective solution strategies without relying on historical feedback.

The experiments primarily use 43 combinatorial optimization task families from NLCO for training and evaluate the model on optimization modeling, heuristic discovery, direct text reasoning, and additional reasoning benchmarks. The results show that R2CO training provides cross-paradigm generalization benefits, while Reflective RL further improves performance on these tasks.

Critical strengths
  1. This paper presents a training approach for combinatorial optimization that leverages historical reasoning experiences and verifier feedback to improve the model's reasoning. The experiments demonstrate that this approach not only improves performance on the source tasks but also transfers these gains to different optimization paradigms, offering meaningful research value.

  2. The paper evaluates cross-paradigm transfer across multiple target benchmarks and evaluation frameworks, with comparisons against R2CO-SFT, Generic Code-RL, and R2CO-RL. The authors further investigate the sources of performance improvements through reasoning–code cross-evaluation, reflection mode ablations, and experiments with different base models. These experiments provide substantial support for the paper's main observations.

Critical weaknesses
  1. Limited methodological novelty and insufficient differentiation from existing reflection-based training methods.

Although the method achieves performance improvements, its unique algorithmic contribution remains unclear compared with existing approaches such as Strategy-Guided Exploration (SGE), feedback-guided training, and self-distillation. A direct comparison with closely related methods such as SGE under matched training budgets would strengthen the paper.

  1. Insufficient explanation of the underlying cross-paradigm generalization phenomenon.

Although the authors provide training dynamics analysis and reasoning–code cross-evaluation, a systematic investigation of how reasoning strategies evolve during training is still lacking. For example, does the model progressively learn new perspectives on problem analysis, algorithm selection, or search strategies?

Furthermore, the authors emphasize that reflecting only on reasoning rather than referring to previous code facilitates the learning of transferable strategies, but a direct ablation study is missing to validate the necessity of this design.

  1. Reliance on a single source training dataset limits the generality of the conclusions.

The proposed training approach has potentially broad applications. Although the authors evaluate the model on multiple external benchmarks, the source post-training data comes exclusively from NLCO. It remains unclear whether similar cross-paradigm transfer benefits would emerge when training on other combinatorial optimization datasets. Additional training experiments using alternative source datasets would help validate the generality of the findings.

Questions for authors

Q1. What is the core algorithmic novelty of Reflective RL compared with existing feedback-guided exploration and self-distillation methods? Could the authors provide direct comparisons with methods such as SGE?

Q2. Can the cross-paradigm transfer findings of R2CO generalize to other source training datasets?

Q3. Could the authors further analyze how the model's reasoning strategies evolve during training and investigate how these changes relate to cross-paradigm transfer gains?

9 comments
AuthorsOpenReview ↗

Reply to Reviewer Ub4J (1/3)

Dear Reviewer Ub4J,

Thank you for recognizing the value of cross-paradigm transfer and the evidence from our controlled comparisons. We address your concerns by clarifying the contribution relative to prior methods and examining strategy evolution, access to previous code, and transfer from a second training source.

[W1, Q1] Methodological contribution and comparison with SGE

1. Contribution of R2CO and Reflective RL

Thank you for asking us to clarify the novelty. Rather than proposing a completely new algorithm for feedback-guided exploration, we study a novel research question: whether learning to develop optimization algorithms can improve an LLM across different solving paradigms, and reflection-based learning is our way to enhance performance. Specifically, we introduce R2CO to investigate this new question. We find that training in this source setting improves optimization modeling, heuristic discovery, and direct text reasoning, without further learning on these target tasks.

To further strengthen this transfer, we introduce Reflective RL, motivated by the limitation that outcome rewards evaluate solutions but provide little guidance on how to improve the underlying reasoning. Our method builds on the general idea of strategy reflection in SGE [1], as acknowledged in Section 3.3, but introduces several designs tailored to R2CO. First, we separate reflection-guided reasoning from program generation: previous experiences guide the refinement of solution strategies, while fresh code is generated without the reflection context. Second, context relabeling allows these refined strategies to be learned under the original task prompt. Third, optimization-specific feedback, including constraint violations and optimality gaps, enables reflection on feasible but suboptimal solutions, beyond execution failures. These designs aim to improve the learning and reliable application of optimization strategies rather than simply increasing strategy diversity.

Empirically, Reflective RL improves all three transfer paradigms over standard R2CO-RL. For example, optimization modeling accuracy increases from 73.66% to 76.83%, while relative improvements in heuristic discovery rise from 2.07% to 4.99% on EoH and 3.24% to 4.22% on ReEvo (Tables 2–3 and Appendix E.3).

Regarding self-distillation, SDPO [2] and SDFT [3] train a policy to match self-teacher predictions conditioned on feedback or expert demonstrations. Reflective RL instead uses previous reasoning and feedback to generate a new attempt, then updates the policy using its verified reward. The update uses the original problem prompt, so the trained model does not need reflection context at inference time.

2. Direct comparison with SGE under matched training settings

Following your suggestion, we added a direct comparison with SGE [1]. We adapted SGE to single-turn optimization by treating the reasoning block as the strategy and the generated program as the action, with sampling temperatures of 1.2 and 0.7, respectively. For this adaptation, we used the same R2CO reward function and negative and positive reflection probabilities, (p−,p+)=(0.15,0.10)(p_{-}, p_{+})=(0.15,0.10), as Reflective RL. We trained SGE for 120 optimization steps on the same NLCO training data as Reflective RL. The results are summarized below.

ConfigurationR2CO AFR / Acc. (%)Modeling Acc. (%)EoH RI (%)ReEvo RI (%)Direct Text AFR / Acc. (%)
SGE66.67 / 51.6374.062.983.1169.61 / 37.13
Reflective RL69.3 / 54.576.834.994.2271.2 / 37.8

Under these matched settings, Reflective RL achieves higher R2CO feasibility and accuracy and stronger transfer across all three paradigms, showing the effectiveness of our implementation.

AuthorsOpenReview ↗

Reply to Reviewer Ub4J (2/3)

[W2.1, Q3] Strategy evolution during training and its relation to transfer

Thank you for suggesting this analysis. We analyzed responses to the same held-out instances across five training checkpoints to examine how the model's reasoning strategies evolve and how these relate to cross-paradigm gains. We find that the number of successful strategies initially increases and then declines, while successful responses become more frequent. Transfer can continue to improve even as sampled strategy coverage narrows.

1. How do reasoning strategies evolve during training?

To examine how reasoning strategies evolve during training, we investigate whether the model becomes better at problem analysis, such as correctly identifying the objective and all key constraints, and how its solution strategies change across checkpoints.

We evaluate the base model (step 0) and the Reflective RL checkpoints at steps 30, 60, 90, and 120, sampling 32 responses per instance on the same 129 held-out NLCO instances. For each instance, we consider the responses sampled from all five checkpoints. Following the strategy counting method proposed by Lee et al. [4], we use an LLM (i.e., DeepSeek-V4.1-Flash) to group these responses by solution strategy based on their reasoning traces and generated programs. Responses using the same strategy are assigned to the same group, regardless of which checkpoint produced them. We then count the distinct strategies represented in the 32 responses sampled at each checkpoint. During the initial grouping step, we also ask the judge to check whether each reasoning trace correctly identifies the objective and all key constraints. The full evaluation procedure is provided in Appendix E.14.

A response is successful if its generated program returns a feasible solution with a relative optimality gap of at most 10−410^{-4}. For each checkpoint, let KiK_i denote the number of distinct strategies in the 32 responses sampled for instance ii, and KisuccK_i^{\mathrm{succ}} the number of these strategies with at least one successful response. We report Strategy Count (SC) and Successful Strategy Count (SSC) as

\qquad \mathrm{SSC}=\frac{1}{129}\sum_{i=1}^{129}K_i^{\mathrm{succ}}.$$ The successful-response count is also averaged over the 129 instances. The correct problem-analysis rate is the percentage of responses whose reasoning correctly identifies the objective and all key constraints. | Checkpoint | Correct problem analysis (%) | SC | SSC | Successful responses (of 32) | | :--- | ---: | ---: | ---: | ---: | | Step 0 | 92.93 | 5.496 | 1.054 | 5.364 | | Step 30 | 92.20 | 5.636 | 1.442 | 13.442 | | Step 60 | 92.51 | 5.574 | 1.356 | 13.791 | | Step 90 | 92.85 | 5.178 | 1.288 | 15.411 | | Step 120 | 92.37 | 4.651 | 1.240 | 15.938 | The table shows that the base model already correctly identifies the objective and all key constraints in most responses, and this rate changes little during training. SSC initially increases, but after step 30 both SC and SSC decline, while successful responses continue to increase. **These results suggest that training improves the model’s ability to produce successful solutions beyond correctly identifying the problem requirements. During later training, successful responses become more frequent, while the number of distinct strategies observed under the same sampling budget decreases.** Thus, higher solution accuracy does not necessarily imply broader sampled strategy coverage. This is consistent with prior findings that RL can improve solution performance while concentrating generation on fewer solution strategies [4–6]. We have added this analysis to Appendix E.14. **2. How do these changes relate to cross-paradigm transfer gains?** We compare the strategy statistics above with transfer performance at the corresponding checkpoints (Appendix E.2, Figure 3). From initialization to step 120, performance improves across all three transfer paradigms: optimization modeling, heuristic discovery, and direct text reasoning. These gains accompany more frequent successful responses on the held-out NLCO instances evaluated under R2CO, without a sustained increase in the number of successful strategies. From step 30 to step 120, both the total number of sampled strategies and the number of successful strategies decrease, while successful responses continue to increase. Over the same period, transfer performance improves overall across all three paradigms. These results show that transfer can continue to improve as successful R2CO responses become more frequent, even as sampled strategy coverage narrows.
AuthorsOpenReview ↗

Reply to Reviewer Ub4J (3/3)

[W2.2] Effect of access to previous code during reflection

We omit previous code from the reflection prompt to encourage the model to reconsider the solution approach instead of editing its earlier program. To test whether this choice contributes to the transfer gains, we compare Reflective RL with a matched variant that also receives the previous program during reflection.

Specifically, both reflection configurations use the same NLCO training split, verifier feedback and reward, and a 120-update schedule with 32 instances per update and eight rollouts per instance. The variant with previous code receives the previous program during both positive and negative reflection. During reflection, the prompt asks the model to inspect the implementation when revising its strategy. The results are summarized below.

ConfigurationR2CO AFR / Acc. (%)Modeling Acc. (%)EoH RI (%)ReEvo RI (%)Direct Text AFR / Acc. (%)
Qwen3-4B-Instruct (base)25.4 / 19.260.090.000.0065.9 / 34.8
R2CO-RL64.4 / 51.473.662.073.2469.2 / 36.1
Reflective RL with previous code66.5 / 52.575.072.392.6569.2 / 37.0
Reflective RL69.3 / 54.576.834.994.2271.2 / 37.8

Compared to incorporating previous code, our setting achieves higher optimization-modeling accuracy and direct-text accuracy. It also yields stronger heuristic discovery results in both EoH (4.99% vs. 2.39% RI) and ReEvo (4.22% vs. 2.65% RI). These results support our design choice across all three evaluated transfer paradigms.

The variant with previous code improves over the variant without reflection in modeling, EoH, and direct text accuracy, although its ReEvo RI is lower (2.65% vs. 3.24%). Thus, reflection with previous code remains beneficial on several target evaluations, while Reflective RL without previous code yields stronger results throughout the reported transfer evaluations. The ablation details and results have now been added to Appendix E.15 (Table 26) of the revised manuscript.

[W3, Q2] Transfer from a second source dataset

Thank you for suggesting this experiment. We have evaluated R2CO training on another dataset (i.e., GraphArena), and we found that the transfer gains also appear when we train on another dataset, but the performance gain is smaller than that obtained by training on NLCO.

Specifically, we initialized the same Qwen3-4B-Instruct base model and trained it with Reflective RL for 120 updates on 1,920 GraphArena instances from six tasks at two difficulty levels. We then evaluated all three transfer paradigms, with direct text reasoning tested on held-out NLCO instances, and the results are summarized below.

Training sourceModeling Acc. (%)EoH RI (%)ReEvo RI (%)Direct Text AFR / Acc. (%)
Qwen3-4B-Instruct (base)60.090.000.0065.9 / 34.8
GraphArena71.201.761.0969.92 / 36.74
NLCO76.834.994.2271.2 / 37.8

We still see that R2CO training works for GraphArena, showing the generalizability of our method. However, the gains with GraphArena are smaller than those with NLCO. NLCO covers 43 tasks, including routing, scheduling, packing, assignment, and graph optimization, whereas the GraphArena training set used here contains six graph tasks. NLCO's natural-language problem descriptions therefore expose the model to a broader range of problem structures, objectives, and constraints. This broader coverage may help explain the stronger transfer results and is why we chose NLCO as our main training source. The experimental setup and results are provided in Appendix E.16, Table 27, of the revised manuscript.

References

[1] Szot, A., Kirchhof, M., Attia, O., and Toshev, A. 2026. Expanding LLM Agent Boundaries with Strategy-Guided Exploration. arXiv preprint arXiv:2603.02045.

[2] Hübotter, J., et al. 2026. Reinforcement Learning via Self-Distillation. Proceedings of the 43rd International Conference on Machine Learning, PMLR 306, pp. 48677–48721.

[3] Shenfeld, I., Damani, M., Hübotter, J., and Agrawal, P. 2026. Self-Distillation Enables Continual Learning. arXiv preprint arXiv:2601.19897.

[4] Lee, S., Kim, M., Kim, J., Kim, D., Rhee, S., and Jung, K. 2026. Are We Measuring Strategy or Phrasing? The Gap Between Surface- and Approach-Level Diversity in LLM Math Reasoning. Proceedings of EMNLP 2026, pp. 52966–52996.

[5] Cheng, Z., Huang, Y., Zhu, H., and Sojoudi, S. 2026. How RL Reshapes LLM Reasoning: Transferability, Coverage, and Scaling Laws. arXiv preprint arXiv:2610.04158.

[6] Massoudi, S., Apaza, G., Habibi, M., and Fuge, M. 2026. Beyond Inference-Time Search: Reinforcement Learning Synthesizes Reusable Solvers. arXiv preprint arXiv:2605.18374.

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

This paper investigates the cross-paradigm transfer capabilities of large language models (LLMs) in combinatorial optimization (COP) tasks. Previous LLM optimization methods have mostly been limited to a single paradigm (such as optimization modeling, heuristic discovery, or direct text reasoning). It introduces Reasoning-to-Code Optimization (R2CO), a source post-training setting where the model first analyzes the problem structure and derives a strategy, and then implements it as a self-contained executable program. It develops reflective reinforcement learning (RL), which utilizes previously evaluated reasoning trajectories and verifier-derived diagnostic feedback to focus on strategy-level exploration and revision. Using Qwen3-4B-Instruct as the base model, R2CO training is conducted combined with the NLCO benchmark dataset, and extensive evaluations and ablation studies are performed across multiple optimization modeling benchmarks, heuristic discovery frameworks (EoH, ReEvo), direct text reasoning tasks, and independent atomic reasoning benchmarks.

Critical strengths
  1. The paper systematically explores the cross-paradigm transfer capability from one problem-solving paradigm (R2CO) to other mainstream optimization paradigms (modeling, heuristics, direct reasoning). The experimental coverage is extremely broad (covering multiple benchmarks and multiple base model families), and control experiments demonstrate the difference between "code-training generalization" and "pure-strategy reflective reinforcement learning".
  2. This method cleverly restricts the "reflection" process strictly to the reasoning trace level rather than on already generated code patches. By constructing optimal and non-optimal reflection buffers and updating via group relative policy optimization (GRPO), it both strengthens reusable underlying problem-solving capabilities and avoids overfitting to specific code interfaces.
Critical weaknesses
  1. Strong dependency of source tasks on medium-scale instances and scalability limitations: Although the R2CO model performs well in cross-paradigm transfer, its source training setting relies on "medium-scale" instances in the NLCO dataset that are equipped with accurate/high-quality reference optimal solutions o^*. For larger-scale real-world NP-hard problems where reference optimal solutions are not easily obtainable or difficult to solve, the training closed-loop of this method (relying on reference gaps to compute rewards) may face scalability bottlenecks.
  2. Trade-off conflicts between hyperparameters and reward design on transfer performance in ablation experiments: As shown in Appendix E.7, changing the reward tolerance parameter \tau introduces clear trade-offs between the "average feasibility rate (AFR)" and "solution accuracy (Acc.)" of R2CO instances as well as downstream cross-paradigm transfer performance, indicating that the system is highly sensitive to reward shaping.
Questions for authors
  1. Regarding the theoretical or mechanistic explanation of cross-paradigm transfer: The paper demonstrates through atomic reasoning capabilities that R2CO enhances general reasoning skills, but is there more direct evidence or analysis showing why "executable code generation (R2CO)" can bring stronger heuristic discovery transfer capabilities compared to direct "solver-grounded modeling"?
4 comments
AuthorsOpenReview ↗

Reply to Reviewer cyPE (1/2)

Dear Reviewer cyPE ,

Thank you for recognizing the breadth of our evaluation and the value of the controlled comparisons. Your comments help us clarify the requirements for source training, the effect of reward tolerance, and the evidence behind our explanation of transfer to heuristic discovery.

[W1] Source-training scale and reference solutions

Thank you for raising this concern. We would like to clarify that using moderate-scale training instances is a practical choice given our model capacity and compute budget. Larger instances produce longer prompts and are harder for small models to interpret and reason about. With the compute available in this study, we train models up to 8B on two H200 GPUs (Appendices B.2 and E.9) and use instances that are manageable for these models. However, R2CO does not impose a fixed instance size: the same training method could be applied to larger models and larger instances, provided the models can process the inputs and computational resources are available.

Regarding reference solutions, we agree that obtaining high-quality references becomes more challenging as problem size and complexity increase. Nevertheless, existing CO solvers demonstrate considerable potential for scaling beyond the instances considered in this study. For example, Helsgaun [1] evaluated LKH on TSP instances with up to 10 million cities, including a million-city instance for which the best tour was within 0.019% of a known lower bound. Concorde has also certified an optimal solution for an 85,900-city TSP [2]. For CVRP, HGS [3], which is already used in NLCO, can effectively handle instances with up to 1,000 customers. Importantly, our reward uses a reference objective value rather than requiring a proof of global optimality. As discussed in Appendix B.1, NLCO already uses high-quality heuristic solutions as references for some problems. This provides a practical basis for extending reference-based training to larger instances.

We nevertheless recognize that these results do not eliminate the scalability challenge, particularly for more complex or less structured NP-hard problems, where obtaining reliable references may require substantial computation. Approximate references may also introduce noise into reward estimation. Addressing these limitations through more efficient reference generation and quality-aware reward estimation is an important direction for future work. Similar challenges also arise in existing solver-supervised LLM approaches to CO, such as Jiang et al. [4].

Training on moderate-scale instances already benefits heuristics for larger downstream problems. In Appendix E.4, we select each heuristic at its discovery size and run the same code unchanged on larger held-out instances. Bin-packing heuristics discovered on 500-item instances are tested on 1,000-item instances, and orienteering heuristics discovered on 50-node instances are tested on 200-node instances. At the largest test size for each of the four ReEvo tasks, heuristics discovered with Reflective RL outperform those discovered with Qwen3-4B-Instruct by 0.66% to 9.76% (Figure 4). These results show that R2CO training can also benefit generalization towards larger-scale problems.

[W2] Sensitivity to the reward tolerance

Thank you for drawing attention to this trade-off. The reward tolerance affects the balance between feasibility and solution quality, while improvements over the base model remain present at all three tested values. In Table 17(b) of Appendix E.7, τ = 0.1, 0.3, and 1.0 all improve optimization modeling, both heuristic discovery evaluations, and direct text accuracy over Qwen3-4B-Instruct. Thus, the observed cross-paradigm gains are not confined to a single tested tolerance value, although their magnitude varies.

The parameter τ controls how much reward a feasible solution receives at a given gap from the reference. A larger τ gives more credit to feasible solutions with positive gaps, while the evaluation accuracy criterion stays fixed. Comparing τ = 0.1 with τ = 1.0, in-domain AFR rises from 69.3% to 74.7%, but Acc. decreases from 54.5% to 53.1%. Modeling and heuristic discovery also perform worse at τ = 1.0. This illustrates why higher feasibility alone need not yield stronger transfer.

Our main experiments used τ = 0.1 before this ablation was conducted. Among the three tested values, it gives the highest in-domain accuracy and the strongest modeling and heuristic discovery results. It is not best on every metric: τ = 1.0 gives slightly higher direct text accuracy (37.9% vs. 37.8%). We will make this trade-off explicit: the transfer gains over the base model persist across the tested tolerance values, but the reward setting affects which capabilities improve most.

AuthorsOpenReview ↗

Reply to Reviewer cyPE (2/2)

[Q1] Why does R2CO transfer more strongly to heuristic discovery?

Thank you for this question. We believe the difference primarily lies in which parts of the optimization process the model must learn to perform.

In R2CO, the model must identify the problem structure, select a suitable solution algorithm, and implement the search procedure itself, using only the Python standard library and NumPy (Section 3.2). This requires reasoning about how to construct and improve solutions, enforce constraints, and balance solution quality against computational cost. In contrast, solver-grounded modeling focuses on constructing a mathematical formulation, while the external solver handles the actual search. Heuristic discovery, particularly EoH and ReEvo, requires the model to design executable heuristic components that guide solution construction and search. R2CO therefore shares more of the algorithm-design and search-related reasoning required by heuristic discovery, even though the generated programs serve different purposes.

The comparison in Appendix E.3 (Table 13) provides empirical support for this explanation. With the same base model, training instances, reward, and rollout schedule, and reflection disabled in both settings, R2CO achieves relative improvements of +2.07% on EoH and +3.24% on ReEvo, compared with −0.74% and −0.21% for solver-grounded modeling. Interestingly, solver-grounded modeling achieves slightly higher optimization modeling accuracy (74.61% vs. 73.66%), suggesting that better formulation performance does not necessarily translate into better heuristic design. Moreover, Generic Code-RL shows inconsistent improvements in heuristic discovery (Table 3), indicating that the benefit is not simply due to code-oriented post-training.

Together, these results support a plausible mechanism: requiring the model to design and implement optimization procedures provides training experience more closely aligned with heuristic discovery than delegating the search to an external solver. While this does not establish a causal explanation for every aspect of transfer, it helps explain the observed difference between the two source training settings.

References

[1] Helsgaun, K. (2009). General k-opt Submoves for the Lin–Kernighan TSP Heuristic. Mathematical Programming Computation, 1, 119–163.

[2] Applegate et al. (2009). Certification of an Optimal TSP Tour Through 85,900 Cities. Operations Research Letters, 37(1), 11–15.

[3] Vidal, T. (2022). Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood. Computers & Operations Research, 140, 105643.

[4] Jiang, X., Wu, Y., Li, M., Cao, Z., and Zhang, Y. (2025). Large Language Models as End-to-end Combinatorial Optimization Solvers. Proceedings of the 39th Annual Conference on Neural Information Processing Systems.

AuthorsOpenReview ↗

Follow-up on Our Responses

Dear Reviewer cyPE,

We would like to thank you again for your positive evaluation and thoughtful feedback.

With two days remaining in the discussion period, we want to ensure that all your questions and concerns have been adequately addressed. We have provided further clarifications and additional experimental results regarding scalability, reward tolerance, and cross-paradigm transfer.

We sincerely hope our responses have addressed your concerns. Please let us know if you have any further questions or points for clarification.

Thank you again for your time and consideration.

Sincerely,

Authors of Submission 23970

AuthorsOpenReview ↗

Your Feedback Would Be Appreciated

Dear Reviewer cyPE,

As the discussion period is set to close in one day, we want to ensure that your questions and concerns have been addressed. We have carefully reviewed your comments and provided detailed responses. We sincerely hope our clarifications meet your expectations.

If you have any further questions, we will do our best to answer them. Thank you again for your valuable feedback, and we look forward to hearing from you.

Sincerely,

Authors of Submission 23970

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

The paper trains language models to solve combinatorial optimization problems by generating solution plans and executable programs. During training, reflection uses earlier plans and evaluation feedback to improve subsequent attempts. The trained models also improve at formulating solver inputs, designing search heuristics, and producing solutions directly.

Critical strengths

One training procedure improves several ways of solving optimization problems, without requiring reflection when the trained model is used.

Controlled training comparisons, repeated runs, and evaluations across models support the reported gains. Experiments that exchange solution plans between models further demonstrate the contribution of improved intermediate reasoning.

Critical weaknesses

Better performance does not establish improved exploration. The paper argues that reflection helps discover alternative solution strategies. Higher scores could instead result from selecting familiar successful strategies more consistently. The experiments do not distinguish these explanations. This leaves the central exploration claim unresolved: the method improves solution quality, but its effect on the range of strategies discovered is unknown.

The benefit of withholding previous code is untested. During reflection, the model receives its earlier written plan but not the program it previously generated. The paper argues that this encourages learning reusable solution approaches rather than repairing individual programs. The evaluation compares the method with training without reflection, but not with reflection that also includes previous code. Consequently, it does not establish whether withholding code contributes to the transfer gains.

Questions for authors

At a fixed sampling budget, does reflection increase the number of distinct successful solution approaches? How does solution quality change as the sampling budget increases?

With training data, feedback, and computational budget matched, how does the method compare with a variant that allows the model to inspect its previous code?

8 comments
AuthorsOpenReview ↗

Reply to Reviewer sQqV (1/2)

Dear Reviewer sQqV ,

Thank you for recognizing the cross-paradigm transfer gains and the contribution of intermediate reasoning. We appreciate your suggestions and have added strategy analyses and a previous-code ablation to address your two concerns.

[W1, Q1] Strategy coverage and solution quality under matched sampling budgets — Part 1 of 2

Thank you for raising this important distinction. To better understand how reflection affects strategy exploration and selection, we conducted additional experiments comparing Reflective RL with R2CO-RL under the same sampling budget. We sampled 32 responses per model on each of 129 held-out NLCO instances, covering all 43 COP families and three difficulty levels. The results reveal that reflection encourages more consistent use of effective strategies, while still producing successful alternatives not observed from R2CO-RL on some instances.

1. Does reflection produce a wider range of strategies at the same sampling budget?

Reflective RL generates fewer distinct strategies on average, but it also produces successful alternatives absent from R2CO-RL's samples on some instances.

To examine whether reflection broadens the range of solution strategies, we compare Reflective RL and R2CO-RL using two metrics: Strategy Count (SC) and Successful Strategy Count (SSC). We sample 32 responses from each model on the same 129 held-out NLCO instances.

Following the strategy analysis of Lee et al. [1], we use DeepSeek-V4.1-Flash to distinguish responses by how they solve the problem. For each instance, responses from both models are assigned common strategy labels based on their reasoning traces and generated programs.

For each model, let KiK_i denote the number of distinct strategies sampled on instance ii, and KisuccK_i^{\mathrm{succ}} the number of these strategies with at least one successful response. A response is successful if its generated program returns a feasible solution with a relative optimality gap of at most 10−410^{-4}. We average these counts over the 129 instances:

\qquad \mathrm{SSC}=\frac{1}{129}\sum_{i=1}^{129}K_i^{\mathrm{succ}}.$$ Further details are provided in Appendix E.13. | Model | SC | SSC | AFR (%) | Acc. (%) | | :--- | ---: | ---: | ---: | ---: | | R2CO-RL | 5.465 | 1.426 | 63.57 | 48.74 | | Reflective RL | 4.651 | 1.240 | 66.28 | 49.81 | Reflective RL has lower SC and SSC than R2CO-RL, while achieving higher feasibility and accuracy. Nevertheless, on 11.6% of the evaluated instances, it produces at least one successful strategy absent from all 32 R2CO-RL responses, including unsuccessful ones. For example, on the k-minimum-spanning-tree instance KMST_L_004, both models use a strategy that enumerates vertex subsets and constructs a minimum spanning tree for each subset. Reflective RL samples this shared strategy more frequently: it appears in 21 of 32 responses, with 14 successes, compared with 7 of 32 responses and 5 successes for R2CO-RL. Reflective RL also produces a successful alternative that filters high-weight edges before searching the reduced graph; this strategy does not appear in the R2CO-RL samples. These findings indicate that reflection does not broadly increase strategy coverage, but neither does it simply reproduce the same successful strategies. **2. Does reflection help the model choose effective strategies more often?** To examine the reviewer's alternative explanation, we focused on strategies that both models can generate. Using the first 16 responses from each model, we identified shared strategies with at least one successful response across both models and selected the one with the most successful responses in total. We then measured its frequency in the remaining 16 responses, separating strategy identification from frequency measurement. Across 89 eligible instances, Reflective RL generates the selected shared effective strategy in 76.12% of responses, compared with 69.17% for R2CO-RL (Appendix E.13). This supports the interpretation that reflection makes effective strategies more likely to be used, rather than simply increasing the number of different approaches. We continue our response to this question in Part 2 below.
AuthorsOpenReview ↗

Reply to Reviewer sQqV (2/2)

[W1, Q1] Strategy coverage and solution quality under matched sampling budgets — Part 2 of 2

This comment continues our response to [W1, Q1].

3. How does the chance of finding an accurate solution vary with the number of samples?

We evaluated Pass@K at K = 1, 2, 4, 8, 16, and 32 using the 32 sampled responses for each of the 129 held-out instances. For Reflective RL, Pass@K rises from 49.81% at K = 1 to 72.09% at K = 32 (Appendix E.13, Figure 5). At K = 32, 93 of 129 instances have at least one accurate response. This shows that additional samples uncover accurate solutions on more instances, although the gains become smaller at larger budgets.

4. Interpretation and manuscript revisions

Together, these findings suggest that Reflective RL shifts strategy generation toward more consistent use of effective approaches, while retaining the ability to produce successful alternatives. This is consistent with our method design, where positive reflection draws on successful reasoning and negative reflection uses diagnostic feedback to revise unsuccessful attempts.

We have revised the Introduction and Section 3.3 to clarify the role of reflection in guiding strategy refinement and reuse, rather than claiming a general increase in strategy diversity. We have also expanded Section 4.5 with the reasoning and strategy analyses. Appendix E.13 provides the detailed strategy coverage and selection-frequency analyses, along with the Pass@K results. These additions provide a more precise characterization of how reflection improves solution quality and complement our cross-paradigm generalization results.

[W2, Q2] Transfer with access to previous code during reflection

Thank you for suggesting this comparison. We omitted previous code to encourage the model to reconsider the solution strategy rather than edit its earlier code implementation. Our aim is to strengthen reasoning skills, such as constraint reasoning and planning, that may be useful across optimization paradigms (Section 3.3). However, we acknowledge that the benefit of withholding previous code can be more directly evaluated through an ablation study. Following your suggestion, we compared Reflective RL with a variant that also receives previous code during reflection.

Specifically, both reflection configurations use the same NLCO training split, verifier feedback and reward, and a 120-update schedule with 32 instances per update and eight rollouts per instance. The variant with previous code receives the previous program during both positive and negative reflection. During reflection, the prompt asks the model to inspect the implementation when revising its strategy. The results are summarized below.

ConfigurationR2CO AFR / Acc. (%)Modeling Acc. (%)EoH RI (%)ReEvo RI (%)Direct Text AFR / Acc. (%)
Qwen3-4B-Instruct (base)25.4 / 19.260.090.000.0065.9 / 34.8
R2CO-RL64.4 / 51.473.662.073.2469.2 / 36.1
Reflective RL with previous code66.5 / 52.575.072.392.6569.2 / 37.0
Reflective RL69.3 / 54.576.834.994.2271.2 / 37.8

Compared to incorporating previous code, our setting achieves higher optimization-modeling accuracy (76.83% vs. 75.07%) and direct-text accuracy (37.8% vs. 37.0%). It also yields stronger heuristic discovery results in both EoH (4.99% vs. 2.39% RI) and ReEvo (4.22% vs. 2.65% RI). These results support our design choice across all three evaluated transfer paradigms.

The variant with previous code improves over the variant without reflection in modeling, EoH, and direct text accuracy, although its ReEvo RI is lower (2.65% vs. 3.24%). Thus, reflection with previous code remains beneficial on several target evaluations, while Reflective RL without previous code yields stronger results throughout the reported transfer evaluations. The ablation details and results have now been added to Appendix E.15 (Table 26) of the revised manuscript.

References

[1] Lee, S., Kim, M., Kim, J., Kim, D., Rhee, S., and Jung, K. 2026. Are We Measuring Strategy or Phrasing? The Gap Between Surface- and Approach-Level Diversity in LLM Math Reasoning. Proceedings of EMNLP 2026, pp. 52966–52996.

AuthorsOpenReview ↗

Follow-up on Our Responses

Dear Reviewer sQqV,

With two days remaining in the discussion period, we would like to kindly follow up on our responses to your questions and concerns.

We have provided additional experiments and analyses on strategy coverage, sampling budget, and the effect of access to previous code. We sincerely hope that our clarifications have addressed your concerns.

Please let us know if you have any further questions or points that require clarification. We will do our best to address them.

Thank you again for your valuable feedback and time.

Sincerely,

Authors of Submission 23970

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We sincerely appreciate the reviewers for acknowledging the value of our cross-paradigm transfer findings and the strong experimental evidence supporting them. We also thank the reviewers for their thoughtful questions. Overall, the reviewers' main concerns focus on understanding why and how cross-paradigm transfer occurs, clarifying the differences from existing methods, and examining the limitations and generalizability of our approach. We have carefully addressed these concerns through additional experiments, analyses, and clarifications in the revised manuscript.

Specifically, during the discussion, we addressed the reviewers' main concerns through additional experiments and analyses:

  1. Transfer from a second training dataset (Ub4J). To test whether the transfer gains extend beyond NLCO, we trained on GraphArena and observed that the R2CO transfer gains also appear, but the performance gain is smaller than that obtained by training on NLCO.
  2. Ablation on previous code during reflection (sQqV, Ub4J). We trained a model variant that included the previous code during reflection. We found that our original design without previous code achieved stronger transfer across all three target paradigms.
  3. Comparison with Strategy-Guided Exploration (Ub4J). We highlighted the difference between Reflective RL and SGE. We also compared the performance between them using the same training configurations, which shows our method still achieved stronger transfer across all three target paradigms.
  4. Strategy selection and evolution (sQqV, Ub4J). We compared Reflective RL with R2CO-RL trained without reflection at the same sampling budget. We found that Reflective RL sampled fewer distinct strategies on average but used effective strategies more consistently. We also tracked strategy use across training checkpoints. We observed that at later checkpoints, the model used fewer distinct strategies but produced successful solutions more often. Its performance across the three transfer paradigms also improved overall.

These additional results strengthen our main findings, provide direct evidence for key design choices, and clarify the mechanisms of our approach.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.