SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups

Q3: Why are experiments limited to TSP-20 instances rather than including larger TSP instances? TSP-20 is considered a very small problem size. This experiment is the most interesting to me and it would be interesting to see how this method performs on larger TSP instances. Can you provide an additional comparison on TSP-100?

A3: We are running larger-scale TSP experiments like TSP-50 and TSP-100 right now, but it takes much longer to train the models compared to other experiments. Since there is only limited time for the rebuttal period, we will post a follow-up response if our experiments finish before the discussion deadline.

We would like to point out that the current literature on permutation learning has never done experiments on TSPs. As a general permutation learning model, our model is certainly different from models specifically designed for the TSP. The TSP is just one application, and our model has been verified to be much more effective than previous methods on other tasks like the jigsaw puzzle and sorting 4-digit MNIST numbers. Previous work, such as the baseline methods in our experiments, can only learn permutations up to a small sequence length. For example, for the sort 4-digit MNIST numbers experiment, previous methods are only effective for sequences of length up to $32$, while our method has promising results for sequence lengths up to $200$ and outperforms the baseline methods significantly under longer sequence lengths. Our method already provide a substantial improvement over previous methods in the field of permutation learning.

Q4: Can your method be combined with the framework proposed in [1] to solve TSP using diffusion models without requiring data from classical solvers?

A4: Thanks for pointing out the reference! The framework proposed in [1] offers a compelling approach to unsupervised neural combinatorial optimization. In particular, [1] uses an energy $H$ as signals to the quality of a solution, and use a tractable Joint Variational Upper Bound of the commonly used reverse KL divergence to bypass the need for exact likelihood evaluations. Diffusion models can be naturally incorporated into the Joint Variational Upper Bound. Specifically, our method can certainly be combined with the framework in [1] as long as we pick a reverse transition such that the Shannon entropy $S(q_{\theta}(X_{t-1}|X_t))$ in Eq.(6) of [1] is tractable. Solving the TSP without requiring data from classical solvers is definitely an exiciting research direction, and combining our method and [1] could be an interesting future work. We have discussed [1] in the newly uploaded version of our paper (line 517 on page 10, colored blue).

References

[1] Sanokowski, Sebastian, Sepp Hochreiter, and Sebastian Lehner. "A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization." Forty-First International Conference on Machine Learning.

[2] Austin et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

Thank you for the insightful and constructive comments. We appreciate your positive feedback and address the questions below.

Q1: How do the proposed reverse and forward processes compare to naive discrete denoising diffusion models? What is the difference between your method and other differentiable sorting baselines in Tab. 1?

A1: Existing discrete diffusion models assume token-wise conditional independence when modeling the reverse transition distributions. This assumption does not hold in learning permutations since different components of $X_{t-1}$ are not independent conditioned on $X_t$ in the reverse process, and they have to satisfy the constraint of permutations (i.e., being one of the vertices of Birkhoff Polytope). Therefore, if we have a distribution over $[n]^n$, the denoising step in standard diffusion models would lead to noisy data $X_{t-1}$ that is not an exact permutation. Furthermore, it is also computationally expensive to project it to a distribution over $S_n$.

Discrete diffusion methods like D3PM [2], which model categorical distributions, are also unsuitable for $S_n$. These methods require explicit matrix multiplications involving $n!\times n!$ transition matrices. While D3PM uses dense transition matrices such as uniform or discretized Gaussian distributions, performing dense matrix multiplications at this scale is impractical.

Our proposed method addresses these challenges by defining efficient, customized transition distributions through card-shuffling methods. This approach avoids explicit matrix multiplications by directly simulating the forward process using the efficient operations of shuffling methods. Essentially, the shuffling methods induce “sparse” transitions on $S_n$, resolving the efficiency issues inherent in existing discrete diffusion models. As our framework is fundamentally different and existing frameworks are infeasible for $S_n$, our baselines focus on comparing different shuffling methods within our framework.

The differentiable sorting baselines in Table 1 represent the predominant approach in the literature for learning permutations. They define differentiable approximations to sorting operations, enabling optimization over permutations. In contrast, our method uses discrete diffusion models to learn a distribution over $S_n$ via forward noising and reverse denoising processes—a fundamentally different paradigm from differentiable sorting. Additionally, our method significantly outperforms differentiable sorting methods on longer sequence lengths, marking a substantial improvement in permutation learning.

