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

• URL: http://arxiv.org/abs/2608.12443v1
• Date: Wed, 12 Aug 2026 16:04:54 GMT
• Title: SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization
• Abstract summary: Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers.<n>We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all $B$ sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline.
• Score: 7.503926194234302
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Baseline-Free Policy Optimization for Neural Combinatorial Optimization [1.2891210250935148]
  Group Relative Policy Optimization eliminates the baseline entirely by normalizing advantages within groups of sampled trajectories.<n> GRPO achieves solution quality within 2% of POMO, a strong AM-based multi-start baseline, while requiring no external baseline.<n>These results identify GRPO as a promising baseline-free alternative for NCO, particularly in settings where baseline-dependent training becomes fragile.
  arXiv  Detail & Related papers  (2026-06-09T02:18:30Z)
• Multi-Fidelity Flow Matching: Cascaded Refinement of PDE Solutions [6.144605787421899]
  Multi-Fidelity Flow Matching is a cascade refinement framework for PDE solutions.<n>We exploit this in Multi-Fidelity Flow Matching (MFFM), a cascade refinement framework for PDE solutions.<n>MFFM is a learned analog of multigrid refinement that reaches the finest grid in $L$ deterministic network evaluations per query.
  arXiv  Detail & Related papers  (2026-05-15T16:02:18Z)
• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• Neural Network Pruning via QUBO Optimization [0.08796261172196741]
  We propose a unified Hybrid QUBO framework that bridges the importance of estimation with global optimization.<n>Our formulation integrates gradient-aware sensitivity metrics into the linear term, while utilizing data-driven similarity in the quadratic term.<n> Experiments on the SIDD image denoising dataset demonstrate that the proposed Hybrid QUBO significantly outperforms both greedy Taylor pruning and traditional L1-based QUBO.
  arXiv  Detail & Related papers  (2026-04-07T13:16:40Z)
• When Right Meets Wrong: Bilateral Context Conditioning with Reward-Confidence Correction for GRPO [18.988527161000203]
  Group Relative Policy Optimization (GRPO) has emerged as an effective method for training reasoning models.<n>We present a contrastive reformulation of GRPO, showing that the GRPO objective implicitly maximizes the margin between the policy ratios of correct and incorrect samples.<n>We propose Bilateral Context Conditioning (BICC), a mechanism that allows the model to cross-reference successful and failed reasoning traces.
  arXiv  Detail & Related papers  (2026-03-13T16:25:02Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Not All Preferences Are Created Equal: Stability-Aware and Gradient-Efficient Alignment for Reasoning Models [52.48582333951919]
  We propose a dynamic framework designed to enhance alignment reliability by maximizing the Signal-to-Noise Ratio of policy updates.<n>SAGE (Stability-Aware Gradient Efficiency) integrates a coarse-grained curriculum mechanism that refreshes candidate pools based on model competence.<n> Experiments on multiple mathematical reasoning benchmarks demonstrate that SAGE significantly accelerates convergence and outperforms static baselines.
  arXiv  Detail & Related papers  (2026-02-01T12:56:10Z)
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization [17.694852175354555]
  We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values.<n>Experiments on Job-shop Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods.
  arXiv  Detail & Related papers  (2025-03-10T17:45:30Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Equivariant Deep Weight Space Alignment [54.65847470115314]
  We propose a novel framework aimed at learning to solve the weight alignment problem. We first prove that weight alignment adheres to two fundamental symmetries and then, propose a deep architecture that respects these symmetries.
  arXiv  Detail & Related papers  (2023-10-20T10:12:06Z)
• PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
  We present a novel unified bilevel optimization-based framework, textsfPARL, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning. Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design) by the lower optimal variable. Our empirical results substantiate that the proposed textsfPARL can address the alignment concerns in RL by showing significant improvements.
  arXiv  Detail & Related papers  (2023-08-03T18:03:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.