acceptodds
Under review as a conference paper at ICLR 2027

Transformers Learn Two Competing Sorting Algorithms, and Only One Length-Generalizes

Abstract

We show that two-layer transformers trained to near-zero loss on a sorting task converge to one of two mechanistically distinct solution classes depending on their initialization. One solution class consists of solutions that do not use the second attention layer to sort, but also fail to length-generalize. The other, which uses both attention layers, length-generalizes perfectly, despite only being trained to sort sequences of a fixed length. By carefully choosing the weight initialization, we demonstrate that we can steer the model toward learning one solution or the other. We identify input types that are rare at the training length but increasingly common at longer sequence lengths as a source of this disparity in length-generalization, and find that layer-wise specialization of the second class of solutions allows them to handle these rare sequences more accurately. On the related task of finding the minimum of a sequence, we find a similar two solution-type phenomenon, but with the opposite generalization pattern, where a different form of layer-wise specialization causes the two-layer solution to length-generalize worse than the single-attention solution.

Primary area:
interpretability and explainable AI
Keywords:
Sorting with Transformers, Length generalization, simplicity bias, Mechanistic Interpretability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_zigROpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how two-layer transformers trained on algorithmic tasks can converge to one of two mechanistically distinct solution classes depending on their weight initialization. The problem statement is: transformers either learn a "single-stage" solution that doesn't meaningfully use the second attention layer and fails to generalize to longer sequences - or a "two-stage" solution that leverages both attention layers and length-generalizes perfectly. The authors demonstrate they can steer models toward either solution by adjusting the relative initialization scale between layers. They identify two key mechanisms explaining the two-stage solution's superior generalization: layer-wise specialization across gap sizes and a "hinting mechanism" in which first attention layer provides contextual information to narrow the second layer's search space. This generalization relationship is task-dependent, the authors show that for for minimum-finding the simpler single-stage solution actually generalizes better, challenging existing ideas about simplicity bias in neural networks. The paper shows examples of how neural networks can implement multiple algorithms for the same task, with different solutions exhibiting different out-of-distribution behavior depending on their internal mechanisms. I find the results interesting and also important.

Critical strengths

