acceptodds
Withdrawn from ICLR 2027

The Limits of Algorithm Acquisition in Sequence Models

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

Abstract

Can neural networks acquire computational procedures absent from training? Prior evaluations are confounded by the possibility that a model saw the target task during pretraining. We introduce , a procedurally generated benchmark in which target computations are sampled only after a pretrained model is fixed, isolating acquisition of genuinely unseen functions from primitive familiarity. Each target is a previously unseen member of a small, structured computational family – not an open-endedly novel procedure – but rapid acquisition of such a target is itself a nontrivial, underexamined question, and we claim no more than that. In small, controlled synthetic sequence models – not Internet-scale language models – we find a sharp acquisition bottleneck: single-stream computations are learned to near-perfect accuracy, while non-separable two-stream computations – additive or multiplicative combinations of raw stream values, and arbitrary joint lookups alike – fail catastrophically. Separability, not stream count, governs the outcome: two-stream targets built from two independently sampled, information-compressing per-stream transformations ( or ) are learned as well as single-stream targets, even though the same combination of untransformed streams fails completely. Separability alone is not sufficient, however – a bijective (information-preserving) separable variant fails just as badly, a result we report but do not fully explain. The failure persists across Transformer, recurrent, and convolutional architectures; a parameter range; and larger optimization budgets. Fixing one input stream restores near-perfect learning of the same target, and coupling the two streams progressively restores performance, localizing the bottleneck to jointly combining two independently varying streams – not to sequential state, target complexity, or capacity. Pretraining does not reliably remove this bottleneck in our setting; whether it persists at frontier scale remains open. NORA offers a framework for studying what pretrained representations contribute to acquiring genuinely new computations, and for locating exactly where that transfer breaks down.

Primary area:
learning theory
Keywords:
neural networks, NORA, unseen functions, procedural learning, generalization, separability, two-stream computation, pretraining, transformers, representation learning, transfer learning, synthetic benchmarks, computational bottleneck, function acquisition, machine learning

Reviews

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

In this paper the authors introduce NORA, a benchmark of algorithmic tasks used to evaluate how well sequence models can learn and generalize computational procedures (e.g., additive [z=x+y], additive+state [z=2x+3y+c], etc.). This benchmark is used to investigate three questions. First, the authors investigate whether pretraining helps (it does not, at least when we look at the overall results). Then, they identify separability (with exception) as the main discriminator of learnability, ablating the result on different factors (architecture type, task framing and complexity, optimization budget). Finally, they test whether changing the pretraining data or increasing the size of the model helps with learning non-separable tasks (it does not).

Critical strengths

Studying how sequence models learn algorithmic procedures is a genuinely interesting problem.

Critical weaknesses

A major weakness of this submission is its lack of novelty compared with prior work, which substantially (if not entirely) overlaps with the proposed contributions and is not properly addressed in the related work section. This is especially problematic, since most of them are not concurrent or contemporary works (this line of research mostly flourished between 2022 and 2025).

In particular:

  • Wu et al. (2024), Bhattamishra et al. (2024) and Dziri et al. (2023) already extensively studied the relation between memorization and generalization in arithmetic and algorithmic tasks.

  • Zhou et al. (2023), Lee et al. (2023), Shen et al. (2023), and McLeish et al. (2024) investigated failures in simple arithmetic tasks, identifying positional indexing as the main culprit for these failures, and proposed solutions to it. These techniques are not ablated against in NORA.

  • Lippl and Stachenfeld (2024) already investigated a very similar hierarchy of tasks (conjunction-wise additive and non-additive tasks), providing a kernel-based theory of when and how sequence models can learn arithmetic

  • Level 1 tasks are equivalent to simple finite-state transducers. Their learnability by sequence models has also been extensively studied in previous works, such as Delétang et al. (2022) and Merrill et al. (2024)

Other than this, the writing itself is hard to follow. Sentences are often too long, spanning multiple lines and conveying many messages at once. The abuse of em dashes does not help clarity. Furthermore, the exposition of the results is very unclear. I dislike embedding most of the results in the text and/or pushing them to the appendix, as it makes parsing them in a structured, meaningful way extremely hard. Many important details are also scattered across the entire text. For instance, I did not get what the authors meant by “computational families” until Table 2 in Page 7. Finally, I do not see how the results in this paper might be informative at scale.

The text also contains some typos:

  • Line 320 starts with an em dash; it looks like some text was cut there.

  • In many tables, e.g., Table 3, entries are preceded by “¿”


Dziri, Nouha, et al. "Faith and fate: Limits of transformers on compositionality." Advances in neural information processing systems 36 (2023): 70293-70332.

Wu, Zhaofeng, et al. "Reasoning or reciting? exploring the capabilities and limitations of language models through counterfactual tasks." Proceedings of the 2024 conference of the north american chapter of the association for computational linguistics: Human language technologies (volume 1: Long papers). 2024.

Bhattamishra, Satwik, et al. "Understanding in-context learning in transformers and llms by learning to learn discrete functions." International Conference on Learning Representations. Vol. 2024. 2024.

Zhou, Hattie, et al. "What algorithms can transformers learn? a study in length generalization." International Conference on Learning Representations. Vol. 2024. 2024.

Lee, Nayoung, et al. "Teaching arithmetic to small transformers." arXiv preprint arXiv:2307.03381 (2023).

Shen, Ruoqi, et al. "Positional description matters for transformers arithmetic." arXiv preprint arXiv:2311.14737 (2023).

