I believe there are some major flaws with the theoretical results.
First, the proof provided for Theorem 2 is more of a sketch than a rigorous proof. Furthermore, the reasoning in the sketch contradicts statements made in the proof of Theorem 1. In particular, in the informal argument given for Theorem 2, it is stated that (lines 1335-1337):
"Note that the input can have any character appearing in it till the last character, thus the LRNN model has no way of knowing which cj to keep in memory, and it has to keep all the distinct tokens seen in an input in its hidden state to be able to solve the underlying task...the only way for LRNNs to solve this task is to keep maintaining an increasing amount of memory, LRNNs fail to learn to solve this task length generalizably."
However, in the proof of Theorem 1 (lines 1305-1306), it is stated that the hidden state can encode the output of the counting operation without the local constraint, which is unbounded. The earlier setup in Section 2.1 also allows exact computations in intermediate states, in line with the proof of Theorem 1. Thus the argument for Theorem 2 does not seem to hold as stated. For a similar reason, the informal argument given for Theorem 3 also does not hold, since the hidden states can store unbounded integers and therefore unbounded information.
Furthermore, under the current assumptions of Theorem 2, the theorem does in fact hold but for somewhat vacuous reasons which would also extend to other languages which should be expressible by the LRNN. In particular, the regularizer includes the Frobenius norm of the embedding matrix. In finite precision, the norm of the embeddings have a minimum nonzero value, so if inference procedure returns a sequence of models with bounded regularizer, then there can be at most a finite number of symbols in C with nonzero embedding. Thus, models satisfying the conditions of Theorem 2 will not be able to length generalize on target functions which need to be able to distinguish between an unbounded number of symbols in C.
Minor: F(Σ) is used several times but never explicitly defined in the paper.
We are sorry to hear that the reviewer could not follow our presentation. We thank the reviewer for engaging with us despite not following the details fully.
We would greatly appreciate feedback for how we can make the paper more accessible.
C-RASP can be thought of as a programming language, and one where if one is able to write a program for a task/function then Transformers can learn length-generalizable solutions to such functions.
These are two completely separate notions, and in a prior result by [1], the existence of a CRASP program for a task was linked to a guarantee of getting length generalization for Transformers on that task (with some simplification assumptions).
The proposed H-RASP is a superset of C-RASP with more primitives in the programming language, and thus we can write richer programs. Secondly, we were able to show in our paper that the existence of an H-RASP program guarantees that Hybrid models (i.e. language models that interleave Transformers and Linear RNNs) will length generalize, thus extending Huang et al's results to an architecture that is being more commonly used in modern LLMs.
A monoid is one of the most fundamental algebraic structures. It is a set with a single binary associative operator (which let us say we denote with '.') i.e. for elements a, b, c in a monoid, (a.b).c = a.(b.c)) and an identity element (i.e. if the identity element is e, any other element of the set satisfies the fact that a.e=a). Examples would be Natural numbers with addition as the operator or Strings acting under concatenation.