Non-Asymptotic Length Generalization

We sincerely thank reviewer YXKG for their time, detailed comments, and constructive criticism.

Author statement: The submitted paper contained an error in the proofs, which we discovered only after submission. We’ve revised the proofs and sent the revised draft to the AC. Here are how the revised draft’s results differ from the submitted draft’s.

• The main result (Theorem 5.1) is unchanged except for the addition of a weak assumption to the function class $C-RASP^{2,K,T}$, that $\sum_{i \in [K]} \lambda_i > z$ for each function in $C-RASP^{2,K,T}$ (analogous to the existing assumption $z > 0$; see line 220, left col). Theorem 5.1 claims the same upper bound of $N_{A_{si}}(K,T) \leq O((KT)^{O(K^2)})$ for $C-RASP^{2,K,T}$. The proof is almost exactly the same. The significance of the result is unchanged.
• The revised draft no longer contains Theorems 5.4 and 5.6, which together were intended to extend Theorem 5.1 to prove length generalization guarantees for a class of functions which contains Dyck1 and its higher-precision variants. The absence of these side-results doesn’t affect the significance of the paper.
• Results for DFAs and CFGs unchanged.

Source of error:

• Lemma A.24 in line 1557

We apologize for the error and hope that either the reviewer can view the revised draft; or ignore Theorems 5.4 and 5.6 in their review. Thank you.

Addressing Reviewer Concerns:

The proof sketch in the main content may be quite confusing

We apologize for the lack of clarity of the proof sketch and thank the reviewer for their patience in reading through it. We will re-write it and include more details of the basis schemas in the main content.

It is yet unclear whether there’s a training setting for Transformers such that the optima correspond to the minimum C-RASP program interpolator on the training dataset.

This is true. However, there is circumstantial evidence which lends some credence to the idea of studying transformer training with the min-complexity interpolator, for some complexity measure.

• Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].

• Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].

If one assumes that there is some complexity measure $C$ such that training transformers with SGD roughly corresponds to the min-complexity interpolator with $C$ (which is strong, granted), then the RASP-L paper [3] suggests that $C$ should be RASP-L program length, as they show empirically that when the ground-truth is also a short-RASP program, then the trained model achieves far better length generalization.

[1] Abbe et. al. arxiv.org/pdf/2301.13105

