$\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization

We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal will properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Q1: How does the natural language description of the CO problem look like?

A1: Thank you for your question. In our paper, we do not use natural language to describe specific combinatorial optimization problems. Instead, we represent CO problems using graph structures to capture their intrinsic topological properties effectively. As detailed in Section 4.1 of the manuscript, we construct a bipartite graph where:

• Nodes represent the variables of the CO problem.
• Edges represent the constraints between these variables.

However, natural language plays a key role in our framework during the code generation task. We use natural language within our prompts to describe the general form of the inputted CO problem, rather than specific instances. For example, in the prompt for MILP problems, we include a definition such as:

"A Mixed Integer Linear Programming (MILP) problem is defined as: $\min_{x \in \mathbb{R}^n} \boldsymbol{w}^{\top} \boldsymbol{x}$, subject to $\boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}$, $\boldsymbol{l} \leq \boldsymbol{x} \leq \boldsymbol{u}$, and $x_j \in \mathbb{Z}$ for all $j \in \mathbb{I}$, where $\boldsymbol{w}$ is the objective coefficient vector, $\boldsymbol{A}$ is the constraint matrix, $\boldsymbol{b}$ is the right-hand side vector, $\boldsymbol{l}$ and $\boldsymbol{u}$ are lower and upper bounds, and $\mathbb{I}$ specifies integer-constrained variables."

This general description, provided in natural language, guides the LLM in generating solver-specific code tailored to the problem class, conditioned on the structural embeddings extracted by the GNN. The prompt thus bridges the structural representation and the code synthesis process, ensuring that the generated algorithms respect both the problem’s topology and solver syntax. For concrete examples of how we integrate natural language into our prompts, we kindly direct you to Appendix I: Prompt and Corresponding Responses in the paper. This appendix illustrates sample prompts, including general problem definitions like the one above, alongside the corresponding code snippets generated by our STRCMP framework. This approach ensures clarity in communicating the problem class to the LLM while relying on graph structures for specific problem representation. We hope this clarifies our methodology.

Q2: You train the GNN with classification loss, but is it justified that different problems subsume different structures? Some graph based CO problems can be similar, e.g. what if I want to model the maximum independent set and minimum vertex cover problems, they are complementary.

A2: Thank you for your insightful and intuitive question. We absolutely agree with your observation that different CO problems may exhibit structural similarities. To address this, we designed our STRCMP framework to account for potential structural overlaps across CO problems. Specifically, rather than training separate models for each problem class, we post-train our composite model—comprising the GNN and the LLM—using a mixed-class dataset that includes a diverse set of CO problems. This approach enables the model to learn generalized structural features that are applicable across various problem types, including those with similar or related structures.

To further justify this methodology and directly respond to your concern, we conducted an experiment comparing two training strategies. We trained a separate STRCMP model using only one class of dataset—here, we adopted the MIK dataset—and compared its performance with that of a model trained on a mixed dataset encompassing multiple CO problems, including MIK, Set Cover, and others. The experimental results are presented below:

Table 1: The Optimization Performance Comparison between Different Dataset Used Methods

Note that for the Primal-Dual Integral, a lower value indicates better performance.

These results highlight that training on a mixed-class dataset not only mitigates the risk of overfitting to a single problem’s structure but also enhances generalization and efficiency across structurally similar CO problems. By exposing the GNN to a variety of problem instances during post-training, the model captures shared topological patterns while still generating solver-specific code tailored to each problem’s nuances. This aligns with our theoretical analysis (Section 4.2 of the paper), which demonstrates that incorporating structural priors improves the performance upper bound of generative models for CO tasks.

Q3: Is the solving code generated by the LLM guaranteed to be executable without bugs or syntax error?

A3: We appreciate the reviewer’s question about the executability and correctness of LLM-generated code in our STRCMP framework. To ensure reliability:

1. Compilation Check:

   • Each code snippet is compiled with its CO solver (e.g., SCIP, EasySAT).
   • Snippets failing compilation are discarded with a low score.

2. Performance Evaluation:

   • Valid snippets are tested on benchmark CO instances (Section 5.1).
   • Metrics (Appendix E.1, E.2) assess performance; only high-scoring, error-free code is used.

This ensures all experimental code is executable, syntactically correct, and effective. See Appendices E.1 and E.2 for details. We welcome further feedback.

Q4: Could you explain more about the sup(P) in definition 1? It is not clear to me why it takes the form of that.

A4: Your question is insightful and highlights a point that deserves more detailed explanation. The formulation for $\sup(\mathcal{P})$, the upper bound of model performance, is designed to capture the theoretical maximum potential of a generative model for a specific downstream task (e.g., generated code snippets improving the solving accuracy/efficiency of CO problems) , rather than its average-case performance.

Let us break down the formula to explain its structure $\sup(\mathcal{P}_\mathcal{C})$:

1. The Inner Term: Maximum Performance for a Single Prior

The core of the definition lies in the term $\max_{\mathbf{w}}p(\mathbf{w}|\mathbf{c})\Phi(\mathbf{w})$. Let's analyze its components for a single, fixed prior $\mathbf{c}$:

