Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

Zhenxing Xu; Zeyuan Ma; Weidong Bao; Yan Zheng; Chongshuang Hu; Ji Wang; Zhiguang Cao

cs.LGFeb 24, 2026

Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

Authors: Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

Organizations: National Key Laboratory of Big Data and Decision, National University of Defense Technology · School of Computer Science, South China University of Technology · School of Computing and Information Systems, Singapore Management University

Abstract

We study efficiency as a first-class objective in Neural Combinatorial Optimization (NCO) and present ECO, an efficient learning framework that combines batched preference optimization with a Mamba backbone. Instead of tightly interleaving every policy update with on-policy rollouts, ECO decouples trajectory generation from gradient updates through two stages: supervised warm-up on pre-computed solutions and iterative Direct Preference Optimization (DPO) on batched candidate sets generated by the current policy. We pair this learning pipeline with a mixed Mamba encoder-decoder that reduces memory growth on long sequences and improves hardware utilization. A local-search-guided bootstrapping strategy is further used during training to widen preference margins and stabilize iterative improvement. Importantly, local search is only used to construct stronger preference pairs during training and is never invoked at inference time. On TSP and CVRP, ECO achieves the strongest overall performance among the compared neural baselines while also delivering clear advantages in memory usage and throughput. We provide additional analysis on memory scaling, throughput, and the contribution of each design component.

Figures & tables

Fig. 1: Convergence efficiency on TSP1000. The curves display the average optimality gap over 20 independent runs, with shaded regions indicating the standard deviation. All methods were trained on a single NVIDIA A800 GPU; wall-clock time includes rollout or candidate generation during training but excludes the one-time generation of shared SFT labels. Batch sizes were tuned within the same memory budget for each method.

Fig. 2: The core designs and workflow of our ECO. Left : The Mamba-based Encoder-Decoder architecture proposed to facilitate offline NCO training. Right : The two-phase offline learning with a SFT warm-up as quick knowledge adaption and an iterative preference learning to further enhance performance.

Method	TSP200			TSP500			TSP1000			TSP5000
Method	Obj. $\downarrow$	Gap $\downarrow$	Time $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Time $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Time $\downarrow$	Obj. $\downarrow$	Gap $\downarrow$	Time $\downarrow$
Concorde	10.72	0.00%	3.0m	16.55	0.00%	37.6m	23.12	0.00%	7.9h	50.96	0.00%	18.4h
LKH-3	10.72	0.00%	0.8m	16.55	0.00%	1.5m	23.12	0.00%	24m	50.96	0.00%	9.6h
AM	11.03	2.89%	0.3m	21.24	28.34%	1.4m	35.18	52.16%	2.2m	96.37	89.11%	5.7m
POMO	10.97	2.33%	0.2m	20.85	25.98%	1.0m	32.94	42.47%	1.6m	87.79	72.27%	4.8m
LEHD	10.79	0.65%	0.3m	17.08	3.20%	0.8m	24.70	6.83%	2.5m	55.82	9.54%	8.6m

TABLE I: Performance comparison on TSP and CVRP instances of varying sizes. We report the average objective value (Obj.), the average optimality gap (Gap) relative to the ground truth, and the total wall-clock evaluation time (Time) over the same 1,000-instance test set. Time follows the max-utilization batched protocol recommended by each implementation; fixed-batch timing and protocol details are reported in Tables II and XI . Concorde , LKH-3 and HGS are used as the ground truth solvers for TSP and CVRP, respectively (indicated by 0.00% Gap). ‘ECO’ denotes the full model trained with LS-augmented preference construction, while ‘ECO w/o LS Boot.’ removes this training-time signal. No local search is used during inference for either row. For learning-based methods, the best results are highlighted in bold , and the second-best results are underlined .

Method	TSP1000 Time		CVRP500 Time
	Max	Fixed-8	Max	Fixed-8
AM	2.2	2.8	2.0	2.4
POMO	1.6	2.0	1.4	1.8
LEHD	2.5	3.1	2.0	2.3
CNF	7.7	7.9	4.3	4.4
GFlowNet-HBG	1.3	1.5	0.7	0.8

