- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes order-learnability, measured through prequential codelength, to quantify how efficiently a fixed learner acquires the same corpus under different token prediction orders. Since the true joint entropy is invariant to factorization order, differences in prequential codelength are interpreted as differences in the finite learner's redundancy while learning. Authors compare 21 fixed orders across 13 corpora spanning natural language, code, mathematical chain-of-thought, biological sequences, VQ-tokenized images, and synthetic tasks. Interesting findings are that left-to-right is uniquely favored only for mathematical chain-of-thought; reversal has surprisingly little cost on text compared with local shuffling; order effects change with additional training; and content-dependent frequency sorting can dramatically reduce prediction loss.
Critical strengths
The experimental question is well motivated. The reversal/local-shuffle comparison is interesting. For the seven text corpora, reversal accounts for at most 5.5% of the global-shuffle excess while four-token local shuffling incurs 50–62%. This is the paper's most interesting empirical observation. Prequential codelength is a sensible operational measure. The coding interpretation is clear. An order that allows the learner to make accurate predictions earlier pays less redundancy while learning. The synthetic calibration is strong. On IID data, the instrument correctly detects no order preference; when the authors plant a Markov dependency along a particular order, the metric identifies that order as most learnable. The statistical protocol is thoughtful. The authors use eight paired runs, shared data ordering across orders, separate learning-rate tuning data, and multiplicity correction when selecting the best alternative.
Critical weaknesses
My primary concern is that the central result is based on only one learner. This is especially important because prior work cited by the authors indicates that Transformer positional and locality biases themselves affect performance under permuted orders. The paper explicitly treats those biases as part of the learner which could be inconclusive.
Scale is particularly problematic because the paper shows that the answer changes with training. The paper itself demonstrates that order rankings and gaps change as learning progresses. Figure 3 further shows that additional training narrows order differences for text but widens them for protein.
The interpretation of reversal versus local shuffling is not fully identified. This concern is especially relevant because the learner has explicit positional encodings and Transformer positional biases are known to matter under permutation.
Frequency-sorted-order experiment is interesting but not comparable to the main experiments. The finding that reversal performs similarly to left-to-right for a 17M-parameter learner does not imply that reverse generation is preferable: generation quality, inference caching, streaming, prompting conventions, downstream use, and architecture all matter. The paper explicitly does not compare downstream performance.
Questions for authors
I would consider at least one additional architecture or meaningful model-size scaling experiment important. Otherwise it is difficult to know whether they characterizes the corpora or this specific learner.
The paper could temper the causal interpretation or provide more controlled permutations matching additional structural statistics.
I think Frequency-sorted-order experiment should be presented more clearly as a conceptual upper-bound rather than one of the four main empirical findings. As implemented, it does not demonstrate a usable generation policy because the policy needs information about tokens that have not yet been revealed.
Can the authors more precisely justify the conclusion that the reversal/local-shuffle result specifically identifies local adjacency, rather than other positional structures preserved by reversal?
What practical model-design decision should the proposed order-learnability measurement inform? In particular, how should its conclusions translate to variable-order or masked-diffusion models rather than fixed permutations?
4 comments
Local adjacency and positional biases
Thank you for raising these concerns about local adjacency and positional biases. We have followed both of your suggestions: we added a controlled permutation, and we tempered the causal wording in the main text. We explain both below.
First, on reversal versus local shuffling. The two orders do differ in two respects at once. Local shuffling (for example ls4) still proceeds left to right overall and only permutes the positions inside each block: every token is predicted within one block of its original position, with the prefix outside its block complete, but its local relation to its neighbors is scrambled. Reversal keeps every token next to its neighbors, but predicts it far from its original position, and from a suffix instead of a prefix, so the global context is entirely different. For people who already know a language, a scrambled local order is fairly easy to adapt to, whereas reversed text is very hard (Mirault et al., 2018; Saberi & Perrott, 1999); our results show that for a model learning from scratch it is the other way round.
To separate the two, we have added block reversal (appendix, Table 4): the blocks are read in order, and each block from its last position to its first. Inside a block it is the same as reversal, with every adjacency kept; outside the block it is the same as local shuffling, with all earlier blocks already read in full. Adjacency is broken only once, at the head of each block. On the seven text corpora, block reversal costs 37–47%, 17–29% and 4–15% of the excess of a global shuffle at block widths 4, 16 and 64, against −2.5% to 5.5% for full reversal. A regular order can therefore be expensive too, and the wider the blocks and the fewer the cuts, the lower the cost.
Split by position inside a block (six text corpora), the token read immediately after a cut costs 2.7–6.1 bits more than under left-to-right, whereas the other tokens of the block cost only 0–0.4 bits more on average; at width 4, this single token accounts for 69–95% of the total cost.
These results show that the cost depends on how much adjacency is broken, not on the reading direction, nor on whether the order is regular. We have also softened the wording in the main text (Sections 1, 3.2 and 4.2): it now says that the results suggest, rather than establish.
Second, on whether this is only a bias of the model's positional encodings. The calibration answers this directly. On synthetic data we lay a chain of adjacent dependencies into the window along a target order and let the model read in that order. Under all nine target orders its codelength lies between 0.5839 and 0.5848 bits/token, close to the entropy of 0.5773; it is 0.5846 when the chain is laid along a global random order and 0.5845 when it is laid along the reversed order. The model itself is therefore not averse to a scrambled order of positions: as long as the dependencies follow the reading order, it learns equally well under any order. The cost of shuffling on text thus comes from how the dependencies in the data are arranged, not from a bias of the positional encodings.
Clarifying frequency-sorted orders
We agree that frequency order should be set apart from the main experiment more clearly. The submission already stated that these losses exclude the cost of communicating the order, that they are not standalone codelengths, and that the runs are separate from the main experiment. The revision now explicitly calls them assisted orders (abstract, introduction, Sections 3.2 and 4.4): the order is computed from tokens that have not yet been predicted, so it is not a usable generation policy, and the reported losses cannot be compared with the codelengths of the main experiment.
We did not use the term “upper bound” because the experiment does not establish a formal bound. Instead, we call these “assisted orders” to emphasize that the ordering itself supplies information derived from tokens that have not yet been predicted.
Limitations of downstream evaluation and implications for variable-order and masked-diffusion models
We agree: a codelength for reversal close to that of left-to-right does not make backward generation preferable. The codelength measures only how efficiently the data are learned under a given order. Because each document is seen once and scored before the update, the single-pass codelength is also a held-out loss, but it is not an evaluation of generation. The paper does not compare sample quality or downstream performance, with the single exception of exact-match accuracy on arithmetic, and it does not address practical aspects of generating in an order other than left-to-right, such as the loss of streaming output. We now state this in the Limitations section and in the appendix. We should note that every order in the paper is a fixed permutation and that we do not measure the objective of variable-order training or of masked diffusion itself, so the implication for such models is indirect. Within this scope, the results show one thing: the data themselves do not require left-to-right. Except on chain-of-thought, left-to-right has no significant advantage over its best alternative on any corpus. As far as the data are concerned, there is thus no built-in obstacle to models that are not tied to the left-to-right order, which encourages the further exploration of non-autoregressive models. We have added this point to the Conclusion of the revised paper.
Model size and architecture
Thank you for raising this single learner concern. We agree: order-learnability is by definition relative to a learner, so how far the conclusions extend across learners needs to be checked. Of the two options you name, we have added a model-size experiment (new appendix "Model size"). Model size. We repeated the single pass with a smaller and a larger learner of the same architecture: 5M and 60M parameters, beside the 17M of the main experiments, a 12-fold range; one corpus per data type (seven in all) and eight orders, with the learning rate tuned at each size.