Research map / Image generation / Fast diffusion sampling
SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SymmetricDiffusers, a discrete diffusion model over the finite symmetric group S_n using riffle-shuffle forward noising and a generalized Plackett-Luce reverse transition, evaluated on 4-digit MNIST sorting, jigsaw puzzles, and TSP.
Problem
Learning probability distributions over the finite symmetric group S_n is intractable due to factorial size and discreteness, and existing discrete diffusion models assume fixed small vocabularies and cannot handle it.
Approach
Discrete diffusion on S_n with riffle shuffles as the forward process (chosen via mixing-time theory), a generalized Plackett-Luce (GPL) reverse transition proven to be universal and more expressive than PL, and a theoretically motivated denoising schedule that merges reverse steps.
Key results
- On 4-digit MNIST sorting with n=200, achieves Kendall-Tau 0.453 and accuracy 0.1% versus Error-free DiffSort's 0.002 and 0.0%; at n=100 Kendall-Tau 0.641 vs 0.140.
- On Noisy MNIST jigsaw 5x5, Kendall-Tau 0.2853 and accuracy 0.00 vs Gumbel-Sinkhorn 0.2430; on 6x6 Kendall-Tau 0.1208 vs 0.1755 for Gumbel-Sinkhorn (Gumbel-Sinkhorn wins there).
- On TSP-50 the method reaches 0.41% optimality gap, behind DIFUSCO's 0.10% and comparable to GCN's 3.10%-level baselines (far better than GCN).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SymmetricDiffusers instead of Error-free DiffSort | 4-digit MNIST sorting · sequence length 52 | Kendall-Tau: 0.170 -> 0.786 | Helped |
| Use SymmetricDiffusers instead of DiffSort | 4-digit MNIST sorting · sequence length 200 | Kendall-Tau: 0.107 -> 0.453 | Helped |
| Use SymmetricDiffusers instead of Gumbel-Sinkhorn Network | Noisy MNIST jigsaw · 6×6 | Correct (%): 14.91 -> 18.54 | Helped |
| Use SymmetricDiffusers instead of Gumbel-Sinkhorn Network | CIFAR-10 jigsaw · 4×4 | Kendall-Tau: 0.4016 -> 0.2518 | Hurt |
| Use SymmetricDiffusers instead of DIFUSCO | TSP · TSP-20 | Optimality Gap (%): 1.07* -> 0.18 | Helped |
| Use SymmetricDiffusers instead of DIFUSCO | TSP · TSP-50 | Optimality Gap (%): 0.10 -> 0.41 | Hurt |
| Replace GPL with inverse riffle shuffle (IRS) (ablation) | SymmetricDiffusers with greedy decoding · sorting 52 four-digit MNIST images | Kendall-Tau: 0.799 -> 0.390 | Hurt |
| Replace beam search with greedy decoding (ablation) | GPL reverse transition · sorting 52 four-digit MNIST images | Accuracy (%): 27.4 -> 24.4 | Hurt |
| Replace GPL with PL while using beam search (ablation) | SymmetricDiffusers · sorting 52 four-digit MNIST images | Accuracy (%): 27.4 -> 26.4 | Hurt |
| Use inverse transposition (IT) with random-transposition forward diffusion (ablation) | SymmetricDiffusers · sorting 52 four-digit MNIST images | Kendall-Tau | Hurt |
| Use inverse insertion (II) with random-insertion forward diffusion (ablation) | SymmetricDiffusers · sorting 52 four-digit MNIST images | Kendall-Tau | Hurt |
Surprising findings
- Discrete diffusion baselines such as SEDD reach only 88.75-95.47% accuracy on a single-permutation toy task, while the proposed method reaches 100%.
- Gumbel-Sinkhorn outperforms the proposed method on the 6x6 Noisy MNIST jigsaw Kendall-Tau and on CIFAR-10 4x4 metrics.
Limitations
- Scalability to larger n remains limited, as the authors acknowledge.
- Performance on 5x5 and 6x6 jigsaw and TSP-50 is not uniformly best; Gumbel-Sinkhorn and DIFUSCO are stronger on some settings.
- Exact GPL decoding is intractable, requiring approximate hierarchical beam search.
Experimental setup
Datasets: MNIST Noisy MNIST CIFAR-10 TSP-20 TSP-50
Benchmarks: 4-digit MNIST sorting Noisy MNIST jigsaw CIFAR-10 jigsaw TSP-20 TSP-50
Metrics: Kendall-Tau accuracy correct (%) RMSE MAE tour length optimality gap
Baselines: Gumbel-Sinkhorn Network DiffSort Error-free DiffSort Concorde LKH-3 2-Opt GCN DIFUSCO SEDD
Builds on: Plackett-Luce GSR riffle shuffle model SEDD DiffSort Gumbel-Sinkhorn
Closest papers by meaning
- Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.89)
- Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.87)
- Efficient Diffusion Models for Symmetric Manifolds (ICML 2025 · similarity 0.86)
- A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization (ICML 2024 · similarity 0.85)
- DisCo-Diff: Enhancing Continuous Diffusion Models with Discrete Latents (ICML 2024 · similarity 0.85)
- Align Your Steps: Optimizing Sampling Schedules in Diffusion Models (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.