Paper deep dive
Learning Permutation Distributions via Reflected Diffusion on Ranks
Sizhuang He, Yangtian Zhang, Shiyang Zhang, David van Dijk
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/22/2026, 5:51:54 AM
Summary
The paper introduces Soft-Rank Diffusion, a generative framework for learning permutation distributions. It replaces discrete shuffle-based corruption with a continuous latent space approach where permutations are relaxed into soft ranks. The method uses a reflected diffusion bridge on these soft ranks and introduces contextualized generalized Plackett-Luce (cGPL) denoisers to improve expressivity for sequential decision tasks like sorting and the Traveling Salesperson Problem.
Entities (5)
Relation Signals (3)
Soft-Rank Diffusion → uses → Reflected Diffusion Bridge
confidence 98% · Soft-Rank Diffusion, which defines the forward noising process as a reflected diffusion bridge
Soft-Rank Diffusion → appliedto → Traveling Salesperson Problem
confidence 95% · We evaluate Soft-Rank Diffusion on standard permutation generation benchmarks, including 4-digit MNIST sorting and TSP.
cGPL → generalizes → Plackett-Luce
confidence 95% · cGPL denoisers that generalize prior PL-style parameterizations
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.17353v1
- Canonical: https://arxiv.org/abs/2603.17353v1
Trouble viewing inline? Open PDF directly →
Full Text
53,619 characters extracted from source content.
Expand or collapse full text
Learning Permutation Distributions via Reflected Diffusion on Ranks Sizhuang He Yangtian Zhang Shiyang Zhang David van Dijk Abstract The finite symmetric group SnS_n provides a natural domain for permutations, yet learning probability distributions on SnS_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. Machine Learning, ICML 1 Introduction Permutations are fundamental objects in a wide range of applications, from ranking search results and recommendations [6, 15] to sorting and learning-to-rank [16] and combinatorial optimization problems such as the traveling salesperson problem (TSP). In many settings, we aim to model a distribution over permutations—and ultimately build generative models with which to sample permutations. In continuous Euclidean domains, diffusion models [26, 11, 28, 27] have emerged as powerful and scalable tools for modeling complex distributions like images, and related ideas have been extended beyond ℝdR^d to discrete objects such as text and graphs, a class of models known as Discrete Diffusion models [1, 18, 5, 7, 10, 31]. Yet permutations remain a particularly challenging case: although they are discrete, the state space grows factorially with sequence length n, and the natural transitions on permutations, like card-shuffling, are often abrupt—small local moves can cause discontinuous, non-differentiable changes in the induced ordering. Consequently, diffusion-style constructions that work well for other discrete domains can become brittle on permutations and scale poorly with n. Developing discrete diffusion models over permutations remains relatively underexplored. Recent progress on permutation diffusion [34] tackles above challenge by defining the forward noising process directly on permutations—typically as a random walk induced by riffle shuffles [8]—and parameterizing the reverse dynamics with the Plackett–Luce distribution (PL) [23, 19] and its generalizations (GPL) [34]. While effective on small instances, these discrete forward trajectories can be highly “jumpy”: even a single riffle–shuffle can simultaneously move many items across the sequence, yielding abrupt, non-smooth changes in the ordering. Performance often degrades rapidly and can even collapse in the long-n regime. In this paper, we take a different perspective: rather than diffusing within SnS_n, we lift a permutation—viewed as the rank of each element—to a continuous latent representation and diffuse in that space. Concretely, we represent an ordering by assigning each item a continuous-valued soft rank z∈[0,1]z∈[0,1], obtaining a soft rank vector Z∈[0,1]nZ∈[0,1]^n and recover the induced permutation by sorting, σ=argsort(Z)σ=argsort(Z). This relaxation lets us define smooth stochastic dynamics in a continuous space, while still producing a discrete permutation at any time via a simple sorting operation. Building on this idea, we introduce Soft-Rank Diffusion, which defines the forward noising process as a reflected diffusion bridge [17, 33] on [0,1]n[0,1]^n, and observes permutations through the induced ordering σt=argsort(Zt) _t=argsort(Z_t). The latent construction also yields a reverse-time sampler. We augment the intractable discrete reverse step with an auxiliary, tractable continuous update in the soft-rank space, followed by a projection back to permutations via sorting. We further introduce contextualized GPL (cGPL) and a pointer-cGPL variant, generalizations of PL/GPL that make stagewise logits depend on the evolving prefix and the shrinking candidate set—a natural fit for intrinsically sequential and dynamic tasks such as TSP. We evaluate Soft-Rank Diffusion on standard permutation generation benchmarks, including 4-digit MNIST sorting and TSP. Across settings, our method consistently outperforms prior permutation diffusion baselines and differentiable sorting baselines, with gains that widen as sequence lengths increase. Taken together, our results suggest that reflected diffusion in soft-rank space provides a principled and scalable route to permutation generative modeling. Contributions. Our main contributions are: • We introduce Soft-Rank Diffusion, a permutation diffusion framework induced by reflected diffusion bridges in a relaxed continuous soft-rank space. • We derive a hybrid reverse sampler that augments the intractable reverse dynamics in permutation space with tractable updates in the soft-rank space. • We propose cGPL and pointer-cGPL, generalizations of PL/GPL that improve prefix-conditional expressivity for sequential permutation tasks. • We demonstrate strong empirical performance on long-sequence MNIST sorting and TSP benchmarks, particularly in the large-n regime. 2 Related Works Discrete Diffusion Models. Diffusion models [26, 11, 28] were initially developed for continuous data. D3PM [1] extended this framework to discrete domains by defining forward noising processes based on masking or uniform replacement. Subsequent work introduced alternative parameterizations and training objectives for discrete diffusion [18, 7] and further extended discrete (both in state space and time) diffusion to continuous-time variants [3, 29, 25]. However, most existing methods assumes a manageable or factorized state space; directly extending them to permutation-valued data is challenging because the group SnS_n has size n!n!, making naive transition representations intractable without exploiting additional structure. Learning Permutations. Sorting algorithms can be viewed as producing a permutation of a set of items and are well understood; however, their hard discrete decisions are non-differentiable, which hinders end-to-end training when permutations are produced by, or embedded within, neural models. This motivates differentiable sorting methods that replace discrete swaps or permutation operators with smooth surrogates, yielding a soft permutation (or rank) representation amenable to gradient-based optimization [21, 4, 24, 2, 9, 22]. Another widely used family is Pointer Networks (Ptr-Nets) [32], which parameterize permutation-valued outputs by decoding a sequence of indices into the input, rather than symbols from a fixed vocabulary. At each decoding step, an attention mechanism induces a categorical distribution over input positions, and the chosen index specifies which input element is appended next in the output ordering. Because the effective output domain scales with input length, Ptr-Nets naturally accommodate variable-sized instances and provide a natural generic parameterization for combinatorial prediction problems whose outputs are orderings (e.g., sorting and routing). Discrete Diffusion on Permutations. Zhang et al. [34] introduce SymmetricDiffusers, which formulates discrete diffusion directly on the finite symmetric group SnS_n. The forward noising dynamics are instantiated as a random walk on SnS_n, with the riffle shuffle [8] serving as an effective transition that mixes rapidly to enable short diffusion chains in practice. For the reverse (denoising) parameterization, Plackett–Luce-style (PL) models are adopted and extended to a generalized Plackett–Luce (GPL) family. While the PL distribution is defined as pPL(σ)=∏i=1nexp(sσ(i))∑j=inexp(sσ(j)),p_PL(σ)= _i=1^n \! (s_σ(i) ) _j=i^n \! (s_σ(j) ), (1) i.e., it assigns a single preference score sks_k to each item k and samples items without replacement according to these fixed scores, the GPL family generalizes this construction by assigning step-specific scores for each item rather than a single fixed global score. As a result, GPL is strictly more expressive than PL; in particular, GPL is universal in the sense that it can represent arbitrary distributions over SnS_n. Reflected Diffusion and Reflected Flow Matching. Diffusion models are often trained on data supported on bounded domains (e.g., [0,255][0,255] for unnormalized image pixels), yet the learned dynamics can leave the domain at intermediate time steps—a pathology that is commonly handled by ad-hoc clipping. Lou and Ermon [17] address this issue by formulating generation as a reflected score-based SDE, augmenting the dynamics with an additional reflection term that enforces the state constraint and keeps trajectories in-bounds throughout sampling. Xie et al. [33] later extend the same principle to flow matching, incorporating reflection into the corresponding flow/ODE formulations. 3 Methods Let [N]≔1,…,N[N] \1,…,N\. A permutation is a bijection σ:[N]→[N]σ:[N]→[N]. We can write it as σ=(12⋯Nσ(1)σ(2)⋯σ(N)),σ\;=\; pmatrix1&2&·s&N\\ σ(1)&σ(2)&·s&σ(N) pmatrix, meaning that each element i∈[N]i∈[N] is mapped to σ(i)σ(i). We can make the source indices (1,2,…,N)(1,2,…,N) implicit and use the one-line notation σ=(σ(1),σ(2),…,σ(N)).σ\;=\;(σ(1),\,σ(2),\,…,\,σ(N)). Under this convention, σ(i)σ(i) can be interpreted as the (destination) position of element i after reordering, i.e., the rank of element i of the original sequence in the permuted ordering. We denote by NS_N the set of all such permutations (i.e., the symmetric group under composition). Applying a permutation to an ordered list simply reindexes its entries. Equivalently, each σ∈Nσ _N can be represented by a permutation matrix Pσ∈0,1N×NP_σ∈\0,1\^N× N, so that the same reindexing can be implemented via matrix multiplication. Given an instance X=(x1,…,xN)∈ℝN×dX=(x_1,…,x_N) ^N× d consisting of N items (with associated features), we aim to model a conditional distribution over permutations σ∈Nσ _N. We observe i.i.d. training pairs (X,σ0)∼p⋆(X, _0) p , and our goal is to learn a generative model that can efficiently sample valid permutations conditioned on X. We write Xt=σt(X)X_t= _t(X) to be the permuted instance at time t. We adopt a diffusion-style approach on NS_N. Specifically, we define a forward noising process on permutations that gradually transforms σ0 _0 toward a target distribution, and train a parameterized reverse-time model pθ(σt−Δt∣σt,X)p_θ( _t- t _t,X) to approximately invert this corruption process. At test time, sampling starts from the reference distribution and iteratively applies the learned reverse dynamics to generate σ^0∈N σ_0 _N conditioned on X. 3.1 Forward Process: Soft-Rank Diffusion Instead of defining diffusion dynamics directly on the discrete space NS_N (e.g., via card shuffling methods as in Zhang et al. [34], which can be abrupt and unstructured), we adopt a continuous latent viewpoint in which a permutation is encoded by the relative ordering of real-valued coordinates. The key idea is to relax the discrete rank values in [N][N] to continuous soft ranks in [0,1][0,1], and to define a diffusion process over these continuous variables. At any intermediate time, the induced ordering of the latent coordinates yields a valid permutation of the original items. This relaxation brings two immediate benefits. First, it provides a Euclidean state space where noise injection and interpolation are natural, enabling diffusion-style modeling without relying on discrete, jump-like transitions. Second, the forward marginals can be designed to be analytically tractable, which later allows us to derive a reverse-time sampler. Intuitively, one may view each item as a particle undergoing Brownian motion: starting from an initial ordered configuration, the particles gradually diffuse, and the permutation at time t is given by the snapshot ordering of their positions. Formally, to initialize a continuous latent state, we convert a permutation σ∈Nσ _N into a canonical soft-rank vector in [0,1]N[0,1]^N by mapping discrete ranks to a fixed grid. Let grr=1N\g_r\_r=1^N be a uniform grid on [0,1][0,1], e.g., gr=r−1N−1(r=1,…,N).g_r\;=\; r-1N-1 (r=1,…,N). (2) We define the grid-mapping operator LiftToGrid:N→[0,1]NLiftToGrid:S_N→[0,1]^N by LiftToGrid(σ)i≔gσ(i),i∈[N].LiftToGrid(σ)_i\; \;g_σ(i), i∈[N]. (3) In particular, we set Z0≔LiftToGrid(σ0)Z_0 ( _0). We generate ZtZ_t by coupling the data latent Z0Z_0 to a randomly sampled endpoint Z1∼prefZ_1 p_ref via a Brownian bridge, where prefp_ref is a tractable, data-independent reference distribution (e.g., (0,IN)N(0,I_N) or Unif([0,1]N)Unif([0,1]^N)). We apply this construction coordinate-wise: each entry of ZtZ_t evolves as an independent one-dimensional bridge driven by its own Brownian motion. For clarity, we describe a single coordinate using lowercase notation. Specifically, we consider the following SDE, which corresponds to a VE diffusion bridge as in Zhou et al. [35]: dzt=z1−zt1−tdt+ηdwt+dlt,dz_t\;=\; z_1-z_t1-t\,dt\;+\;η dw_t\;+\;dl_t, (4) where wtw_t is a standard one-dimensional Brownian motion, η is the noise scale and ltl_t is a reflection term [17, 33] that enforces the state constraint zt∈[0,1]z_t∈[0,1]. Then, at any time t, we obtain a discrete permutation in the rank representation simply by ranking the coordinates of ZtZ_t. Assuming distinct coordinates (almost surely under continuous noise) and using 11-based indexing, we recover σt _t as σt=argsort(argsort(Zt)). _t\;=\;argsort\! (argsort(Z_t) ). Figure 1 illustrates the forward process. Figure 1: Soft-Rank Diffusion. We define the forward diffusion by relaxing each item’s rank to a continuous soft-rank variable and evolving these soft ranks in a reflected diffusion process [17]. At each time t, the soft ranks induce a discrete ordering by simple sorting, thereby yielding a forward process in permutation space. For reverse sampling, we couple a discrete denoiser in permutation space (predicting a clean permutation from XtX_t) with an auxiliary continuous update: we lift the predicted permutation to a grid-aligned soft-rank vector Z^0 Z_0, sample an intermediate latent ZsZ_s for s<ts<t from a conditional reverse kernel p(Zs∣Zt,Z^0,Z1)p(Z_s Z_t, Z_0,Z_1), and map back to permutation space by sorting ZsZ_s, thus stepping backward in time. 3.2 Reverse Process Although the forward process is defined in a continuous latent space, our observations and learning targets are the induced permutations. In other words, the model operates on discrete permutation-valued states, while the continuous latent dynamics serve as an underlying construction that we invoke only to derive a convenient reverse-time update. One can choose to treat the continuous latent ZtZ_t as the primary reverse-time state and learn a denoiser directly in ℝNR^N. We instead work in NS_N: during sampling we keep the permutation σt _t as the explicit state, and reconstruct a rank-consistent latent ZtZ_t only as an auxiliary variable when executing each backward update. We adopt a σ0 _0-prediction style parameterization. Specifically, a neural network fθf_θ predicts an estimate of the initial permutation, σ0^=fθ(Xt,t), _0=f_θ(X_t,t), (5) which in turn induces an estimate of the clean sequence via the permutation action, X^0=σ^0(X) X_0= σ_0(X). We describe the overall reverse process next, and later provide details on the parameterization of fθf_θ. Reverse-time transition kernel. Our forward process in Eq. 4 is a reflected Brownian bridge. Following Xie et al. [33], in practice one first solve an unconstrained backward step in ℝNR^N using the corresponding unreflected bridge conditional, and apply the reflection operator only afterwards (and only when needed). Specifically, let μ(u)≔(1−u)z0+uz1μ(u) (1-u)z_0+uz_1 denote the linear interpolation between endpoints. For the unconstrained bridge, for any 0<s<t<10<s<t<1 we have the closed-form Gaussian conditional zs∣zt,z0,z1∼(μ(s)+st(zt−μ(t)),η2s(t−s)t).z_s z_t,z_0,z_1 \! (μ(s)+ st (z_t-μ(t) ),\;η^2 s(t-s)t ). (6) Equivalently, we sample a proposal z~s z_s by z~s=μ(s)+st(zt−μ(t))+ηs(t−s)tϵ,ϵ∼(0,1). z_s=μ(s)+ st (z_t-μ(t) )+η s(t-s)t\,ε, ε (0,1). (7) and then enforce the latent-domain constraint via reflection: zs←ℛ(z~s).z_s ( z_s). (8) We defer the derivation of Eq. (6) to Appendix B. The reverse sampling procedure is initialized by drawing z1∼prefz_1 p_ref. Since our model maintains only a permutation-valued state, we obtain the corresponding initial permutation by mapping the latent to the grid via σ1=LiftToGrid(z1) _1=LiftToGrid(z_1) in Eq. (3). The complete reverse-time algorithm is summarized in Algorithm 1 and illustrated in Figure 1. Algorithm 1 Reverse Sampling via Reflected Gaussian-Bridge Updates 0: Number of items n; time grid 0=t0<t1<⋯<tK=10=t_0<t_1<·s<t_K=1; diffusion scale η. Reference distribution prefp_ref on [0,1]n[0,1]^n. Score network fθf_θ defining pθ(σ∣Xt,t)p_θ(σ X_t,t). Operators LiftToGrid(⋅)LiftToGrid(·) and Reflect(⋅)Reflect(·). 1: Sample z1∼prefz_1 p_ref and set ztK←z1z_t_K← z_1. 2: for k=K,K−1,…,1k=K,K-1,…,1 do 3: t←tk,s←tk−1t← t_k, s← t_k-1. 4: Xt←argsort(zt)X_t (z_t) (induce discrete state) 5: Sample σ^0∼pθ(⋅∣Xt,t) σ_0 p_θ(· X_t,t) (via fθf_θ) 6: z^0←LiftToGrid(σ^0)∈[0,1]n z_0 ( σ_0)∈[0,1]^n. 7: μt←(1−t)z^0+tz1,μs←(1−s)z^0+sz1 _t←(1-t) z_0+tz_1, _s←(1-s) z_0+sz_1. 8: Sample ξ∼(0,In)ξ (0,I_n). 9: z¯s←μs+st(zt−μt)+ηs(t−s)tξ z_s← _s+ st (z_t- _t )+η s(t-s)t\;ξ. 10: zs←Reflect(z¯s)z_s ( z_s). 11: zt←zsz_t← z_s. 12: end for 13: return zt0z_t_0 and optionally σ^←argsort(zt0) σ (z_t_0). 3.3 Model architecture We now describe the model architecture used to parameterize the σ0 _0-prediction distribution and to sample an estimate of the clean permutation, as in Eq. 5. We extend the Generalized Plackett–Luce (GPL) parameterization of [34] to a contextualized Generalized Plackett–Luce (cGPL) model. In contrast to the encoder-only architecture used in Zhang et al. [34], we implement cGPL with a full encoder–decoder Transformer [30]. This formulation generalizes GPL, and we show empirically that cGPL yields a more expressive parameterization across our benchmarks. Contextualized GPL. Similar to GPL [34], cGPL models a permutation σ∈nσ _n with a stagewise distribution that, at each position i, normalizes scores over the remaining (unselected) set ℛi(σ):=[n]∖σ(1),…,σ(i−1)R_i(σ):=[n] \σ(1),…,σ(i-1)\: pθ(σ∣X,t) p_θ(σ X,t) =∏i=1nexp(sσ(i),i)∑k∈ℛi(σ)exp(sk,i). = _i=1^n \! (s_σ(i),i ) _k _i(σ) \! (s_k,i ). (9) The distinction between GPL and cGPL lies entirely in the context each position-i score vector s:,is_:,i is allowed to depend on. In GPL, scores are prefix-agnostic and can be computed once as a static matrix. Consequently, sampling from GPL consists of a single forward pass to obtain all scores, followed by sequentially reading the corresponding columns and sampling without replacement. GPL: sk,i≔[fθ(X,t)]k,i,s_k,i\; \;[f_θ(X,t)]_k,i, (10) In contrast, cGPL makes scores explicitly prefix-conditional through an encoder–decoder Transformer. As a result, sampling from cGPL must proceed autoregressively: scores are recomputed progressively as the prefix σ<i _<i is instantiated. cGPL: sk,i=[fθ(X,σ<i,t)]k,i.s_k,i=[f_θ(X, _<i,t)]_k,i. (11) See Algorithm 2 for the complete sampling procedure of cGPL. Empirically, prefix-conditioning improves performance across all tasks we consider, and the benefits are particularly pronounced on intrinsically sequential and dynamic settings such as the Traveling Salesperson Problem, where next-step decisions depend strongly on the evolving partial solution. When the decoder is made prefix-agnostic such that sk,i(X,σ<i,t)≡sk,i(X,t)s_k,i(X, _<i,t)≡ s_k,i(X,t) for all prefixes, cGPL reduces to GPL; hence we can conclude cGPL generalizes GPL. Figure 2 demonstrates the difference among sampling from PL, GPL and cGPL. (a) PL and GPL sampling. (b) cGPL sampling. Figure 2: Sampling in PL/GPL/cGPL. (a) PL and GPL. In PL, each item is assigned a single scalar score; sampling a permutation amounts to repeatedly sampling from the same score vector without replacement, masking selected items and renormalizing at each step. In GPL, each item is assigned a length-N score vector, yielding position-specific logits: at step i we sample according to the i-th column of the score matrix (after masking previously selected items), proceeding sequentially from i=1i=1 to N. (b) cGPL. In cGPL, each item is assigned a position-dependent score vector dynamically. Sampling proceeds autoregressively: the score vector at later positions depends on the outcomes sampled at preceding positions. As in GPL, we apply masking and subsequent renormalization to obtain a valid probability distribution over the remaining items. In practice, both sampling and likelihood evaluation require normalizing scores only over the remaining (feasible) set ℛi(σ)R_i(σ). We implement this via a feasibility mask mk,i(σ<i)∈0,−∞m_k,i( _<i)∈\0,-∞\ added to the predicted scores: mk,i(σ<i) m_k,i( _<i) =0,k∈ℛi(σ),−∞,k∉ℛi(σ), = cases0,&k _i(σ),\\ -∞,&k _i(σ), cases (12) s~k,i s_k,i\; :=sk,i(X,σ<i,t)+mk,i(σ<i), :=\;s_k,i(X, _<i,t)+m_k,i( _<i), (13) so that softmax(s~:,i)softmax( s_:,i) renormalizes over ℛi(σ)R_i(σ) and assigns zero probability to infeasible items. Training objective. We train our model by maximizing the standard variational lower bound: pdata(X0,X)[logpθ(X0∣X)] ≥\;E_p_data(X_0,X)[ p_θ(X_0 X)] ≥ ≥\; pdata(X0,X)q(X1:T∣X0,X)[logp(XT∣X) _p_data(X_0,X)\,q(X_1:T X_0,X) [ p(X_T X) +∑t=1Tlogpθ(Xt−1∣Xt,t)q(Xt∣Xt−1)]. 26.00009pt+ _t=1^T p_θ(X_t-1 X_t,t)q(X_t X_t-1) ]. Our model predicts a denoised distribution pθ(X0∣Xt,t)p_θ(X_0 X_t,t). To obtain a one-step reverse transition, we compose this predictor with a reconstruction kernel q~t(Xt−1∣Xt,X0) q_t(X_t-1 X_t,X_0): pθ(Xt−1∣Xt,t):=∑X0q~t(Xt−1∣Xt,X0)pθ(X0∣Xt,t).p_θ(X_t-1 X_t,t)\ :=\ _X_0 q_t(X_t-1 X_t,X_0)\,p_θ(X_0 X_t,t). (14) Note that q~t q_t in the discrete permutation space is generally intractable but as discussed in 3.2, we can augment with a tractable update step in the continuous soft-rank space. With the feasibility mask in Eq 13, the negative log-likelihood reduces to a sum of cross-entropies on the masked scores: ℒ(σ;X,t)=−∑i=1nlogexp(s~σ(i),i)∑k=1nexp(s~k,i).L(σ;X,t)=- _i=1^n \! ( s_σ(i),i ) _k=1^n \! ( s_k,i ). (15) Algorithm 2 Autoregressive Sampling from cGPL 0: Input set X=x1,…,xnX=\x_1,…,x_n\; diffusion step t; neural decoder fθf_θ 0: Permutation σ^∈n σ _n 1: ℛ←1,2,…,nR←\1,2,…,n\ (remaining items) 2: σ^←[] σ←[\ ] (empty prefix) 3: for i=1,…,ni=1,…,n do 4: Compute logits s:,i←([fθ(X,σ^<i,t)]k,i)k=1ns_:,i← ([f_θ(X, σ_<i,t)]_k,i )_k=1^n 5: s~k,i←sk,i s_k,i← s_k,i if k∈ℛk , else −∞-∞ (mask) 6: π⋅,i←softmax(s~⋅,i) _·,i ( s_·,i) 7: Sample σ^(i)∼Categorical(π⋅,i) σ(i) ( _·,i) 8: ℛ←ℛ∖σ^(i)R \ σ(i)\ 9: end for 10: return σ σ Pointer parameterization. As an alternative to a fixed n-way linear head that directly outputs n logits (treating output coordinates as a fixed “vocabulary” indexed by absolute positions), we draw inspiration from Pointer Networks [32] and parameterize the cGPL scores with an item-aligned pointer head that explicitly points to the encoded input items. Concretely, at decoding step i we compute a compatibility score between the decoder state and each encoder item representation, and interpret the resulting length-n vector as a categorical distribution over the input indices (rather than over a fixed output dictionary); see Fig. 4 for an illustration. This parameterization naturally supports variable-size output dictionaries and provides another way of producing valid permutations other than relying on versions of the Plackett-Luce distribution [32]. Formally, given encoder item representations and a prefix-dependent decoder state, we compute the pointer scores as a bi-affine transformation between them: ek e_k\; =Encθ(Xt,t)k∈ℝd,k∈[n], =\;Enc_θ(X_t,t)_k ^d, k∈[n], di d_i\; =Decθ(σ<i,Xt,t)i∈ℝd,i∈[n], =\;Dec_θ( _<i,X_t,t)_i ^d, i∈[n], sk,i(Xt,σ<i,t) s_k,i(X_t, _<i,t)\; =di⊤Wek+u⊤di+v⊤ek+b, =\;d_i We_k\;+\;u d_i\;+\;v e_k\;+\;b, (16) where W∈ℝd×dW ^d× d and u,v∈ℝdu,v ^d and b∈ℝb are learned parameters. The conditional distribution at step i is then obtained by applying the same remaining-set normalization as in Eq. (9). 4 Experiments 4.1 4-digit MNIST sorting We evaluate Soft-Rank Diffusion on four-digit MNIST sorting, a standard benchmark for permutation modeling in differentiable sorting and permutation diffusion [9, 22, 34]. Each instance is a list of N four-digit MNIST images (randomly ordered), and the task is to predict the permutation that sorts the list in ascending order by the underlying four-digit numbers they represent. We report Kendall–Tau correlation (a correlation coefficient between ranks) [13], accuracy (fraction of exactly matched sorted lists), and correctness (fraction of items placed in their correct positions). We rerun the baseline methods DiffSort [22], Error-free DiffSort [14] and SymmetricDiffusers [34] using their official GitHub repositories and the recommended (or default) hyperparameters. For SymmetricDiffusers, we use GPL sampling and disable beam search so that the comparison focuses on cGPL versus GPL under the same sampling setting. See Appendix A.1 for details. Table 1 summarizes results on the 4-digit MNIST sorting benchmark across sequence lengths N∈9,15,32,52,75,100,150,200N∈\9,15,32,52,75,100,150,200\. Overall, Soft-Rank Diffusion consistently outperforms all baseline methods, with the performance gap widening as N increases. In particular, the Pointer variant further outperforms the plain cGPL variant, and is the only method that maintains non-trivial performance in the long-sequence regime (N≥150N≥ 150). While SymmetricDiffusers performs strongly on short sequences, its accuracy and correctness degrade rapidly as N grows, approaching chance-level behavior at N>100N>100. By contrast, Soft-Rank Diffusion degrades more gracefully, indicating improved scalability and robustness to longer permutations. This scaling advantage is further illustrated in Figure 3, which examines exact-match accuracy as a function of the sequence length N. Figure 3(a) shows that both variants of Soft-Rank Diffusion are substantially less prone to catastrophic accuracy collapse as N increases, with the Pointer variant exhibiting consistently stronger robustness at larger sequence lengths. Figure 3(b) further quantifies this effect by reporting the relative exact-match accuracy of Soft-Rank Diffusion over SymmetricDiffusers, computed as the ratio relative to the baseline accuracy. The improvement margin grows rapidly with N, indicating that Soft-Rank Diffusion achieves increasingly favorable scaling behavior compared to SymmetricDiffusers. Table 1: MNIST sorting benchmark. We compare baselines and our models across sequence lengths. Bold indicates the best value in each column. For a controlled comparison, SymmetricDiffusers and both Soft-Rank Diffusion variants use the same 7-layer Transformer backbone (ours: 3-layer encoder + 4-layer decoder with matched hidden width). This differs from Zhang et al. [34], which used a 12-layer Transformer for n=200n=200 and a 7-layer Transformer for other lengths. Method Metric Sequence Length N 9 15 32 52 75 100 150 200 DiffSort [22] Kendall-Tau ↑ 0.8163 0.7386 0.4423 0.3037 0.2227 0.1617 0.0891 0.0636 Accuracy ↑ 0.5555 0.2350 0.0003 0.0000 0.0000 0.0000 0.0000 0.0000 Correctness ↑ 0.8643 0.7975 0.5335 0.3897 0.2987 0.2251 0.1307 0.0953 Error-free DiffSort [14] Kendall-Tau ↑ 0.9151 0.9160 0.8798 0.0042 0.0005 0.0029 0.0006 0.0002 Accuracy ↑ 0.7953 0.7492 0.5186 0.0000 0.0000 0.0000 0.0000 0.0000 Correctness ↑ 0.9365 0.9334 0.9019 0.0258 0.0132 0.0112 0.0072 0.0030 SymmetricDiffusers with GPL [34] Kendall-Tau ↑ 0.9483 0.9320 0.8610 0.7890 0.7304 0.1114 0.0641 0.0022 Accuracy ↑ 0.8955 0.8260 0.5896 0.3009 0.1379 0.0000 0.0000 0.0000 Correctness ↑ 0.9605 0.9450 0.8846 0.8232 0.7733 0.1620 0.0975 0.0061 Soft-Rank Diffusion with cGPL Ours Kendall-Tau ↑ 0.9668 0.9384 0.8765 0.8092 0.6925 0.6279 0.4821 0.3982 Accuracy ↑ 0.9397 0.8601 0.6555 0.4239 0.1908 0.0863 0.0080 0.0004 Correctness ↑ 0.9742 0.9505 0.8967 0.8393 0.7347 0.6773 0.5468 0.4644 Soft-Rank Diffusion with Pointer-cGPL Ours Kendall-Tau ↑ 0.9645 0.9455 0.8944 0.8459 0.7727 0.7454 0.6198 0.6048 Accuracy ↑ 0.9329 0.8710 0.6854 0.4909 0.2742 0.1922 0.0421 0.0137 Correctness ↑ 0.9719 0.9559 0.9119 0.8724 0.8082 0.7849 0.6704 0.6607 (a) Exact-match accuracy in logit scale over N. (b) Accuracy ratio relative to SymmetricDiffusers (SD), shown on a log scale. Figure 3: Exact-match accuracy and relative improvement versus SymmetricDiffusers as a function of sequence length (N). Panel 3(a) shows accuracy on a logit scale. Panel 3(b) reports the accuracy ratio of Soft-Rank Diffusion relative to SymmetricDiffusers on a log scale. Starred points mark sequence lengths where SymmetricDiffusers attains zero accuracy; the corresponding ratios are undefined and are clipped to the top of the plotted range for visualization. 4.2 Traveling Salesperson Problem (TSP) We evaluate Soft-Rank Diffusion on the traveling salesperson problem (TSP), an NP-hard combinatorial optimization task. Given a set of 2D points V=v1,…,vn⊂ℝ2V=\v_1,…,v_n\ ^2, the goal is to predict a tour permutation σ∈Snσ∈ S_n that minimizes the total length ∑i=1n∥vσ(i)−vσ(i+1)∥2 _i=1^n v_σ(i)-v_σ(i+1) _2, where σ(n+1):=σ(1)σ(n+1):=σ(1). We report the tour length and the optimality gap (see Appendix A.2 for details) on TSP-20 and TSP-50 (n=20n=20 and n=50n=50, respectively). We rerun SymmetricDiffusers using their respective official GitHub repositories and default hyper-parameters. For SymmetricDiffusers, we again use GPL sampling and disable beam search to ensure a fair comparison. See Appendix A.2 This task is particularly well-suited to highlight the advantage of our dynamic cGPL parameterization: unlike static scoring schemes, TSP decoding requires making prefix-dependent decisions over a shrinking set of remaining cities, where the desirability of each candidate depends strongly on the current partial tour. By producing context-conditioned, step-specific logits over the remaining items, cGPL better matches this dynamic decision structure and therefore exhibits larger performance gains as problem size increases. Table 2: TSP performance on TSP-20 and TSP-50. We report tour length L(Tour)L(Tour) and the optimality gap (both lower is better). Method TSP-20 TSP-50 L(Tour)L(Tour) ↓ Gap ↓ L(Tour)L(Tour) ↓ Gap ↓ SymmetricDiffusers with GPL [34] 5.4342 0.4169 12.8525 1.2618 Soft-Rank Diffusion with cGPL Ours 3.8732 0.0079 5.7336 0.0078 Soft-Rank Diffusion with Pointer-cGPL Ours 3.8557 0.0034 5.7157 0.0047 Table 2 reports Euclidean TSP results on TSP-20 and TSP-50. Across both problem sizes, Soft-Rank Diffusion substantially improves over SymmetricDiffusers, reducing tour length and closing the optimality gap by more than two orders of magnitude. Moreover, the Pointer variant consistently achieves the best performance, yielding further gains over the fixed variant—especially on TSP-50—highlighting the benefit of our dynamic cGPL parameterization for prefix-dependent decoding over a shrinking candidate set. 5 Ablation Studies We study the impact of several key design choices of Soft-Rank Diffusion in Table 4. While our default configuration adopts an σ0 _0 parametrization for the cGPL reverse model, we observe that the model achieves consistently strong performance when using an σt−1 _t-1 parametrization, as also employed in Zhang et al. [34]. In contrast, when paired with the Riffle Shuffle forward process, the σ0 _0 parametrization consistently fails, leading to a severe degradation in performance across all evaluation metrics. This may be due to the intractability of the reverse transition when the forward process is defined via a riffle shuffle. Moreover, even under the shared σt−1 _t-1 parametrization, models trained with the Soft-Rank Diffusion forward process consistently outperform those using the Riffle Shuffle forward process. Finally, incorporating a biaffine pointer mechanism in the cGPL reverse model further improves performance over the vanilla cGPL variant, highlighting the benefit of explicitly modeling autoregressive selection in the reverse dynamics. 6 Conclusions We presented Soft-Rank Diffusion, a diffusion framework for permutation-valued data that bridges diffusion modeling with principled ranking distributions. By lifting permutations into a continuous latent space through soft rank representations, our approach enables a smoother and more tractable forward process than existing abrupt schemes such as riffle–shuffles, and a theoretically sound reverse solver grounded in Plackett–Luce–style likelihoods. Central to our method is the proposed contextualized Generalized Plackett–Luce (cGPL) parameterization, which conditions each selection step on the evolving prefix and generalizes prior prefix-agnostic models. Across sorting and combinatorial optimization benchmarks, Soft-Rank Diffusion consistently outperforms existing permutation diffusion and differentiable sorting approaches, with particularly strong gains on long and intrinsically sequential permutations. These results highlight the importance of context-aware reverse dynamics for scalable permutation modeling. We believe this framework opens the door to further unifying diffusion-based generative modeling with structured, likelihood-based formulations over discrete combinatorial objects. Impact Statement This paper advances methods in machine learning. We do not anticipate societal impacts that require specific discussion beyond standard considerations. References [1] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg (2023) Structured denoising diffusion models in discrete state-spaces. External Links: 2107.03006, Link Cited by: §1, §2. [2] M. Blondel, O. Teboul, Q. Berthet, and J. Djolonga (2020) Fast differentiable sorting and ranking. External Links: 2002.08871, Link Cited by: §2. [3] A. Campbell, J. Benton, V. D. Bortoli, T. Rainforth, G. Deligiannidis, and A. Doucet (2022) A continuous time framework for discrete denoising models. External Links: 2205.14987, Link Cited by: §2. [4] M. Cuturi, O. Teboul, and J. Vert (2019) Differentiable ranks and sorting using optimal transport. External Links: 1905.11885, Link Cited by: §2. [5] S. Dieleman, L. Sartran, A. Roshannai, N. Savinov, Y. Ganin, P. H. Richemond, A. Doucet, R. Strudel, C. Dyer, C. Durkan, C. Hawthorne, R. Leblond, W. Grathwohl, and J. Adler (2022) Continuous diffusion for categorical data. External Links: 2211.15089, Link Cited by: §1. [6] Y. Feng, Y. Gong, F. Sun, J. Ge, and W. Ou (2021) Revisit recommender system in the permutation prospective. External Links: 2102.12057, Link Cited by: §1. [7] I. Gat, T. Remez, N. Shaul, F. Kreuk, R. T. Q. Chen, G. Synnaeve, Y. Adi, and Y. Lipman (2024) Discrete flow matching. External Links: 2407.15595, Link Cited by: §1, §2. [8] E. Gilbert (1955) Theory of shuffling. Technical report Technical memorandum, Bell Laboratories. Cited by: §1, §2. [9] A. Grover, E. Wang, A. Zweig, and S. Ermon (2019) Stochastic optimization of sorting networks via continuous relaxations. External Links: 1903.08850, Link Cited by: §2, §4.1. [10] I. Gulrajani and T. B. Hashimoto (2023) Likelihood-based diffusion language models. External Links: 2305.18619, Link Cited by: §1. [11] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. External Links: 2006.11239, Link Cited by: §1, §2. [12] C. K. Joshi, Q. Cappart, L. Rousseau, and T. Laurent (2021) Learning tsp requires rethinking generalization. Vol. 210, p. 33:1–33:21 (en). External Links: Document, Link Cited by: §A.2. [13] M. G. Kendall (1938-06) A new measure of rank correlation. Biometrika 30 (1-2), p. 81–93. External Links: ISSN 0006-3444, Document, Link, https://academic.oup.com/biomet/article-pdf/30/1-2/81/423380/30-1-2-81.pdf Cited by: §4.1. [14] J. Kim, J. Yoon, and M. Cho (2024) Generalized neural sorting networks with error-free differentiable swap functions. External Links: 2310.07174, Link Cited by: §A.1, §4.1, Table 1. [15] Y. Koren, R. Bell, and C. Volinsky (2009) Matrix factorization techniques for recommender systems. Computer 42 (8), p. 30–37. External Links: Document Cited by: §1. [16] T. Liu (2009-03) Learning to rank for information retrieval. Found. Trends Inf. Retr. 3 (3), p. 225–331. External Links: ISSN 1554-0669, Link, Document Cited by: §1. [17] A. Lou and S. Ermon (2023) Reflected diffusion models. External Links: 2304.04740, Link Cited by: §1, §2, Figure 1, Figure 1, §3.1. [18] A. Lou, C. Meng, and S. Ermon (2024) Discrete diffusion modeling by estimating the ratios of the data distribution. External Links: 2310.16834, Link Cited by: §1, §2. [19] R. D. Luce (1959) Individual choice behavior. John Wiley. Cited by: §1. [20] TorchVision: pytorch’s computer vision library Note: https://github.com/pytorch/vision Cited by: §A.1. [21] G. Mena, D. Belanger, S. Linderman, and J. Snoek (2018) Learning latent permutations with gumbel-sinkhorn networks. External Links: 1802.08665, Link Cited by: §2. [22] F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen (2022) Monotonic differentiable sorting networks. External Links: 2203.09630, Link Cited by: §A.1, §2, §4.1, Table 1. [23] R. L. Plackett (1975) The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics) 24 (2), p. 193–202. External Links: Document, Link, https://rss.onlinelibrary.wiley.com/doi/pdf/10.2307/2346567 Cited by: §1. [24] S. Prillo and J. M. Eisenschlos (2020) SoftSort: a continuous relaxation for the argsort operator. External Links: 2006.16038, Link Cited by: §2. [25] J. Shi, K. Han, Z. Wang, A. Doucet, and M. K. Titsias (2025) Simplified and generalized masked diffusion for discrete data. External Links: 2406.04329, Link Cited by: §2. [26] J. Sohl-Dickstein, E. A. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. External Links: 1503.03585, Link Cited by: §1, §2. [27] J. Song, C. Meng, and S. Ermon (2022) Denoising diffusion implicit models. External Links: 2010.02502, Link Cited by: §1. [28] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole (2021) Score-based generative modeling through stochastic differential equations. External Links: 2011.13456, Link Cited by: §1, §2. [29] H. Sun, L. Yu, B. Dai, D. Schuurmans, and H. Dai (2023) Score-based continuous-time discrete diffusion models. External Links: 2211.16750, Link Cited by: §2. [30] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin (2023) Attention is all you need. External Links: 1706.03762, Link Cited by: Figure 4, Figure 4, §3.3. [31] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard (2023) DiGress: discrete denoising diffusion for graph generation. External Links: 2209.14734, Link Cited by: §1. [32] O. Vinyals, M. Fortunato, and N. Jaitly (2017) Pointer networks. External Links: 1506.03134, Link Cited by: §2, §3.3, §3.3. [33] T. Xie, Y. Zhu, L. Yu, T. Yang, Z. Cheng, S. Zhang, X. Zhang, and C. Zhang (2024) Reflected flow matching. External Links: 2405.16577, Link Cited by: §1, §2, §3.1, §3.2. [34] Y. Zhang, D. Yang, and R. Liao (2025) SymmetricDiffusers: learning discrete diffusion on finite symmetric groups. External Links: 2410.02942, Link Cited by: §A.1, §A.1, §A.1, §A.2, §1, §2, §3.1, §3.3, §3.3, §4.1, Table 1, Table 1, Table 2, §5. [35] L. Zhou, A. Lou, S. Khanna, and S. Ermon (2023) Denoising diffusion bridge models. External Links: 2309.16948, Link Cited by: §3.1. Appendix A Details on experimental setup A.1 4-digit MNIST sorting Dataset Following Zhang et al. [34], we generate the 4-digit MNIST dataset using the code from their official GitHub repository. For each experiment, we construct training sequences by sampling 60,00060,000 length-N sequences of 4-digit MNIST images from torchvision.datasets.MNIST [20], where N is an experiment-specific parameter. We generate an additional 10,00010,000 sequences for testing. Each 4-digit image is created on the fly by first sampling four digits uniformly at random, then drawing the corresponding digit images from MNIST, and finally concatenating them into a single 4-digit image. Model architecture For SymmetricDiffusers, we use a 7-layer encoder-only Transformer with hidden dimension 512, feedforward dimension 128, with 8 attention heads. For Soft-Rank Diffusion, we match the overall model capacity by using a 7-layer encoder–decoder Transformer, with 3 layers in the encoder and 4 layers in the decoder. We keep the hidden and feedforward dimensions the same as SymmetricDiffusers. Note: While Zhang et al. [34] use a 12-layer Transformer for N=200N=200, we use a 7-layer Transformer for all N to keep model capacity consistent across sequence lengths and ensure performance is comparable across settings. Training All models are trained on a single NVIDIA H100 GPU with batch size 64 for 120 epochs. Training data are generated on the fly at each epoch. For SymmetricDiffusers, we use the default hyperparameters from the authors’ official GitHub repository. For N∈75,150N∈75,150, where no default hyperparameters are provided, we reuse the settings for N=52N=52 and N=100N=100, respectively. Inference and metrics At inference time, we randomly generate 10,00010,000 sequences of N 4-digit MNIST images. Since each image is labeled by its underlying 4-digit number, we can obtain the ground-truth ascending order directly from the labels. We report the same three metrics as Zhang et al. [34]: Kendall–Tau coefficient, Accuracy (exact match), and Correctness (element-wise match). Kendall–Tau measures rank correlation between the predicted and ground-truth permutations; Accuracy indicates whether the two permutations are identical; and Correctness is the fraction of elements placed in the correct position. Non-diffusion model baselines We retrain and evaluate DiffSort [22] and Error-free DiffSort [14] under the same dataset setup. For DiffSort, we use the default hyperparameters from the authors’ official GitHub repository, with the odd–even sorting network, steepness 1010, and learning rate 10−3.510^-3.5. For Error-free DiffSort, we use TransformerL as the backbone and the hyperparameters listed in Table 3. Sequence Length Steepness Sorting Network Loss Weight Learning Rate 9 34 odd even 1.00 10−410^-4 15 25 odd even 0.10 10−410^-4 32 124 odd even 0.10 10−410^-4 52 130 bitonic 0.10 10−3.510^-3.5 75 135 bitonic 0.10 10−3.510^-3.5 100 140 bitonic 0.10 10−3.510^-3.5 150 170 bitonic 0.10 10−3.510^-3.5 200 200 bitonic 0.10 10−410^-4 Table 3: Hyperparameters for Error-Free Diffsort on 4-digit MNIST sorting A.2 TSP Dataset For TSP-20 and TSP-50, we use the dataset from Zhang et al. [34], which is adapted from Joshi et al. [12]. The training set contains 1,512,0001,512,000 graphs, and the test set contains 1,2801,280 graphs. Model architecture For SymmetricDiffusers, we use a 16-layer encoder-only Transformer with hidden dimension 1024, feedforward dimension 256, with 8 attention heads. For Soft-Rank Diffusion, we match the overall model capacity by using a 16-layer encoder–decoder Transformer, with 8 layers in the encoder and 8 layers in the decoder. We keep the hidden and feedforward dimensions the same as SymmetricDiffusers. Training All models are trained on a single NVIDIA H100 GPU for 50 epochs with batch size 64. We use a peak learning rate of 2×10−42× 10^-4 with a cosine decay schedule and 51,60051,600 warm-up steps. Inference and metrics At inference time, we evaluate on the 1,2801,280 held-out test graphs and report two metrics: the tour length of the predicted solution, LpredL_pred, and the optimality gap relative to an OR solver baseline, LORL_OR. The optimality gap is defined as Gap=Lpred−LORLORGap= L_pred-L_ORL_OR Appendix B Derivations Here we derive the reverse conditional transition kernel q(zs∣zt,z0,z1)q(z_s z_t,z_0,z_1) for 0<s<t<10<s<t<1 in Eq. 6. We present the derivation for a single scalar soft-rank coordinate; the N-dimensional extension follows by independence across coordinates. For the (unreflected) Brownian bridge with noise scale η, the marginal at time u∈(0,1)u∈(0,1) is Gaussian: q(zu∣z0,z1)=(zu;μ(u),η2u(1−u)),μ(u)≔(1−u)z0+uz1.q(z_u z_0,z_1)=N\! (z_u;\,μ(u),\,η^2u(1-u) ), μ(u) (1-u)z_0+uz_1. (17) A convenient representation of a Brownian bridge is zu=μ(u)+ηbu,u∈[0,1],z_u\;=\;μ(u)+η\,b_u, u∈[0,1], (18) where bub_u is a standard Brownian bridge with b0=b1=0b_0=b_1=0 and covariance Cov(bs,bt)=min(s,t)−stCov(b_s,b_t)= (s,t)-st. Therefore, conditional on (z0,z1)(z_0,z_1), the pair (zs,zt)(z_s,z_t) is jointly Gaussian with means [zs∣z0,z1]=μ(s),[zt∣z0,z1]=μ(t),E[z_s z_0,z_1]=μ(s), [z_t z_0,z_1]=μ(t), (19) variances vs≔Var(zs∣z0,z1)=η2s(1−s),vt≔Var(zt∣z0,z1)=η2t(1−t),v_s (z_s z_0,z_1)=η^2s(1-s), v_t (z_t z_0,z_1)=η^2t(1-t), (20) and covariance (for s<ts<t) cst≔Cov(zs,zt∣z0,z1)=η2(min(s,t)−st)=η2s(1−t).c_st (z_s,z_t z_0,z_1)=η^2 ( (s,t)-st )=η^2s(1-t). (21) Hence, writing μs≔μ(s) _s μ(s), μt≔μ(t) _t μ(t) and c≔cstc c_st, q(zs,zt∣z0,z1)=([zszt];[μsμt],[vsccvt]),q(zt∣z0,z1)=(zt;μt,vt).q(z_s,z_t z_0,z_1)=N\! ( bmatrixz_s\\ z_t bmatrix; bmatrix _s\\ _t bmatrix, bmatrixv_s&c\\ c&v_t bmatrix ), q(z_t z_0,z_1)=N(z_t; _t,v_t). (22) By Bayes’ rule, q(zs∣zt,z0,z1)=q(zs,zt∣z0,z1)q(zt∣z0,z1).q(z_s z_t,z_0,z_1)= q(z_s,z_t z_0,z_1)q(z_t z_0,z_1). (23) Since the denominator does not depend on zsz_s (for fixed ztz_t), it suffices to view the joint density as a function of zsz_s and complete the square. Let x≔zs−μsx z_s- _s and y≔zt−μty z_t- _t. Using the closed-form inverse for a symmetric 2×22× 2 matrix, the inverse of the covariance matrix is then [vsccvt]−1=1D[vt−c−cvs],D≔vsvt−c2. bmatrixv_s&c\\ c&v_t bmatrix^-1= 1D bmatrixv_t&-c\\ -c&v_s bmatrix, D v_sv_t-c^2. (24) Therefore, [xy]⊤[vsccvt]−1[xy] bmatrixx\\ y bmatrix^\! bmatrixv_s&c\\ c&v_t bmatrix^-1 bmatrixx\\ y bmatrix =1D(vtx2−2cxy+vsy2) = 1D (v_tx^2-2cxy+v_sy^2 ) =vtD(x−cvty)2+const(y), = v_tD (x- cv_ty )^2+const(y), (25) where const(y)const(y) does not depend on x (hence not on zsz_s). This yields the Gaussian conditional zs∣zt,z0,z1∼(μs+cvt(zt−μt),vs−c2vt).z_s z_t,z_0,z_1 \! ( _s+ cv_t(z_t- _t),\;v_s- c^2v_t ). (26) Substituting vs=η2s(1−s)v_s=η^2s(1-s), vt=η2t(1−t)v_t=η^2t(1-t), and c=η2s(1−t)c=η^2s(1-t) (for s<ts<t), we obtain cvt=st,vs−c2vt=η2s(t−s)t. cv_t= st, v_s- c^2v_t=η^2 s(t-s)t. (27) Hence, zs∣zt,z0,z1∼(μ(s)+st(zt−μ(t)),η2s(t−s)t),0<s<t<1.z_s z_t,z_0,z_1 \! (μ(s)+ st (z_t-μ(t) ),\;η^2 s(t-s)t ), 0<s<t<1. (28) Extension to N dimensions. Under coordinate-wise independent bridges sharing the same noise scale η, the same conditional holds with ϵ∼(0,IN)ε (0,I_N), i.e., the conditional covariance becomes η2s(t−s)tINη^2 s(t-s)tI_N. Appendix C Additional figure and tables (a) Model Architecture. (b) Pointer-cGPL factorization. Figure 4: Model architecture and Pointer-cGPL parameterization for permutation generation.We adopt a standard encoder–decoder Transformer backbone [30]. In the vanilla cGPL parameterization, the decoder states are mapped to logits via a linear output head (yielding a distribution over candidates at each step). In contrast, Panel 4(b) illustrates Pointer-cGPL, where a bi-affine compatibility module scores each encoded item representation against the current decoder state, producing step-wise logits over the input items that can be interpreted as a pointer distribution. Table 4: Ablation study over forward diffusion processes, reverse models, and parametrizations on sorting 32 4-digit MNIST images. Forward Process Reverse Model Parametrization Kendall-Tau ↑ Accuracy ↑ Correctness ↑ Riffle Shuffle GPL xt−1x_t-1 0.8610 0.5896 0.8846 x0x_0 -0.0013 0.0000 0.0312 Soft-Rank Diffusion cGPL xt−1x_t-1 0.8764 0.6425 0.8958 cGPL w/ Biaffine Pointer xt−1x_t-1 0.9074 0.7152 0.9232 Riffle Shuffle cGPL xt−1x_t-1 0.8527 0.5833 0.8758 cGPL w/ Biaffine Pointer xt−1x_t-1 0.8742 0.6404 0.8950 cGPL x0x_0 -0.0011 0.0000 0.0313 cGPL w/ Biaffine Pointer x0x_0 0.0001 0.0000 0.0314