Learning Permutation Distributions via Reflected Diffusion on Ranks

• URL: http://arxiv.org/abs/2603.17353v1
• Date: Wed, 18 Mar 2026 04:28:24 GMT
• Title: Learning Permutation Distributions via Reflected Diffusion on Ranks
• Abstract summary: We propose a discrete diffusion framework that replaces shuffle-based corruption with a structured soft-rank forward process.<n>Experiments show that Soft-Rank Diffusion consistently outperforms prior diffusion baselines.
• Score: 6.107905126312009
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.

Related papers

• Variational Learning for Insertion-based Generation [50.15012125719375]
  We introduce a probabilistic framework for learning insertion order in variable-length insertion models.<n>We propose the Insertion Process (IP), a generative model that jointly learns where to insert, what to insert, and when to terminate.
  arXiv  Detail & Related papers  (2026-06-01T11:59:46Z)
• Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching [46.08543848104545]
  In this work, we extend adjoint-based trajectory optimization methods to discrete domains.<n>We propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion.
  arXiv  Detail & Related papers  (2026-05-29T07:04:42Z)
• Learning Unbiased Permutations via Flow Matching [22.51828421737954]
  PermFlow is a conditional flow matching framework for learning permutations.<n>It captures multimodal permutation distributions rather than collapsing them to a single mode.<n>It achieves high accuracy on unambiguous inputs and recovers both valid permutations under ambiguity.
  arXiv  Detail & Related papers  (2026-05-16T02:10:35Z)
• Tracking High-order Evolutions via Cascading Low-rank Fitting [10.036945747389058]
  High-order dynamics has emerged as a promising frontier in generative modeling.<n>We introduce cascading low-rank fitting, an ordinary differential equation inspired method that approximates successive derivatives.<n>We prove that if the initial difference is linearly decomposable, the generic ranks of high-order derivatives are guaranteed to be monotonically non-increasing.
  arXiv  Detail & Related papers  (2026-04-13T04:39:49Z)
• Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization [20.63685754619351]
  We use a large language model (LLM)-guided program evolution framework to discover an effective shuffling rule for without replacing SGD.<n>We show that block reshuffling strictly reduces prefix-gradient variance constants within the unified shuffling, yielding provable improvements over random reshuffling under mild conditions.<n>We also show that paired reversal symmetrizes the epoch map and cancels the leading order-dependent second-order term, reducing order sensitivity from quadratic to cubic in the step size.
  arXiv  Detail & Related papers  (2026-03-31T21:40:43Z)
• Differentiable Knapsack and Top-k Operators via Dynamic Programming [10.762219154434709]
  Knapsack and Top-k operators are useful for selecting discrete subsets of variables.<n>We propose a unified framework casting these operators as dynamic programs, and derive differentiable relaxations.<n>On the algorithmic side, we develop efficient algorithms supporting both deterministic and forward passes.<n>On the theoretical side, we prove that Shannon entropy is the unique regularization choice yielding permutation-equivariant operators.
  arXiv  Detail & Related papers  (2026-01-29T14:25:35Z)
• An Elementary Approach to Scheduling in Generative Diffusion Models [55.171367482496755]
  An elementary approach to characterizing the impact of noise scheduling and time discretization in generative diffusion models is developed.<n> Experiments across different datasets and pretrained models demonstrate that the time discretization strategy selected by our approach consistently outperforms baseline and search-based strategies.
  arXiv  Detail & Related papers  (2026-01-20T05:06:26Z)
• Spanning Tree Autoregressive Visual Generation [51.7635842702602]
  We present Spanning Tree Autoregressive (STAR) modeling, which can incorporate prior knowledge of images, such as center bias and locality, to maintain sampling performance.
  arXiv  Detail & Related papers  (2025-11-21T09:45:17Z)
• Permutation Randomization on Nonsmooth Nonconvex Optimization: A Theoretical and Experimental Study [15.960271016276447]
  gradient-based networks that incorporate randomization often showcase superior performance on complex optimization.<n>Permutation randomization disrupts the behavior of gradient-baseds.<n>Permutation randomization can preserve the convergence of the underlying baseline.
  arXiv  Detail & Related papers  (2025-05-16T23:28:38Z)
• A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond [7.325166704015515]
  We aim to provide a unified convergence analysis for permutation-based Gradient Descent (SGD)<n>We categorize existing permutation-based SGD algorithms into four categories: Arbitrary Permutations, Independent Permutations, One Permutation and Dependent Permutations.<n>We develop a unified framework for permutation-based SGD with arbitrary permutations of examples, incorporating all the aforementioned representative algorithms.
  arXiv  Detail & Related papers  (2025-01-27T15:07:02Z)
• SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups [14.925722398371498]
  We introduce a novel discrete diffusion model that simplifies the task of learning a complicated distribution over $S_n$.<n>We provide empirical guidelines for selecting the diffusion length based on the theory of random walks on finite groups.<n>Our model achieves state-of-the-art or comparable performances on solving tasks including sorting 4-digit images, jigsaw puzzles, and traveling salesman problems.
  arXiv  Detail & Related papers  (2024-10-03T19:37:40Z)
• Diffusion Forcing: Next-token Prediction Meets Full-Sequence Diffusion [61.03681839276652]
  Diffusion Forcing is a new training paradigm where a diffusion model is trained to denoise a set of tokens with independent per-token noise levels.<n>We apply Diffusion Forcing to sequence generative modeling by training a causal next-token prediction model to generate one or several future tokens.
  arXiv  Detail & Related papers  (2024-07-01T15:43:25Z)
• TERM Model: Tensor Ring Mixture Model for Density Estimation [48.622060998018206]
  In this paper, we take tensor ring decomposition for density estimator, which significantly reduces the number of permutation candidates. A mixture model that incorporates multiple permutation candidates with adaptive weights is further designed, resulting in increased expressive flexibility. This approach acknowledges that suboptimal permutations can offer distinctive information besides that of optimal permutations.
  arXiv  Detail & Related papers  (2023-12-13T11:39:56Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  We propose a new accelerated first-order method called clipped-SSTM for smooth convex optimization with heavy-tailed distributed noise in gradients. We prove new complexity that outperform state-of-the-art results in this case. We derive the first non-trivial high-probability complexity bounds for SGD with clipping without light-tails assumption on the noise.
  arXiv  Detail & Related papers  (2020-05-21T17:05:27Z)

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.