Q2: What is the sequence length $n$ in the four-digit MNIST dataset?

A2: The sequence length $n$ is the number of four-digit MNIST numbers that we are sorting, which is also the $n$ in $S_n$. We have clarified this on line 423 (colored blue) of the newly uploaded paper.

References

[1] Sanokowski, Sebastian, Sepp Hochreiter, and Sebastian Lehner. "A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization." Forty-First International Conference on Machine Learning.

[2] Austin et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

I thank the authors for their detailed answers and I have raised my score to 8. I am glad to hear that the authors are conducting further experiments on TSP and I am curious to see what comes out in the large-scale TSP experiments!

I have a follow-up question: You are writing that the framework from Sanokowski et al. 2024 can be used "as long as we pick a reverse transition such that the Shannon entropy $S(q_\theta(X_{t-1}|X_t))$ is tractable". What do you exactly mean by that? I see that in Sanokowski et al. 2024 $q_\theta(X_{t-1}|X_t)$ is chosen so that $S(q_\theta(X_{t-1}|X_t))$ can be calculated exactly. But it is not a strict requirement as you can alternatively Monte Carlo estimate the entropy with $S(q_\theta(X_{t-1}|X_t)) = - E_{X_{t-1} \sim q_\theta(X_{t-1}|X_t)} [ \log q_\theta(X_{t-1}|X_t) ]$, which is possible as long as $q_\theta(X_{t-1}|X_t)$ can be evaluated. So my question reduces to whether your proposed reverse diffusion transitions $q_\theta(X_{t-1}|X_t)$ can be evaluated?

For me what you write down in L. 350 ff. "Note that although we may not have the analytical form of $q(X_t|X_{t-1})$, we can draw samples from it." would rather be a show stopper of the framework from Sanokowski et al. 2024, because $q(X_t|X_{t-1})$ must be analytically available.

Q3: Note that $S_n\subseteq [n]^n$. If the input data comprises of only permutations, then the network should learn to sample from a distribution whose samples are permutations and the standard framework of diffusion models applies.

The authors also mention that representing a transition matrix over $S_n$ requires $n!\times n!$ sized matrix. However, the authors themselves give a succinct description/representation of the forward transition matrix in the paper. The authors should elaborate why it is not possible to use this representation algorithmically.

A3: It is true that we can view each permutation in $S_n$ as a sequence in $[n]^n$. However, standard diffusion models assume token-wise conditional independence when modeling the reverse transition distributions. This assumption does not hold in learning permutations since different components of $X_{t-1}$ are not independent conditioned on $X_t$ in the reverse process, and they have to satisfy the constraint of permutations (i.e., being one of the vertices of Birkhoff Polytope). Therefore, if we have a distribution over $[n]^n$, the denoising step in standard diffusion models would lead to noisy data $X_{t-1}$ that is not an exact permutation. Furthermore, it is also computationally expensive to project it to a distribution over $S_n$.

Discrete diffusion methods like D3PM [4], which model categorical distributions, are also unsuitable for $S_n$. These methods require explicit matrix multiplications involving $n!\times n!$ transition matrices. While D3PM uses dense transition matrices such as uniform or discretized Gaussian distributions, performing dense matrix multiplications at this scale is impractical.

Our proposed method addresses these challenges by defining efficient, customized transition distributions through card-shuffling methods. This approach avoids explicit matrix multiplications by directly simulating the forward process using the efficient operations of shuffling methods. Essentially, the shuffling methods induce “sparse” transitions on $S_n$, resolving the efficiency issues inherent in existing discrete diffusion models. As our framework is fundamentally different and existing frameworks are infeasible for $S_n$, our baselines focus on comparing different shuffling methods within our framework.

Thanks for pointing out the related references [2,3]. We have acknowledged their contributions in the updated paper (lines 84–86 on page 2, marked in blue). Work [2] extends D3PM with a continuous-time Markov chain approach but still involves costly computations tied to the transition distribution, making it challenging to apply directly to $S_n$. Work [3] models a diffusion process on sequences in $\mathcal{X}^L$, changing one index of the sequence at each forward step.

