Search papers, labs, and topics across Lattice.
This paper introduces Soft-Rank Diffusion, a novel discrete diffusion framework for learning permutation distributions by lifting permutations to a continuous latent space of soft ranks, enabling smoother diffusion trajectories compared to shuffle-based methods. They propose contextualized generalized Plackett-Luce (cGPL) denoisers for the reverse process, improving expressivity for sequential decision structures. Experiments on sorting and combinatorial optimization tasks demonstrate that Soft-Rank Diffusion outperforms existing permutation diffusion methods, especially in long-sequence and sequential settings.
By mapping permutations to a continuous space of "soft ranks," this new diffusion approach makes learning permutation distributions far more tractable, especially for long sequences.
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.