• $\Phi(\mathbf{w})$ is the performance score w.r.t. downstream task of a generated output $\mathbf{w}$.
• $p(\mathbf{w}|\mathbf{c})$ is the probability that the model generates $\mathbf{w}$ given the prior $\mathbf{c}$.
• A standard evaluation would typically compute the expected performance, $E_{\mathbf{w}\sim p(\mathbf{w}|\mathbf{c})}[\Phi(\mathbf{w})] = \sum_{\mathbf{w}}p(\mathbf{w}|\mathbf{c})\Phi(\mathbf{w})$, which averages the performance over all possible outputs.

However, our goal is to define an upper bound. Therefore, instead of averaging, we seek the best possible outcome for the given prior $\mathbf{c}$. The term $p(\mathbf{w}|\mathbf{c})\Phi(\mathbf{w})$ can be viewed as the "probability-weighted performance" of a single output. The $\max_{\mathbf{w}}$ operator then identifies the single piece of generated content $\mathbf{w}$ that maximizes this value.

This captures the model's "peak capability" for a specific prior $\mathbf{c}$. It finds the most impactful single output the model could theoretically produce, considering both the intrinsic quality of the output ($\Phi(\mathbf{w})$) and the model's ability to generate it ($p(\mathbf{w}|\mathbf{c})$). An extremely high-quality output that is nearly impossible for the model to generate (i.e., $p(\mathbf{w}|\mathbf{c}) \to 0$) would not represent a realistic upper bound on its capability, which is why the probability is included inside the maximization.

2. The Outer Term: Expectation over All Priors

The outer summation, $\sum_{\mathbf{C}\in \mathcal{C}}\sum_{c\in\mathbf{C}}p(\mathbf{c})[\dots]$, simply calculates the expected value of this peak capability over the entire distribution of priors.

• $\mathcal{C}$ is the set of all types of priors (e.g., text, structural embedding of CO problem instances).
• Each $\mathbf{C}$ is a specific prior type (e.g., $\mathbf{C}_1$ = text prompts, $\mathbf{C}_2$ = structural embeddings).
• This sum ensures we account for all distinct modalities/contexts in the task.
• The double summation iterates over all types of priors $\mathbf{C}$ and all specific instances $\mathbf{c}$ within each type.
• $p(\mathbf{c})$ is the probability of encountering a specific prior $\mathbf{c}$.

Therefore, the entire expression calculates the expected maximum probability-weighted performance. It aggregates the best-case scenarios from all possible starting conditions ($\mathbf{c}$), weighted by how likely each condition is to occur.

In essence, the formula defines the model's performance ceiling by first identifying the single best possible output for each prior, and then averaging these peak potentials across the distribution of all priors. This provides a theoretical upper limit on what the model can achieve, which is a useful concept for analyzing its ultimate potential. We hope this breakdown clarifies the intuition and formal justification behind the definition. We will incorporate this detailed explanation into the revised manuscript to enhance its clarity for all readers.

Thank you for acknowledging the value of our work and rebuttal, and for the positive feedback. We appreciate your valuable time and effort in recognizing our paper's novelty in bridging GNNs and LLMs for combinatorial optimization problems.

We have tried our best to address each reviewer's question and provide a more thorough response. We have taken your feedback seriously, especially regarding the potential inefficiency and rigor of the two-phase training strategy. To clarify its effectiveness and rationale, we have conducted additional experiment. The experimental results and observations are shown below, with which we hope the additional results could address your concerns.

Additional Comparison between Two-Phase Training and Jointly End-to-End Training

We admit that the initial submission lacked a thorough discussion of why we adopted the two-stage training procedure. To fully and convincingly answer this question, we have re-designed and implemented an end-to-end joint training method for our proposed model. This new method directly aligns the learning objectives of the graph and text modalities with the same optimization goal: improving the performance of the generated code. Specifically, we do not discriminate between the weights of the GNN and the LLM, meaning they share the same loss function, and the gradient is backpropagated from the parameters of the LLM to those of the GNN.

We implemented the end-to-end joint training method described above and tested the resulting models on two SAT datasets, given the time constraints of the rebuttal phase. All the experimental settings keep the same except for the training method. The results of this new training and testing are presented below. We can conclude two main points from these results:

1. The end-to-end joint training is extremely unstable compared to our proposed two-stage training method. We infer that the training instability stems from the significant architectural and optimization differences between the GNN and the LLM. The gradients, originating from a sequence-level generation loss in the deep LLM, become noisy and attenuated when backpropagated through the entire LLM and into the much shallower GNN. This creates a challenging optimization landscape where a single learning rate is ineffective for both components, leading to unstable convergence (even with many more training steps) as shown in Table 1. Compared with the joint training, the loss curve of our two-stage training method is stable and close to zero at convergence (Please see the loss curve of our two-stage training method in Figure 7 in Appendix B). The GNN and LLM are trained together, which makes it difficult for the models to learn optimal parameters simultaneously.

Table 1: The Training Loss of End-to-End Joint Training

