CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization

AI summary

Overview

Research area: Machine learning for combinatorial optimization (Neural Combinatorial Optimization), specifically heatmap-based solvers built on discrete diffusion models.

Technical level: Advanced. The paper assumes familiarity with diffusion denoising processes, Markov Decision Processes, policy-gradient methods (REINFORCE), LoRA adaptation, and standard CO benchmarks (TSP, MIS).

Scope: This paper diagnoses a systematic objective mismatch in supervised-learning-trained heatmap solvers and proposes CADO, a reinforcement-learning fine-tuning framework that directly optimizes the cost of decoded solutions.

What This Paper Is About

Heatmap-based solvers generate a full solution probability map in one shot and then hand it to a lightweight, non-differentiable decoder that projects it into a feasible solution. They are almost always trained by supervised learning (SL) to imitate known optimal solutions, on the implicit hope that a heatmap closer to the optimum will decode into a cheaper solution. The authors show empirically that this hope fails: minimizing imitation loss does not reliably minimize solution cost. Their goal is to realign a pretrained heatmap generator with the true combinatorial optimization objective by fine-tuning it with reinforcement learning on the actual post-decoded cost.

Key Contributions

1. Empirical dissection of the objective mismatch. The authors split the SL/RL mismatch into Decoder-Blindness (the training loss ignores the non-differentiable decoding heuristic) and Cost-Blindness (it prioritizes structural imitation over solution quality), and show empirically that the mismatch degrades performance.

2. The CADO framework. A streamlined RL fine-tuning framework that formulates the diffusion denoising process as an MDP and rewards the policy with the (negated) cost of the final decoded solution, thereby addressing both blindnesses simultaneously. When the number of denoising steps T = 1, the formulation collapses to a single-step MDP, making it model-agnostic and applicable to non-diffusion heatmap solvers.

3. Label-Centered Reward (LCR) and Hybrid Fine-Tuning (Hybrid-FT). LCR repurposes ground-truth solutions as instance-specific, action-independent, theoretically unbiased baselines (reward = negative optimality gap) rather than as imitation targets. Hybrid-FT applies LoRA to the input layer and the first 11 of 12 GNN layers while fully retraining the final GNN layer and output layer, for stable and memory-efficient adaptation.

4. State-of-the-art empirical results. CADO is reported to outperform existing baselines across TSP (100 to 10k nodes) and MIS (SATLIB and Erdős-Rényi) benchmarks, with all CADO results averaged over 4 independent runs.

Main Findings

• Both SL hypotheses fail. On TSP-100, the paper tests Decoder Monotonicity (H1, lower SL loss implies lower Hamming distance after decoding) and Cost Smoothness (H2, lower Hamming distance implies lower cost). H1 shows a strong but imperfect correlation. H2 shows a near-zero correlation between structural proximity to the optimum and the final solution cost. The direct relationship between SL loss and cost gap is the weakest of the three plots, with R² = 0.038.

• Cost-blindness is confirmed during RL fine-tuning. In the MIS-SAT learning curve, CADO-L cuts the cost gap by 58.5% (from 0.6% to 0.25%) while the SL loss monotonically increases. The authors interpret this sustained divergence as evidence that the two objectives have distinct optima rather than reaching the same optimum via different landscapes. This is consistent with the R² = 0.038 finding and with the negligible gains from extending SL training by 50% additional epochs (DIFUSCO+SFT).

• Decoder-blindness is confirmed by swapping decoders. The same SL-trained DIFUSCO heatmap scores 1.62% drop with a greedy decoder but 2.32% with a nearest-neighbor decoder. Training CADO-L separately for each decoder yields 0.19% (greedy) and 0.34% (greedy-decoder-trained CADO-L evaluated on NN), and 0.31% both ways for the NN-trained variant; each variant peaks when the inference decoder matches the training decoder, showing the heatmap learns decoder-specific structure.

• TSP results. On TSP-100, CADO reaches 7.76 tour length and 0.06% drop. On TSP-500, 16.65 length and 0.61% drop. On TSP-1k, 23.32 length and 0.88% drop, roughly halving DIFUSCO's 1.86% drop (23.55 length) at 3.6m versus 18m runtime. On TSP-10k, 73.69 length and 2.68% drop, beating DIFUSCO's 3.10% and divide-and-conquer methods such as GLOP (4.90%) and UDC.