[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316

[3] Zhou et. al. arxiv.org/abs/2310.16028

The C-RASP program have very restricted expressive capability

We agree.

The proven results imply that … since this require the dataset size to be exponential, this is highly unrealistic

Having all inputs of length at most O((KT)^{(O(K^2)}) is a sufficient condition for length generalization, and indeed unrealistic. A weaker sufficient condition is that for every pair of unequal functions in the hypothesis class, there is at least one (short) input which distinguishes them. The cardinality of the training set need only be at most the square of the number of hypotheses (which is $O(T^{O(K)})$ instead of $2^{ O(T^{O(K^2)})}$).

A more interesting result might be probabilistic

This is an important question. If one introduces a test or train distribution (or both) and relax the definition of length generalization, one can perhaps get more palatable sample complexity.

If one keeps the current notion of length generalization (i.e. identification) but require that the training set be drawn i.i.d. from some training distribution, we suspect that the sample complexity will be no better than our doubly-exponential sample complexity, because perfect length generalization requires one to distinguish every pair of functions in the hypothesis class. Given two very similar functions $f, f’$, we suspect the strings of length $n$ which distinguish $f$ and $f’$ may have density which is order $1/\exp(n)$. Random sampling is no better than including all strings of length n.

One could also relax the definition of length generalization from identification. One could say that length generalization is achieved if the hypothesis achieves 99% accuracy on a particular test-distribution. However, it is unclear what is a realistic test distribution is, so that the theoretical setup models practical scenarios. Also, the 99%-accuracy length generalization notion may be too weak. The 1% of examples which a learned hypothesis gets wrong could be exclusively on the long/interesting examples that we care about. If the test-distribution is supported on {0,1}$^*$, the weight of all strings length $N$ or larger will be less than 1% for N suff. large.

We sincerely thank reviewer CEK9 for their time, detailed comments, and constructive criticism.

Author statement: The submitted paper contained an error in the proofs, which we discovered only after submission. We’ve revised the proofs and sent the revised draft to the AC. Here are how the revised draft’s results differ from the submitted draft’s.

• The main result (Theorem 5.1) is unchanged except for the addition of a weak assumption to the function class $C-RASP^{2,K,T}$, that $\sum_{i \in [K]} \lambda_i > z$ for each function in $C-RASP^{2,K,T}$ (analogous to the existing assumption $z > 0$; see line 220, left col). Theorem 5.1 claims the same upper bound of $N_{A_{si}}(K,T) \leq O((KT)^{O(K^2)})$ for $C-RASP^{2,K,T}$. The proof is almost exactly the same. The significance of the result is unchanged.
• The revised draft no longer contains Theorems 5.4 and 5.6, which together were intended to extend Theorem 5.1 to prove length generalization guarantees for a class of functions which contains Dyck1 and its higher-precision variants. The absence of these side-results doesn’t affect the significance of the paper.
• Results for DFAs and CFGs unchanged.

Source of error:

• Lemma A.24 in line 1557

We apologize for the error and hope that either the reviewer can view the revised draft; or ignore Theorems 5.4 and 5.6 in their review. Thank you.

Addressing Reviewer Concerns:

the paper could be made relevant to a wider audience by discussing a broader range of prior work

We thank the reviewer for the very detailed list of references. We will add them in.

Shaw et. al. induced synchronous CFGs... I assume the apparent contradiction is resolved because ...

Yes, specific instances of CFGs, $f \in \mathcal{F}$, have different ``identification times", $N_{A_{si}}(f)$ (line 126, left column). As such, some CFGs require much longer-length data than others in order to be identified by $A_{si}$. But this doesn’t contradict that there is a particular sequence of CFGs where the identification times as a function of the complexity of the CFGs (i.e. their description lengths) can grow faster than any computable function. All CFGs have finite $N_{A_{si}}(f)$, but this doesn’t preclude some CFGs from having very large $N_{A_{si}}(f)$ which is not bounded by any reasonable function of $C(f)$.

In addition, the empirical studies of CFG induction evaluate the learned CFG on a test-set, with finite support. Achieving good accuracy on the test-set is an easier task than identification.

The results hold for a minimum complexity interpolator…

We acknowledge that it is largely unclear whether the min-complexity interpolator behaves similarly to the realistic transformer training setting. However, there is circumstantial evidence which lends some credence to the idea of studying transformer training with the min-complexity interpolator.

• Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].

• Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].

• The RASP-L conjecture [3] suggests that transformers are biased towards learning functions of short RASP-L program length.

[1] Abbe et. al. arxiv.org/pdf/2301.13105

[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316

[3] Zhou et. al. arxiv.org/abs/2310.16028

(1) If such guarantees are crucial, then it is problematic that the theoretical results do not hold for models trained in practice. (2) In practice, testing models on inputs that are arbitrarily longer than those seen during training seems sufficient for most applications.

(1) We agree

(2) (i) It isn’t clear whether for most applications, one would have access to arbitrarily long data to test whether one’s model length generalized. Long proofs of difficult theorems, for instance, are very scarce.

(ii) Even if one could generate arbitrarily long inputs to test one’s model for length generalization, for large integer $n > 0$, it would be infeasible to test one’s model on all $\exp(n)$ inputs of length $n$. One would have to choose a relatively-small representative set of examples of length $n$ which could certify that one's model has length generalized, but it isn’t clear how to do this systematically. I.i.d. samples may be too easy for the model to cheat/hack (see Fig. 6; page 9 of [4]).

Due to (i) and (ii), we hope that theoretical guarantees could increase confidence that a model has length generalized, when checking length generalization empirically is hard.

[4] Liu et. al. arxiv.org/abs/2210.10749

define “non-asymptotic” upper bound vs. “asymptotic” upper bound

Will do. A non-asymptotic upper bound of $N_{A_{si}}(c)$ is a computable upper bound of $N_{A_{si}}(c)$ in $c$, the complexity of the ground truth, only omitting universal constants with Big-O notation. Asymptotic upper bounds omit some dependencies on the complexity or they only guarantee that $N_{A_{si}}(c) < \infty$.

We sincerely thank reviewer qTut for their time, detailed comments, and constructive criticism.

Author statement: The submitted paper contained an error in the proofs, which we discovered only after submission. We’ve revised the proofs and sent the revised draft to the AC. Here are how the revised draft’s results differ from the submitted draft’s.

• The main result (Theorem 5.1) is unchanged except for the addition of a weak assumption to the function class $C-RASP^{2,K,T}$, that $\sum_{i \in [K]} \lambda_i > z$ for each function in $C-RASP^{2,K,T}$ (analogous to the existing assumption $z > 0$; see line 220, left col). Theorem 5.1 claims the same upper bound of $N_{A_{si}}(K,T) \leq O((KT)^{O(K^2)})$ for $C-RASP^{2,K,T}$. The proof is almost exactly the same. The significance of the result is unchanged.
• The revised draft no longer contains Theorems 5.4 and 5.6, which together were intended to extend Theorem 5.1 to prove length generalization guarantees for a class of functions which contains Dyck1 and its higher-precision variants. The absence of these side-results doesn’t affect the significance of the paper.
• Results for DFAs and CFGs unchanged.

Source of error:

• Lemma A.24 in line 1557

We apologize for the error and hope that either the reviewer can view the revised draft; or ignore Theorems 5.4 and 5.6 in their review. Thank you.

Addressing Reviewer Concerns:

it remains open how minimum-complexity inference based on C-RASP complexity is linked to training transformers

This is a valid point. However, there is some circumstantial evidence which lends some credence to the idea of studying transformer training with the min-complexity interpolator.

• Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].
• Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].
• The RASP-L conjecture [3] suggests that transformers are biased towards learning functions of short RASP-L program length.