TABLE II: Fixed-batch timing audit. Runtime in minutes on the same 1,000-instance test sets with inference batch size fixed to 8 for all neural methods. The max-utilization time is copied from Table I . Objective values are unchanged by the batching protocol.

Method	TSP1000	CVRP500	CVRP1000
CNF	$8.95{\pm}0.09$	$3.64{\pm}0.08$	$5.82{\pm}0.12$
GFlowNet-HBG	$5.62{\pm}0.07$	$\textbf{2.81}{\pm}0.06$	$2.89{\pm}0.07$
ECO	$\textbf{4.84}{\pm}0.05$	$2.85{\pm}0.05$	$\textbf{2.87}{\pm}0.08$

TABLE III: Bootstrap 95% confidence intervals for close neural comparisons. We report mean gap

\pm

95% CI over 10,000 bootstrap resamples of the 1,000 test instances.

Fig. 3: Memory and throughput comparison on an NVIDIA A800 GPU. (a) Peak memory usage versus problem size. ECO scales near-linearly and avoids the Transformer’s memory explosion. (b) Autoregressive inference throughput. ECO sustains substantially higher throughput as the sequence length increases.

Method / order	TSP1000 Gap		CVRP500 Gap
	Mean	Perm. std.	Mean	Perm. std.
POMO	42.47	0.02	24.17	0.03
ECO, raw input order	5.31	0.43	3.17	0.28
ECO, $x$ -coordinate sort	4.97	0.18	3.01	0.14
ECO, Hilbert order	4.82	0.04	2.83	0.04
ECO, Morton order (ours)	4.84	0.01	2.85	0.01

TABLE IV: Sensitivity to input node order. For each trained model, we evaluate 16 random permutations of the same test instances and report mean gap and the standard deviation across permutations. POMO is included as a set-equivariant attention reference.

Objective	Rel.	Gap (%) $\downarrow$	Time $\downarrow$
Pairwise logistic ranking	No	5.31	10.0h
Margin hinge ranking	No	5.58	9.8h
Online PPO	–	4.88	34.5h
DPO (ours)	Yes	4.84	10.2h

TABLE V: Objective-level comparison on TSP1000 under a matched Mamba backbone. All variants use the same SFT initialization, the same preference data budget, the same LS augmentation ratio, and the same stopping criterion. “Rel.” indicates whether an explicit reference policy is used during preference optimization.

Variant	Backbone / Update	SFT	LS	Gap (%) $\downarrow$ / Time $\downarrow$
SFT-only	Mamba / NLL	✓	✗	18.76 / 1.1h
w/o SFT	Mamba / DPO	✗	✓	$>20.0$ / –
w/o LS Boot.	Mamba / DPO	✓	✗	9.55 / 9.5h
Transformer+DPO	Transformer / DPO	✓	✓	5.47 / 14.6h
Mamba+PPO	Mamba / PPO	✓	✓	4.88 / 34.5h
Transformer+PPO	Transformer / PPO	✓	✗	9.73 / 38.7h

TABLE VI: Factorized ablation and counterfactual controls on TSP1000. We separately toggle the backbone, iterative update rule, SFT warm-up, and LS bootstrapping. “–” indicates divergence or unstable training.

$\alpha$	TSP1000 Gap	CVRP500 Gap	Margin (%)
0.0	9.55	3.94	0.22
0.1	6.21	3.24	1.05
0.3	4.84	2.85	1.87
0.5	4.92	2.88	2.19
1.0	5.37	3.06	3.04

TABLE VII: Sensitivity to the LS-augmented pair ratio

\alpha

. Gap is reported under pure neural inference. Margin denotes the average normalized winner–loser cost margin in the DPO buffer.

Training signal	TSP1000 Gap	CVRP500 Gap
Raw self-play DPO, no LS	9.55	3.94
SFT on LS-refined routes only	7.42	3.37
DPO + 2-opt / relocate	5.21	3.05
DPO + 3-opt / swap	5.08	2.98
DPO + combined LS (ours)	4.84	2.85