The submission demonstrates that two-layer transformers trained on sorting tasks converge to one of two mechanistically distinct solution classes depending on weight initialization, with dramatically different length-generalization behaviors. Only the two-stage solution generalizes to longer sequences. It challenges ideas about the simplicity bias in neural networks by showing that depending on tasks complexity-generalization relationships exist. It shows that for sorting, the more complex two-layer solution generalizes better, while for minimum-finding, the simpler single-layer solution actually generalizes better. Furthermore, and third, it provides detailed mechanistic interpretability identifying specific mechanisms (layer-wise specialization across gap sizes and a hinting mechanism where the first layer narrows the second layer's search space) that explain the two-stage solution's superior generalization, while also demonstrating practical control over which solution emerges by adjusting the relative initialization scale between layers

Critical weaknesses

The paper primarily focuses on sorting, with only brief extensions to minimum-finding and coin denomination tasks. The authors explicitly say that they have to leave a deeper study of these other tasks to future work. Additionally, the phenomena may be specific to the one-head per layer setup, as multi-head models eliminate the length-generalization failure of single-stage solutions. I would appreciate more dteails about this.

While the paper tests 4-layer transformers, the authors acknowledge they don't attempt to characterize three- and four-layer solutions mechanistically, noting that "the mechanisms identified for two layers do not generalize neatly to more layers".

Some models at vocabulary size 1024 deviate from expected patterns, showing a seed-dependent behaviour rather than vocabulary-size-dependent, maybe the findings are not fully consistent across all conditions?

The paper explicitly leaves several important questions unanswered: whether cooperative structures can be characterized in deeper models, whether solutions can be predicted reliably early in training, and whether the same seed-dependent selection occurs in larger models trained on natural data.

Questions for authors

Your experiments use relatively small vocabularies (up to 1024) and sequence lengths (training on length 16), which may not reflect real-world transformer scales. The simplified architecture with one attention head per layer and no positional encodings differs from standard transformer architectures used in practice. Please comment on this.

Your paper shows that training length affects which solution emerges non-monotonically, and models trained at small lengths have worse length-generalization. This creates a practical constraint where training configuration significantly impacts outcomes. How can this be solved?

2 comments
AuthorsOpenReview ↗

Author Response

We thank the reviewer for their kind feedback. We have addressed the reviewer's concerns and questions below.

(C1) “Some models at vocabulary size 1024 deviate from expected patterns, showing a seed-dependent behaviour rather than vocabulary-size-dependent, maybe the findings are not fully consistent across all conditions?”

(Response): We thank the reviewer for studying the appendix closely. The deviation here concerns one simplifying assumption that is used in our analysis as opposed to the main results (the classification into single-stage and two-stage models, the length-generalization gap, and the steering result), which we would like to emphasize none of which depend on this assumption. In appendix F, we study the dependence of the second attention’s scores on components of the residual stream and find that it can be computed from only the first MLP’s output, but find that there are rare checkpoints where this claim does not hold. We believe that these rare checkpoints also fit with the theme of the paper of variation between seeds.

(C2) “While the paper tests 4-layer transformers, the authors acknowledge they don't attempt to characterize three- and four-layer solutions mechanistically, noting that "the mechanisms identified for two layers do not generalize neatly to more layers".”

(Response): In the appendix, we test the paper’s central claims at 4 layers, namely that a model given more layers than the task needs can use a varying number of them depending on the seed, that this can be controlled via modifying the initialization scale, and that the solutions only using one layer still fail to length-generalize. We show that the three of these claims carry over to deeper models, using 4 layers instead of 2. In the paper, the mechanisms we describe for two layer models are part of our explanation for why the difference generalization arises in the cleanest case, but we don’t claim that they explain how cooperation between layers occurs at every depth. With more layers, since there are more ways to divide the work, we expect that the mechanisms would be correspondingly more varied and more complex, which we preferred to report honestly rather than suggesting that the two-layer explanations we describe apply exactly to deeper models.

(C3) “The paper explicitly leaves several important questions unanswered: whether cooperative structures can be characterized in deeper models, whether solutions can be predicted reliably early in training, and whether the same seed-dependent selection occurs in larger models trained on natural data.”

(Response): We listed these open questions in the paper because we see them as next steps for future work, and we appreciate the reviewer highlighting them.

(C1) Thanks, the distinction drawn is correct and supported by your paper. The classification into single-stage and two-stage solutions is defined operationally via second-attention ablation, the length-generalization gap is measured behaviorally, and the steering result is read off the ablation-defined class fraction. None of these depend on the MLP1-only residual-stream property, so the outliers do not threaten the headline findings. So I am happy with the response. Imaybe add a one-line statement in the paper identifying how many checkpoints violate which property (Appendix I provides this: 5/17 for Claim 2, 17/17 for Claim 1)

(C2) I accept the reframing: Appendix E.1 does establish at depth 4 that (i) solution type varies across seeds (four types rather than two), (ii) lowering the scale of layers 2–4 steers 14 of 50 models to a one-layer solution, and (iii) only solutions using at least two layers length-generalize. My original comment conflated the absence of mechanistic characterization with the absence of preliminary evidence, and the former was never claimed to hold at every depth.

(C3) Ok, thanks for the clarifiaction. Characterizing these as future work is appropriate; they are out of scope for a two-layer mechanistic study. I note that two quantities measured in the paper — first-layer attention on the input at gap 1 and second-attention candidate-set size — correlate strongly with final length-generalization and are natural starting points for an early-prediction probe. This is an observation, not a requirement.

Final assessment. The response resolves most of the three addressed points without altering the paper's core claims. The residual items are minor presentation matters. I hold my review score.

Reviewer_mSLbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper „Transformers Learn Two Competing Sorting Algorithims, and Only One Length-generalizes” studies how a two-layer transformer architecture learns an integer sorting algorithm. The methods use a combination of layer ablations (setting attention of one layer to zero), consideration of the attention maps, and targeted analysis of token gap impact on the outcome. The results show two general paradigms, one where a single layer is used but has problems generalizing to unseen length, and one where two layers are used which generalizes better to other lengths. Additional experiments show that for larger vocabularies (i.e., a larger integer space) both layers are required, while having longer embeddings means that a single layer is always sufficient.

Critical strengths
  1. Interesting insights into the two structures that emerge, i.e., splitting the task across two layers versus solving in a more compressed manner within one layer.
  2. Sensible hypotheses for inner workings, supported by (sometimes very) indirect evidence is collected.
Critical weaknesses
  1. While the results indicate the learned mechanism and the hypotheses seem reasonable, I am a bit disappointed that this is all only shown indirectly. The transformers considered are very small, meaning that it should be possible to directly analyze what the key and query projections do and how the tokens are encoded. Basically, the authors use interpretation methods one would typically expect to be used with large models with many heads and layers and focus on visualizations. I understand that this is likely difficult to achieve for all models trained with different seeds. But once the two algorithms were identified, I would have expected an attempt to directly demonstrate their hypothesis by selecting one or two trained models for each type of algorithm and directly inspect the attentions there. This should be feasible given the small embedding size, vocabulary size, etc and would provide (much!!) stronger evidence than just looking at how scores evolve with different token gaps.
  2. The experiment size is mostly small and if I see it correctly uses typically an embedding dimension of 64 with a vocabulary size of 64. Thus, a one-hot encoding is basically not only possible, but given that we are talking about integer sorting, possibly even an optimal choice for embedding. As later ablations show, if the embedding space is made larger, the second layer becomes irrelevant, if the embedding becomes smaller, the second layer is mandatory. I wonder if the split between paradigms is possibly only there, because the embedding is unusually large for the vocabulary size. In other words, if the embedding dimension would be a lot smaller than the vocabulary size (which is generally the case in realistic models), I wonder if this split would ever naturally occur or if there would not just always be the two-stage (ore possibly even more layer) solutions.
Questions for authors
  1. Why was there no direct inspection of the projection matrices and embeddings to determine if the hypothesis regarding the role of the layers is correct?
  2. To which degree might the result be an artifact of the unrealistically large embedding space in comparison to the vocabulary size?
2 comments
AuthorsOpenReview ↗

Author Response

We appreciate your feedback. We have addressed the reviewer's concerns and questions below.

(C1) “But once the two algorithms were identified, I would have expected an attempt to directly demonstrate their hypothesis by selecting one or two trained models for each type of algorithm and directly inspect the attentions there.”

(Response): Thank you for the feedback. We agree that inspecting weights directly is a good standard for models of this size, and we apologize that this part of our analysis was not easier to find. More details are found in the appendix, and we summarize it here.

Indeed, we have rigorously identified how the query and key embeddings interact in both attention layers and how their outputs help determine the next number through the residual stream. In Section 4.2 and Appendix F, we show that the first layer's query (for number q) and key (for number k) embeddings produce scores that peak near q and then decrease roughly monotonically (Figure 23). The first layer therefore usually attends to either the next correct number or the number after it in the sorted sequence.

We then examine how the first layer's attention affects the second layer's query and key interactions (Section 4.2; Appendices G, H; Figures 24–28). When the first layer attends to a single number, we find the windowed monotonicity mechanism (Figure 5): the second layer retains roughly the same monotonic behavior, but its interaction peaks at a key number corrected using the first layer's spike as a hint. This shows how context from the first layer changes the embeddings and the second layer's query–key interactions. This context affects the interactions only on the query side, not the key side (Figure 24). The behavior remains robust when the first layer attends to multiple numbers (Appendix H; Figures 25–27). In most checkpoints, the second layer's embeddings depend mainly on MLP1 outputs, though in rare cases the first attention output and input also contribute directly through the residual stream (Appendix F).

We also analyze how both layers affect the output logits. We distinguish direct first-layer circuits—from the input, first attention, and first MLP—from circuits after the second layer's attention. Both can contribute to the final residual-stream embedding read by the language head, separately or jointly. For smaller gaps to the next number, both contribute directly, so disabling or modifying either can change or hijack the output (Figure 4).

(C2) “[The experiment size] uses typically an embedding dimension of 64 with a vocabulary size of 64”

(Response): We would like to clarify that for the majority of experiments, the embedding dimension is much smaller than the vocabulary size. We thank the reviewer for raising this, and we apologize for a lack of clarity here. We realize that section 2 never states the embedding dimension, which made this hard to read off. All sorting experiments in the main text use embedding dimension 64 and vocabulary size 256 or larger, which make one-hot encodings impossible. We have made it more clear in the text regarding the embedding dimensions of experiments.

(C3) “I wonder if the split between paradigms is possibly only there, because the embedding is unusually large for the vocabulary size. In other words, if the embedding dimension would be a lot smaller than the vocabulary size (which is generally the case in realistic models), I wonder if this split would ever naturally occur or if there would not just always be the two-stage (ore possibly even more layer) solutions.”

(Response): We address this question with the sweeps in Appendix C. The split across solution types does occur when the embedding dimension is much smaller than the vocabulary, where at embedding dimension 64, we still see both solution types for vocabulary sizes as high as 896. The setting described by the reviewer, where the embedding dimension is equal to the vocabulary size, is the leftmost point of the sweep, where the split across types is absent, with seeds being single-stage. Thus, this provides evidence that the split is not produced by a large embedding, but the reviewer is right that the balance shifts as the task becomes harder relative to the model.

In new experiments, we find that this picture is supported by a direct analysis of the embeddings, which we add in Figure 11. Two-stage models use a more compact code, with the leading components arranging tokens along an ordered arc, which may be an additional factor in why they are favoured when embedding capacity is lower relative to the vocabulary size.

We hope these clarifications and additions address the reviewer's concerns, and we would be grateful if they would consider updating their score.

C1: Thank you for this detailed response. I must admit that I cannot follow everything from the response. The referenced figure 23 is just accuracy information. The statement may rather refer to figure 21, but this is not referenced within the text and provides information only for one specific token (z=250), i.e., would be very restrictive as supporting evidence for how QK is computed in general. For Figure 24, I see the difference in smoothness but wonder that the different x values are for Attn2 are. I also wonder what the „key-side y“ is if Attn1 is shown „vs all keys“ and how this relates to the x-axis. It also seems to me that different information is shown for Attn1 and Attn2 and I do not understand if this difference in information possibly also explains the smoother representation.

Indeed, Figure 26 shows much smoother Attn1 lines that are similar to the ones for Attn2 in Figure 24. Given that Figure 26 is apparently also not averaging about all keys, this seems to support that the reason for the more noisy Attn1 curve in Fig. 24 might just be a difference in information shown and not a difference between the attentions.

C2: Thanks, this clarifies this.

C3: Figure 9/11 are indeed very interesting. This hints that that two-stage solution rather uses a structured embedding space with meaningful semantics in clear principal components, whereas the single-stage solution is rather a „brute force“ that has a chaotic embedding which indicates that ordering is rather memorized instead of exploiting some embedding space structure. Figure 9 seems to indicate that this higher structure is required when the embedding dimension is much smaller than the vocabulary and gets relevant in this setting roughly at a factor of 10 between both and is prevalent at a factor of 20.

This is still well below realistic ratios between embedding size and vocab size. For example, ModernBERT users 50k tokens for the vocab with a 1k dimensional embedding space (factor 50), BERT has the same embedding size but only 30k tokens (factor 30), Qwen3 has 150k tokens and 4k embedding size (factor 37). So while not the extreme case of one-hot-encoding, this still strongly indicates that at realistic ratios between embedding size and vocab size a one-stage algorithm is infeasible and because it seems to be enabled by having sufficient capacity to learn sorting without having a „decent“ structure in the embedding space that enforces semantic relationships.

Thus, this issue is not resolved for me and this rather supports that the two algorithms are only possible due to the experimental setup that gave too much embedding capacity to the model in comparison to the vocabulary size. I further note that this comment goes into a similar direction as the „OLMO-comment“ from Reviewer niGX, which also wonders about whether these results are relevant for a realistic setting.

Due to this concern, I hold my score.

Reviewer_niGXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how in a toy Transformers of 2 layers the initialisation affects the solutions on sorting and related tasks. Models learn either to rely on one attention layer or to use both , and for sorting, models using both layers generalise much better to longer sequences. The authors attribute this advantage to specialisation between layers and a mechanism in which the first layer helps narrow the second layer’s search for the next number. They also show that changing the relative initialisation scales can steer training toward either solution. On minimum-finding, the generalisation pattern reverses, suggesting that generalisation depends on the learned mechanism and the task, rather than simply on how many layers are used.

Critical strengths
  • The paper shows that models with the same architecture and similarly high training accuracy can learn different computational strategies, showing why performance on the training distribution alone isn't enough to assess how a model will behave on unfamiliar inputs.

  • I appreciated the controlled initialisation experiments and targeted interventions, I think they important to study how training determins if the second attention layer becomes important for solving the task.

Critical weaknesses

Not a strong weakness but I'm quite sure the main related works section shouldn't be in the appendix. The value of a paper is also determined by how it relates to the state of the art.

  • The results are limited to the toy setting of the paper. The experiments and the results are good, but they're only correct if we consider this specific setting, and unfortunately there aren't many use cases for a 2 layers toy transformer. More specifically, sorting distinct integers from a fixed vocabulary is way different than performing natural language prediction, maybe a study using Pythia or OLMo would have helped strengthening the paper?

  • The ablation experiments show whether a model needs the second attention layer, but they don't really show how it solves the task. A single-stage model still uses both MLP layers, so removing the second attention layer doesn't mean that all computation happens in the first transformer block. Likewise, models that need both attention layers could use them in different ways. The distinction between single-stage and two-stage solutions is useful, but it doesn't by itself establish two distinct algorithms or show that one performs a simpler computation than the other.

  • I think the proposed mechanisms don't really explain what causes better generalisation. Because the attention interventions provide useful evidence for layer specialisation and for the first layer guiding the second layer’s search. But, showing that these behaviours happen is different from showing that they explain the generalisation. I think the paper need a stronger causal analysis that maybe specifically disrupt the proposed cooperation between layers and test whether performance on longer sequences drops as predicted.

Questions for authors

Since the single stage models still use both MLP layers, have you tried studying what happens in the second MLP in these models?

I think this would help understand whether the two solution classes have different computational complexity or if they just have a different way of distributing computation between attention and MLP layers.

2 comments
AuthorsOpenReview ↗

Author Response

Thank you for your feedback. Below, we have addressed the reviewer's concerns.

(C1) “The results are limited to the toy setting of the paper. The experiments and the results are good, but they're only correct if we consider this specific setting, and unfortunately there aren't many use cases for a 2 layers toy transformer. ”

(Response): Thank you for the comment and for the kind words about the experiments. We would like to emphasize that beyond interpreting how models sort, our work aims to study a fundamental question about when training uses capacity that a task doesn’t need, what factors that choice depends on, and whether it impacts generalization. We chose to train small models as it allows us to train hundreds of seeds and many configurations to compare solution types, a reason that prior work on modular addition uses small models (Zhong et al., 2023, Nanda et al., 2023).

At two layers, the behavior was richer than we expected and we believe it has to be understood at this scale before it can be understood in larger models. We also do experiments on four-layer models in the appendix which show the same main result of the number of essential attention layers depending on the seed, but the exact mechanisms are already harder to characterize there, which is why we see the two-layer case as the necessary first step, and why we see rigorously interpreting large pretrained models as a significant task out of the scope of this work.

We appreciate the suggestion of Pythia or OLMo. However, since our conclusions rely on comparing many independently trained models, and pretrained models are often available with only one or a handful of seeds, we feel that the same type of comparison is beyond the compute available for this project. We agree that studying larger models could be a natural next step, and we have modified the conclusion to reflect this.

(C2) “the ablation experiments show whether a model needs the second attention layer, but they don't really show how it solves the task. ”

(Response): We agree that the ablation on its own only shows whether the 2nd attention is needed, but we do provide evidence for how the model solves the task as it relates to the purpose of the 2nd attention when it is needed. Our evidence for how the two-stage solution works can be found in section 4, where we provide evidence of specialization across layers and cooperation between layers, with further analyses in the appendix. For example, for cooperation between layers, we compute the second attention’s score directly from the weights and show the first attention’s output shifts which key it prefers.

The reviewer is correct that single-stage models still use both MLPs. We claim that some models are not reliant on the 2nd attention and do not claim a lack of reliance on the second MLP. Section 3 states our hypothesis that the MLPs and the unembedding select the correct token from the set the first attention attends to. Our mechanistic analysis focuses on the attention layers and how they cooperate, and we treat the MLPs as transformations of the residual stream without interpreting their neurons. A closer study of MLPs in single stage models could be one valuable future direction.

(C3) “I think the proposed mechanisms don't really explain what causes better generalisation. Because the attention interventions provide useful evidence for layer specialisation and for the first layer guiding the second layer’s search. But, showing that these behaviours happen is different from showing that they explain the generalisation.”

(Response): We agree that this distinction matters. Beyond the interventions, we want to highlight some results in the paper that connect the two mechanisms to generalization. Single-stage models fail on consecutive integer inputs at the training length, which connects the failure to the gap size independent of length. Additionally, we show in the appendix that among two-stage models trained at short lengths, the degree of first-layer specialization and the candidate set size, both measured at the training length, predict how far each model generalizes.

Thank you for the clarifications. I understand the reason for using small models, especially since the study requires comparisons across many independently trained seeds. My suggestion though wasn't to repeat the full comparison on OLMO, but to add one or two targeted experiments testing whether a specific finding also appears in a larger pretrained model. These wouldn't really establish the same seed-dependent behaviour, but they could provide useful evidence about how far the proposed mechanisms extend beyond the controlled setting. I still see this as a valuable addition, while recognising that a full analysis of larger models is outside the scope of the paper.

About the point that the distinction between the solution classes concerns their reliance on the second attention layer, rather than on the whole second Transformer block, I agree that Section 4 provides evidence beyond the ablation itself. But my remaining concern is mostly with describing one solution as simpler, since the MLPs may still perform substantial computation that hasn't been fully characterised.

The failure on consecutive integers at the training length provides useful support for the explanation based on gap size. The reported relationship between specialisation, candidate-set size, and later generalisation also strengthens the argument. Could you point to the relevant appendix results and clarify how these predictions are evaluated, including whether they hold on held-out models? This would help assess how reliably the proposed measurements predict generalisation.

Overall, the response helps clarify some of the contribution. I still think the paper should distinguish evidence that the proposed mechanisms are associated with better generalisation from evidence that they cause the improvement, and qualify the claims about computational simplicity accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Author Response

We thank the reviewers for their feedback on our work. Below, we answer their questions and clarify their concerns. We have also updated the PDF with our revised manuscript, highlighting some changes in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.