- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper belongs to the empirical tradition of understanding capabilities and limitations of neural sequence models on formal languages. The authors argue that while prior empirical work tests these models on different classes of formal languages, e.g. star-free regular languages, context free languages, etc., the languages from these classes are hand-picked and might not be representative of the entire class. To combat this, the authors propose algorithms to sample languages from the following formal language classes with the full support from the entire class (in order of least general to most general): R-trivial languages, Star-free languages (that are not R-trivial), Regular Languages (that are not star free), and Context-Free Languages. The idea is that the coverage for the benchmark hence can be improved by simply sampling more languages using these algorithms. The authors then test simple RNNs, LSTMs, and Transformers, and find that while LSTMs can perfectly learn a large fraction of languages for each class, Transformers tend to struggle on all of them, especially on non-star free regular languages, where the proportion of perfectly learned languages for them is 0.
Critical strengths
-
I think the proposed algorithms and the resulting benchmarks for this work are valuable and address a genuine issue of working with hand-picked languages in prior work. Beyond benchmarking, I can see the sampling algorithms can be useful for meta-learning and in-context learning related research as well.
-
Apart from a couple of sections, the paper is written well, the background concepts are explained clearly and the problem is properly motivated.
Critical weaknesses
-
While I understand that the key contribution of the work is the sampling algorithms, there are important experiments about evaluation of the models that I feel are currently missing. For example, for transformers sinusoidal position encodings were used. It is well known from the prior work that these position embeddings show poor length generalization. Since the test set also contains strings longer than the ones from training data, the low performance of transformers might be attributed to that. It would have been helpful to see if alternates like simply using positional masking and no encodings (which has been shown to perform much better on length generalization for formal languages [1]) or modern position encoding methods that are used in LLMs like RoPE. Since transformers perform poorly on the proposed benchmark, it could be very useful to delineate the architecture choices that might influence these limitations.
-
Related to above, I think it can be useful to show whether introducing Chain-of-thought circumvents the limitations of transformers on learning the formal languages as has been motivated in prior work on learnability for the Parity language [2] and the expressiveness result from [3] that shows with CoT the expressive power of transformers rises to include all regular languages. I understand that training with CoT means introducing extra supervision (e.g. DFA states for the regular languages) but it can still be helpful to know how well the theoretical results about CoT translate to practical performance.
-
The paper is missing some form of evaluations of guarantees for the sampling algorithms to provide a convincing argument for the sampled languages to be representative of the full support of the language class. Can we be sure that the algorithms are not biased towards sampling a specific sub-set of languages, e.g., the authors talk about prior work that shows that sampling DFAs approach results in sampled languages being concentrated towards strictly local languages. While authors try to circumvent this specific issue of sampling strictly local languages, can we be sure that we simply do not narrow down to another specific sub-class of languages?
[1] On the Ability and Limitations of Transformers to Recognize Formal Languages (Bhattamishra et al., EMNLP 2020)
[2] Transformers Provably Solve Parity Efficiently with Chain of Thought (Juno Kim, Taiji Suzuki, ICLR 2025)
[3] The Expressive Power of Transformers with Chain of Thought (William Merrill, Ashish Sabharwal, ICLR 2024)
Questions for authors
For the weakness number 3, i would appreciate to know the authors’ thoughts.
3 comments
Dear reviewer GDd6,
We have updated our draft, and we'd like to let you know that we have added new experiments with NoPE to Figure 1 and Section 4.
Since today is the last day of the discussion period, please let us know if we have addressed any of your concerns.
Thank you for answering my questions and running new experiments. I understand the Weakness 3 that I mentioned in my review better now and agree with the authors response. I will increase my score by 1. The reason I am not going to a 4, is because I feel the key contribution of the work is in the empirical direction and hence missing out on the recent architectural changes (e.g. recent position encoding methods) and training / inference time methods (e.g. CoT), is still a weakness for me. But I acknowledge the contribution of the work for proposing the sampling algorithms for building and scaling formal language benchmarks.
Dear reviewer GDd6,
Thank you very much for your review and your excellent questions.
Weakness 1: You make a good point about the positional encodings. If we have time, we will add experiments with transformers with NoPE and RoPE.
Weakness 2: This is a nice idea, although it would probably need to be a separate paper (as you mentioned, it would require adding extra supervision, which would require substantial effort). We know from [3] that, under certain simplifying assumptions, transformers can simulate Turing machines (not just finite automata), so CoT should allow them to solve all of the languages we test on. It would be interesting to see if it holds up with unsimplified transformers. But for our paper, we're mostly interested in testing the theories that pertain to transformers without CoT (i.e., R-trivial and star-free languages).
Weakness 3: This is a great question and one that we thought about quite a lot. First, we'd like to point out that a language class is just a set of languages, so every infinite language class contains an infinite number of sub-classes---some are just more famous than others, like the star-free languages. Moreover, one cannot distribute probability uniformly over an infinite set of languages, so any distribution one picks inevitably assigns most of the probability to a sub-class of languages while the rest sit in the long tail. The question of whether that sub-class is too simple depends on the specific claims that one is testing; and if there are no such specific claims, it is simply subjective. In our case, we are testing specific claims about the language class that transformers can express, so we only need to avoid specific sub-classes (cf. Figure 1). Additionally, as described in Section 3.5, we calibrate the parameters of the language distributions so that they have similar average difficulties. This ensures that none of the distributions concentrate on a sub-class of languages that are trivially easy (see the "3-Gram Classifier" rows in Table 1).