2. The model exhibits poor performance when tested on solving SAT instances. Unsurprisingly, due to its very unstable training and relatively high loss at convergence, the performance of the jointly trained model is significantly lower than our two-stage model on the two SAT datasets, as shown in Table 2.

Table 2: The Jointly Trained Model's Performance over Two SAT datasets

These empirical findings confirm the "significant optimization challenges" mentioned in the paper and justify our decision to use a more stable and effective two-stage training protocol.

However, given the time and resource constraints of the rebuttal period, we are aware that we may not have been able to cover all aspects of the paper, such as testing on a broader range of CO problems or conducting more extensive hyperparameter tuning. We are committed to addressing these limitations and further strengthening the rigor of our results in our future work. Could you please consider raising the score again given that we have addressed the main concerns issued by each reviewers?

Thank you once again for your constructive feedback and continued support of our work.

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score ("3: Borderline reject"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Q1: Is it possible that the performance gain comes from the post-training process rather than the inclusion of $h_q$?

A1: Thank you for your insightful comments, which highlight critical points regarding the significance of our proposed method’s improvements and the source of performance gains. To address your concerns, we have supplemented our experimental results with a comprehensive analysis of ablation variants across the MILP domain, complementing the existing results on the SAT domain in Tables 5 and 6 of the appendix. This additional data helps disentangle the contributions of structural priors, SFT, and DPO to the performance of STRCMP, as shown in below Table.

Table 1: The Optimization Performance result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP domain

Note that for the Primal-Dual Integral, a lower value indicates better performance.

Based on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:

1. The structural prior (integrated via GNN) is critical to performance: The STRCMP w/o GNN variant consistently underperforms compared to the other versions. This empirically validates our central hypothesis that integrating a structural prior into the LLM enhances its ability to generate high-quality code snippets for combinatorial optimization problems.
2. SFT is generally sufficient: For most cases, STRCMP (SFT Only) achieves the best or near-best performance. This suggests that SFT alone is a highly effective method for adapting the composite model, providing a strong and efficient baseline.
3. Full post-training excels on harder instances: For more complex problem instances, such as the corlat dataset (which is notable for its structural difficulty), the full STRCMP model (SFT+DPO) discovers a superior algorithm. This indicates that the preference optimization phase is particularly valuable when tackling challenging instances where nuanced trade-offs in the solution space are more critical.

Q2: The advantage of STRCMP over existing framework (LLM4Solver and AutoSAT) in terms of efficiency and effectiveness.

A2: Thank you for raising this important point. We appreciate the opportunity to clarify the comparative advantages of STRCMP. Our framework demonstrates distinct improvements in both efficiency and effectiveness relative to existing algorithm discovery paradigms, specifically achieving superior or equivalent solution quality with reduced computational resources.

1. Comparison with AutoSAT: All variants of STRCMP consistently discover higher-performing (or equally effective) algorithms at earlier iterations than AutoSAT. This efficiency advantage is empirically validated across multiple problem domains, as illustrated in Figures 4, 8, and 9 of our manuscript.

2. Comparison with LLM4Solver (MILP Domain): We acknowledge that the smoothed performance curves in Figure 10 may have suggested parity between STRCMP and LLM4Solver on simpler datasets (knapsack, mis, setcover). This smoothing was applied for visual clarity but obscured nuanced performance differences. Crucially, on more challenging MILP datasets, STRCMP achieves significant gains in search efficiency. To substantiate this, we provide tabular results (below) detailing non-smoothed, iteration-by-iteration performance. Employing an early stopping criterion (termination after three consecutive iterations without improvement), STRCMP consistently identifies better-performing algorithms faster than LLM4Solver.

Table 2: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over corlat Dataset

Table 3: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over mik Dataset

Table 4: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over loadbalancing Dataset

Q3: Adjustment of problem setting: instead of searching for a general improvement for a code snippet, targeting a problem-specific improvement seems to be more promising.

A3: We thank you for your insightful and constructive feedback on our submission. You raise a crucial and well-articulated point regarding the apparent misalignment between our goal of general algorithmic discovery and our method of providing instance-specific structural information to the LLM.

Your suggestion to adjust the problem setting to target problem-specific improvements is excellent. It provides a much clearer and more direct application for our proposed method. Following your recommendation, we have conducted a new set of experiments to validate this revised problem-specific framework. In this setup, the composite model is prompted to generate an improved heuristic specifically for each problem instance in the target problem family, conditioned on the structural embedding representing topological characteristics of the problem instance.

The results, summarized below, demonstrate that this approach is highly effective. We compare a general-purpose heuristic discovered by AutoSAT against our STRCMP framework, which is tasked with generating both a general heuristic (STRCMP-General) for a class of problem instances and specialized heuristics per instances in the Zamkeller and PRP datasets.

Table 5: Performance of Specialized vs. General Heuristics on SAT Benchmarks (PAR-2 Score ↓)

Note: Base scores for AutoSAT and STRCMP (General) are taken from Table 5 of our submission.

As the results clearly indicate, the specialized heuristics outperform the general-purpose ones on their respective target datasets. The STRCMP-Zamkeller-Specialized heuristic achieves a better PAR-2 score on the Zamkeller test set, but its performance degrades on the PRP dataset. Conversely, the STRCMP-PRP-Specialized heuristic excels on PRP instances while being suboptimal for Zamkeller.

This outcome directly validates the reviewer's intuition and strengthens our paper's core thesis: fusing structural information with LLM-based code generation is a powerful technique for discovering tailored, high-performance algorithms. We are deeply grateful for your feedback. It has prompted us to perform a more focused and compelling evaluation of our framework. We will revise the manuscript to adopt this problem-specific framing, incorporating these new results and clarifying the connection between our methodology, experiments, and theoretical claims.

We sincerely thank you for your thoughtful review, for recognizing the value of our work, and for raising your score. We appreciate the time and effort you have invested.

We agree that the practical challenges you've highlighted regarding the "online" setting are crucial next steps.

• One-Shot Generation: Your point about the limited utility of iterative improvement for a single, time-sensitive problem instance is well-taken. For a truly practical system, minimizing the initial time from problem submission to solution delivery is paramount. We concur that future work must focus on improving the one-shot generation quality to ensure the first generated code snippet is as effective as possible.

• Engineering Overhead: You also raise a critical engineering consideration regarding the on-the-fly compilation overhead for solvers, especially those in languages like C++. This is an essential factor for real-world deployment that must be accounted for to ensure the overall process is time-efficient.

Given the time and resource constraints of the current project, we were unable to explore these aspects in full detail. However, your feedback reinforces their importance. We are committed to tackling these specific challenges—improving one-shot accuracy and mitigating engineering overheads like compilation time—in our future research to enhance the practical viability of our approach. Thank you again for these valuable and constructive suggestions.

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score ("3: Borderline reject"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Q1: Ablated variants and performance: the paper is incomplete without an explanation as to why, or a way of picking which ablated variant to use in which case.

A1: Thank you for raising this critical question. We acknowledge that our initial draft did not sufficiently explain the performance variations among the different ablated versions of STRCMP, which could be confusing. We agree that providing a way to select the appropriate variant is crucial. In addition to the complete results for the SAT domain already in the appendix (Tables 5 and 6), we have added a comprehensive table detailing the optimization performance of the ablation variants on the MILP domain below.

Table 1: The Optimization Performance Result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP Domain

Note that for the Primal-Dual Integral, a lower value indicates better performance.

Based on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:

1. The structural prior is beneficial: The STRCMP w/o GNN variant consistently underperforms compared to the other versions. This empirically validates our central hypothesis that integrating a structural prior into the LLM enhances its ability to generate high-quality code snippets for combinatorial optimization problems.
2. SFT is generally sufficient: For most cases, STRCMP (SFT Only) achieves the best or near-best performance. This suggests that SFT alone is a highly effective method for adapting the composite model, providing a strong and efficient baseline.
3. Full post-training excels on harder instances: For more complex problem instances, such as the corlat dataset (which is notable for its structural difficulty), the full STRCMP model (SFT+DPO) discovers a superior algorithm. This indicates that the preference optimization phase is particularly valuable when tackling challenging instances where nuanced trade-offs in the solution space are more critical.

Q2: Clarification on Experimental Results on MILP domain.

A2: Thank you for raising this point. We recognize that the smoothed curves in the original Figure 10 might have suggested that STRCMP's performance was identical to LLM4Solver in several cases. This was a simplification for visual clarity. On easier datasets like knapsack, mis, and setcover, the problems are not challenging enough to create significant performance separation between the advanced methods.

To provide a clearer picture, we have compiled tables showing the non-smoothed, iteration-by-iteration performance on the more challenging MILP datasets. We employ an early stopping strategy where the search terminates if no performance improvement is observed within three consecutive iterations. As the tables below illustrate, our proposed STRCMP framework consistently discovers better-performing code snippets at an earlier stage compared to LLM4Solver, demonstrating its superior search efficiency.

Table 2: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over corlat Dataset

Table 3: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over mik Dataset

Table 4: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over loadbalancing Dataset

Q3: Positioning this work (and comparing where adequate) with recent LLM-based Optimization Co-Pilots.

A3: We thank the reviewer for the insightful suggestions regarding LLM-based Optimization Co-Pilots and Perozzi et al.’s work. Below is our concise positioning:

1. Positioning vs. LLM Optimization Co-Pilots: Our work targets a distinct stage of the optimization pipeline: Co-Pilots (e.g., OptiMUS, Holy Grail 2.0) automate translation from natural language to formal models (front-end). Our method enhances solver performance for pre-existing models (back-end), using LLMs to generate heuristics, branching strategies, and solver parameters. Thus, we complement—rather than overlap with—this emerging paradigm.

2. Differentiation from Perozzi et al. [1]: While both integrate GNNs and LLMs, our framework (STRCMP) diverges fundamentally: 1) Objective: Perozzi et al. focus on graph QA; our work targets synthesis of executable optimization algorithms; 2) Training: End-to-end training (used in [1]) proved unstable for our code-generation task (please kindly see Table 4 in Response to Reviewer zr9g). STRCMP uses two-stage training (pretrained GNN + frozen embeddings) followed by solver-guided refinement and 3) Execution loop: STRCMP embeds LLM output in an evolutionary feedback loop using solver execution—essential for generating high-performance CO code but absent in [1].