• MIS results. On SATLIB, CADO achieves 425.43 set size and 0.12% drop in 6.5m, improving on DIFUSCO's 0.33% and T2T's 0.22%. On ER-[700-800], CADO achieves 43.62 set size and 2.78% drop, an 85% gap reduction relative to pretrained DIFUSCO (18.53%) and a 70% improvement over the previous best, FastT2T (9.52%, with T2T at 11.83%).

• The objective mismatch hurts most when the base model is weak. MIS-SAT, where the SL baseline is already accurate (0.33% drop), sees modest refinement; MIS-ER, where the SL baseline fails badly (18.53% drop), sees the largest gains. The authors read this as confirming that the mismatch manifests most severely when SL heatmaps are highly suboptimal.

• SL initialization is necessary; more SL training is not. In the controlled comparison with all auxiliary heuristics disabled, pure RL from scratch (RL-Scratch) and DIMES perform far worse than SL-based solvers. On MIS-ER, RL-Scratch records 26.4% drop and DIMES 14.8%, versus DIFUSCO's 18.5%. On TSP-500, RL-Scratch is 18.0% and DIMES 15.0%. Meanwhile DIFUSCO+SFT barely moves from DIFUSCO, indicating the SL plateau is an objective problem, not a training-steps problem.

• Realignment beats post-hoc guidance. CADO-L, without Local Rewrite, outperforms T2T and FastT2T (which rely on cost-guided search) on all four reported settings: TSP-500 3.0% versus T2T 6.9% and FastT2T(5,3) 5.5%; TSP-1k 6.1% versus 9.8% and 8.9%; MIS-SAT 0.16% versus 0.22%; MIS-ER 4.3% versus 11.8% and 9.5%. Adding Local Rewrite to CADO widens the gap further (TSP-500 1.3%, TSP-1k 4.0%, MIS-SAT 0.12%, MIS-ER 2.8%).

• Efficiency and generality. CADO-L omits Local Rewrite, reducing computational overhead to 40% of baseline methods. The framework also transfers beyond diffusion: applying it to pretrained FastT2T (1,0), a single-forward-pass heatmap solver, yields substantial gains reported in the paper's Tables 13 and 14.

Methodology in Plain English

The authors start from a public, well-trained SL heatmap solver (DIFUSCO checkpoints) and ask whether its imitation loss is actually a good proxy for the thing they care about — the cost of the final solution. They test this with scatter plots on TSP-100, pairing SL loss against Hamming distance, Hamming distance against cost gap, and SL loss directly against cost gap.

They then reframe the diffusion model's reverse (denoising) process as a sequential decision problem. The state is the instance, the remaining timestep, and the current noisy solution; the action is the next, less-noisy solution; and the reward is zero everywhere except at the final step, where it equals the negative cost of the decoded solution. Because the decoder is non-differentiable, they optimize this with REINFORCE, treating the sum of log-probabilities of each denoising step as the policy-gradient term.

Two reward variants are studied. The Standard Reward simply uses the negative cost, batch-normalized. The Label-Centered Reward subtracts the ground-truth solution's cost for that instance as a baseline, turning the reward into the negative optimality gap. Because the baseline depends only on the instance and not on the policy's actions, it stays the same in expectation and therefore does not bias the gradient — a useful property when the available labels are not truly optimal.

To keep fine-tuning stable and cheap, they split the network's parameters: LoRA adapters on the input layer and the first 11 GNN layers preserve the pretrained features, while the final GNN layer and the output layer are fully retrained because they shape the heatmap most directly. They then evaluate with standard decoding and refinement protocols — greedy decoding for MIS, greedy plus 2-opt or MCTS for TSP — and an ablated CADO-L variant without Local Rewrite so the effect of RL fine-tuning can be isolated.

Hardware for the experiments: eight NVIDIA L40 GPUs for training, one L40 GPU for testing, on an AMD EPYC 7413 24-Core Processor.

Why This Matters