Applying [3] to $S_n$ would involve modeling sequences in $[n]^n$ using [3], with $X_0$ as the data distribution of the permutations. While Glauber dynamics in [3] avoids the conditional independence issue mentioned earlier, one caveat is that $X_t$ for $t\geq 1$ would most likely lie outside $S_n$. In the reverse process, if learning is imperfect, the final sampled sequence may not be a permutation, necessitating projection onto $S_n$, which is again a non-trivial task. Currently, the code for [3] is not publicly available. We find their approach intriguing and look forward to experimenting with GGM once the code is released.

Q4: In proposition 1, should it be changed to "the GPL distribution can represent a delta distributions in the limit" instead of "exactly"?

A4: You are correct since we are using $-\infty$ for the logits. We have reorganized the expressiveness results in the newly uploaded version of the paper. The original Proposition 1 is now separated into Proposition 1 (colored blue) in the main paper and Lemma 4 in Appendix E. The expressiveness result for GPL is stated as Theorem 2 (colored blue) in the main paper and proved in Appendix E.

References

[1] Generating a random permutation with random transpositions by Diaconis and Shahshahani

[2] Simplified and Generalized Masked Diffusion for Discrete Data by Shi et al.

[3] Glauber Generative Model: Discrete Diffusion Models via Binary Classification by Varma et al.

[4] Austin et al. "Structured denoising diffusion models in discrete state-spaces." Advances in Neural Information Processing Systems 34 (2021): 17981-17993.

Thank you for the insightful and constructive comments. We appreciate your positive feedback and address the questions below.

Q1: Experiments are very small scale, comprising of sorting 4 digit MNIST, solving 20 node TSPs and solving jigsaw puzzles of CIFAR-10 data.

A1: We acknowledge the concern about the experiment scale. However, scalability remains a highly challenging aspect in permutation learning. Previous methods in the literature are generally limited to smaller permutation lengths. For example, for the sort 4-digit MNIST numbers experiment, previous methods are only effective for sequences of length up to $32$, while our method has promising results for sequence lengths up to $200$ and beats the baseline methods significantly in these longer sequence lengths. Furthermore, none of the previous permutation learning methods have tackled TSP experiments. While our model is not specifically designed for TSP tasks, it represents a substantial improvement over existing general-purpose permutation learning methods.

To test our framework on more complicated and larger tasks, we are conducting additional experiments, including solving jigsaw puzzles on ImageNet and larger-scale TSP tasks (e.g., TSP-50). However, these experiments require extensive hyperparameter tuning and significantly longer training times, particularly for larger TSP instances. Due to the limited time during the rebuttal period, we will provide a follow-up response if these experiments complete before the discussion deadline.

Q2: The reverse process for random transposition is not very expressive. Suppose the reverse transposition is $(1,2)$ with probability $0.5$ and $(2,3)$ with probability $0.5$. This simple distribution cannot be expressed using the model.

A2: It is true that the inverse transposition model cannot represent the specific distribution you described. However, inverse transposition is only one of the many reverse process methods we proposed. Importantly, we demonstrate that the GPL distribution, which is the best-performer in our experiments, can approximate your distribution to any precision. The distribution you mentioned on $S_3$ is

Consider the following score parameters for GPL

where $C$ is some arbitrary large positive number. Then we have

as $C\\to\\infty$. We also have

In fact, during the rebuttal period, we proved that the reverse process using GPL is expressive enough to represent any distribution over $S_n$, which is a significant result regarding the expressiveness of the reverse process. Please refer to Theorem 2 (colored blue) and Appendix E of the newly uploaded paper. We also provide an example illustrating the idea we used in the proof in Figure 3 and lines 895 to 904 in Appendix E.

Finally, for the empirical performance of these different reverse methods, please refer to the ablation studies (Table 3 and 5) in the paper.

Thank you for the response. I appreciate the proof regarding the GPL distribution and regarding the scale of the experiments. However, I have some further concerns with response A3. The authors quote that the original D3PM work assumed factored denoising and thus the denoising trajectory cannot be ensured to be a permutation.

1. While this is true, there are many other proposals for diffusion models which do not assume factorization. For instance SEDD ([1a]) does not assume factorization of the reverse distribution and would be a valid baseline for the current work.

2. When modeling distributions over $[n]^n$ it is not necessary that the entire trajectory is restricted to $S_n$. It is sufficient if the algorithm outputs a permutation at time $0$.

