Soft-Rank Diffusion Beats Shuffle-Based AI Ordering by 10x
A new ICML 2026 paper reframes permutation generation by diffusing continuous soft ranks instead of shuffling cards, with sharp gains on long sorting and combinatorial tasks.
ProTakeaways
- New ICML 2026 paper introduces Soft-Rank Diffusion for learning distributions over permutations, arxiv.org/abs/2603.17353.
- Replaces abrupt riffle-shuffle noising with a reflected Brownian bridge over continuous soft ranks in [0,1]^n.
- Permutations are recovered at any timestep via argsort of the latent soft-rank vector.
- Introduces contextualized generalized Plackett-Luce (cGPL) denoisers for the reverse discrete step.
- Beats prior baselines on sorting and combinatorial optimization, especially on long sequences.
- Position accuracy heatmaps show cGPL and pointer variants far outperform SymmetricDiffusers baseline.
Diffusion models have become the default recipe for generating images, audio, and molecules, but permutations, orderings of n items, have stubbornly resisted the same treatment. A new ICML 2026 paper, Learning Permutation Distributions via Reflected Diffusion on Ranks, proposes Soft-Rank Diffusion, a rethink of how to noise and denoise orderings that swaps the usual card-shuffle process for a smooth walk through a continuous rank space.
The authors, Sizhuang He, Yangtian Zhang, Shiyang Zhang, and David van Dijk, show the method beats existing permutation-diffusion baselines on sorting and combinatorial optimization, with the biggest wins on long sequences where prior approaches tend to fall apart.
Why permutations break diffusion
The symmetric group S_n, the set of all orderings of n items, is where problems like ranking, learning-to-rank, and the traveling salesperson live. Modeling distributions over permutations matters for ranking search results, recommendations, and combinatorial optimization problems like TSP, and in many settings the goal is to build generative models that can sample orderings.
S_n is huge and discrete. It has n! elements and no natural Euclidean structure, so you cannot just add Gaussian noise the way image diffusion does. Recent permutation diffusion methods sidestep this by defining forward noising as shuffle-based random walks, such as riffle shuffles, and learning reverse transitions with Plackett-Luce variants. The resulting trajectories can be abrupt and increasingly hard to denoise as n grows. A riffle shuffle jumps between very different permutations at each step, so the denoiser has to make big, discrete decisions with little continuous signal to lean on. The bigger n gets, the worse this scales.