McLeish, Sean, et al. "Transformers can do arithmetic with the right embeddings." Advances in Neural Information Processing Systems 37 (2024): 108012-108041.

Lippl, Samuel, and Kim Stachenfeld. "When does compositional structure yield compositional generalization? a kernel theory." arXiv preprint arXiv:2405.16391 (2024).

Merrill, William, Jackson Petty, and Ashish Sabharwal. "The illusion of state in state-space models." arXiv preprint arXiv:2404.08819 (2024).

Delétang, Grégoire, et al. "Neural networks and the chomsky hierarchy." arXiv preprint arXiv:2207.02098 (2022).

Questions for authors

Q1. In related works you cite some works on grokking. However, your pre-training only processes 20M tokens (625 steps at batch size 16) or 2000 steps at batch size 32 for tasks-specific training runs. However, the works that you cite on grokking show that some tasks like modular addition and multi-stream indexing might require tens of thousands of gradient steps to be learned. Have you tried extending your evaluation to this regime?

Q2. To verify whether the observed failures are an artifact of positional indexing or not, could you try to apply some of the techniques proposed in the provided related works (e.g. interleaved tokens or positional IDs)?

Q3. In the bijective vs. non-injective experiment, non-injective functions f,gf,g introduce marginal correlations between a single stream xix_i and the output ziz_i (the staircase property of Abbe et al., 2021). Can you run an experiment using a non-separable joint table F(x,y)F(x,y) that also has non-zero marginal mutual information I(z;x)>0I(z;x)>0? If this is learnable, the bottleneck might actually be explained as zero-marginal-correlation compounded by positional distance, not functional separability.


Abbe, Emmanuel, et al. "The staircase property: How hierarchical structure can guide deep learning." Advances in Neural Information Processing Systems 34 (2021): 26989-27002

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

This paper is about the extent to which transformers can learn algorithms that it hasn't see directly during training, but of which it has seen components. The paper compares different model setups (scratch training, in-context learning, rule following and fine-tuning), across a set of different model architectures. Scratch training is the only one that shows some success, and it only succeeds when the target effectively depends on one input stream, or when the two streams are passed through random, information-losing per-stream lookup tables before being added or multiplied.

Critical strengths

The core idea of the paper is of interest.

Critical weaknesses

The paper is very hard to read, and many concepts are used before a definition or without a definition (e.g., "separable", "active streams", "trivial-transform" etc. The text parts are rather disconnected and poorly motivated, and full of LLM-phrases.

The paper’s headline says separability decides success, but its own table contradicts this statement: z = x + y is perfectly separable (f = g = identity) but fails. Bijective f(x)+g(y) is also separable and fails, too. Separability alone hence doesn’t predict what is going on.

The paper uses the idea of pretraining but real-world pretraining contains trillions of tokens vs here they have 20M tokens. The paper doesn't justify any choices.

Each of the experiments in this work uses synthetic data -- there is no real-world task anywhere in the benchmark, and they admit it themselves: results may not transfer to natural mathematical, programming, or scientific reasoning. This makes the motivation of this work very weak.

It is unclear that the architectures can even express the tasks that the authors are trying to make them learn. Such small-scale experiments, without concrete theoretical support, amount to mere speculation.

The paper also contains many hints of completely LLM-driven research that has very little value -- The entire introduction has no citations; The relevant work is all from the LLM side but the focus of the work is completely different; Appendix K is a generic eight-item checklist unconnected to any results; Appendices have a lot of ¿ (inverted question marks); usage of phrases like "sharp bottleneck", "rapid acquisition", etc.

Questions for authors

why is a 20M-token corpus enough? why character tokenization?

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

The paper introduces NORA, a controlled benchmark that freezes pretrained weights before target algorithm generation, avoiding pre-exposure to specific targets and enabling analysis of familiar computational primitives. For gradient-driven algorithm acquisition in small autoregressive models, the bottleneck stems from joint computation across independent input streams instead of stream quantity. Separability alone cannot guarantee learnability: learnable tasks often involve non-injective, compression-inducing per-stream transforms, whereas certain separable bijective tasks remain unlearnable. While this highlights the relevance of input compression, the root mechanism is left open.

Critical strengths

The topic investigated in this paper is important.

Critical weaknesses
  1. Separability and effective input-domain compression are not adequately disentangled. The random (f,g) for the separable condition in Table 1 and Figure 1 are almost surely non-injective, compressing the 100 input pairs to around 46 unique transformed values, whereas bijective or identity-based separable tasks fail under the same additive structure. Success may thus arise from compression instead of separability. Though noted in Section 6.2.1 and Appendix I.2, this confounder is not experimentally isolated, leaving the bottleneck explanation weakly supported.
  2. The manuscript overuses spaced en dashes for parenthetical remarks, especially in the abstract and introduction. Although acceptable under some conventions, this frequent interruption disrupts flow and reduces readability. More concise sentences and fewer parenthetical interruptions would improve the writing.
  3. Unwanted line breaks and LaTeX macros remain present in the web-rendered abstract, suggesting the authors have not carefully proofread the submission.
  4. The paper contains excessive defensive language that substantially degrades readability. The authors repeatedly disavow unintended claims and preempt potential reviewer concerns throughout the text, with repetitive qualifiers hedging the core insight.
Questions for authors

Please refer to weaknesses.

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

Related papers

Discussion (0)

Sign in to comment.