Paper deep dive
SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization
Yuanyu Li, Jintao Xu, Zijiang Liu, Yongzhi Qi, Ningxuan Kang, Jianshen Zhang, Wei Qi, Chen Xie, Zuo-Jun Max Shen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/14/2026, 4:23:08 AM
Summary
The paper introduces SSPO (Structure-Aware Similarity-Weighted Preference Optimization), a method for Neural Combinatorial Optimization (NCO) that addresses two failure modes in existing training methods: gradient signal polarization (discarding non-best solutions) and baseline redundancy (uniformly weighting structurally similar solutions). SSPO constructs zero-parameter solution embeddings from encoder node representations to measure structural dissimilarity between sampled solutions. It then uses these dissimilarities to weight a leave-one-out baseline, giving higher weight to structurally distinct peers to reduce gradient variance. Experiments on TSP, EFL, and JSP benchmarks show consistent improvements, and the method has been deployed in a production system at JD.com.
Entities (9)
Relation Signals (7)
SSPO → usedon → EFL
confidence 95% · Experiments on TSP, EFL, and JSP benchmarks show consistent gains
SSPO → usedon → TSP
confidence 95% · Experiments on TSP, EFL, and JSP benchmarks show consistent gains
SSPO → usedon → JSP
confidence 95% · Experiments on TSP, EFL, and JSP benchmarks show consistent gains
SSPO → deployedat → JD.com
confidence 92% · The SSPO-trained EFL policy has been deployed in a production facility-location system at JD.com
SSPO → addresses → Gradient Signal Polarization
confidence 90% · SSPO... scores all B sampled solutions jointly... resolving both failures in a single mechanism.
SSPO → addresses → Baseline Redundancy
confidence 90% · SSPO... scores all B sampled solutions jointly... resolving both failures in a single mechanism.
SSPO → outperforms → RLOO
confidence 85% · A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers-a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high-a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all $B$ sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD$\mathord{.}$com, confirming practical viability at scale.
Tags
Links
- Source: https://arxiv.org/abs/2608.12443v1
- Canonical: https://arxiv.org/abs/2608.12443v1
Trouble viewing inline? Open PDF directly →
Full Text
39,783 characters extracted from source content.
Expand or collapse full text
SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization Yuanyu Li1, Jintao Xu1, Zijiang Liu1, Yongzhi Qi1, Ningxuan Kang1, Jianshen Zhang1, Wei Qi2†, Chen Xie1, Zuo-Jun Max Shen3 Thanks: Corresponding authors. Abstract Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers—a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high—a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all B sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder’s existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD. .com, confirming practical viability at scale. 1 Introduction Combinatorial optimization problems (COPs)—such as the Traveling Salesman Problem (TSP) (Dantzig, Fulkerson, and Johnson 1954), Job-Shop Scheduling (JSP) (Ingimundardottir and Runarsson 2018), and the Entity Facility Location (EFL) problem---are key to logistics, scheduling, and resource allocation. Traditional exact solvers (e.g., SCIP11 1 https://w.scipopt.org/, Gurobi22 2 https://w.gurobi.com/) guarantee optimality but scale poorly to large instances. Neural combinatorial optimization (NCO) (Bello et al. 2017; Kool, van Hoof, and Welling 2019a) learns solution-construction policies directly from data, achieving near-optimal quality with orders-of-magnitude faster inference. A hallmark of modern NCO training is parallel solution sampling: for each instance, B candidate solutions are drawn from the current policy simultaneously, and their collective cost signal is used to update the policy parameters. How to maximally exploit the information contained in this co-sampled group is therefore central to training efficiency—yet existing methods leave substantial signal on the table through two complementary failure modes. Failure Mode 1: Gradient Signal Polarization. Self-labeling methods and preference-optimization approaches such as BOPO (Liao et al. 2025) treat the single best solution in a group as a privileged “anchor” and cast every other sample as an undifferentiated negative. All training signal is thus concentrated at one extreme of the quality spectrum. The fine-grained quality gradients that exist among the non-best solutions—and the structural differences that explain why one non-best solution is better than another—are completely discarded. When B is large (e.g., B=256B=256), the wasted information is immense. This is a specific instance, in the NCO parallel-sampling regime, of the well-known best-vs-rest information-loss problem studied in pairwise preference learning and RLHF; what is particular to NCO is that the discarded “losers” carry rich structural signal (which edges were chosen, which facilities were selected) that no existing method has exploited. Failure Mode 2: Baseline Redundancy and High Variance. Another family of methods avoids the best-anchor bias by incorporating all B solutions into the baseline via their average cost—whether as a simple group mean or a leave-one-out variant—but weights them uniformly regardless of their structural relationships. For NCO problems, co-sampled solutions often share strong topological similarity, especially early in training when the policy is near-deterministic. This uniform weighting floods the baseline with redundant information from near-identical peers, yielding a less discriminative control variate and leaving gradient variance persistently high. The general phenomenon—that correlated samples weaken the variance-reduction power of a control variate—is classical in Monte Carlo estimation; our contribution is to show that in NCO it can be diagnosed and repaired cheaply using structural information that is already present in the encoder’s hidden states. 1.1 Our Approach: SSPO Both failure modes share a common root: existing methods are structure-blind, either ignoring the structure of non-best solutions entirely (polarization) or equating structurally identical and diverse solutions (redundancy). We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization) to address both problems simultaneously with a single, unified mechanism. The key insight is that a peer solution which is structurally different from the current solution represents a genuinely alternative strategy: its cost provides far richer information about the policy landscape than a near-duplicate. SSPO therefore: • Scores all B B solutions jointly—beyond simple best-vs-rest comparisons—preserving fine-grained quality differences among non-best solutions in the gradient signal. • Weights each peer by structural dissimilarity, assigning higher baseline weight to topologically distinct solutions, so that informative contrast is amplified and redundant similarity is suppressed. Concretely, SSPO builds zero-parameter solution embeddings from the encoder’s existing node representations: Hadamard products of node pairs for edge-structured problems such as TSP, and mean-pooling over solution-relevant selected nodes for problems whose solutions are represented by selected or allocated node sets, such as EFL and JSP. It then centers these embeddings to remove shared global bias and derives dissimilarity weights wij∝(1−Sij)w_ij (1-S_ij), where SijS_ij denotes the cosine similarity between solutions i and j. Since Sii=1S_i=1, the self-weight wii=0w_i=0 follows automatically, excluding the reference cost from its own baseline and preserving the leave-one-out construction. When all solutions are structurally identical, wijw_ij degenerates uniformly to 1/(B−1)1/(B-1), recovering standard RLOO as a special case. 1.2 Contributions 1. Current NCO training suffers from two failure modes—gradient signal polarization and baseline redundancy—both caused by structure-blindness. We provide a formal diagnosis of each. 2. We propose SSPO, a structure-aware, dissimilarity-weighted leave-one-out baseline that simultaneously addresses both failure modes: it uses all B solutions (no polarization) and up-weights structurally dissimilar peers (no redundancy). Structural similarity is measured via problem-adaptive, zero-parameter solution embeddings—Hadamard node-pair products for TSP and mean-pooling over selected nodes for EFL and JSP—that fully reuse the encoder’s existing representations, so SSPO retains the leave-one-out construction and introduces no additional learnable parameters. 3. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL isolates structure-aware weighting as the primary driver of improvement. 2 Related Work 2.1 Neural Combinatorial Optimization Pointer Networks (Vinyals, Fortunato, and Jaitly 2015) pioneered autoregressive construction policies for COPs under supervised learning. The Attention Model (AM) (Kool, van Hoof, and Welling 2019a) established the transformer-based encoder–decoder paradigm with REINFORCE training. POMO (Kwon et al. 2020) amplifies solution diversity at inference by using B different start nodes, and adopts the group mean cost as a shared baseline; however, this baseline is biased and still aggregates all B solutions with uniform weight. Graph convolutional networks (Joshi, Laurent, and Bresson 2019) and neural–heuristic hybrids (Xin et al. 2021) provide complementary approaches. None of the above exploit the structural relationships among co-sampled solutions as a training signal. 2.2 Gradient Signal Polarization: Best-Anchor Methods A prominent line of work treats the best solution in a sampled group as a privileged supervisory signal. Self-labeling / self-improvement methods use the best candidate as a pseudo-label and train the policy to imitate it, discarding all other samples. Preference-optimization approaches (Pan et al. 2025; Liao et al. 2025) form pairwise winner–loser pairs where the best solution is always the “winner” and every other solution is an undifferentiated “loser.” Both paradigms polarize the training signal: the entire learning signal collapses onto a single best-anchor solution, while the fine-grained quality gradients and structural variation among the remaining B−1B-1 solutions are wholly wasted. As B grows, the discarded information becomes increasingly significant. SSPO avoids polarization entirely by assigning a meaningful, differentiated weight to every solution in the group. 2.3 Baseline Redundancy: Uniform-Weighting Methods Methods that aggregate all B solutions via a mean-based baseline avoid the best-anchor bias, but weight every peer solution equally regardless of structural relationships. When co-sampled solutions are topologically near-identical—a common occurrence early in training or with greedy decoders—the uniformly-weighted baseline accumulates redundant information from structurally equivalent peers. The resulting control variate has low discriminative power, and gradient variance remains persistently high. SSPO breaks the uniformity assumption while retaining the leave-one-out construction: structurally dissimilar peers receive higher weight, while the reference cost is excluded from its own baseline. 2.4 Leave-One-Out Baselines and Group-Relative Methods Leave-one-out (LOO) baselines have a long history as low-variance, unbiased control variates for REINFORCE. Kool et al. (Kool, van Hoof, and Welling 2019b) introduced the RLOO estimator, in which the baseline for sample i is the uniform mean of the costs of the remaining B−1B-1 peers. Ahmadian et al. (Ahmadian et al. 2024) recently rediscovered RLOO in the LLM RLHF setting and showed it is a competitive, simpler alternative to PPO for language-model alignment. Group Relative Policy Optimization (GRPO) (Shao et al. 2024), popularized by DeepSeek-Math/-R1 (Guo et al. 2025), follows the same template: it groups B rollouts per prompt and forms each sample’s advantage relative to the uniform mean and variance of its peers. POMO’s group-mean baseline (Kwon et al. 2020), while biased (it includes the sample’s own cost), is structurally identical: all peers contribute with equal weight. These methods all instantiate a common template, bi=∑j≠iwijcjb_i= _j≠ iw_ij\,c_j with wij=1/(B−1)w_ij=1/(B-1), and their effectiveness as control variates degrades whenever peers are strongly correlated—precisely the regime NCO operates in, where co-sampled solutions are often topologically near-identical. SSPO can be seen as a structure-dependent generalization of this template: it keeps the leave-one-out form but replaces the uniform weight with wij∝(1−Sij)w_ij (1-S_ij), where SijS_ij is computed from solution structure rather than cost. To the best of our knowledge, SSPO is the first method to make leave-one-out weights structure-dependent in the NCO setting. 2.5 Structural Similarity as a Training Signal Structural diversity metrics (Hamming distance, Jaccard edge overlap) are standard in population-based metaheuristics (Helsgaun 2017) for maintaining solution variety, but are used at inference or search time, not during policy gradient training. SSPO instead brings this structural signal into policy gradient training, using it online to reweight the baseline for variance reduction. 3 Problem Formulation 3.1 Graph-Based Optimization Instance We represent a COP instance as a graph =(V,E,,)G=(V,E,X,A), where V is the set of N decision nodes, ∈ℝN×dxX ^N× d_x are node features (e.g., coordinates, demands), and ∈ℝN×N×daA ^N× N× d_a are edge features (e.g., pairwise distances). 3.2 Learning Objective A policy πθ _θ autoregressively constructs a solution =(s0,s1,…,sT−1)s=(s_0,s_1,…,s_T-1) by selecting actions from the feasible set at each step. The training objective is to minimize the expected solution cost: (θ)=∼πθ[c()],J(θ)=E_s _θ [c(s) ], (1) where c()c(s) is a problem-specific cost. For minimization problems c()c(s) is the objective directly (e.g., total tour length for TSP, makespan for JSP); for maximization problems it is the negated objective (e.g., c()=−c(s)=-\,satisfied demand for EFL, whose goal is to maximize demand coverage). Throughout, we adopt the cost-minimization convention without loss of generality. 4 Structure-Aware Similarity-Weighted Preference Optimization 4.1 Overview Figure 1: Overview of SSPO. For each instance, B solutions are sampled from the policy. Zero-parameter solution embeddings are built from the encoder’s node representations via Hadamard products (TSP) or mean-pooling (EFL/JSP), then centered and used to compute pairwise dissimilarity weights. The dissimilarity-weighted leave-one-out baseline is used in place of a uniform baseline in the REINFORCE update. For each training instance, SSPO samples B solutions ii=1B\s_i\_i=1^B with costs cii=1B\c_i\_i=1^B from the current policy πθ _θ. Unlike best-anchor methods that discard all but the optimal sample, and unlike uniform mean-based baselines that ignore structural diversity, SSPO constructs a dissimilarity-weighted leave-one-out baseline biSSPOb_i^SSPO that assigns meaningful, differentiated weights to all B solutions based on their pairwise structural dissimilarity. The design rests on two components (Figure 1). First, we represent each solution by a structure-aware embedding. It is built directly from the encoder’s node representations and adds no parameters. Second, we turn the pairwise dissimilarities between these embeddings into leave-one-out baseline weights, so that a structurally distinct peer contributes more to the baseline than a near-duplicate. The resulting advantage Ai=biSSPO−ciA_i=b_i^SSPO-c_i then drives a standard REINFORCE update. 4.2 Structure-Aware Solution Embeddings To measure structural similarity between two solutions without any additional learnable parameters, we reuse the graph encoder’s existing node representations vv∈V\h_v\_v∈ V (output of the final attention layer) and construct solution-level embeddings in a problem-adaptive manner. TSP Problem. In TSP, all solutions visit the same node set; what differs is which edges are traversed. For a solution route (k)=(s0,…,sT−1)s^(k)=(s_0,…,s_T-1), with the closing convention sT(k):=s0(k)s_T^(k):=s_0^(k), we compute the Hadamard product for each consecutive edge: t(k)=st(k)⊙st+1(k),t=0,…,T−1,e_t^(k)=h_s_t^(k) _s_t+1^(k), t=0,…,T-1, (2) and mean-pool over all edges: k=1T∑t=0T−1st(k)⊙st+1(k).z_k= 1T _t=0^T-1h_s_t^(k) _s_t+1^(k). (3) Properties of the Hadamard embedding. Three properties make the Hadamard product well suited to edge-level structural encoding: • Symmetry: i⊙j=j⊙ih_i _j=h_j _i, correctly modeling undirected edges in TSP. • Non-degeneracy: Unlike simple addition, 1T∑t=0T−1(st+st+1)=2T∑v∈Vv 1T _t=0^T-1(h_s_t+h_s_t+1)= 2T _v∈ Vh_v for all-node closed TSP tours, yielding identical embeddings for any route. Hadamard products over distinct node pairs yield irreducible, route-specific representations. • Context-richness: vh_v is refined through L mixed-attention layers integrating global topology, so i⊙jh_i _j encodes the interaction between nodes i and j in the context of the full instance—far richer than raw coordinate differences. EFL and JSP Problems. In EFL, solution diversity is determined by which facility nodes are selected; in JSP, by which operations are assigned to which machines. We directly mean-pool the encoder embeddings of selected decision nodes: k=1T∑t=0T−1st(k).z_k= 1T _t=0^T-1h_s_t^(k). (4) Both embeddings reuse existing encoder representations with zero additional parameters. Centering to remove a shared global direction. Mean-pooling introduces a global base direction shared by all B solutions (since every solution draws from the same encoder embeddings of the same instance). Without correction, all pairwise cosine similarities cluster near 1.01.0, making solutions appear structurally identical and collapsing the weight distribution to near-uniform—effectively collapsing SSPO to a structure-blind uniform baseline. We therefore remove the shared direction by centering: ~k=k−1B∑j=1Bj. z_k=z_k- 1B _j=1^Bz_j. (5) After centering, cosine similarity purely captures relative structural differences among solutions, yielding a discriminative and numerically stable measure. 4.3 The Dissimilarity-Weighted Leave-One-Out Baseline We now turn the centered embeddings into baseline weights. We compute pairwise cosine similarities on the centered embeddings: Sij=~i⊤~j‖~i‖‖~j‖,Sij←clamp(Sij, 0, 1).S_ij= z_i z_j\| z_i\|\,\| z_j\|, S_ij (S_ij,\;0,\;1). (6) The SSPO dissimilarity weight for peer j relative to solution i is: wij=1−Sij∑k≠i(1−Sik),wii=0.w_ij= 1-S_ij _k≠ i(1-S_ik), w_i=0. (7) Intuitively, a peer that is structurally different from is_i represents a genuinely alternative strategy; its cost carries far more information about the value landscape than a near-duplicate. The SSPO baseline for solution i is: biSSPO=∑j≠iwijcj.b_i^SSPO= _j≠ iw_ij\,c_j. (8) Graceful degradation to uniform baseline. When all solutions are structurally identical (Sij=cS_ij=c for all j≠ij≠ i), the numerators (1−Sij)(1-S_ij) are equal and wij=1/(B−1)w_ij=1/(B-1), recovering uniform leave-one-out weighting exactly. In practice, a small ϵ=10−8ε=10^-8 is added to the denominator of Eq. (7) for numerical stability. The advantage for solution i is: Ai=biSSPO−ci.A_i=b_i^SSPO-c_i. (9) The SSPO policy gradient loss is: ℒ=−1B∑i=1Bsg(Ai)∑t=0T−1logπθ(at(i)∣st(i))−βH¯(πθ),L=- 1B _i=1^Bsg(A_i) _t=0^T-1 _θ\! (a_t^(i) s_t^(i) )-β\, H( _θ), (10) where sg(⋅)sg(·) is stop-gradient (the baseline does not receive gradients through embeddings), and H¯(πθ) H( _θ) is an optional entropy bonus weighted by β≥0β≥ 0 to encourage exploration. The full procedure is summarized in Algorithm 1. Algorithm 1 SSPO Training 0: Policy πθ _θ, group size B, entropy weight β 1: repeat 2: Sample a mini-batch of instances (m)\G^(m)\ 3: for each instance (m)G^(m) do 4: Sample B solutions; compute costs ck\c_k\ 5: Obtain node embeddings v\h_v\ from encoder 6: Build k\z_k\ via Eq. (3) or (4) 7: Center: ~k z_k via Eq. (5) 8: Compute SijS_ij via Eq. (6) 9: Compute wijw_ij via Eq. (7) 10: Compute biSSPOb_i^SSPO via Eq. (8) 11: end for 12: Update θ with ℒL via Eq. (10) 13: until convergence 4.4 Complexity Analysis Beyond the standard REINFORCE forward pass, SSPO adds two operations: (i) solution-level embedding construction via Hadamard products (TSP) or mean-pooling (EFL/JSP), with cost (BND)O(BND); and (i) a B×B× B cosine-similarity matrix, with cost (B2D)O(B^2D). For the settings used throughout our experiments, both are negligible compared to the encoder–decoder forward pass ((N2DL)O(N^2DL) per rollout, executed B times per instance). SSPO introduces no additional learnable parameters beyond those of the underlying policy network. 4.5 Variance Trade-off Relative to RLOO The introduction identified baseline redundancy as a principal failure mode: when co-sampled peers are strongly correlated, a uniformly weighted leave-one-out baseline loses variance-reduction power. We now make this intuition precise, and characterize when SSPO’s dissimilarity weighting yields a lower-variance baseline than uniform RLOO. Fix one training instance and one reference rollout i. Let i=1,…,B∖i,m=B−1.J_i=\1,…,B\ \i\, m=B-1. Consider the general convex leave-one-out baseline bi(w)=∑j∈iwjcj,wj≥0,∑j∈iwj=1.b_i(w)= _j _iw_jc_j, w_j≥ 0, _j _iw_j=1. Uniform RLOO is obtained by setting wj=1/mw_j=1/m: biRLOO=1m∑j∈icj.b_i^RLOO= 1m _j _ic_j. To obtain a closed-form comparison, we adopt a standard exchangeability-style assumption on peer costs. It is a mild symmetry condition: peers drawn from the same policy on the same instance share a marginal variance, and only their pairwise correlations ρjk _jk vary—exactly the quantities SSPO’s structure-aware weights aim to exploit. Assumption 1. Peer costs have equal marginal variance and pairwise covariances of the form Var(cj)=σ2,Cov(cj,ck)=σ2ρjk,j≠k.Var(c_j)=σ^2, (c_j,c_k)=σ^2 _jk, j≠ k. (11) Under Assumption 1, we obtain a closed-form expression for the variance gap introduced by the SSPO weights, decomposed into a marginal-variance penalty and a signed covariance-term reduction. Proposition 1. Variance difference between the weighted leave-one-out baseline and uniform RLOO is Var(bi(w))−Var(biRLOO) \! (b_i(w) )-Var\! (b_i^RLOO ) = = σ2[∑j∈iwj2−1m⏟marginal-variance penalty≥0−∑j,k∈ij≠k(1m2−wjwk)ρjk⏟signed covariance-term change]. σ^2 [ _j _iw_j^2- 1m_marginal-variance penalty~≥~0- _ subarraycj,k _i\\ j≠ k subarray ( 1m^2-w_jw_k ) _jk_signed covariance-term change ]. (12) Consequently, Var(bi(w))≤Var(biRLOO)Var\! (b_i(w) ) \! (b_i^RLOO ) if and only if ∑j,k∈ij≠k(1m2−wjwk)ρjk≥∑j∈iwj2−1m. _ subarraycj,k _i\\ j≠ k subarray ( 1m^2-w_jw_k ) _jk≥ _j _iw_j^2- 1m. Proof. For a fixed weight vector w, the variance of the weighted baseline is Var(bi(w)) \! (b_i(w) ) =∑j∈iwj2Var(cj)+∑j,k∈ij≠kwjwkCov(cj,ck). = _j _iw_j^2Var(c_j)+ _ subarraycj,k _i\\ j≠ k subarrayw_jw_kCov(c_j,c_k). Substituting Var(cj)=σ2,Cov(cj,ck)=σ2ρjk,j≠k.Var(c_j)=σ^2, (c_j,c_k)=σ^2 _jk, j≠ k. gives Var(bi(w))=σ2(∑j∈iwj2+∑j,k∈ij≠kwjwkρjk).Var\! (b_i(w) )=σ^2 ( _j _iw_j^2+ _ subarraycj,k _i\\ j≠ k subarrayw_jw_k _jk ). For uniform RLOO, wj=1/mw_j=1/m. Then we have Var(bi(w))−Var(biRLOO) \! (b_i(w) )-Var\! (b_i^RLOO ) =σ2[∑j∈iwj2−1m−∑j,k∈ij≠k(1m2−wjwk)ρjk]. =σ^2 [ _j _iw_j^2- 1m- _ subarraycj,k _i\\ j≠ k subarray ( 1m^2-w_jw_k ) _jk ]. ∎ Uniform RLOO minimizes ∑jwj2 _jw_j^2 over the probability simplex. Therefore, the first term in (12) is always nonnegative: any deviation from uniform weights incurs a positive marginal-variance penalty. The second term is an aggregate covariance adjustment and can have either sign. For a positively correlated peer pair satisfying wjwk<1/m2w_jw_k<1/m^2, the quantity (1/m2−wjwk)ρjk(1/m^2-w_jw_k) _jk is positive, and contributes to reducing the variance difference. The benefit becomes larger as the correlation ρjk _jk increases and as wjwkw_jw_k falls further below 1/m21/m^2. Therefore SSPO achieves a lower baseline variance when the resulting aggregate covariance reduction is sufficient to offset the marginal-variance penalty induced by nonuniform weights. Hence SSPO has lower baseline variance precisely when its structure-aware weights sufficiently reduce the contribution of highly correlated peer pairs to offset the penalty caused by weight concentration—the regime our experiments (Section 5.3) identify as structurally diverse. 5 Experiments 5.1 Experimental Setup We evaluate SSPO on three problem families chosen to probe different assumptions in preference-optimization NCO training. TSP (N∈50,100N∈\50,100\, uniform [0,1]2[0,1]^2; gap vs. LKH-3 (Helsgaun 2017)) is edge-structured, with solutions that share most edges early in training—the regime where baseline redundancy is most severe. EFL (Entity Facility Location) is a real-world facility placement benchmark with coverage and demand constraints; its solution space is assignment-dominated, so co-sampled solutions can occupy completely disjoint regions and best-anchor methods risk locking onto a single suboptimal mode. JSP (Job-Shop Scheduling) spans three standard families (LA/TA/DMU) whose difficulty and instance size vary widely, letting us probe how each method scales with problem hardness. Fair comparison protocol. For every problem–method pair, all methods share the identical backbone encoder (L=6L=6 mixed-attention layers, 8 heads, hidden dimension D=256D=256), the same random initialization, the same group size B=256B=256, and the same optimizer schedule. The only difference across methods is the baseline formulation. This isolates the effect of the baseline design—the central object of study in this paper—from confounders such as architecture width, sampling strategy, or curriculum. Optimality gaps are reported against LKH-3 (TSP), the best result among all compared methods (EFL, for which exact optimization is computationally intractable), and best-known solutions (JSP). Baselines and ablation. We compare SSPO against three categories of prior work: (i) BOPO (Liao et al. 2025), the current state-of-the-art best-anchor preference-optimization method for NCO; (i) POMO (Kwon et al. 2020) and Sym-NCO (Kim, Park, and Park 2022) for TSP, and SLIM (Corsini et al. 2024) for JSP, as representative structure-blind baselines; and (i) uniform RLOO, which shares SSPO’s leave-one-out form but sets wij=1/(B−1)w_ij=1/(B-1). RLOO is critical for our analysis: comparing SSPO with RLOO isolates the contribution of structure-aware weighting, while comparing RLOO with BOPO isolates the contribution of the leave-one-out form itself. Together the three-way comparison exposes the trade-off that motivates SSPO’s design (Section 5.3). 5.2 Main Results Tables 1–3 show that SSPO attains the best average optimality gap on five out of six main-benchmark settings, and is within 0.05p of the best result on the sixth. Beyond the raw ranking, the tables reveal a consistent qualitative pattern across the three problem families, which we discuss in turn. TSP. On TSP, SSPO improves over BOPO at both scales, and the margin grows with instance size: from 0.01p on TSP-50 (0.14% vs. 0.15%) to 0.08p on TSP-100 (0.40% vs. 0.48%). This size dependence is the signature predicted by our variance analysis (Section 4.5): larger instances admit more topologically distinct co-sampled solutions, so the signed covariance-term reduction in Proposition 1 grows, and the dissimilarity weighting has more leverage to offset the marginal-variance penalty. Table 1: TSP optimality gap (%). Best in bold. Method TSP-50 TSP-100 POMO 0.21% 1.04% Sym-NCO — 0.94% BOPO 0.15% 0.48% RLOO 0.33% 1.32% SSPO (ours) 0.14% 0.40% LKH-3 0% 0% EFL. On EFL, we report the relative gap to the best result among all compared methods. SSPO attains this best result (0% relative gap), while BOPO and POMO trail by 7.31% and 7.34% respectively. The gap here is much larger than on TSP, and the cause is structural rather than numerical: the assignment-dominated solution space is far wider than an edge-structured tour, so a best-anchor method that concentrates its learning signal on a single top solution tends to lock the policy into a suboptimal mode. By scoring all B solutions jointly and weighting them by structural dissimilarity, SSPO keeps the whole group informative throughout training. Table 2: EFL relative gap (%) to the best result among all compared methods. Best in bold. Method Gap to Best POMO 7.34% BOPO 7.31% RLOO 2.64% SSPO (ours) 0% We further probe SSPO on production-scale facility-placement cases at JD.com, whose demand and coverage distributions are considerably less regular than the standard EFL benchmark. Figure 2 shows two representative real-world instances. In both, the SSPO policy places facilities so that demand coverage stays consistent with the pattern reported on the benchmark, confirming that the method transfers beyond the regularized EFL setting. Figure 2: Comparison of real-world EFL facility-placement solutions produced by RLOO, SSPO, BOPO, and POMO. These production-scale cases have far less regular demand and coverage distributions than the standard EFL benchmark, yet SSPO yields placements consistent with the benchmark results. JSP. On the harder TA and DMU families SSPO improves over BOPO by 1.14p (7.52% vs. 8.66%) and 0.86p (12.95% vs. 13.81%). On the easier LA family BOPO holds a marginal 0.05p edge (2.50% vs. 2.55%). This reversal is consistent with our analysis rather than adverse to it: on compact instances the policy settles into a tight mode early, so structural diversity among co-sampled peers is low. Consequently, the signed covariance-term reduction in Proposition 1 shrinks toward zero, and SSPO approaches uniform RLOO. The residual 0.05p gap matches the small marginal-variance penalty ∑jwij2−1/(B−1) _jw_ij^2-1/(B-1) that SSPO pays whenever its weights deviate from uniform. Table 3: JSP average optimality gap (%) across benchmark families. Best in bold. Method LA Avg TA Avg DMU Avg SLIM 2.59% 7.84% 13.11% BOPO 2.50% 8.66% 13.81% SSPO (ours) 2.55% 7.52% 12.95% 5.3 Analysis Best-anchor vs. uniform-LOO trade-off. The most informative comparison in Tables 1 and 2 is not SSPO vs. BOPO, but BOPO vs. RLOO—the two baseline designs that SSPO subsumes—because their ranking reverses across problem families. On TSP-100 the best-anchor signal is strong: BOPO (0.48%) beats RLOO (1.32%) by 2.75×2.75×, since co-sampled tours share many edges and anchoring on the top tour concentrates the gradient on a meaningful direction. On EFL the picture inverts: RLOO (2.64%) beats BOPO (7.31%) by 2.8×2.8×, because the assignment space is wide and anchoring on one solution strands the policy in a local mode. Neither baseline is uniformly correct; each fixes one failure mode and aggravates the other. SSPO is designed around this trade-off—it keeps the leave-one-out form to avoid best-anchor lock-in while re-weighting peers by structural dissimilarity to avoid the redundant baseline of uniform RLOO—and it improves over the better of the two in both regimes (0.40% vs. 0.48% on TSP-100; 0% vs. 2.64% on EFL). Effect of structural diversity. The size of SSPO’s advantage tracks how structurally diverse the co-sampled solutions are. Where diversity is high—EFL, and the larger TSP and harder JSP instances—SSPO’s gain over BOPO is largest, matching Proposition 1: the signed covariance-term reduction ∑j≠k(1/m2−wjwk)ρjk _j≠ k(1/m^2-w_jw_k) _jk scales with peer dissimilarity, so the signal SSPO recovers grows with the diversity that best-anchor methods miss. Where diversity is low, as on the compact JSP LA family, the bound tightens to equality and SSPO’s margin shrinks to a marginal gap of 0.05p. Ablation: structure-aware weighting. Replacing SSPO’s dissimilarity weights with uniform weights (i.e., recovering plain RLOO) on TSP-100 degrades the gap from 0.40% to 1.32%—a 3.3×3.3× deterioration on the same architecture, initialization, and rollouts. This isolates the source of the gain. The leave-one-out form alone is insufficient: uniform RLOO underperforms even BOPO (1.32% vs. 0.48%), so the improvement does not come from excluding the current solution’s own cost from the baseline. The gain comes from the weighting itself—substituting uniform wij=1/(B−1)w_ij=1/(B-1) with the dissimilarity-driven wij∝1−Sijw_ij 1-S_ij, with no other change, accounts for the improvement from 1.32% to 0.40%. Together with the trade-off analysis above, this attributes SSPO’s improvement to structure-aware weighting as a design choice rather than to the leave-one-out form or a tuned encoder, exactly as Section 4.3 anticipates. 6 Conclusion We presented SSPO, which reweights the leave-one-out baseline by structural dissimilarity between co-sampled solutions. This single mechanism addresses two orthogonal failure modes in NCO training—gradient signal polarization and baseline redundancy—while remaining zero-parameter and preserving the leave-one-out form. Experiments on TSP, EFL, and JSP show consistent gains over best-anchor and uniform-weight baselines, and a direct comparison against uniform RLOO isolates structure-aware weighting as the primary driver. More broadly, our results suggest that the structural information encoded in the graph representations—so far used only for action selection—is a rich, underused signal for variance reduction, opening the door to structure-aware training beyond the specific baselines studied here. References Ahmadian et al. (2024) Ahmadian, A.; Cremer, C.; Gallé, M.; Fadaee, M.; Kreutzer, J.; Pietquin, O.; Üstün, A.; and Hooker, S. 2024. Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs. In Ku, L.-W.; Martins, A.; and Srikumar, V., eds., Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 12248–12267. Bangkok, Thailand: Association for Computational Linguistics. Bello et al. (2017) Bello, I.; Pham, H.; Le, Q. V.; Norouzi, M.; and Bengio, S. 2017. Neural Combinatorial Optimization with Reinforcement Learning. arXiv:1611.09940. Corsini et al. (2024) Corsini, A.; Porrello, A.; Calderara, S.; and Dell'Amico, M. 2024. Self-Labeling the Job Shop Scheduling Problem. In Globerson, A.; Mackey, L.; Belgrave, D.; Fan, A.; Paquet, U.; Tomczak, J.; and Zhang, C., eds., Advances in Neural Information Processing Systems, volume 37, 105528–105551. Curran Associates, Inc. Dantzig, Fulkerson, and Johnson (1954) Dantzig, G.; Fulkerson, R.; and Johnson, S. 1954. Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America, 2(4): 393–410. Guo et al. (2025) Guo, D.; et al. 2025. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645(8081): 633–638. Helsgaun (2017) Helsgaun, K. 2017. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Roskilde University. Ingimundardottir and Runarsson (2018) Ingimundardottir, H.; and Runarsson, T. P. 2018. Discovering dispatching rules from data using imitation learning: A case study for the job-shop problem. Journal of Scheduling, 21(4): 413–428. Joshi, Laurent, and Bresson (2019) Joshi, C. K.; Laurent, T.; and Bresson, X. 2019. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227. Kim, Park, and Park (2022) Kim, M.; Park, J.; and Park, J. 2022. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In Koyejo, S.; Mohamed, S.; Agarwal, A.; Belgrave, D.; Cho, K.; and Oh, A., eds., Advances in Neural Information Processing Systems, volume 35, 1936–1949. Curran Associates, Inc. Kool, van Hoof, and Welling (2019a) Kool, W.; van Hoof, H.; and Welling, M. 2019a. Attention, learn to solve routing problems! In International Conference on Learning Representations. Kool, van Hoof, and Welling (2019b) Kool, W.; van Hoof, H.; and Welling, M. 2019b. Buy 4 REINFORCE Samples, Get a Baseline for Free! Kwon et al. (2020) Kwon, Y.-D.; Choo, J.; Kim, B.; Yoon, I.; Gwon, Y.; and Min, S. 2020. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., Advances in Neural Information Processing Systems, volume 33, 21188–21198. Curran Associates, Inc. Liao et al. (2025) Liao, Z.; Chen, J.; Wang, D.; Zhang, Z.; and Wang, J. 2025. BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization. In Singh, A.; Fazel, M.; Hsu, D.; Lacoste-Julien, S.; Berkenkamp, F.; Maharaj, T.; Wagstaff, K.; and Zhu, J., eds., Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, 37456–37475. PMLR. Pan et al. (2025) Pan, M.; Lin, G.; Luo, Y.-W.; Zhu, B.; Dai, Z.; Sun, L.; and Yuan, C. 2025. Preference optimization for combinatorial optimization problems. In Proceedings of the 42nd International Conference on Machine Learning, ICML’25. JMLR.org. Shao et al. (2024) Shao, Z.; Wang, P.; Zhu, Q.; Xu, R.; Song, J.; Bi, X.; Zhang, H.; Zhang, M.; Li, Y. K.; Wu, Y.; and Guo, D. 2024. DeepSeekMath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Vinyals, Fortunato, and Jaitly (2015) Vinyals, O.; Fortunato, M.; and Jaitly, N. 2015. Pointer Networks. In Cortes, C.; Lawrence, N.; Lee, D.; Sugiyama, M.; and Garnett, R., eds., Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc. Xin et al. (2021) Xin, L.; Song, W.; Cao, Z.; and Zhang, J. 2021. NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. In Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P.; and Vaughan, J. W., eds., Advances in Neural Information Processing Systems, volume 34, 7472–7483. Curran Associates, Inc.