[1] Abbe et. al. arxiv.org/pdf/2301.13105

[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316

[3] Zhou et. al. arxiv.org/abs/2310.16028

Section 6 is very hard to read.

We apologize for the lack of clarity in Section 6 and thank the reviewer for their patience in reading through it. We will rewrite it.

line 333, left col: why "s_k" not "s_N"?

$k$ is the number of 2D lines of the form $Y = s_i \cdot X$, with slope $s_i \in (0,1)$. The slope of each 2D line correspond to the parameters of a head in the first layer of either $f$ or $f’$.

$N$ is the length of the discrete test-function (equivalently, of the string which corresponds to the discrete test-function). The interplay of $k$ and $N$ is in the definition of the activations induced by the discrete test-function, where for $i \in [k]$, the $i$th activation is the proportion of "time-steps" from 1 to N in which the test-function lies above line $i$.

$\forall i \in[k], B_i := \frac{1}{N} \sum_{j = 1}^N 1[ps(x)_j > s_i \cdot j]$

line 341, left col: "they're in [0,1]": does this mean "both are subsets of [0,1]"?

Yes

line 356, right col: what does "B" range over?

$(B_1(x), \ldots, B_k(x))$ ranges over all possible binary strings $x \in$ { 0,1}$^*$. Each binary string corresponds to a discrete test-function, which induces a tuple of activations over the fixed $k$ lines of the form $Y = s_i \cdot X$.

line 413, left col: "the linear constraint for the i-th face" -- a "constraint" would be an equation, whereas here a number is referenced

A constraint here is a linear inequality, e.g. $x_1 + ... + x_{M} \geq 1$. In line 413, we mean that the $i$th face of the polytope is parameterized by the boundary of the half-space given by some linear inequality $L_i$. Evaluating a point $x \in R^M$ on the constraint $L_i$ is denoted as $L_i(x)$ and returns a scalar, equal to the margin that the point $x$ has on the constraint. The variable $C$ in the Lemma 6.4 is the centroid defined in the preceding paragraph (line 405, left column), which is a point. $L_i(C)$ is the margin of the centroid on the $i$th face.

line 427, right col: what does "higher-precision variants" refer to

This referred to Definition A.43 on line 2255 on page 42. However, the Dyck1 results are no longer valid.

what does the "si" in A_{si} stand for

simplest interpolator

line 308 (right column): it is argued that PARITY is not expressible … I think state tracking problems believed to be outside of TC0 are a more apt example.

We understand the reviewer’s point as that in order to argue that there are ground-truth functions which are experimentally tested for length generalization but that are theoretically intractable (due to not having a short C-RASP program), we should pick a function outside TC0 since C-RASP is upper bounded by TC0. We thank the reviewer for the insightful comment.

could acknowledge link to Huang et al more

Will do.

We sincerely thank reviewer 5Dit for their time, detailed comments, and constructive criticism.

Author statement: The submitted paper contained an error in the proofs, which we discovered only after submission. We’ve revised the proofs and sent the revised draft to the AC. Here are how the revised draft’s results differ from the submitted draft’s.

• The main result (Theorem 5.1) is unchanged except for the addition of a weak assumption to the function class $C-RASP^{2,K,T}$, that $\sum_{i \in [K]} \lambda_i > z$ for each function in $C-RASP^{2,K,T}$ (analogous to the existing assumption $z > 0$; see line 220, left col). Theorem 5.1 claims the same upper bound of $N_{A_{si}}(K,T) \leq O((KT)^{O(K^2)})$ for $C-RASP^{2,K,T}$. The proof is almost exactly the same. The significance of the result is unchanged.
• The revised draft no longer contains Theorems 5.4 and 5.6, which together were intended to extend Theorem 5.1 to prove length generalization guarantees for a class of functions which contains Dyck1 and its higher-precision variants. The absence of these side-results doesn’t affect the significance of the paper.
• Results for DFAs and CFGs unchanged.

Source of error:

• Lemma A.24 in line 1557

We apologize for the error and hope that either the reviewer can view the revised draft; or ignore Theorems 5.4 and 5.6 in their review. Thank you.

Addressing Reviewer Concerns:

the main weakness is the areas with lack of clarity in the explanation in the paper.

We apologize for the lack of clarity of the explanations and thank the reviewer for their patience in reading through the paper and for very detailed edits. We will improve it.

Line 109 second col: "a complexity" is supposed to have what properties?

The only property we require of a complexity measure is that it is a mapping from function class to natural numbers. We pick complexity measures which are ``natural", such as the number of states in a DFA, or the description size of a CFG. For C-RASP, we chose $T$ and $K$ as two natural parameters.

Algorithm 1: what does "interpolator" refer to

We meant that the learning algorithm picks a hypothesis $h \in \mathcal{F}$ such that each $(x,y)$ pair in the training set, $h(x) = y$.

Line 119 second col; Explain "are very nontrivial"

We mean that it difficult to characterize the learned solution by SGD in non convex landscape. The learned solution is not necessarily local minima; even if it is a local minima, we don’t know which one it is due to non convexity.

Line 124 second col "the learner" - what is the difference

“Learner” and Learning algorithm are synonymous. Learning is involved in the paper since the learning algorithm takes as input a training set and outputs a hypothesis.

Line 189 - 190 first col: (1) Is A_{si} the same as before? (2) what does it mean for it to "see inputs of length at least" some number?

(1) Yes; $A_{si}$ always refers to Algorithm 1.

(2) The sentence containing the phrase was meant as a prose introduction to definition 3.2 on line 192 (left column). The phrase “the learner sees inputs of length at most N” means that it takes as input dataset $D_N$ of (string, label) pairs for all strings of length at most $N$.

Line 268-269 first col: be more precise with this (undecidability) statement

The computational problem which we’re saying is undecidable is: Given two CFGs $G_1$ and $G_2$, output whether or not $L(G_1) = L(G_2)$.

Line 311-316 second col: "This inability of the transformer … "

If no setting of the transformers weights will result in the function expressed by the overall transformer being equal to the ground truth, then the transformer cannot learn a function which is correct on all inputs. What’s more, for many ground truths investigated empirically like PARITY, we believe that any function expressible by transformers will differ from the ground truth on infinitely many strings in {0,1}$^*$. Thus, transformer cannot length generalize perfectly to arbitrary lengths.

Definition 6.2 seems contradictory

The definition of precision of rational numbers only applies in the context of rational numbers in [0,1], so the magnitude of the denominator is all that matters. Further, the precision of a rational number is calculated from the simplest form of the rational number, where its numerator and denominator are relatively prime.

Length generalization to accuracy 99%

This is an important question. We can define train and test distributions, $D_{train}$ and $D_{test}$ over {0,1}$^*$ to make the setup more like PAC. E.g. for each natural number $N_{train}$ which is the maximum length of strings in the train distribution, let the test distribution be the uniform distribution over strings of length $N_{train} + 1$. However, it was unclear to us what choice of test and train distribution would make for a generally-realistic model for situations practitioners care about. More discussion in rebuttal to Reviewer YXKG at the bottom.