3. I also want to point out that D3PM style models have been shown to be capable of planning (such as generating SuDoKus, Solving SAT problems), where factorization certainly does not hold and there are lots of structure and constraints in the output. I refer to [2a], [3a] and references in the paper. Even language modeling and image generation involve structure and constraints, where factorization does not hold, yet D3PM based models have been successful.

4. Regarding Glauber Generative model [3], I see that their algorithm has been clearly described in the paper and can be implemented in a straightforward manner.

I am not satisfied with the baselines used in this work and the absence of other discrete diffusion based approaches.

[1a] Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution

[2a] BEYOND AUTOREGRESSION: DISCRETE DIFFUSION FOR COMPLEX REASONING AND PLANNING

[3a] LayoutDM: Discrete Diffusion Model for Controllable Layout Generation

Thank you for your response, and we definitely agree that intuitions should be backed up by experiments. We have tested our model against SEDD, which is currently one of the strongest discrete diffusion models. To clearly compare our method and SEDD, we set up a simple experiment for the models to learn a delta distribution over $S_n$ (i.e. a single permutation) for $n=100$ and $200$. In particular, we let the models learn the identity permutation and a fixed arbitrary distribution.

For SEDD, we view a permutation as a sequence of length $n$, where each number of the sequence is from $\\{0,1,\ldots,n-1\\}$. While the sequence at time 0 is a permutation, the trajectory may fall outside of $S_n$ for SEDD. We use the uniform transition for the forward process following the original work. For the reverse process of SEDD, we start by sampling a random sequence of length $n$.

For our method, we use riffle shuffle as the forward process and the GPL distribution as the reverse process. The entire trajectory is restricted in $S_n$. At the start of the reverse process, we sample a permutation from $S_n$ uniformly at random.

The SEDD model we use in our experiments has about 25M parameters, while our model only has about 2M parameters. For $n=100$, we use a batch size of 512 and 30K training steps on both methods. For $n=200$, we use a batch size of 128 and 30K training steps on both methods. For performance evaluation, we randomly sample 2560 sequences for SEDD and 2560 permutations for our method, and we perform their respective decoding processes.

The results are detailed in the following three tables with experiment setting stated in the header.

Our method reaches 100% accuracy in all experiments. While the accuracies of SEDD are also high, there are still notable gaps between SEDD and our method, particularly as the sequence length increases. We also observe that SEDD makes mistakes exactly because some of the samples are not permutations. These experiments demonstrate that by restricting the trajectory to $S_n$ and leveraging the structures of $S_n$, our method is more effective than previous discrete diffusion models that rely on transitions in the larger sequence spaces. We plan to include these experiments in a future version of our paper. We also plan to conduct a more comprehensive analysis in the future, including tasks like learning mixture distributions.

We would also like to highlight that it is nearly impossible for other discrete diffusion models (including SEDD) to solve the tasks introduced in our paper, including the jigsaw puzzle, sorting multi-digit MNIST numbers, and the TSP. The reason is that all prior discrete diffusion models assume a fixed alphabet or vocabulary, and they model categorical distributions on the fixed alphabet. For example, in NLP tasks, the vocabulary is predefined and fixed. However, the alphabet is the set of all possible image patches for image tasks such as jigsaw puzzles and sorting MNIST numbers. It is impractical to gather the complete alphabet beforehand. We could potentially train VQVAEs to obtain quantized image embeddings. However, such an approach introduces the approximation error from the quantized alphabet. For the TSP, each node of the graph is a point in the continuous space $\mathbb{R}^2$, so it is also impossible to gather the complete alphabet. In contrast, our method can be successfully applied to these tasks because we model a distribution on the fixed alphabet $S_n$, and we treat each permutation as a function that can be applied to an ordered list of objects.

Finally, we apologize for the delay in our response, as it took us additional time to modify the code of SEDD. We hope that our response addresses your concerns thoroughly.

Thank you for the insightful and constructive comments. We appreciate your positive feedback! We have corrected the typos in the newly uploaded version of the paper.

Q1: Have the authors considered evaluating OOD performance (e.g., feeding colored, or otherwise font-shifted MNIST into a model that was trained on grayscale images)? Do they anticipate a drop in performance in that setting?

