- 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 introduce marginal correlations between a single stream and the output (the staircase property of Abbe et al., 2021). Can you run an experiment using a non-separable joint table that also has non-zero marginal mutual information ? 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