The finite symmetric group S_n provides a natural domain for permutations, yet learning probability distributions on S_n is challenging due to its factorially growing size and discrete, non-Euclidean structure. Recent permutation diffusion methods define forward noising via shuffle-based random walks (e.g., riffle shuffles) and learn reverse transitions with Plackett-Luce (PL) variants, but the resulting trajectories can be abrupt and increasingly hard to denoise as n grows. We propose Soft-Rank Diffusion, a discrete diffusion framework that replaces shuffle-based corruption with a structured soft-rank forward process: we lift permutations to a continuous latent representation of order by relaxing discrete ranks into soft ranks, yielding smoother and more tractable trajectories. For the reverse process, we introduce contextualized generalized Plackett-Luce (cGPL) denoisers that generalize prior PL-style parameterizations and improve expressivity for sequential decision structures. Experiments on sorting and combinatorial optimization benchmarks show that Soft-Rank Diffusion consistently outperforms prior diffusion baselines, with particularly strong gains in long-sequence and intrinsically sequential settings.
Figures & tables
Figure 1: Soft-Rank Diffusion. We define the forward diffusion by relaxing each item’s rank to a continuous soft-rank variable and evolving these soft ranks in a reflected diffusion process [ 19 ] . At each time t , the soft ranks induce a discrete ordering by simple sorting, thereby yielding a forward process in permutation space. For reverse sampling, we couple a discrete denoiser in permutation space (predicting a clean permutation from Xt ) with an auxiliary continuous update: we lift the predicted permutation to a grid-aligned soft-rank vector Z^0 , sample an intermediate latent Zs for s<t from a conditional reverse kernel p(Zs∣Zt,Z^0,Z1) , and map back to permutation space by sorting Zs , thus stepping backward in time.
Figure 2: Sampling in PL/GPL/cGPL. (a) PL and GPL. In PL, each item is assigned a single scalar score; sampling a permutation amounts to repeatedly sampling from the same score vector without replacement, masking selected items and renormalizing at each step. In GPL, each item is assigned a length- N score vector, yielding position-specific logits: at step i we sample according to the i -th column of the score matrix (after masking previously selected items), proceeding sequentially from i=1 to N . (b) cGPL. In cGPL, each item is assigned a position-dependent score vector dynamically . Sampling proceeds autoregressively : the score vector at later positions depends on the outcomes sampled at preceding positions. As in GPL, we apply masking and subsequent renormalization to obtain a valid probability distribution over the remaining items.
Figure 3: Exact-match accuracy and relative improvement versus SymmetricDiffusers as a function of sequence length (N). Panel 3(a) shows accuracy on a logit scale. Panel 3(b) reports the accuracy ratio of Soft-Rank Diffusion relative to SymmetricDiffusers on a log scale. Starred points mark sequence lengths where SymmetricDiffusers attains zero accuracy; the corresponding ratios are undefined and are clipped to the top of the plotted range for visualization.
Method
TSP-20
TSP-50
L(Tour)↓
Gap ↓
L(Tour)↓
Gap ↓
SymmetricDiffusers with GPL [ 38 ]
5.4342
0.4169
12.8525
1.2618
Soft-Rank Diffusion with cGPL Ours
3.8732
0.0079
5.7336
0.0078
Soft-Rank Diffusion with Pointer-cGPL Ours
3.8557
0.0034
5.7157
0.0047
Table 2: TSP performance on TSP-20 and TSP-50. We report tour length L(Tour) and the optimality gap (both lower is better).
Method
Metric
Grid Size n×n
3×3 ( N=9 )
4×4 ( N=16 )
8×8 ( N=64 )
SymmetricDiffusers with GPL [ 38 ]
Kendall - Tau ↑
0.8312
0.6101
0.0250
Accuracy ↑
0.7002
0.2172
0.0000
Correctness ↑
0.8662
0.6753
0.0501
Soft-Rank Diffusion with cGPL Ours
Kendall - Tau ↑
0.9494
0.9320
0.2521
Accuracy ↑
0.9221
0.8752
0.0924
Table 3: CIFAR-10 jigsaw benchmark. Bold marks the best value per (metric, n ). All methods use a 7-layer Transformer backbone with the same hidden width.
Figure 4: Per-position accuracy heatmaps on 8×8 CIFAR-10 jigsaw. Each cell is the fraction of test samples where that grid position is correctly assigned. Left: SymmetricDiffusers (mean 5.0% ). Middle: cGPL (mean 28.5% ). Right: Pointer-cGPL (mean 52.3% ). Random baseline 1/64≈1.6% .
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Sequence Length
Steepness
Sorting Network
Loss Weight
Learning Rate
9
34
odd even
1.00
10−4
15
25
odd even
0.10
10−4
32
124
odd even
0.10
10−4
52
130
bitonic
0.10
10−3.5
75
135
bitonic
0.10
10−3.5
100
140
bitonic
0.10
10−3.5
Appendix
Table 4: Hyperparameters for Error-Free Diffsort on 4-digit MNIST sorting.
Decoder
Init Distribution
Perm Acc (%)
Kendall τ
Prop Correct (%)
cGPL
Uniform
86.67
0.9303
93.93
Gaussian
86.96
0.9317
94.08
Pointer-cGPL
Uniform
87.35
0.9365
94.43
Gaussian
86.94
0.9347
94.38
Appendix
Table 5: Matched train/eval pref on CIFAR10 jigsaw ( n=4 , σ=0.5 , T=5 ). Both Uniform and Gaussian reference distributions yield essentially identical performance, indicating the choice of pref has negligible impact on training.
Decoder
Train pref
Eval: Uniform
Eval: Gaussian
cGPL
Uniform
86.67 / 93.93 / τ=0.930
87.09 / 94.08 / τ=0.931
Gaussian
86.71 / 94.01 / τ=0.932
86.96 / 94.08 / τ=0.932
Pointer-cGPL
Uniform
87.35 / 94.43 / τ=0.937
87.33 / 94.51 / τ=0.937
Gaussian
87.17 / 94.31 / τ=0.935
86.94 / 94.38 / τ=0.935
Appendix
Table 6: Mismatched train/eval pref on CIFAR10 jigsaw ( n=4 , σ=0.5 , T=5 ). Each cell shows Perm Acc / Prop Correct / Kendall τ . Performance is preserved even when training and evaluation use different reference distributions, confirming the Brownian bridge formulation drives z toward z0 regardless of starting distribution.
[0,1]N (ours)
Birkhoff polytope BN
Orthogonal group O(N)
Dimension
N
(N−1)2
N(N−1)/2
Dynamics
Independent reflected Brownian bridges with closed-form transition kernels
Table 7: Comparison of three continuous relaxations of permutations. The soft-rank relaxation [0,1]N used by Soft-Rank Diffusion has linear dimension and admits independent closed-form Brownian-bridge dynamics, while Birkhoff- and O(N) -based relaxations require coupled, more expensive constructions.
Figure 5: Model architecture and Pointer-cGPL parameterization for permutation generation. We adopt a standard encoder–decoder Transformer backbone [ 34 ] . In the vanilla cGPL parameterization, the decoder states are mapped to logits via a linear output head (yielding a distribution over candidates at each step). In contrast, Panel 5(b) illustrates Pointer-cGPL , where a bi-affine compatibility module scores each encoded item representation against the current decoder state, producing step-wise logits over the input items that can be interpreted as a pointer distribution.
Figure 6: Accuracy ratio (green; Soft-Rank Pointer accuracy / SymmetricDiffusers accuracy) and runtime ratio (red; Soft-Rank Pointer wall-clock time / SymmetricDiffusers wall-clock time) across problem scales. The accuracy advantage grows superlinearly with N , reaching 4.0× at N=16 and becoming unbounded at N=64 (*baseline accuracy is 0%). Runtime overhead remains moderate: with KV cache optimization (solid red), the slowdown is 1.0× – 4.3× , while the shaded region shows the speedup across diffusion steps (up to 1.55× at N=64 ). The accuracy gains far outpace the runtime cost at every scale.
Figure 7: Patch-wise Manhattan displacement distributions on 8×8 CIFAR-10 jigsaw. Manhattan displacement is the grid distance between a patch’s predicted and correct positions. Dashed gray = random baseline (mean 5.2 ). Left: SymmetricDiffusers (mean 3.8 ). Middle: cGPL (mean 2.8 ). Right: Pointer-cGPL (mean 1.6 ).
Method
3×3
4×4
8×8
SymmetricDiffusers
28.0s
21.6s
36.3s
cGPL, w/o cache
31.4s
41.5s
216.6s
cGPL, w/ cache
26.3s
31.4s
131.7s
speedup
1.19 ×
1.32 ×
1.64 ×
Pointer-cGPL, w/o cache
31.6s
51.6s
242.3s
Pointer-cGPL, w/ cache
26.7s
36.7s
156.7s
Appendix
Table 9: Wall-clock inference time. Single H100 GPU, 10,000 test samples.
Learning permutations is fundamental to sorting, ranking, and matching, but existing differentiable methods based on entropy-regularized Sinkhorn produce a single softened solution and collapse under ambiguity. We present PermFlow, a conditional flow matching framework that operates directly on the affine subspace of matrices with unit row and column sums. A closed-form tangent-space projector preserves these constraints exactly along every trajectory, by construction rather than through iterative correction, and a nearest-target coupling routes distinct noisy initializations toward distinct valid permutations. The result is a model that captures multimodal permutation distributions rather than collapsing them to a single mode. On a range of problems, PermFlow achieves high accuracy on unambiguous inputs and recovers both valid permutations under ambiguity.
Yimeng Min, Carla P. Gomes
Department of Computer Science, Cornell University, Ithaca, NY, USA
Many learning problems require uncovering a hidden ordering that reveals structure in unordered data, such as monotonicity in sorting or spatial continuity in jigsaw reconstruction. In these settings, permutations can be learned as latent operators by optimizing objectives defined directly on the reordered output, often without access to ground-truth orderings. Differentiable relaxations such as Gumbel-Sinkhorn make this approach practical by approximating permutation matrices with doubly stochastic matrices. However, learning from structure without supervision induces a non-uniform uncertainty: some assignments become confident early, while others remain ambiguous. Existing methods control this process using a single global temperature, forcing all assignments to sharpen or diffuse simultaneously and leading to instability at scale. We introduce an entropy-adaptive formulation of Gumbel-Sinkhorn that locally modulates temperature based on assignment uncertainty. This allows confident assignments to discretize early while preserving exploration where uncertainty remains. Across sorting and jigsaw reconstruction tasks and in routing-style settings, adaptive entropy control improves training stability and final permutation quality relative to fixed-temperature baselines, particularly as problem size and assignment ambiguity increase.
Ran Eisenberg, Ofir Lindenbaum
Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel. · Faculty of Engineering, Bar-Ilan
Learning to rank (LTR) is one of the core tasks in Machine Learning. Traditional LTR models have made great progress, but nearly all of them are implemented from discriminative perspective. In this paper, we aim at addressing LTR from a novel perspective, i.e., by a deep generative model. Specifically, we propose a novel denoise rank model, DenoiseRank, which noises the relevant labels in the diffusion process and denoises them on the query documents in the reverse process to accurately predict their distribution. Our model is the first to address traditional LTR from generative perspective and is a diffusion method for LTR. Our extensive experiments on benchmark datasets demonstrated the effectiveness of DenoiseRank, and we believe it provides a benchmark for generative LTR task.
Ying Wang, Preslav Nakov, Shangsong Liang
Sun Yat-sen University, Guangzhou, China · MBZUAI, Abu Dhabi, UAE