Q4: How much does the performance of STRCMP depend on the underlying LLM?

A4: Thank you for raising this insightful question. Your point about isolating the contribution of the GNN versus the LLM is well-taken. To address this, we have conducted additional ablation studies during the rebuttal period to evaluate the impact of different LLM backbones on STRCMP's performance.

Given the time and resource constraints, we focused our evaluation on the Llama2 and Qwen2 families of models, selecting representatives of varying sizes. We performed training and testing on two datasets from the MILP domain and two from the SAT domain. The results are presented below.

Table 5: The Performance of STRCMP w.r.t. Primal-Dual Integral with Varied-Size Backbone LLM over MILP Domain

Table 6: The Performance of STRCMP w.r.t. PAR-2 Score with Varied-Size Backbone LLM over SAT Domain

Note that for both metrics, a lower value indicates better performance.

It is important to note that the entire Llama2 family of models failed on our code generation task, either by exceeding the context limitation of 4096 tokens or by being unable to generate syntactically correct, executable code. Similarly, the smaller Qwen2 models (0.5B and 1.5B) were also unable to produce viable code for the solvers. This underscores the complexity of the task, which requires a highly capable code-generating LLM. From the results in the tables, we can draw the following conclusions:

1. The structural embedding from the GNN consistently and significantly contributes to the final performance. Across both MILP and SAT domains, and for both the 7B and 14B model sizes, STRCMP consistently outperforms its STRCMP w/o GNN variant. This confirms that the GNN provides a crucial inductive bias that guides the LLM toward better solutions, regardless of the LLM's scale.

