acceptodds
Withdrawn from ICLR 2027

Discovering Learning-Friendly Generation Orders for Sequential Computation

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Sequential computation via autoregressive generation can make hard tasks learnable, but the generation order of intermediate steps strongly affects whether training succeeds. We address the problem of discovering a learning-friendly target order automatically, rather than designing it manually. Our key observation is that learning-friendly orders often exhibit a faster loss drop in the early stage of training. We exploit this by loss profiling, which ranks candidate orders by the early-stage loss of a single short run. To handle the factorial candidate space, we wrap loss profiling in a hierarchical global–local search over block- and within-block-level orderings. Experiments on benchmark tasks show that, in the best case, our method recovers the optimal forward order for sequences of length from random initialization and from structured initialization, lifting success rates from about 10% to near 100%. It also rediscovers the reverse-digit order for integer multiplication, reported to be efficient in prior studies. A case study in delay dynamical systems shows that learnability varies sharply even among valid topological sorts of the dependency graph. Namely, computational admissibility is not a sufficient condition for learning-friendliness.

Primary area:
causal reasoning
Keywords:
Autoregressive generation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WkF7OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies how to automatically discover a generation order that makes sequential computation tasks easier to learn. The proposed method is based on loss profiling: first briefly train a small Transformer on a mixture of targets written in different orders, then select the orders with the fastest validation loss decrease. Because the number of possible orders grows factorially with sequence length, they combine this with a hierarchical search that first chooses an order over blocks and then an order within each block. On six recurrence tasks where the forward order is known to be best, the method recovers it in the best cases for lengths up to L = 13 when starting from random candidates, and up to L = 40 when starting from structured candidates. It also rediscovers the reverse-digit order for multiplication. Finally, a case study on delay dynamical systems shows that orders consistent with the dependency graph can still differ substantially in how easy they are to learn.

Critical strengths

The observation is useful: the early validation loss of a model trained on a mixture of orders predicts which order will be learnable when trained alone. On RELU and MLP, the profiling ranking correlates well with final accuracy. The signal also appears very early, so ranking orders is cheap.

Critical weaknesses
  1. The main search results seem inconsistent with the paper's seed study. Table 3 reports single runs, while the three-seed study (Table 29) gives much lower numbers for many of the same settings. For example, SQUARE and TRIANGLE with Ps−P^-_s at L=20L = 20 drop from 100% to 2.7% and 3.5%. The paper does not explain this gap, and the L=40L = 40 results have no multi-seed check.

  2. The paper does not show that the method can discover new orders. In the recurrence tasks the best order is the forward causal order, and in multiplication it is the known reverse-digit order. In the delay systems, where the best order is unknown, the profiling ranking barely correlates with final accuracy on two tasks, and global search is worse than the best hand-designed orders on three of five tasks.

Questions for authors
  1. Could the authors report Table 3 as means over seeds with validation-based selection, and explain why it differs so much from Table 29?
Reviewer_RbxhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks how to choose the order in which an autoregressive Transformer emits intermediate targets so that a sequential computation task becomes learnable. It proposes loss profiling: train one small GPT-2 for 1–2 epochs on a mixture of target sequences under many candidate permutations, and rank permutations by early validation loss. To scale beyond a few thousand candidates, profiling is wrapped in a hierarchical search: a global stage over block-level permutations (plus reversals), then a local stage over within-block permutations. Evaluation uses six synthetic first-order recurrences (ReLU, Square, Triangle, MLP, Sine, Cubic) where the forward order is learnable and the reverse is not; integer multiplication (PROD), where the reverse-digit order is known to help; and six discrete delay dynamical systems, where the best order is unknown. Main claims: recovery of the forward order up to L = 13 from random candidates and L = 40 from structured candidates; rediscovery of reverse-digit multiplication; and evidence that a computationally admissible (topological) order is not enough to make a task learnable.

