Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides empirical evidences of generalizability of modern neural architectures over synthetic tasks following the Chomsky hierarchy. The results generally agree with theoretical results, highlighting (again) the need for external memory.
strength_and_weaknesses: Strength
======
- A nice empirical study with clear designs and messages sent across.
- Results are useful, pointing to directions of memory, which has been somewhat neglected in the past 8 years.

Weaknesses
==========
- As with any empirical study, there is never enough experiments to 100% confirm the points. The authors have clearly articulated that in the limitations section.
- The authors pointed out that learning procedure (e.g., gradient-based) would have an important impact on the generalizability, but this was not analyzed further.
- If the empirical nature is the main focus, some statistical analysis would be useful.
- It would have been much more insightful if some in depth analysis of why models behave they way they do (e.g., LSTM after all is a RNN with state transition dynamic, Transformer is similar to feedforward net, but with clever design of attention, we can make it behave like it has some memory), and why some theoretical properties do not hold in the experiments (e.g., attention is Turing complete, but why Transformer doesn't seem to work well in designed tasks?).
clarity,_quality,_novelty_and_reproducibility: The paper is clear and likely to be reproducible. The novelty is somewhat limited due to its empirical nature and most of the properties highlighted are well-known by now.
summary_of_the_review: An useful empirical study to highlight the need for memory to clime the Chomsky hierarchy. More in depth analysis of model behaviors and learning dynamics would be much more beneficial to the community, which is currently sticking around Transformer for empirical successes.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work conducts extensive experiments, showing that the ability of common neural network architectures to learn formal languages can roughly be characterized by the Chomsky hierarchy. 

Another contribution of this paper is that, the results empirically confirmed that augmenting neural network architectures with auxiliary memory (e.g. stack or tape) is helpful for generalization in the formal language setting. (The paper under review is not the first paper that proposes this idea, but it is still good that the paper provides more evidence on this with extensive empirical results.)

strength_and_weaknesses: Strengths:

1. Some interpretation results (in Section 5.2) on some combinations of tasks and trained models are strong evidences that the models did learn some groundtruth algorithms to solve the tasks. 

2. The paper reports the empirical average accuracy of models trained and evaluated on a wide range of tasks.


Weaknesses: 

The set of interpreted/interpretable combinations of tasks and models are limited compared with the set of all claims made in this paper. In particular, when a model achieves higher-than-random but much-lower-than-perfect accuracy on some task, it remains unclear whether the model implemented a correct algorithm (up to small numerical errors), or it implemented a crude approximation. In particular, such approximation may reside in a lower level of the Chomsky hierarchy (e.g. approximating a context-sensitive task with some context-free level algorithm). The authors' claim is somewhat ambiguous on this point (see my 2nd question below).


Questions for the authors: 

1. In Figure 2(b), for the modular arithmetic task, why is there a slight increasing trend for transformers when the sequence length is between ~150 and ~300? Does this phenomenon robustly persist if you re-run it? (In comparison, all other curves in Figure 2 show a general decreasing trend.)

2. In Section 5.4, 2nd paragraph, the author stated that “Table 3 shows that Transformers generally succeed on permutation-invariant tasks: They solve Bucket Sort (CS) and demonstrate non-trivial generalization on Cycle Navigation (R).” However, Table 3 shows that on Cycle Navigation, the average accuracy is just 61.9% (random baseline = 20%). This is indeed higher than the baseline, but still seems too low to convincingly justify that the model correctly solved the task. (See my comment in the Weaknesses section above.) Could the authors provide more evidence on whether transformers indeed learns some correct algorithm for Cycle Navigation, or propose a revision of the claim that "Transformers generally succeed on permutation-invariant tasks" to make the statement more precise?

3. In Appendix A.1, the authors discusses the limitations of predicting the set of possible next tokens by mentioning that it is “incompatible with the (standard sequence) prediction setting and thus of lesser interest to the wider machine learning community.” Could you share your thoughts on whether we *should* pay more attention to the type of next token prediction tasks whose target is a set rather than a single token? In particular, I am curious to learn:
- In principle, is it fundamentally different from current approaches? (i.e. is "training with multiple labels for each sample" a good approximation of "training with a single label, different each time, for multiple steps"?)
- Practically, I can imagine some applications like auto-completing sentences in email apps or text editors. When it provides multiple candidates, it seems to me that this can be done with models trained either with single-target, or with multi-target?


clarity,_quality,_novelty_and_reproducibility: Clarity: The description of the transduction task is a little unclear. Other than that, the paper is well-written.

Quality: The empirical results cover a wide range of models and tasks.

Novelty: Although I think some pieces of the conclusions have been proposed in prior works (which tend to be less systematic and mostly case-by-case), I view the current paper under review as a systematic empirical survey, with extensive independent verifications. (I think this is still valuable information, though in the response section to this review, the authors can feel free to clarify exactly what results are new in this paper, versus what results are already known in prior works.)

Reproducibility: In the supplementary materials, the authors included codes. I assume that the authors will publicly release the codes.
summary_of_the_review: In summary, this work reports extensive empirical results. This work also includes a small number of case studies that shows the models did learn some groundtruth algorithms to solve the tasks in a limited number of settings. I think these strengths justify at least a weak accept. Satisfactorily resolving the above-mentioned weaknesses and questions may potentially justify a higher rating.



Edit after reading authors' response: 

I think the authors sufficiently addressed my main concerns about correctness and clarity by updating their paper with some additional in-depth analyses. So I increased the overall rating from 6 to 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: **High level motivation:** The authors are interested in understanding what it takes for machine learning systems to reliable generalize to novel circumstances, especially when those are out-of-distribution. 

**Research question:** Do insights from the theory of computation (specifically the Chomsky Hierarchy) inform us about the limits of neural network generalization in practice? 

**Operationalization:** The authors have:
* **(tasks)** Designed 15 tasks that cover regular, context-free, context-sensitive and recursively enumerable languages (i.e. require automatons with computational requirements that are associated with the aforementioned grammar types to solve),
* **(success definition)** Picked length generalization (ability to learn from short problem instances to generalize to longer ones ) as the target capability,
* **(architecture)** Run extensive experiments on RNNs (augmented with a stack and a tape), LSTMs and transformers (in total 10250 models),
* **(insights)** Demonstrated that the computational capabilities (i.e. access to stack or memory, a state etc.) of models roughly predict which tasks they display length generalization on. 

**Contributions:** 
* An extensive empirical study spanning multiple architectures and tasks,
* The release of a dataset to evaluate length generalization on,
* The depiction of serious failure modes regarding length generalization that can partially be explained by the (mis)match between a given model's computational capabilities and the language class the task at hand belongs to.
* Evidence that some architectural modifications (like the addition of external memory modules) might mitigate length generalization deficiencies. 


strength_and_weaknesses: **STRENGTHS**
* **Important and timely study:** Investigating the generalization patterns of sequence models is a very important research direction and comes at a time when we need more of this type of work that bridges theory and practice, and when safety concerns (that might be caused by lack of robustness under distribution shifts) are growing. 
* **Crisp problem description and task design:** The authors are very systematic in the way they pick the tasks and define length generalization as the locus of their analysis. There are many ways of framing this problem, and the way the authors have done it seems very sensible. 
* **Relatively comprehensive experiments:** While the experiments and ablations aren't exhaustive (some of the important components that are omitted will be described below), the experiments are still quite comprehensive and has a reasonable focus (i.e. on tools to augment sequence models with tools such as stacks and tapes).
* **Nontrivial and interesting insights:** The reported limitations of existing architectures have important consequences on the forecasting of AI progress. For example, it looks like naive scaling (i.e. increase model size and in-distribution data size) alone won't solve length generalization unless we get clever with training details. 
* **Nice interpretability analysis:** The interpretability analyses of RNNs with tapes and stacks confirm the intuitions one might have about why these models are able to display length generalization. 

**WEAKNESSES**
* **Missing components of ablation:** I'd like to highlight some components that seem to be missing in the experiments. (I'd like to note that no study is fully comprehensive -- I'm listing these in order to provide a balanced view of the weaknesses of the submission)
  * Convolutional architectures missing: Bansal et al. [3] have shown that fully convolutional networks show near-perfect length generalization on the prefix sum task (akin to parity). It looks like convolutional networks are also relevant in a study that focuses on the effect of architecture on length generalization. 
  * Effect of pretraining: [4] shows that pretraining data could have an effect on the inductive bias displayed by transformer models. Likewise, [2] shows that large language models (when prompted properly) can display nontrivial length generalization, which is largely due to the pretraining procedure instead of scale. 
  * Effect of depth: While RNN-like architectures "reason" through timesteps, transformers "reason" along their depth. Hence, it makes sense that a 5 -transformer -block architecture won't have the capacity to handle large depths unless there's a shallow shortcut (like there is in Bucket sort). It'd be interesting to see either very deep transformers, or universal transformers [5] investigated in this work too. 
  * No focus on autoregressive models: Autoregressive generation is what enables scratchpad strategies in transformers, which could help them attain length generalization capabilities. 
* **Missing references:** I'd like to highlight two prior work that appear to be very relevant to the current submission:
  * "Unveiling Transformers with LEGO: a synthetic reasoning task" This paper proposes a task that allows for testing encoder-only transformers' ability to display length generalization. The paper has interesting insights into what goes wrong when transformers fail at length generalization and which components (like pretraning) seem to help. 
  * "Exploring length generalization in large language models" This paper explores length generalization too, and finds that vanilla transformers lack this ability even at an extremely large scale. They show, however, that in-context learning and the use of a scratchpad significantly improves transformers' ability to posses length generalization. 

**QUESTIONS TO AUTHORS**
* What exactly is the rightmost column in Table 1? 
* The square root computation doesn't appear to be marked as requiring superlinear time in Table 3. Could you explain what linear algorithm solves this task? 




[1] Zhang, Yi, et al. "Unveiling Transformers with LEGO: a synthetic reasoning task." arXiv preprint arXiv:2206.04301 (2022).

[2] Anil, Cem, et al. "Exploring length generalization in large language models." arXiv preprint arXiv:2207.04901 (2022).

[3] Bansal et al. End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking

[4] Wu, Yuhuai, et al. "Lime: Learning inductive bias for primitives of mathematical reasoning." International Conference on Machine Learning. PMLR, 2021.

[5] Dehghani, Mostafa, et al. "Universal transformers." arXiv preprint arXiv:1807.03819 (2018).

clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality:** The paper is written very well. The introduction and background is written beautifully in a way that's succinct while discussing crucial subtleties (such as the distinction between transduction vs. recognition). The experiments and analyses are rigorous and well executed. 

**Originality:** While there exist works in the literature that also tackle the problem of length generalization (some listed above), the angle that this paper takes on it (angle of theory of computation) is novel and worthy of study. 

**Reproducibility:** To the extent I can tell, the paper provides enough details to reproduce the findings. Perhaps some low-level details on the types of initializations is missing, but the code release remedies this. 







summary_of_the_review: The authors run an extensive empirical study checking whether theory of computation can be used to predict which architectures will generalize on different tasks. To a large extent, there's a match between a given architecture's computational limitations and the requirements (in the theory of computation sense) a task requires. 

That this is a well-executed paper on an important and timely topic. I believe ICLR would be a better conference with this paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper empirically groups sequence to sequence neural architectures models according to the Chomsky Hierarchy. They achieve this by evaluating 10250 neural architectures models across 15 transduction tasks spanning the entire Chomsky Hierarchy.

They demonstrate that memory augmented architectures tend to fall higher in the Chomsky Hierarchy than those without structures memory (e.g. stack or tape). 
strength_and_weaknesses: Strengths
-------------

Formal languages are relatively under-explored in AI literature, so it is quite encouraging to see efforts in this direction. This work does a great job of identifying Chomsky’s hierarchy as a possible proxy for studying inductive biases in neural architectures and their corresponding training mechanisms for sequence prediction tasks.

This work also marries well with existing literature on the Turing completeness of neural architectures. The empirical evidence from this work, covers an important gap that was missing from the theoretical literature.

Although the results are slightly underwhelming (some architectures cannot solve tasks at their supposed level), it nevertheless demonstrates the limits of these neural architectures for sequence prediction tasks.

The results from this work have also demonstrated some interesting insight on memory augmented neural architectures, which are often less favoured for sequence prediction tasks.

Weaknesses
-----------------

The main weaknesses of this work is the disambiguation of transduction and recognition. I can appreciate that the authors have made an effort to disambiguate between the two concepts which in itself is a non-trivial feat but I don’t think it’s evident from the introduction and abstract that sequence prediction would translate to Finite State Transduction (FST) Machines instead of Finite State Automata (FSA) Machines. 

I would suggest dedicating an entire section before the background describing transduction vs recognition and FST/FSA. This was partially addressed in the background section but it is tucked away at the end and requires a couple reads to finally get the greater picture. However this doesn’t take away from the paper, as the motivation to reduce the problem to a transduction problem is justified.

- The generative grammar section could be better explained and would suggest discussing more about Chomsky’s rules as they are also vital in categorizing across Chomsky’s hierarchy. I also suggest placing the generative grammar section before the formal language section or combining the two, as this might read better.
- The per sequence accuracy equation in page 5, doesn’t seem to make sense. I would suggest revising this. Same applies for the equation in Algorithm A.1.
- The stack manipulation example in Table A.1 seems incorrect. Are you pushing an empty string? If so, would that be the result?
- The claim regarding the hard limits on scaling laws is not well explored in this paper and is only mentioned in the introduction and conclusion. I would suggest elaborating on this in the results. I think this is sadly one of the shortfalls of this paper.
clarity,_quality,_novelty_and_reproducibility: Clarity
---------
There is a lack of clarity on the Chomsky's hierarchy of transduction tasks vs Chomsky's hierarchy of language tasks, but beyond this I found the paper to be clear and an enjoyable read. The Algorithm A.1 was especially beneficial in understanding the work and would suggest adding to the main paper if space permits.

Quality
---------
I am quite happy with the quality of this work.

Novelty
---------
I find this to be novel work and I believe the field would greatly benefit from this work especially in understanding the limits of our architectures and training mechanisms.

Reproducibility
-------------------
They have open sourced a length-generalization benchmark. Yes, it should reproducible.
summary_of_the_review: I find this work to be an important contribution towards understanding the limits of our neural architectures and their corresponding training mechanisms for sequence prediction tasks. The results on memory-augmented neural architectures were similarly insightful. All in all, I am happy to accept this paper.

I am willing to reconsider my recommendation to an oral presentation if:
- Clarity around transduction and recognition is improved
- The per sequence accuracy equation in page 5 is revised
- The generative grammar section formally defines grammar and includes some dummy examples of Chomsky grammar rules.
- The claim regarding the hard limits on scaling laws is well justified.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper conducts a large-scale extensive empirical study to practically investigate whether insights in the computation theory can predict the out-of-distribution generalization limits for neural networks.

It uses more than 10 thousand models and 15 tasks to evaluate the performance of program induction neural network models on sequence prediction tasks defined in the Chomsky hierarchy. The models include state-of-the-art architectures, such as RNN, LSTM, Transformer, and memory-augmented networks, such as Stack-RNN and Tape-RNN.

It finds the relation between models and hierarchy on out-of-distribution generalization. For example, memory-augmented networks can solve high-hierarchy tasks.

It also finds that using more training data does not enable the generalization higher up in the hierarchy for some architectures.

It opensources a novel benchmark for length generalization, designed to accurately pinpoint the architectures' problems.

strength_and_weaknesses: ***Strength:***

The best strength is the scale of the evaluation.
It includes a variety of models and representative tasks in the hierarchy.

The Chomsky hierarchy is essential in computation theory. So it is reasonable to find its relation to the neural network to help understand the out-of-distribution generalization for neural networks.

***Weakness:***

I have comments and questions.

(1) This paper uses the "limit" of generalization to group neural network architectures.
It indicates that even if a model architecture works on a representative task for a Chomsky hierarchy level, it might not work on other tasks on the level.
Though it is mentioned in the "limitation," it might be worth attention because it differs from the classic automatons' case.

(2) The introduction mentions that the length generalization problem "subsumes all computable problems."
Is it for classic models like automatons, or is it also correct for neural networks?

For example, suppose a neural network is trained with short inputs starting with 'a' and can generalize to long inputs beginning with 'a'. However, it is still unclear whether it can generalize to short inputs starting with 'b.'

clarity,_quality,_novelty_and_reproducibility: The paper is clear and easy to read.

The empirical evaluation quality is high.

The novelty is to relate the Chomsky hierarchy and neural network out-of-distribution generalization and to conduct an extensive empirical study.

The paper has details for experiments, and it open-sources the benchmark.
summary_of_the_review: This paper has an extensive empirical study with high coverage of models in interest and tasks in the Chomsky hierarchy.

It has significant contributions and strengths, as mentioned above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposed a fairly thorough experimental scaffolding, exploring the capabilities of transformer-based architectures to learn (and generalize) on various tasks "sorted by difficulty" through the Chomsky hierarchy. The authors explored both vanilla transformer-based architectures, and various "memory-augmented" variants, and compile a thorough set of both positive and negative results. The reviewers, throughout the course of the discussion, suggested various additional experiments, and expository clarifications, which substantially improved the paper. The consensus is this is a good paper, that will be of interest to many in the conference. 
justification_for_why_not_higher_score: As with any probing study, the conclusions are always "somewhat provisional" --- e.g. it's difficult to exclude whether tweaks to the hyperparameters or architecture could not change the results (especially so for the negative results in the paper). Various reviewers pointed out weaknesses with both the experimental scaffolding and architectural ablations (and the authors have been forthright for some of these as well).  
justification_for_why_not_lower_score: The paper is a good large-scale, thorough study of the empirical performance of various versions of transformer-like architectures. These kinds of studies are likely to be of interest to a large fraction of the ICLR community.
Decision: Accept: notable-top-25%