2. STRCMP's performance is robust, provided a sufficiently capable LLM backbone is used. While our framework's effectiveness is contingent on the LLM's fundamental ability to comprehend the task and generate valid code, the performance is stable across capable models of different sizes.

3. STRCMP's performance is sensitive to the size of the LLM backbone, but this effect is problem-dependent. The results reveal a nuanced relationship between model scale and performance. For the more complex mik instances, scaling the LLM from 7B to 14B parameters yields a notable performance gain. However, for the setcover instances, the 7B and 14B models perform almost identically. This suggests that while larger models can unlock better performance on certain complex problem structures, a more moderately-sized model may be sufficient for others.

We thank the reviewer for this suggestion, as these experiments have strengthened the paper and provided a clearer understanding of the interplay between the structural and language components of our framework. We will add this analysis to the final version of the paper.

Dear Reviewer,

We hope this message finds you well. As the discussion period concludes in less than two days, we wanted to confirm whether we have adequately addressed all your concerns.

We have already incorporated feedback from Reviewers 2EbJ, 7osJ, and zr9g, who acknowledged our rebuttal and raised their scores accordingly. If you have any remaining questions or additional suggestions, we would greatly appreciate the opportunity to address them before the deadline.

Your insights have been invaluable in improving our work, and we remain committed to refining it further based on your feedback.

Thank you again for your time and thoughtful review.