Critical strengths
  1. Clear, well-posed problem, with a useful empirical observation. Treating target order as a searchable design choice is well motivated (parity, multiplication). The delay-system study (Sec. 6, Tab. 7, Tab. 32) gives concrete evidence that topological admissibility does not guarantee learnability: on the ReLU delay network, var_first_topo stays at ≥94.5% exact match up to T = 17, while time_first falls to 0.3%. This is the paper's most informative contribution, and it bears directly on how chain-of-thought style supervision should be ordered.
  2. Cheap ranking signal that sometimes works. On the tasks where profiling works (ReLU, MLP), early-loss rankings agree well with full-retraining rankings (Spearman 0.92/0.90, Tab. 21). The budget analysis (App. E.4) shows the ranking stabilises after about 100 steps. Where it applies, this is a practical, low-cost screening heuristic.
Critical weaknesses
  1. Headline results are best-case selections, and the authors' own controlled rerun does not support them. Tab. 3 reports "single-run results from the one [of four configurations] with the highest success rate after final training" (Sec. 5.2). That is selection on the evaluation outcome. App. F.5 (Tab. 29) reruns the same 18 settings with three seeds and validation-based selection, and many bold "100%" entries in Tab. 3 collapse:

    • Square, P_r⁻, L = 10: 100.0 → 18.5 ± 5.2
    • Square, P_s⁻, L = 20: 100.0 → 2.7 ± 0.7
    • Triangle, P_s⁻, L = 20: 100.0 → 3.5 ± 0.9
    • Sine, P_s⁻, L = 20: 100.0 → 16.7 ± 5.4
    • Cubic, P_b⁻, L = 20: 100.0 → 46.4 ± 1.3

    Other entries move the other way (Cubic P_r⁻ L = 10: 0.3 → 54.5 ± 40.8; MLP 38.2 → 94.2), which suggests the two protocols also differ in more than selection. The abstract's "lifting success rates from about 10% to near 100%", and the claimed L = 13 / L = 40 recovery, rest on Tab. 3. Under a validation-selected protocol the method's reliability is far lower and strongly task-dependent. This is the main reason for my recommendation.

  2. The benchmark favours the search operators, and the gains over simple baselines are not established at matched compute. In every benchmark task the optimum is the forward or the reverse order, and the global stage explicitly adds the reversal P·Q·J of every candidate (Eq. 3). For P_s⁻ the initial pool is built by bubble-sorting toward the reverse order (Sec. 5.2). If the sorting trajectory's endpoint is included, its reversal is exactly the forward order, so "discovery" can reduce to applying J. The only task whose optimum is neither forward nor reverse (random arithmetic DAG, App. H) is evaluated with profiling alone, without the hierarchical search, and is described as "a single illustrative case". Compute is also not favourable: on the recurrence tasks, exploration costs 6.7×, 11.4× and 13.8× one full training run (Tab. 30; L = 10, 13, 40). This contradicts the general efficiency framing; the main-text Tab. 6 shows only PROD, where the ratio is below 1. Baselines are missing:

    • reverse-plus-forward (two runs);
    • successive halving or Hyperband over the same pools using the same low-fidelity signal;
    • local search or simulated annealing driven by the profiling oracle;
    • the ES baseline of App. B.2, compute-matched.

    Tab. 4 (32 orders, no selection) is acknowledged not to be compute-matched.

    Limited novelty and missing literature context. Loss profiling is a low-fidelity performance proxy of the kind standard in hyperparameter optimisation and NAS (successive halving, Jamieson & Talwalkar 2016; Hyperband, Li et al. 2018; training-speed estimators, Ru et al. 2021), and should be positioned and compared as such. The related-work section cites only Shen et al. (2023), Welleck et al. (2019) and Asano et al. (2026) on generation order, and omits work that learns or infers generation orders: insertion-based decoding with inferred order (Gu et al., 2019), the Insertion Transformer (Stern et al., 2019), variational order inference (Li et al., 2021), permutation language modelling (XLNet, Yang et al., 2019) and any-order autoregressive models (σ-GPT, Pannatier et al., 2024). Lee et al. (2024, "Teaching arithmetic to small transformers") also report gains from reversed outputs in arithmetic.