TABLE VIII: Disentangling LS supervision on TSP1000 and CVRP500. For CVRP, all moves are accepted only when capacity feasibility is preserved; infeasible relocate, swap, or 2-opt* moves are rejected before pair construction.

Pair source	Mean	Median	P10	P90
TSP1000 raw self-play	0.22	0.17	0.03	0.48
TSP1000 LS-refined	1.87	1.42	0.31	3.76
CVRP500 raw self-play	0.18	0.14	0.02	0.41
CVRP500 LS-refined	1.46	1.13	0.24	2.91

TABLE IX: Winner–loser margin distribution after LS refinement. Margins are normalized by the loser cost and reported in percent for the DPO buffer at

\alpha=0.3

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Parameter	Value
Embedding Dimension ( $D$ )	128
Number of Layers ( $L$ )	3
Mamba State Dimension ( $d_{state}$ )	16
Mamba Conv Kernel Size ( $d_{conv}$ )	4
Mamba Expansion Factor ( $E$ )	2
Feed-Forward Network (FFN) Ratio	4

Appendix

TABLE X: Hyperparameters of the Mixed Mamba Architecture.

Method	Decoding / budget	Batch policy	Model source
AM	greedy, 1 rollout	fixed-8 / max batch	retrained per scale
POMO	native multi-start, no 8-fold aug.	fixed-8 / max batch	retrained per scale
LEHD	heavy-decoder greedy	fixed-8 / max batch	official or retrained
CNF	official flow steps	fixed-8 / max batch	official recipe
GFlowNet-HBG	32 sampled candidates	fixed-8 / max batch	official 24h budget
ECO	greedy, 1 rollout, no LS	fixed-8 / max batch	retrained per scale

Appendix

TABLE XI: Evaluation protocol for neural baselines. “Max batch” means the largest batch fitting in 80GB GPU memory at the target scale. Fixed-batch timing uses batch size 8 for all listed methods.

Neural Combinatorial Optimization

Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.

See all 137 papers

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization
Jul 30, 2026Shengda Gu, Kai Li, Xinyi Ke +3Automated Algorithm Discovery Pairwise Preference Evaluation
C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab +1
SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization
Aug 12, 2026Yuanyu Li, Jintao Xu, Zijiang Liu +6Combinatorial Optimization Preference Optimization
Supply Chain Tech Team Y, JD.com, Beijing, China · Department of Industrial Engineering, Tsinghua University, Beijing, China · Faculty of Engineering and Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China
Recurrent State Encoders for Efficient Neural Combinatorial Optimization
Sep 5, 2025Tim Dernedde, Daniela Thyssens, Lars Schmidt-ThiemeRecurrent Neural Networks Combinatorial Optimization
Information Systems and Machine Learning Lab (ISMLL) Institute of Computer Science University of Hildesheim

Jul 30, 2026J/K move · Enter open · S save

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

Shengda Gu, Kai Li, Xinyi Ke, Haobo Fu+2

C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab+1

Automated Algorithm Discovery Pairwise Preference Evaluation Preference Optimization Neural Combinatorial Optimization Preference-Based RL

Open paper AskPDF arXiv

Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast construction policies, typically with reinforcement learning (RL), while preference-based NCO improves sample efficiency by learning from relative solution quality. However, existing preference objectives combine two distinct design choices in manually specified, one-size-fits-all formulations: what learning signal to extract from each solution pair and how to weight each pair relative to the sampled set. We present AutoPref, the first LLM-guided framework for automated preference-objective discovery in NCO. AutoPref factorizes the objective into a pairwise loss program, which defines the learning signal, and a set-aware weighting program, which determines each pair's relative contribution. Their composition forms a unified programmatic objective space containing existing preference objectives as special cases. To make its search tractable, we introduce a staged conditional search strategy with behavioral gates that filter inadmissible programs before short-horizon training and evaluation. Across TSP, CVRP, FFSP, and JSSP, AutoPref consistently outperforms strong hand-designed baselines across problem scales, demonstrating the benefits and scalability of automated objective discovery for NCO.

Abstract

Neural Combinatorial Optimization

Explore similar work

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Recurrent State Encoders for Efficient Neural Combinatorial Optimization