Best regards,
The Authors of Submission7504

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score ("3: Borderline reject"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Q1: Ragarding the counterintuitive result of the ablation studies: could you elaborate on how your "multi-modal co-learning" specifically helps the LLM overcome these "weaker priors for structured domains"?

A1: We sincerely thank the reviewer for this insightful question, which highlights critical points regarding the significance of our proposed method’s improvements and the source of performance gains. To address your concerns, we have supplemented our experimental results from two perspectives.

(1) Comprehensive analysis of ablation variants across the MILP domain, complementing the existing results on the SAT domain in Tables 5 and 6 of the appendix. This additional data helps disentangle the contributions of structural priors, SFT, and DPO to the performance of STRCMP, as shown below.

Table 1: The Optimization Performance Result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP Domain

Note that for the Primal-Dual Integral, a lower value indicates better performance.

Based on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:

• The structural prior (integrated via GNN) is critical to performance: The STRCMP w/o GNN variant consistently underperforms compared to the other versions. This empirically validates our central hypothesis that integrating a structural prior into the LLM enhances its ability to generate high-quality code snippets for combinatorial optimization problems.
• SFT is generally sufficient: For most cases, STRCMP (SFT Only) achieves the best or near-best performance. This suggests that SFT alone is a highly effective method for adapting the composite model, providing a strong and efficient baseline.
• Full post-training excels on harder instances: For more complex problem instances, such as the corlat dataset (which is notable for its structural difficulty), the full STRCMP model (SFT+DPO) discovers a superior algorithm. This indicates that the preference optimization phase is particularly valuable when tackling challenging instances where nuanced trade-offs in the solution space are more critical.

(2) Experiments about isolating the contribution of the GNN versus the LLM backbone. To address this, we have conducted additional ablation studies during the rebuttal period to evaluate the impact of different LLM backbones on STRCMP's performance. Given the time and resource constraints, we focused our evaluation on the Llama2 and Qwen2 families of models, selecting representatives of varying sizes. We performed training and testing on two datasets from the MILP domain and two from the SAT domain. The results are presented below.

Table 2: The Performance of STRCMP w.r.t. Primal-Dual Integral with Varied-Size Backbone LLM over MILP Domain

Table 3: The Performance of STRCMP w.r.t. PAR-2 Score with Varied-Size Backbone LLM over SAT Domain

Note that for both metrics, a lower value indicates better performance.

It is important to note that the entire Llama2 family of models failed on our code generation task, either by exceeding the context limitation of 4096 tokens or by being unable to generate syntactically correct, executable code. Similarly, the smaller Qwen2 models (0.5B and 1.5B) were also unable to produce viable code for the solvers. This underscores the complexity of the task, which requires a highly capable code-generating LLM. From the results in the tables, we can draw the following conclusions: the structural embedding from the GNN consistently and significantly contributes to the final performance. Across both MILP and SAT domains, and for both the 7B and 14B model sizes, STRCMP consistently outperforms its STRCMP w/o GNN variant. This confirms that the GNN provides a crucial inductive bias that guides the LLM toward better solutions, regardless of the LLM's scale.

Q2: Could you provide more specific details on challenges related to joint end-to-end training?

A2: We sincerely thank the reviewer for this insightful question. We admit that the initial submission lacked a thorough discussion of why we adopted the two-stage training procedure. To fully and convincingly answer this question, we have re-designed and implemented an end-to-end joint training method for our proposed model. This new method directly aligns the learning objectives of the graph and text modalities with the same optimization goal: improving the performance of the generated code. Specifically, we do not discriminate between the weights of the GNN and the LLM, meaning they share the same loss function, and the gradient is backpropagated from the parameters of the LLM to those of the GNN.

We implemented the end-to-end joint training method described above and tested the resulting models on two SAT datasets, given the time constraints of the rebuttal phase. All the experimental settings keep the same except for the training method. The results of this new training and testing are presented below. We can conclude two main points from these results:

1. The end-to-end joint training is extremely unstable compared to our proposed two-stage training method. We infer that the training instability stems from the architectural and optimization differences between the GNN and the LLM. The gradients, originating from a sequence-level generation loss in the deep LLM, become noisy and attenuated when backpropagated through the entire LLM and into the much shallower GNN. This creates a challenging optimization landscape where a single learning rate is ineffective for both components, leading to unstable convergence (even with many more training steps) as shown in Table 4. Compared with the joint training, the loss curve of our two-stage training method is stable and close to zero at convergence (Please see the loss curve of our two-stage training method in Figure 7 in Appendix B). The GNN and LLM are trained together, which makes it difficult for the models to learn optimal parameters simultaneously.

Table 4: The Training Loss of End-to-End Joint Training

2. The model exhibits poor performance when tested on solving SAT instances. Unsurprisingly, due to its very unstable training and relatively high loss at convergence, the performance of the jointly trained model is lower than our two-stage model on the two SAT datasets, as shown in Table 5.

Table 5: The Jointly Trained Model's Performance over Two SAT datasets w.r.t. PAR-2 Score

Note that for PAR-2 Score, a lower value indicates better performance.

These empirical findings confirm the "significant optimization challenges" mentioned in the paper and justify our decision to use a more stable and effective two-stage training protocol.

Q3: How does the interpretability of these generated code functions scale with the increasing complexity of the CO problem or the sophistication of the heuristics discovered?

A3: We appreciate your insightful inquiry regarding the scalability of interpretability in STRCMP. We fully acknowledge that while code generation enhances transparency relative to neural black-box methods, interpretability does not scale linearly with problem complexity. For highly intricate CO problems or novel heuristics, generated code may involve nested logic, context-dependent optimizations, or non-intuitive transformations. This necessitates non-trivial effort for human experts to parse, reducing immediate interpretability.

Nevertheless, STRCMP retains fundamental advantages over neural NCO methods: 1) Inspectability: solver logic remains open to direct inspection in its artifactual form; 2) Modifiability: code can be edited without model retraining; and 3) Debuggability: runtime validation and issue tracing via standard tools remain possible.

We view the interpretability of complex generated code as an ongoing research challenge and are committed to addressing it in future work. Potential directions include simplifying the generated algorithms through post-processing or enhancing them with annotations to aid human understanding. For now, we believe STRCMP strikes a valuable balance, advancing interpretability over NCO methods while laying the groundwork for further improvements.

Q2: The new experiments of the ablation study still raises this question of whether we need a model with SFT+DPO. It works only for one dataset. Also, what is the complexity of the dataset? Could you provide insights on when one might need SFT+DPO?

A2: To provide a clearer and more comprehensive answer, we offer a detailed analysis focusing on dataset complexity and the iterative optimization behavior of our proposed method, STRCMP, and its variants.

Dataset Complexity

The complexity of combinatorial optimization problems can be characterized by various metrics. Drawing from established literature, we focus on several key graph-based metrics—Modularity, Density, and Clustering—to provide a quantitative perspective on the structural complexity of the datasets used in our experiments. While not absolute, higher values in these metrics generally suggest a more intricate problem structure and complexity. The problem sizes are detailed in Appendix D of our manuscript. The statistics for the MILP and SAT datasets are presented below.

