REVIEW 4 major objections 4 minor 39 references
Learning Distributions over Permutations and Rankings with Factorized Representations
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Permutation codes turn ranking into ordinary token prediction, the paper claims.
desk verdict The representation theory is clean and the jigsaw results are genuinely strong, but the paper's headline claim about learning non-trivial distributions at low compute is not actually measured by the benchmarks as presented. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the family of factorized representations: the right-Lehmer code $L(X)_i$ counts smaller elements to the right of $X_i$; the Fisher-Yates draws record the swap offsets of the shuffle that produces $X$; and the insertion vector $V(X)_k$ records the slot, relative to a reference ranking, into which the $k$-th reference item is inserted. The load-bearing property is that each code is a bijection with the symmetric group, so the support constraint that all outputs must be valid permutations is enforced purely by the token domains, not by a learned constraint. The paper also derives Theorem 4.3, $V(X)_k = k - L(X^{-1})_k$, which reduces insertion-vector decoding to a Lehmer-code decode of the inverse permutation and makes batch decoding practical.
What would settle it
Measure the model's full joint distribution at one forward pass on the cyclic-permutation benchmark: if the fully-factorized Fisher-Yates model does not concentrate on cyclic permutations and does not approach uniform mass over the held-out cycles as training grows, the claim that factorized representations learn non-trivial distributions at one NFE is falsified. A direct check is the KL divergence from the fitted fully-factorized code distribution to a uniform distribution over the $(n-1)$ cyclic permutations of a fixed length $n$; a value that fails to decrease with data would contradict the paper's central claim.
Extended reading notes
Core claim
The central claim is that three classic permutation encodings are not just convenient algorithms but interchangeable coordinate systems for the symmetric group that make unconstrained neural density estimation over permutations possible. The paper argues that the right-Lehmer code, the Fisher-Yates draw sequence, and the insertion vector each give a bijection between permutations and integer sequences with position-dependent ranges, so any probability mass function over permutations corresponds to some distribution over these codes and vice versa. It further shows that in the autoregressive limit these factorized models subsume Mallows' weighted model and the Repeated Insertion Model, and at one function evaluation they still describe non-trivial families instead of collapsing. A new identity, Theorem 4.3, states that $V(X)_k = k - L(X^{-1})_k$, connecting insertion vectors to left-Lehmer codes of the inverse permutation and enabling batched decoding of insertion vectors through Lehmer machinery.
Load-bearing premise
The load-bearing premise is that cross-entropy-trained conditional distributions over code tokens, including those sampled in parallel at low numbers of forward passes, approximate the target distribution on held-out data; the paper demonstrates this empirically on three benchmarks but provides no theoretical guarantee for the low-NFE regime.
Editorial extensions
If this is right
- At one forward pass, factorized representations can still represent non-trivial distributions such as Mallows' model and the Repeated Insertion Model, whereas any inline model restricted to one pass can only output a delta distribution.
- Every sample from the model is a valid permutation by construction, at any number of forward passes, eliminating the need for constrained decoding or projection onto the permutation polytope.
- On jigsaw puzzles the method reports higher accuracy than diffusion and Gumbel-Sinkhorn baselines, with masked models solving the puzzle in a single function evaluation.
- Because insertion vectors condition naturally on sub-rankings, the same trained model can predict the remaining ranking given any observed prefix, which the MovieLens experiment exploits.
- Theorem 4.3 makes insertion-vector sampling fast enough for batched inference, removing a computational obstacle to using this representation.
Reading between the lines
- A testable extension is to plug these codes into other generative training objectives, such as discrete diffusion or flow matching, rather than only masked and autoregressive losses; the bijection property should carry over and may give smoother low-temperature sampling.
- The identity in Theorem 4.3 suggests that the left-Lehmer code of the inverse permutation is exactly the insertion vector, so any algorithm or metric developed for Lehmer codes transfers immediately to insertion vectors; this could simplify future analyses of Repeated Insertion Model-type families.
- If the low-NFE family characterization from Section 6 is filled in, it may show that the one-NFE Fisher-Yates model for cyclic permutations is exactly the uniform distribution over cycles, since the positivity condition $F Y_i > 0$ is necessary and sufficient for cyclicity.
- The MovieLens setting hints that the same approach could be applied to ranking with partial preference data in recommender systems, where the item set is not fixed in advance; the paper notes this as future work.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes to learn distributions over permutations by training language models on factorized representations—right-Lehmer codes, Fisher-Yates draws, and insertion vectors—each of which is in bijection with the symmetric group. The authors argue that modelling these representations rather than the inline notation avoids the capacity collapse of fully factorized inline models, gives automatic validity guarantees, and subsumes Mallows and RIM families in appropriate conditional limits. They also prove a relationship between insertion vectors and left-Lehmer codes of inverse permutations (Theorem 4.3) to support batched decoding. Empirically, the paper reports strong results on CIFAR-10 jigsaw puzzles and introduces two new benchmarks: uniform cyclic permutations of length 10 and MovieLens re-ranking at sizes up to n=50.
Significance. The theoretical framework is attractive: the representations are simple, the bijections are standard but well packaged for deep learning, and the low-NFE compute/expressivity trade-off is practically useful. The paper includes working encode/decode code for all three representations, constructive subsumption arguments for Mallows and RIM, and a new decoding identity that, once indexing is clarified, enables batched insertion-vector decoding. The jigsaw results are strong and the new benchmarks are welcome in principle. However, the experiments designed to demonstrate learning of non-trivial distributions do not measure distributional fidelity, and two theoretical statements contain errors that need correction before the central claims are fully supported.
major comments (4)
- [Section 4.1, Eq. (4)] Equation (4) does not bound the entropy of inline models as stated. For n=4 with partition S1={1,2}, S2={3,4}, define X1 uniform on {1,2}, X2 uniform on {3,4}, and X3,X4 equal to the two remaining values in increasing order. This distribution satisfies the factorization in Eq. (2), assigns probability only to valid permutations, and has entropy 2 bits; the right-hand side of Eq. (4) is log2(3)+log2(1)=1.585 bits. The 1-NFE delta conclusion is correct, but the general capacity-loss argument for intermediate NFEs needs a corrected bound.
- [Section B.2, Theorem 4.3] In the proof of Theorem 4.3, Eq. (7) is false with the paper's stated 1-based index sets. For X=[3,5,4,1,2] and k=5, k−L(X)_5=5−3=2, while |{j<5: X_j<X_5}|=1. The identity V(X)_k=k−L(X^{-1})_k is correct when k and sequence positions are indexed from 0 (as in the code in Section D, which uses values 0..n−1), but the theorem and proof never state this convention. Restate Theorem 4.3 with one consistent indexing scheme; with 1-based indices the right-hand side should be (k−1)−L(X^{-1})_k.
- [Section 5.2, Figure 6] The cyclic benchmark in Section 5.2 reports only support and validity metrics: % unique, % unique and valid, and % unique, valid and cyclic, together with the observation that about 20% of samples fall in the training set. These metrics do not test whether the learned distribution matches the target uniform distribution over cyclic permutations. A sampler that always outputs a small set of cyclic permutations whose train/holdout split is 20/80 would pass all three checks. The paper's claim that the model 'learns non-trivial distributions even in the least expressive mode' is therefore not supported by this experiment; please add a proper distributional comparison (e.g., exact log-likelihood under the uniform law for n=10, total variation distance, or a chi-square test over the 362,880 cyclic permutations).
- [Section 5.3, Figure 7] Section 5.3 evaluates the MovieLens model with NDCG@k. NDCG@k is a top-weighted ranking-quality metric, not a proper scoring rule for the predicted distribution over rankings; a model can achieve high NDCG@k even if its uncertainty is wrong, as long as the top-k order is mostly correct. Since the paper's central claim is about learning distributions, at least one distributional metric (held-out log-likelihood or a proper scoring rule over rankings) should be reported for the MovieLens experiments, together with variance estimates.
minor comments (4)
- [Section 5.1, Figure 5] No error bars or number of seeds are reported, and the state-of-the-art claim does not compare against the Lehmer-code autoregressive baseline of Diallo et al. (2020), which is cited in Section 2; please add this comparison or justify its exclusion.
- [Section 3.1] The text 'forms a bijections with the symmetric group' should read 'forms a bijection with the symmetric group'.
- [Section 4.2, Remark 4.1] The notation P_{L_j|L_{<j}} is introduced without explicitly stating that L here denotes the right-Lehmer code; clarify the code convention to avoid confusion with the left-Lehmer code used in Theorem 4.3.
- [Section 5.2, Figure 6] The text says 'All methods can fully model the target distribution at full NFEs' but no distributional metric is shown; at minimum the plot should include a line for the uniform-law log-likelihood of the empirical samples.
Circularity Check
No circular steps: the bijection and decoding results are proved from definitions, and the only self-citations are non-load-bearing implementation references.
full rationale
The derivation chain is self-contained. Lehmer codes, Fisher-Yates draws, and insertion vectors are defined through standard external algorithms (Lehmer, 1960; Fisher and Yates, 1953; Doignon et al., 2004; Sattolo, 1986), and their bijective correspondence with the symmetric group is an immediate consequence of those definitions, not of a fitted quantity. Theorem 4.3 is proved directly in Section B.2 from the definitions of insertion vectors, inverse permutations, and left-Lehmer codes via a change of variables; the equality V(X)_k = k - L(X^{-1})_k is derived, not assumed. The Mallows and RIM containment claims (Remarks 4.1 and 4.2) are explicit specializations of the conditional distributions, so they are containment statements rather than predictions inferred from data. The only self-citations of note are to Kunze et al. (2024a,b) for Lehmer/Fisher-Yates encoding and decoding; although an author of the present paper overlaps, those references are implementation-level and the algorithms are restated as runnable code in Appendices D.1-D.3, so they do not carry the central argument. In-scope limitation statements were weighed: Section 6 concedes 'there is room for more characterization of the properties of these families of distributions in the low NFE setting', and Section C notes that n forward passes are needed for full expressivity; these are acknowledged gaps. The skeptic's point that the cyclic benchmark's % Unique / % Valid / % Cyclic metrics and the MovieLens NDCG metric do not directly measure distributional fidelity is a validation weakness, not circularity, because the model's construction and Theorem 4.3 do not rely on those measurements. No prediction in the paper is equivalent by construction to a fitted input, and no load-bearing step resolves to a self-citation chain.
Assumptions & free parameters
assumptions (5)
- standard math Lehmer codes, Fisher-Yates draws, and insertion vectors are bijections with the symmetric group.
- standard math The chain rule over a bijective representation can express any probability distribution over permutations at full autoregressive decoding.
- standard math Sattolo's algorithm, with Fisher-Yates draws restricted to positive values, generates exactly the cyclic permutations of length n.
- domain assumption Cross-entropy training on the code-token conditionals is an effective surrogate for learning the target distribution over permutations.
- domain assumption The three benchmark tasks (CIFAR-10 jigsaw, uniform cyclic permutations, MovieLens re-ranking) are representative of permutation-learning problems with practical value.
Cite this review
Pith. "Pith review of Learning Distributions over Permutations and Rankings with Factorized Representations." pith.science (2026). https://pith.science/paper/JRF3I4EW
@misc{pith2026250524664,
author = {Pith},
title = {Pith review of: Learning Distributions over Permutations and Rankings with Factorized Representations},
year = {2026},
howpublished = {\url{https://pith.science/paper/JRF3I4EW}},
note = {Machine review of arXiv:2505.24664}
}
read the original abstract
Learning distributions over permutations is a fundamental problem in machine learning, with applications in ranking, combinatorial optimization, structured prediction, and data association. Existing methods rely on mixtures of parametric families or neural networks with expensive variational inference procedures. In this work, we propose a novel approach that leverages alternative representations for permutations, including Lehmer codes, Fisher-Yates draws, and Insertion-Vectors. These representations form a bijection with the symmetric group, allowing for unconstrained learning using conventional deep learning techniques, and can represent any probability distribution over permutations. Our approach enables a trade-off between expressivity of the model family and computational requirements. In the least expressive and most computationally efficient case, our method subsumes previous families of well established probabilistic models over permutations, including Mallow's and the Repeated Insertion Model. Experiments indicate our method significantly outperforms current approaches on the jigsaw puzzle benchmark, a common task for permutation learning. However, we argue this benchmark is limited in its ability to assess learning probability distributions, as the target is a delta distribution (i.e., a single correct solution exists). We therefore propose two additional benchmarks: learning cyclic permutations and re-ranking movies based on user preference. We show that our method learns non-trivial distributions even in the least expressive mode, while traditional models fail to even generate valid permutations in this setting.
Reference graph
Works this paper leans on
-
[1]
Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete state-spaces, 2021. https://arxiv.org/abs/2107.03006
arXiv 2021
-
[2]
From ranknet to lambdarank to lambdamart: An overview
Christopher JC Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11 0 (23-581): 0 81, 2010
2010
-
[3]
Elements of information theory
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999
1999
-
[4]
Differentiable Ranks and Sorting using Optimal Transport
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranks and sorting using optimal transport, 2019. https://arxiv.org/abs/1905.11885
work page Pith review arXiv 2019
-
[5]
Bert: Pre-training of deep bidirectional transformers for language understanding, 2019
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019. https://arxiv.org/abs/1810.04805
arXiv 2019
-
[6]
ssatou Diallo, Markus Zopf, and Johannes F \
A \" ssatou Diallo, Markus Zopf, and Johannes F \"u rnkranz. Permutation learning via lehmer codes. In ECAI 2020, pages 1095--1102. IOS Press, 2020
work page 2020
-
[7]
The repeated insertion model for rankings: Missing link between two subset choice models
Jean-Paul Doignon, Aleksandar Peke c , and Michel Regenwetter. The repeated insertion model for rankings: Missing link between two subset choice models. Psychometrika, 69 0 (1): 0 33--54, 2004
work page 2004
-
[8]
Revisit recommender system in the permutation prospective
Yufei Feng, Yu Gong, Fei Sun, Junfeng Ge, and Wenwu Ou. Revisit recommender system in the permutation prospective. arXiv preprint arXiv:2102.12057, 2021
arXiv 2021
Show all 39 references
-
[9]
Statistical tables for biological, agricultural and medical research
Ronald Aylmer Fisher and Frank Yates. Statistical tables for biological, agricultural and medical research. Hafner Publishing Company, 1953
1953
-
[10]
E. N. Gilbert. Theory of shuffling. Technical memorandum, Bell Laboratories, 1955
1955
-
[11]
Stochastic optimization of sorting networks via continuous relaxations, 2019
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations, 2019. https://arxiv.org/abs/1903.08850
2019 arXiv
-
[12]
The movielens datasets: History and context
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5 0 (4): 0 1--19, 2015
2015
-
[13]
Diffusionbert: Improving generative masked language models with diffusion models, 2022
Zhengfu He, Tianxiang Sun, Kuanning Wang, Xuanjing Huang, and Xipeng Qiu. Diffusionbert: Improving generative masked language models with diffusion models, 2022. https://arxiv.org/abs/2211.15029
2022 arXiv
-
[14]
a rvelin and Jaana Kek \
Kalervo J \"a rvelin and Jaana Kek \"a l \"a inen. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information Systems (TOIS), 20 0 (4): 0 422--446, 2002
2002
-
[15]
Jorge K. S. Kamassury, Henrique Pickler, Filipe R. Cordeiro, and Danilo Silva. Cct: A cyclic co-teaching approach to train deep neural networks with noisy labels. IEEE Access, 13: 0 43843--43860, 2025. doi:10.1109/ACCESS.2025.3548510
2025
-
[16]
A new measure of rank correlation
Maurice G Kendall. A new measure of rank correlation. Biometrika, 30 0 (1-2): 0 81--93, 1938
1938
-
[17]
Generalized neural sorting networks with error-free differentiable swap functions, 2024
Jungtaek Kim, Jeongbeen Yoon, and Minsu Cho. Generalized neural sorting networks with error-free differentiable swap functions, 2024. https://arxiv.org/abs/2310.07174
2024 arXiv
-
[18]
Disk: A diffusion model for structured knowledge, 2024
Ouail Kitouni, Niklas Nolte, James Hensman, and Bhaskar Mitra. Disk: A diffusion model for structured knowledge, 2024. https://arxiv.org/abs/2312.05253
2024 arXiv
-
[19]
Practical shuffle coding
Julius Kunze, Daniel Severo, Jan-Willem van de Meent, and James Townsend. Practical shuffle coding. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 a . https://openreview.net/forum?id=m2DaXpCoIi
2024
-
[20]
Entropy coding of unordered data structures
Julius Kunze, Daniel Severo, Giulio Zani, Jan-Willem van de Meent, and James Townsend. Entropy coding of unordered data structures. In The Twelfth International Conference on Learning Representations, 2024 b . https://openreview.net/forum?id=afQuNt3Ruh
2024
-
[21]
The neural autoregressive distribution estimator
Hugo Larochelle and Iain Murray. The neural autoregressive distribution estimator. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 29--37. JMLR Workshop and Conference Proceedings, 2011
2011
-
[22]
Teaching combinatorial tricks to a computer
Derrick H Lehmer. Teaching combinatorial tricks to a computer. Combinatorial Analysis, pages 179--193, 1960
1960
-
[23]
Effective sampling and learning for mallows models with pairwise-preference data
Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwise-preference data. J. Mach. Learn. Res., 15 0 (1): 0 3783--3829, 2014
2014
-
[24]
Individual choice behavior, volume 4
R Duncan Luce et al. Individual choice behavior, volume 4. Wiley New York, 1959
1959
-
[25]
Non-null ranking models
Colin L Mallows. Non-null ranking models. i. Biometrika, 44 0 (1/2): 0 114--130, 1957
1957
-
[26]
Learning latent permutations with gumbel-sinkhorn networks
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint arXiv:1802.08665, 2018
2018 arXiv
-
[27]
The llama 3 herd of models, 2024
Meta. The llama 3 herd of models, 2024. https://arxiv.org/abs/2407.21783
2024 arXiv
-
[28]
Large language diffusion models, 2025
Shen Nie, Fengqi Zhu, Zebin You, Xiaolu Zhang, Jingyang Ou, Jun Hu, Jun Zhou, Yankai Lin, Ji-Rong Wen, and Chongxuan Li. Large language diffusion models, 2025. https://arxiv.org/abs/2502.09992
2025 arXiv
-
[29]
Monotonic differentiable sorting networks, 2022
Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Monotonic differentiable sorting networks, 2022. https://arxiv.org/abs/2203.09630
2022 arXiv
-
[30]
The analysis of permutations
Robin L Plackett. The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statistics, 24 0 (2): 0 193--202, 1975
1975
-
[31]
Language models are unsupervised multitask learners
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019
2019
-
[32]
Simple and effective masked diffusion language models, 2024
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models, 2024. https://arxiv.org/abs/2406.07524
2024 arXiv
-
[33]
An algorithm to generate a random cyclic permutation
Sandra Sattolo. An algorithm to generate a random cyclic permutation. Information processing letters, 22 0 (6): 0 315--317, 1986
1986
-
[34]
A mathematical theory of communication
Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27 0 (3): 0 379--423, 1948
1948
-
[35]
Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis K. Titsias. Simplified and generalized masked diffusion for discrete data, 2025. https://arxiv.org/abs/2406.04329
2025 arXiv
-
[36]
Neural autoregressive distribution estimation
Benigno Uria, Marc-Alexandre C \^o t \'e , Karol Gregor, Iain Murray, and Hugo Larochelle. Neural autoregressive distribution estimation. Journal of Machine Learning Research, 17 0 (205): 0 1--37, 2016
2016
-
[37]
Gomez, Lukasz Kaiser, and Illia Polosukhin
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762, 2017. http://arxiv.org/abs/1706.03762
2017 arXiv
-
[38]
Symmetricdiffusers: Learning discrete diffusion on finite symmetric groups
Yongxing Zhang, Donglin Yang, and Renjie Liao. Symmetricdiffusers: Learning discrete diffusion on finite symmetric groups. arXiv preprint arXiv:2410.02942, 2024
2024 arXiv
-
[39]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.