The paper argues against a widely held assumption in neural combinatorial optimization: that better imitation of optimal solutions automatically produces better solutions. By showing that this link breaks down (R² = 0.038 between surrogate loss and cost gap), it reframes the problem as one of objective alignment rather than model capacity or training duration, and it delivers a reusable recipe for correcting that alignment without discarding expensive pretrained checkpoints.

The approach is also practically attractive because combinatorial optimization offers something image-generation RL fine-tuning does not: exact, cheaply computable cost functions and deterministic decoders. That removes the need for learned reward models or KL regularization.

Real-world applications, based on the benchmarks the paper studies and the standard problems it cites (TSP, MIS, CVRP, Knapsack):

• Routing and logistics: vehicle routing, delivery fleet dispatch, and last-mile planning, where TSP-style instances and short tour lengths translate directly into fuel and time savings.
• Network and infrastructure design: maximum independent set formulations underlie frequency assignment in wireless networks and certain sensor placement problems.
• Resource allocation and scheduling: knapsack-like and graph-based formulations appear in packing, capacity planning, and job scheduling.
• Chip design and verification: graph combinatorial problems of these forms appear in VLSI layout and circuit partitioning.

Industry relevance is direct: the work comes from LG AI Research, targets problems whose cost functions are exactly verifiable, and demonstrates scalability up to 10k-node TSP instances — where CADO beats divide-and-conquer methods built specifically for large scale — while cutting inference overhead to 40% of baselines in the CADO-L variant.

Future Directions

• Reducing reliance on labeled data. The paper reports that the Standard Reward offers a label-free alternative that maintains competitive performance, and notes that acquiring large-scale optimal datasets is often computationally prohibitive due to NP-hardness. How far SR can close the gap to LCR is left as an open question, and the truncated content does not report the final SR versus LCR comparison.

• Broadening the model-agnostic claim. The paper shows transfer to FastT2T (1,0), a single-forward-pass solver, via the T = 1 reduction of the MDP. Extending this to more heatmap architectures and to problems whose cost is not exactly evaluable in polynomial time remains open.

• Separating gains from search. CADO-L exists to isolate the RL fine-tuning effect from Local Rewrite, and the paper reports CADO-L at 40% of baseline computational overhead. The boundary between what fine-tuning alone can achieve and what still requires additional search remains an active design question.

• Failure-mode diagnosis. The paper observes that the objective mismatch is most severe when the SL base model is poor (MIS-ER at 18.53% drop versus MIS-SAT at 0.33%). Whether an a priori indicator can predict when RL fine-tuning will help most — and how much labeled data or pretraining quality is required — is not resolved.

Target Audience

Researchers and practitioners in neural combinatorial optimization who work with heatmap-based or diffusion-based solvers; reinforcement learning researchers interested in objective alignment and RL fine-tuning of generative models; and applied scientists at logistics, networking, or chip-design companies who want to extract more performance from an existing supervised checkpoint without retraining from scratch. Readers should be comfortable with diffusion models, policy gradients, and standard CO problem formulations.

Authors’ abstract

Heatmap-based solvers have emerged as a promising paradigm for Combinatorial Optimization (CO). However, we argue that the dominant Supervised Learning (SL) training paradigm suffers from a fundamental objective mismatch: minimizing imitation loss (e.g., cross-entropy) does not guarantee solution cost minimization. We dissect this mismatch into two deficiencies: Decoder-Blindness (being oblivious to the non-differentiable decoding process) and Cost-Blindness (prioritizing structural imitation over solution quality). We empirically demonstrate that these intrinsic flaws impose a hard performance ceiling. To overcome this limitation, we propose CADO (Cost-Aware Diffusion models for Optimization), a streamlined Reinforcement Learning fine-tuning framework that formulates the diffusion denoising process as an MDP to directly optimize the post-decoded solution cost. We introduce Label-Centered Reward, which repurposes ground-truth labels as unbiased baselines rather than imitation targets, and Hybrid Fine-Tuning for parameter-efficient adaptation. CADO achieves state-of-the-art performance across diverse benchmarks, validating that objective alignment is essential for unlocking the full potential of heatmap-based solvers.