A1: Evaluating the OOD performance of our model is indeed an interesting and important direction, and we would anticipate a performance drop in such settings. Feeding colored or font-shifted MNIST into a model that was trained on grayscale images would primarily test the OOD performance of the underlying vision encoder (e.g., the CNN) of SymmetricDiffuser. Testing the generalization ability with varying sequence lengths would also be interesting. For example, we could train on short-length sequences and test on long sequences. However, the focus of this paper is on proposing a novel discrete diffusion framework for symmetric groups, and enhancing OOD performance falls outside the scope of our current study. Addressing OOD performance would likely require significant modifications to the loss function or model design, making it a promising topic for future research.

Thank you for the insightful and constructive comments. We appreciate your positive feedback and address the questions below.

Q1: Why machine learning applications require generative models over permutations in the first place, rather than just outputting a single permutation, if ultimately only a single learned permutation is required per input?

A1: As in many other prediction tasks, predicting a distribution is often more useful than predicting a single output. In particular, in our context, there are several advantages.

First, there are many tasks where the optimal permutation is not unique. For example, in the jigsaw puzzle experiments, there may be identical patches in an image, in which case there would be multiple permutations that can recover the image. We added noise to the MNIST dataset to disambiguate the patches purely to simplify the evaluation metric computations, and our framework is certainly able to solve jigsaw puzzles with identical patches. Another example is the TSP, where multiple permutations may exist that result in the same minimum tour length.

Second, many NP-hard problems exist, e.g., TSPs and graph isomorphism problems, where the optimal solution is hard to find. Having a distribution over $S_n$ is extremely useful in constructing probabilistic approximate algorithms, e.g., MCMC-based search methods.

Last but not least, learning a distribution over $S_n$ allows learning to sample permutations, which further enables learning to generate other discrete objects. For instance, when generating expander graphs, one of the key steps in the probabilistic construction is to generate random permutations of vertices, cf., [1].

[1] Friedman, J., 2003, June. A proof of Alon's second eigenvalue conjecture. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 720-724).

Q2: For the right choice of parameters, can the reverse processes actually represent the exactly correct distributions induced by the corresponding forward diffusion process?

A2: Yes! During the rebuttal period, we proved that the reverse process using GPL can represent any distribution over $S_n$, which is a significant result regarding the expressiveness of the reverse process. Please refer to Theorem 2 (colored blue) and Appendix E of the newly uploaded paper. We also provide an example illustrating the idea we used in the proof in Figure 3 and lines 895 to 904 in Appendix E.

Q3: The abstract claims to learn a distribution over $S_n$, but the concrete objects that are dealt with are ordered sets of objects (stored in an $n$ by $d$ matrix). Would it be accurate to refer to this method as conditional diffusion? If not, how could the architectures best be modified to output a distribution over raw permutation matrices?

A3: For a set of distinct objects/components, there is a one-to-one correspondence between all ordered sequences of the components and $S_n$. If there are identical components, then we can apply arbitrary tie-breaking rules and still obtain the one-to-one correspondence. Therefore, dealing with concrete objects is equivalent to learning a distribution over $S_n$. In our experiments, we are using conditional diffusions in the sense that we are conditioning on the set (i.e. the unordered collection) of components. We do not need any modifications to output a distribution over the raw permutations because of this one-to-one correspondence.

Q4: As noted on line 154, $\mathcal{S}$ does not change across steps — why enforce this for diffusion models? Does this make something easier? Is it potentially restrictive in terms of what distributions can be represented after a given number of steps?

A4: We let $\mathcal{S}$ to remain the same across steps to construct a time-homogeneous Markov chain. The first reason is that existing random walk theories on finite groups primarily deal with time-homogeneous Markov chains. If we allow $\mathcal{S}$ to change across steps, the convergence analysis may become very difficult in general. The second reason is that having $\mathcal{S}$ to change across time-steps may not bring any additional benefits. For example, we could mix riffle shuffles, random transpositions, and random insertions together in the forward process. However, we know that riffle shuffles mix the fastest, so having other shuffling methods will only slow down the mixing time. Experiments also show that the riffle shuffle alone is very effective with fast mixing time.

Q5: Can symmetric diffusers be adapted for other structured discrete data beyond permutations, such as specific types of graph structures or other combinatorial tasks?

A5: Our model is directly applicable if a combinatorial problem with other structured discrete data can be equivalently reformulated using permutations. For instance, permutations can be used to represent solutions to TSP on graphs and exact graph matching (or graph isomorphism testing). For combinatorial problems that can not be reformulated using permutations, permutations could still be instrumental, e.g., generating expander graphs and various assignment problems. Given the central role of permutations in various combinatorial problems, our model has the potential to address a wide range of tasks involving structured discrete data.

