△ Mechanism confirmed, baseline not beaten 2026

Diversity-Weighted Leave-One-Out Policy Baseline

Implementation & benchmark of arXiv:2608.12443 — SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Usefulness7/10

Difficulty4/10

Novelty6/10

Optimization Stability Sample efficiency Accuracy Optimizer Rl Training Graph nn Probability Optimization Linear algebra Geometry

Source paper: SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization arXiv:2608.12443 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace the usual best-sample or uniform group baseline in sampled-policy training with a leave-one-out baseline weighted toward structurally dissimilar solutions. Diverse peers contribute more independent information, while near-duplicate trajectories contribute less redundant signal.

Formulas

$$\mathcal{J}(\theta)=\mathbb{E}_{\mathbf{s}\sim\pi_{\theta}}\bigl[c(\mathbf{s})\bigr]$$

$$d_{ij}=\lVert z_i-z_j\rVert_2^2,\qquad w_{ij}=(d_{ij}+\varepsilon)^p\quad(i\neq j)$$

$$b_i=\frac{\sum_{j\neq i}w_{ij}c_j}{\sum_{j\neq i}w_{ij}},\qquad A_i=b_i-c_i$$

$$\mathcal{L}_{\mathrm{SSPO}}=-\frac{1}{B}\sum_{i=1}^{B}\operatorname{stopgrad}(A_i)\sum_{t=0}^{T-1}\log\pi_{\theta}(s_{i,t}\mid s_{i,<t})$$

Mathematical statement

The paper defines the expected-cost objective $\mathcal{J}(\theta)=\mathbb{E}_{\mathbf{s}\sim\pi_\theta}[c(\mathbf{s})]$, where $\pi_\theta$ is an autoregressive policy, $\mathbf{s}$ is a complete sampled solution, and $c(\mathbf{s})$ is a cost to minimize. For a group of $B$ samples $\{\mathbf{s}_1,\ldots,\mathbf{s}_B\}$ from the same instance, construct an embedding $z_i\in\mathbb{R}^d$ for each solution from the encoder's existing node representations; the paper specifies Hadamard-product aggregation for TSP and mean-pooling for EFL/JSP, followed by centering. A concrete implementation of the stated pairwise-dissimilarity weighting is $d_{ij}=\|z_i-z_j\|_2^2$ and $w_{ij}=(d_{ij}+\varepsilon)^p$ for $i\neq j$, where $\varepsilon>0$ prevents zero weights and $p\geq0$ controls diversity emphasis. The leave-one-out baseline for sample $i$ is $b_i=\frac{\sum_{j\neq i}w_{ij}c_j}{\sum_{j\neq i}w_{ij}}$, with $c_j=c(\mathbf{s}_j)$. For minimization, the advantage is $A_i=b_i-c_i$: a sample cheaper than its structurally distinct peers has positive advantage. The adapted surrogate loss is $\mathcal{L}_{\mathrm{SSPO}}=-\frac{1}{B}\sum_{i=1}^B\operatorname{stopgrad}(A_i)\log\pi_\theta(\mathbf{s}_i)$, where $\log\pi_\theta(\mathbf{s}_i)=\sum_t\log\pi_\theta(s_{i,t}\mid s_{i,<t})$. Stop-gradient is required through costs, embeddings, distances, weights, and baselines.

Implementation notes

