- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper describes several theoretical results on the state tracking capabilities of sequence models (transformers / gated delta-net), and it introduces a new state tracking benchmark along with performance results of the different models. Both the theoretical results and the benchmark are derived from the perspective of the Krohn-Rhodes theory, which studies the decomposition of finite state automatons into simpler ones. The authors argue that this perspective onto state tracking gives rise to a natural hierarchy of tasks, forming the basis for the theoretical results and benchmark.
Critical strengths
The paper is very informative and well-written, and I truly enjoyed diving into the rabbit hole of Krohn-Rhodes theory alongside reading the paper. I used to consider group structure as key aspect to consider in the context of studying state tracking, and this work made me rethink this (in favor of monoids, allowing for studying exactly the interplay between information-preserving and information-erasing structures).
Studying state tracking capabilities through the Krohn-Rhodes perspective seems to close a critical open gap in our understanding of what models can and cannot do.
Critical weaknesses
The paper could be more accessible. For example, it took me an effort to really appreciate the role of periodicity and presence/absence of non-trivial group structure in studying state tracking. This may be because I wasn’t familiar with Krohn-Rhodes theory. But I suspect many potential readers won’t be.
A high level criticism of the line of work studying representation capabilities of models could be that the question “what can a model do” may be less important in practice than the question “how well can a model efficiently learn“ (in terms of data efficiency, generalization, etc.). For example, the fact that certain variants of transformers are Turing-complete does not change the fact they can be extraordinarily hard to train to generalize on even simple tasks like Parity. I admit that this is a somewhat philosophical point though.
Questions for authors
The sensitivity analysis seems really interesting and would have been worth elaborating on more deeply in my opinion. Similarly, for the CruxEval experiments, as these help make the paper much more directly practically relevant.
There is no detailed mention of the experimental details, like the amount of training data, mentioned in the main text.
Small typo, line 130: “these types of monoids is in terms of”?
3 comments
Expressivity vs Learnability: Personally, I believe expressivity analyses on their own will ultimately prove to be insufficient for characterizing what models are good at or able to do. It seems likely that there will be no way around incorportating insights from learning theory and thinking about inductive biases and generalization to gain any real insights.
That being said, I agree that results on expressivity help us understand the models better, and I stand by my rating (which is already 4).
Thank you again for reading our work and for giving helpful comments and critiques. We sincerely appreciate the time you have dedicated to reviewing our paper and helping improve it.
Response to Reviewer QtK8
Thank you for your careful reading and thoughtful review of our work. We offer the following for your specific questions.
Accessibility. We sympathize with this point; if accepted, we will use the additional page of room to provide more intuition on how these algebraic concepts relate to the practical implications for data distributions, in particular about the role of periodicity.
Expressivity vs Learnability. We agree with this broad point. Two of our specific results highlight this contrast: first, the fact that sensitivity curricula help transformers, and second, the fact that GDN+-/Hybrid+- models fail at generalizing on general finite data despite being able to express it. We will more explicitly note that we hope these kinds of non-expressivity failures from our benchmark can be used to advance progress on learnability as well.
Typos. Thank you! This will be fixed.
Experimental Details. We will add the following details in an appendix. For all direct training experiments, we use 275m-parameter models trained from scratch. Models use the Dolma2 tokenizer. We train using the AdamW optimizer with values β1=0.9,β2=0.95 with non-embedding weight decay of 0.1. Peak learning rate is ≈1.7×10−3. We use a WSD-S schedule. Global batch size is ≈0.6M. We use a 1× Chinchilla multiplier for data volume, which amounts to ≈5.5B tokens. For frontier models, we use generative scoring with a cap of ≈16k output tokens per request, inclusive of reasoning tokens; truncated replies, which happened only very infrequently, score as incorrect. We use the provider-default reasoning levels for each model, and evaluate 10 samples per length tier and complexity class.
In addition to these points, we have slightly revised our statement of Theorem 1:
Theorem 1. After submission, we realized that the upper bound of Aprd on GDNf+ that we cited in prior work depends on a particular choice of fixed-precision arithmetic. Prior work has largely assumed one specific fixed-precision model, but we think a slightly revised and generalized definition more accurately incorporates how rounding works in fixed-precision environments, and is a better model for GDNs as typically instantiated in practice. We have therefore revised Theorem 1 to GDNf+⊋Aprd and exhibited a specific example of a GDN+ model that can solve a soluble problem, if one admits rounding. This change better accords with our experimental results, which showed GDN+ and Hybrid+ models generalize far better than would otherwise be predicted on the Soluble split of StateBench.