Table 1: Data Complexity of MILP Dataset

Table 2: Data Complexity of SAT Dataset

Iterative Behavior of STRCMP and its Variants

In addition to the iterative optimization results for the MILP domain (presented in Tables 2, 3, and 4 in our main rebuttal to Reviewer 7TYC), we now provide the corresponding analysis for the SAT domain. These results illustrate the performance trajectory (PAR-2 score) of STRCMP against its SFT-only and DPO-only ablations.

Note: We employ a conditional stopping strategy, halting the training process if the model's performance on the training set does not improve for three consecutive iterations. Hence the total iteration number of different method will be varied.

Table 3: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over CNP Dataset

Table 4: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over CoinsGrid Dataset

Table 5: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over PRP Dataset

Table 6: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over Zamkeller Dataset

Thank you for your valuable feedback and for allowing us to clarify our contributions. We apologize for the previous ambiguity in our rebuttal. We provide a distinct and detailed discussion for Q1 below, supported by new experimental results. We sincerely appreciate you raising this insightful point. Here, we address your question: Could you elaborate on how your "multi-modal co-learning" (line 223) specifically helps the LLM overcome these "weaker priors for structured domains"? Is it primarily the GNN providing the structured information that the LLM then learns to condition on?

To empirically validate the criticality of this GNN-provided structural prior, we have re-run our ablation experiments with a more robust termination condition.

Additional Experimental Validation over Two SAT Datasets.

We re-ran the experiments for the CNP and CoinsGrid datasets on the SAT domain since in the original experiment, the performance distinction between different variants of STRCMP is very close, which cannot correctly distinguish the performance of different variants especially the effectiveness of inclusion of GNN. The key change was switching the termination condition from a fixed maximum number of iterations to stopping when the model's training set performance did not improve for three consecutive iterations. This aligns the methodology with our MILP experiments and provides a clearer view of each variant's potential. The new results are presented in Table 1.

Table 1: The Optimization Performance result w.r.t. PAR-2 Score between Different Ablation Variants over SAT Domain

Experimental Validation over MILP Datasets

Table 2: The Optimization Performance result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP domain

Experimental Validation on Structral Prior's Contribution with Varied-Size backbone LLM

Table 3: The Performance Comparison between STRCMP and STRCMP w/o GNN w.r.t. Primal-Dual Integral with Varied-Size Backbone LLM over MILP Domain

Table 4: The Performance Comparison between STRCMP and STRCMP w/o GNN w.r.t. PAR-2 score with Varied-Size Backbone LLM over SAT Domain

Claims Made Upon above Results

By combining these updated results with our existing experiments (Tables 2, 3, and 4), we can draw two firm conclusions:

1. The structural prior (integrated via GNN) is critical to performance. In every experiment across both SAT (Table 1) and MILP (Table 2) domains, the STRCMP w/o GNN variant consistently underperforms compared to the full STRCMP model and its other variants with GNN. This empirically validates our central hypothesis that integrating a structural prior is essential for enhancing the LLM's ability to solve combinatorial optimization problems.

2. The structural embedding from the GNN consistently and significantly contributes to the final performance. As shown in Tables 3 and 4, STRCMP consistently outperforms its STRCMP w/o GNN counterpart across both the 7B and 14B model sizes. This demonstrates that the GNN provides a crucial and scalable inductive bias that guides the LLM toward better solutions, regardless of the LLM's parameter count.

These comprehensive results strongly support our claim that the multi-modal co-learning approach, driven by the GNN's structural prior, is the key factor in overcoming the LLM's inherent weaknesses in structured domains.

Analysis and Insights

From the iterative performance results, we draw two primary observations:

1. SFT-only models often converge faster in terms of iteration count but may stabilize at a suboptimal performance level. This suggests that while SFT is effective at rapidly imitating strong solutions, it may overfit to the strategies present in the initial dataset, leading to premature convergence in a local optimum.

2. DPO-inclusive models (DPO-only and SFT+DPO) demonstrate a capacity for continued improvement over a longer training horizon, often surpassing the SFT-only model's peak performance. We posit that DPO enhances the model's generalization capabilities. By learning from preference pairs rather than absolute solutions, the model develops a more nuanced understanding of what constitutes a better search trajectory, allowing it to escape local optima and discover superior solutions.

Based on these observations and the complexity analysis, we can summarize our insights on selecting a training strategy:

1. For "easy" datasets (e.g., small-scale, sparse, solvable to optimality quickly): The SFT-only approach is often sufficient and efficient. On these problems, high-quality training data (i.e., optimal or near-optimal solutions) can be generated at a low cost, allowing SFT to quickly learn an effective policy.

2. For "hard" datasets (e.g., large-scale, dense, complex structure, intractable): We strongly recommend a DPO-based approach (DPO-only or SFT+DPO). For these problems, obtaining optimal solutions for SFT is prohibitively expensive or impossible. However, generating preference pairs by comparing the performance of different candidate solutions is still feasible and relatively cheap. The superior generalization of DPO-trained models makes them better suited to navigating the vast and complex search spaces of these challenging instances.