Questions for authors
  1. [Clarification] In the mixed-order profiling run, is there a token or embedding that tells the model which permutation a sample uses? If not, the same X has T different targets, and the per-order loss also measures ambiguity across the mixture. Also: with T up to 2 × 7! = 10,080 candidates and ~10⁵ samples × 1–2 epochs (Sec. 4.2), each order receives on the order of 10–20 training examples. How does this match the formal definition D̄ = ∪_t D^{P_t} (P1, Sec. 4.1), which implies m·T samples?
  2. [Clarification] Does the initial pool P_s⁻ contain the exact reverse order (the endpoint of the bubble-sort trajectory)? If it does, how often is the forward order obtained simply by the J operation in Eq. 3? Please report results with J removed, or with the trajectory truncated before the endpoint.
  3. [Clarification] Tab. 5 uses P_s (no "−") for PROD at L = 20. Does that pool contain the reverse-digit order? If so, this result is identification from candidates, not rediscovery.
  4. [Clarification] Why do Tab. 3 and Tab. 29 differ in both directions (e.g., Cubic P_r⁻ L = 10: 0.3 vs 54.5)? Which protocol should readers trust? Please move a validation-selected, multi-seed table into the main text in place of Tab. 3.
  5. [Suggestion] Report compute-matched comparisons against successive-halving / Hyperband-style screening and against the two-run forward/reverse baseline.
  6. [Suggestion] Evaluate the full hierarchical search on several random DAGs (App. H), where the optimum is neither forward nor reverse, and report the average over graphs.
  7. [Clarification] How does loss profiling differ, conceptually and empirically, from standard low-fidelity proxies used in HPO/NAS, and how is the work positioned relative to prior methods that learn or infer generation orders (e.g. Gu et al., 2019; Stern et al., 2019; Li et al., 2021)?
Reviewer_XDK5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper addresses the interesting problem of finding an ordering of the target sequential data that is more suitable for learning, i.e., a learning-friendly generation order for sequential computation tasks. Tasks whose output is a sequence of tokens can benefit from generating these tokens in a particular order, and the sought after permutation depends only on the type of task, not on the individual examples. A well-known example is integer multiplication, where transformers learn the product much more easily when its digits are generated starting from the least significant ones.

To find such orders, the paper introduces loss profiling: a small transformer is trained for a short time on a mixture of targets reordered by a set of candidate permutations, and the candidates are ranked by their validation loss. Owing to the simplicity bias of neural networks, which tend to learn easy samples first, the model learns the learning-friendly orders earlier. This is measured by the validation loss on data specific to the permutations. Since the number of permutations grows factorially with the target length, loss profiling is used as a subroutine of a hierarchical exploration procedure: a global stage searches over block-level permutations, and a local stage refines the order within the blocks.

Critical strengths

S1. Loss profiling is an appealing technique for identifying learning-friendly orders. I really enjoyed the idea of ranking candidate orders by validating on permutation specific data a small model that is trained briefly on a mixture of all of them. The technique is demonstrated well on the example tasks and performs well on them (Section 5.1).

Critical weaknesses

W1. The motivation of the method is not developed deeply enough, in two respects. First, the tasks studied are not particularly relevant in practice. Second, the computational cost of the search for the right order, and not only of the training, is discussed only very briefly in the main text (Section 4.2, and Table 6 for PROD), which makes it hard to judge the benefits of the work; the runtime breakdown for the recurrence tasks is deferred to the appendix (Table 30). I acknowledge that the tasks serve to demonstrate the phenomenon that some orders of the target sequence are easier to learn than others. However, this breakdown shows that the search is already costly for relatively moderate target lengths: for the recurrence tasks, the exploration takes up to 13.84 times as long as a final training run, and 11.42 times already at L=13L = 13, and the local stage is even omitted for L≥20L \ge 20 because it is costly (lines 344–345).

W2. The tasks are simple, deterministic computations without clear real-world implications. Not unrelated to W1, all tasks studied, including the delay dynamical systems of Section 6, are deterministic computations in which the target is a function of the input (Section A.1). Many practically relevant sequential tasks lack this functional relationship. For example, if the task is to prove a mathematical statement and the target is a sequence of statements that forms a valid proof, there is no unique proof to look for, even though one would expect proofs whose deductions respect their chronological order to be more learning-friendly (and, in practice, more often correct). Since it is unclear how the approach would apply to such settings, this limits the significance of the results.