Q6: Could you provide more insights or experiments to demonstrate the practical benefits of using the generalized Plackett-Luce (PL) distribution over the standard PL model?

A6: We have conducted the ablation studies and experiments in Appendix G.2. As seen from the results, the GPL distribution has better performance when sorting 4-digit MNIST numbers with $n=52$ .

From a theoretical perspective, the standard PL distribution cannot represent a delta distribution, which is the ground truth for many problems. During the rebuttal period, we further proved that the reverse process using GPL can represent any distribution over $S_n$, which is a significant result regarding the expressiveness of the reverse process. This result is formalized in Theorem 2 (colored blue) and proved in Appendix E of the newly uploaded paper. We also provide an example illustrating the idea we used in the proof in Figure 3 and lines 895 to 904 in Appendix E.

Thank you for the insightful and constructive comments. We appreciate your positive feedback and address the questions below.

Q1: Could you provide additional comparisons between symmetric diffusers and other discrete diffusion models, such as discrete denoising diffusion probabilistic models (D3PMs), particularly regarding tasks that involve smaller permutation spaces?

A1: Existing discrete diffusion models assume token-wise conditional independence when modeling the reverse transition distributions. This assumption does not hold in learning permutations since different components of $X_{t-1}$ are not independent conditioned on $X_t$ in the reverse process, and they have to satisfy the constraint of permutations (i.e., being one of the vertices of Birkhoff Polytope). Therefore, if we have a distribution over $[n]^n$, the denoising step in standard diffusion models would lead to noisy data $X_{t-1}$ that is not an exact permutation. Furthermore, it is also computationally expensive to project it to a distribution over $S_n$.

Discrete diffusion methods like D3PM, which model categorical distributions, are also unsuitable for $S_n$. These methods require explicit matrix multiplications involving $n!\times n!$ transition matrices. While D3PM uses dense transition matrices such as uniform or discretized Gaussian distributions, performing dense matrix multiplications at this scale is impractical.

Our proposed method addresses these challenges by defining efficient, customized transition distributions through card-shuffling methods. This approach avoids explicit matrix multiplications by directly simulating the forward process using the efficient operations of shuffling methods. Essentially, the shuffling methods induce “sparse” transitions on $S_n$, resolving the efficiency issues inherent in existing discrete diffusion models. As our framework is fundamentally different and existing frameworks are infeasible for $S_n$, our baselines focus on comparing different shuffling methods within our framework.

Q2: How do symmetric diffusers handle scalability as increases, and what strategies do you envision for managing the factorial growth in the state space for large permutations? An empirical analysis or theoretical discussion on the scalability limits and potential optimizations (e.g., sparse transition matrices or modular architectures) would provide greater insight into the model’s practicality for large-scale tasks.

A2: First, our method significantly improves the scalability of existing approaches. As evidenced by prior work, scalability remains a highly challenging problem in permutation learning. For instance, in the 4-digit MNIST sorting experiment, baseline methods are only effective for sequence lengths up to 32. In contrast, our method achieves promising results for lengths up to 200, outperforming these baselines by a large margin.

Second, as mentioned in A1, shuffling methods serve as efficient "sparsification" of D3PM transition matrices, which is crucial to our scalability improvement. While our framework has achieved significant progress, there is definitely lots of room (e.g., better parameterization of forward/reverse diffusion steps, better neural network architecture, and so on) for further scalability improvement, and it would be an exciting topic for future research.

Q3: How significant is the denoising schedule's impact on computational efficiency and model performance? Have you considered alternative denoising schedules that might further improve efficiency?

A3: The denoising schedule is an important hyperparameter in our model. We have already conducted an ablation study on the denoising schedule and provided a detailed discussion in Appendix G.2 and Table 6. We have also provided a theoretical justification and empirical guidelines for choosing the denoising schedule in Section 3.4 of the main paper.

Q4: Could you clarify certain technical details of the forward and reverse diffusion processes, especially for readers unfamiliar with symmetric groups? … To make these sections more accessible to readers, illustrative examples for the shuffling and reverse diffusion steps or a more detailed explanation of terms such as “stationary distribution” and “mixing time” could be added.

A4: Thank you for the suggestion. We will include additional explanations and illustrative examples of these concepts in the final version of the paper to improve accessibility.