$\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
Authors: Xijun Li
Jiexiang Yang
Jinghao Wang
Bo Peng
Jianguo Yao
Haibing Guan
Venue: NeurIPS 2025 poster ()
Keywords: Learning to Optimize
LLM Code Generation
Combinatorial Optimization
Primary area: machine_learning_for_sciences
TL;DR: We propose a novel structure-aware LLM-based algorithm discovery framework for combinatorial optimization (CO)，simultaneously enhancing solution quality and computational efficiency in solving CO problems.

Abstract: Combinatorial optimization (CO) problems, central to operation research and theoretical computer science, present significant computational challenges due to their $\mathcal{NP}$-hard nature. While large language models (LLMs) have emerged as promising tools for CO—either by directly generating solutions or synthesizing solver-specific codes—existing approaches often $\textit{neglect critical structural priors inherent to CO problems}$, leading to suboptimality and iterative inefficiency. Inspired by human experts’ success in leveraging CO structures for algorithm design, we propose $\texttt{STRCMP}$, a novel structure-aware LLM-based algorithm discovery framework that systematically integrates structure priors to enhance solution quality and solving efficiency. Our framework combines a graph neural network (GNN) for extracting structural embeddings from CO instances with an LLM conditioned on these embeddings to identify high-performed algorithms in the form of solver-specific codes. This composite architecture ensures syntactic correctness, preserves problem topology, and aligns with natural language objectives, while an evolutionary refinement process iteratively optimizes generated algorithm. Extensive evaluations across Mixed Integer Linear Programming and Boolean Satisfiability problems, using nine benchmark datasets, demonstrate that our proposed $\texttt{STRCMP}$ outperforms five strong neural and LLM-based methods by a large margin, in terms of both solution optimality and computational efficiency. The code is publicly available in the repository: https://github.com/Y-Palver/L2O-STRCMP.

STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
Xijun Li Jiexiang Yang", Jinghao Wang', Bo 22 Jianguo Yao Haibing Guan 1.
'Shanghai Key Laboratory of Scalable Computing and Systems School of Computer Science, Shanghai Jiao Tong University (1ixijun,jjaageee jianguo. yaou jsstasjtuuuu.... wtd.assuuuuuuu...... edu.
Abstract
Combinatorial optimization (CO) problems, central to operation research and theo- retical computer science, present significant computational challenges due to their N'P-hard nature. While large language models (LLMs) have emerged as promising tools for CO-either by directly generating solutions or synthesizing solver-specific codes codes-existing approaches often neglect critical structural priors inherent to CO problems, leading suboptimality and iterative inefficiency. Inspired by human experts" success in leveraging CO structures for algorithm design, we propose STRCMP, novel structure-awe aaare LLM-based algorithm discovery framework that systematically integrates structure priors to enhance solution quality and solving efficiency. Our framework combines a graph neural network (GNN) for extract- ing structural embeddings from CO instances with an LLM conditioned on these embeddings to identify sershoerformin algorithms in the form of solver-specific codes. This composite architecture ensures syntactic correctness, preserves prob- lem topology, and aligns with natural language objectives, while an evolutionary refinement process iteratively optimizes generated algorithm. Extensive evaluations across Mixed Integer Linear Programming and Boolean Satisfiability problems, using nine benchmark datasets, demonstrate that proposed STRCMP outperforms five strong neural and LLM-based methods by a large margin, in terms of both solution optimality and computational efficiency. The code is publicly available the repository: https://github.com/Y wawply---aaaelaaaa 200-S/RCMM
Introduction
Making complex plans subject to multiple constraints is time- and labor-intensive process, but is critical in many aspects of our lives such as scheduling (1 logisties (2), and robotics 3 These problems are frequently mod- eled as combinatorial optimization (CO) problem, a cor- nerstone of operation research and theoretical computer science, where the objective to identify optimal solu- tions within discrete, highly constrained search spaces, However, the inherent A WPPhhadneess of many CO prob- lems renders obtaining exact solutions computationally intractable, posing significant challenges in solving them efficiently and accurately. Consequently, substantial search efforts have endeavored to developing algorithms that balance solution quality with computational cost, typically requiring specialized domain expertise and rigorous analytical modeling of problem structure (4-).
Prompt
LLM
Code
Solver
Previous work
Structure
Σ} Solver
Our Model
Code
Prompt
The proposed method
Figure I: Intuitive comparison berween
prior work and the proposed framework.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Machine learning (ML) techniques, particularly deep learning and reinforcement learning, have demonstrated significant potential in addressing CO problems 77. As many CO problems arising from similar application domains exhibit inherent structural patterns, MI methods can leverage these patterns to reduce computational complexity in traditional CO approaches through data-driven strate- gies. The integration of MI. and CO frameworks can be broadly categorized into three paradigms [7] (1) End-to-end neural solvers [+I0],, which train ML models to directly output CO solutions; (2) ML- augmented algorithm configuration [1H leveraging ML models to predict optimal algorithmic configurations for specific CO algorithm to solve associated problems; and (3) Hybrid methods 14- 16 embedding ML models critical decision modules within traditional CO solvers. However, real-world adoption of above approaches remains limited due to reliance on training distributional alignment for generalization and inherently insufficient interpretability [17].
Building on the explosive advancements in large language models (LLLMs) over recent years, combi- natorial optimization tasks have shown potential for delegation to LLMs, particularly owing to their improved accountability and interpretability compared to conventional MI. approaches Capitalizing on their extensive world-knowledge priors and advanced code generation capabilities, numerous LLM-based approaches for CO problems have emerged. These methods bifurcate into two classes: (I) direct utilization of LLMs to solve CO problems [8 [19, and (2) employing LLMs to discover high-quality algorithm (in the form of solver-specific codes) for traditional solvers [20-22). For example, Yang et al. [18] present Optimization by PROmpting (OPRO), which harnesses LLMs as blxck-box optimizers through iterative solution refinement via natural- -aauuale problem specifica- tions and optimization trajectories. In contrast, Cammera-Pareder et al. (20 proposes FunSearch that integrates a pre-trained L.M into an evolutionary algorithm to incrementally generate solver code, achieving state-of-the-art results the cap set problem and discovering novel heuristics for online bin packing. Additionally, Huang et al. [19 demonstrates that multi-modal fusion of textual and visual prompts enhances LLM-driven optimization performance, as evidenced in capacitated vehicle routing problems.
Despite these advances, current LLM-based approaches for solving CO problems remain in their infancy. As illustrated in Figure [1 they primarily rely on textual (or occasionally visual) prompting mechanisms to interface with LLMs, failing to effectively exploit the inherent topological structures of CO problems. Historically, human experts have successfully leveraged structural priors of CO problems design sophisticated and efficient algorithms (4. Furthermore, existing LLM-based methods 20 21 18 often require multiple iterations to produce high-quality solutions or algorithm implementations, primarily due to their lack of integration with CO-specific structural priors. As highlighted in Yao's insightful analysis (23, pre-training language model establishes strong priors for conversational tasks but weaker priors for structured domains like computer controls or video games - -challenges exacerbated in solving CO problems, as these domains differ significantly from Internet text distributions. Given these challenges. developing a generative model that effectively integrates structural priors for CO problem solving becomes particularly compelling, As shown in Figure [ the distinct insight lies in constructing a generative model that generates solver-specific code while respecting the intrinsic topological structure of CO problems. Theoretically, this approach aligns with the rising research directions of multi-modal generative model. Practically, such integration offers substantial benefits, dramatically reducing inference iterations while enhancing solution quality in solving CO problem.
To tackle this challenge, we present STRCMP ! a novel structure-prior-an discovery framework for solving CO problems. To the best of our knowledge, STRCMP is the first framework to explicitly integrate structural priors of CO problems into LLM-driven algorithm discovery, jointly improving solution quality and computational efficiency. Our framework first constructs composite architecture combining a graph neural network (GNN) and an LLM. The GNN extracts structural embeddings from input CO instances, which serves as inductive biases for subsequent algorithm discovery via code generation. The L.M then produces solver-specific code conditioned on these structural priors, ensuring adherence to solver syntax, preservation of CO problems' topological characteristics, and alignment with natural language optimization objectives. This composite model is further embedded within an evolutionary algorithm-baser refinement process to iteratively enhance solution quality. Besides, we provide the theoretical analysis why fusing the structure prior into LLM can benefit solving CO problem from the perspective of information theory.
LLM-based algorithm
'STRCMP stands for STRucture- aware CoMPposite model that can discover and generate algorithm imple- mentation for CO problems considering intrinsic topological structure of the problem.
2

---

Extensive experiments across two representative CO domains (Mixed Integer Linear Programming and Boolean Satisfiability), spanning nine benchmark datasets, demonstrate that STRCMP outperforms five well-recognized baselines by large margin-inchuddng neural combinatorial optimization methods and I.L.-based approaches- both solution optimality and computational efficiency.
2 Related Work
15 16 has explored machine learning integration with combinatorial optimization for improved computational approaches to A'P- hard problems, forming Neural Combinatorial Optimization (NCO) methods that either approximate expert heuristics or learn policies via reinforcement learning. Following Bengio et al. 7'ss 's taxonomy, NCO encompasses: (1) End-to-end neural solvers [8-10], (2) ML-augmented algorithm configuration 11 and (3) Hybrid methods integrating learned components into classical frameworks [6
Neural Combinatorial Optimization. Extensive research [14
24
25
Pointer Networks (25 represent seminal work, employing attention mechanisms g as dynamic
pointers for CO problems, eliminating dependence on fixed output dictionaries in conventional seq2seq models 26 The framework achieves competitive performance on convex hulls, Delaunay triangulation, and small TSP instances while generalizing to unseen sizes. hybrid approaches, Gasse et al. 14] introduced GCNs trained via imitation learning to replace strong branching heuristics 27 in branch-and- bound algorithms for MIP solvers. While avoiding manual feature engineering through graph representations, such approaches face scalability challenges under extreme problem sizes, key limitation of neural solver architectures. Moreover, NCO's reliance on opaque ma- chine learning models yields policies with insufficient interpretabilityy decision- maanin systems demanding traceable logic [7]. Our approach addresses these gaps by furnishing optimality certificates bounded sub-optimality guarantees via CO solver integration. By procedurally generating solver-executable code through iterative refinement, our framework ensures superior interpretability relative black-box NCO policy learning.
for high-stakes
Language Models for Combinatorial Optimization Problem. Recent advances large lan- guage models (LLMs) have spurred explorations of their applications to combinatorial optimization [20 30). Current approaches fall into two categories: (1) direct solution generation via LLM inference [18 [19, and (2) automated generation of solver-compatible formalizations (2 33). In the first paradigm, Yang et al. [18] propose Optimization by PROmpting (OPRO), leveraging LLMs black-box optimizers through iterative refinement of natural-languuag problem descriptions. While achieving comparable performance to heuristics on small TSP instances, OPRO scales poorly beyond 50 nodes due to context limitations and solution- space complexity. For the second paradigm, Romera-Paredes et al. [20] introduce FunSearch, combining evolutionary methods with L.MM-gudddd program synthesis to obtain breakthroughs
the cap set problem [3] and generate novel bin packing heuristics (32). Similarly, (21) develop Evolution of Heuristics (FoH), integrating evolution- ary algorithms with L.MMs co-optimize natural language "thoughts" and code implementations through iterative prompting, outperforming existing methods like FunSearch in query efficiency 20 Existing approaches predominantly employ natural language (or occasionally visual (19) prompts combined with evolutionary frameworks for iterative code generation to solve CO problems. However, these methods universally neglect the topological structural characteristics intrinsic to combinatorial optimization problems, which are systematically exploited by human experts during algorithm design [4.6. Furthermore. evolutionary framework- based code generation with LLMs often necessitates multiple iterations for convergence while incurring significant computational overhead from repeated solver invocations during evaluation. To overcome these limitations, we propose composite model that effectively incorporates structural priors of CO problems during algorithmic discovery. By developing composite architectures tailored to CO problem structures, our method substantially improves both solution quality and computational efficiency compared to existing LLM-based solving approaches.
3 Problem Statement
we formulate general combinatorial optimization problem Q (e.g.. Boolean Satisfiability (SAT) and Mixed Integer Linear Programming (MILP)) as constrained discrete optimization problem. For an instance of Q, the formulation becomes:
Combinatorial Optimization. Following (33],
min c(x; g) + f(x;)))
(I)
xES(g)
3

---

Combinatorial Structure Extract.
Structure-Aware Code Generation
Evolutionary Code
Refinement for CO
(a) Curation
Prompt
Math. Model
Specification of generataion
6000
Evaluate
Model
ΣX
Prompt
LLM
Code
Solver
Bipartie
Graph
Collects Triplets: (Math. Model, Code, Metrics)
Photraned
(b) Post Training
SFT/DPO the Model
Feedback
Graph Neural
w/ collected data
GNN
Prompt
Generate Code
Network
Pretrained
Pretrained GNN
ΣX
Code
Structure
The Composite Model
Embeddding
Evaluate
Code
Structure
Figure 2: Overview of the proposed STRCMP. O Combinatorial Structure Extraction. We utilize a graph neural network (GNN) to encode the topological structure combinatorial optimization problems into latent embeddings, capturing problem-specific structural invariants. @ Structure- Aware Code Generation: (a) Data Curation: For given CO problem's 's mathematical model, target solver and the specific prompt, LLM generates candidate algorithm in the form of code snippets, which are automatically validated via the solver execution to generate performance metrics. This yields curated dataset comprising (mathematical model, code snippet, metric) triplets. (b) Post Training: composite architecture integrating a frozen pretrained GNN with an LLM fine-tuned this dataset, ensuring code generation respects both the CO's S intrinsic topology and solver-specifie syntax. Evolutionary Code Refinement. Drawing on 220). the composite model is embedded within evolutionary framework to evolve the algorithm discovery process through performance- driven iterations.
where x denotes decision variables subject to solution space S(q); c(æ; q) represents the objective function to minimize, and f'z;; 9) corresponds to constraint penalties (zero when all constraints are satisfied). In SAT problems, the objective function e(2; q) is absent since only constraint satisfaction required. Conversely, MILP problems feature both objective and constraint functions.
Generation Task. Given a combinatorial optimization problem Q, our goal is find algorithm A that can consistently solve Q well:
(c min E (.= [c(2; 4) + (x;;g)
A~A
where A denotes the algorithm search space. This work focuses on symbolic search spaces where A comprises algorithms representable as code snippets executable within a combinatorial optimization solver. We resort a generative model to synthesize the target algorithm through code generation.
Proposed Solution
The proposed framework is illustrated in Figure 2 We first describe the technical interplay among components within the proposed framework. highlighting design motivations and synergistic interac- tions. Subsequently, we provide a theoretical analysis demonstrating that integrating structural priors into L.LMs enhances performance in solving combinatorial optimization problems.
4.1 Methodology
Combinatorial Structure Extraction. Combinatorial optimization problem is equivalently converted bipartite graph. Thus, the intrinsic structure of the combinatorial optimization problem can be casily captured by graph neural network, as has been done in many previous work [16] 24 14]

---

As shown in the leftmost part of Figure 2 we continue to use this technique to extract structure embedding of given CO problem, benefiting the following algorithm discovery process.
Specifically, a bipartite graph G = (C. E, V) is constructed for the CO problem instance where C' corresponds the constraints of q; V denotes the variables of q; and edge eij E E between constraint node i and variable node if they have a connection. A graph neural network 0g takes as input the bipartite graph to generate the structural embedding h, E R2 of the problem instance q. We simply train 0G via a classification task, where group of CO problems and their class label are given. The problems falling into the same class means that they originates from the same scenario/domain, such as traveling salesman problems [34], production planning [35,, vehicle routing problem [6], etc. The data representation. training, implementation details are left Appendix [B.]] In this way. GNNs can capture structure priors of CO problem (such as symmetry. sparsity, and degeneracy), which are critical for solver decisions. The extracted embeddings transfers structural insights to downstream code generation task, facilitating generalization across problem classes.
Structure- Code Generation. In this step, we construct a composite generative model to achieve structure-aware algorithm discovery for CO problem. The composite model is essentially concatenation of a GNN and an LLM. GNN obtained via training method mentioned in Step 1 and frozen in the composite model, which provides the structure embedding of given CO problem to LLM. The LLM takes as input the natural language description of the problem and of the code generation task. Then the LLM generates candidate algorithm in the form of code snippet conditioned on the natural language description and structure embedding for a specific solver, as shown in the The code generation procedure can be formulated below:
middle part of Figure 2
T P(W1, W2, ..., WT) = II Po..
NLL)
where [wali 1,,, T is the code snippet predicted by the composite model: hy is the structure embedding of given CO problem instance q; N L is the natural language description of q and of code generation task; Or, is the parameter of LLM.
As anticipated, the composite model exhibits suboptimal performance on code generation tasks for CO problems due to architectural incompatibilities that disrupt the native token prediction mechanism of the underlying LLM. To address this architectural mismatch, we implement a two-phase training protocol consisting of: (a) data curation through systematic problem sampling, and (b) parameter optimization via post-training. This phased approach enables effective adaptation of the composite architecture while preserving the structural integrity of the original CO problem representations.
(a) Data Curation. To facilitate the post-training phase, we aim to collect four key categories of data: 1) mathematical formulations of CO problems; 2) natural language specifications detailing problem requirements alongside corresponding code generation objectives for targeted CO solvers; 3) executable code implementations derived from these specifications; and 4) quantitative performance metrics evaluating solution quality and computational efficiency of the implemented code.
(b) Post- Training. In this phase, we only train the parameter 0r of the composite model, which means that structural embeddings remain consistent during post-training. We conduct Supervised Fine-Tuning (SFT) on Or using the curated dataset, followed by Direct Preference Optimization (DPO) 377 initialized from the SFT checkpoint to derive the final composite model. All details, including prompt template, data curation and post-training, are presented in Appendix B.2
@ Evolutionary Code Refinement for Combinatorial Optimization Problem. Prior work 30
20
29 leverages L.Mss code generation and algorithm design capabilities within Eyolutionary Algo- rithms (EAs) to address combinatorial optimization problems through iterative feedback frameworks. The iterative nature of evolutionary algorithms introduces significant computational overhead as the primary limitation of prior approaches [30 20 29 for identifying optimal code snippets or algorithms to solve combinatorial optimization problems. Convergence typically requires numerous iterations, exacerbated by the prolonged execution times required for solver- based evaluation of generated code or algorithm candidates.
Our evolutionary code optimization framework for combinatorial optimization adopts the core with the significant distinction lying in the composite model learned in Step @ (see Figure 2 right panel). Our framework jointly processes both textual problem descriptions with algorithm discovery objectives and formal mathematical model of CO problems.
principles of prior work[30]
20 29
5

---

The composite model generates solver-specific, siructure-awat code through standard EA operators (selection, crossover, mutation), producing higher-quality algorithm implementation within fewer iterations a capability empirically validated in our experiments. By integrating this model into EA-based algorithm discovery frameworks, we achieve superior optimization performance while maintaining compatibility with existing evolutionary algorithm design paradigms, suggesting broader applicability across LLM-driven optimization methodologies.
4.2 Theoretical Analysis
In the following, we give the theoretical analysis why fusing the structure prior into the generative model helps algorithm discovery for solving CO problem the basis of information theory (38] and multi-modal co-learning [39] Specifically, we prove that a generative model with an additional prior will not lower the upper bound of its performance on the downstream task. Note that we leave all proofs into the Appendix A due to the space limitation.
Definition 1 (Upper Bound of Model Performance). The performance upper bound of generative model, denoted by sup(P), is utilized to measure the maximun expected performance of generative model for downstream task p(w]c), where w is the generated content conditional on the different kinds of prior c. Formally, Sup(P) associated with kinds of prior C can be expressed as
sup(Pc) = ΣΣ p(c) max maxp(w(c))(w)).
CEC
where &i is the performance evaluator for given generated content w; is the complete set of differrnnt priors and C is a type of prior belonging the prior C.
Theorem 1. Given prior dataset 'D whose data samples comprises M types of prior C {CI...., C the distinct priors follow respective true distribution pl pCC; (.) Let c₁ be a sam- ple drawn from the distribution, i.e., C; p( ((C.))) ). A generative model with an additional rype of prior will not lower the upper bound of model performance sup(P).
Remark 1. Theorem [ esstablishes that introducing additional priors cannot reduce a generative model's 's performance upper bound, while decreasing its entropy. Consequently, integrating combina- torial optimization structural priors into LLMs dues not degrade their performance in generating code for solving CO problems.
Definition 2 (Performance- Enhancing Prior). Assume a type of prior C can boost the performance of generative model compared to the one without the prior, then C is the performance--nhancing prior to the generative model. It can be formally expressed as
Ew f w", plww' [c) Deec > plw"lc)l(w (eee(())))))))))) DeEe)HC)
(5)
where w* arg max pl w/ c) (w)(()))))))))))
Theorem 2. If prior Cpe is performance gerfrmnnnceeehhaciing prior, a generative model neglecting prior Ope will decrease the upper bound of model performance. can be expressed as
sup(Peu(C..) < sup(Pe)
Remark Theorem demonstrates that generative models equipped with perfornance-enhancing priors achieve superior performance relative to their prior-free counterparts. Specifically, the structural prior serves as such performance-enhancinn prior for LLMs in code generation tasks targeting CO problems, which is empirically validated through our comprehensive experiments.
5 Experimental Evaluation
To empirically evaluate the efficacy of our proposed STROMP in solving combinatorial optimization problems, we conduct extensive experiments across two fundamental CO problem classes: mixed- integer linear programming and Boolean satisfiability, evaluated on over nine benchmark datasets. We benchmark our approach against five well-established baselines encompassing both neural optimization methods and contemporary -.bse approaches. We aim to answer the following research questions:

---

Research Questions
Does the proposed STRCMP identify superior algorithmic implementations compared to existing algorithm discovery approaches?
RQ1:
RQ2:
Does the proposed composite model effectively reduce computational overhead in existing algorithm discovery frameworks?
RQ3: Does the structural prior benefit the generative model in solving combinatorial opti- mization problems?
5.1 Settings
Baselines. We evaluate our framework against two categories of baselines: neural combinatorial optimization methods and LLM-based evolutionary code optimization frameworks, covering mixed- integer linear programming (MILP) and Boolean satisfiability (SAT). More details of baselines and used backend solvers can be found in Appendix
Neural Combinatorial Optimization: For MILP, we compare with the seminal work L2B [14), which employs graph convolutional networks for variable selection to replace the strong branching policy, and HEM [5]]]]]]]] [6], a hierarchical sequence model for cut selection in branch-and -bund
solvers. For SAT, we include NeuroSAT [40], message- passagg-passing neural network trained with single-bit supervision for SAT solving.
While numerous LLM- evolutionary code optimization approaches exist for combinatorial optimization, we specifically compare with methods specialized for SAT and MIIP: AutoSAT (2 and L.M44olver (30). AutoSAT leverages L.MSs automate heuristic optimization in SAT solvers, minimizing manual intervention. L.M4Solver integrates LLMs with multi-objective evolutionary algorithms to automatically design effective diving heuristics for MILP solvers
Evolutionary Code Optimization:
Dataset. We perform the empirical evaluation over ten widely-used benchmark dataset for SAT and MILP respectively. More details and statistics of the used datasets can be found in Appendix
Mixed-integer linear programming (MILP): The datasets for MILP solver evaluation contain three difficulty tiers [15] 16] 30]: (1) Easy features synthetic benchmarks (Set Covering
Maximum Independent Set [2]. Multiple Knapsack
(33) generated using protocols from [44 45
(2) Medium includes MIK [46] and CORLAT [4): (3) Hard contains the Google-inspired Load
Balancing problem and the industrial-scale Anonymous problem [48]
Boolean satisfiability (SAT): The dataset comprises two sources: SAT Competition problems 49 and automatically generated instances via Picat [29]. SAT Competition data includes Profitable- Robust- Product (PRP) and Chromatic- of the-Plane (CNP) problems, while Picat- generated data contains CoinsGrid and Zamkeller instances. We adhere to the generation
Robust-Product
protocol established in 29
Metrics. To evaluate the effectiveness of the proposed framework, we analyze solving time to optimality solution quality attainable within fixed time budget. For solving efficiency evaluation, we measure the number of iterations or training steps required for convergence. Specifically, for MILP domain, critical metries include solving time and primal-dual (PD) integral which widely used in benchmarking the MILP solvers [15 16 [4]. For SAT domain, key metrics encompass solving time, PAR-2, and number of timeout frequently measured in evaluating SAT solvers 22 40)
Metrics such as solving time, PD integral, number of timeout, and PAR-2 are minimized through optimization. More details of the used metrics are presented in Appendix
5.2 Implementation
The proposed composite model comprises two components: a GNN and dinucture-prior-aweee LLM. We implement the GNN using graph convolution operators from torch_geometric, structured with three sequential convolutional layers terminated by global mean
Model Architecture.
Forr fair comparison, we slightly adjusted LLM4Soolve''s optimization focus from diving heuristics to cut selection for MILP solver.
7

---

CoinsGrid
AutoSAT
HEM
EasysAr
STACMP
losdbalancing
knaosack
LLM4Solver
STRCMP (DPO Only.
STRCMP (SFT Only)
STRCMP
STRCMP (DPO Only)
STRCMP (SFT Only)
Zamkeller
(a) PAR-2 in SAT domain
(b) PD integral in MILP domain
Figure 3: Optimization performance over different CO domains. Aligned with 29), normalize value-min each benchmark's s indicator values using mxmma=mmnn) where value represents the method's measured indicator, with min and mar denoting respectively the minimum and maximum values observed during evaluation. A larger shaded area corresponds to superior performance.
pooling. We adapt the LLM component based on Quen2. (wen2.5-Codeds -eee---I-IInuuttoo model through modifying its architecture, forward propagation dynamics and inference paradigm. Comprehen- sive implementation details including hyperparameter configurations, adaptations, and software dependencies provided in Appendix B. and B.2
Training, Inference and Used Hardware. We first train Nommin--ppecfii GNNs for SAT and MILP problems using aforementioned benchmark dataset. The GNNs are trained for three epochs on SAT instances and four epochs on MILP instances, followed by conducting post-training of the adapted LLM with specialized corpus. All post-training data is collected via queries to Qwen2. 5 IB-nstrrctt,,,,, aligned with the model used in the post training. The adapted LLM undergoes three epochs of post training per domain. Both GNN and LLM selecting optimal checkpoints based on validation prediction loss. We then integrate the composite model (i.e. the trained GNN and adapted LLM) into EA-based framework discover solver-specific algorithm configurations optimized for training instances. Finally, we evaluate the performance of identified algorithms held-out test sets. All experiments conducted on hardware platform with dual AMD EPYC 9534 64-core processors @ 2.45GHz and two NVIDIA H800 80GB GPUs connected via PCIe. More training specifics and data curation are detailed in Appendix B.I and B.2 respectively.
5.3 Results
Optimization Performance (Answer to RQ1). The
Table 1: Optimization performance result w.r.t. Number of Timeout between differ- ent methods over SAT domain.
comparative optimization results are presented in Fig-
ure 3 and Table [ ("CGD" and "ZAM" denotes Coins- Grid and Zamkeller dataset respectively) with respect
Compared Methods
Number of Timeout (L)
primary objective metrics (i.e. PAR-2 and Number of Timeout for SAT and PD integral for MILP domains). Comprehensive results for all evaluation metrics provided in Appendix G.T). As evidenced in Figure 3 and Table I. our STRCMP with various post-training vari- ants consistently matches or exceeds all bascline perfor- mance across both SAT and MILP domains. Specifically for SAT, STRCMP demonstrates universal superiority over its closest counterpart AutoSAT, particularly achieving significant reductions in terms of timeout (77.8% on Zamkeller: 18:4; 66.7% on PRP: 9-+3) and solving time (on PRP: 22967 seconds - 146 seconds; on Zamkeller: 20772 seconds - 6929 seconds). On MIL.P benchmarks, STRCMP maintains strong performance parity with NCO methods L2B/HEM and its direct competitor LLM4Solver. These
CNP CGD PRP
ZAM
AutoSAT 29
16
18
EasySAT
32
25
50
18
NeuroSAT 40
44
18
46
29
STROMP
17
STRCMP (DPO Only)
16
STROMP (SFT Only)
33
16
45
4
STRCMP w/o GNN
32
16
44
14

---

empirical findings conclusively address RQI: STRCMP successfully identifies superior algorithmic configurations compared existing strong baselines.
Efficiency Improvement (Answer to RQ2). Next, assess the efficiency of pro- posed STRCMP framework in discovering high- performance algorithms via iterative search for
STRCMP
STRCMP IDPO Only)
PAR-2
combinatorial optimization problems. The rep- resentative convergence comparison for SAT do- main are presented in Figures 4 More evalua- tions over other SAT datasets and MILP domain across additional metrics are provided in Ap- pendix G.2 Our experiments reveal that STRCMP achieves convergence significantly faster than existing evolutionary-basee algorithm discov- ery frameworks. Furthermore, the framework attains markedly higher-quality convergence points compared to baseline methods AutoSAT and LLM4Solver. Notably, STRCMP achieves stable convergence while AutoSAT exhibits persistent oscillations even after convergence. These findings validate that our proposed STRCMP substantially reduces computational overhead in evolutionary-basee algorithum discovery frameworks. Ablation Studies (Answer to RQ3). To address RQ3, we conduct comprehensive ablation studies on our composite model by systematically deactivating individual components and evaluating their impact optimization performance and computational efficiency. Representative results are shown in Figure 5 with full ablation studies detailed in Appendix G.3] Ánalysis of Figure 5 reveals that the structural prior provides measurable benefits for code generation in combinatorial optimization tasks: the STRCMP w/o GNN variant (lacking structural guidance) exhibits consistently inferior optimization performance compared to counterparts incorporating the prior: Furthermore, this variant demon- strates increased solution variability during algorithmic search iterations, potentially resulting in higher computational costs. Counterintuitively the full STRCMP model (with complete cost-training) does not uniformly outperform its ablations STRCMP (SFT Only) and STRCMP (DPO Only) across all benchmarks, suggesting underlying conflicts within the post-training data distribution. We plan to investigate this phenomenon in subsequent research.
10
20
30
50
60
Iterations
Figure 4: Convergence comparison (w.rt. PAR-2) between evolutionary based algorithm discovery frameworks on Zamkeller dataset SAT domain.
5.4 Further Analysis
Two-phase Training v.s. Joint Training? Besides the implementation of two-phase training strategy, we also design and implement 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 I.LM 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 (i.e., Zamkeller and PRP). All the experimental settings keep the same except
STREM (DPO Only) STREM (SFT Only)
STRCM wio ENN
STRCMP STRCMP (SFT Only)
6
STRCMP (DPO Only)
PAR-2
wio
3
Zankeller
Iterations
(a) PAR-2 SAT domain
(b) Convergence performance on Zamkeller dataset
Figure 5: Ablation studies in terms of optimization performance and convergence rate.

---

for the training method. The detailed results of this new training and testing are presented show in Table 7nd ii Appendix ! We can conclude the followings from these results: 1) The end-to-end joint training is extremely unstable compared to our proposed two-stage training method. Compared with the joint training. the loss curve of our two-stage training method is stable and close to zero at convergence. The GNN and LLM are trained together, which makes it difficult for the models to learn optimal parameters simultaneously: 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 much lower than our two-stage model on the two SAT datasets.
Insight of Training Strategy. 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, shown in Appendix []] Through the above thorough analysis and additional experiments, we can summarize our insights on selecting training strategy: 1) For "easy" datasets: 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 low cost, allowing SFT to quickly learn an effective policy. 2) For "hard" datasets: 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 a robust default, leveraging SFT for strong initialization and DPO for refinement and generalization.
Dependence on the Underlying LLM. To investigate how much does the performance of STRCMP depend on the underlying LLM, we focused our evaluation on the Llama2 and Qwen2 families of models, selecting representatives of varying sizes. We performed training and testing two datasets from the MILP domain and two from the SAT domain. The full result and analysis are presented in Appendix K It is important to note that the entire Llama2 family of models failed 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 highly capable code-generating LLM. From the results in Table T8 and Table [9] can draw the following conclusions: 1) The structural embedding from the GNN consistently and significantly contributes to the final performance; 2) STRCMP 's performance is robust, provided sufficiently capable LLM backbone is used, and 3) STRCMP 's performance is sensitive to the size of the LLM backbone, but this effect is problem-depeneet
code
6 Conclusion
We propose STRCMP, novel structure-aware LLM-based algorithm discovery framework for combi- natorial optimization problems. To our knowledge, this represents the first methodology that explicitly incorporates structural priors of combinatorial optimization problems into Mrr-vereee algorithm discovery, simultancously enhancing solution quality and computational efficiency. We validate the effectiveness of STRCMP through theoretical analysis and extensive empirical evaluations across SAT and MILP problems, demonstrating consistent improvements in both solving efficiency and solution optimality. Our framework offers principled foundation for future research integrating additional modal priors into LLMs for solving combinatorial optimization problems.
Acknowledgements
We thank all the reviewers and chairs for their reviews and valuable feedback. This work was funded by the National Key Research & Development Program of China (No. 2022YFB45001033, NSFC (No. 62506227, 62032008), STCSM (No. 252R 1402224, 2351 100100). Startup Fund for Young Faculty at SJTU (SFYF at SJTU, No. 25x010502616) and Aviation Key Laboratory of Science and Technology on Acrospace Vehicle. The corresponding authors are Bo Peng and Jianguo Yao.
10

---

References
[1] David M Ryan and Brian A Foster. An integer programming approach to scheduling. Computer scheduling of public transport urban passenger vehicle and crew scheduling, pages 269-280, 1981.
[2] Xijun Li, Mingxuan Yuan, Di Chen, Jianguo Yao, and Jia Zeng. A data-driven three-layer algorithm for split delivery vehicle routing problem with 3d container loading constraint. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 528-536, 2018.
[3] Bo Liu. Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Lim+ p: Empowering large language models with optimal planning proficiency, arXiv preprint arXiv:2304. 1477, 2023.
[4] Etienne De Klerk. Exploiting special structure in semidefinite programming: A survey theory and applications. European Journal of Operational Research, 201(1):1-10, 2010.
[5] Maria Chimmaa. Exact algorithuss for network design problems using graph orienta- tions. PhD thesis, Citeseer, 2011.
[6] Bruce Hendrickson. The molecule problem: Exploiting structure in global optimization. SIAM Journal Optimization, 5(4) 857, 1995.
[7] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290-2):405-421, 2021.
[8] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[9] Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint 1XX1:16111009400 2016.
[10] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driver framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10219-10227, 2022.
[11] Carlos Ansótegui, Britta Heymann, Josep Pon, Meinolf Sellmann, and Kevin Tiemney Hyper- reactive tabu search for maxsat. In Learning and Intelligent Optimization: 12th International Conference, LION 12, Kalamata, Greece, June 10-15, 2018, Revised Selected Papers 12, pages 309-325. Springer, 2019.
[12] Markus Kruber, Marco E Lübbecke, and Axel Parmentier. Learning when to use decompo- sition. In International conference on Al and OR techniques constraint programming for combinatorial optimization problems, pages 202-210. Springer, 2017.
[13] Pierre Bonami, Andrea Lodi, and Giulia Zarpellon. Learning classification of -ixee-integer quadratic programming problems. In International conference on the integration of constraint programmingg artificial intelligence, and operations research, pages 595-604. Springer, 2018.
[14] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Ex- act combinatorial optimization with graph convolutional neural networks. arXiv preprint arXiv:/906.01669 2019.
[15] Zhihai Wang. Xijun Li. Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. arXiv preprint 2xXv:2332.00024 2023.
[16] Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming. IEFE Transactions on Puttern Analysis and Machine Intelligence, 2024.
11