3. For medium complexity datasets, the choice is less definitive. As the results show, the interplay between SFT and DPO is intricate. Our full STRCMP model (SFT+DPO) often acts as a robust default, leveraging SFT for a strong initialization and DPO for refinement and generalization. However, we acknowledge that determining the optimal blend is a significant challenge. The task-specific training of large models has not yet fully clarified the precise relationship between SFT and DPO—when one is definitively superior, or how their data should be optimally combined. We consider this an important open problem for the field.

We hope this detailed analysis clarifies the rationale behind our approach and provides valuable insights into when a combined SFT+DPO model is most impactful.

Reference

[1] Li, Yang, et al. "Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong structure-hardness-aware baseline." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

[2] Geng, Zijie, et al. "A deep instance generative framework for milp solvers under limited data availability." Advances in Neural Information Processing Systems 36 (2023): 26025-26047.

[3] Ye, Huigen, et al. "ML4MILP: A Benchmark Dataset for Machine Learning-based Mixed-Integer Linear Programming."

While our proposed method, STRCMP, does exhibit certain advantages in interpretability when compared to some existing neural combinatorial methods, this was not the primary focus of our work. We acknowledge that a comprehensive and rigorous treatment of the interpretability of deep learning models for combinatorial optimization is a significant and challenging research area. Fully addressing this issue would require a dedicated study that, we believe, extends beyond the intended scope of the current paper. We appreciate the reviewer highlighting this important aspect, which we consider a valuable direction for future research.

Thank you for your response and for acknowledging our work. We greatly appreciate the time and effort you have devoted to reviewing it. If you have any further questions or concerns, please feel free to let us know—we would be happy to address them. We will incorporate all feedback into the final version of our paper.

We sincerely hope this detailed response has adequately addressed your remaining concerns. If so, we would deeply appreciate it if you could raise your score ("3: Borderline reject"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission. We are grateful for the thorough and constructive feedback throughout this process, as it has helped us significantly strengthen the paper.

Reviewer zr9g

4. Interpretability of these generated code functions scale with the increasing complexity of the CO problem.

We explain the interpretability of the generated code functions with the following points: 1) Inspectability: solver logic remains open to direct inspection in its artifactual form; 2) Modifiability: code can be edited without model retraining; and 3) Debuggability: runtime validation and issue tracing via standard tools remain possible. We view the interpretability of complex generated code as an ongoing research challenge and are committed to addressing it in future work.

Reviewer 7TYC

5. Clarification on Experimental Results on MILP domain.

To provide a clearer picture, we have compiled tables showing the non-smoothed, iteration-by-iteration performance on the more challenging MILP datasets. We employ an early stopping strategy where the search terminates if no performance improvement is observed within three consecutive iterations. As the newly added results shown, our proposed STRCMP framework consistently discovers better-performing code snippets at an earlier stage compared to LLM4Solver, demonstrating its superior search efficiency.

6. Positioning this work (and comparing where adequate) with recent LLM-based Optimization Co-Pilots.

We have supplemented the thorough comparison between our work and reviewer listed work.

7. How much does the performance of STRCMP depend on the underlying LLM?

To address this, we have conducted additional ablation studies during the rebuttal period to evaluate the impact of different LLM backbones on STRCMP's performance. Given the time and resource constraints, we focused our evaluation on the Llama2 and Qwen2 families of models, selecting representatives of varying sizes. We performed training and testing on two datasets from the MILP domain and two from the SAT domain.

Reviewer 7osj

8. The advantage of STRCMP over existing framework (LLM4Solver and AutoSAT) in terms of efficiency and effectiveness.

We have highlighted the distinct improvements in both efficiency and effectiveness relative to existing algorithm discovery paradigms, specifically achieving superior or equivalent solution quality with reduced computational resources.

9. Adjustment of problem setting.

We have tried to addjust the problem setting. Following this new setting, we have conducted a new set of experiments to validate this revised problem-specific framework. The experimental results demonstrate that this approach is highly effective and validate the reviewer's intuition and strengthens our paper's core thesis: fusing structural information with LLM-based code generation is a powerful technique for discovering tailored, high-performance algorithms.

Reviewer 2Ebj

10. Please explain the natural language description of the CO problem.

We have explained and give more details about the natural language description of the CO problem.

11. Justification on that different problems subsume different structures.

To further justify this methodology and directly respond to this concern, we conducted an experiment comparing two training strategies. We trained a separate STRCMP model using only one class of dataset and compared its performance with that of a model trained on a mixed dataset encompassing multiple CO problems. The experimental results highlight that training on a mixed-class dataset not only mitigates the risk of overfitting to a single problem’s structure but also enhances generalization and efficiency across structurally similar CO problems.

12. The executability and correctness of LLM-generated code in the proposed framework.

We have explained the executability and correctness of LLM-generated code in terms of compilation check and performance evaluation.

13. Explain more about the sup(P) in definition 1.

We have explained this definition via breaking down the formula sup(P) and explaining the components seperately.