(1) Integrate this into the sampled-policy loss for a neural combinatorial solver or any grouped trajectory optimizer. For each input instance, sample $B$ complete solutions with the current policy and retain their per-sample costs $c_i$. At the same time, expose the encoder node states $h_{i,1},\ldots,h_{i,N}$ used while decoding. Build one solution embedding per sample: for TSP, aggregate representations of consecutive selected nodes using a Hadamard product and mean-pool the resulting edge features; for a simpler first implementation, mean-pool encoder states indexed by selected solution elements. For EFL/JSP, directly mean-pool representations of selected or assigned nodes. Center embeddings across the group with $z_i=\tilde z_i-B^{-1}\sum_k\tilde z_k$. (2) Compute pairwise squared distances $d_{ij}=\|z_i-z_j\|_2^2$, weights $w_{ij}=(d_{ij}+10^{-8})^p$ with $p=1$ initially, and baselines $b_i=\sum_{j\ne i}w_{ij}c_j/\sum_{j\ne i}w_{ij}$. Form $A_i=b_i-c_i$, optionally divide by the group cost standard deviation, detach all baseline quantities, and backpropagate $-B^{-1}\sum_iA_i\log\pi_\theta(\mathbf{s}_i)$. (3) The exact mathematical computations are centered embeddings, pairwise dissimilarities, normalized leave-one-out weights, and advantages; no learned baseline parameters are added. Sweep $p\in\{0,0.5,1,2\}$ and measure the effective baseline sample count $1/\sum_j\bar w_{ij}^2$, where $\bar w_{ij}=w_{ij}/\sum_{k\ne i}w_{ik}$. (4) First test on a small attention-based TSP solver on TSP-50, using the same batch size, number of samples, optimizer, and compute budget as REINFORCE with a uniform leave-one-out baseline and a best-sample baseline. Track gradient-norm variance, cost versus environment samples, training throughput, and final tour length. Success means lower gradient variance and reaching a fixed tour-quality threshold with fewer samples or training steps, while the additional pairwise $O(B^2d)$ computation does not materially increase wall-clock time.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built the diversity-weighted leave-one-out baseline and detached PyTorch SSPO loss. The mechanism checks matched predictions: p=0 recovered uniform LOO and effective count 5.0, distance ratios matched the squared-distance power law (16.0), and effective count fell from 4.0 to 2.00 as p increased from 0 to 2. The secondary categorical policy proxy did not show a win: diversity weighting increased gradient variance 3.47x versus uniform LOO, so this is mechanism-validated but not evidence of improved training.

Agent confidence: 9/10

Baseline: Uniform LOO proxy gradient variance 0.0466
Idea: Diversity-weighted proxy gradient variance 0.1616 (3.47x baseline); effective counts for p=0,0.5,1,2 were 4.000, 2.200, 2.010, 2.000

Limitations: No neural TSP-50 solver, multi-step training curve, wall-clock throughput, final tour quality, or GPU experiment was tested. The toy variance comparison used a four-action categorical policy and does not establish general RL performance.

How to run: python3 run_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.12443) Sep 2, 2026

No significant difference vs. the tuned baseline (+3.5%, p=0.5343, wins 2 / 8 paired seeds).

Benchmark: Dynamics forecasting
Model: rnn_small
Paired seeds: 8
Baseline mean: 0.0144
Idea mean: 0.0149
Effect (Δ): 0.0005 (+3.5%; negative = idea better)
Wins: 2 / 8 paired seeds
p-value: 0.5343 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±11.1%
Mechanism: Confirmed ✓
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

Only the registered dynamics track was tested because the idea requires grouped stochastic trajectories. The implementation is a Gaussian dynamics-prediction surrogate rather than a full combinatorial solver; no throughput or gradient-variance comparison was included, and the idea-side sweep used p=1 only with a duplicate nearby configuration.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 1, 2026 latest Failed ✗

Agent confidence: 9/10

The idea was implemented as a grouped Gaussian rollout objective on the registered dynamics track using the shared rnn_small architecture, with uniform leave-one-out as baseline and diversity-weighted leave-one-out as the only intervention. The mechanism signature was confirmed on trained-model representations, but the idea was slightly worse on test MSE and not significant, so it does not qualify as a win.

Baseline: Uniform LOO, tuned lr=0.01: test MSE 0.0144065906 ± 0.0059627913 over 8 seeds.
Idea: Diversity-weighted LOO p=1: test MSE 0.0149132591 ± 0.0066294191 over 8 seeds; delta +0.0005066685, permutation p=0.5343.

Benchmark result