---

[17] Weiwei Sun, Shengyu Feng, Shanda Li, and Yiming Yang. Co-bench: Benchmarking lan- guage model agents in algorithm search for combinatorial optimization. arXiv preprint arXiv:2504.04310, 2025.
[18] Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le. Denny Zhou, and Xinyun Chen. Large language models as optimizers. arXiv preprini Stti::33090340000 2023.
[19] Yuxiao Huang, Wenjie Zhang, Liang Feng, Xingyu Wu, and Kay Chen Tan. How multimodal integration boost the performance of Ilm for optimization: Case study on capacitated vehicle routing problems. arXiv preprint 2rXiv:2403.01757 2024.
[20] Bernardino Comera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468 475, 2024.
[21] Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. arXiv preprint arXiv:2401.0200 2024.
[22] Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristics with reflective evolution. arXiv preprint arXiv:2402.0114552200 2024.
[23] Shunyu Yao. The Second Half. http:: https://ysynytth. http://yysyytt..ihhb... github So/The-Second-e
2025.
[24] Xijun Li, Qingyu Qu, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, and Jie Wang. Accelerating linear programming solving by exploiting the performance variability via reinforcement learning. 2023.
[25] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[26] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. Advances in neural information processing systems, 27, 2014.
[27] Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. theoretical and com- putational analysis of full strong-branching. Mathematical Programming, 205(1):303-336, 2024.
[28] Fei Liu, Yiming Yao, Ping Guo, Zhiyuan Yang, Zhe Zhao, Xi Lin, Xialiang Tong, Mingxuan Yuan, Zhichao Lu, Zhenkun Wang, et al. systematic survey on large language models for algorithm design. arXiv preprint arXiv:2410. 14716, 2024.
[29] Yiwen Sun, Furong Ye, Xianyin Zhang, Shiyu Huang, Bingzhen Zhang, Ke Wei, and Shaowei Cai. Autosat: Automatically optimize sat solvers via large language models. arXiv preprint arXiv:2402.10705, 2024.
[30] Yuyan Zhou, Jie Wang, Yufei Kuang, Xijun Li, Weilin Luo, Jianye HAO, and Feng Wu. Lim4solver: Large language model for efficient algorithm design of combinatorial optimization solver.
[31] Ernie Croot, Vsevolod F Lev, and Péter Pál Pach. Past and future of the cap set problem. arXiv preprint arXiv:2408.00 02328, 2024.
[32] Baoying Wang, Zhaohui Lin. Weijie Kong, and Huixu Dong. Bin packing optimization via deep reinforcement learning. IEEE Robotics and Automation Letters, 2025.
[33] Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
[34] Karla L. Hoffman, Manfred Padberg, Giovanni Rinaldi, et al. Traveling salesman problem. Encyclopedia of operations research and management science, 1:1573-1578, 2013,
12

---

[35] Ludo F Gelders and Luk N Van Wassenhove. Production planning: a review. European Journal of Operational Research, 7(2):101-110, 1981.
[36] Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002.
[37] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances Neural Information Processing Systems, 36:53728-53741 2023.
[38] Robert B Ash. Information theory. Courier Corporation, 2012.
[39] Amir Zadeh, Paul Pu Liang, and Louis-Philippp Morency. Foundations of multimodal co- learning. Information Fusion, 64:188 111118881131 193, 2020.
[40] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo Moura, and David Dill. Learning sat solver from single-bit supervision. arXiv preprint arXiv: wrXiv:1802.03685 2018.
[41] Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, pages 37-60. Springer, 1980.
[42] David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume Springer, 2016.
[43] Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke- Smith, and Karen Aardal. Learning to branch with tree mdps. arXiv preprint arXiv:220.111100 2022.
[44] Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com- binatorial optimization with graph convolutional neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[45] Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning. In Learning Meets Combinatorial Algorithms NeurIPS2020, 2020.
[46] Alper Atamtürk. On the facets of the mixed-integer knapsack polyhedron. Mathematical Programming, 98(1):145-177 2003.
[47] Carla P Gomes, Willem-Jan van Hoeve, and Ashish Sabharwal. Connections in networks: A hybrid approach. In International Conference Integration Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pages 303-307. Springer, 2008.
[48] Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Maxime Gasse, Ambros Gleixner, Aleksandr M, Kazachkov, Elias B, Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J, Maddison, Christopher Morris, Dimitri J, Papageorgiou, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scavuzzo, and Giulia Zarpellon. Machine learning for combinatorial optimization, 2021. URL https://wwrd ecole. a1 al/ //t////02//m/co/ 2t1/2//////444--c-pottttttt
[49] Tomas Balyo, Marijn Heule, Markus Iser, Matti Järvisalo, and Martin Suda. Proceedings of sat competition 2023: Solver, benchmark and proof checker descriptions. 2023.
[50] Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym- like library for machine learning in combinatorial optimization solvers. arXiv preprint arXiv:20/ 1.06069, 2020.
[51] Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and strong harncuue-harddees--eee aware baseline. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4414-4425, 2023.
13

---

