Euclidean Score-Based Generative Modeling with Permutation Semantics

Generative modeling over permutations is challenging because permutations are discrete structured objects, whereas many powerful generative samplers, including score-based diffusion models, are formulated in continuous spaces. Existing diffusion-based approaches typically bridge this mismatch either by relaxing permutations into continuous permutation surrogates or by designing discrete diffusion processes with specialized transition kernels. We propose a geometric alternative based on the coordinate ordering of centered vectors. Sorting a centered vector maps it to a permutation, and the sorting operation partitions the space into permutation-indexed regions whose facet adjacencies correspond to adjacent swaps between permutations. In this view, the learned score controls how probability mass is transported across sorting regions, thereby inducing transitions between neighboring permutations through their shared boundaries. The resulting sampler remains close to standard score-based diffusion: train in the centered Euclidean space, run the reverse diffusion, and sort once at the end. Experiments across a variety of standard benchmark tasks such as jigsaw puzzle reconstruction (structured prediction), sorting 4-digit MNIST numbers (ordering), the traveling salesman problem (combinatorial optimization), and preference-based ranking show state-of-the-art performance while remaining computationally efficient, especially compared with discrete generative methods.