W3. The presentation relies heavily on the appendix, which makes the paper hard to follow. I had to move back and forth between the main text and the appendix, because relevant explanations are deferred to the appendix. For example, Section A.1, which defines the task as a deterministic mapping and formalizes order sensitivity, was instrumental for my understanding of Section 3; on its own, Section 3 was not clear enough to me. Moreover, many experimental results that, I have to emphasize, are necessary for understanding the paper are deferred to the appendix, and the main text leaves gaps that can only be filled from there. The appendix contains valuable information, and it would be good to use it better in the main text. Finally, Section 4.2 would greatly benefit from a numerical example; without one, the hierarchical exploration is very convoluted to follow.

Questions for authors

Q1. Is it guaranteed that the global stage ends with a single permutation in its last iteration k=Kk = K? As far as I can see, the choice T=2K!T = 2K! gives ⌊T/(2K!)⌋=1\lfloor T/(2K!) \rfloor = 1, so this seems to hold by construction; if so, it would help to state it explicitly in Section 4.2.

Q2. How exactly is Assumption 1 (learning prefers computationally efficient orders) reflected in the design of the method?

Q3. Similarly, how is Assumption 2 (weak locality) reflected in the design of the method, and how could it be quantified, i.e., what counts as a small local reordering, and how much may it change the learning quality?

Q4. Why is loss profiling evaluated by the top-kk identification accuracy of the forward order (Figure 3 and Tables 15 to 20)? In my view, these accuracies are of limited interest: if other highly ranked candidate permutations also perform well on the task, recovering the original (forward) permutation is not essential.

Q5. Could you explain some values in the appendix tables that seem surprising to me? In line 1215 (Table 20, TRIANGLE, L=50L = 50, Pb\mathcal{P}_\mathrm{b}), the top-1, top-5 and top-10 accuracies are all 66.67%, with a median rank of 1, i.e., in one third of the runs the forward order is not even among the ten best of the 128 candidates, while it is ranked first in all other runs. Similar patterns appear in line 1222 (Table 20, TRIANGLE, L∈40,…,50L \in \\{40, \dots, 50\\}, Ps\mathcal{P}_\mathrm{s}) and in line 1187 (Table 19, MLP, L∈40,…,50L \in \\{40, \dots, 50\\}, Ps\mathcal{P}_\mathrm{s}).

Q6. In Table 16 (SQUARE), increasing the fixed target length from L=30L = 30 to L=50L = 50 improves the top-1 accuracy for Pr\mathcal{P}_\mathrm{r} (from 77.78% to 96.30%) but decreases it for Pb\mathcal{P}_\mathrm{b} (from 92.31% to 62.96%). Intuitively, I would expect a larger fixed LL to give better accuracies in general. Could you comment on this difference?

Q7. Could you explain lines 342–343 in more detail, i.e., how exactly the initial candidate sets Pr−\mathcal{P}_\mathrm{r}^-, Ps−\mathcal{P}_\mathrm{s}^- and Pb−\mathcal{P}_\mathrm{b}^- are constructed?

Feedback for the authors (not part of my assessment)

  • In Section 3, orders are permutations π∈SL\pi \in S_L applied to the target as π(Y)\pi(Y), whereas from Section 4 on they are permutation matrices PtP_t applied as YPtY P_t. I found the notation π\pi much easier to follow, and I do not see a need for the switch.
  • The added value of Assumptions 1 and 2 is not clear to me (see also Q2 and Q3).
  • The exploration seems strongly biased towards the forward and reverse orders, since in the global stage every candidate is also profiled in reversed form (the exchange matrix JJ in Eq. 3). Why was it necessary to add the reversed permutations?
  • Figure 3 does not state how many candidate permutations the top-1 accuracy refers to, nor which permutations the candidate sets contain; this only becomes clear from Section E.1 (128 candidates), Figure 9 and Tables 15 to 20. The figure alone is therefore not sufficient, and the tables are needed to interpret it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.