[52] Ksenia Bestuzheva, Mathicu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doommalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, al. The scip optimization suite 8.0. arXiv preprint arXiv: 2e..12..0222 2021.
[53] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.133393 2020.
[54] He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[55] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Automated configuration of mixed in- teger programming solvers. In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques Constraint Programming, pages 186 202. Springer, 2010.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We validated the effectiveness the proposed method over 10 benchmarks compared with five baselines (please see Section 5.3 and Appendix G Meanwhile, we pro- vide the theoretical analysis to support our claim (please see Section 4.2 and corresponding proofs in Appendix A
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: we still discuss its limitation and future improvement room (see Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
we state all definitions, theorem and remarks. Besides, we provide the formal proofs to above theorems in Appendix A
Justification: In Section 4.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We present the methodology our proposed framework in Section 4.1 and then disclose all information related to model implementation, used dataset (all used dataset are publicly available and can be found referred papers), metrics interest and compared baselines in Section C.2 Besides,
provide all the details of above experimental elements. Please see Appendix B for model implementation details, Appendix [ for description of used dataset, Appendix E for metrics of interest, Appendix [C.1 for solver adoption, Appendix [ for details of compared baselines and Appendix [. for example prompts used in related experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code, data and learned model will be publicly available upon the accep- tance of the paper.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. htcc/publcc/guudeeee /etp///guudde//deeuuuuuiiiii /at////ooeSSsiiseeeeeeeeeeeeeeee ississssns ssionPolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We disclose all the details, including statistics of dataset, implementation of the proposed composite model, hyperparameters, etc. in Appendix C.2 and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Please the result in Appendix G
Guidelines:
17

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments are conducted hardware platform with dual AMD EPYC 9534 64-core processors @ 2.45GHz and two NVIDIA H800 80GB GPUs connected via PCIe. More training specifics and data curation are detailed in Appendix B. and B.2 respectively.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httph::t///// httpppis//////is...... httppppp........iiiccccccccelell
Answer: [Yes]
Justification: We confirm that the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
18

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper does not explicitly show the positive/negative societal impacts. But we still discuss its limitation and future improvement room (see Appendix (F).
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
We confirm that the baselines and datasets used in the paper all are publicly available.
Justification:
Guidelines:
19

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
20

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non standaadd components.
Please refer to our LLM policy for what should or should not be described.
21

---

A Proofs
Theorem 1. Given prior dataset DD whose data samples comprises M types of prior C (C,..., ..., the distinct priors follow respective true distribution pl D(C,)) Let c; be a sam- ple drawn from the distribution, i.e. C; p(Ca w). generative model with additional type of prior will not lower the upper bound of model performance sup(P).
Proof. Assume that there is generative model, which is associated with set of prior Cк [C,,.., Ck}. Its upper bound of model performance is denoted by sup(Pck). According to Definition sup(Pcx) ) can be expanded as
sup(Pcx) = Σ
p(c) CECK CEC
Σe
max w
Σ CECR CEC
Σ p(c) max Σ p(c, c/c.cc//w/cccc)00
CEEC;
E
CECK c;CC;
Σ p(ci, maxp(w/e,c.)00(
CECx cEC e,EC,
Σ
Σ p(c, c) maxp(w/c,c.)WWW
CECx
sup(Pex U(c.))
Above proof indicates that for given generative model with any additional modal prior C,, its performance upper bound sup(Pex U(C,)) is greater equal to its original performance upper bound sup(Pcx).
Theorem 2. If prior Cpc is a performance-enhrrenn prior, a generative model neglecting prior Ope will decrease the upper bound of model performance. It can be expressed as sup(Per(C,..)) sup(Pe)
(6)
Proof. If prior Ope is performance-enhancinn prior, according to Definition 2 we have (wxxp(/)c)B())occ.cco max ( (WW)eEC
Σ p(Cpe c) max ((wc)) (w)eec Epe
(8)
Then, according to Definition I sup(Pertc.... can be expanded as sup(Pov(c..)
Σ
Σ
p(c)
maxp(w/c)
CEeV/C,,
Substitute Eq. into Eq
9 to derive
sup(Per(C..))
Σ
Σ
p(c) maxp(w/ce@(w))
Cec CEC
Σ
Σ
p(c) Σ p(cpele) ( maxp(w/c)((()
CCc cEC
Epe
Σ
Σ
Σ
p(c)p(Cpel max pax
Cc Epe
(10)
Σ
Σ
Σ
p(cpe c) maxp(w/c)((w)
CECY/C cEC EpeECpp
= -Σ
p(c) max maxp(wlc))(w)
w
CEC
sPup(Pe)
22

---

B Implementation Details
B.1 Combinatorial Structure Extraction
Data Representation of MILP problem. A mixed-integer linear programming (MILP) problem is formally defined as:
min x, S.L. Az b. EER
23 EZ, Vjel,
(11)
where w E R", A R be RT le C (1,2, ,n specifies integer--onsstranned variables.
(- E (R {+o0))", and the index set (R R
To encode MILP instances, design bipartite graph g (CUV,E) with constraint-variabee interactions. The constraint node set C = {ci.-. ... Cm corresponds to rows of Az S b, where each node C; is associated with ID feature vector C, (b,) representing its right-hand side value. The variable node set V/ {e).... Un. represents decision variables, each equipped with a 9D feature vector 2 containing the objective coefficient wy, variable type indicator (integer/continuous)) and bound parameters 1,. új. Edges & = {eij) connect constraint G to variable iff ai # O, with edge features eij- (a.y) encoding the constraint coefficients.
Furthermore, mixed-ine intteger linear programming (MILP) instance is encoded as a weighted bipartite graph with feature matrices G = (C.V. V. E), where C, V. and E aggregate constraint node features Ca. variable node features v, and edge features Gij. respectively. The full specification of these features is summarized in Table 2 which preserves all structural and numerical information of the original MILP problem. Following standard practice, we utilize the observation function from Ecole (50) to generate these bipartite graph representations from MILP instances.
Table 2: Description of the constraint, variable, and edge features in our bipartite graph representation for MILP instance.
Tensor
Feature
Description
Constraint coefficient
Average of all coefficients in the constraint.
C
Constraint degree
Degree of constraint nodes.
Bias
Normalized right-hand-side of the constraint.
Objective
Normalized objective coefficient.
Variable coefficient
Average variable coefficient in all constraints.
Variable degree
Degree of the variable node in the bipartite graph representation.
Maximum variable coefficient
Maximum variable coefficient in all constraints.
Minimum variable coefficient
Minimum variable coefficient in all constraints.
E
Coefficient
Constraint coefficient.
Data Representation of SAT problem. A Boolean satisfiability (SAT) problem consists of variables I; and logical operators A, V, and m. A formula satisfiable there exists a variable assignment that makes all clauses evaluate to true. Following [51] we focus on formulas in conjunctive normal form (CNF)- - conjunctiin (A) of clauses, where each clause is a disjunction (V) of literals (variables I; their negations- -x,). Any SAT formula can be converted to equisatisfiable CNF formula in linear time. For example, (z) V -x2) A (I2 V -T3) represents a CNF formula with two clauses.
We utilize the Variable- CCause Graph (VCG) to represent SAT formulas. For a SAT formula, the VCG constructed with nodes representing literals and clauses, and edges indicating the inclusion of a literal in clause. The bipartite structure of VCGs ensures a one-to-one correspondence between CNF formulas and their graph representations. Formally, a bipartite graph G = (V, U V2, E) is defined by its vertex set Vi U V2 = (U1,..., u..). ) and edge set È C {(1), V2) |12, vy V). The vertex set is partitioned into two disjoint subsets V1 and V2, with edges restricted to connections between nodes in distinct partitions: E C {(0,, uy)lu, V1, 22 V2). In the context of VCGs, CNF formula with
23

---

14
Prediction Accuracy
12
Training Loss
0.6
0.4
100
120
Steps
Steps
Training Loss
(b) Prediction Accuracy
Figure 6: The convergence curve of training GNN for SAT domain.
literals and m clauses induces a bipartitioned graph where V1 = (4::..,, 4p) denotes the literal nodes and 1/2 {ei,,... Cm represents the clause nodes.
GNN Structure. The process using GNN extract combinatorial optimization problem can be formulated as:
(OJ)EE Σ J.p
(k+1) + fv(
(M)
Bv(v;
(R)
0, K -1) -
(12)
hg = Pool(ty (K)
(13)
where fy and are perceptrons for node representation; K represents the total number of times that we perform the convolution; Pool denotes pooling function that aggregates the embedding of each node in the graph, obtaining the structure embedding hy E Rd of the instance q. We denote the parameters of GNN as fG..
GNN Training. The loss function w.r.t. 0g is given below:
N
C
((0G)
Vice log Pe (clas),
(14)
N
exp (WT hg: + be)
pea (cl4s)
(15)
1== exp (W3 ha: + by)
where N is the total number of CO problems in the training procedure; C' denotes the number of classes; Vi E {0,1) 10 is the ground-true -ruth label of problem instance qı: and W, E Id b, RR 1.... ..., C") is the parameters of final classifying layer, which are also part of 0g..
Implementation & Training Details. Following the training protocol outlined above, we implement separate GNN models for the SAT and MILP domains using the dataset described in Appendix() Our GNN architecture consists of three convolutional layers (K 3) followed by global mean pooling operation. We leverage the graph convolution operator from the bearch_geomeetr embedding dimensions of 16, 32, and 64 for successive layers"] To capture global graph structure, we apply mean pooling to the final convolutional layer's node embeddings. For classification, softmax layer processes the pooled representation to produce final predictions. The models are trained using the loss function defined in (q.)14) with AdamW optimizer and cosine decay learning rate. T
library, with node
the training convergence for SAT instance classification (5-way classification task). Upon model convergence, compute structural prior representations for combinatorial optimization problem instances by processing their bipartite graph representations through the above GNN. The final convolutional layer's output embeddings are extracted the structural prior for each instance in the target domain.
For the MILP domain, we increase the final layer's dimensionality to 128 to account for higher problem complexity compared SAT domain.

---

B.2 Structure-Aware Code Generation
Data Curation, We begin by assembling& a curated collection of mathematical models for CO prob- lems, which are directly compatible with corresponding CO solvers, alongside their natural language descriptions. Subsequently, for each CO problem. we compile prompt that integrates the natural language description with specific code generation requirements. For instance, the code generation re- quirements may include details such as the function name, input/output parameters, expected function behavior, relevant background knowledge, etc. Illustrative examples for SAT and MILP domain are provided in Appendix L This prompt is then fed into an LLM to generate a code snippet. Note that to maximize the diversity of collected code snippets, we employ multiple LLM queries per prompt under high temperature settings to sample distinct candidate implementations. Each generated code snippet is evaluated by embedding it into the target solver and solving the corresponding CO problem, thereby obtaining performance metrics for the code snippet. Note that based on the principles of data curation, we collect the needed data via querying Qwen2. 5-Coder IBB-Istrruttor same as the model adopted in the following post training procedure.
Post Training. Specifically, we first curate the collected data by processing each CO problem Q; with its associated prompt z; and corresponding multiple generated code snippets yا 1,... M). These code snippets are systematically ranked based on previously obtained performance metrics to establish quality ordering. The highest-performing code-prompt pairs are selected to form the SFT dataset FSFT { vi }i Additionally, by leveraging pairwise comparisons extracted from the established ranking hierarchy, we derive the preference dataset DDPO = {(I;,, Ve, yt) 8t)re Jim where Yw: l/t are preferrea/dissrefeered code snippets. The training process can be formulated as follows:
LDOO Ee Me. Mw) B:D-DDO log (11n TTB2 (zm)
T82 (2)((r)
B BIn
(16)
Trer(Vin (z)
where a is the Sigmoid function; 3 is the hyperparameter that governs the trade-off between reward maximization and KL divergence minimization; Ter is the reference model trained on DSFT. Note that both Tee and To. updates only the parameter 0₁ of the composite model. Through above post- training, we obtain generative model capable of structure-aware code generation that simultaneously respects combinatorial optimization problems' inherent topological constraints and solver-specific syntactic requirements. Note that based on above principle of data curation and post- trainiinnnng, we collect 8k and 4k post-training instances for MILP and SAT instances respectively.
Implementation & Training Details. To implement the proposed composite model, we first design structure- ceaeeee-rrrr-wwrarr forward propagation mechanism and corresponding adapted inference framework based on the Qwen2. (5--ooor--77 7B- Instructor IB-IItrrcttntttttoooooooo model via the Transformery library.
Pritturr-rPio---wrree Forward Propagation Mechanism. Specifically, we process the input prompt through the tokenizer and the model's embedding layer obtain input_embedd which are then merged with structural feature vectors of combinatorial optimization problems extracted by the previous graph neural network.
First, we align the dimensionality of the combinatorial optimization problem feature vector h. E Rd with the hidden layer dimensions of the large language model via zero-padding. Given the text embedding shape embeds E R. Sx where the batch size, S is the sequence length (number of tokens), and H is the hidden dimension, the dimension-adapter feature vector is obtained as:
Hg Zero (addinggn, @b 0 0(H-d)) BxH
(17)
where ZeroPadding denotes zero sarroppading, and H. represents the padded graph structural feature vector. Subsequently, we fuse text and structural features between the embedding layer and decoder layer by prepending the graph feature vector to the text embedding sequence, forming a hybrid input:
E(embeds, H₂) = (CI.S + H ① embeds(1 (1 :] E TR (x(++))x
(18)
Here, emabeds is the inpul_embedd obtained from processing the textual prompt via the tokenizer and embedding layer, enabling the self-attention mechanism to jointly model textual semantics and graph structural features. A mask of all True values is constructed and merged with the attention_menn match the shape of the combined inputtembedss, ensuring H, participates in attention computation. Let the original attention <ecention_maskko shape be M {0, BxS; the merged atttention_mash becomes:
to
Min [M..; 1 B, M E (0, Bx(1+5)
(19)
"This model is available at http:://nngggiiiiieeo////eeweees In-strrue
25

---

DPO Rewards
4
SFT Loss
DPO Loss
0.6
3
0.75
2
0.4
0.50
0.2
0.25
0.00
200
400
600
200
400
600
Steps
Steps
Steps
(a) SFT Loss
(b) DPO Loss
(c) DPO Reward Accuracies
Figure 7: The convergence curve of post-training composite model for SAT domain.
The resulting phpput_embett and attention m_aak are then passed to the decoder layers and subse- quent model structures standard forward propagation.
Parameter-Efffiiiet Finetuning. We adopt LoRA for parameter-efficient fine-tuning on an autoregressive language model task. Key hyperparameters controlling the latent dimension of low-rank adaptation matrices; scaling factor lora_alpha = 32 for output normalization; dropout probability 0.05 for regularization; trainable low-rank adaptation layers injected exclusively into query (q_proj) and value (v (v_proj) projection submodules of the Transformer architecture while keeping other parameters frozen; bias parameters set to "none" to preserve original model biases. The adapted LLM is trained with AdamW optimizer and cosine decay leamingg rate. An illustrative training curve of the model for SAT domain is given in Figure 7
configured as: rank dimension 16
@ Adapted Inference Framework. Based on this modified architecture, we further adapt the LLM inference framework with structure-prior feature vector integration. During each autoregressive forward pass, logits are obtained via the feature-enhanced forward propagation, ensuring persistent influence of the structure-prior feature vector throughout the generation process rather than only affecting the initial output. We employ hybrid sampling strategy with Top-k set to 20, Top-p to 0.8, and repetition penalty 1.0.
C Baseline Details
C.1 Solver Adoption
MILP Solver. In all experiments related to MILP domain, we employ SCIP 8.0.0 (52) as the MILP solver backend-a leading open-source solver widely adopted machine learning research for com- binatorial optimization [44] 533. To ensure reproducibility and fair comparisons, all SCIP parameters remain at default values. We retain the solver's advanced features (e.g., presolve, heuristies), aligning our experimental setup with real-world applications.
SAT Solver. In all experiments related to SAT domain, parability with AutoSAT(29). The solver incorporates modern Conflict-Drive Clause Learning (CDCL) techniques including Literal Block Distance (LBD) heuristics, and VSIDS variable selection, and conflict-driven clause learning. All configurations (compiler versions, interfaces, time budgets) maintain parity with 29 for reproducibility.
EasySAT to ensure direct
C.2 Baselines Setting
C.2.1 Neural Combinatorial Optimization
The paper addresses the challenge of variable selection in the branch-and-bound (B&B) algorithm for solving mixed-integer linear programs (MILPss, where traditional expert-designed heuristics like strong branching incur prohibitive computational costs. To overcome this, the authors propose a graph convolutional neural network (GCNN) framework that leverages the natural bipartite
L2B [14.
EEsySAT: A Simple CDCL SAT Solver, http:////wwiiii....o//////eeeeep
26

---

graph representation of MILPs with variable and constraint nodes connected via edges representing their coefficients to learn branching policies through imitation learning. Key innovations include features, designing permutation- invariant sum-based graph convolutions with prenormalization layers to handle variable-sized inputs, and training via behavioral cloning of strong branching decisions using cross-entropy loss. All configurations take the default value used in [14] for fair comparison.
encoding MILP states as bipartite graphs with constraint/varian
HEM 15 [6]. The paper addresses the challenge of improving cut selection in mixed-integer linear programming (MILP) solvers by simultaneously optimizing three critical aspects: which cuts to select (PI), how many to choose (P2), and their ordering (P3), Existing learning- -based methods focus primarily on scoring individual cuts while neglecting dynamic cut count determination and sequence dependencies. To overcome these limitations, the authors propose a novel hierarchical sequence model (HEM) that leverages a two-level architecture: a higher-level policy predicts the ratio of cuts to select using tanh-Gaussian distribution, while lower-level pointer network formulates cut selection as a saaeenne-to-seuenee learning problem to output ordered subsets. The model is trained via hierarchical policy gradient optimization within reinforcement learning framework, where states encode MILP relaxation features and candidate cut characteristics, actions represent ordered cut subsets, and rewards correspond to solver performance metries like primal-dual gap integral. All hyperparameters take the default value used in [5 [6] for fair comparison.
NeuroSAT [40]. The paper proposes a message-passingg neural network (MPNN) to solve the Boolean satisfiability problem by training solely on binary labels indicating satisfiability. The key innovation lies in representing SAT instances as bipartite graphs where literals and clauses are nodes connected via edges, and leveraging permutation-invarie these graphs. NeuroSAT iteratively refines node embeddings through bidirectional message passing: clauses aggregate information from their constituent literals, while literals update their states based on connected clauses and complementary literals. Trained distribution of random SAT problems generated by incrementally adding clauses until unsat, the model learns to predict satisfiability via a cross-entropy loss on the final aggregated literal embeddings. Crucially, the architecture enforces structural symmetries (variable/clause permutation invariance, negation equivalence) and generalizes to larger instances and entirely unseen domains (e.g., graph coloring, vertex cover) at test time by simply extending the message-passing iterations, despite being trained only on small random n S 40 problems. All configurations of this algorithm take the default used in 44) for fair comparison. Note that since NeuroS AT is a prediction framework for Boolean satisfiability problem, it is meaningless to measure the solving time for this framework over the SAT instances. Besides, the ground- truth dataset used to train the NeuroSAT model is those SAT instances can be proved/solved within timelimit т. Thus, we only count the number predicted to be correct of AeuroSAT (this number must be less than the number of ground-truth labels). Then, the number of timeout for Ae is equal to the total number of test instances minus the number predicted be correct.
neural architectures to process
C.2.2 Evolutionary Code Optimization
AutoSAT [29]. The paper introduces framework that leverages Large Language Models (LLMs) to automatically optimize heuristics in Conflict-Driven Clause Learning (CDCL) SAT solvers. The authors address the challenge of manually designing and tuning heuristic functions in modern CDCL solvers, which is time- cone-conuuming and expert-dependent. Instead of generating solvers from scratch, AutoSAT operates within a modular search space comprising nine key heuristic functions (e.g.. branching, restart, and clause management) derived from an existing CDCL solver. The framework employs LLMs to iteratively refine these heuristics through two search strategies: a greedy hill climber (GHC) and a (1+1) Evolutionary Algorithm (EA), where LLMS generate candidate code modifications guided by performance feedback. All configurations of this algorithm take the default used in 29 for fair comparison.
LLM4Solver (30]. The paper proposes novel framework that integrates large language models (LLMs) with evolutionary search to automate the design of high-performance diving heuristics for exact combinatorial optimization (CO) solvers. The key challenge addressed is the inefficiency of traditional manual and learning- based approaches in navigating the vast, discrete algorithm space for CO solver components like diving heuristics, which require domain expertise and suffer from poor generalization. The core methodology leverages L.MSS as prior-knowledge-guicee to produce candidate algorithms encoded as interpretable score functions, while a derivative-fres evolutionary framework (single- or multi-objective) optimizes these candidates through iterative
generators
27

---

population-basee based search. The algorithm space is defined via 13 interpretable variable features, with LLMs enabling code-level manipulations during initialization, crossover, and mutation. We slightly adjusted L.M4Solver's optimization focus from diving heuristics to cut selection for MILP solver for fair comparison with previous work
[15 [6]. All configurations of this algorithm take the default
used in 15 16] for fair comparison.
D
Dataset Details
D.1 SAT Domain
Juromatic-Vumber-offttiee (CNP). This problem requires coloring graph vertices such that adjacent nodes have distinct colors.
Cooftabl--Robus-PPoodrece (PRP). This problem seeks robust production plans maintaining profitabilitty under uncertain/fluctuatinn conditions. The generation setting of PRP adhere to [29]
CoinsGrid. This problem, based on Tony Hurlimann's coin puzzle, involves arranging coins on a grid with row-wise, column-wise, and distance-based constraints. The generation setting of CoinsGrid
adhere to 29
Zamkeller. This problem requires finding a permutation of integers from 1 to n that maximizes differential alternations in subsequences divisible by integers follows 29
< k < n). Instance generation
Table 3: The statistical description of used SAT datasets. Const. and Var. stand for constraints and variables respectively.
Dataset
Size
Const. (mean)
Const. (std)
# Var. (mean)
# Var. (std)
CNP 150
261,260
352,379
8,798
8,893
CoinsGrid
78
1,116,972
1,068,009
154,828
148,571
PRP
80
2,120,983
1,346.344
317,635
201,185
Zamkeller
80
310,804
335,102
24.592
22.190
D.2
MILP Domain
Easy. The SCIP 8.0.0 solver solves MILP instances in the Easy dataset within one minute. This dataset comprises three synthetic problems: Set Covering [41], Maximum Independent Set [42). and Multiple Knapsack 43). We select these classes because: (I) they serve as standard benchmarks for MILP solver evaluation
44
and (2) they encompass diverse MILP problem structures encountered
we generate set covering instances (500 rows x 1000 columns), Maximum Independent Set instances (500-node graphs with affinity 4), and multiple knapsack instances (60 items, 12 knapsacks). For each dataset within this category, we generate 1,000 training instances and hold 100 instances as test set. Besides, we set the timelimit as 60 seconds for solving problem instances within this dataset.
in practice. Following
44
Medium. The SCIP 8.0.0 solver requires at least five minutes to solve this set of instances optimally, Following [54] 55 53), this dataset combines MIK [6) (MILPs with knapsack constraints) and
CORLAT 47 (real-world grizzly bear corridor planning in Northern Rockies). Each problem set partitioned into 80% training and 20% test instances. Furthermore, we set the timelimit as 120 seconds for solving problem instances within this dataset.
The SCIP 8.0.0 solver requires These d include Load Balancing from the NeurlPS 2021 ML4CO competition (48). Load Balancing instances model server task allocation under resource constraints. Same Medium dataset, each problem set in Hard dataset is also partitioned into 80% training and 20% test instances. Additionally, we set the timelimit 360 seconds for solving problem instances within this dataset.
Hard.
than one hour solve Hard dataset instances optimality.
MIK data be found at http:://wannuuu...oooooeoeeeoees knaaakkk 1 "CORLAT data is available at http://tthiicceee////iimaaaaaaat
All these data can be found at hhtp:s//www.coooe.////////oooooo
28

---

Table 4: The statistical description of used MILP datasets.
Dataset
# Constraints (mean)
Varaibles (mean)
Set Covering (SC)
500
1,000
Maximum Independent Set (MIS)
1,953
500
Knapsack
72
720
MIK
346
413
CORLAT
486
466
Load Balancing
64,304
61,000
E
Metric Details
E.1
Metries related to MILP
For fair comparison, our evaluation employs metrics aligned with HEM well-establisedd in the MILP community.
15 16
which are
Solving Time. For MILP instances solved to optimality within time limit T, measure the solver runtime & required to obtain certifiably optimal solutions. For those MILP instances that cannot be solved to optimality within time limit T,, utilize the following metrics.
Primal-Dual Gap. During the execution of MILP solvers, two critical bounds are maintained: global primal bound and the global dual bound. The global primal bound represents the objective value of the incumbent feasible solution, serving as the tightest upper bound for the MILP. The global dual bound corresponds to the minimal lower bound among all active nodes in the search tree, constituting the strongest lower bound for the problem. The primal-dual gap is defined as the absolute difference between these two bounds. In SCIP 8.0.0 [52] the initial primal-dual gap is initialized to constant value of 100.
Hhimal-Dual (PD) Integral. The primal-dual gap integral is defined as the area enclosed between the primal and dual bound trajectories during solver execution. Formally, given a time limit T, this integral is expressed as:
[ (w x; )it, ===
(20)
where w denotes the objective coefficient vector of the MILP instance; of represents the incumbent feasible solution time f, z corresponds to the tightest dual bound at time This metric quantifies the cumulative optimality gap over the solving horizon and serves as an established performance benchmark for MILP solvers. Notably, the primal-dual gap integral was adopted as the primary evaluation criterion the NeurIPS 2021 ML4CO competition (48).
E.2 Metrics related SAT
To ensure fair comparison, our evaluation adopts metrics consistent with AutoSAT 29 which are widely recognized in the SAT community.
Solving Time. For SAT instances that can solved/proved within a timeout limitation т, we record the running time t of SAT solver solving/proving these instances. For those SAT instances that cannot be solved/proved within timeout limitation т, we measure the two following metrics.
Number of Timeout. Given timeout limitation and set of SAT instances, we record the number of SAT instances that cannot be solved/proved within 7 for different compared methods. The 7 is set as 5000 seconds, same as [29].
Penalized Average Runtime with factor of score (PAR-2). PAR-2 a standard evaluation metric in SAT solver competitions and benchmarks, employed to assess and compare solver performance under incomplete executions or timeout scenarios. Specifically, the PAR-2 score aggregates runtime across test instances as follows: 1) For solved instances, record the solver's 's runtime; 2) For instances where the solver exceeds the timeout limitation т, assign twice the timeout threshold 7 as the penalty-thir this is why we call this metric PAR-2; 2; 3) Compute the average across all instances by summing these values and dividing by the instance count. Lower PAR-2 scores indicate better overall solver efficiency.
29

---

Intuitively, consider a benchmark set comprising n SAT instances. Let E, denote the solver's runtime on the i-th instance. The PAR-2 score is formally defined as
PAR-2
(21)
t=1
where
tz: if T;
4
(22)
2T, if > or the solver fails return solution.
F
Discussion
End-to-End Training, In this work, we adopt a two-stage training procedure for our composite model: first training graph neural network (GNN), then training large language model (LLM) conditioned on the frozen GNN embeddings. This approach stems from our empirical observation that end-to-end joint training of the composite model presents sigmificant optimization challenges. We hypothesize that this limitation could be mitigated by exploring more sophisticated GNN architectures or developing enhanced alignment strategies between the GNN's structural representations and the LLM's semantic space.
Explore Domaif-specific Distributional Discrepancies. In our ablation studies, empirical results reveal that the full STRCMP model (with complete post-training) underperforms relative to its variants STRCMP (SFT Only) and STRCMP (DPO Only) across benchmark datasets, suggesting potential con- flicts between optimization objectives during multi-stage post-training. This observation motivates future investigation into domain-spect speciifc distributional discrepancies that may arise from the hetero- geneous nature of combinatorial optimization problems, which could inform improved alignment strategies for cross-domain post-training protocols.
Interpretability of the generated code functions scale with the increasing complexity of the CO problem. We fully acknowledge that while code generation enhances transparency relative 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 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-procest enhancing them with annotations aid human understanding. For now, we believe STRCMP strikes valuable balance, advancing interpretability over NCO methods while laying the groundwork for further improvements.
or
Incorporating Additional Modal Priors. In this study, we focus specifically on integrating graph structural priors into LLM-based algorithm discovery for combinatorial optimization problems. While current methodologies rely on human expertise to predefine target components, we posit that LLMs' context-aware capabilities could assimilate additional modal priors (e.g., dynamic constraint patterns or solution quality metrics) to enhance combinatorial optimization moblemm-ollving performance. Future extensions may enable LLMs autonomously identify computational bottlenecks through techniques such as runtime complexity profiling or constraint violation pattern analysis, thereby prioritizing component optimization.
30

---

G
Additional Experimental Results
G.1
Optimization Performance Result
Table 5:
The optimization performance result w.r.t. PAR-2 score between different methods over SAT
domain.
PAR-2 Score (J)
Compared Methods
CNP
CoinsGrid
PRP
Zamkeller
AutoSAT
644.72
1098.69
639.34
807.75
EasySAT
649,42
1595.75
2000
829.38
STRCMP
624.15
1124.09
1804.46
270.62
STRCMP (DPO Only)
643.45
1098.69
482.92
265.94
STROMP (SFT Only)
643.23
1098.47
1837.86
227.69
STRCMP w/o GNN
645.67
1098.34
1820.38
646.12
Table 6: The optimization performance result w.r.t. Solving Time between different methods over
SAT domain.
Solving Time (1)
Compared Methods
CNP
CoinsGrid
PRP
Zamkeller
AutoSAT
32472
19158
22967
20772
EasySAT
32942
26064
50000
21810
STRCMP
31415
18971
46223
7990
STROMP (DPO Only)
32345
19158
21146
7765
STRCMP (SFT Only)
32323
19151
46893
6929
STRCMP w/o GNN
32567
19147
47019
17014
6.0
STRCMP
STRCMP (SFT Only)
STRCMP (DPO Only)
PAR-2
5.5
AutoSAT
5.0
0
10
20
30 Iterations
40
50
60
Figure 8: Convergence comparison (w.rt. PAR-2) between evolutionary-basee based algorithm discovery frameworks on PRP dataset of SAT domain.
31

---

G.2
Convergence Comparison Result
PAR 2
PAR
10
20
30
40
50
10
20
30 Iterations
40
50
60
Iterations
(a) CNP
(b) CoinsGrid
STROMP
4.5
STROMP
Solving Time
STROMP ISFT Only)
Solwing Time
STROMP IDPO Only)
Only)
AutuSAT
3.5
10
20
40
50
60
10
20
30 Iterations
40
50
Iterations
(c) CNP
(d) CoinsGrid
-15
3.0
Solving Time
STRENP EITT anl)
Solving Time
STRCMP On
STRCMP IDPO Onyl
STRCMP IDPO Ony)
AutesA!
AutosA
2.0
2.4
20
30
lterations
(c) PRP
(f) Zamkeller
Number of Timeout
S STREMM
Number of Timesoat
STREMP SIRCCP 5PTT Onl)
S S/REHH Gir Only
STRCMP IDPO Only)
STRCHP IDPO Only
AUcoSAT
AuTo
20
50
10
20
30 Iterations
50
Iterations
(g) CNP
(h) CoinsGrid
Number of Timeout
3.0
STREMP
Numbbr of Timoout
3.0
STRCMP STREMP (SFT on
2.8
STREMP GTTT (nl)
STRCHP IDPO
STRCMP IDPO only)
2.4
2.2
10
20
30
10
20
30
40
50
[ter lerations
Iterations
PRP
(i) Zamkeller
Figure 9: Convergence comparison (w.r.t. PAR-2, Solving Time, and Number of Timeout) between evolutionary-basse based algorithm discovery frameworks on SAT domain.
32

---

2.5
0.8
2.5
30
30
Reratiors
Itorations
(a) MIK w.I.t PD Integral
(b) MIK w.r.t. Solving Time
STRCC0
STRCK
STTCKP
STR2M
STACK
STRCK BPD
2.2
0.5
0.54
Berwtooe
Beeahior
(c) MIS W.I.L PD Integral
(d) MIS w.r.t. Solving Time
STRCHO
STIC 15T Only
STRCI ETT 011
STROM
STRON Only
STROK EDTO D-I.
Liitcker
50
Rorations
Itorations
(c) CORLAT w.r.t PD Integral
(f) CORLAT
$18C89
STAOMP 1PRt Onb1
STROP ONG
S1RCMP
STROP (aT only
STROP DNY
3.5
1.0
2.5
30
30
50
Rerations
Borations
(g) Knapsack w.r.t PD Integral
(h) Knapsack w.r.t. Solving Time
STATEE (MPT Oeb1 STAOOP 1r0 Deg.
STREE JUPT O1ly
2.5
10
30
40
50
10
30
50
Rerations
Iterations
(i) Set Cover w.r.t. PD Integral
(i) Set Cover w.r.t. Solving Time
Figure 10: Convergence comparison (w.rt. PD Integral and Solving Time) between evolutionary- based algorithm discovery frameworks on MILP domain.
33

---

G.3
Ablation Studies Result
STREMP
STREMP
STRCMP (SFT Only
STROMP (SFT Only)
S IRCHY (DYO Only)
STRRCMY tD Only)
84R.2
STRCMP yao CNN
PAR
STRIMP we GNN
4-
Iterations
iterations
(a) CNP
(b) CoinsGrid
SIRCMP
STRCMP
Solving Time
STRCMP CSFT Onlv)
Solving Time
STRCMP (SFT Onl)
5.0
SICCC 1pо trlyy
STRCMP yan GNN
3.0
50
30 Iterationn
Iterations
(c) CNP
(d) CoinsGrid
3.0
STREMP
STRCMP
Solving Time
STNCMP (FF Onl)
Salving Time
3.0
STRCMP (SFT
2.0
STREMP pro
STRCMP ppo Only)
STRCMP GNN
2.5
STACMP GNN
2.6
10
20
30
4.0
10
20
30 Iterations
40
50
60
Iterations
PRP
(f) Zamkeller
Number of Timeeut
STROMP
Number of Timeout
STRCMP (SFT Only
ONY)
STREMP
Only
STRCMP GNN
STROMP wwo GNN
10
20
40
50
10
20
40
50
Iterations
Iterations
(g) CNP
(h) CoinsGrid
Number of Timeoit
3.0
STREMP
Number of Timcout
3.0
STROMP Onl)
STROMP
2.5
2.6
2.4
2.2
10
20
30
40
10
20
30
40
50
60
Iterations
Iterations
PRP
(j) Zamkeller
Figure 11: Ablation studies (w.nt. PAR-2, Solving Time, and Number of Timeout) during algorithm search on SAT domain.
34

---

H Experiment Statistical Significance
lirrations
Earations
(a) CNP
(b) CoinsGrid
STRCMP
STROAP SITO
STAONO IPP Deb1
KAGSKT
STACKP
STACHI GeT
STROMP (OPO Day!
ASSSAT
6.0
4.5
10
23
30
55
10
10
20
30
53
(c) PRP
(d) Zamkeller
STROM
STROMP GFT Oeby
STREMP 1OTO Oey!
AUSSAT
Soleing
10
20
30
50
60
10
20
50
(c) CNP
(f) CoinsGrid
STROMP
STNCUP SIT 040
STROMP IOPO ONET
3.0
1.0
10
23
30
55
10
10
20
50
50
60
gg) PRP
(h) Zamkeller
STROM
STROME GFT Oely
STREMP 1070 Ony!
AMSSAT
10
20
30
40
55
63
10
20
50
(i) CNP
(j) CoinsGrid
STROM EFT 040
STROM Debl
NISSAT
2.50
1.25
1.00
TE Laration
Eerations
(k) PRP
()) Zamkeller
Figure 12: Convergence comparison with variance statistic (w.rt. PAR-2, Solving Time, Number of
Timeout) between evolutionary-based algorithm discovery frameworks on SAT domain.
35

---

I Comparison between Two-stage training and Joint End-to-End Training
The detailed results of this new training and testing are presented show in Table and Table can conclude the followings from these results:
We
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 challenging optimization landscape where single learning rate is ineffective for both components, leading to unstable convergence (even with many more training steps) as shown in Table 7 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 Figure 7 Appendix). The GNN and LLM are trained together, which makes it difficult for the models to learn optimal parameters simultaneously.
The model exhibits poor performance when tested 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 two-stage model the two SAT datasets, shown in Table g
Table 7: The Training Loss of End-to-End Joint Training
End-to-End DPO Loss
End-to-End SFT Loss
Training Step
100
0.54
1.64
200
0.60
1.53
300
0.26
1,44
400
0.43
1.28
500
0.56
1.14
600
0.13
1.04
700
0.42
0.98
800
0.29
0.88
900
0.30
0.86
Table 8: The Jointly Trained Model's Performance over Two SAT datasets w.r.t. PAR-2 Score
Dataset Two-Stage Joint End-to-End
Zamkeller
270.62
751.34
PRP 1804.46
2092.71
36

---

Experiment on the Training Strategy
To provide clearer and more comprehensive answer, we offer a detailed analysis focusing on dataset complexity and the iterative optimization behavior of our proposed method, stremp, and its variants.
Dataset Complexity. The complexity of combinatorial optimization problems can be characterized by various metrics. Drawing from established literature, focus several key graph-based metrics-Moddularigg Density, and Clustering provide quantitative perspective on the structural complexity of the datasets used in our experiments. While absolute, higher values in these metries generally suggest more intricate problem structure and complexity. The problem sizes are detailed Appendix of our manuscript. The statistics for the MILP and SAT datasets are presented below.
Table Data Complexity of MILP Dataset
Dataset
Modularity
Density
Clustering
setcover
0.18
0.07
0.34
knapsack mis
0.07
0,04
0.36
0.48
0.01
0.02
mik
0.11
0.23
0.30
loadbalancing
0.49
0.01
0.01
Table 10: Data Complexity of SAT Dataset
Dataset
Modularity
Density
Clustering
CNP 0.8181
0.0016
0.2012
CoinsGrid
0.9306
0.0005
0.5377
Zamkeller 0.7383
0.0004
0.5659
PRP 0.8865
0.0002
0.5429
Iterative Behavior STRCMP and Variants. To provide a clearer picture, we have compiled tables showing the non-smoothed, iteration-be -uattionbb--teratioon performance on both MILP and SAT datasets. We employ an early stopping strategy where the search terminates if no performance improvement observed within three consecutive iterations. Hence the total iteration number of different method will be varied. These results illustrate the performance trajectory (Primal-Dual Integral and PAR-2 score) of STRCMP against its SFT-only and DPO-only ablations, as shown in the following tables.
Table 11:
The Performance v.s. Iteration Result w.r.. Methods over corlat Dataset
Primal-Dual Integral between Different
Iterations
L.L.MSrlvver
STRCMP
STRCMP (SFT Only)
STROMP (DPO Only)
STROMP w/o GNN
9939.48
8750.84
6880.25
7159.24
10325,77 10435.85
9860.20
8889.19
7235.31
6870.31
9
9673.47
8836.85
7364.47
6881.48
10404.27
12
9900.06
6932.57
Table 12: The Performance v.s. Iteration Result w.r.t.
Primal-Dual Integral between Different
Methods over mik Dataset
Iterations
LLM4Solver
STROMP
STRCMP (SFT Only)
STRGMP (DPO Only)
STROMP w/o GNN
535.04
478.08
394.25
451.48
492.96 494.24
499.60
455.18
421.44
434.09
15
470.48
450.72
408.55
431.42
481.97
21 466.45
438.51
372.12
27
471.22
448.31
380.74
37

---

Table 13:
The Performance v.s. Iteration Result wrr..
Primal-Dual Integral between Different
Methods over loadbalancing Dataset
Iterations
LLM4Solver
STRCMP
STRCMP (SFT Only)
STRCXP (DPO Only)
STROMP w/o GNN
1942.27
1881.74
2125.22
2193.62
1910.53 1905.49
9
1885.31
1878.52
2065. 61.61
2245.97
15
1867.71
1859.14
205 1.36
Table 14: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over
CNP Dataset
Iteration
STRCMP
STRCMP (SFT Only)
STRCMP (DPO Only)
3
49931
49395.1667
48963.5
15
60433.3333
59101.3333
57184
51
57108. 1667
51935.6667
57688.67
57
55257.8333
52890.1660 1667
57352
75
48779.5
78
47443
Analysis and Insights. From the iterative performance results, we draw two primary observations:
SFT-only models often converge faster terms of iteration count but may stabilize a suboptimal performance level. This suggests that while SFT is effective at rapidly imitating strong solutions, it may overfit to the strategies present the initial dataset, leading to premature convergence in local optimum.
OPO-inclusive models (DPO-only and SFT+DPO) demonstrate capacity for continued improve- ment 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 more nuanced understanding of what constitutes better search trajectory. allowing escape local optima and discover superior solutions.
Based on these observations and the complexity analysis, we can summarize our insights on selecting training strategy:
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 low cost, allowing SFT to quickly learn an effective policy.
For "hard" datasets (e.g., large-scale, dense, complex structure, intractable): We strongly rec- ommend DPO- 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 navigating the vast and complex search spaces of these challenging instances.
@ For medium complexity datasets, the choice 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 strong initialization and DPO for refinement and generalization. However, we acknowledge that determining the optimal blend is significant challenge. The task-specific training of large models has not yet fully clarified the precise relationship between SFT and one is definitively superior. or how their data should be optimally combined. We consider this an important open problem for the field.
38

---

Table 15: The Performance v.s. Iteration Result w.r.t PAR-2 Score between Different Methods over
CoinsGrid Dataset
Iteration
STRCMP
STROMP (SFT Only)
STRCMP (DPO Only)
3
60376
59444
59735.67
9
65177.67
65305
70214.83
30
58516.83
62026.17
61296.83
33
58091.67
62460.83
61622.17
57
56775.17
53737.67
60
58212.83
Table 16: The Performance v.s. Iteration Result w.r.t. PAR-2 Score between Different Methods over
PRP Dataset
Iteration
STRCMP
STRCMP (SFT Only)
STRCMP (DPO Only)
3
53808.17
53696.33
54977.5 54462.5
9
54523
56456.67
39
53015.83
55141.67
52635
42
50812.5
53459
52731.67
66
52701.5
53627
51030
69
50352.33
87
49281
Table 17: The Performance v.s. Iteration Result w.r.t PAR-2 Score between Different Methods over
Zamkeller Dataset
Iteration
STRCMP
STRCMP (SFT Only)
STRCMP (DPO Only)
3
45613.5
44988
45427
6
56487.17
47457.5
51138
27
56511.5
49499.1 17
44826.5
30
54933.67
50914
45185.67
51
51801.33
53002.83
42444.17
54
51900.67
49976.5
38346.17
72
41710
75
36365
39

---

K Dependence on the Underlying LLM
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.
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 by being unable to generate syntactically correct, executable code. Similarly, the smaller Qwen2 models (0.5B and 1.5B) were also unable produce viable code for the solvers. This underscores the complexity of the task, which requires highly capable code-generating LLM. From the results in the tables, we can draw the following conclusions:
Table 18: The Performance of STRCMP w.r.t. over MILP Domain
Primal-Duu Integral with Varied-Size Backbone LLM
STROMP
STRCMP w/o GNN
Dataset mik setcover
Qwen2(0.5B)
Qwen2(1.5B)
Qwen2(7B) 269.68
Qwen2(14B)
Qwen2(7B)
Qwen2(14B)
233.56
292.41
262.74
34.02
34.29
34.06
34.24
Table 19: The Performance of STRCMP w.r.t. PAR-2 Score with Varied-Size Backbone LLM over SAT Domain
STRCMP
STRCMP w/o GNN
Dataset PRP
Qwen2(0.5BB)
Qwen2(1.5B)
Qwen2(7B) 470.63
Qwen2(14BB 414.12
Qwen2(7B) 500.00
Qwen2(14B)
455.09
7amkeller
355.3
127.7
635.75
308.30
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 crucial inductive bias that guides the LLM toward better solutions, regardless the LLM's scale.
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 comprehend the task and generate valid code, the performance is stable across capable models of different sizes.
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 L.LM from 7B to 14B parameters yields 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.
40

---

L Prompt and Corresponding Responses
Prompt of data curation for SAT domain (adapted from AutoSAT (29])
# Description of the role duty You are SAT solver researcher trying to write the bump_var to help SAT solver escape from local optimum.
Description of the task goal Your goal is to improve bump_vay var for the SAT solver, after reading and understanding the <key code> of SAT solver below.
# Description of the example codes
As an example, format of bump_var var can be:
77 start
void Solver: bump_ (int var, double coeff)
// end
To replace original code:
TTT
77 start
void Solver: :uump__buumvvee (int var, double coeff)
if ((activity [var] +s var_inc coeff) > 1e100) // Update score and prevent float overflow for (int i 1; var var_inc *= 1e-100;}
vars; i++) activity[i] 1e-100;
if (vsids. inHeap vsids. v (
// update heap
// end
Description of the tips to the task
Tips:
1) Your bump_var code must start with "/// start!" and end with 11// !nd
2) Feel free to unleash your creativity and provide your improved and correct code. (Pay attention to correct namespace.)
3) Your bump_var code must be different from original codes.
4) You can only modify the current bump_va var and use the existing external variables (e.g. variables that defined in Solver).
5) You cannot add new external variables outside the bump_
6) The SAT problems that the SAT solver needs to solve have the structural characteristics.
# The whole code of target solver <key code> of SAT solver is:
nan
// Omit the key code of SAT solver here for space limitations. unm
Take deep breath and think it carefully. Then respond in correct format!
41

---

Collected Response to above Prompt
// start
void Solver: : bump- var (int var, double coeff) {
// Update the activity score with dynamic coefficient based on
+ LBD
double dynamic_coeff coeff (1.0 (clause_DB. back () .1bd
10.0));
if ((ativvtyy [var] += var_inc dynamic_coeff 1e100) { + // Update score and prevent float overflow for (int i i <= vars; it+) activityli) *= 1e-100; var_inc *= 1e-100;
}
if (vsids. (vsids.inHesl inHeap(var) vsids. (
// update heap
// Implement decay factor for activity scores based on the number of conflicts
static conflict_count 0; conflict_count+:::
if Cconflict_coum % 1000 0) {
for (int i = 1; i <= vars; i++) activity[i] *= 0.95; // Decay activity scores
}
}
// end
42

---

Prompt of data curation for MILP domain (adapted from previous work 15 30J
Description of the task background
1. Introduction to MILP: Mixed Integer Linear Programming (MILP) is mathematical optimization or decision making methodology for mathematical planning problems in which the objective function and constraints are linear and some of the decision variables are restricted to integers.
2. MILP Defimition: mixed integer linear programming (MILP) problem has the following elements:
2.1) linear objective function fx, where is column vector of constants and is a column vector of unknowns.
2.2) Boundary and linear constraints, but no nonlinear constraints.
2.3) Restrictions on certain components
so that they must
have integer values.
3. Cutting Planes Definition: cutting planes are additional linear inequality constraints added to the MILP problem. These inequalities attempt restrict
feasible domain the relaxation so that its solution is closer to an integer.
4. Cutting Plane Algorithm: The Cutting Plane method solves the MILP problem by linearly relaxing the integer problem into non-integer linear problem
solving it. The theory of linear programming states that under mild assumptions (if there exists an optimal solution to the linear programming and the feasible domain does not contain line), there always exists an extremum optimal solution
or vertex that is optimal. Test whether obtained is integer solution. If not, then there must exist linear inequality separating the optimal point from the convex envelope of the true feasible set. Finding such an inequality is the separation problem, and such an inequality is the cutting plane. The cutting plane can be added to the linear program being relaxed such that the current abelian solution is no longer feasible for the relaxation. The process is repeated until optimal integer solution is found.
5. Instructions: You need to understand the above, especially about the cut-plane algorithm, the next tasks will be closely related to the cut-plane algorithm.
Description of task details 1. Sample code for cut plane selection function:
[start]
import numpy as np import as def fam_name (cuts_features, sel_cuts_nun)
return idxes [end]
The parameters of the function the characteristics of all cuts and the number of cuts to be selected. After completing the selection, returns an idx list of all selected cutting planes.
In addition, each function is independent, each function needs to import the corresponding package such as numpy... and each function uses [start] and [end] as the start and end identifiers.
43

---

(Continued) Prompt of data curation for MILP solver
2. Characterization: Pay attention to the cutting plane features in the function input. The following are the specific contents contained in these features:
cut cut_feature obj_parall, eff,
# Target Parallelism
# Cut-plane validity
support,
integral_support,
tormalized_Voolation,,
mean_coeff_cut,
max_coeff_cut,
min_coeff_cut,
std_coeff_cut,
mean_coeff_obj
max_coeff_obj.
min_coeff_obj
std_coeff_ob]
3. No comments annotations required, only the code needs to be provided.
Collected Response to above Prompt
[start]
import numpy as np def
featurre, sel_cuts_nun)
features array (euttsfeatures) if len (fneaturres) sel cuts num: return list (range (len (features)))
eff features 1]
viol features[: 4]
supp features [;, 2] features
coeff f_s__std = features(; 8] (features(: 5] + 1e-10)
quality np (eft viol) np. 1p.1og(p(supp)
q. thresh
percentile (quality, 70)
var thresh np. percenttle(coofff...
30)
mask (quality >= q-thresh) & (coeff_sta <= var_thresh)
candidates np. where (mask) [o]
if len (candidates) <= sel_cuts_mun
return candidates. tolist()
active_features features [aad diversity = zeros (len (1en(cadidaates)) for i in range (len coeff (ee(andiddates)
np sum sum abs
+ active_ [eatturrusss obj_diff np abs abp (abbracciiveefeetuesss:::00 + active fariieefeetures___ [i (])
axis=1)
diversity [i] np mean (coeff_diff diff obj_diff)
scores = quality [candidates] * diversity
return candidates [np argsort (-scores) [:sel_cuts_nnnneeeeeesss tolist()
[end]
44


Reviews:
[{"review_id": "MBYDr7f1FW", "reviewer": "Reviewer_zr9g", "summary": "The paper provides a framework for solving combinatorial problems that integrates structure priors on the problems themselves to enhance solution quality and solving efficiency. This is achieved through combining a GNN to extract the structural embeddings from CO instances, which are then fed to a LLM that produces the solver-specific code.", "questions": "- This quote from Yang's analysis (lines 69-72) indeed points to a fundamental limitation of LLMs pre-trained primarily on text for structured domains. While fine-tuning is crucial, the initial pre-training distribution shapes the model's inherent priors. The STRCMP framework effectively addresses this by introducing structural priors via a GNN. 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, or is there a deeper, emergent understanding of structure fostered within the LLM itself due to this multi-modal input that goes beyond just adapting to the fine-tuning data?\n- The paper mentions that the full STRCMP model (with SFT + DPO) doesn't uniformly outperform its ablations, suggesting \"underlying conflicts within the post-training data distribution\". Could you elaborate on what these \"domain-specific distributional discrepancies\" might entail?\n- The paper has adopted a two-stage training due to \"significant optimization challenges\" with end-to-end joint training. Could you provide more specific details on these challenges? For instance, were they related to gradient propagation issues across the GNN-LLM boundary, computational resource limitations, or difficulties in aligning the learning objectives of the two very different modalities?\n- The paper claims superior interpretability due to generating solver-executable code. However, CO problems can be highly complex, and the generated code snippets (e.g., hybrid_diversity_selector in Appendix I) can be quite intricate. 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? Is the generated code always easily understandable and modifiable by a human domain expert, or can it become opaque in its own right, albeit in a \"code\" format?", "limitations": "The limitation of two stage process has been mentioned in the limitation. But this is also a major weakness of this paper.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n- STRCMP consistently matches or exceeds all baseline performance in terms of solution optimality and computational efficiency. It shows significant reductions in timeouts and solving time for SAT problems, and maintaining strong performance parity for MILP\n- The paper highlights that existing LLM-based approaches for CO problems \"often neglect critical structural priors\". STRCMP directly tackles this significant gap by explicitly integrating these structural priors.\n- The paper also provides a theoretical analysis based on information theory and multi-modal co-learning, showing how integrating priors does not lower the upper bound on model performance.\n\n**Weaknesses:**\n\n- The ablations results are counterintuitive. STRCMP does not uniformly outperform its ablations (SFT Only and DPO Only) across all benchmarks. While acknowledged as a limitation and an area for future research, it indicates an incomplete understanding or unresolved issue in the current training protocol, which slightly diminishes the overall quality of the \"full\" proposed solution.\n- The paper adopts a two-stage training procedure (GNN first, then a frozen GNN with LLM) due to \"significant optimization challenges\" with end-to-end joint training. This suggests a practical workaround rather than an ideal integrated solution. It might potentially limit the synergistic learning that could occur with true end-to-end training.\n- The interpretability part is not convincing. While code generation offers interpretability over black-box NCO methods, the complexity of generated code for highly intricate CO problems or novel heuristics might still pose interpretability challenges in practice. The generated code, even if syntactically correct, might not always be easily digestible or modifiable by human experts without significant effort.", "was_revised": true, "final_justification": "The rebuttal has clarified some of the concerns.", "rebuttal": "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.\n\n**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\"?**\n\n**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.\n\n**(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.\n\n**Table 1: The Optimization Performance Result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP Domain**\n| Dataset| STRCMP| STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n|:-|:-|:-|:-|:-|\n|corlat|**6597\\.61**|6866\\.61|7709\\.85|7650\\.13|\n|knapsack|3\\.24|3\\.23|3\\.21|3\\.19|\n|loadbalancing|2204\\.89|**2121\\.20**|2202\\.50|2228\\.26|\n|mik|269\\.68|**252\\.24**|284\\.89|292\\.41|\n|mis|5\\.46|6\\.64|5\\.45|5\\.48|\n|setcover|34\\.02|33\\.95|34\\.17|34\\.06|\n\n*Note that for the Primal-Dual Integral, a lower value indicates better performance.*\n\nBased on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:\n\n- **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.\n- **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.\n- **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.\n\n**(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.\n\n**Table 2: The Performance of STRCMP w.r.t. Primal-Dual Integral with Varied-Size Backbone LLM over MILP Domain**\n||||STRCMP||STRCMP w/o GNN||\n|:-|:-|:-|:-|:-|:-|:-|\n|**Dataset**|Qwen2(0\\.5B)|Qwen2(1\\.5B)|Qwen2(7B)|Qwen2(14B)|Qwen2(7B)|Qwen2(14B)|\n|mik|--|--|269\\.68|233\\.56|292\\.41|262\\.74|\n|setcover|--|--|34\\.02|34\\.29|34\\.06|34\\.24|\n\n**Table 3: The Performance of STRCMP w.r.t. PAR-2 Score with Varied-Size Backbone LLM over SAT Domain**\n||||STRCMP||STRCMP w/o GNN||\n|:-|:-|:-|:-|:-|:-|:-|\n|**Dataset**|Qwen2(0\\.5B)|Qwen2(1\\.5B)|Qwen2(7B)|Qwen2(14B)|Qwen2(7B)|Qwen2(14B)|\n|PRP|--|--|470\\.63|414\\.12|500\\.00|455\\.09|\n|Zamkeller|--|--|355\\.3|127\\.7|635\\.75|308\\.30|\n\n*Note that for both metrics, a lower value indicates better performance.*\n\nIt 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.\n\n**Q2: Could you provide more specific details on challenges related to joint end-to-end training?** \n\n**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. \n\nWe 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:\n\n1.  **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.\n\n**Table 4: The Training Loss of End-to-End Joint Training**\n|**Training Step**|**End-to-End DPO Loss**|**End-to-End SFT Loss**|\n|:-|:-|:-|\n|100|0\\.54|1\\.64|\n|200|0\\.60|1\\.53|\n|300|0\\.26|1\\.44|\n|400|0\\.43|1\\.28|\n|500|0\\.56|1\\.14|\n|600|0\\.13|1\\.04|\n|700|0\\.42|0\\.98|\n|800|0\\.29|0\\.88|\n|900|0\\.30|0\\.86|\n\n2.  **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.\n\n**Table 5: The Jointly Trained Model's Performance over Two SAT datasets** w.r.t. PAR-2 Score\n| **Dataset** | **STRCMP (Two-Stage)** | **Joint End-to-End Model** |\n| :--- | :--- | :--- |\n| **Zamkeller** | 270.62 | 751.34 |\n| **PRP** | 1804.46 | 2092.71 |\n\n*Note that for PAR-2 Score, a lower value indicates better performance.*\n\nThese 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**.\n\n**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?**\n\n**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.  \n\nNevertheless, 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.\n\nWe 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."}, {"review_id": "wndQ0xT0OR", "reviewer": "Reviewer_7TYC", "summary": "Summary: \nThis works falls into the line of work of using LLMs to generate programs to solve combinatorial optimization models. The authors incorporate additional constraints / priors in the generation process by converting the input CO problem into a bipartite graph as is commonly done. This graph is passed through a GNN to generate a “structure embedding” which is also passed as input to the final LLM.", "questions": "1.\tHow much does the performance of STRCMP depend on the underlying LLM? It would be interesting to see how performance changes with changing LLMs. This would help give an understanding of how much the structural embedding from the GNN contributes to the final result.  \n\n2.\tPerozzi et al. [1] dive deeper into generating tokens from graphs and merging a GNN and LLM to improve downstream task performance. I would recommend giving their paper a read to look for potential avenues of improvement. \n\n[1] Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R. and Halcrow, J., 2024. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1.\tThe work is well motivated. Adding additional constraints to the generation process to improve quality of generation seems like a good avenue to explore. \n2.\tPaper is well written and structured \n\nWeaknesses: \n1.\tResults are not convincing enough and a bit confusing in places. Across all results – Figs. 4, 5b, 8, 9, 10, 11 and Tables 5 and 6, the ablated variants of the STRCMP often outperform STRCMP. While the authors acknowledge this issue, I feel the paper is incomplete without an explanation as to why, or a way of picking which ablated variant to use in which case, especially given that in a lot of cases, the differences are quite drastic. \n2.\tAlong the same lines, results on MILP instances shown in Figure 10 are not very convincing with LLM4Solver performing identical to STRCMP in most cases.\n\nPlease also consider positioning this work (and comparing where adequate) with recent LLM-based Optimization Co-Pilots. These seem omitted in the current version. Naming only a few here and plz see references therein to better position the work\n- OptiMUS: Optimization Modeling Using MIP Solvers and large language models, A. AhmadiTeshnizi et. al. \n- Constraint modelling with LLMs using in-context learning, K Michailidis, CP 2024 \n- Ner4Opt: Named entity recognition for optimization, Kadioglu et. al. Constraints 2024 \n- Enhancing decision making through the integration of large language models and operations research optimization, Wasserkrug et. al. AAAI'25\n- Holy Grail 2.0: From Natural Language to Constraint Models, D. Tsouros et. al.", "was_revised": true, "final_justification": "Raising my score per the rebuttal. There are still some concern as raised by all reviewers but nevertheless an interesting paper with promising results that might worth sharing with the community.", "rebuttal": "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.\n\n**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.**\n\n**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.\n\n**Table 1: The Optimization Performance Result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP Domain**\n| Dataset| STRCMP| STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n|:-|:-|:-|:-|:-|\n|corlat|**6597\\.61**|6866\\.61|7409\\.85|7650\\.13|\n|knapsack|3\\.24|3\\.23|3\\.21|3\\.19|\n|loadbalancing|2204\\.89|**2121\\.20**|2202\\.50|2228\\.26|\n|mik|269\\.68|**252\\.24**|284\\.89|292\\.41|\n|mis|5\\.46|6\\.64|5\\.45|5\\.48|\n|setcover|34\\.02|33\\.95|34\\.17|36\\.06|\n\n*Note that for the Primal-Dual Integral, a lower value indicates better performance.*\n\nBased on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:\n\n1.  **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.\n2.  **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.\n3.  **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.\n\n**Q2: Clarification on Experimental Results on MILP domain.**\n\n**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.\n\nTo 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.\n\n**Table 2: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over corlat Dataset**\n| Iterations | LLM4Solver  | STRCMP      | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n| :- | :-  | :- | :-  | :- | :-  |\n| 3 | 9939\\.48 | 8750\\.84 | 6880\\.25 | 7159\\.24 | 10325\\.77|\n| 6 | 9860\\.20 | 8889\\.19 | 7235\\.31| 6870\\.31| 10435\\.85|\n| 9 | 9673\\.47 | 8836\\.85  | 7364\\.47| 6881\\.48|10404\\.27|\n| 12| 9900\\.06 |  | | 6932\\.57 ||\n\n**Table 3: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over mik Dataset**\n| Iterations | LLM4Solver  | STRCMP      | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n|:-|:-|:-|:-|:-|:-|\n|3|535\\.04|478\\.08|394\\.25|451\\.48|492\\.96|\n|9|499\\.60|455\\.18|421\\.44|434\\.09|494\\.24|\n|15|470\\.48|450\\.72|408\\.55|431\\.42|481\\.97|\n|21|466\\.45|438\\.51|372\\.12|||\n|27|471\\.22|448\\.31|380\\.74|||\n\n**Table 4: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over loadbalancing Dataset**\n| Iterations |LLM4Solver| STRCMP|STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n|:-|:-|:-|:-|:-|:-|\n|3|1942\\.27|1881\\.74|2125\\.22|2193\\.62|1910\\.53|\n|9|1885\\.31|1878\\.52|2065\\.61|2245\\.97|1905\\.49|\n|15|1867\\.71|1859\\.14|2051\\.36|||\n\n**Q3: Positioning this work (and comparing where adequate) with recent LLM-based Optimization Co-Pilots.**\n\n**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:  \n\n1. **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. \n\n2. **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].  \n\n**Q4: How much does the performance of STRCMP depend on the underlying LLM?**\n\n**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.\n\nGiven 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.\n\n**Table 5: The Performance of STRCMP w.r.t. Primal-Dual Integral with Varied-Size Backbone LLM over MILP Domain**\n||||STRCMP||STRCMP w/o GNN||\n|:-|:-|:-|:-|:-|:-|:-|\n|**Dataset**|Qwen2(0\\.5B)|Qwen2(1\\.5B)|Qwen2(7B)|Qwen2(14B)|Qwen2(7B)|Qwen2(14B)|\n|mik|--|--|269\\.68|233\\.56|292\\.41|262\\.74|\n|setcover|--|--|34\\.02|34\\.29|34\\.06|34\\.24|\n\n**Table 6: The Performance of STRCMP w.r.t. PAR-2 Score with Varied-Size Backbone LLM over SAT Domain**\n||||STRCMP||STRCMP w/o GNN||\n|:-|:-|:-|:-|:-|:-|:-|\n|**Dataset**|Qwen2(0\\.5B)|Qwen2(1\\.5B)|Qwen2(7B)|Qwen2(14B)|Qwen2(7B)|Qwen2(14B)|\n|PRP|--|--|470\\.63|414\\.12|500\\.00|455\\.09|\n|Zamkeller|--|--|355\\.3|127\\.7|635\\.75|308\\.30|\n\n*Note that for both metrics, a lower value indicates better performance.*\n\nIt 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:\n\n1.  **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.\n\n2.  **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.\n\n3.  **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. \n\nWe 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."}, {"review_id": "1XI2ACbpdw", "reviewer": "Reviewer_7osJ", "summary": "This paper proposes to add structural priors for LLM-based algorithmic discovery to improve the performance of the generated code snippet in optimization solvers. Optimization problems are transformed into graphs based on their structures, and a GNN is adopted to encode the graph information into vectors, which are concatenated with the text embedding of the prompts. Experiments are conducted on SAT (bump_var function) and MILP (cut plane selection function).", "questions": "See \"weaknesses\".", "limitations": "See \"weaknesses\".", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n- The general idea of improving LLM with structural information is promising.\n- Good writing and sufficient details. The theoretical analysis provides some insights into the role of priors for LLM-based algorithmic discovery.\n- Experiments conducted on both SAT and MILP, two representative CO problems.\n\n## Weaknesses\nWhile the structure of an optimization problem is surely important, the specific method proposed in this paper is questionable. Generally speaking, algorithmic discovery should be problem-irrelevant. That is, LLMs are prompted to perform _general_ improvement on the code snippet, and an improved code snippet should work well on a wide variety of problem instances with different structural information. However, it seems that this paper proposes to fuse the structural information (embedding vectors) of _a specific problem instance_ with a prompt that asks for general improvement, which is not aligned. Consider the following simplified prompt: \n> \"I have the graph information of a Boolean formula $ q = (x₁ ∨ x₂) ∧ (¬x₁) ∧ (¬x₁ ∨ x₂) $ as (...). You are a SAT solver researcher, your goal is to improve bump_var for the SAT solver, ...\"\n\nFrom the perspective of a SAT solver researcher, I don't feel that the previous sentence informing graph information (i.e., the problem feature vector $ h_q $ in the paper) is super useful for me, especially considering that my aim is to improve bump_var in a general sense, rather than just for the specific problem q = (x₁ ∨ x₂) ∧ (¬x₁) ∧ (¬x₁ ∨ x₂). At least, the intuition behind fusing a specific $h_q$ with a general prompt is not immediately clear to me.\n\nTo investigate the issue, I looked into the theoretical analysis and experiential evaluation of the paper, but the issue remains unsolved:\n- For theoretical analysis, the paper proposes some very general theorems regarding \"performance-enhancing prior\". However, it remains unclear why the structural information $h_q$ of a specific problem $q$ could theoretically be a \"performance-enhancing prior\" for generating generally improved code snippets.\n- For experiential evaluation, the improvement of the proposed method is not very significant either. For example, for the four datasets in Table 1 and 5,  comparing STRCMP with AutoSAT, the performance on CNP and CGD is generally the same, while the performance on PRP is much slower. Considering that algorithmic discovery could be a very randomized process with great variance, the current result does not seem to be significant enough to show the effectiveness of $h_q$'s inclusion. It is also worth noting that the baseline approach (AutoSAT) does not adopt any post-training process. Is it possible that the performance gain comes from the post-training process rather than the inclusion of $h_q$?\n\n## Suggestions\nI feel that this paper would make more sense if the problem setting could be adjusted a bit. Instead of searching for a general improvement for a code snippet, targeting a problem-specific improvement (i.e., improvement w.r.t some prior information of the problem) seems to be more promising (the evaluation function should also be adjusted to be problem-specific). Given a problem instance $q$, an LLM could incorporate the structure of the problem $h_q$ by the proposed method, to generate a _problem-specific_ code snippet, which is \"tailored\" to solve the specific problem $q$ efficiently.", "was_revised": true, "final_justification": "As the authors have initially shown the effectiveness of the problem-specific setting with empirical results, I have raised my score.", "rebuttal": "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.\n\n**Q1: Is it possible that the performance gain comes from the post-training process rather than the inclusion of $h_q$?**\n\n**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.\n\n**Table 1: The Optimization Performance result w.r.t. Primal-Dual Integral between Different Ablation Variants over MILP domain**\n| Dataset       | STRCMP       | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n| :------------ | :----------- | :---------------- | :---------------- | :------------- |\n| corlat        | **6597\\.61** | 6866\\.61 | 7409\\.85 | 7650\\.13|\n| knapsack      | 3\\.24| 3\\.23| 3\\.21| 3\\.19|\n| loadbalancing | 2204\\.89| **2121\\.20**      | 2202\\.50   | 2228\\.26|\n| mik           | 269\\.68 | **252\\.24**      | 284\\.89| 292\\.41 |\n| mis           | 5\\.46| 6\\.64    | 5\\.45| 5\\.48 |\n| setcover      | 34\\.02 | 33\\.95    | 34\\.17 | 36\\.06|\n\n*Note that for the Primal-Dual Integral, a lower value indicates better performance.*\n\nBased on the complete test results across both SAT and MILP domains, we can draw three clear conclusions:\n\n1.  **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.\n2.  **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.\n3.  **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.\n\n**Q2: The advantage of STRCMP over existing framework (LLM4Solver and AutoSAT) in terms of efficiency and effectiveness.**\n\n**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**.\n\n1. **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. \n\n2. **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. \n\n**Table 2: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over corlat Dataset**\n| Iterations | LLM4Solver  | STRCMP      | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n| :--------- | :---------- | :---------- | :---------------- | :---------------- | :------------- |\n| 3          | 9939\\.48 | 8750\\.84 | 6880\\.25| 7159\\.24  | 10325\\.77|\n| 6          | 9860\\.20| 8889\\.19 | 7235\\.31| 6870\\.31| 10435\\.85|\n| 9          | 9673\\.47| 8836\\.85 | 7364\\.47 | 6881\\.48 | 10404\\.27|\n| 12         | 9900\\.06 |             |                   | 6932\\.57 |                |\n\n**Table 3: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over mik Dataset**\n| Iterations | LLM4Solver  | STRCMP      | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n| :--------- | :---------- | :---------- | :---------------- | :---------------- | :------------- |\n| 3          | 535\\.04 | 478\\.08 | 394\\.25| 451\\.48| 492\\.96 |\n| 9          | 499\\.60| 455\\.18| 421\\.44| 434\\.09| 494\\.24|\n| 15         | 470\\.48| 450\\.72| 408\\.55| 431\\.42| 481\\.97|\n| 21         | 466\\.45| 438\\.51| 372\\.12|                   |                |\n| 27         | 471\\.22| 448\\.31 | 380\\.74|                   |                |\n\n**Table 4: The Performance v.s. Iteration Result w.r.t. Primal-Dual Integral between Different Methods over loadbalancing Dataset**\n| Iterations | LLM4Solver  | STRCMP      | STRCMP (SFT Only) | STRCMP (DPO Only) | STRCMP w/o GNN |\n| :--------- | :---------- | :---------- | :---------------- | :---------------- | :------------- |\n| 3          | 1942\\.27 | 1881\\.74 | 2125\\.22  | 2193\\.62| 1910\\.53  |\n| 9          | 1885\\.31| 1878\\.52 | 2065\\.61 | 2245\\.97| 1905\\.49 |\n| 15         | 1867\\.71 | 1859\\.14  | 2051\\.36 |                   |                |\n\n**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.**\n\n**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.\n\nYour 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.\n\nThe 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.\n\n**Table 5: Performance of Specialized vs. General Heuristics on SAT Benchmarks (PAR-2 Score ↓)**\n| **Heuristic** | **Zamkeller Test Set** | **PRP Test Set** | **CoinsGrid Test Set** | **Description** |\n| :--- | :---: | :---: | :---: | :--- |\n| AutoSAT (General) | 807.75 | 639.34 | 1098.69 | Baseline general heuristic. |\n| STRCMP (General) | 270.62 | 1804.46 | 1124.09 | Our general-purpose heuristic. |\n| **STRCMP (Zamkeller-Specialized)** | **185.31** | 1950.12 | 1205.45 | Heuristic specialized per Zamkeller instances. |\n| **STRCMP (PRP-Specialized)** | 755.40 | **451.77** | 1152.81 | Heuristic specialized per PRP instances. |\n\n*Note: Base scores for AutoSAT and STRCMP (General) are taken from Table 5 of our submission.*\n\nAs 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.\n\nThis 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."}, {"review_id": "ZQ0hkXqWif", "reviewer": "Reviewer_2EbJ", "summary": "This paper proposed a framework that combines GNN and LLM for CO problems. First, a GNN is pretrained to encode structural information of CO problems. Second, a composition model is trained so that LLM generates better code to solve the CO problem. The authored proved that a GNN prior does not hurt the performance, and exhibited promising empirical results.", "questions": "- How does the natural language description of the CO problem look like?\n- 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. \n- Is the solving code generated by the LLM guaranteed to be executable without bugs or syntax error?\n- Could you explain more about the sup(P) in definition 1? It is not clear to me why it takes the form of that.", "limitations": "The limitations are discussed in appendix F, which already address my concerns as well.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n- The paper is well motivated and well written.\n- The background of current research is well explained. \n- The details of GNN and LLM implementations are clear, even to readers that have little background of LLMs. \n\nWeakness:\n- The diagrams in experiments are good, but I still expect some tables with actual numbers. \n- Some empirical results are not consistently better, e.g. CNP solving time in table 5 and 6.\n- The theory is a bit weak, but that is very minor point.", "was_revised": true, "final_justification": "I believe this paper, even with a few flaws, is worthwhile for the community. I am not well knowledgable in LLM, therefore, I would like to maintain my confidence score and raise the scores due to the nice rebuttal by the authors", "rebuttal": "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.\n\n**Q1: How does the natural language description of the CO problem look like?**\n\n**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:\n\n- **Nodes** represent the variables of the CO problem.\n- **Edges** represent the constraints between these variables.\n\nHowever, 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:\n\n> \"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.\"\n\nThis 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. \n\n**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.**\n\n**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**.\n\nTo 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:\n\n**Table 1: The Optimization Performance Comparison  between Different Dataset Used Methods**\n|Methods|Primal-Dual Integral|\n|:-|:-|\n|STRCMP (mixed)|269\\.68|\n|STRCMP w/o GNN (mixed)|292\\.41|\n|STRCMP (`mik` only)|276\\.35|\n|STRCMP w/o GNN (`mik` only)|295\\.93|\n\n*Note that for the Primal-Dual Integral, a lower value indicates better performance.*\n\nThese 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.\n\n**Q3: Is the solving code generated by the LLM guaranteed to be executable without bugs or syntax error?**\n\n**A3:** We appreciate the reviewer’s question about the executability and correctness of LLM-generated code in our STRCMP framework. To ensure reliability:\n\n1. **Compilation Check:**  \n   - Each code snippet is compiled with its CO solver (e.g., SCIP, EasySAT).  \n   - Snippets failing compilation are discarded with a low score.  \n\n2. **Performance Evaluation:**  \n   - Valid snippets are tested on benchmark CO instances (Section 5.1).  \n   - Metrics (Appendix E.1, E.2) assess performance; only high-scoring, error-free code is used.  \n\nThis ensures all experimental code is executable, syntactically correct, and effective. See Appendices E.1 and E.2 for details. We welcome further feedback.\n\n\n**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.**\n\n**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.\n\nLet us break down the formula to explain its structure $\\sup(\\mathcal{P}_\\mathcal{C})$:\n\n1. **The Inner Term: Maximum Performance for a Single Prior**\n\nThe 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}$**:\n\n* $\\Phi(\\mathbf{w})$ is the performance score w.r.t. downstream task of a generated output $\\mathbf{w}$.\n* $p(\\mathbf{w}|\\mathbf{c})$ is the probability that the model generates $\\mathbf{w}$ given the prior $\\mathbf{c}$.\n* 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.\n\nHowever, 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.\n\nThis 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.\n\n2. **The Outer Term: Expectation over All Priors**\n\nThe 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.\n\n- $\\mathcal{C}$ is the set of all *types* of priors (e.g., text, structural embedding of CO problem instances).  \n- Each $\\mathbf{C}$ is a specific prior type (e.g., $\\mathbf{C}_1$ = text prompts, $\\mathbf{C}_2$ = structural embeddings).  \n- This sum ensures we account for all distinct modalities/contexts in the task.  \n-  The double summation iterates over all types of priors $\\mathbf{C}$ and all specific instances $\\mathbf{c}$ within each type.\n-  $p(\\mathbf{c})$ is the probability of encountering a specific prior $\\mathbf{c}$.\n\nTherefore, 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.\n\n\nIn 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."}]

Author rebuttal:

Meta-review: In this paper, the authors introduce STRCMP, a framework that integrates graph structural priors with LLMs to address combinatorial optimization problems. By embedding explicit graph information into LLM-driven reasoning, STRCMP improves the model’s ability to capture problem structure in tasks such as routing and scheduling. Experimental results show that STRCMP delivers competitive or superior performance compared to heuristic solvers and LLM-only methods, which demonstrates the effectiveness of combining graph priors with LLM adaptability. After rebuttal, all reviewers turn to be positive about this paper, and I also agree with them for acceptance. However, please take into account the comments of reviewers and the new results during rebuttal in the final version.
Decision: Accept (poster)