Non-Asymptotic Length Generalization
Authors: Thomas Chen
Tengyu Ma
Zhiyuan Li
Venue: ICML 2025 poster (2025)
Keywords: Large Language Model
Length Generalization
Machine Learning Theory
Primary area: deep_learning->large_language_models
TL;DR: We propose a theoretical explanation for when a learner can learn a hypothesis that generalizes across input-length. We prove upper bounds on the minimum input-length needed during training to length generalize, for various function classes.

Abstract: Length generalization is the ability of a learning algorithm to learn a hypothesis which generalizes to longer inputs than the inputs in the training set. In this paper, we provide provable guarantees of length generalization for various classes of functions in an idealized setting. First, we formalize the framework of non-asymptotic length generalization, which requires a computable upper bound for the minimum input length that guarantees length generalization, as a function of the complexity of ground-truth function under some given complexity measure. We refer to this minimum input length to length generalize as length complexity. We show the Minimum-Complexity Interpolator learning algorithm achieves optimal length complexity. We further show that whether a function class admits non-asymptotic length generalization is equivalent to the decidability of its language equivalence problem, which implies that there is no computable upper bound for the length complexity of Context-Free Grammars. On the positive side, we show that the length complexity of Deterministic Finite Automata is $2n - 2$ where $n$ is the number of states of the ground-truth automaton. Our main results are upper bounds of length complexity for a subset of a transformer-related function class called C-RASP (Yang & Chiang, 2024). We show that the length complexity of 1-layer C-RASP functions is  $O(T^2)$ when the ground-truth function has precision $T$, and that the length complexity of 2-layer C-RASP functions is $O(T^{O(K)})$ when the ground-truth function has precision $T$ and $K$ heads.

Non-Asymptotic Length Generalization
Thomas Chen
Tengyu Ma
Zhiyuan Li?
Abstract
1. Introduction
The generalization of trained model from shorter inputs seen during training time to longer inputs seen inference time is a phenomenon called length generalization. The question of when length generalization is possible is an important question in the area of language modeling and reasoning with Large Language Models (LLMs) (Brown et al., 2020). Real-world language understanding often re- quires handling longer contexts that exceed training-time input lengths, such as long Chain-of-Thought for reasoning problems, multi-turn conversations, lengthy documents, or complex code. Many factors limit the ability to train on long sequences directly, such the increasing computa- tional cost and memory requirement of training on longer sequences and the fact that long sequences are rare, Suc- cessful length generalization does not only allow efficient training for good long-con long-context performance, but also is a natural test on whether the model has robustly learned the underlying language reasoning patterns.
Length generalization is the ability learning algorithm to learn a hypothesis which generalizes to longer inputs than the inputs in the training set. In this paper, we provide provable guaran- tees of length generalization for various classes of functions in an idcalized setting. First, we for- malize the framework of non-asymptotic length generalization, which requires a computable up- per bound for the minimum input length that guar- antees length generalization, as a function of the complexity of ground-truth function under some given complexity measure. We refer to this mini- mum input length to length generalize as length complexity. We show the Minimum-Complexine Interpolator learning algorithm achieves optimal length complexity. We further show that whether function class admits con-asymtootic length gen- eralization equivalent to the decidability of its language equivalence problem, which implies that there is no computable upper bound for the length complexity of Context-Free Grammars. On the positive side, we show that the length complexity of Deterministic Finite Automata 2n - where n is the number of states of the ground-trute -trth au- tomaton. Our main results are upper bounds of length complexity for a subset of transformer- related function class called C-RASP (Yang & Chiang, 2024). We show that the length complex- ity of 1-layer C-RASP functions is ( when the ground-truth function has precision T. and that the length complexity of 2-layer C-RASP functions O(To(K)) when the ground-truth function has precision T and K heads.
Prior works study length generalization in a controlled set- ting where Transformers (Vaswani et al., 2017) are trained on algorithmic tasks from seratch. In this context, length generalization has been empirically observed for certain algorithmic tasks but not others, and it appears that trans- formers cannot length generalize for most tasks. Tasks that have been tested arithmetic tasks like integer addition (Nogueira et al., 2021; Nye et al., 2021; Anil et al., 2022; Zhou et al., 2024), formal-language tasks like PARITY (Anil et al., 2022), algorithmic tasks in the Chomsky Hierarchy (Shaw et al., 2021; Delétang et al., 2023; Ruoss et al., 2023), copying tasks, tasks involving sequence of integers such as sorting or finding the mode (Zhou et al., 2023), and de- ducing the end-assignment of variable in block of code (Anil et al., 2022). Some of these tasks do not exhibit length generalization in their vanilla form, but do exhibit length generalization if certain modifications are made to the learn- ing setup. These modifications include modifying the input and output format (Zhou et al., 2023; 2024), adding posi- tional embeddings (Jelassi et al., 2023), and adding access to scratchpad (Nye al., 2021).
Department of Computer Science, Stanford Univer- sity, Stanford, USA TToyota Technological Institute at Chicago, Chicago, USA. Correspondence to: Thomas Chen richen@essttafford.cd
On the theoretical side, (Gold, 1967) provides a founda- tional result in the theory of length generalization, which is originally stated in a more broad context of language iden-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Non-Asymptotic Length Generalization
Function Class
Complexity of Ground- Truth Function
Length Training Data Sufficient to Generalize
DFAs
number of states, c description length,
2c- 2 (Proposition 2.7)
CFGs
no computable bound in exists (Proposition 3.5)
C-RASP
precision, T
O(T") (Theorem 5.5)
C-RASP
precision, T, and number of heads, K
O(T (Theorem 5.6)
Table 1. Summary of results: upper bounds on minimum length of binary strings in training data which suffices for length generalization.
tification. Let Σ be a finite alphabet, let a hypothesis be mapping from all strings E" to (0, 1). and let F be the hy- pothesis class. Gold (1967) roughly says that there is a learn- ing algorithm A such that for all hypotheses in F. A will eventually learn the ground-truth hypothesis, when the train- ing set inputted to A contains (string, label) pairs for all the strings up to a sufficiently large length. Gold's result holds for all hypothesis classes F satisfying the mild assumption that F can be enumerated by a Turing machine, including Regular languages, Context- languages, decision prob- lems that can be solved by finite-precision transformers with or without -hain-of- Shain-of--houghhe Thought, etc. The learning algorithm A simply returns the first hypothesis in the enumeration of F that correctly labels all training examples. When this enumeration lists the functions in F in order of increasing complexity for some complexity measure, then we call this learning algorithm the Mininum-Complexity Interpolator, denoted by Amci-
achieve length generalization as a function of complexity of ground-trath hypothesis, assuming we have infinite computational resources?
This paper provides a more fine- grained analysis of length generalization, by providing a asymptoiii guarantee on the minimum input length re- quired to achieve length generalization, as a function of complexity of ground-truth. More specifically, we make the following contributions:
Our Contributions:
introduce the framework of non- asymptotic length generalization (Definition 2.6), which requires non-asymptotic upper bound for the minimum input length that guarantees length generalization, given the complexity of ground-truth function under some given complexity measure C. The latter we call the length complexity under C (Definition 3.1). We show that the MomilunnComplexity Interpolator learning algorithm Amai instantiated with complexity measure C, is the opti- mal with respect to the length complexity under C. As a concrete example, we show that Amai only needs inputs up to length 2c 2 to learn any ground-trute Deterministic Finite Automata (DFA) of c states.
In Section 2,
The gap between the wide range of function classes which Gold's theory predicts length generalization for and the lim- ited classes of functions that transformers empirically length generalize on presents an opportunity to develop a more pre- dictive theory of length generalization. There are many po- tential reasons for this gap, such as the discrepancy between the learning algorithm Amai and the gradient-based learning algorithms used in practice. However, a more fundamen-
In Section 3, we show whether a hypothesis class ad- mits non-asymptotic length generalization is equivalent to whether the problem of deciding equivalence of two finite descriptions of hypotheses is decidable. As con- sequence, Context-Free Grammars (CFGs) do not admit non-asymptotic wength-generalization though they admit (asymptotic) length- generalization in the limit.
tal issue of Gold's result is that the guarantee is inherently asymptotic - it does not provide any information on the minimum input length required to achieve length general- ization. It completely possible that even if gradient-basee training methods like SGD are able to find the minimum- complexity interpolating hypothesis, length generalization still only happens when the training set contains impracti- cally long length inputs. In this case, it may appear empiri- cally that length generalization does not occur at all, despite the asymptotic theoretical guarantee.
In Section 5, we prove non- non-asymptotic length general- ization for subset of the transformer-relatee hypothesis class, C-RASP (Yang & Chiang, 2024). C-RASP is su- perset of functions expressible by transformers. Variants of the RASP function class, RASP-L and C-RASP, have been shown to have a good predictive power on the length generalization performance of transformers (Zhou et al., 2023; Huang et al., 2024). We study two subclasses of C-RASP: C-RASP (Theorem 5.5) and C-RASP2 (Theo- rem 5.6), which are of depth 1 and 2, respectively.
Intuitively, the minimum input length required to achieve length generalization should be function of the complexity of the ground truth hypothesis, and better length generaliza- tion is expected for simpler hypotheses. To both get a more useful length generalization guarantee and better understand the limit of length generalization, the goal of this paper is to answer the following question:
2. Non-Asymptotic Length Generalization
Notation. Fix the alphabet Σ = {0. throughout the paper. Define computable (recursive) functions as func- tions which can be computed by a Turing Machine (TM),
What is the minimum input length required to
2

---

Non-Asymptotic Length Generalization
which halts on all inputs. A function / N + N is computably bounded if there exists computable function
Finally, a Linear CFG is a CFG G (N, (0. where each production rule in P has at most one nonter- minal symbol on its right-hand side. The encoding system for Linear CFGs is RL-CFG. where (p) = (P) for representing Linear CFGs, and otherwise (F) returns the TM with the empty language.
g : IN- + N such that f(n) S g(n) for all E N. Let (M) E {0, denote the binary string encoding of M. Let [N] := 21,
N- - 1, N. Denote {0, 13"h as the set of binary strings of length n, {0, 10, == (0, 1), and
{0. 13" :- U2 (0. 13. [:]] denotes the indicator function
and cI(A) as the closure of set C Rd
Learning Setup. With the ground truth function being denoted f or R(p), we define the labeled training dataset consisting all data up to length N as below, for all N E N: Dx(f) == [(2, f=)=) x {0, 1)", |x|| S N).
Representation of Functions. We are interested in learn- ing subsets of computable functions mapping {0, 13" to {0, 1), denoted by F. Because a learning algorithm can only return finite description of the hypothesis it selects, we need to define the representation of the hypothesis and the corresponding encoding system below in Definition 2.1.
With R as the encoding system, an adversary picks any ground-truth function I* E FRR A learning algorithm is a TM A which takes as input a training set Df and outputs some á E {0. 13". We say a learning algorithm A amggh-ggneralliabbl learns a function f input length N w.r.t encoding system R iff R(A(D (f*))(((*))))))))) (f*))) = f".
Definition 2.1 (Encoding System). An encoding system is a TM R which on input of a finite string p (which can be thought as the code or description of a function), outputs the TM description of the computable function f {0, 13* + {0. 1} represented by p. Here we denote the description of the TM as (R)) and the function f as R(p). We use JR to denote the function class implicitly defined by the encoding system R, i.e. FRR = (R(p)= E (0, 1}*}.
To give context to our notion of -oymppttio length gen- eralization, we describe Gold (1967)'s 's asymptotic notion of learnability in Appendix B.
Complexity Measure. We are interested in understand- ing the minimum length of training data which suffices for length generalization. To this end, a complexity measure for the functions in F is necessary. We assume complex- ity measure C: : {0, 13 - N, which assigns a complexity to each representation p. and define the complexity of the function ff as the minimum complexity of any representa- tion of f in R, namely (f) == minpe (0.1)>,R(p)= R(p)= C(p). We may drop the superscript R. and just use C for function complexity when R is clear from the context. We will make the following mild assumption that C is reasonably simple throughout the paper, unless otherwise stated.
Often the standard encoding system is only defined on valid inputs. For convenience we define the encoding system R for all inputs in {0. 1)" and map invalid inputs to the empty language. As examples of encoding systems, DFAs and CFGs are two encoding systems for regular languages and context-free languages, respectively.
An n-state Deterministic Finite Automaton (DFA) is a tuple M- = (Q = [m]. Σ = {0, 1), 5, go, F) where Q = [r] is the set of states, Σ = {0, 1} is the input alphabet, 8: Q x Σ + Q is the transition function, 9o E Q is the start state, and F S Q is the set of accepting states. The encoding system ROFA is TM that reads (M) and outputs the description of a TM that simulates M. For any input string I E {0, 1}", the language characterized by M is where ROFA (z) = 1 if and only if 6* (go. x:) E F, where 5" : Q x 13 + Q is the natural extension of 8 to strings defined recursively as 5' <) = q and 5'(4 sa)= = 6(8" (g. s), a) for any q E Q, s E {0, 13", and a E {0, 13.
Definition 2.2.
Assumption 2.4. C is computable and there exists a TM E which enumerates programs E {0, 1 in non-decreasing order of C(p). In particular, the range of E is {0, 1)- and Vi S 1,, C(F(() & C(F((()). In addition, C is such that for each E N. Kp E 10, C(p) S c]| < co.
This assumption is easily satisfied by a standard choice of C, namely where C(p) returns the length of p E 13". There is little loss in generality in just thinking of C as this standard complexity measure. Having a general C provides some extra flexibility and makes the results easier to understand.
Definition 2.3, A Context-Free Grammar (CFG) is a tuple G= -N, T = (0, 1). P,S) where N is a finite set of non- terminal symbols, T = {0, 1} is the terminal alphabet, P a finite set of production rules of the form A + a where A E N and a E (N UrY", and S E N is the start symbol. Let (G) E {0, 1)a denote the binary string encoding of G. The encoding system RoFG is a TM that reads (G) and outputs the description of TM that simulates G. For any input string x E {0, 1)", the language characterized by G is RCFG (CFa((G)) (z) = 1 if and only if x can be derived from by applying a finite sequence of production rules from P.
Definition 2.5 (Complexity Measures for DFAs and CFGs). The complexity measure CDFA for DFAs maps a DFA M = (Q [m], 2, 6, go, Po) (represented by (M)) to n, the number of states in Q. The number of states of any DFA is within logarithmic factor of the length of its representation in bits (n log For CFGs, given a CFG G = (N, T, P. P.S). let [P] be the total length of the pro- duction rules in P. The complexity measure of CFG G is CCFa((G)) = |P| + |N] + [T], which is within a constant
3

---

Non-Asymptotic Length Generalization
factor of the length of (G) in bits.
Algorithm 1 Mininum-Complexity Interpolator (A
Hyperparameters: Complexity Measure C, encoding
Now we define non non-asympiotic length generalization.
system R
Definition 2.6 (Non- Aon--ssyptootic Length Generalization).
Input: Finite Training Dataset S C ((x,y) | x E
A function class F C FR admits non-asymptotic length generalization w.r.t encoding system R and complexity measure C if there exists a learning algorithm A and com- putable function R.F.F. :N + N such that for all f E F and for all N' 2 NX. (f*)())). A length-generalizably learns/ f at input length N'
{0,1)", 1)",y E {0, 13}. Output: arg
C(p)
3.1. Optimality of Minimum Complexity Interpolator
The Mininum-Complexity Interpolator (Algorithm 1) is the main learning algorithm which we study in this work. Al- though it would be ideal to study a learning algorithm closer to what used empirically to train transformers, we study the Minimum-Compplsn complex training dynamics of gradient-basee -based methods like SGD, which are very non-trivial even for training 2 layer neural networks (Mahankali et al., 2023). We also acknowl- edge the limitation that the Minimun-Complexity Inter- polator is computationally intractable for general function classes and encoding systems. For instance, it was shown that the problem of finding the minimum regular language is NP-hard (Pitt & Warmuth, 1993).
Length Complexity. For notation simplicity, we define the length complexity of a function f for a learning algo- rithm A w.r.t. encoding system R. (((()) as the mini- mum length of training data which suffices for the learn- ing algorithm A to length generalize on f": ((())) = min( 0: Vn 2 N, RRAAD,, (f*))) = f*3
Interpolator to abstract away the
This quantity is co if there is such N where Vn 2 N, ((A(D,((f)))
f" We also define the length complexity of functions in F c .FR up to complexity e for a learning algorithm A w.r.t. encoding system R. RRR.F.F (c), as the maximum length complexity of any function in F C FR with complexity at most c, given as N.... (c) == max CF NZ
DFA for a
We denote the Mininum-Complexiyy Interpolator learning algorithm by R.C for short when the encoding system is R and complexity measure is C. When the complexity measure C is the length of the program, A is just the famous Minimum Description Length (MDL.) algorithm (Rissanen, 1978). A has the nice property that it is the best possible algorithm over all learning algorithms in minimizing N R (c), in the following sense.
maxpe (0,1)) SL Cip)SCNR(P)E (R(()) We denote NR.F= (c) by (c) for convenience.
As a concrete example, Proposition 2.7 shows that DFAS admits non-asymptotic length generalization w.r.t. the stan- dard encoding system RDFA and complexity measure CDFA in Definition 2.5. Its proof is in Appendix D.
Proposition 2.7 (Non-Asympiotic Length Generalization for DFAS). Let RDF be the DFA encoding system defined in Definition 2.2, and let COFA be the number of states in DFA. Regular languages FR admits non-asymptotic length generalization w.r.t. encoding system RDF and complexity measure CDFA. More specifically, there exists a learning algorithm A such that NR (c) 2c for all E N.
Theorem 3.2 (Optimality of Minimum-Complest
Inter- polator). Given any encoding system R and complexity measure C, for all E N, it holds that c(c
N = N(FR). As a consequence, the follow- ing three statements are equivalent:
Function class FR admits non-asymptotic length gener-
alization:
Function class FR admits non-asymptotic length gener- alization, via learning algorithm AR.C. For all e E N, length complexity of FR, N(JR), is computably bounded in c.
3. Characterization of Definition 2.6
In Section 3, we characterize the conditions under which a function class admits non-asymptotic length generalization w.r.t. an encoding system R and complexity measure C satisfying Assumption 2.4. First, we introduce Definition 3.1, an algorithm-independeet version of length complex- ity, which coincides with the optimal algorithn-dependent length complexity, over all learning algorithms A.
The proof of Theorem 3.2 is in Appendix C. Though the above optimality result of AR. holds for all complexity measures C, Aa may not be computable without restric- tions on the complexity measure. For example, it is well- known that Kolmogorov complexity is not computable (Li & Vitányi, 2008). Lemma 3.3 shows that RR. is indeed computable under Assumption 2.4.
Definition 3.1 (Length Complexity of Function Class) Given a function class F. we define the length complex- ity of F as the minimum input length that can distinguish any two functions F: N(F) == min(n& E N: vf + f e F, Br E (0, 1] Sn s.t. f(x) # (x))
Lemma 3.3. Under Assumption 2.4, Algorithm I is com- putable and thus a valid learning algorithm.
4

---

Non-Asymptotic Length Generalization
The proof of Lemma 3.3 is in Appendix C. In the remaining sections, we may omit R and C in the superseripts of A when they are clear from context for convenience.
Zhou al. (2023) propose the RASP-L Conjecture, which says that whether transformer length generalizes par- ticular ground-truth function f. is well predicted by whether f. has short RASP-L description. Huang et al. (2024) for- mulate the problem of length generalization-and the RASP- L Conjecture-formally as a version of Identification-in- Limit and prove asymptotic results for identifying languages expressible by Limit Transformers. None of the works above provide non-asymptotic guarantees. We distinguish this work from previous work by providing non-asymptotic bounds on the length of the training data required in order to guarantee that the learner outputs single hypothesis which exhibits perfect length generalization.
3.2. Equivalence to Decidability of Language Equivalence Problem
The main goal of this paper is to seek concrete upper bounds for the length complexity Nº (c) of various function classes. Surprisingly, such upper bounds are not always computable. In this section, we show that there cxist computable upper bounds on the length complexity if and only if the Language Equivalence Problem for encoding system R is decidable, where the Language Equivalence Problem for encoding system R. is the computational problem where given any P.q E {0, 1)", determine whether R(p) = R(q)..
(Weiss et al., 2021) (Zhou et al., 2023), (Yang & Chiang, 2024), and (Shaw et al., 2024) study programming lan- guages which capture the set of functions which transform- ers can express (like RASP).
Lemma 3.4. For any encoding system R and complexity measure C satisfying Assumption 2.4, the Language Equiv- alence problem for R. is decidable if and only if length complexity of F.R N(FR), ), is computably bounded in c. Thus it is also equivalent to the property that JR admits non non-asymptotic length generalization.
Regarding theoretical works for length generalization not related to transformers, Marsden et al. (2024) prove length generalization for learning linear dynamical systems with SGD. Abbe al. (2024) prove out-of- generalization for boolean functions of fixed input size.
As consequence, we have the following impossibility re- sult for non-asymptotic length generalization for special case of CFGs: Linear CFGs. Comparing Proposition B.2 and Proposition 3.5, we see that CFG serves as a concrete example for the separation between length generalization in the limit and non-asymptotic length generalization.
5. Main Results: Non-Asymptotic Length Generalization of C-RASP
5.1. Recap:
Definition of C-RASP
Our main results pertain to a class of functions called C- RASP. C-RASP is variant of RASP that, with alphabet Σ = {0, 1}. defines class of functions from {0, 1)" to {0, 1]. where only certain sqquenc-to-sequenee operations are permitted. C-RASP was shown to be a subset to the class of functions expressible by transformers with infinite- precision activations and a superset to that expressible by prnite-precision transformers (Yang & Chiang, 2024).
Proposition 3.5 ((Linear) CFGs only admit length general-
ization in the limit). Recall RL-CFG is the encoding system for Linear CFGs defined Definition 2.3 and CaFa is the complexity measure that maps CFG G (N, P,S P,S 1)) to |N| + [T| + IP]. Then for any learning algo- rithm A, the length complexity, NR is not computably bounded. That is, Linear CFGs do not admit non-asymptotic length generalization (w.rt. standard CFG encoding system R.FFF), and neither does the set of all CFGs.
Definition 5.1 (C-RASP, (Yang & Chiang, 2024)). A se- quence is an element of N C-RASP program over al- phahet Σ (0, 1} is defined series of n < oo C-RASP operations. We denote the h(() ...., (n)) as the output se- quences of each C-RASP operation. Denote æ E (0. as the input sequence to the C-RASP program. Denote h/))) as the jth element of the sequence (), where i E [m] and j E ||=[]. Table 2 shows the list of allowed operations in C-RASP. The partial-sum operator ps : {0, 13" - No is defined as: Vh E {0, 13", Vj e (s()), = =Eeep hi The entire C-RASP program is mapping (0. + {0, 13" We take the last bit of the output sequence as the output bit, yielding a function {0, 13" to (0. 1).
The proofs of Lemma 3.4 and Proposition 3.5 are in Ap- pendix C and Appendix D, respectively. In Appendix C.3, we show equivalence between non-asymptotic length gener- alization to a variant of "finite identification" proposed in Gold (1967). The results are summarized in Figure 1.
4. Related Work
Solomonoff (1964) proposed beresiiinnniffeeeee-bee al- gorithms which when given sequence of symbols, predict the next symbol according to the posterior distribution com- puted from the Solomonoff- prior distribution. Gold (1967) introduced Identification-in in-the-LLin as an asymp- totic notion of learnability and proved that many classes of functions can be learned in this sense.
There are several natural parameters that contribute to the complexity of CASP functions. First, we study the impact of the following notion of precision of the parameters of
5

---

Non-Asymptotic Length Generalization
C-RASP functions on the difficulty of length generalization.
indicates the value of a quantity on the jth prefix of x.
Definition 5.2 (p-precision). An integer of absolute value at most is of p-precision. A rational number between [0, 1] is of p-precision if in simplest form, where the numerator and denominator are relatively prime, its denominator is at most p in magnitude. A tuple of rational numbers in [o, 1] is precision p if the least common denominator of its entries is at most p in magnitude.
The second layer computes the output, which is the rath bit of the final sequence: f(x) = [[ ).ps(h()), )n > 2- n).
Then, C-RASP2
UiSTASKKTTS C-RASP2.K.T Given a function f E C-RASP?, let (f) be the number of heads, h(,, in the first layer of / and let T() = max(max |a(*), maXie[K([]] 16(0), (X) [al.,
The com- plexity measure is C(f) T(f)((), the precision of the function's 's parameters to the power of the number of heads.
This notion of precision makes sense for C-RASP since C-RASP only allows integer combinations of previously computed variables instead of arbitrary linear combinations.
We also study the impact of depth of C-RASP programs on the difficulty of length generalization where depth is, loosely, the maximum number of sequentially-applie ps operations along any part of the C-RASP program. We study 1 and 2 programs, which we will also refer to as 1-layer and 2-layer programs. We will first prove length generalization results pertaining to the following subset of I-layer C-RASP, which we call C-RASP!. Note that for convenience, use functions f E FR and descriptions P E 13 interchangeably in the following definitions.
We refer to functions in C-RASp2.K,7 as 2 layer, K-head, T T-precision programs, where each intermediate variable M0, i E [K] is called a head.
Here, the encoding system RC-RASPZ maps string p to a C-RASP2 function. The string p is interpreted by RA-RASP2 to encode ((K) parameters, each taking Ollo 7) bits to encode, so that the entire encoding of a C-RASP2.K." fune- tion is roughly @(K log T) bits long. Invalid encodings are mapped to default C-RASP2 function. Thus, the com- plexity measure C(f) = ((f)(()) = (f) log T()) returns an integer which is roughly exponential in Ip]-
Definition 5.3 (C-RASP'). With integer T, let C-RASPI.T denote the set of programs of the following form. Each [-T,T]] a > 0. For any > 0, input x E (0.1)" J computes: f(x) = Laa ps(z)n- b-n n - d > 0j. Then, C-RASP" = UTZI C-RASPI.T Given a function f E C-RASP!, the complexity measure C(f) = max(la), [b], [d]), the preci- sion of f's parameters in the sense of Definition 5.2.
program f has parameters a, b, d
5.2. Non-Asymptotic Length Generalization of C-RASP" and C-RASP2
The following result states that in order to identify the ground-truth function from the set C-RASP! where the precision of parameters is at most T, it suffices for the Minimum-Com Complexity Interpolator to receive (string, label) pairs for all strings of length at most (
Here, the encoding system R maps string p a C-RASPI function. The string p is interpreted by R to encode 3 parameters, each taking O(log T bits to encode. Invalid encodings are mapped to a default C-RASP" function. Thus, the complexity measure proposed above, which takes in p and returns the maximum precision its parameters, returns an integer which is roughly exponential in the length of p.
Theorem 5.5 (C-RASP- Length Generalization). Let F C-RASP" and C(f) = max(la), [b], Id)). defined in Defini- tion 5.3. Then VT E N, we have N (T) S ((T)). That is, the Minimum-Cooe Complexity Interpolator, with complexity C and function class F, can length generalize given inputs of length ( when the ground--ruth has complexity T.
Our main length generalization result will apply to subset of 2-yayer C-RASP, which we call C-RASP². For 2 layer programs, the width K of the first layer becomes natural parameter to study.
The following our main length generalization result. states that in order to identify the ground-truth function from the set C-RASP2 where the precision of parameters is at most T and number of heads is at most K, it suffices for the Interpolator to receive (string, label) pairs for all strings of length at most O(TO()).
Definition 5.4 (C-RASP2). With integers T and S K < T let C-RASp2.K.1' be the set of programs of the follow- ing form. Each program f has parameters 0- 2 $ T, vi E [K]. (19),,))))))) (,))) A E {-T,... ...T....,J. T). with (+)) > 0. We require that for all i E [K]. 860 gitl) ato
Theorem 5.6 (C-RASP² Length Generalization, Main Re- sult). Let F C-RASP2 and C(f) = (Tf)(((K)))) defined in Definition 5.4. If the ground-truth function Sx has T(J=) S T and K K(f.) S K, then the Ekinimm--Compled lator, with complexity C and function class F, can length generalize given inputs of length ((TO(K)).
E (0, 1) and is distinct from
for i' * i. We also require ΣiE[K] X; >>> z.
Interpo-
For any > 0, on input E 10" the first layer com- putes the values of K heads, (h(1) [M()) on the n pre- fixes of x: { f21, #2)..., (..,.,,......................... 2n}] as follows:
By Theorem 5.6, C-RASP2,K,T can be learned in a length generalizable way with inputs of length ((TO(K)). By
Vj E [m], Vi E [K], m (ps(()) > 509)
J. Subscript
6

---

Non-Asymptotic Length Generalization
Theorem 5.5, C-RASPL.T can be learned in a length gener- alizable way with inputs of length O(T²). Our upper bound on the minimum length required to learn C-RASp2. is much larger than that of C-RASPI.T. We don't have a lower bound on the length of inputs required to identify C-RASP2.K:7 but our best guess is that one of the form ((T*) exists in the regime K V (logT)).
has size k; where K I k S 2K. We will refer these numbers as "slopes." We will denote R {8;] (8)))(H)) C (0, 1), where 81 is the largest slope and sy is the smallest slope, and the slopes are sorted in descending order so that 81 > ....> Ak- For i E [K], let ord(1, i) [K] + [K] be 600
the index within R of the ith slope of f. 205- Let ord 1) [ - [R] be the index within R of the ith slope of f'. abyy
The proof of Theorem 5.5 can be found in Appendix E.I. Below we sketch the proof of Theorem 5.6.
(aay. In the following exposition, as the homogeneous, 2D line syx, with slope sy. E [M]] We will denote "line j" by the symbol 1,. We will call the set of - 2K unique slopes (St] a configuration.
will refer to "line j"
6. Proof Sketch of Theorem 5.6.
Definition 6.4. A (k: -ooffiuurrtiinnn is set of i distinct T T-precision rational numbers (5ahe C (0, 1).
Theorem 5.6 follows as a Corollary to the following, stronger Theorem 6.1, which says that the Minimum Com- plexity Interpolator with complexity measure c(f) = (()) will length generalize if it receives inputs of length A (a) & ())))), when the ground-trute func- tion has complexity at most a.
We will refer to strings in {0, 1) synonymously as dis- crete lest-functions, because there is a one-to-one cor- respondence between I and the sequence of 2D points {(j, p=());)) C R.2 The latter set of points acts as a "test" of whether two programs f. E C-RASp2.K.7 are different not.
Theorem 6.1. Let F = C-RASP2 and C(f) = T(f)K() as in Definition 5.4. Then Vo E N, (a) S (())))
Definition 6.5 (Discrete Test-Function). Given a (k, T)-- configuration {8) a discrete test-function X' with respect to fs; hejl and of length n < co, is a func- tion {0, 1, 1, m) - 1, _) where x()) = 0 and Vj E [m]. x() = X( - 1) or x() = X( - 1) + 1. The induced activations (B) ., (x) of X with respect the (k: configuurainn are defined as: Vi [N], =x
Theorem 6.1 is proved in Appendix E.2. The proof that Theorem 5.6 follows as a Corollary to Theorem 6. is simple, and deferred to Appendix A for brevity. Below, we sketch the proof Lemma 6.2, a weaker version of Theorem 6.1. Although weaker, our proof sketch of Lemma 6.2 will still illustrate the key ideas of the proof of Theorem 6.1.
Lemma 6.2. Let F = C-RASP2 and C(f)= = T())((), as in Definition 5.4. Then Va E N, NAmo (a) & (a o)).
= Eド= 1[x()) > s 5. j]
In our proof sketch, we will need to analyze properties of a continuous analog to discrete cest-functions, which can be thought of as corresponding to infinite-length strings.
To prove Lemma 6.2, it suffices to prove Lemma 6.3. We will upper bound, for any T and K, the minimum length of inputs required to distinguish any two unequal C-RASP2 functions that have at most K heads and T precision.
Definition 6.6 (Continuous Funnttunn..... Given a (k,T)- configuration {s))=e[s). a continuous test-function V, with respect to {sæ)<e(N)- is 1-Lipschitz, monotone non- decreasing continuous function [0, - [0, 1]. with (0)) O. Continuous rest-functions can only intersect the k lines hee of slopes given by [ss at finitely many points. The induced activations (BI()),... (2)) of y w.r.t.
Lemma 6.3 (Length Bound on C-RASp2.K.T), ). For any 1 < T. < K < T2, for all J'J' E C-RASP2KKT such that f # fr, there exists a string V. E 10 of length at most O(TO(K2)) such that fxx)) # (z.)..
The proof that Lemma 6.2 is a Corollary to Lemma 6.3 is simple and is deferred to Appendix A. The rest of the proof sketch describes how to prove Lemma 6.3. To do this, given two arbitrary S, E C-RASp2.K, that are not equal, we show the existence of short string x. which distinguishes f and f', in the sense that fxx)) + f((x.).
{ss (iEj) are: Vi E [K], B(()) = - 1D')) > Ss jldj.
We study continuous test-functions as proxy for dis- crete test-functions. As each C-RASP2 function can be thought of as a linear threshold function over the in- duced activations of the input string (test-function) with respect to the (k, coonfiiuurri given by the param- eters of its first layer, it will be important to study the activations which can be induced by continuous test-functions: A({s))e))) = ("")),,,, y continuous test-function w.r.t (s:]ve[H))
6.1. Key Definitions.
Suppose f.f' E C-RASP2K.T with parameters (a (e(K), (6()) (AWSEeK), and ((a()))))
((b())))())) (A))sERg. 2', respectively.
The importance of the activations induced by continuous test-functions motivates the segmentation of continuous test- functions at the points where the continuous fest-function
Suppose the set of unique numbers R = ( 1 ]E(K]] U (b0y (awy ](E C 10) between the first layer of I and f'
7

---

Non-Asymptotic Length Generalization
intersects the I lines, {y- s,x: : i E [k]].
ference between the left-hand-side and right-hand-side of the inequality when the coordinates of x are plugged into L. Let L(x) = 0 > z satisfies the inequalities with equality. We say L(x) is the margin of z for L.
Definition 6.7 (Segment). Given any (), configuratio {&) C (0, 1), a segment is restricted test-function S la b] + [0, 1] where [a, b] C [0, 1] which maps a con- tinuous subset [a, bj to [0, 1]. S is 1-Lipschitz and monotone non-decreasing. The segment's 's start-point (a, S(a)) and the end-point (b, S(b) each lie on one of the i lines, in the sense that there exists some j [k] where S(a)= st a
6.2. Proof Sketch of Lemma 6.3.
Proof Plan. We want to show that any two C-RASP pro- grams f. E C-RASP2.K.7 that are not equal must be dis- tinguished by some string x' of length at most O ((TO(K))) Consider any two C-RASP programs f. E C-RASp22K.T with parameters (al") )se[K] (1())=s (A))se = and ((a())))(())) (((())) ()EK]] (A)) z', respectively.
and S(b) 8. b. where
or l - jl = 1. No other points (ar, (zz)), x E b) can lie on line ......44.
Figure depicts a continuous test-function. Figure 7 shows four generic types of segments. Two different test- fest-functions can share the same schema: roughly, the order which the fest-functions cross the & lines.
For any n > O, consider the induced activations by an ar- bitrary string x E {0, 1)", defined as { (pa(k() he(]]] U { ( kee[k] per Definition 6.5. With & S 2K being the number of unique slopes (i.e. unique values in { (am НEEK]] U { faarry )E(K)) among the heads in the first layers of f and f', denote (B, B2(x), (.(a))))..,,((.))) Bx(x)) ==
Definition 6.8 (Schema). Given any (k. cconfiiguuri {&; heejs] C (0, 1), a schema Y is a blueprint for contin- uous test-function, specifying sequence of lines {4(be(k) that any test-function of the schema must cross. It consists of an integer < M < 0o and two tuples {idx(i)]<eMM) C M,,, [s C [k+ [R+1]MM where [idx(i) -idx((+))) S
(
{ (P(())())))) (x)) HE[K] U (Fa((h hE(R].
1 for all i [M- 1]. If [i) idx(i + 1)] 1, then
sec++1 is unique and must be max(idx idx(i + 1)). If
To argue that the existence of distinguisher vn for f and f' implies existence of a short distinguisher for for f and f", suffices to find an x E [0.1)", n I O(KKT)O(K*) that induces activations (B(()))) where either ΣiE[Ky dr (:Bod((),))a)) > 2 and EiejKy (,nd S x' or Eiginn d; Bo S x and ΣierK X (x) > x'. In particular, de- fine the following halfspaces. H "H HHH Hr. Vj 21, HJ (BB1... ........................... Bb) >x and Нí := {(B)... Bb) Σie(K] A.BoodG.) < 2]. With this goal in mind, we use the following proof plan.
idx(i) idx(i + 1), then sec;+1 can be either idx(i + 1) or idx(i+ 1) + 1. secı can be either idx(1) or idx(1) + 1.
Any continuous test-function of schema Y ((idx(i))=gIM)) (s)M)))))))) consists of exactly M segments S1, S2.....
....... Syy whose domains are a partition of [0, 1]. For each i [M). the ith segment S 's end-point lies on 4axca)) For i > 1, S,'s start-point lies on line (ux(t-1)- and Si's start-point is the origin, (0, 0). In addition, the ith segment must be contained in Sectorsee, where Sector; is the subset of the positive quadrant of the 2D plane which lies above y = 81 Sector++1 is the subset of the positive quadrant which lies below y sgx, and for i E (2...., k). Sector, is the subset of the positive quadrant which lies below y i and above y s,X.
2]
1. First, we argue that if ʃ * S', then there exists continuous test-function Vo which induces activa- tions (B) (3))........ (D6)) that is either contained in H n H or H; n H₂. This is non-trivial step which uses a technical Lemma E.30, whose proof is deferred to Appendix E.6. WLOG, suppose that E H n H
There is useful approximation property between discrete and contimuous test-functions which we use later.
Lemma 6.9 (Discrete Approximation to Continuous Test- Function, weaker version of Lemma E.24). Suppose we are given (k:, cooffggguuttii [si) For any schema Y of M segments, suppose y is any continuous test-function of schema Y, with segment lengths (ny
2. Next, we will show that because the set A((sthet)) H n H5 is non-empty, then A ((())ee()) nH n nH; must be at least a minimum "size." We accomplish this via the following steps.
nM ())) E [0, waa (where we assumed WLOG that E, ()) = 1). Suppose every (Y) is a rational number and that the common denominator of all (Ti, (T)(()))se(a)) is p. Then there exists an no < Opp TK) so that for any positive integer multiple n of no, there exists a discrete test- function X' of length n so that Vi E [K], (B,))) - B, (x)) < T²+M
With Corollary E.14, we first characterize the set A ((ss)lee))) as the union of finite number of poly- topes, where each polytope is equal to the set of ac- tivations which can be induced by test-functions of a particular schema. In this way, each polytope cor- responds to a unique schema, and the finite set of schemas corresponding to the finite set of polytopes
Definition 6.10 (Margin). Given a linear inequality L over M variables and a point x E M define [xx as the dif-
8

---

Non-Asymptotic Length Generalization
n must be larger than no. which was prerequi- the same activations as Vo, but which follows one of the "basis" schema, Y. This new test-function, which we call 1/. is specified by a tuple of M == M() I 122 numbers (Mi, R22, ......................... nM)) E [0, 1ja4, the lengths of the segments of V in schema Y.
serves as "basis" of all test-functions.
We convert Vi into new test-function which induces
site of using Lemma 6.9. There is second, im- portant requirement. WLOG, suppose that the con- tinuous test-function Vo outpuited in step 1 of the proof plan is such that: (BI())) B& e Hit n Hz. Then, the procedure in steps 2 and are such that (Bi())).... (x))))) E Ht n H (Bi()))..... ()(()) E HJ n H and (B .Bi...., BE) E H n H... Now, we would like to be large enough so that (BI)).,.... Bx in HJ n Hz. so that X' would distinguish ʃ and f'. To do this, we need to ensure the coordinate- wise dis- tance between ( (B1(2"..... (x)))) and (Bi..... BB)) is smaller than the margin 7 of C, on the faces of ((M) n ( divided by the maximum L, norm of the linear inequalities defining the faces of A({x))en)) n H n Hy. It is important that the margin of c, is large, as the smallest value of n which ensures that (B) (X"),..... Ba()")) E H NHE is proportional to : In short, we need n z (maxx(o0, poly(K.I)) )) for the resulting discrete test-function X' to distinguish f and f'. Since M S k2, h < 2K, and K < T2, it suffices for n = (poly(T)) M = O(TO(K))) X' corresponds to a string x' E {0, 1)0()o(k3)) that distinguishes f and f'.
Let (Y) C [0, 1jad denote the polytope of valid settings of the lengths of segments of schema Y, as ex- plained in Lemma E.6. Then, there are two halfspaces (1 and 11,44) over M variables such that the poly- tope P settings of the lengths of segments of schema Y, which correspond to rest-functions whose induced activations are contained in (H n cll (H.t). By the existence of V/. P + 0. Moreover, are low-precision, in the sense of Definition 5.2.
is also
:= := (Y) n n H!()) ) is the set of
a polytope whose faces
Denote the set of vertices of P as V. Let e := V
Evev v E P be the average of the vertices of P. We apply Lemma 18 to P to derive lower- bound of the margin of e to the faces of P. of 7 2 V (T) Since e E P PC [0, 1j is a valid setting of the lengths of the segments of schema Y, there is continuous test-function J/2 of schema Y with segment lengths given by c.
Extra materials for the proof sketch are in Appendix A.2.
3. It follows from steps and 2 of the proof plan that if f' are not equal, then there exists a point e e
7. Conclusion
P whose margin to the faces of P is least 7 2 (poly(K.T)vM))'''> where we used the fact that
We prove guarantees of length generalization for various function classes in an idealized setting. We formalize the framework of non-asymptotic length generalization, which requires a computable upper bound for length complexity, We show the Mimilum--Comleextty Interpolator learning algorithm achieves optimal length complexity. We show that whether function class admits non-asymptotic length generalization is equivalent to the decidability of its lan- guage equivalence problem, which implies that there is no computable upper bound for the length complexity of CFGs. On the positive side, we show that the length complexity of DFAs is 2n where n is the number of states of the ground- truth automaton. We show that the length complexity of I-layer C-RASP functions is O(?2) when the ground- -ruth function has precision T, and that the length complexity of 2-layer C-RASP functions is O ((T(()) when the ground- truth function has precision T and K heads.
3M
[V] S 3M2, from Lemma E.22.
Using Lemma E.29, we perturb the coordinates of e E [0, 11 slightly to attain a point that still has 2 margin to the faces of P. but whose coordinates have precision
most poly(K,T) in the sense of Definition 5.2. We will call this perturbed point C. = (n) (e.) mnt") ,...,,,../) ) E [o, 1jM. Let (Bi...., .B) be the activations induced by test- function of schema Y with segment lengths set according to (n) (e-) (c-)
n2
n2 ....,,,(,) (c-)).
4. Finally, we apply Lemma 6.9 the test-function of schema Y. with segment lengths set according to (n(e nn .....,n.. (c.)). to attain a discrete rest-function X' of length n whose induced activations are such (Bi.... Bo X Note that there is a minimal value no S (T)KK, 1 which must be multiple 7. of, as a requirement of Lemma 6.9.
that [I(B) (X"),..... Bx(x")) (x()")
It is open whether the proof techniques can be extended to 3-Layer C-RASP programs, or to C-RASP programs whose layers contain bias terms. It is open how to formalize weaker notion of partial length generalization which does not entail length generalization to arbitrary length inputs.
O pally(k))poly(1))
Now, we discuss how large n needs to be so that dis- crete fest-function X² distinguishes I and f" First,
9

---

Non-Asymptotic Length Generalization
Acknowledgements
Hoperoft, J. and Ullman, J. Introduction automata theory, languages, and compuation, 1979.
This work was supported by NSF IIS 2211780 and the Stanford HAI-Google Cloud Credits Program. TC acknowl- edges funding from an NSF Graduate Research Fellowship. ZL acknowledges funding from OpenAl Superalignment Grant.
Huang, X., Yang. A.. Bhattamishra, S., Sarrof, Y., Krebs, A., Zhou, H., Nakkiran, P., and Hahn, M. formal frame- work for understanding length generalization in trans- formers, 2024, URL https: / /ppnrevieeeeeeeeeeeeee nett/ forum?id-U49N5V33
Impact Statement
Jelassi, S., d' Ascoli, S., Domingo- C., Wu, Y., Li, Y., and Charton, F. Length generalization in arithmetic trans- formers, 2023. URL https: happ:://axivve perxiv.orgge /abs/ 1306.15400.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Li, M. and Vitányi, P. An introduction to kol- mogorov complexity and its applications, 2008. URL https://link: springer com/book/1...o..
References
Abbe, E., Bengio, S., Lotfi, A., and Rizk, K. Generalization on the unseen, logic reasoning and degree curriculum, mlr. mllr.press/
Mahankali, A., Haochen, Z., Dong, K. Glasgow, M., and Ma, T. Beyond ntk with vanilla gradi- ent descent: mean-field analysis of neural net- works with polynomial width, samples, and time, net/ forum?
2024. URL URLhtttss:/prrccedee /202/abboe23d (atbbee3a/bbbbbe waw.e/abbbeaaaa.ee .df.
Anil, C., Wu, Y., Andreassen, A., Lewkowycz, A., Misra, V., Ramasesh, V., Slone. A., Gur-Ari, G.. Dyer, E., and Neyshabur, B. Exploring length generalization in large language models, 2022. URL https:// openreviex net/ forum? wwt.::........s//......
2023. URL 2aar222nMiiimmmmnotttessss22...
Marsden, A., Dogariu, E., Agarwal, N., Chen, X., Suo, D., and Hazan, E. Provable length generalization in sequence prediction via spectral filtering, 2024. URL https:
Baker, B. S. and Book. R. V. Leversal-bounder multipush- down machines, 1974. URL httpp::/ /ttpps:://///// /oii..... org/10. 1016/5000 0000 (74) 80027-9.
/ //arxiv. orgiii.orrg/bbba www.rr/gbbb.........oo 2411. 01035.
Nogueira, R., Jiang, Z., and Lin, J. Investigating the limita- tions of transformers with simple arithmetic tasks, 2021, URL https: /awxiv httgg//bb//1.....
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan,
J. Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G.,
Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler,
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., Sutton, C., and Odena, A. Show your work: Scratchpads for intermediate computation with language models, 2021. URL abs/20 Abs/2112.00 00114.
M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020. URL https:
http:ppss..ppsscccppppee//////// 1457CC66ff433977111111133a Absttracc L. and Warmuth, M. K. The minimum consistent df problem cannot be approximated within any polynomial, 1993. URL http:: / /dl acm. www//e///ooooo /pdd//dd 1145 1455138027.1533 138042.
html.
Delétang, G., Ruoss, A., Grau-Moya, J., Genewein, T., Wen- liang, L. K., Catt, E., Cundy, C., Hutter, M., Legg, S., Ve- ness, J., and Ortega, P. A. Neural networks and the chom- sky hierarchy, 2023. URL https: peattps://peerewee htt//pdfPid-WWxttakeeeeee
Rissanen, Modeling by shortest data description Autom., 14:465-471, 1978. URL https: //pi. semanticscholar orgg/oorpsID::31400000
Freiwald, R. C. An introduction to set theory and topology, 2014. URL ht https: /ptpa///oasscchsaaaiiiii.. wustl. edu/books/20/.
Rockafellar, R. Convex analysis, 1970.
Ruoss, A., Delétang, G., Genewein, T., Grau-Moya, J.,
Csordás, R., Bennani, M.. Legg, S., and Veness, J. Randomized positional encodings boost length gen- eralization of transformers, 2023. URL https:// aclanthology, www./oo2..........o (.002..ccl--a wwo.rsssoor....... 161/.
Gold, E. M. Language identification in the limit, com/
1967. URL 1oO..UR.Lattte:///w..eeeeeeeaee
10

---

Non-Asymptotic Length Generalization
Shaw, P., Chang, M.-W., Pasupat, P., and Toutanova, K. Compositional generalization and natural language vari- ation: Can semantic parsing approach handle both?, 2021. URL https: hac.annhology..ogg//ooo acl mell-ong.200 75/.
Shaw, P., Cohan, J., Eisenstein, Lee, K., Berant, J., and Toutanova, K. Alta: Compiler-based analysis of trans- formers, 2024. URL
/ n
Forum?id=h73 51wllwll.. 9xiR.
Solomonoff, R. J.
A formal theory of induc-
tive inference. part i, 1964. URL https:
//www.sctencedlrectt cww.science//////eeccccccccccccc atricle/pp//00119951911555
Vaswani. A., Shazeer, N., Parmar, N., Uszkoreit, J.. Jones, L., Gomez, A. N.. Kaiser, L., and Polosukhin, I. Attention is all you need, 2017.
URL
https://prccedding..eurr...
ce
3ffe223357cce1110033000033332223 pdf.
Weiss, G., Goldberg, Y. and Yahav, E. Thinking like trans- formers, 2021. URL /tthhtpps//prooeeellnn mll. press/v139/ /wtss//s///eeesssllllla... pdf.
Yang, A. and Chiang, D. Counting like transformers: Com- piling temporal counting logic into softmax transformers, 2024. URL https:// /ewe:///eeeeeeeeeeeeeeeeeee n forum?
Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J., Bengio, S., and Nakkiran, P. What algo- rithms can transformers learn? a study in length gener- alization, 2023. URL /tt3://tttttttt//////eeeeeeeeeee httpss///ppeeeeeeeneeeee net/ forum? Rid=Asa TuHnHHX.
Zhou, Y., Alon, U., Chen, X., Wang, X., Agarwal, R., and Zhou, D. Transformers can achieve length generalization but not robustly, 2024. URL https: http::ttt////ppetteee r/venn/eew............. net net/pdf? het/ppdffid

---

Non-Asymptotic Length Generalization
Organization of Appendices.
Section A contains supplementary material to the main paper, particularly the proof sketch. Section B contains a discussion of Gold (1967)'s is asymptotic notions of learnability and the proof of Proposition B.2. Section contains the proofs of Theorem 3.2, Lemma 3.4, and Lemma C.6. Section D contains the proof of Propositions 2.7 and 3.5. Section E. contains the proof of Theorem 5.5. Section E.2 contains the full proof of Theorem 6.1, which uses Definitions and Lemmas defined in the later sections E.3 to E.6. Section E.3 contains proofs of Lemmas relating completeness of basis schema. Section E.4 contains proofs of Lemmas relating to lower bounding the margin of the average-of-vertice of polytope with fow-precision faces. Section E.5 contains proofs of Lemmas for approximating a continuous test-function with a discrete test-function. Section E.6 contains auxiliary Lemmas.
A. Missing Parts from Main Paper
Here, we put some supporting content which were referred to in the main paper, but omitted due to space constraints.
A.1. List of Allowed C-RASP Operations in (Yang & Chiang, 2024), in the Context of Definition 5.1.
Table Boolean- and count-valued operations allowed in a C-RASP program.
Boolean- Boolean-Valued Operations
Count- Valued Operations
Initial
(1 = 1 [2g = a] for a E {0,1}
Partial Sum
h = (s(((()))
h -11(6')
hg = 11/²) ? 113
Boolean
Conditional
h (1) nn(")) h
(8))
11 h1 + (1")
Addition
Sign
hg) = 11g (8))
> 0]
hg = nn(1) (1")
Subtraction
Constant
hnt) :=
h (1) min(h (8)) .n(("))
Min/Max
j
()) h " := max(h;
, .n))')) j (1)
Constant
1
A.2. Supporting Material for the Proof Sketch in Section 6.
Proof that Theorem 5.6 follows from Theorem 6.1. Proof of Theorem 5.6. Every function f in C-RASp2,K.T has at most K heads and T precision, and so C(f) < T =: a. Thus, Theorem 6.1 implies that inputs of length at most N Ama (a.) < (a.
(1)) = ((TO(K)) suffices to learn C-RASP2.K.T
Proof that Lemma 6.2 follows from Lemma 6.3. Proof of Lemma 6.2. By Theorem 3.2, it suffices to show that for any two un-equal functions f C-RASP2 such that T(f) < a and T(f)((f) I a, there is string of length at most Olog' o) which distinguishes them. If x()) < a and ((f))(()) < a, then T(f), are upper bounded as T(f') S a, maximized when K(f), K(f) = 1. Meanwhile, K(f), K(f)) are upper bounded as K(f), K(f') < log a, maximized when K(f) = T(f)² K(f) = T(f)?. Thus, f. E C-RASSp2.og.... Applying Lemma 6.3 implies that there is a string of length (a a)) distinguishing f and f
Formal Summary of Each Step of Proof Plan in Section 6.2. Below, we formalize the conclusions drawn from each step of the proof plan in the proof sketch of Lemma 6.3. Putting these Lemmas together yields Lemma 6.3.
Lemma A.1 (Analysis of Step 1). f + f' e C-RASP2,K,1 then there exists continuous test-function Vo such that (B:(%)))k(M) E (HH n H U (H n H.)) WLOG, suppose (B.())))eMM) E H n
Lemma A.2 (Analysis of Step 2). Given continuous test-function Vo where (B(())) E H n H then there exists a continuous test function Y2 of schema Y of M S k.2 segments, where lengths of the segments of Y2 is given by
12

---

Non-Asymptotic Length Generalization
(n/)) E [0,1]MM In addition, the M -dimmensional point (m(") )estar] has margin at least 7y 2 3M² (poly (KTT) to the faces of polytope P == cl(A(M) n H(M) (H2
Lemma A.3 (Analysis of Step 3). Given any point c: (mg )E(M>] E [0, 1jad which are segment lengths of particular test-fiunen test-function of schema Y. suppose с has margin at least y > to faces of polytope P = =X(A( n H(*)) nn Hz ())
Then, one can perturb the coordinates of e. to get a point c, E [0, 1] MM such that (1) the margin of c, to the faces of P is at least and (2) the coordinates of Cs have precision at most (o
Lemma A.4 (Analysis of Step 4). If there exists > 0, C, E P such that the margin of c. to the faces of P is at least 3 and the coordinates of c. have precision at most poly(K.T) then there exists discrete test-function X' such that (B:(2")))E1 E H1 n H2z and the length of X' is at most O (poly(K.)) TTh3.
With M < k2, S 2K, and K S T2, we conclude that f + f', then there exists a string x', |x'| S O(TO(K)) such that [(x)) (''))
Details of Key Steps of Proof Plan of Section 6.2. We now elaborate on key steps of the proof plan. We will focus on Step 2, because Step just applies Lemma E.30, Step just applies Lemma E.29, and Step 4 applies Lemma 6.9 and analyzes how large n needs to be so that the final discrete test-function distinguishes f'
Details of Step 2. First, we characterize A A(fss)eejs) the union of a finite number of polytopes.
Lemma A.5 (Characterization A ((())))))) combination of Corollary 1, and Lemma E.16). For any (k; T)- configuration [sikeek) there are a finite number of k-dimensional convex polytopes {A]]EEN,) Na co, such that
A({saliE(H) = U A
NE
Figure 9 pictorally depicts the completeness Lemma for A 2, which shows that (((s:)et))) is the union of two triangles.
The way Lemma A.5 is proved is by showing that for any continuous cest-function V, there exists another continuous test-function of one of a finite number of possible schemas which induces the same activations (B:))) (E(K) We call these NA schemas "basis" schema; they are a "basis" in the sense that any continuous test-function is equivalent to a continuous fest-function which follows some basis schema. Figure 8 depicts a basis schema. We defer the details to Appendix E.3. The main take-away is that each polytope A, C [0, 1]&k corresponds to schema Yj. and A, is the set of activations which be induced by test-function of schema Y--
Vj E N1). A₁ = (B.. Bx())) y valid test-function of schema Y, } C [0, 1|*
Thus, given Yo from Step such that, WLOG, (B.O%)))eja E H n H then there is an equivalent test-function 3 of one of the basis schema, Y (Yg) (e(a)) such that (B((i)) (B;(6)))vEM) H H.. Denote the set A(Y) as the particular Aj which corresponds to schema Y.
A(Y) ((B.0)) ... B&)))) y valid test-function of schema Y } C [0, 1]
Now, suppose that schema Y consists of M segments, whose lengths denote (n1, (i,,,,,..... nas) E [0, 1]M with Eie(M) n4 1. Note that not all settings of (ni, .., are valid, because there are linear constraints which must be met by (n, n2,..., n. which are described in Lemma E.6. Define A(M) C [0, 1] as the set of all valid settings of (n1, .l,...,, My)) per Lemma E.6. (Y) is an (M - 1)dimmensional polytope, whose faces are parameterized by linear inequalities whose coefficients are at most poly (K, T) in magnitude (i.e. poly K, -reeeiiio.
13

---

Non-Asymptotic Length Generalization
(Y) = {(21,................... nar): valid segment lengths of schema Y and
n4 - 13 c 10 Σ M
Further, define H1 (M) and H1 (M) as the analogous halfspaces to HJ and H but in the space of segment lengths as follows. There exists a linear map : RM + IR which maps points in A (Y) to points in A(Y). L {0. 1) is such that Try =1 - segment j schema Y lies above line (that is, for every in the domain of segment j. the y-value of the segment at x least s; x) and hence contributes the ith activation ())) of any test-function of schema Y. Using L, we can rewrite the inequalities which characterize H1, H2 in terms of (M. nMM)
K
K
1 = {(n11 nar)
Bon(11)) > >}}= = {((I,-.... ,RM) Σ
A
Σ
n2J >
2}
i=1
I s.L. Lone),))
K
K
H = {(11 nm)
X M.n((2(2.) <z) = [(ni....... )
Σ
X
Σ
R2 < <2}
I jst. (2
With P = c((A(A) (Y) n ((()) n )), we use the fact that (B(()))EE)) E H1 n H to deduce that AY)) n.
* 0. Let V be the set of vertices of P. This next Lemma is for lower lower-bounding the margin of point c- M +- Evev [0, Mj on the faces of P, when the latter is non-empty.
H H n H M)
Lemma A.6 (Margin lower bound, slightly informal version of Lemma E.18). Consider nonempty d-dimensional polytope P C. Rd with vertices V and N faces. Suppose the faces of P are each defined by linear inequality over variables failiela with integer coefficients of magnitude at most Piace where points on the face satisfy the linear inequality with equality. For j E [,], define Lj as the linear inequality for the face of P. Then, for any j E [N), for any vertex x E V which does not lie on the jth face of P. we have the following lower bound on the margin of x on the jth face of P.
1
Lz(x)
(Piace Vayd
With d M and Piace = (olyoo,, T) and using the linearity of the margin, it follows that the margin of [V] Evev [VI (poly(K,7)VMM) c is a point in [o, 1]M, and it is a valid setting of segment lengths for
on any face of P is at least 1 test-function of schema Y, since e has positive margin to the faces of P, it is contained in P C (00 The activations of the test-function with segment lengths given by e will be contained in H n H5 since e e P C ((M) concludes Step 2.
n H, (M) This
B. Asymptotic Length Generalization, Adapted from (Gold, 1967)
Define the following asymptotic notion of learnability.
Definition B.1 (Length Generalization in the Limit, adapted from Gold (1967)). A function class F C FR admits length generalization in the limit w.r.t. encoding system R if there exists a learning algorithm A such that for all f E F, there learns f at input length N'.
exists a natural number such that for all N' 2 N, A
The above definition of length generalization in the limit is special case of the so-called identification the limit in the informant model in (Gold, 1967). The major difference is that (Gold, 1967) requires the function class F be learnable in arbitrary order of data presentation, while in our case, we only interested in particular order of data presentation, namely the order of increasing input length.
Proposition B.2 is result about which function classes are learnable in the sense of Definition B.I. We provide proof here, which is similar to that of Theorem 1.4 of (Gold, 1967) Proposition B.2 (Adapted from Theorem 1.4 of Gold (1967)). For all encoding systems R, the function class JRR admits length generalization in the limit, and thus so does any function class F FR.
14

---

Non-Asymptotic Length Generalization
Proof. Consider a learning algorithm which enumerates functions in FR. It maintains a current hypothesis, which is initialized to the first element of the enumeration. Given input training set, the learning algorithm checks whether the current hypothesis interpolates the training data. If does not, then the current hypothesis is updated to the next function in the enumeration until the current hypothesis interpolates the training data, at which point the current hypothesis is outputted.
First, because R. maps 10" to FR, then we can enumerate FR simply by enumerating all strings E {0, 1}", say in the of natural numbers, and then computing R(p) for each string p. The computation of R(p) will always halt by Definition 2.1. Every function in FR appears at some point in this enumeration by the definition of FR. Suppose that we denote this enumeration by & {fo. fi, f2....h .. with & == {fo. fi. f2, ......................... fe} being the first c+ elements of the enumeration, for any C N.
order of increasing Dinary-representation
Second, because the output of R. is always a computable function which halts on every input, the learning algorithm described in the first paragraph is computable.
By Theorem 3.2 with C(-) being the mapping from a binary string to the integer it represents in binary (so that each finite representation is mapped to its order in the aforementioned enumeration), it suffices to show that for any e E N, (EE)) := min(n Vf + f Ee, 3r E {0,1) s.t. f(x) * f'(=) < oc. This follows directly from the fact that |Ec]
and that for any f f E Ec, there exists some string z; |ac| < oo where f(x) * f'()). For each pair of unequal functions in & pick the shortest such string x which distinguishes them, and take (EE)) to be the maximum of the lengths of these distinguishers. This must be finite.
C. Proofs on Equivalence of Different Non-Asymptotic Length Generalization Definitions
C.1. Properties of Amci
We will prove that Amai optimal with respect to the quantity NA (c). Note we will drop the superscripts for F,C, R from the notation for convenience.
Theorem 3.2 (Optimality of Minimum-Complexity Interpolator). Given any encoding system R and complexity measure C. for all E N, it holds that NR (c) = min (c) = N(FR)). As consequence, the following three statements are equivalent:
A
AR.C
ma
Function class F. admits non-asymptotic length generalization;
Function class FR admits non-asymptotic length generalization, via learning algorithm ARCC For all e E N, length complexity of FR, N(FR), computably bounded in c.
Proof of Theorem 3.2. For any E N, have
N(F == min min f e F with (f)) Sc, there exists x E (0, Sn s.t. f(x) # f((r))
We will show separately that (A)a(c) 2 mina Na(c) 2 ( and NAma (c) S N(FB).
(1). min NN(c)= 2 ((FR) follows from the fact that for any N < N(F.), there exists f # f' with C (P)) e that agree on all imputs (0, 1)S,, Given training set (zx, (xx)) Va E (),1) = {(x, f(()) Va E (0,1) any algorithm A which outputs an encoding of a function which is not equal to f will be wrong in the case the ground truth is f. Meanwhile, any algorithm A which outputs an encoding of a function which is not equal to f' will be wrong in the case the ground truth f'. Thus, NA(f)= > N or (A()') > N, so Na(c)= > N.
(2). (c) < N(FR). ). For f with CR(F) S c, suppose that on input of ((xff(z)) VX E f0, (0.1)SM(F Amai outputs p', where R(p')= * f. This implies that C(R(p')) S C(r') & (R( S c and that R(p') is consistent with (xx, f())): Ve E {0. 1)5 This is contradiction of the definition of N(FR), ), which says that all pairs of unequal functions f with CR (F) S can be distinguished from each other by some input of length at most N(FR)
Denote p = p' R(() = R(p'). The following Lemma is also useful for showing that the same bounds on the length com- plexity hold whether we think of Amai as operating over finite descriptions E {0, 13* (which is the actual implementation) or as operating over functions f F (which is more abstract way to think of Ama)).
15

---

Non-Asymptotic Length Generalization
Lemma C.I. Given (R,,,O with (R) -in then for all N:
min(n: : VS # f e
=min Vp pl E C(p)),,, < Fr, |z|| (v) # R2y)(x)))
Proof. Every function f F with (f) has some finite description p with R(p) f and C(p) S No function E F with (J) > has any finite description p with R(p) and C(p) S c.
We also have the following result which says that Ama is computable if C satisfies Assumption 2.4. Lemma 3.3. Under Assumption 2.4, Algorithm is computable and thus valid learning algorithm.
Proof of Lemma 3.3. By Assumption 2,4, we use TM E' to enumerate all programs E {0, 1 in non-decreasing order of C(p) and at each iteration check if (p) consistent with the training data. it is, we output p and stop. Otherwise, we continue to the next program. Both the enumeration and thecking-consistenee procedures are computable, as assumed by Assumption 2.4 and Definition 2.1.
C.2. Equivalence of Non-Asymptotic Length Generalization with Decidability of Language Equivalence Problem
Now, we will prove that Definition 2.6 equivalent to a few other definitions. First, recall the definition non-asymptotic length generalization and the language equivalence problem.
Definition 2.6 (Non-Asymptotic Length Generalization). functioo class F S FR admits non-asymptotic length generalization w.r.t. encoding system R. and complexity measure C if there exists learning algorithm A and computable function N RR.F. NN + N such that for all f* F and for all N' 2 NR. (F*),, length-eennrralizabll learns f at input length N'.
Definition C.2 (Language Equivalence Problem). The Language Equivalence Problem for encoding system R. is the computational problem where given any p.q E {0, 1)", determine whether R(p) R(gg).
We now prove the following equivalences.
Lemma 3.4. For any encoding system R and complexity measure C satisfying Assumption 2.4, the Language Equivalence problem for R is decidable if and only if length complexity of FR, N(FR), is computably bounded in c. Thus it is also equivalent to the property that FR admits non-asymptotic length generalization.
Proof. Suppose TM E enumerates elements in {0, 1] non-decreasing order of their complexity according to C.
N (FF) computably bounded in c = Language equivalence problem for R decidable.
Suppose there is computable procedure F that, for any receives input and outputs upper bound on N(FR) We will describe an algorithm that is given any two finite representations, p.q E {0, and uses F to determine if R(p)= R(g).
Given p.g E (0, 10, compute c = max(C(p).C(g)) and generate the training dataset Dr (R(g)). Now, check whether V(,, (x)) E "non-equivalent".
that (x) = Rx))(x). If this the case, return "equivalent." Otherwise, return
To argue correctness, if there is some (z, R(g)(x)) E (R(g))(()) where R(p)(x) # (())(a), then clearly these two functions are not equal. If V(,, (z)) E DF(e) (R((), R())(z) (x)) then since C(R(p)) & C(p) S c and C(R(g)) < C(g) < c, then it must be that R(p) = R(a), or else F(c) is not an upper bound of N(FR).
Language equivalence problem for R decidable = N(FR) computably bounded in c. Suppose TM А solves
the Language Equivalence Problem for R. By Lemma C. 1, it suffices show that the following quantity is computably bounded E N.
m vp # p' (111),,CC).cc)))) ar, |x| S n, R(p))))) # R(p'(()))
Algorithm 2 computes an upper bound of this quantity.
16

---

Non-Asymptotic Length Generalization
Algorithm 2 Computation of ((FR)
Require: Integer N
Ensure: R)
1: N +
2: for all pairs of programs (p, q) (enumerated by E) with C(p), S do
3: if (p. q) = "non-equivalen"" then
4:
for all strings x E {0, 13" with non-decreasing length do if (z)) (x) then
5:
6:
N < max(NV [z])
7:
break
8: end if
9: end for
10: end if
end for
return N
Algorithm always terminates, since the for-loop in line 4 only is performed on p. E {0,1) which are not equivalent, which are distinguished by a finite string. It returns the smallest length required to distinguish every two non-equivalent p.q E {0, 13"
Finally, it follows from Theorem 3.2 that the language equivalence problem for R being decidable is equivalent to non-asymptotic length generalization of FR w.r.t. R, C when C satisfies Assumption 2.4.
C.3. Connection to Finite Identification, (Gold, 1967)
Our notion of non-asymptotic length generalization is related to Gold's notion of Finite Identification (Gold, 1967), which is restated as follows in the context of length generalization.
Definition C.3 (Finite Length Generalization ("Identification", (Gold, 1967))). function class F C FR admits Finite Length Generalization w.r.t. encoding system R if there exists a Turing Machine (TM) A, where for any fa E F, on input of training set D (f=) for some E N. A satisfies:
1. A can only output either "pass" or some program P E {0, 13" outputs P at least for one N E N.
2. Whenever A outputs some program E 1)", , it must be correct in the sense that R(p) = fx.
is clear that Finite Length Generalization implies Length Generalization in the limit- one can replace "pass" by arbitrary program á and sticks to the same (correct) output á once A outputs any program p. Intuitively, function class admits Finite Length Generalization if there exists learning algorithm which can perfectly length generalize at finite input length (and where the learning algorithm knows the length at which it length generalizes), rather than only generalizing in the limit. Thus, Finite Length Generalization is a very desirable property. However, it is in general too good to be true. We give a characterization of Finite Length Generalization in Lemma C.4. As a consequence of Lemma C.4, functions classes as simple as the set of languages that are finite do not admit Finite Length Generalization.
Lemma C.4 (Characterization of Finite Length Generalization). A function class FR admits Finite Length Generalization w.r.t encoding system R if and only for any fo FRR there exists a natural number N such that f is the only function that is consistent with the training set D (f.).
The proof of Lemma C.4 is straightforward and omitted.
Since Finite Length Generalization is in general too restrictive, we relax the definition allow the learning algorithm output a program á with some information the complexity measure of ground truth fs. namely some 2 C (f.). This leads to the definition of Finite Length Generalization with Complexity Information in Definition C.5. Interestingly, Definition C.5 is equivalent to non-asymptotic length generalization (Definition C.3).
Definition C.5 (Finite Length Generalization with Complexity Information). A function class F C JR admits Finite Length Generalization w.r.t encoding system R and complexity measure C if there exists a Turing Machine (TM) A. which for any f. F, on input of training set D (f.) ).. for some N N and a natural number c 2 C (f.), it satisfies that:
17

---

Non-Asymptotic Length Generalization
1. A only output either "pass" some program ý E {0, A outputs least for one N N.
2. Whenever A outputs some program (0, it must be correct in the sense that R(p) = fe.
Lemma C.6 (Equivalence Finite Length Generalization Definitions), For any encoding system R. and complexity measure satisfying Assumption 2.4, function class FR admits Finite Length Generalization with Complexity Information w.r.t. R and C if and only if length complexity of FR. NFF)) is computably bounded in c. Thus is also equivalent to FR admits non-asymptotic length generalization.
Proof of Lemma C.6. Suppose TM E enumerates elements in (0, 13* in non-decreasing order of their complexity according to C.
(FF) computably bounded in c = F² admits Finite Length Generalization with Complexity Information w.r.t. R. and C. Let F N + N be computable upper bound on (FFR). Let be given by Algorithm 3, on input (f-f)) and CR E.
Algorithm 3 Learning Algorithm A
Require: Dataset (x(s=); e with e 2 C (f.)
Ensure: Either "pass" an program p
1: if N < F(c) then
2: return "pass"
3: else
4: D (xAmn(DD(()))
5: return p
6: end if
First, A only ever returns "pass" or some E {0, 1} since Amal only ever returns elements of {0, 1)". Second, by Theorem 3.2, for с 2 C (f+) and VN F(c), then ((Amai(D (Dx(())))f))) = f.. Thus, whenever returns an element p E {0, 1}", it is such that (p) f., and there is at least one N where (Dx.)()) f..
FR admits Finite Length Generalization with Complexity Information w.r.t. R and C - N(FR) computably bounded in c. We need to prove that there exists some computable F which upper bounds N Suppose A satisfies Definition C.5. Let F be given by Algorithm 4.
Algorithm 4 Algorithm for F
Require: Integer N
Ensure: Nmax
1: Nmax t- 0
2: for all p E 10, with C(p) S (Enumerate with E') do
3: N +-0 0
4: while A(Dx(R(p)),
"pass" do
5: N < N +1
6: end while
7: N + max(NNax. N)
8: end for
9: return Nmxx
Algorithm 4 is computable, due to the guarantee of that for any f., given c 2 CR (f=), there exists some N where R(A(Dx(f.)) fr, which ensures termination of Algorithm 4.
Regarding correctness, if there exists some E N where F(c.) < min(n: # p' E (0, 1) C(p), < c. 3r, |æ| < (x) * (x))) then there must exist two p.q E 13 with C(p), ((p),C(g) S c., which are not equivalent, but which agree on all inputs of length at most F(c.). WLOG, suppose that C(p) - C(g).
There exists N₂ < F(..) where A(Dx, (R(g)),C())) + "pass". In particular, A(Dx, (R())), C(q)) must return a á which equivalent to 4, where # p. On the other hand, since N₂ S F(c.), we have DN (R(g)) Dx, (R(p)). Thus, we
18

---

Non-Asymptotic Length Generalization
have shown that A(DN, (R(p)), C(g)) + "pass" and is finite representation which is not equivalent to the ground-truth p. Since C(p) S C(g). this yields contradiction with the fact that whenever A is given upper bound on the ground-truth complexity and A does not return "pass", it must return finite description ş which is equivalent to the ground-truth.
Figure C.3 sums up all these equivalences.
Non-Asymptotic Length Generalization (Definition 2.6)
Decidability of Equivalence Problem (Definition C.2)
Lemma 3.4
Length complexity N(F computably bounded in
Theorem 3.2
Lemma C.6
Non-Asymptotic Length Generalization by Minimum Complexity Interpolator
Finite Length Generalization with Complexity Info (Definition C.3)
Figure 1. Summary of equivalence results hetween different characterizations of length generalization in Section 3 under some mild simplicity assumptions on the complexity measure C (Assumption 2.4). Each arrow represents an implication proven by the corresponding theorem.
D. Proofs on Length Generalization for DFAs and CFGs.
Proposition 2.7 (Non-Asymptotic Length Generalization for DFAs), Let RDFA be the DFA encoding system defined in Definition 2.2, and let CDFA be the number of states in DFA. Regular languages FR admits non-asymptotic length generalization w.r.t encoding system RDFA and complexity measure CDFA. More specifically, there exists learning algorithm A such that NR (c) 2c for all E N.
In the following proof, we essentially describe and analyze the State Minimization Algorithm (Hoperoft Ullman, 1979). Before proving the proposition, we will need few concepts and Lemma D.I.
Suppose there is some ground-truth minimal DFA, D, of n states, with language ::= L(D). Define as the empty string, of length O. For two strings v. denote up as their concatenation. For any E {0, 13", denote f.(x) = + a E L. Denote Q as the set of n states for D and 6(-))) -) Q x {0, 1} + Q as the state transition function for D, with start state go- Let F C Q be the set of accepting states. We say that states 9, d' E Q are distinguished by string u E {0, 1)" if 5(g. v) E F and 8(d', v) & F. or if 8(q, v) & F and 8(g', v) E F.
In general, applying string from the start state go in the DFA will cause the DFA to end up some state q E Q and an identification can be made between the input string and the state it causes the DFA end up in. Thus, to learn the DFA, would like to find mapping from {0, 1 3 to [n:]. which tells us which strings correspond to which states in the ground-truth DFA. To do this, we claim it is sufficient to consider the equivalence class given by the sets (E(u))us(o,pp where:
Vu E (0,1) = to {0, (0 we L}
u, If for u, u' E 10,1)5M E(u) E(u'), then we will claim that these two strings correspond the same state. Otherwise, u, u' correspond to different states. This is what is meant by an equivalence class over (E(w))ve(o.1)5r
Once a learning algorithm can make this identification between strings and the states they correspond to, then the learning algorithm can infer the transition function of the DFA by considering, for each u E (0, (0 the states E(u), E(u0), and ([()))uego.)
and (uul), via the sets (E(u))=e((.1)) to the start state. Strings u corresponding to accept states will be such that E Flu). Note that we just need to consider
This gives the transition function. E(e) corresponds
19

---

Non-Asymptotic Length Generalization
(uE (0.1)5 instead of {E(u) (e (0.) characterize the states of D, since any u of length larger than will cause the DFA reach some state that is also reached by string of length at most n.
(E(u)) wE
We claim that proving the following property about our sets E(u) suffices to prove that there is learning algorithm which identifies the ground-truth DFA.
Lemma D.1. For any minimal DFA D with n 2 2 states and transition function 6, then with E(u) defined as above for each u E (0, 13S", we have Vu, wf E {0, 135", ,8(q0, u) = 6(10, u²) + Fl(u)= = F(u').
First, we will show how prove Proposition 2.7 with this Lemma.
Proof of Proposition 2.7. Suppose DFA learning algorithm is given inputs of length 2n - 2. For 2 2, Lemma D. implies that the learning algorithm can identify the states of D by constructing the sets {E(u))uE(0.1) [e(001) using its training data ((x, fx)) |a|| I 2n 23. Each state is identified with an equivalence class of { (E (0,11] since each state in an n state DFA can be reached by string of length at most n - 1. The state transitions can be identified from {E(")) (0.1) by considering, for each E {0, 1}55=1, the states E(u), E(uO), and E(ul). E(e) corresponds to the start state. Strings u corresponding to accept states will be exactly those such that E E(u). In the case that the learning algorithm only receives inputs of length at most O (i.e. it only receives (c, fc))) 1, it will simply output the DFA with language 0 if the labels of all inputs received are 0 and it will output the DFA with language {0, 1 if the labels of all inputs received are 1. This handles the case where n 1.
The learning algorithm above identifies the ground-truth DFA, requiring inputs of length at most 2n - 2 when the ground- truth DFA has n states. By Theorem 3.2, the Minimum Complexity Interpolator Amai will also require inputs of length at most 2n 2 to identify the ground-truth DFA. This proves the Proposition.
Now we prove Lemma D.I.
Proof of Lemma D.I. Showing 5(2o: u) = 8(1o u²) the states reached by u. from qu are the same, so no string of any length can distinguish them 8(go. u), 8(9,, u'), so E(u)= = Evu).
F(u) = F(u') is easy, since if ā(go; u) = ō(go, n'), then
We now show 8(90, u) # 8(go, w') = E(u) # Elu'). We are given that the ground truth DFA has n states and is the minimal DFA for its language, so that there are no DFAs of fewer states with the same language. Given this, we claim that there are exactly n equivalence classes among { [E(u)) (0.1) (o.1 su. Each equivalence class must correspond unique state, so cach of unique states can be identified with a unique E(u), finishing the proof of Lemma D.I.
For 0 S i 2, u E (0, 1)5 define (n) (u (0, 1)+1 E T.). To do this, we claim that for any < n 2, if the number of equivalence classes in (E) (0,1) is less than then there must be some u, w' E {0, S and e/41 E {0, 13s+1 such that
We will now show that there are exactly n equivalence classes among uE
E,(u) E,(u') and fa (um:41) # f=(((1(4))
Suppose this were not the case. That is, suppose that for some i < n 11-22 2, (1) the number of equivalence classes in [E((4))ue(o,)ss is less than n. (2) Yet, Vu, u' E {0.1).mm Vo,41 E {0.1)*+1, E,(u) = Ex()) = fuu7411)
f (u(10141). We want to show that together, (1) and (2) contradict the minimality of the ground-truth DFA.
We claim that, by induction, (2) implies that for every 2 i, for every u, u' E {0, 11 and uk+1 E (0, 11 Ex(u) = Eg (u') = (ure+1) (u(vv))). This is true for base case k = by (2).
For the inductive step, suppose the claim is true for k > i. Suppose u, u' {0, 1)55 are such that Ex(u)) Ex(n'). Then Ve% E {0, (. = (a('v)), For any such string Us with length k we can break Uy into prefix of k i bits and suffix of i bits. Thus,
Vek-i E (0,1)*-1, Vos E (0, f. = (u'vx-
Each string utk-i and u - will correspond to some state reachable by some strings n", n E (0, 1),1,, in the sense
20

---

Non-Asymptotic Length Generalization
that 8(yo: uek-s) 8(10, n") and 8(10, u' w() 8(1o ) each state in the DFA can be reached by string of length at most 1. Thus, Fr("") E,(u"), that by (2), V0.41 E {0, 13 f. (u"" fu(" Since 8(go, wvn-i) 8(20, u") and 8(go, u'vn-i) = 8(10, u"") imply that for any such 0441 fo foU = fu and g++1 fu' = fa (u" "ul"us 11+1), then Vo4+1 {0.1)*+ (urk-)111)11)) = (u('tx (((4). In short,
Vok-s E [0,1)*-1,v0) Vus+1 E f = fo (ul (061)))1)
Thus, VeR+1 E {0,1) f. (wvx+1) = (u)))+),, completing the induction. We have proved the claim for all A 2 i. However, this will lead to a contradiction we take - oc, since applying the guarantee for all 2 we have that
Yu, u' 10, ,,(,) E((')) (u) Eoo(
Where (u) {o E (0,1)* ue L}. We know that any two distinct states in minimal DFA will be distinguished by some finite string (See Theorem 4.24 of (Hoperoft & Ullman, 1979)). Thus, for any u, u' E {0, 1js
Eu(u) = Ei("')
Eas (u) = Foc (1²)
8(10, u) 8(90, u¹)
So n #EEuiivalence classes in {Ex (w) (w)) # (Equivalence classes (E((W))e(o))ss) < n, where the last inequality is due to (1). This is contradiction.
Thus, while the number of equivalence classes in (E is less than n, there must be some u, u' E {0, 1J5" and 1 E {0, 1 such that
Fu(u)= = Fi(u') and (uv(41) # fa (1(v441)
This implies that the number of equivalence classes in {E+z1 (u) heee) is at least 1 greater than the number of equivalence classes (F(("))ue while the latter less than n.
Finally, (u) (e has 2 equivalence classes for any non-trivial DFA that whose language isn't 0 {0, 1)", and any 2 2 state minimal DFA must be non-trivial, the minimal trivial DFAs have at most state. The two equivalence classes of (Eo(u)) (0, sn given by the states that are accepting and those that are not. For all < n - 2, the number of equivalence classes in (E+z (u) we (0,1)) grows by at least from that of {Ex(u) (u(()))eet))))) (0, We can have no more equivalence classes than n, and the i where [1) me (0, has n equivalence classes will be at most n 2. This implies
Lemma D.I is true if we let E'u)= (
(w), Vu E 1)
Now, we will prove an impossibility result for linear CFGs.
Proposition 3.5 ((Linear) CFGs only admit length generalization the limit). Recall RL-CFG is the encoding system for Linear CFGs defined in Definition 2.3 and CcFo((G)) the complexity measure that maps CFG G (N,T,P,S {0, 1}) to | + [T] + IPl. Then for any learning algorithm A, the length complexity, Recrs is not computably bounded. That is, Linear CFGs do not admit non-asymptotic length generalization (w.rt. standard CFG encoding system RCFG), and neither does the set of all CFGs.
Proof of Proposition 3.5. This follows directly from Lemma 3.4 and Theorem 3.2, with R. being encoding system which maps string encodings of linear CFGs to the corresponding language, F =R being the languages recognized by linear CFGs, and being the complexity measure described in Definition 2.3. Because RL-CFG satisfies Assumption 2.4, Lemma 3.4 and Theorem 3.2 imply that encoding system FR admits non asymtttt length generalization w.r.t. R, C iff the language equivalence problem for decidable, However, by (Baker Book, 1974), the latter undecidable.
21

---

Non-Asymptotic Length Generalization
E. Proofs for Length Generalization of C-RASP
E.1. Proof Theorem 5.5
Theorem 5.5 (C-RASP* Length Generalization). F= C-RASP and C(f) = max([al, (6], |d). defined in Definition 5.3.
Then VT N, we have (T) I O(T²). That is, the Minimum- Complexity Interpolator, with complexity C and function class F, can length generalize given inpuls of length (TT2) when the ground-truth has complexity T.
Proof. With integer T and integers a, b, E [-T,T], a > O, recall C-RASP1.2' is the set of functions of the form:
fa,b 1sa p=(x) - b
0]
By Theorem 3.2, it is sufficient to show that for any tuples of integers (a, b, d), (a', D. d)) E [-T, with a, a' >> 0, if there exists an æ E {0, 13 with fa,,a(z) # v. (x), then there exists an x' E {0, 13 with |a'| S O(T?) such that fa,),((z') + far (z").
Suppose there a string x that distinguishes fa and b, We can rewrite f and I' as follows.
b d
f(x) == fabdd()) (ps(2)
n
>
0]
a
a
b'
d'
f((x) = fo (x) = 1(ps(x)
a'
n
a
>
0]
Since f, differ on v, either _/2 + N. or but +
Case 1: + 6/
There are 3 categories for the value of a slope a/2 (resp. ))
Type (i): b 2 1 (resp.
6' a' 2 1)
Type (ii): & < 0 (resp.
o S 0)
Type (iii): b E 10, (resp. E (0, 1))
Below we will consider how to distinguish two functions f, f' whose slopes
b V. a a² are in each of the categories.
a is type (iii); 5 either type (iii). (ii), or (i)
For any two 2D lines y = 4 y - xx+ d- there is a lattice point coordiidan x, := |aa'l (2 max 1 I)+
1) that lies strictly above the line with smaller slope and un-strictly below the line with greater slope. This follows from the fact that when & * 1, then the smallest that 1/= _ can be |
I Thus, v å |aa' (2 max( ا 11 + 1) >
2 max(1 E, 1 1 so that [ + - E + _ ) 2 1. Because the vertical gap between the two lines at horizontal coordinate x, is at least there is a lattice point (x., y=) 2² with y+ (min 9x, d _x, $). max (x, + d 5xx + 4' ). In fact, for any x 2 Xx, one can find such lattice point with horizontal coordinate x, since the gap between the two lines will continue to grow as x increases for x 2 x., and so the gap will always be at least 1.
We want to pick such lattice point (x, y) subject to four constraints:
1. y < max x + d
8 + d' x d'
y min(? 0x
a
3. y S x
ý 2 0
22

---

Non-Asymptotic Length Generalization
Since _ E (0, 1), then it suffices find such lattice point either between y - a and y = 0, or between y = x + d and y 5 x d' a' For each of the 3 cases, any lattice point between the two lines specified in that case will satisfy all four constraints.
4 + d and y x, between y - -
By the argument in the previous paragraph, for each of the three cases, horizontal coordinate x,, which will be at most the following, across the three cases.
construct such lattice point with
x & max |lad (2 (ax( @ d' a. 1),la (2 max(
d (1.00 + 1), la 1 (2.11((2mm) (2mmx d 10) + 1))
a
< max( lad') + aa'
37
Denote the vertical coordinate of this lattice point as 0 S y S X. Finally, any string x' E {0, with |x'| = 8, consisting of y 2 0 ones and - y 2 0 zeros will distinguish f and f" This string will have length at most 372.
b and D' a are type (ii)
Since a * 5/ say WLOG that < 0.
a
5x If a' <0, 0, then after x coordinate at most T + 1, then lines = d y= 6/ d' n' go below y = 0 and no lattice point nonnegative coordinate can be below one but above the other (i.e. both S become the all-ones function on strings of length least T 1). Thus, any distinguisher of f. f (in particular, the presumed in the beginning of the proof of this Theorem) must have length at most T, and we take x' =
If 77 = O, then in the case 말 < 0, the same argument implies that |x|| S T.
In the case that 0. then a lattice point which lies between the two lines is (T + 1,0). Thus, the string x' 0r+1 distinguishes f, f and has length T + 1.
a is type (ii) and 2 is type (i)
The analysis of this case similar to the Types (iii) versus (iii), (ii). (i) case. One can take the line of slope 2 1 and modify just its slope be between (0, 1), apply the analysis in the Types (iii) versus (iii), (ii), (i) case attain lattice point which lies below the original line of slope 2 1 and above the line of slope < 0. Such lattice point corresponds to a string of length at most 2T which distinguishes f.
E' A and 7 are type (i)
Analogous the argument about Type (ii) versus (ii). There will be string of length at most T which distinguishes S.J'
Case 2: 6' but d * a' (i) versus (i) will suffice, where it must be the case that the string x which was presumed to distinguish f has length at most T +
d' If the slopes are at least 1 or at most 0 an analogous argument as Case 1, Type (ii) versus (ii) or
Otherwise, if both slopes are (0, 1), then we can take lattice point (x..y.) which lies on the one of larger intercept. Such lattice points occur periodically with spacing a < T, and we need only take one such lattice point where x. yv 2 0. We can find one such lattice point where x, 37.
Notation and Conventions. For the remaining sections. we will use lower-case æ to denote bit-strings in {0, 1)*
We define [k] {1, k -
the first ls positive integers.
We will use symbol / to denote functions in the relevant hypothesis class, like C-RASP DFAs. These will be mappings from {0, 1 to {0, 1}. We will sometimes refer to functions in C-RASPI and C-RASP2 as programs, which is synonymous with "functions." " We will say that two functions are equal they agree on all strings {0. 1}", and that they are unequal they are distinguished by at least one string x e 13. We will call such an x a distinguisher of the two functions. To be clear, the word function here has a distinct meaning and type from fest-funciions
23

---

Non-Asymptotic Length Generalization
We will use X' denote discrete test-functions and y' to denote continuous test-functions. When we say "test-function" without specifying whether it is discrete continuous, assume mean a continuous test-function. We will use (B;)))) (or (Be) when clear from context) to represent the activations induced by a continuous test-function (see Definition 6.6), We will use symbol Y to denote a schema of continuous test-functions (see Definition E.5). When we talk about a 2D coordinate system, in the context of test-functions, we will use symbol x to denote the horizontal axis of this 2D coordinate system and y to denote the vertical axis. To be clear, x is distinct from the symbol z, which we use to denote bit-strings.
Regarding geometric objects, denote cI(S) as the closure of set S. Denote S as the complement of set S. For a convex set S, the affine hull of S is the set of linear combinations of points in S. Denote dim as the dimension of the affine hull of S. Denote the interior of a convex set S as iS) and the relative interior of convex set S as ri(S), which is the set of points in S such that there is some non-zero radius such that the Euclidean ball centered at that point with that radius, intersected with the affine hull of S, is contained in S. Finally, sometimes we will talk about geometrical set in R$ and its "analog" in IR M, where M > A (what "analog" means, we won't ' go into here). Notationally, if we use symbol A E IR for the set in R., we will use symbol (M) to denote a set that's analogous to A, but in R.M.
A halfspace of IR is a subset of Rd which satisfy a linear inequality over the d coordinates of F4. polytope is the intersection of finite number of halfspaces. The polytopes we will be working with will be restricted to [0, 1] for some dimension d. The faces of polytope P c [0, 1]d refer to the d - 1 dimensional polytopes which form the boundary P. Each face is associated with linear inequality (halfspace) which defines the face in the sense that points on the face satisfy the linear inequality with equality. A d-dimensional simplex is a d-dimensional polytope with d + 1 vertices and d + +1 faces.
E.2. Proof of Theorem 6.1.
We reiterate the definition of C-RASP2 here.
Definition 5.4 (C-RASP*). With integers T and 1 < K < T2, let C-RASPa.K, be the set of programs of the following form. Each program f has parameters 0 < 2 S T. Vi E [K]. a (0) B0, E (-T...., ,T, with a! > 0. We require that for all i E [K]
(0, 1) and is distinct from a0
5
b(l") aGr for i' * i. We also require Σ{E(K] X; > 2.
For any n > O, on input x E (0, 13", the first layer computes the values of K heads, (h()) ]e[K]. on the n prefixes of a: {{r1] }, {21, .2)..... (ri,...,,z,, ,za} as follows: Vj E [m]. Vi h = 1/ps(x)) > g9 d. Subscript j indicates the value of quantity on the jth prefix of x.
The second layer computes the output, which is the rith bit of the final sequence: f(x) 1[Eie(K] App(h((),, n...
Then, C-RASP2- = -USTTIKKST C-RASp2KK.T Given a function f E C-RASP2, let K(F) be the number of heads, (6)) in the first layer of f and let T(f)= = max(max;e(K(n)) |a max{e[K([) [B0)| max [Ad), [z]). The complexity measure is C(f) = ((), the precision of the function's 's parameters to the power of the number of heads.
We will prove the following length generalization guarantee.
Theorem 6.1. Let F C-RASP2 and C(f) = K() as in Definition 5.4. Then Vo E N, Na S O())
Note that Theorem 6.1 is actually stronger than a result which says that we can learn C-RASP2,K, with length ((T))))). This is because for a fixed T and K, C-RASp2.K.T only contains functions of precision at most T' and at most K heads, whereas Theorem 6. 1 also provides length generalization guarantees for C-RASP2 functions f with T(f) > T, K(f) K or T())= < T, K() > K such that k() < TKk
Proof of Theorem 6.1. By Theorem 3.2, to upper bound N Ammii(a), it suffices to bound:
minfn E NN: E C-RASP2 with C(f) S a, exists I E (0, s.t. f(x) # f()))
Suppose f. E C-RASP2 are not equal and differ on zo E {0, (0,1)* For any n > O, suppose f and f' have the following 2-layer form on an arbitrary input E (0, 1)m
24

---

Non-Asymptotic Length Generalization
b(,)
fA Vj [K], (x) (ps(()) a(1)
f(z)= 1 Σ {ps((h (2)) > n.
kE[K]
(bily
fj [n]. We [y)) (11))(()) 1[ps(x))
(atoyr:)
= - Σ Xps(( > z'
KE|K
Where has K first-layer heads and integer parameters of precision T and f" has K' first-layer heads and integer parameters of precision T', where C(J) = 7 I a and C(²)) (TT) S a, and K I T and K' (T"), WLOG, suppose that T' 2 1". We will find short string x, {0, 1] o()) such that f(x+) + (x.)..
U Taby hejay (0, 1) between the first layer of f and f has size k where max(K, K, K') & k K + K'. We will denote R = {sy]jem C (0, 1), where $1 the largest slope and sy is the smallest slope, and the slopes are sorted in descending order so that $1 > ... > 5k. Let (I, [K] + [k] be the index
b Suppose the set of unique slopes R == a Ne(
y
within R of the ith slope of ato. Let ord(2, i) [K'] + [k] be the index within of the ith slope of f", (B6t
g60)
(a In the
following exposition, we will refer to "line i" as the homogeneous, 2D line s;x, with slope s;, i [k].
Definition 5.4 requires that 2, 2 > 0, and that [ig(K] A; > 2 and [igjke X > z'. Since f differs from f' on discrete test-function given by Tg. then the non-trivial Lemma E.37 implies that there exists a continuous test-function ) that induces activations (Di)...... BB (Di)) which satisfies either Case or Case II.
Case
Σ iE[K]
de (add(1.a)))) and KE(K*)
Σ
X (od(,, <
Case II:
Σ KE[K]
Bad (Di) < and
Σ
(
For the remainder of the proof, we will suppose Case is true. The proof for Case II is entirely analogous to what we will present below, since we will not use the direction of the signs of the two halfspaces in the following proof. Denote the two halfspaces induced by the second-layer of f and I' by H, and H2 respectively.
H1 :1 11:=(EER)
Σ X Bod((1.) > =}
SE[K]
(B== Σ
X(Bod(2,5) < <x)}
SE(K")
By Corollary 1.14 (Completeness of Basis Schema), there exists a continuous test-function )12 of basis test-function schema, Y. specified in Corollary E.14, such that ()a), Ba()2)) (D))),..., Thus,
(.(),...BB(())))) e Hi Hz
25

---

Non-Asymptotic Length Generalization
Let M be the number of segments in the basis schema Y of V/2. Note that our previous application of Lemma E.37 guarantees that Y is basis schema of either one monotone curves (see Definition E.9), ensuring that
M S 2k
(I)
as opposed to the naive bound of M & 1.2 via Corollary E.15. This fact will be useful at the end for achieving a better final bound.
Denote the lengths of the M segments of schema Y (n...... (2.)) E [0, [0,1]M, Let (Y) be the of valid segment lengths (n1...., Rar) for continuous test-functions of schema Y. where particular setting of (Ma....,, aM) is valid if it obeys the constraints described by Lemma E.6 for schema Y and Cie(ar] 1.
(V) = {(11,...., nM): : valid segment lengths of schema Y and
Σ M
n4 n= [0. 10.
Additionally, define A(Y) as the analogous set to (Y) in the space of activations rather than the space of segment lengths.
A(Y)= = ((Bi()),..... B&())) y valid test-function of schema Y } C [0, 1]
There exists a linear map R -> IR. which maps points in A(M to points in A(Y). {0, 1) is such that Lij =1 1 - segment in schema Y lies above line (that is, for every in the domain of segment j. the y-value of the segment at least 8; x) and hence contributes the ith activation ()) of any test-function y of schema Y. Using L. we can rewrite the incqualities which characterize H1, H2 in terms of (Ri...., RMM.
K A Ban((1.)) >) = nM) ):
K
H|M) = {(n1..................... nas)
A
Σ
n2 1
2}
t=1
j st. 11)
K'
K'
( = ( aM) Daarre <22}
Σ
X
Σ
R2 < <2}
j S&L 10
Since (Ai)) z are integers most T in magnitude and (A))sE(KY) x' are integers at most T in magnitude, the coefficients of the linear inequality for (M) (resp. H(M) ΣK de Ej 11 ny (resp. Em= E Luwa n3
2') are integers of at most KT < T (resp. K'T' S (TT))) in magnitude, since for each j E [M], at most every i E [K] (resp. i E [K')) can contribute to the jth coefficient.
Now, we describe few more properties of (Y). Suppose the segment lengths of V/2 in schema Y is (n, (J2),..... (M), e [0, 11M Then, we have:
e AY) n H n H. (M) +
By Lemma E.16 (Y) is polytope: the intersection of a finite number of halfspaces. It follows that (M) ) convex. Moreover, by Lemma 1.16, we have dim(A(M)())) M 1. Because ( (M) n H (M) + 9 and H (M) H (MM) are open sets of dimension M, then by Lemma E.27, (M n H((M) (() (A()
M 1
We have that cl( cl(A(M) (M(M) n H()) is the intersection of a finite number of halfspaces. Each face of the polytope cl( (((A(M)( H M) M) is defined by one of these halfspaces. We now discuss the precision of the linear inequalities
26

---

Non-Asymptotic Length Generalization
which define the faces of cl(A(M) H n H, where precision of an linear inequality with integer coefficients the maximum magnitude of the integer coefficients, per Definition 5.2. The linear inequalities of the halfspaces which form the faces of A A(M)( (Y) are such that there is a subset of at most 6K of them with precision at most T while the remaining faces of (Y) have precision at most (T*) This is due to the following argument. First, because the (k, T) configurrrai {s; ) jejs]] is such that there is subset of at most K of the & elements of {&i [E())) which are precision at most T, while the rest of {st)ejkk are precision most T', Next, referring to Lemma E. the only faces of A (Y) with 2 precision are ones that correspond to segment of Y whose start-point end-point is on one of the K lines of slope whose precision is T Third, by Corollary E. 1.14, any basis schema of one or two monotone curves will cross each of the k lines at most three times. Since each of the (at most) K slopes of precision T correspond to at most 3 grossing-points of Y with that the line of that slope, and each crossing point is adjacent to at most two segments of Y, then there are at most 2 2-3K segments of Y such that the start-point or end-pont point is on a line of slope that is precision T'. Thus, at most 6K of the faces of A(M (Y) are defined by linear inequalities of precision at most T while the remaining faces of (Y) are defined by linear inequalities of precision most (T Note that the square (i.e. in T and (T*)2) comes from the form of the inequalities defining the faces of (Y), stated in Lemma E.6. Finally, argued in carlier paragraph, the face given by H|M) has precision at most T while that given by H/(²) has precision at most (T In summary, there is a subset of at most 7K faces of cl (Y) H[M) n H{ such that each face of the subset has precision at most T while the faces not in the subset all have precision at most (T') In short, we ve shown that polytope cl(A(M)(Y)) n H((M) n ()) satisfies the pre-conditions of Corollary E.21, which we will apply in the next step.
Now, we return to the process of converting V/2 into a short distinguisher of f. Let V denote the set of vertices of the polytope cl(A ( H1 (M) n H²()) Let e E [0, M be the average of the vertices in V.
Σ x
==
V
PEV
Label the coordinates of e as c:= (n1 1 ....., n
(e)) c is in the relative interior of cl cl(A(M(()) HMM) n HH(D)) (which is
non-empty by Lemma E.25) so that c E A n nH(M)
(M) n H M), In particular,
Σ
(c)
n
>2
I 5... L =1
K'
Σ
n
(c)
<2''
1=1
L ()
=1
We will now lower bound the margin (see Definition 6.10) of to the faces of (((((M)())))))))))))) ((())
M)) which includes the faces given by (M)) (M) Suppose (1(440) (Y)(e n (M) n (H( has N faces, and let {LiheEN; denote the linear
inequalities which define each face of cI(A(M(()) n H (M) n H)))),, so that La(c)= E IR is the non-negative margin of c on the ith face. Noting that M s 2k < 2(K + K'), we apply Corollary E.21 on polytope cI(A(M) (T) n H (M) n Hr! ()))))
get the following lower bound on the margin of e on the faces of cl (Y)() ((M) n H)
Vi L(Cc) 2 2 1
V oay
Then by Lemma E.22, we have |V| < 3M2, we deduce that:
Vi [N]. L(c) 2 Ω 1 1
M )0())
27

---

Non-Asymptotic Length Generalization
In particular, the margins, 71, 72 of e on the two inequalities defining H and H2 will be least:
K
(0)
n
I Loat( 19)
1
1
2 Q
2 )
K'
Σ
(c)
==
nj
j st L.d( =1
2 0
M o01)
Now that we have shown that has large margin, we need to augment it one final time before converting it into discrete test-function. This process will find nearby point E Ball," (c) n {Eie(M) R4 = 1} = { E R
[I(11...... nM) c|l I r) n (EiEt n, 1} such that c, has both large margin to the faces of cl(A(00 n H M) and low-precision coordinates. With ||4/|| denoting the sum of the magnitudes of the coefficients of the linear inequality which defines the ith face of cl(A((0 (Y) n (M) ( n nH, (M))), let:
YLB = T T(M
S 71,179 72
YLB
r = 2- [ [N]
|,1h]
By linearity of the margin of point in its coordinates (ni,.... nM), each point d' BBlll [EieM] n; 1} will (M)
have margin at least YLB r max |||||| 2 ILE to each face of cI(A(M) (Y) H()) n H (1)). This also means (M)
2
that every such d' is contained in AY)) (M()) n H YLB O.
By Lemma E.29, there exists a low-precision point c, E Ball, (c) n [ (c) n = 1), denoted c, := (m (c.)
n (c.)
)
M
such that for all E [M] n/c)) is rational number, and the least common denominator of all elements in the tuple
(n(c)) (c.) ,..., na (e.)) is Po.. where:
Pe. S [M [M. -11
s OM max ||.]]]] [3M2a iE(M]
< 0(33 (MM)7)).. a00)
Let the tuple c, = (n) (e.) has positive margin - to all the faces of cl (l(A(M((Y) HM(M), n H(()) and is contained in (AM) n H(()) (M) so is valid setting of segment lengths of schema Y. respecting the constraints of Lemma E.6.
) be the segment lengths of the continuous test-function V, of schema Y. Note that c, nM
Finally, applying Lemma E.24 on the continuous test-function of schema Y with segment lengths c. (m/( jE[[) we deduce that there exists a no I O(e,, a 0(1) so that for any integer multiple of no. there exists a discrete test-functie function X. (O....,,) n + {O...., n.,, of length n, corresponding to string x. E (0, 13" of length n. such that
T M
Wi (BL.) B.(x.)
28

---

Non-Asymptotic Length Generalization
Where (B)()))) are the activations induced by V/,, a test-function of schema with segment lengths (n (n:-*) ( (E(M)) and (B)(() the activations induced by X. Because Vi, |A,] S T, [X]] S T" S I' then the difference between the margin of (B:(2)))ee and (B)(E) on H1 and H2 can be bounded by a term proportional to +.
(e[M))
K Xg (ord
Σ
X B o,
(X.)
(2)
K
S (max [B:().) - B,(x,)))
max
Xc)
(3)
[k]
(7 + M)KT
(4)
0 KMT
(5)
Using analogous argument, the difference between Σ X (add).)) and Σ X (X,, is also bounded by an analogous expression.
K'
K' (D.) Σ X. S S0(
K' 3
Together, these imply that for sufficiently large n, the difference in the margin of (B; )EER and (B:(I)))sEI) on Hi and H2, caused by the discrete test-function approximation, will be smaller than the margin of (B.())))e(() on Hi and H2. The latter equals the margin of e, on HT(M) and H((,) by the definition of H((M) and HM( as the analogous halfspaces to Hi and H2, which is lower bounded by 24 More precisely,
KMT
A B.,)
2
TLB
2 0
K'
K' K'M
(z) <
TLB
+ 0
2
To this end, since 7LB = -2( ( ), it suffices for n to be the following value in order for activations (B,(X.) )EEM induced by X. to be in H, n H2 (and therefore to cause f and f' to differ, as 1/1 and y. do).
max (K, K'MT3 O M2 (
20 - n O(M max (K, K')
(6)
n
Let I. be the string of length corresponding to X,, which uniquely determined by X., For n max(1 + 3 max(K, & Ope. o()))) will be sufficiently large make the approximation error smaller than the margin of e, per Equation 6, and also satisfy the condition required to apply Lemma E.24 in the previous part of this proof. Thus, with this value of n, will cause fxx.) 1, O.
We noted previously in Equation (1) that M < 2k < 2(K + K') for the basis schema Y as a result of Lemma E.37.
Plugging this in for M, and noting that a 2 max(T (TT) k'), we conclude that the length such an x' distinguishing f. f need only be at most
29

---

Non-Asymptotic Length Generalization
n max O(M max (K, K')T"a00) Olpe.
max(1 + O(M max K, K" " ),)), O(M ( 011) . )))))
(ia (())
E.3. Lemmas for Completeness of Basis Schema
Goal. In the main proof, we will fix two arbitrary unequal f. E C-RASP2 and prove they have short distinguisher. The goal of this section is to prove that the of realizable activations (())))eea)) equals the union of the set of activations of small number of basis test-function schema. This culminates in Corollary E.14.
Basic Definitions. Recall the definition of precision.
Definition 5.2 (p-precision). An integer of absolute value at most p is of p-precision. rational number between [0, 1] is of p-precision if in simplest form, where the numerator and denominator relatively prime, its denominator is most p in magnitude. A tuple of rational numbers in [0, 1] is precision if the least common denominator of its entries is most p in magnitude.
Note will say halfspace defined via linear inequality with integer coefficients has p-precision if each coefficient is at most in magnitude.
Suppose f and I' have and K' heads, respectively, and consider the set of max K, K*) < k < K + K' distinct slopes from the parameters of the first layer of f and f": ( ]EE(K] U (a HEeK" Disregard for now which slope belongs to f or to f', and denote these k slopes as (8t heeM)] (0, 1), sorted descending so that $1 is largest and sy is smallest. We will refer to [EEM) C (0, 1) as (k, -oooffiguuraii.nn Definition 6.4. (ks, conffigguaa
(B
of distinet T-precision rational numbers (siHE) (0.
These & slopes {st (ejR) specify & homogeneous, 2D lines, of the form y 83 Denote these lines 4...., la with line I; having slope s; for all E [A]].
Recall the definition of Discrete Test-Functions.
Definition 6.5 (Discrete Testt-unction). Given (k:, coonfiiuurtn (st (Ea)) a discrete test-function X,, with respect
(E and of length < co, is a function (0, ... n + {0, ..,., where x(0) 0 and V E [n]. X(i X)- or x') = (j - 1) + 1. The induced activations (B, (X),... (x)))) of X with respect to the (k, (), confiigratiin are
defined as: Vi E [k]. B, == E ([x()) s4 -]]
For string E 10, the discrete test-function induced by x is the set of 2D points ((())s(()))) bjjj(ll where we will associate the y-axis for pz()); and the x-axis for j.
Recall two central objects: continuous test-functions and A(fs)tee))
Definition 6.6 (Continuous Test-Function). Given a (k, comnooiiiuutttnn {st [si)e continuous test-function V. with respect to {s; ]ve[s]. is 1-Lipschitz, monotone non-decreasing continuous function [o, 1] - [o, 1], with (( = 0. Continuous test-functions can only intersect the lines (1i)e of slopes given by (*t [ai)ee)) at finitely many points. The induced activations (Bi ())). (2)) of y w.r.t. {si)aets) are: Vi [k),, B,()") Jo 1P() 8; j]dj-
Definition E.1. (A((s:)ee()) Given (k, configuuraaioo fs define (({s:)ve(n) the set of activations induced by continuous test-functions with respect {S)))
A ((silie()) ((Bi))).... ..... B&())) continuous test-function w.r.t. (sihel))
Regarding properties of continuous fest-functions, first note that the scaling of y can be set WLOG because of the homogeneity of the ie lines. Thus, we let their domain be [0, 1].
30

---

Non-Asymptotic Length Generalization
Second, for any continuous test-function y, we can let the end point of y be on one of the lines (4))et))) Suppose the last line crossed by Y/ is 4-- Then we can adjust the segment of y between its last crossing point at 1 and its endpoint so that the endpoint is also on line 4, We can make this tweak so that no other lines (e A are crossed and so that (Bi()),... B& ())) remains unchanged by this tweak. In short, the endpoint of any continuous test-function y is. WLOG, (1,8) where 1 is the last line crossed by y.
Lemma E.2. For any configuration {si)eel)) for any continuous test-function y w.r.t. {8i) suppose the last line H4Jiem crossed by y is L6 for E [k]] Then, WLOG, we can let Y's end point be (1,8;) without changing the activations induced by y.
Proof. Suppose that the last line y crosses is 1 at the point (x, St x). Then, the portion of y on the interval [x, 1] is wedged between either the two lines and 1,+1 or the two lines I and 1,-1, since y will not cross any other line on the interval. The quantity of interest are the activations with respect to the k lines induced by y/:
Vi (.)) = ['' 1D'()) > 8: -5ldj
Suppose that Vj E (x, 1], 8:j > V()= > st+1j. The ht quantities (B;())))s(()) will be unchanged we adjust the values of ()) for j E (x, 1] so long as we retain that Vjj E (x, 1], sij > >)(i) > 51+1] except on a set of measure 0. With allowed to be any continuous function with slopes in [0, 1] and with 8; E (0, we can adjust }i() to stay between lines 4; and 4+1 but closely follow the line in the sense that (3'G) scjl > 0 can be made arbitrarily small at all points j E (x, 1), and (11)= 8; (note, this end-point (1, s:) violates the condition that s,j > )())= > 8:11 but only at single point). This ensures that the modified test-function, call it J", is such that Vi E [k], B())) = B,()")
Suppose that Vj E (x, 1|, 8;-1) > V(j)= > stj. Then an analogous adjustment to y()) on the interval j E (x, 1] can be made so that the endpoint (1).
From now on, assume that each test-function will have starting-point at the origin (0, and have end point on some line 4 (4.....,42) 4. at point (1, st). This will make the following definitions about segments and schema cleaner.
Define the span of continuous test-function as the set of lines in (4 which the continuous test-function intersects at some point.
Definition E.3. The span of a rest-function is the set of lines (4,,.... 1 that the test-function crosses at least once. That is, y crosses 4 if there exists x where (x) = 8, x. Note that the span must be a contiguous subset of [k].
We'll also give names to the regions of the positive quadrant of the 2D plane between consecutive lines in [4:)eek)) Definition E.4. (Sectors) Given a (k, c))n-))iguaatiion {s; he(k), a sector is region of the 2D space between two consecutive lines. Define Sector, as the sector strictly above line l1, and Sector as the sector below line 4g. For i E f2..... k} define Sector; as the sector below line 4-1 and strictly above line 1,
Sectors are depicted in Figure 7. We'll now define segments and schema. Definition E.5. (Segments and Schema) Given any (k: T) configguuati (s.hveta C. (0, 1), define the following.
1. A segment is a restricted test-function S: ja, bj + [0, 1] where (a, 6] [0, 1] which maps a continuous subset (a, bj to [0, 1]. S is 1-Lipschitz and monotone non-decreasing. The segment's 's start-point (a, S(a)) and the end-point (b, S(b)) each lie on one of the & lines, in the sense that there exists some i.j E [K]] where S(a) = and S(b) = Sj b, where j=j or j - jl = 1. No other points (x, (()), x E (a, b) can lie on line 4,...,,s. 1s-
2. A schema Y is a blueprint for a continuous fest-function, specifying sequence of lines (4) that any test-function of the schema must cross. It consists of an integer 0 < M < co and two tuples (idx(i) [e[M)) C [K]M, (sec; C
Ik + 1|M, where lidx(i)= idx(i + 1)] < for all i E [M - 1]. If [idx(i) idx(i + 1)] = 1, then sec;41 is unique and must be max(idx(i)) (i), idx(i + 1)). If idx(i) = idx(i + 1), then sec,41 can be either idx(i + 1) or idx(i + 1) + 1. sec; can be either idx(1) or idx(1) +
Any continuous test-function of schema Y = (fidx(t))xe[M)) (sec) consists of exactly M segments S1, S2...., Sas whose domains are a partition of [0, 1). For each [M], the ith segment S,'s 's end-point lies
31

---

Non-Asymptotic Length Generalization
ps(x)j
4
l2
l1
4
4s
Seg. #1
Seg. #2
Seg. #3
Seg. #4
Figure 2. Depiction of a Test-Function consisting of 4 segments. y-axis shows the prefix sum of input string x-axis shows the length of the prefix imput string z. The five lines have slopes (......, ss). Sectori the portion of the quadrant which is above 4, Sectorg the portion of the quadrant below lg. For 2 S i & 5. Sector, is the portion of the quadrant below 4--1 and above 4.
on (ax(t)- For > 1. S,'s start- point lies on line (1)(i-1)- and S₁ 's start-poing is the origin, (0, 0). In addition, the ith segment must be contained in Sector
Notationally, we denote n, E [0. 1] as the length of the ith segment S, but note that different cist-funciions of the same schema may have different segment lengths [nsJeetM) subject to some constraints we detail below. For schema Y, denote
A(Y) : ((BOO). B&)O)) continuous test-function of schema Y w.r.t. {sshe
Figure shows test-function of schema with segments. Figure 7 shows four generic types of segments.
We will think of schema list of M segments, for some M 0. We will denote the length of the vth segment n,, Let idx(-) be the mapping from [M] to [k] that gives the index of the line that segment i's endpoint is on.
For continuous cest-function, the first segment of length has start-poing at the origin, (0, The last segment of length i-1 nM has end-point which lies on the line ((x(M)) The ith segment has start-point (Ej=1 ny $ax(i-1)) ΣE= n2) on line hax(i-1) (as long as i 2 2) and end-point (Ej=1 Nij Sidx(t) Σj=1 mı)) on line hax(s) and has length There is freedom in choosing [n.]sE[M], so long as they satisfy the following constraints.
Lemma E.6. For any segment in any schema, the constraints given Definition E.5 exactly characterize the range of values allowed for that segment. For all E [M], these constraints are:
(Segment Starts and Ends on Same Line) If idx(i 1) idx(i) 1, the only constraint on the segment's length
32

---

Non-Asymptotic Length Generalization
ps(x))
ps(X),
Sector;
Sector,
Sector>
Sectors
1
Sector;
Sector,
13
Sector,
Sector,
Figure 3.
Figure 4.
Start-point on 4, End-point on lz.
Start-point on l,, End-point on 1
ps(x))
ps(x))
Sector,
4
Sector
4
Sector;
Sector;
4
4
Sectors
Sectory
1g
4
Sector,
Sector,
Figure Start-point and End-poin End-point on 12, and in Sectorg.
Figure 6. Start-point and End- End-point on l2, and Sectors.
Figure 7. Four types Segments, based on which lines their start-point and end-point lie on, and the sector they in.
n; 2 0.
(Segment Crosses Down) Ifidx(i - 1) = idx(i) - and 2 2, then The 2
Sit((-11)
-
-
n4
Sate(s)
(Segment Crosses Up) Idixx(i - 1) = idx(1) + 1 and 2 2, then n4 >
S1b(1-11
1) m2.
1)
1-8wete
Proof. Case: Segment Starts and Ends on Same Line. For segment with length n,, if (ixidxii-a - 1) idx(t), then can be any nonnegative number. This is because for each n1,..., 74-1 and for all n; 2 0, there exists a segment of length n, that crosses line idx(i) at the sart-ppoint (Ejsi- ny. Six(() E Ejst-1 n2y) and end-point (E, ny, Siax(s) Ejss nz) and nowhere between. An example of such segment one which stays arbitrarily close the line (xx(()) but doesn't cross until the end-point (Ejsi Tej. Six(() Ejs; n2)), which possible since each line has slope in the range (0, 1) while the test- cest-function can have slopes each point be in the range [0, 1].
Case: Segment Crosses Down. If idx(i - 1) idx(i) 1, then for any Ri,...,, 71-1, the minimum value of in terms of . 74-1 is achieved if the segment has slope of 0 at all points, the "minimal segment", which will let the segment cross lines 11x((-1) and lixx()) most efficiently. Such a minimal segment will cross lines hax(i-1) and 4xx()) at start- start-point (Ejši-1 ni:; 1i)((-1) E n2,) and end-point (E, nz, 8ixx(s) Ejs, n2)). respectively. The value n, required for this minimum traversal can be calculated by:
33

---

Non-Asymptotic Length Generalization
(idx(1)
jjj = 8) 1)
T2j
==1
y=1
11]
1)
Σ
n2
Sidx(()
j=l
The first equation follows from the fact that the zero-slope trajectory will enforce that the y-coordinate of the start-point of the segment 1)) 1) Σj=1 n equals that of the end-point Sidx(i) Σj=ı Mj. Having n, be any smaller will not suffice to make the crossing, under the trajectory of the minimal segment (where the slope is 0 everywhere) and certainly under any other trajectories.
Now, having n4
( - 1) E}= ny is always possible, since the segment can always follow the trajectory of the 0 to closely follow line idx (i) until crosses it at the designated end-point, (Ejs² nij Sidx(t) Ejgi ny)- The latter phase reduces to the case where
Subc(s)
minimal segment to cross to line idx (i), and then use the extra slack, n1 Puaati 11
1)
E
Sit(f)
idx(i - 1) - idx(i). Thus, the allowed values for ni are TH Pan(()
Siari=11 1)
プj ng-
The setup of lines and [0, 1|-slope test-functions has "reflection" symmetry about the line y y= 1.x. Thus, the argument for the constraint on values of for the idx(i - 1) idx(i) + 1 case reduces to that of the case idx(i - 1) = idx(i) - 1, except with "reflected" slopes 1 Sixx(E-1) and 1 - (ax(()) Plugging in these reflected slopes 1) E
Case: Segment Crosses Up.
into the constraint for the Cross Down case yields n, Patcc-111 T-
Another way to see how to derive the constraint by considering the minimal trajectory one where the segment has slope 1 everywhere; and arguing that n, can be anything larger than the length required by the minimal trajectory.
i-1
(1 (1xx(1) )z = (8idk(1) - 8sdx(i-1)
11)
==1
1idx(i-1)
74
1)
8)dx(()
1=1
The first equation above is derived as "Object I of relative speed of (1-9)dx(i) 8jdx(i)) to Object 2 takes n. time to close the initial
gap of (Siax()) 1))((-1)) Σ nz."
Partial Test-functions and Monotone Curves. We'll now define partial test-functions, which is slight generalization of continuous test-functions where the start-point does not need to be (0,0), which will be later in the later proofs. Definition E.7. (Partial Continuous Fusctiunn) Given a (ks, T configguuati (salee(M), a continuous dist-funtiion y is partial if allowed to have a start-point at (M1, 8i, m1), ), n1 [0, 1), E [k), instead of (0, 0). partial test-function undefined on [0, n2). The induced activations (B)))...... (J)) of partial continuous test-function given slopes (sihee C (0, 1) are defined as:
Wi E B((D) = / 120) > 8: ildi
nn
Schemas partial lest-functions can be thought of as a schema a continuous test-function. We will still denote the lengths of the segments of the schema as (mi]eeм) for some M > 1, except that the test-function undefined on the first segment's domain [0, n1).
Note that by re-scaling argument, due to the homogeneity of the i lines (4))et this definition also captures continuous test-functions where the start-point does not need to be at (0, 0) and the end-point need not have x-coordinate of 1.
We'll Il define type (I. k) and (II, k) partial fest-functions, which are particular partial fest-functions whose start-point is on a line whose index is either the smallest or largest element in the span of the fest-function.
34

---

Non-Asymptotic Length Generalization
Definition E.8. (Partial test-functions of type (I, k), (II, k)) Given (k, cconfiiuraann {*)eet)))
Define type (I, k) partial test-function a test-function [0. 1] [0 that is undefined on [0, m1) for some 0 S Ri < 1. It may span any consecutive subset of lines {a..... b) C 21, 1,K],a < b. With this span, we require that its start-poing is at (M1, san1), that it is I-Lipschitz and monotone non-decreasing, and that it can only intersect the k lines at finitely many points.
Define a type (II, k) partial test-function similarly as test-function [0, 1] + [0. 1J undefined on n1). It may span any consecutive subset of lines (a.... 6} {1, ..... ... k - 1, k, b. With this span, require that its start start-point is (N1, s5m1), that it is 1-Lipschitz and monotone non non-decreasing, and that it can only intersect the k lines at finitely many points.
Note that for both type (I, k) partial test-functions, if the start-point is on la with a > 1, then its span cannot contain 1 and it cannot intersect l at any point. An analogous observation holds for type (II. k) partial fest-functions.
We'll describe one primitive (partial lest-function) schema that will be important for our basis test-function schema later: monotone curves.
Definition E.9. (Monotone Curve) Given a (A: 2) coonfigurain {s]]e(s)) we define two schemas: Monnotone Up Curve and Monotone Down Curve. Both schema have + 2 segments.
(Monotone Down) Begins at line 1 (n1, $1 n1), goes above and recrosses line at (n1 + ng, $1 [m] + n crosses each intermediate line (2...., h 1} once, then crosses line twice at (Eiz) n,, 8k: Ei=1 n;) and (Eiz) R4; 8k n.).
(Monotone Up) Begins at line k at (n1, Sk n1), goes below and recrosses line ks at (n1 + n2, Sk In + nzl), crosses each intermediate line once, then crosses line 1 twice at A++1 n4,
k+1 n:) and (Et+ n4y $1 E n2).
k+2
Note n1 E 1) denotes the length of the first, "emply" segment on which the test-function is undefined; there are k + 1 nonempty segments. WLOG by homogeneity of the k lines that Σ n. 1.
Remark E0 Test-functions of the monotone curve schema are monotone in the sense that they don't re-cross lines which they previously crossed, except for line and line
Remark E. 11. Type (I, k)), (II, k) test-functions are strictly more general than test-function since we can just set n1 0 to recover the usual fest-function definition. Type (I, k) test-functions start on the top-most line while (II, k) test-functions start on the bottom-most line. Monotone Down Curves are Type (I, k) while Monotone Up Curves are Type (II, k)
Rearrangement Lemma for Monotone Curve.
Definition F. (Equivalence) Define two partial test-functions as equivalent if both test-functions have the same start-point, end-point, length, and induced activations over the k lines.
We will now introduce a central Lemma in proving that a certain set of schema is complete. This Lemma is about rearranging a test-function into an equivalent test-function with a simpler schema.
Lemma E.13. Given (ks T) -oooffigurat (st (ee). suppose type (I, k) test-function (resp. a type (II, k)) has its start point on line 1 and end point line k (resp. start point line k and end point on line 1) and spans lines [1,..., k). Then there is an equivalent, monotone curve of the same length, start point, end point, and that induces the same (B (BI.... BB)-
Proof. We will only prove the conversion of type (I, k) test-function to monotone (down) curve. The conversion of type (II, k) test-function to a monotone (up) curve is an analogous argument with effective slopes sf = st, Vi E [R]]
Suppose the type (I. k) test-function, y. has M segments of length ..,..., n.M, where n. is the x-coordinate of the starting point of y. Consider a monotone line ()(M) that, like V, starts at (n) $1 - ni)) and ends at (>M 1 n4, 8g E n2). (MM) comprised of l + 2 segments of length n/. né...... n2g. n' nle42 (where ne is an empty segment, denoting the coordinate of the start point), calculated from 01.-.. RM as follows.
35

---

Non-Asymptotic Length Generalization
n/ n1
Vi [k 1], n1411
Σ
ny
(e........ Jeny SSector,
First, we must show that this "rearrangement" forms a valid test-function that meets the constraints that would be enforced on ni, mé..... Thg 4 1s 242 described in Lemma E.6.
First, the only constraint on n² and +2 is that they must be nonnegative.
Second, Vi E k3.k- 1). the ith segment traverses sector and must eross from 4:22 to 4-11 By Lemma E.6, the following constraint is satisfied iff this crossing is possible:
81-2 n
n
8i-1
We would like to show that (n()xe(k=2) meets these constraints. First, Vi [3, k 1], define j: == max [j E (2, (2.3.... ..... M): Nj crosses 1 as the index of the last segment where y crosses Sector; starting on line 4-2 and ending on line
4-11 Then because the curve ) is continuous and its endpoint is on line k, then ji is monotone in i: ja < 14 < < jk+1. Then,
n1.
E
n3
12........o Jny ESector,
Djj.
just the last segment crossing Sector,-1 suffices
(+)-1
81-2
1)
Σ
n2j
8:-1
ji-1
81-2
1)
nl
monotonicity of ja
8:
8--2
Σ
n
8:-1
ny EU Sector
8
1)
m
8:-1
Thus, the monotone curve ((M) is valid monotone test-function. ()()) has the same length as 3 since it just rearranged the segments while preserving their length. )o(A) starts at line and ends at line k. and it starts at (n1, s111) just like ), so it must also end at the same point as (MM) on line k. (M) induces the same activations (BI..., Bb) as y' since the rearranged segment lengths stay in their original sectors in (MM)
The proof for type (II, k) test-function analogous.
Basis Schema. The following is the main result of this section. says that the following finite set of basis schema is complete, in the sense that any continuous est-ffuntion is equivalent some test-function whose schema is one of the basis schema.
Each basis schema described below is indexed by integer m E [k] and set of m tuples (ví v2) hiemm] C. {l, k }m These m tuples parameterize m 1 monotone-curver that, when concatenated, yield the schema. For i E [m - 1). the ith tuple (vi vτ)) E [k]] indicates that the ith monotone curve in the schema will have start- point on line y and end-point on line 2 The concatenation of all m monotone curves yield the basis schema.
36

---

Non-Asymptotic Length Generalization
Corollary E.14. (Completeness of Basis Schema) Given (k, T) -configguratnn (at for any 1 S S ki say that the list of tuples {61 ve(m! C (I,.... k) m is valid if they satisfy the following.
1// = 1/2
Vi [m 1).0i $ V/2
Vi [m 21 vi y/2
3/2 =vit1 1/2 > yi
Vi [m 2), v1 > v/ = w = witt < 1/2 1+1 < vi
(vi v2) (1, k) or (v1: w22 = 1k
For any m [k] and valid {w11 he[m], define the basis schema, You we)mm the concatenation of monotone m 1}, the ith monotone curve has start-point on line y [k] and end-point on line v2 E [k]. The
curves, where for i E 1m-
1st monotone curve has start-poing at the origin, (),0).
Then, the set of basis schemas over all m and valid {(vi: vé)m satisfying the above is complete the following sense.
A((ss)ie(H)
U
A(Y(in) (i)lemm))))
velk) (lt..V (i)lec)m
Where A(Y (6s) vetmm c [0, 1] denotes the set of (BI...., B&) induced by any test-function of schema ((i velmet Finally, note that the number of basis schema with respect to (silke(m) N₂ 2=-1
Refer to Figure to get a sense for what the basis schema look like. Note that the y axis of the figure shows the normalized prefix sum. Also, Figure is a depiction of the Completeness result for the case where 2.
Proof of Corollary E. Recall that A ({x Hetp)) and A(Y((vt ((vf. wille for schema Y(vi wa)lest defined follows.
(VVl (BB()),..... B&)))) continuous test-function of schema Y(ot (ott-)))em w.r. {si)se(H)
A A({s))e))) == ((BI())..... (x)))) continuous test-function w.r.t. {siheen)
First, because every test-function of a basis schema a test-function,
A A({x))E()))
U
A(Y ((ot-a)))e))))
valld [(v) heetm)
It suffices to show that the converse inclusion holds.
A A(()))e)))) C
U
A(Y A(Yio)) (1o (h)lt)))))
malk) {(v] hectm
To do this, we will prove that any arbitrary continuous test-function can be converted into an equivalent test-function (in the sense of Definition 121,), but which follows one of the basis schema. This conversion process is done via Algorithm 5, which partitions the input test-function into pieces, and then uses Lemma E, 13 to convert each piece into a monotone curve, yielding test-function of basis schema.
More precisely, given an arbitrary fest-function V, the main idea is to partition y into pieces, such that each piece is either partial Type (I, 3) Type (II, 3) test-function for some 1 < 8 < k. Each piece can then be rearranged into monotone curve via an application of Lemma 14 We use Algorithm 5 to attain {vf v² (a)))a((m1)) which characterize the appropriate basis-schema for which there exists an equivalent test-function to y
Recall that the span of partial test-function is the set of lines (4...., . 4 that crosses at some point in its domain (where the lines are indexed from 1,..., k). The span of rest-function a continuous subset of [kt since we assume that
37

---

Non-Asymptotic Length Generalization
xs(x)
S1
S2
S3
S4
S5
Monotone Curve #1
Monotone Curve #2
Monotone Curve #3
Monotone Curve #4
Figure 8. Depiction of a Basis Schema consisting of monotone curves. y-axis shows the normalized prefix sum of input string x-axis shows length of the prefix input string æ. five horizontal lines correspond to five lines with slopes {si...., 8s). Curve corresponds Basis Schema with 5. (vi v²) (1, 5), (vf v²) (5, 2), (vi, v²) 4), (ví vz) (4, 3). Finally, note that each monotone curve consists of multiple segments. The first one has 5 segments, the second one has segments, the third one has
segments, and the fourth one has 3 segments.
4 has the highest slope and fii is sorted descending. Regarding notation in Algorithm 5, Span; is a tuple of two integers in [k]],, which represent the smallest and largest index lines in the span some partial continuous test-function. (Span)
smaller element the tuple, and max(Span,) is the larger element. {8; Jej are the slopes we fixed at the beginning, and }'() sıj indicates that fest-function y intersects the line y s.x at (j. s;j). Also, when we say that y intersects the line 4 on [t, to mean that there some j [t, 1] where y(j) s:j. for S 1.
Towards proving completeness of the basis schema, we will prove the following three claims. At the end, we will use these claims to argue that (({x)) ((*)))e()) C Umelk) ((v1.v)))etm A(Y (g
1. Algorithm 5 terminates.
2. Algorithm 5 returns valid YPairs {vv (6)xcm--1] -1] where |Paars| + with m S k, and where the valid predicate is defined in the statement of Corollary E.14.
2}. y restricted to the 3. MaxTB (Tijosism-I [0, is set of real numbers where for each i E {0, 1,..,, m
interval [T,, T can be rearranged into equivalent monotone curve by Lemma E.
Proving Termination. At each iteration a, Algorithm maintains variables Span f.-11 and b which we claim satisfy the property that Span, holds the smallest and largest index of lines {1...., k) which y spans when y is restricted to interval mnax(fa-1- ba ba-1), 1).
38

---

Non-Asymptotic Length Generalization
-2 (-, 1) $
B2 (0,1)
(1, 1)
S - ) (0, - S2
(0,0)
(1,0)
B1
Figure 9. Depiction of A{{* (ie(a) for k 2 with slopes 81 82. Bi is the horizontal axis while B3 is the vertical axis. When & 2, there are only two basis schema: a single monotone (up) curve and a single monotone (down) curve. The dark blue triangle with vertices {(0, 0). (0, 1), (#) 1)} is the set of activations induced by fest-functions of the monotone (down) curve basis schema. The light blue triangle with vertices {(L, 1), (0, 1), (0, -= }} is set of activations induced by lest-functions of the monotone (up) curve. The completeness result says that the union of these two triangles equals (({81,82)).
First, suppose the span of y is single line (recall that the span of y is always at least one line, since by Lemma F.2, we let the endpoint of any test-function be on some line). Then, Algorithm initializes Span, to be the span of y, when restricted interval [0, 1]. Algorithm computes yi y2s then terminates. Our claim holds.
For )/ that span more lines, we will prove via induction that for each iteration a, Span, fa-1, and h.-1 satisfy claim. As base case, Span, = Span())) satisfies our claim. As the inductive step, suppose Span, holds the smallest and largest index of lines {1, /1.....6 }} which ) spans, when restricted to interval [max(t,-) b.- 1). 1]. Then, in iteration a, the variables ta and b, exist (recall that continuous test-function only intersects the lines at finitely many points, so the max is well defined). We can never have that t. = ba as long as min(Span,-)) < max maax(Spon) (Span,.1) 1). which must be true at the start of iteration ax otherwise the algorithm would have terminated iteration a 1. Thus, either 4,- > b, or la < b.. If lo > ba. then the last point where intersects line min(Span,)) is later than the last point where y intersects line max(Span,)) On the interval [max(ta, b,), 1]. y never intersects line max again. Thus, the smallest index of any line which y intersects on the interval [max(ta. b.),, 1] is min min(Span, [max((a, bo.), 1] must be less than max (Span,) as 1, > b,. Thus, the largest index line which ) intersects on the interval [ma ba), 1] is given by the expression, max{i < max maxan)),,)) : [k]. intersects line 4 on [max(to. ba), 1]}. This shows that line 9 correctly sets Span a completing the induction. similar correctness argument can be made for the case where to < ba. This proves that for all a. Span, correctly holds the smallest and largest index of lines {1...., ....., k} which y spans when it is restricted to interval [max(ta-1: ba-1),1] 1].
The largest index of any line which ) intersects the interval
39

---

Non-Asymptotic Length Generalization
Algorithm 5 Decompose-Into-Monooonee
1: Initialize: Span, + Span())), to f- 0, bo +
2: YPairs + % List of all (uf' y2) pairs
3: MaxTB [0
[0]
% List of all max(la; ba) values
4: for a E (1,
11 do
5: ta max j 2 max(fa-1, ba-1) Vi) (Sin(Span_)) ]
6: ba + max
j max(lo-1, ba-1) v)( $max((pan,,))
7: if ta > ba then
8: Vf + max(n)an_)) and v f- min(Span.))
9: Span.. a+1 + SnninSpann. max i < max : e [k]. y intersects line I, on [max(ta. b,), 113)
10: else
11:
5f min(Span,) and 0 + max(Span,))
12:
Span + minn > min(Span, i E [k], y intersects line I on [max(la, ba); []}, max max(Sp)n.))
13:
end if
14:
YPairs +- YPairs ((Vf' 1/)}
MaxTB MaxTB U {max(fo; ba)}
16:
if maxx(Span, min (Span,) then
17: break
18: end if
19:
end for
20:
return (YPairs, MaxTB)
For all a, we have that max (Span,)) (eii))-miinnppaii )in(Span,,) S max max(anan,..)) -Spa-n 1) Thus, the Algorithm terminates after at most [Sp]n())] - < k iterations since the largest that [Span(])] can be is k. when Y spans all lines (by [S))n())], we mean the number of lines which y spans). In particular, we let m == |YPairs] + I returned by Algorithm 5, then m S [Span())] S k.
Proving Validity of YPairs. Towards the second claim, first note that i, > b, in iteration a of Algorithm 5 and the minimum and maximum of Span.+1 are not equal, then in the next iteration + 1, it will be the case that 6,+1 > to+1- This is because the last point where y crosses line min(Span,)) has x-coordinate f.. by line 5 in iteration a. However, by lines 8 and 9 in iteration a, it must also be true that in the next iteration a + 1, ta+1. defined in line 5 of iteration a + 1, equals max(fa: ba) = fa- Since we cannot have fa+1 = ba+1 (argued previously) and fa+1, ha+1 are both la. By lines 11 and 12 in iteration a + 1, Algorithm will set g+ y². Analogously, ta ba and Span has a distinct minimum and maximum element, then ba+1 < ta+1, and of < y2 < yi = y²- This proves that the algorithm returns YPairs which is a set of at most m < Sp))
at least max(fa. ba). we have that ba+1 > fa+1
of > 1/2
< 1 pairs ((Vf v/) Jaemm-1 where each pair has a distinet minimum and maximum and satisfies the properties in Corollary E. 14, except potentially for the property that (v1. v/) = (1, or (yi.u)) = (Is, 1).
The last issue about ensuring YPairs satisfies the property that (yl y²) k1, or (vl y²) (ke, is simple deal with. note that any test-function which
The issue arises when Sp)n()) & [k), so that ) does not span all & lines. However, does not span all l lines can be thought of as part of schema which does span all l: lines, except that the segments of the schema which cross lines in [k] Sp) are the first segments of the schema, and their lengths are set equal to 0 for the particular case of y (which is a valid setting of the lengths of the first segments, per Lemma E.6). Thus, though y does not span I lines, can be thought of as belonging to schema which does. We will discuss this more at the end.
Converting Each Part into Monotone Curve, to Convert y into Continuous Test-function of Basis Schema. Third, with MaxTB = {Titosism-1, for each a im - 1], the pair (yf', v/a) generated by iteration of Algorithm 5 corresponds to the interval [Ta-1, Tal, in the sense that
Ta-1,V(Ta-i) = Ua-1,TTa1 8yp) ((T))(Ta)) = (Tar To -84g)
40

---

Non-Asymptotic Length Generalization
We have already argued that the span of the partial test-function given by restricting 3/ to [Ta: 1] is given exactly by Span.. where either vf min((pan, and y max((pan, or vf = max (nax(Spang) and 1/8 min(Span,)) Thus, the restriction of 3' on interval [To-1; To] is Type (I. max partial test- function, for which Lemma E. 1. applies.
min(Span,,) + 1) or Type (II, max(Span,) min(Span + 1)
By Lemma E,13, the restriction of y on interval (Ta-1: Ta] is equivalent to a monotone curve of span Span,, which has start-point (Ta-1, Syp -T--)) and end-point (Ta; Syg T.). The monotone curve will have the same start-point, end-point, length, and induced activations as y restricted! to 1Ta-1, Thus, we can construct such a monotone curve for each a E im - 1] and concatenate these monotone curves together. The resulting test-function is equivalent to V, as each individual monotone curve is equivalent to the corresponding restriction of y.
We claim the resulting rest-function is of one of the basis schema described in Corollary E.14. This essentially follows from the validity of YPairs outputted by Algorithm 5, which we justified in the previous section. To reiterate key point, if Span()") = [b.. then YPairs satisfies the conditions of Corollary E.14 exactly. On the other hand, if Span()) & [K] is a strict (continuous) subset of [k]. then still we can view the concatenation of monotone curves above as a test-function of a basis schema in Corollary 1. To see this, we observe that for any such V there is a basis schema Y such that we set the lengths of the segments of the monotone curves in schema Y whose span is a striet superset of Span()?) to 0, then the remaining monotone curves are given by YPairs outputted by Algorithm 5 on input V. This basis schema Y would be given as follows. Given YPairs outputted by Algorithm 5 on input V. we pre-pend either one or two pairs to YPairs. If min (Sp)n()))) = 1 or ()pa(()))))) = k. in the second case. If min ()pan())))) > 1 and max max (Span())) < k. we pre-pend two pairs A1, (k, min(Span()")) to YPairs. The resulting list of pairs with one or two pairs pre-pended, which we call I,, will have at most A 1 pairs total. L. will satisfy all requirements in Corollary E.1 As we argued that we can simply set the lengths of the monotone curves corresponding to the pre-pended pairs in L to O, the final test-function we attained by concatenating all the monotone curves together in the previous paragraph is of the basis schema corresponding to the list of pairs L.
pre-pend single pair to YPairs: (kc, 1) in the first case and (1, k)
Thus, the concatenation of monotone curves described above, based on the output by Algorithm 5, is of some basis schema specified in Corollary E.14. This proves that any continuous test-function y is equivalent (in particular, induces the same activations) to some test-function of a basis schema specified in Corollary E.14. This implies that A(Y beth ), as desired.
A (((s)) C vmelk)) (()()))))
Finally, regarding the number of basis schemas, we can first partition up the schema based on which of the k lines the end-point is on. Let f(k, i) be the number of basis schema w.r.t. a configuration of k slopes whose end-point is on line i E [k]. We claim that il,, (K=)), from which it follows that the total number of basis schema is Eie(R) (t=1)= =
For i E [k], to see that ʃ(k, - (1))). ((=) let 1, = +J {i, + 1}. Consider all permutations (4:) which contain {I,2..... - 1} and {k + 1,...., 7 2 2} as a subsequence. We claim there is a one-to-one correspondence between any such (44) and a basis schema ((()) ke)) Given Y((o)) (())mw))) let g(((vi. hem))) be permutation of 4, where the ordering of element j E I; in the permutation is the relative ordering of sector j based on the last time where schema Y ((ort passed through sector j. The mapping is injective because for any two {(vi be)m) * {(vv)', (w)))) Vefme) the first pair such that (wi, v²)) * ((vi), (v5)") will be such that v A (vy)", and one of these schema will have visited Sector,g y2 or Sector (wt) for the last time while the other will return to it later. The surjectivity of the mapping can be checked easily.
There are i 1 elements in (1, 2..,...,ii 1} and k 1 elements in It, there are (-=) such permutations.
Corollary E.15. Given a (k, -oooofiiurrai {si each basis test-function schema specified in Corollary E.14 crosses the k lines of slopes {s, (x))) a total of at most k2 times.
Proof. By Corollary E. 14 each basis schema consists of at most k monotone curves. The ith monotone curve has a span at most the span of that of the previous monotone curve minus 1, so since the first monotone curve spans lo lines, there will be at most k monotone curves. Each monotone curve intersects the & lines each once, except for the two lines at the top and bottom of its span. However, these can be reduced to one intersection when you concatenate alternating monotone lines
Herr we are applying Lemma E.13 restrictions of test-functions where the end-point is not 1, but we can do this due to the homogeneity the setup
41

---

Non-Asymptotic Length Generalization
together as such.
Thus, the number of times the test-functions any basis schema crosses the lines is Σx= i k(++1)
2
Convexity Schema.
Lemma E.16. (Convexity of activation set of test-functions of a schema) Given a (k: T) confiiguuaan,, {si) consider any schema continuous test-functions. Suppose the schema specifies M segments. Let ( be the set of valid ( .RM) of segment lengths with Ex=1 n4 = 1, where valid setting of (R....., Ris)) satisfies the constraints described in Lemma E.6. Then AlM) is convex set of dimension M - 1. Moreover, A(M) is a simplex.
Proof. (M)) is the intersection of the linear subspace over (πI, ...;; Rar) given by dd ny =1 along with M halfspaces of the form in Lemma E.6:
Vi E
[M] n4 2
Ps qi
nj
Each Pt: qi will be determined from the slopes of the lines that segment i first intersects and last intersects. By Lemma E.6, there are three cases:
Case 1: Segment Crosses From Line Line + Then, n4 2
1) ブラ= nzj.
8541
Case 2: Segment Crosses From Line + 1 to Line j. Then, n4 2
1-81+1
1) ش nl.
1-8;
Case 3: Segment i Crosses From Line to Line j. Then, P. = 0.
First, since A (M) is the intersection convex sets, it is convex.
Second, regarding dimension of ( since all elements [stbeet of the configuration are distinct and in (0, 1), each of the M halfspaces different subset of the variables {mi
{n {ni, n2), {ni, n2, nz)...., (RI..... RM-1), (nni),nnn...... (nI,.... . ,.M
In particular, no combination of inequality constraint can form an equality constraint which implies that the intersection of the M halfspaces has dimension M. Thus, (M) has dimension M 1 due to the additional constraint Σ ?2 = 1.
Third, AMM) can be thought of as a polytope over M - 1 variables, once we substitute in nM 11 EMI1 n4. while it has exactly M faces given by the M halfspaces, with dur (MM) remain distinct even after the substitution since the only face whose linear inequality included nas will have bias term of after the substitution, while the other faces' linear inequality remain homogeneous. Since ( has M faces and has dimension M 1, it is simplex.
A-1 n, substituted into the inequalities. The M faces of
E.4. Lemmas for Margin of Point in a Polytope.
Average of Vertices of a Polytope. As motivation for the following definition, recall that the centroid of a d-dimensional simplex is the average of its d + 1 vertices. Informally speaking, the centroid has the nice property that it is far from each face of the simplex. This property is useful for our proof, though we will need to extend this average of vertices notion to general convex polytopes.
Definition E.17. (Average of Vertices) Given a convex polytope of vertices "h....,UN: we will define the average-of- vertices P as c = * EiEN U; E P.
Note that for general convex polytope P, the average of its vertices will not, in general, be its centroid.
Margin of Average Vertices of Polytope with poly(T) poly (K) Precision Faces.
42

---

Non-Asymptotic Length Generalization
Definition 6.10 (Margin). Given a linear inequality L over M variables and point x E IRM, define L(x) the difference between the left-hand-side and higt-haad-ssid of the inequality when the coordinates of plugged into L. Let satisfies the inequalities with equality. We say L(x) is the margin of x for L.
L(x) = 0 >>
Often, we will mention the notion of margin in the context of polytope P. where are interested in the margin of point P onto face of P. For any face F of P. F will be defined as the boundary of the halfspace given by some linear inequality L. In this case. WLOG, we will define the margin of any point z in P to F to be L(x). Moreover, we will define so that [xx) is non-negative for x E P. As such, we will sometimes refer to the margin of a point x E P onto a face of as the "positive" margin to emphasize this point.
We start with the following Lemma.
Lemma E.18. Consider a nonempty (M -i-diennsol convex polytope P C 1 Suppose the faces of consists of N halfspaces over variables {n4)sE[M-I) where each halfspace given by a linear inequality with integer coefficients of magnitude at most p. For j E [N], define I.j as the linear inequality for the jth face.
Then, for any j for any vertex of P which does not lie the jth face of P, then the positive margin Lz(x) is lower bounded as follows.
1
1,(x) 2 (VMp)
x'
Proof. For each j E [ represent the linear inequality Lj vector in vj E [--p.p] MM such that Va' E RM 0/ the margin on the constraint given by Ly. In addition, in our definition of the vector representations Uy, we want to ensure that the vectors 0j are such that Vj E 1, (_1) > for all vertices x which do not lie on the jth face of P. This is always possible due to the convexity of the polytope, which is contained in the intersection of the halfspaces defined by each of its faces.
-
As an example of vector representations of inequalities,
n1 + 2np + +nng > > (1,2,3,4)
2n1 3mg + 10ng S 9 - (-2,3, 10,99)
WLOG, we will prove the statement for the 1st face of P. Pick any vertex which does not lie the 1st face of P (i.e. [[ > 0). is the intersection of M --1 distinct faces of P, whose indices denote as {i<)ie[M-1) C [N] {1). Let A E [-p,p) p) Mx be matrix such that for all E [M -0 1). the row of vj, the vector representation for L,.- Let the M th row U1, the vector representation L1. Write A in block form as:
A c
b
A
d
where E [-p.p] (M-1) and b, c E [-p,p] M- and d E [-p.p], so that ( is the vector representation of L,.
We have that Vi E [M - 11, = (A,) (1)
where A, denotes the ith row of Since x lies on all the faces whose
indices are in (js (j))e(M-1).
43

---

Non-Asymptotic Length Generalization
vi E 1 (x)= =
= Ax =
= I = A
(A-
L1(x) = (Am) T
--1
T
c
d
-1
c
A A - d
Next, we note that
A = A
b
0 T b
= Al(dd - c A b
Thus,
A A
L (x)
> 0
where the margin is strictly positive since xi does not on face Its margin has minimum value of
[ wypj since
the numerator |A] is an integer while the denominator is upper bounded by (V The upper bound on the determinant of A is by the Geomerric-Mennn-uuaarrt------ inequality the eigenvalues of A, where |A| < 1 ||| M-r (VM.)) M
Finally, this lower bound holds for any other face P and any vertex of P which does not lie on that face by an analogous argument.
We now provide Lemma which can improve the margin lower bound in the case that know some additional information about the aforementioned matrix A defined in the setting of Lemma F.18.
Lemma E.19. Suppose (T, K), (T", K') e N² are such that K - T and K' (T')². WLOG, suppose T > T". Suppose M E N such that max(K, K') < M < 2(K K'), and suppose constants d = O(1). Suppose matrix A E M-1XXM- such that:
1. v1 S min(CK, M -), 1), - -FM))
2. V Vmin(c,, M - 1) i M - 1, 1, (-0((T79)....
Then A| 5 O(TO() (TT))
Proof. If 2 2, by the homogeneity of the determinant, we can factor out a factor of O(T") from each of the first min(cK, M -1] 1) rows of and factor of d(T')d) from the remaining rows of A.
|A| < ( ( MM((T)))))---mmmmk
Where Á is an (M - x (M 1) matrix such that the largest magnitude of any entry in À is 1. Since T,T' 2 2, then there is universal constant < c O(1) such that:
44

---

Non-Asymptotic Length Generalization
|A| S (I ((T')ycghht----mckk.-- (
By the same Quadraiie-Mea--GGemttte---- argument in Lemma E.18,
1
A -
M -
S A 7
Suppose that K < K" Then M S 4K' that (Ted)ain(ck,M-))
(("g) ((T))agj--L-nnccckkkd < Teedk (T*)
Meanwhile, since M < 4K" and K' I (T')? then M I (4(T") so that |A| 1 (Tudjnin(KK,M-))
((T))a))M--mmin) MM M < TeeaK (T"))eakk' (4(T")332R' < O(TO(K) (T))O()))))))
Now suppose that K 2 K'. Then S 4K so that (Tedmintek,M--) Trok T Meanwhile. since M < 4K and K S S2, then M < (479)2K so that |A| & (Trd)min(cK,.M-) 11) M < Treck .Teek (4T9)2K < <O(TO(K), ((K))))))
(ir))))M--miinck.A < Teedk (TV) S
((T")))M----iin
In the case T = 1 and T 1. then M = 0(1). so |A| S O(1). In the case T 2 2 but T' = 1, then K' (T")2 = 1, and following similar argument as the case where T, T' 2 2 and K 2 K' yields the desired bound.
As consequence, we have the following finer-graines version of Lemma E.18
Lemma E.20. Suppose a E N. (T,, K') E I² are such that T I a and (T I and S T and K' < (T'2. WLOGG suppose T 2 T'. Suppose M N such that max(K, KKK, K') S M S 2 + K"). Suppose di, d2 011)
Consider nonempty (M 1) dimensional convex polytope P RM-1, Suppose the faces of P consists of N halfspaces over variables [mi)se(M-1] Suppose that there is subset of at most d1 K faces of P such that each face of the subset is given by linear inequality whose coefficients have precision most O(Td2) while the faces in the subset all have precision most d(TT))a)). For j [NV, define Lj as the linear constraint for the jth face.
Then, for any j for any vertex x of P which does not lie on the jth face of P, then the positive margin Lş(x)) is lower bounded as follows.
(5(x) Ω o011
Proof. We follow the proof of Lemma E, 18 up to the step where we' 'e defined and and where we deduce that for any vertex x of P which does not on the first face of P.
(x) =
> 0
A
Because A satisfies the pre-conditions Lemma 19 once swap of rows appropriately, then |A| < ((T))))))))) (())))) Thus, (x) 2 Ω( (dir)) ). An analogous argument holds for all the other faces of P.
The following corollary applies Lemma E.20 to our setting of interest.
Corollary E.21. Suppose E N, (T, K), (T", K') E N² are such that T < a and (T') S and K S T and K' < (T')? WLOG, suppose T 2 T'. Suppose M N such that max(K K, K') S M s 2(K + K') Suppose d1, d2 = 0(1).
Denote the coordinates in an M- M-dimensional Euclidean space E as (nI...., .M)) Consider a nonempty (M - 1)- dimensional polytope E, such that cl(P) has vertices V, with [V] 2 M, and N faces. Suppose P is contained the
45

---

Non-Asymptotic Length Generalization
(M-1)-dimeesionne 11-diemnsson subspace given by Eie(My n4 1. Suppose there a subset of at most dp K faces of P such that each face of the subset is given by linear inequality whose coefficients have precision at most ( while the faces not in the subset all have precision at most ((T)))a)). ) For j E [N], define L,j as the linear constraint for the jth face.
Then the average of the [V] vertices of P will have margin at least S1 ( @drr)) for all (M - 2)-dimensional faces of P.
Proof. To reduce this to the setting of Lemma E.20, first substitute 7MM = 1 Ei=1 nu in the inequalities for all N faces of P so that each inequality is an equivalent inequality over "......,,MM.1) with integer coefficients increased by a factor of at most 2 (which will ultimately absorbed by the Big-O notation).
Applying Lemma E.20 on P. where n =1 EMT n4 was substituted into the inequalities defining faces of P. implies that for every (M dimmensiia face F of cl( and every vertex of cl(P) which does not lie on F, then the margin of x on F is at least Q @d(r)) ). All vertices which lie on F have margin 0.
Consider c, the average of vertices {.1,..., ( of P.
V
T
2iv1 For any face F of P with constraint given by LF()), at least one of the [V] vertices {xi,. ( does not lie on F, as F is (M - d-m-immnsio while P is (M 1)-dimensional. By linearity of the margin,
V [
LF(c)= LF(x))
2 Q 1 V @011)
Finally, we need more Lemma to bound the number of vertices of the polytope of interest in the main proof.
Lemma E.22. Denote the coordinates in an M Addimensional Euclidean space E (NI,...,,Ny Consider a nonempty (M 1-1) --)-ddimensiond polytope P C E, such that cl(P) has vertices V. with [V| 2 M, and N faces. Suppose P is contained 1, and P is the intersection of an (M 1)-dimensional
in the (M - 1)-dimensional subspace given by EmE[M]] simplex and two halfspaces. Then, the number of vertices of P is at most 3M2
Proof. Let P = An H1 O Hz, where the - 1im-mdimmisiinal simplex, and H1, H2 are the halfspaces. First, will have M vertices and M faces.
The new vertices formed by intersecting H1 with A can be upper bounded by counting the number of tuples of M 1 faces of A, as each vertex is formed by the intersection of M faces. H1, when intersecting A will be able to form at most (.M) .M new vertices. H2, when intersecting An H1, will be able form at most M+ M(M+1) 2
(M-1)
new vertices.
The total vertices of An H1 n H2 is at most 2M + M(M+1)
3M2
E.5. Lemmas for Discrete Approximation.
In this section, we are interested in showing that an activation (Bi...., B&) realized by some continuous test-function y also be approximately realized by some discrete csst-function X. The difficulty is that discrete rest-functions consist of sequence of lattice points {(j. ps (x)x)) (r)))))ee ye[[]]] where successive lattice points differ by step of (+1, 0) (corresponding to
4 = 0) or (+1,+) 11 (corresponding to x; = 1).
First, here is an auxiliary Lemma that provides a strategy to construct a trajectory of lattice points where successive lattice points differ by a step of (+1,0) or (+1, +1) and where the trajectory stays between two lines y = _x and = 4x The strategy offers way to iteratively find the next lattice point in the trajectory.
46

---

Non-Asymptotic Length Generalization
Lemma E.23. For any two 2D lines with slopes 1 > è $ > 0 where a, c, d S T, there exists an infinite sequence of bits x E 10 such that for all n 2 T2 we have that 2n 2 ps(z)n > En. That is, the discrete test-function given by x is above the lower line and below the upper line.
c
Proof. mil.g......d....444 - - pz. so for n 2 T2, (H 1) )n 2 1. Thus, for every n 2 T2, there is at least one lattice point (n, va) E - with n 2 yn n.
Now let's consider strategy to jump from (n, Da) to (n + 1, +1). For all n 2 22, from any such lattice point, (n, yn).
either (n + yn) or (n + 1, yn + 1) will be in (- (n + 1), 6 (n + 1)]. Thus, there is always a continuation of the trajectory that remains between the two lines; one either takes a step along (+1,0) (corresponding to In+1 = 0) or along (+1,+1) (corresponding to Fn+1= = t) to reach (n + Vn) or (n+ + L. yn + 1). respectively.
Finally, the trajectory from (0,0) to (T2, can always be made by some trajectory using increments (+1, and (+1,0) since yr2 < _ < T
The following Lemma says that we can approximate any continuous test-function y with a length n discrete test-function, for n above some threshold.
Lemma E.24. (Discrete Approximation to Continuous Test-Function) Suppose E N. (T, K), (T", K') E N2 are such that Tk S a and (TT)x* S a and K S T and K' S (. WLOG, suppose T N T'. Suppose we are given a (): configuration [Si]ee(t). where a subset of [st]ee])) of size at most K have precision at most T, while the remaining entries of (5e (EEN) have precision at most T'. For any schema Y of M segments, suppose y is any continuous test-function of schema Y, with segment lengths (Ti (J),.... T (V)) E 1ja (where we assumed WLOG that Σ, ()) 1). Suppose every (V) is a rational number and that the common denominator of all (T)(())) is p.
Then there exists an no S Opp )²?) so that for any positive integer multiple n of no, there exists a discrete rest-function X of length n so that
Vi E [k]. B.O') - B(())) S T +
Proof. Denote idx(i)= E [k] as the line which the end-point of segment of the schema Y (the schema of 3)) lies on. First, given the l slopes 81, 8k E (0, 1). suppose that the denominators of these slopes are a(").... ..... (*), where Vi E [k]. 8; = a- There is a subset U C [k] of size at most K such that {a(0) i E U} are all positive integers of precision at most T. Further, {a()) i & U} is a set of at most K' positive integers of precision at most T". Let d be the least common multiple of (a(") " (M)) Note that d < T (TT) <a²
g(6)
Now, set 1o = d. p. and consider any multiple n of no- Consider the quantities, (n,)))) == {n 1h-nn (n;))))) (EMM) which are the segment lengths y. rescaled by a factor of n. We will refer to this rescaled y instead of y for convenience of notation in the proof: like a discrete test-function of length n, the rescaled y will be a map from [0, n] + [0, n]. Denote
6, = Ej= ())) for all i E [M] and dn = O.
We will construct discrete test-function which follows the same schema as the rescaled y on the interval [ n]. though on the interval [0, I X' will have no guarantees.
First, we will define M + 1 lattice points where the discrete test-function will cross over the lines ("crossing points"). Second, we show how to connect those crossing points with a sequence of lattice points, where consecutive lattice points differ by increments of the 2D vectors, (+1,+1) and (+1, (so that the sequence of lattice points is like discrete test-function). At the end, we will argue that the constructed discrete test-function X' and the rescaled y will satisfy the y, where the input domain and the output is scaled by n, will cross the k lines 4,...,44 la at the M + 1 points,
guarantee that Vi E [b). [))) - (2)) M+T²
Step 1: Defining the Crossing Points of the Discrete Test-Function on the k Lines. The rescaled continuous test-function
(nan()) U {(0,0)
47

---

Non-Asymptotic Length Generalization
Due to the way we have set n, these are all lattice points. Since n d p, and all ())) have common denominator p. then ())) is integer for all E [M] so o is integer for all E [M. Second, because of the factor of d, Sidx(s) 6; is an integer. They are therefore valid points for the discrete test-function to go through, and we will design discrete U {(0, })} for all 6; 2 T
test-function that crosses the k lines at {ōo, Siax()));
Step 2: Connecting the Crossing Points. We'll describe a strategy for constructing the discrete test-function that connects these crossing points. For any segment in the continuous schema, will either cross between two consecutive lines, or it will cross line and then recross the same line. We need only show how to do these types of crossings in a way that only crosses the appropriate lines the start and endpoint of the segment { (aa(())))/eea and at no point in between. Consider the (i + 1 th segment of )/ which has point (ō,, S1 and end-point (6,-1: 1))(4++)00++)) There are three cases:
The segment crosses down (segment start-point on line 1, and end-point on line 15+1 for some j E [k 1))
The segment crosses up (segment start-point on line 15+1 and end-point on In for some j E [k: 1]) (J)
The segment crosses and re-crosses the same line (segment start and end-point on ly for some j E [k))
The strategies below will apply when the segment's start- start-point's s x-coordinate is at least T (i.e. 6, 2 T²). After describing these, we will handle the corner case where a segment's start-point's x-coordinate is less than T2 but its end-point's x-coordinate is larger than 7
Case 1: Segment Crosses Down, Suppose that we must connect the following start and end-point with a sequence of lattice points which lie between lines 15,
(ō., 6.), (6i+1, 81-1) E z²
The corresponding segment of the rescaled continuous test-function is the (i + 1)th segment with length n,+1((')) E Z.
First, there exists a sequence (trajectory) of lattice points {(x,, ((xx))o))sssmmm)
where (xo. yo) = (o;, 8j 6z), Xt+1 = X + I; and ys+1 = yr + 1 or
(Kn4s (n))) (2)) = (6++1, 8j+1 81+1) where for all < t < Y1+1 = Yr. This because the rescaled Y' is a continuous test-function which connects these two lattice points and which 1-Lipschitz and non-decreasing, We want to further show that there exists such a trajectory of lattice points {(xx, yc)} such that V1 < S ())) 1,85 X yt > 8j41 Xt.
The strategy to do so constructs a trajectory from the start-point (8s, 85 6d)) to the end-point (8:+1, 6c+1) and consists of two phases:
(Phase 1) First, the following iterative procedure is applied, starting with (xo, yo) = (8), 83 5:) and ( = 0:
From the current lattice point (Xe, Yt), choose (x++1-y+11) (xt ye) or (x+ 1, + 1) depending on which one satisfies 8, X 2 y++1 > 8j+1 Xe+1- At least one of the two will always satisfy this condition if x, 2 T as argued in Lemma E.23. If both are possible, then choose either.
This is repeated until, y,, the y-coordinate of the current lattice point equals 8j+ 10+11
(Phase 2) The trajectory only takes steps along the direction (+1,0) so that (Xe41 Yo41) = (xt + 1,yr) until the end-point is reached.
In Phase 1, we will always be able to find a next point (x++1, between L3, 4++1 from a current point (xx, yt) between 41,4+ xo 2 2 as argued in Lemma E.23. By induction, all such lattice points will lie between the two lines 4 4++1- Phase will terminate because yt is non-decreasing in f and cannot remain bounded by any constant as t increases to co, in order to stay between (j, fj+1. since 8j+1 > 0. Thus, there exists some minimal ta such that yr. 8j410041 for the first time. Because the lattice points always stay between 11,,,,, then at time l.,, we must have that x,, < 5,41. Thus, Phase I terminates and Phase 2 can commence.
is clear that Phase 2 will yield a set of lattice points that are between Ly, 1441 with the last lattice point being (be41, 83+1 5(41) ) as desired.
48

---

Non-Asymptotic Length Generalization
This connects the two points with trajectory that does not intersect 1, and 1++1 any points besides the start and endpoint, neither phase crosses the two lines.
Case 2: Segment Crosses Up.
Suppose that we must connect the following start and end-point with sequence of lattice points which lie between lines 1:11:
(6,, 8541 6,), (6r41, 8,+1)
The argument is analogous. First, there exists sequence of lattice points {(x,, y:)} where (x), (6,, (51,8 6z), (Xn4: (J)),)nu ( = (6 53 6/+1) where for all 0 < 1 < ()'), X++1 Xx + and Yr+1 = Yz + or yr+1 = ye- This is because the rescaled y is a continuous test-function which connects these two lattice points and which is 1-Lipschitz and non-decreasing. We want to further show that there exists such a trajectory of lattice points {(x, Ye)} such that V1 < S (0)) 1, X Z Y 8J+1* Xx.
The strategy do so consists of two phases:
(Phase 1) First, the following iterative procedure is applied, starting with (xo, yo) = (6,, 85+1 6z) and ( = 0:
From the current lattice point (xe,ya). choose (Xe+1. Ye+1) (xt ye) (x: y, + 1) depending which one satisfies 8j X 2 y++11 > 8j+1 -x+1- At least one of the two will always satisfy this condition if xo 2 7 as argued in Lemma E.23. If both are possible, then chose either.
This is repeated until the current lattice point Ye) and the end-point 10 8,+1) can be connected with line of slope 1. That is, $j 8.41 Yt 81+1 Xt.
(Phase 2) The trajectory only takes steps along the direction (+1,+1) so that (X411) = (x+ + 1, + 1) until the end-point is reached.
The analysis of this strategy is analogous to that in Case 1.
Case 3: Segment Crosses and Recrosses the Same Line, 1y.
Suppose that we must connect the following start and end-point with sequence of lattice points.
(8,, 89 64), (6.-1, 8y 6(+1)
This can always be accomplished by discrete test-function if 6, T There
subcases: (1) if the trajectory needs cross above line j then recross line j, and (2) if the trajectory needs to cross below line and then recross line j. In case (I), require the sequence of lattice points to lie between lines 15 while in case (2), we require the sequence of lattice points to lie between lines 1,, 14+1.
simple strategy for subcase (1) is to first set Y1) = (5. + 1, 1, + 1) (i.e. move one step along to (+1, +1) from the start-point). Note that (ō, + 1, 8,ō; + 1) will not above line j - since 6, > T so (s--1 - 8,)8, 2 1 and syd, + S ( + 1). The trajectory will now be above line j and below line j 1. Next, use Lemma E.23 to iteratively find the next lattice point (x441,y(41) from the current lattice point (x) by taking steps that are either (+1,+J) or (+1,0) 0) while staying between 15.15-1 until yt = Sy 8.41. Then, take the remaining steps along (+1, 0) until the end-point is reached.
An analogous strategy exists for subcase (2). Move one step according to (+1,0) 0) so that (X1, Yı) is below line j and above line j ++1 Use Lemma E.23 to move to the next lattice point strictly between line j and j + until (5.+1 - X2 = 8 - yt).
Notice that this strategy is similar to those in Cases I and 2, and the analysis of them the same.
49

---

Non-Asymptotic Length Generalization
Step 3: Constructing the Final Discrete Functinn. We have proved that for each E [M], the two crossing points (6--1: Sidx((-))0;- and (ōi, ()ax())))) can be connected by some sequence of lattice points that only crosses the k lines U4,.... 4x) } at the crossing points, long -;-1 7 The lattice points differ from each other by increments of (+1, 0) and (+1, +1), like discrete rest-function. Each sequence of lattice points can be identified with one segment of the rescaled y so that the number of lattice points, excluding (6,-1, (ix((-1))111)) equals ny ()).
Before constructing the final discrete test-function, we will need to construct the rest of the lattice points of the discrete test-function corresponding to segments of y whose start-point is not larger than T
Suppose that the Moth segment of y is such that 0 M S T - 1 òM where Mo E [M]. We split the Moth segment up into two pieces. Consider the restriction of the Moth segment to the following domains: 10 T2) and We will construct sequence of lattice points for the restriction of the Math segment on [Tè, ,8r, using similar techniques as in Step 2. We will then construct a sequence of lattice points from (0, to (+) for some yr, to complete the discrete test-function. There are three cases to consider.
Case 1: idx( MM - 1) = J. (M) = + 1 for some j E [k: 1]
We have that (s, - (T²) 2 I, so there exists lattice point yT) such that y. (sH+122, s,7%) with y, Z. We then construct a sequence of lattice points from (T² y=) to (ō Siax (MM) SM,) using the same strategy in Step 2, Case 1. This sequence of lattice points will be such that consecutive lattice points differ by an increment of (+1, +1) or (+1,0) 0) and all lattice points are between I, and lj+1.
We also construct a sequence of lattice points from (0,0) to (T2, .y). The only requirement of this sequence of lattice points is that consecutive lattice points differ by an increment of (11,+1) or (+1,0). Since y. S 8, < T2, this will be possible.
Case 2: idx 1) = + (do) j for some j [k - 1].
Similar to Case 1. We have that (s, - (T²) 2 1, so there exists lattice point (T² such that y. E (s, sT with y. E Z.. We then construct a sequence of lattice points from (T y.) to (ŌM,, (M,) using the same strategy as in Step 2. Case 2. This sequence of lattice points will be such that consecutive lattice points differ by an increment of +1) or (+1, 0) and all lattice points are between I, and lj+1.
We also construct a sequence of lattice points from (0, (T). The only requirement of this sequence of lattice points is that consecutive lattice points differ by an increment of +1) or (+1,0). Since y. S <3,T2 < T2, this will be possible.
Case 3: id 1) ido(Mo) = for some j E [k]].
There are two subcases: either segment My is contained in Sector, or in Sectory-1 (Sectors are defined in Definition E.4). We will just consider the first subcase, as the second analogous. Define so = and to as the homogeneous, 2D line with slope so-
We have that (s,-1 - (T) 2 1, so there exists lattice point (T².y.) such that y- (s,T?..8-177 with y. Z. We then construct a sequence of lattice points from (T2,y-) to (ŌM, Six)) using the same strategy as in Step 2, Case 1. This sequence of lattice points will be such that consecutive lattice points differ by an increment of (+1,+1) or (+1, 0) and all lattice points are between 1,-1 and 1y.
We also construct a sequence of lattice points from (0, 0) to (T2, y.). The only requirement of this sequence of lattice points that consecutive lattice points differ by an increment of (+1, +1) or (+1, 0). Since y. S --- < T2, this will be possible.
We now construct the full discrete test-function by concatenating all these sequences of lattice points into a sin- gle sequence of lattice points. For each i E [Mo MJ. use the aforementioned constructions to construct sequence of lattice points with start-point (max(,;_1,77)) $ax(i-1) max(,.-1, and end-point (ōt, &:) Remove the start-point from each of these sequences of lattice points, and concatenate all the sequences of lattice points for E [M]. Finally, concatenate the sequence of lattice points from (0, 0) to yT). for y, as described in Case 3 above. This sequence of lattice points is valid discrete test-function since consecutive lattice points differ by an increment of (+1,+1) or (+1,0). We will refer to the constructed discrete test-function as X.
50

---

Non-Asymptotic Length Generalization
Properties of the Final Construction. F E [Mo MJ. there is a correspondence between the ith segment of y and the sequence of lattice points with start-point (max(6,-1,, ) Sidx(i-1) m T))) and end-point (ō,, (idx 6:). The difference between the number of lattice points in the latter and the length of the former is at most T In addition, all except
possibly one of those lattice points (the end mod-point) lie in the sector in which the ith segment of y lies in.
Define (B)())))E(()) and (B)())) as follows.
Vi B.))) J 1(()) 5, -jldj
Vi [8] B(()) = 120) > s.
For any E [k], (x)) depends on the total number of lattice points (out of n)) which are strictly above line i, while ())))) depends on the total length of segments which lie above line i. The maximum deviation between (X)) and ()) is upper bounded by L multiplied by the number of lattice points (i, ( [n], which are not in the Sector which their
corresponding segment is in, which is upper bounded by T # times y crosses line + More precisely, for any i [7c]
[B(()) B.O0B
Σ E
1(0, is not in the same Sector that segment m of y is in]
m 6m Kjss.
T + #(i 1] V(j) -8.-))
2 M
n
The T term arises from the lattice points (j, X()) for j E [T which have no guarantee of being in the Sector of the corresponding segment of y. The # times y crosses line term arises from the fact that for > T2, only (j,X(i) which lie on line i may potentially lie in different Sector than that of the corresponding segment of V. This is upper bounded by M since y has only M segments and so can cross line at most M times.
E.6. Auxiliary Lemmas
Convex Geometry Lemmas.
Lemma E.25. (Theorem 6.2 of (Rockafellar, 1970)) Let C be a nonempty convex set. Then its relative interior, ri(C), is also nonempty.
Lemma E.26. (Theorem 6.1 of (Rockafellar, 1970)) Let be a convex set R.. Let x E ri(C) and E cl(C). Then for all 0 1, A)x + Az E ri(C).
Lemma E.27. Let C be nonempty convex in R", Consider open halfspace H (x R." Eieny d at. If COH # 0, then dim(C' H) dCm(C).
Proof. Suppose that C H. If ri(C), then since H is open set, we done.
not, p E ac = cl(C) ri(C". By Lemma E.25, since C' + 0, there exists ri(C'.. By Lemma E.26, V0 S A < 1, Px = Ap + (1 - \)æ E ri(C).
We claim there exists some setting of À A 1 such that px E H. Since is open, there exists > 0 such that Ball; = (x' I² : || plla < 8} C H. Taking À
ensures that ||p - pll2 < 8 - Pa E H. Thus,
2 2
PA E H Hrii(C).
Lemmas Regarding Existence of Low Precision Element Lox Ball.
Lemma E.28. Let N > 0 be an integer. For any x E R. the interval [x, x + N. contains at least one element of the form m for integer m.
N
51

---

Non-Asymptotic Length Generalization
Proof. For N O, the set 1 m E 2) is such that the minimum distance between any consecutive elements is Since the length of the interval [ar 2 N. is N. it must contain element of S, or else this would imply that there is some pair of consecutive elements in S such that the distance between them is greater than N.
Lemma E.29. Let N > O be an integer. For any I (#1,..., Fa) E Rd with ExEla = 1, the L ball fx' E IR ||r - 1F S 3) (a': Eiela #4 contains a point x" E Q whose fractional coordinates have least common denominator of most d .N.
Proof. Consider B (x) = fa' E R. || 2'1 dv n (x's E CR EsE 1 : aiv
=
Along each dimension i E {1,2, .,. d- - 1), there must exist number in the interval {2; aN + dN for integer my by Lemma E.28. We can set xp = IN for all i E [d - 1]. The last coordinate va will need to be set to Di my that x" E {x': Eielg o 1}. Finally, |a4 zal S Eieja-1] |ay xil
1 of the form
JN
1-
d-1 dN S N. Hence, we
JN have that x" Ball (x)
and that each coordinate is of the form of mi for some integer m,.
Relating to Technical Lemma E.30.
Lemma E.30. for every S C-RASP2 with K(J) heads, we have that z > and Eie(K(ry d > 2, then for any f. E C-RASP2 that are not equal, with K and K' heads respectively, then f and f will differ on some continuous test-function, Y. which strictly satisfies the second layer inequalities. That is, with max(K, (K, K') < k S K + K' distinct heads between I and f", let (B,()),..,BB(()) be the activations induced by y. Then, either:
K
X (o
() <
Or,
K
A B) <=
K'
Σ (Bon((2,)())) > z'
To prove this, we will need Lemma E.33 and E.34. First, define the following notion of connectedness for subsets of Euclidean space.
Definition E.31. (Definition 2.4 (Freiwald, 2014)) Two subsets and of a metric space are said to be separated both cl) n B and A ( 0. A set E C is connected if E is not the union of two nonempty, separated sets.
We will utilize the following Lemma (implicitly) in the proof below to show that a union of sets USE[N| Aj is connected, by iteratively arguing that for each j E [N] {1), Aj is not separated from Uber A, (i.e. they "share an edge").
Lemma E.32. (Theorem 2.9 in (Freiwald, 2014)) Suppose and {oor are connected subsets of X and that for each a, Ca and C are not separated. Then C' U User Ca is connected
Next, fix f' and the k distinct slopes {s: hee( across the first layers of both programs. Let's consider the k-dimensional set ((s))e)j)) [0, _Jat. A({s)):) is equal to the union of finite number of convex polytopes by Corollary 1. and Lemma 1.
A((s:hee())
U
A(Y (lut (Wteem))
me
valid ((v) valid
Here are two key Lemmas we will need.
52

---

Non-Asymptotic Length Generalization
Lemma E.33. (Dimension of Polytopes) Given a (k; cooffguurrtii ( then for each basis schema Y (lit heleemm) the set of activations ((V((i ((vi.1)))cmm has dimension
Proof. Consider any basis schema Y that spans lines with M' segments, as described in Corollary 1. It suffices to show independent degrees of freedom in A(Y).
Given (Bi.... B&) consider the full-rank linear map, Q IR R*
Q(BI..... Bx) [B1,B, - B1, Bs , Bk-1)
Denote Q o A(Y) as the set consisting of points attained by applying Q on all points in A(Y). We have dim(Q o A(Y)) = dim dim(A((Y) dim(ker(()
A(Y)) so since Q has rank k, dim(ker(()) n A(Y)) S dim(ker(Q)) = So to prove that (im(A(Y)) = k. suffices to prove dim (Q a A(Y)) is k.
By Lemma 1.1 schema Y will span all k lines and will have at least one segment in each of the k + 1 sectors. First, set the lengths of all the segments that are in sector k + 1 to O. This can always be done because by Lemma E.6, there is no constraint on any segment in Sector since such a segment would not be crossing two distinct lines. Say that there are M non-zero-length segments left that are each in the sectors (1,2,... ......kk) kj. Let (m1,..., nnM) be the lengths of these segments.
There is a linear mapping QL RM + g that maps (MI,..., n1)) to a vector e E IR*, where for all E [k], Us is the sum of the length of segments that are contained in in Sector,, This map is the multiplication of Q and L, where L is linear map L: TR R2* which maps segment lengths of Y, (M1,-.., ,nM) ), activations (B1,-... B&). In matrix form, L E {0, 1]kx]xxxx kx is such that Lij = segment in schema Y lies above line i and hence contributes activation B,.
Now, for each sector E [k], let:
;= mam[] E [M] : ny E Sector,
be the index of the last segment in the schema that is in Sector
Now, for each
[k). consider setting of (ni.-.., n&s) where for all j Ji. ny 0, but ni, 0. Denote the setting for i E [k] as N; == (n) ;..,,,..,,,,, 2 )- We claim that the & vectors, (QI(N,)) are linearly independent. Since (QL(N)))se[k) C Q a A this would imply the first point of the Lemma. The claim that (QL(N,) are linearly independent can be argued by induction.
(8))
As base case, suppose that in [k] is the sector where the Mth segment of the schema lies in. Then QT((..)) - The singleton set is linearly independent.
For each < < k denote I, := {i E [M] : j: is one of the r-largest of the set { heih so 1 = {.o) Suppose by the inductive hypothesis that for 1 r r S k: the vectors (QL(NN) : E 4,} are linearly independent. Now, let i. be the sector (6-))
nM will be such that n ) is nonzero, which implies that the th entry of QL.N..) is nonzero. In contrast, for all i E f, the i, entry of QL(N,) zero, because for all j > js. there is no segment ny that lies in sector i.. by definition of jr, so by the construction of N, where all segments of index less than ja are set to 0, then the i, th entry of (N:) is for all i I,.. Thus, the r vectors (QL(N,) : E T,+1) are linearly independent. It follows that T3 is set of k linearly independent vectors in Q A(Y), so dim(Q A(Y)) k.
such that ja. is the (r 1)th largest of the set (ii)ee (m1 [1.)
Lemma E.34. (Comnectedness of Interiors of Polytopes) Given a (kof))cconiiuuaation {silien)) the set Ume|kk],vaid (lvi-o)))e (),....k) int ((A(((())))))))))))))))) is connected.
Proof. Let us first recall the set of basis schemas in Corollary E.14. For any 1 S m S le and {(v v5) heemm C [l....,k}m such that
53

---

Non-Asymptotic Length Generalization
V1 = 1/
Vi E [m - 1]. v # V/2
Vi [m 2], vi 1/2
3/2 1/11
1/2 1/2 vi
Vi E im 2). vi > V/2 = y/2 vi i+1
< 1/2 141 < Vi
(wi, 122 = (1, or (vl, (k, 1)
We the test-function schema, Y((d (a])ectm the concatenation of m monotone curves, where the ith monotone curve goes from lines y to 1/ for E [m - 1]. The set these test-function schemas over all valid {(vi Ne)m satisfying the above complete by Corollary E.
Let A(Y vej))) denote the set of activations induced by test-functions of schema Y((ff (5)etm)) A(Y ((sf.)))ee)m a convex set by Lemma 1. Thus, each set int(A(Y((v (vV. ((vi.e)))ctmm) )), by itself, is connected.
Now, imagine graph where each basis schema Y (e)i is node. Create an edge between basis schema Y and Y' if inY(A( O (A(")))) A 0. By Lemma E.32, to prove desired conclusion, it is sufficient to show that this graph is connected. For this, will need to prove which edges exist and that these edges suffice to connect the graph.
Categorize the basis schema into levels, where schema of the same levels have the same number of monotone curves (i.e. the parameter m E [k:).
Edges Within Same Level. Consider any two basis test-function schemas, ((u (( sem and (((o)) ((b))) with m monotone curves. Suppose the two schemas' 1st through (m - 2)-th monotone curves are the same, but the (m - 1)th (i.e. their last) monotone curve's endpoint different by index. That is,
Vi E [m 2], ví (vi)' and vá (vS)
u/-11 (vl (u/"11y'
m-1 (1²2 1---- 1y
We claim that the set activations of these two "adjacent" schema must share an interior point:
int(A(Y (((((A(((())))))))) ((ri.01))e n int((A(Y(()))) (od))))))))) #
Suppose ((( . has M segments and Y ((oo))( smmm has M' segments? Because the two schema have the same monotone curves except the last monotone curve, then there are two possibilities:
m- and ( < (yr-1)) One can interpret these monotone curves as "moving downward",, Either vi- < y/2
since the (m - 1 1t monotone curve of Y ((vs (())pp) (resp. Y((o))) (((o)))) has M') has start-point on line y m-1 (resp. (y) and end-point on line y m-1 (resp. (y)- Note the lines with lower index have higher slope by convention (i.c. s1 largest).
Or yl
V22 m-1 and 1y (3/ Iy One can interpret these monotone curves as "moving upward".
WLOG, consider just the first case (the second one utilizes an analogous argument). Then, since y/ yn-! < y m-1 the last monotone curve is moving downward. Suppose WLOG that the monotone curve which starts line (v1" (0,"-10 y and ends line -1y moves down more line than the monotone curve which starts line nn and ends line m-1
Note: the two schema have same number monotone curves, hut different numbers segments
54

---

Non-Asymptotic Length Generalization
Thus, M M +-1 1. Moreover, the set of segments which make up the two schema are similar: for all j [M], segment of (uil lies in the same sector as segment j of Y (llv)) ((loo)""""))))eem")) Meanwhile, segment M + of has no counterpart in (()
To show connectedness, we need to exhibit a point (Bi...., E [0, 1]th that is in the interior of A ((i..)))Ne and A(Y (oloy..)))))emmm>>
For schema Yoo wgllee (resp. Y((lu)) (ug)) )r there is linear transformation L (resp. L') that maps the set of valid segment lengths A (000(
(Ytof ((of)e))) E [0, 11 (resp. A (000((((ss)))) (KLtef)). (vi)"))=t(m) E [0, 10 ) of schema Y(oi hetm) (((O)))) ((67)))- to the set of activations A(Y ((n kelo E [0, 1] (resp. A(Y Moyy (oo.y.197) (o5Y))))))) E [0, 1]*).
(resp.
Being rank l (see bullet point of Lemma E.33), L (resp. I') will map interior points in (M (V (eei.))))etm (resp.
(M two settings of the lengths of the segments of the two schema (a1....,a.r) and (b)...., b.....,.))) = (bI,..., bur: bM++). ) that are interior points in their respective polytopes A (MO (Y (Y(of v5llemm) (resp. A (XAOOX (X((oF)) (o5))) )), that give rise to
A(X((o)))) A (M²) (Y (CC (ooooi(((o))))) (pi)) to interior points of ((x (oi me) (resp. ((OO)) (old)r )). Thus, it suffices to exhibit
the same (BI.... B&) E [0, 1]
Towards this goal, we are interested in the regime where bxs+1 d << 1 and Vj E [M].aj length has slack with respect to its constraint defined in Lemma E.6. Suppose by Lemma E.6 that the constraints for the first M segments for schema (((o)))((x)))) are:
aj x bj. and where each segment
bj
bi Vj E [M]
4j
We'll now describe how to set {aj]eeM and (by) he(ar-- We will largely ignore the normalization conditions that Ejena 0j- = 1 and E by 1, but only require that the total length is the same: Σ}E[M] Oj - -E by >> 0.
For e, 0, set b, and for (2, (2...., .), sequentially assign by only constraint for ba+1 is that it is nonnegative, being the last segment). (by) [ is a valid set of segment lengths respecting the constraints imposed by schema (((())) (((l)))..v)))))eeetm as per Lemma E. {b; (be)se(a++)) is also an interior point of (AM0 (Y ((0))) (oro))(())))))))))) since each constraint has slack 6 > 0 0.
q: Σí= b, + Set bar+1 8 (where the
Now, suppose that the (M + 1)th segment of Y( (((oE) ((6))))))))))))) lies in sector i.. Because each basis schema spans all k lines, then there exists some j. E [M/] such that segment j. in Y ((fiwthheem is also in sector i, Set {a:} as follows.
Vj E [M] - (i+), set aj bj Finally, set aj. = bj. +
We now need to argue this is valid assignment of {a:}, respecting the constraints segments imposed by the schema Y(or (tllem) Because the first M segments of Y(Oo)) (((ot))) (4)))) are the same as the M segments of Y ((o) va)) then these segments have the same constraints.
follows that for all j Σ j., aj meets its constraint, For subsequent segments, due to the extra contribution on aj., we will need to argue that their constraint is still met with some nonzero slack. The ith constraint after j will have its slack lessened by at most 8 [maxp.oez.lpl.og ( < 8TM & 87*2 where we used that S M < k2 by Corollary 15
Thus, as long as 5 < T.2. then this setting of (a, hE([) will still satisfy each constraint of Y ((1i)0))) with nonzero slack.
a3
Pi
a Vj
[M]
4j
55

---

Non-Asymptotic Length Generalization
Thus, {ag))e(an is an interior point of A A (Yth ((wf.w5))eemm)
Finally, the segments (ajbem and {bi induce the same (BiJer since the sum of the segment lengths each sectoris is the same. This proves that:
int(A (wd. n (iniinnt(tttaaantiii ((ooe):-(()))eee
Edges Between Levels L and L+11 Consider any schema Y ((vi.)))) eemmm> (((o))(())))) with m - 2 and m monotone curves, respectively, where (((wv)) (vA))) 's first - 2 monotone curves are the same as ((()) .v)))etm--1
m 2 monotone curves. Moreover, let schema Y (((o))) be such that:
In the case that 1y < (y2" th y, then (31 Th
1mmm-y y + (y22 T0 1y. Iy.
In the case that (v] fy > th 1y, then (3/ th ly - = (y2" p (y
Instead schema of 2 monotone curves, schema ((vf.w5)eejm. can also be thought of as schema of 1 monotone curves, where the last monotone curves will only cross the line with index y/m²² yー~ Thus, these two schema can be thought of as having their final (m - 1) monotone curves' endpoints differ by one line, which reduces to the case above with two schema in the same level. Using exactly the same argument as in the previous section with two schema in the same level, we can conclude that
int (A( (nt((A(())))) ((tt:)))))mm=)))) int(((( ((oA(((()))))))) (e)r)))))))))))))))))) +
Edges Between Two Connected Components. In our graph where basis schema are nodes, we now have two connected components:
Schemas where the first monotone curve is monotone (up) curve from lines &s to
Schemas where the first monotone curve is monotone (down) curve from lines to k.
Within each of these connected components, we have proved connectedness with the previous two cases, by connecting schemas of the same prefix (of monotone curves) and the same level, and schemas of the same prefix and different levels.
The nodes in the first connected component will all connect in tree to the schema consisting of single monotone curve from lines & to 1. The nodes in the second connected component will all connect in a tree to the schema consisting of a single monotone curve from lines to
Let Y be the schema for m = with single monotone (up) curve from line to 1, and be the schema for m = 3 with two monotone curves: one monotone (down) curve from line 1 to i and then a monotone (up) curve from A 2. These are two representatives from the two aforementioned connected components. We claim that:
int int(A(Y)) n int (n())) *
We will start with an interior point for Z. Suppose it has segment lengths 21, 21...., 2k+1. ..., 82k, where 21 is above line 1, F is below line k and segment 22k lies above line 2 and below line 1, with end-point on line 2.
Again, ignore the normalization condition that Eie(an z 1. For e > O, we assign values to the segments as follows.
21 =
Pi i-1
V2 SiS 2h
1,
2j
41 j=1
56

---

Non-Asymptotic Length Generalization
Note that since 224 is the last segment of the schema, it need not cross sector and need only and re-cross line 2. Therefore, it has constraints under schema Z except that 22k 2 0. However, the key idea is that choose for 22k be sufficiently large so as to satisfy the constraint needed to cross to line 1 from line 2.
2k
P2k
22k
2j + 6
Q2k
j=1
Such (Zitvej2u). after normalization, exists in the (relative) interior of (Z).
We claim that rearranging the segments [ep into a monotone (up) curve (y1,.... 3k+1) with slack will always be possible for any > O. This essentially follows from Lemma E. we have intentionally set #2k 92x 2==1 Zj +
2k-1
large enough to cross from line 2 to line I (and have its end-poin on line 1). More precisely, the following constraints are met by { hE(2A)-
(-1 Pi
Ak 2
2
2j
+
91
j=l
Pt
Σ
Bj + e
jši 1:a; in sector 2 328+3-1)
Then, we obtain a valid monotone curve with segment lengths (y),,..,, 2/++1) by setting:
y1 1
yk+1 21
1/4 21+h 2k+2-1, 2
Thus, the large value of P2k enables the re-arranged test-function of monotone schema cross from line 2 to line 1. Finally, there is no constraint on y/++1, all constraints of the schema Y are satisfied. This re-arrangement will have slack min(e, V1, 11++1 2 because each of the original constraints in Z the segments 21,..., 22k-1 well as the "pssudd-coostraing we imposed on 22% only got looser in this rearrangement, and there is no constraint on yk++1 Thus, the rearranged monotone curve, after normalization of the segment lengths, is in the interior of (Y).
} and } are both interior in their respective polytopes and induce the same activations (BI...., BR) since the segments of } } are just re- er-aranggeeen of the segments of {2:}. and Ei 2 = Eie(e+1j ys. Thus, they give rise to the same interior point (B,,..,, B&) E int(A(Y)), (Bi,..., B&) E int(A(Z)) so int(A(Y)) int(((Z)) + 0.
These edges demonstrate that the graph is connected, proving the Lemma.
Proof of Lemma E.30.
Lemma E.35. (Lemma E.30, restated) for every C-RASP2 with K(f) heads, have that > 0 and Eie(kin d 2, then for any f. I' E C-RASP2 that are not equal, with and K' heads respectively, then f and f will differ on some continuous lest-function, V. which strictly satisfies the second layer inequalities. That is, with max K, K") S S K K' distinct heads between f and fr, let (B,(),.... Bx(V)) be the activations induced by y. Then, either:
K
X (,od( z
K'
D (1) < =
57

---

Non-Asymptotic Length Generalization
Or,
K X ())
K' X (a z
Proof of Lemma& E.30. Fix f. f' and their & distinct slopes (es Suppose f. f differ on some discrete test-function X. We want show that there must be continuous test-function that strictly satisfy the two inequalities strictly and distinguishes f and f'
Let's consider the k-dimensional set A({s)) c [0, 1].. A((s)))) is equal the union of finite number of convex sets by Corollary E. 14 and Lemma E.16
A((s:hee())= =
U
A(Y (ot (chlm))
melkd) valid (vvi
sil C(I.....b)"
Now consider two halfspaces H1, H2, induced by the second layers of ff and f'.
K
H1 : (BER
Σ A Bond(1.)) > 2}
H2: = (BER D/aaa12 >
First, we cannot have that H1 H2, as then f and f' must share the same heads their first layer and also have the same coefficients in the second layer. Thus, f f", contradicting the original assumption that f and f' are not equal (as witnessed by X)).
Thus, H, * Hz. Denote
L = [B R
A Bon((1) =2}
K'
:= = [ R
X(Bont(2.)) = 2/}
H1 # H2 implies L1 + Lz. Now, there are two cases, given by whether L, and L2 have nonzero intersection or not.
Case 1: Ta O La2
H, H2 divide I into 4 quadrants. Denote the (+, +) quadrant as H, O H2, (+. -) quadrant H, HHS (-, +) quadrant as H n H2 and (---) quadrant as H HS.
Towards contradiction, let us consider all possible A({s)):) such that the following Condition holds.
(Condition there is no B A((s)))) in the +) and (+, -) quadrants such that:
58

---

Non-Asymptotic Length Generalization
(,d((1)) 22
K'
X Bor(( <
1=1
X B.d(1.)) <2
K
(o > o
1=1
For ease notation, index each basis schema of Corollary E.14 with j E [N&), where N₁ (= 1) is the total number of basis schema, that A({=):)) = No Aj. Thus, Condition I must also apply each Aj, Vj E [Na]]
In order that A, satisfies Condition I, there is only three convex possibilities:
1. (Type 1) Aj is convex subset of a (k- 1)ddieension plane that has nonzero intersection with the (I: 1 2)- dimensional intersection of O L1 L2 and that is subset of
[cl(H)) U [ n H5.
2. (Type II) Ay is a convex subset of the quadrant ((1)) (cl(H) where:
K
A B,d(11 2
X Bord(2.)) 2 z'
3. (Type III) A, is convex subset of the quadrant, Hq n HS, where:
K X, Bodd(L,)) S
K'
X.Bo S
Lemma E.33 implies that it is impossible for any Aj to be Type since the dimension of Type sets is k - but Ay is dimension k.
Lemma E.34 implies that either all A, are type all A, are type III, which can be seen as follows. Suppose towards contradiction that there was A, of type II and separate Ay of type III. First, point O T. Lg can be interior point of any Aj. because O is & dimensional subspace, and it is impossible for La-ball centered at any point in O of any nonzero radius and dimension & to be completely contained in (cl(H,) cll (2)) U [H n H C UNN Aj, as such a ball would always have non-empty intersection with H₃ int(H)) and H2 n int (HG). Thus, O disjoint from Uje(Na) (A)). Because there is an A, of type II and a separate A₂ of type III, part of U int(A)) (Az) is contained in cl(H)) n cl22)) and part of it is contained in Hi n H5. However, since no point in O can be in No int (Az), then UN =1 int( is not connected (i.e. it is the union of two non-empty, separated sets). This contradicts Lemma E.34. Thus, all A, must be type they must all be type III.
59

---

Non-Asymptotic Length Generalization
Finally, observe that (0, .0,...., 0) E A((s)))) U Aj, realized by test-function which has slope 0 everywhere. Also, (L,.... E A(fs:))) = U Aj. realized by rest-function which has slope everywhere.
Suppose all A, were type II. At least one A, must contain (0, (O.....0) 0), but if (O......) 0) is in the quadrant, cl(H1) n cl H2)) this implies:
K'
Σ (2, 0))=
i=1
K
0 =
Σ
(A
-=1
This contradicts the assumption that 2, > 0.
Now, suppose all Ay were type III. At least one A₁ must contain (1...., 1), but (1, 1) is in the quadrant, Hq 0 H5. this implies:
K'
Σ (X/
K
Σ (A-1)s:
This contradicts the assumption that Σ X > = and Σ X z'
In short, 2 > and Σi((K(() A > z for all functions in f E C-RASP2 = A({s:ks) does not satisfy Condition I. Thus, there exists B E (())))). realized by a continuous test-function, in the (-, +) and (+, -) quadrants such that:
X, (, >
K'
X₂ Bord(2.0) <²
or
X, (,
K'
X Bodd(2.) >
Case 2: L2 = 0.
The argument here similar. We know L1, L2 are parallel hyperplanes which never intersect. We will argue that it is still true that (A})e(Nz) are either all type II or all type III, and then reach a contradiction with the assumption that >> and EleK(( A for all functions in C-RASP2 Given that L1, Le are parallel, consider two subcases.
Let (+.-), (+, -) denote the subcase where halfspace H1, H2 have the same parity, but their intercept term is different. example of this are two halfspaces: "r y > 2, + y > 1"
60

---

Non-Asymptotic Length Generalization
Let (-; +), (+, -) be the subcase where 11, Hg have opposite parities. An example of this are the two halfspaces: 2, y > 1"
Subcase 1: (+. -), (+. In this case, in order that the planes are not identical, there is a nonzero difference in the intercept term between L1. Lg. By Lemma E.34, since UJE(N.) (A)( is connected, then {A, [J))))NN)) are either all type II or all type
III, via similar argument as Case 1, which contradicts that 2, 2' 0, and E d and E X z' respectively. Thus, Condition I cannot hold.
Subcase 2: (+. (-, + In this case, either cl(H1) (22 * 9 or inf(Hf) n int H$) # 0. Once again, {Ashje(Na) are either all type or all type III, contradicting that z' >> 0, and Σ = d > and Σ X > z' respectively. Thus, Condition cannot hold.
Here a Corollary of Lemma E.34 which will be useful in strengthening Lemma E.30, which will let us improve the final bound from ((TO(k))) (a (l))))))) to ((T)(K)) (a)1)).
Corollary E.36. (Connectedness of inninian ( (s (E())) Define ( te(s as the set of activations by basis schema
where E (2. That is, there is only either one two monotone curves in the schema.
2 (23((5))iE(H) =
U
A(Y (67, (e)eem))
me (2,3), (aai) (Lui- Cf
Then, we claim that UmE3(233 volid Uii volld val (U ( (001 is connected.
Proof. We have that (2,((18))E11)) = A( U UjE(2__.E-) A(Y (10.6.))))))))))))) U
A((()))))))) U USe A( (Y(naannn)))) USE(2....k-I) (0.((0
The connectedness of int(A(()a U
U int (Y..())))...)))) U UJE(2.... ((((A((())))0:))))))) follows from inspecting the edges in the graph construction in Lemma E.34.
In the sections where we analyzed edges between nodes in the same level and between consecutive levels, it follows that:
Vj E (2....,k - 1}; node (((.)))(0))) connected to node (((L.))(43))6)))))
And
Vj E . 1}, node ((111)))111))) is connected to node ((111))())))
In the final section the proof of Lemma E,34, we showed that
node Y (L.))) is connected to node (((1,))
As corollary, we can strengthen Lemma E.30 to the following.
Lemma E.37. (Stronger version of Lemma E0) for every f C-RASP2 with K(f) heads, we have that >> 0 and Eserern d > 2, then for any f. C-RASP2 that are equal, with K and K' heads respectively, then and I' will differ on some continuous test-function, V. which strictly satisfies the second layer inequalities. That is, with max(Ks K, K') S K KK distinct heads between f and fr, let (B,(),.... ,,())) be the activations induced by y. Then, either:
K
X Bond(
(( <
61

---

Non-Asymptotic Length Generalization
Or,
K
X (, ())
K' X > _'
In addition, Y will be of a basis schema Y with either one or two monotone curves: Y E (Y sheeem m (2,3), valid {(y, biemmm C fI....,k)) k. In particular, the number of segments M in the schema of will be most 2 k instead of k2 for general basis schema.
Proof. We repeat the proof of Lemma E.30, but with (nt(Aag((fs))ee)) substituted for A (Ess)ee()) and Corollary E.36
substituted for Lemma E.34. Note that int (22 ({: ((()))))) still contains the points (O....,,) 0) E [0, 1 and (1,...,1) 1) [o, 1 as well, as both of these are realized by a test-function where the slope everywhere is equal to everywhere and everywhere, respectively, which are both of schemas with just one monotone curve.
62


Reviews:
[{"review_id": "cI94Y3JEW5", "reviewer": "Reviewer_qTut", "summary": "Taking up recent interest in length generalization of transformers and similar models, this paper studies length generalization for three formal models: DFAs, CFGs, and two-layer C-RASP, with the latter being the main technical contribution. C-RASP has recently been proposed as a formal model of some computations performed by transformers. The present paper shows that programs in two-layer sub-fragments of C-RASP can be identified from inputs up to an explicit computable bound (polynomial in precision, super-exponential in the number of heads). This is shown using ingenious arguments based on convex geometry. As such, it provides a potential path towards proving non-asymptotic quantitative length generalization guarantees.\n\n## update after rebuttal\n\nI maintain the stated concerns after the rebuttal. I believe that the authors and I are on the same page about the presence of these weaknesses.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer qTut for their time, detailed comments, and constructive criticism.\n\n**Author statement:**\nThe 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.\n- 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.\n- 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.\n- Results for DFAs and CFGs unchanged.\n\nSource of error:\n- Lemma A.24 in line 1557\n\nWe 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.\n\n**Addressing Reviewer Concerns:**\n> it remains open how minimum-complexity inference based on C-RASP complexity is linked to training transformers \n\nThis 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.\n- Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].\n- Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].\n- The RASP-L conjecture [3] suggests that transformers are biased towards learning functions of short RASP-L program length.\n\n[1] Abbe et. al. arxiv.org/pdf/2301.13105\n\n[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316\n\n[3] Zhou et. al. arxiv.org/abs/2310.16028\n\n> Section 6 is very hard to read.\n\nWe apologize for the lack of clarity in Section 6 and thank the reviewer for their patience in reading through it. We will rewrite it.\n\n> line 333, left col: why \"s_k\" not \"s_N\"?\n\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\n$N$ is the length of the discrete test-function (equivalently, of the string which corresponds to the discrete test-function).\nThe 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$.\n\n$\\forall i \\in[k], B_i := \\frac{1}{N} \\sum_{j = 1}^N 1[ps(x)_j > s_i \\cdot j]$\n\n> line 341, left col: \"they're in [0,1]\": does this mean \"both are subsets of [0,1]\"?\n\nYes\n\n> line 356, right col: what does \"B\" range over?\n\n$(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$.\n\n> line 413, left col: \"the linear constraint for the i-th face\" -- a \"constraint\" would be an equation, whereas here a number is referenced\n\nA 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.\n\n> line 427, right col: what does \"higher-precision variants\" refer to\n\nThis referred to Definition A.43 on line 2255 on page 42. However, the Dyck1 results are no longer valid.\n\n> what does the \"si\" in A_{si} stand for\n\nsimplest interpolator\n\n> 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.\n\nWe 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.\n\n> could acknowledge link to Huang et al more\n\nWill do.", "claims_and_evidence": "The claims as described in Abstract, Introduction, and Conclusion are supported by convincing evidence.", "methods_and_evaluation_criteria": "N/A. No empirical evaluation is conducted (nor is necessarily needed for this kind of work).", "theoretical_claims": "I checked the proofs about C-RASP at a high level and they appear plausible to me. Within the reviewing timeframe, I could not check all details. While I did not check that the claimed scaling of input length is correct, I believe that a statement of this type can be obtained with the techniques used in this paper.", "experimental_designs_or_analyses": "N/A (no experiments).", "relation_to_broader_scientific_literature": "The paper follows up on recent work arguing that length generalization in transformers can be predicted based on RASP fragments (RASP-L in Zhou et al 2024, C-RASP in Huang et al 2024, both cited in the paper). The key contribution is to show that, for some small RASP fragment (two-layer C-RASP), there are computable upper bounds on the lengths needed to allow full identification (hence, generalization) within the given hypothesis class.\n\nI think the paper could acknowledge the link to Huang et al 2024 [4] a bit more. That work is mentioned once in passing in Section 2, but it is actually quite related in that (1) it also studies length-generalization for C-RASP, (2) also aims to formalize the RASP-L conjecture, (3) also uses a minimum-complexity interpolator, albeit with a different kind of complexity measure that applies to transformers instead of automata or C-RASP programs. There is of course a clear distinguishing property of the current paper, namely that it provides a non-asymptotic guarantee, and mentioning the relation to that prior work where relevant could help contextualize the paper better.\n\n[4] Huang et al, A Formal Framework for Understanding Length Generalization in Transformers, ICLR 2025", "essential_references_not_discussed": "I believe all essential references are discussed.", "other_strengths_and_weaknesses": "Strengths\n\n- The paper tackles a very important theoretical problem of current interest: providing non-asymptotic length generalization guarantees, and links to a recent line of work on RASP variants.\n\n- The paper is upfront about some key limitations of the proposed setup.\n\nWeaknesses\n\n- I believe the biggest weakness of the paper is that the guarantees apply not to machine learning models themselves, but to the C-RASP formalism. As such, the paper proves an (interesting) result about that logical formalism, not about machine learning methods. It remains open (or at least isn't made explicit) how minimum-complexity inference based on C-RASP complexity can be linked at all to training transformers or other machine learning models. The authors are correct in stating that understanding SGD training is extremely intractable in this context, but at least linking to minimum-complexity inference based on transformers' complexities (e.g., parameter weight norms) would help make the relevance to machine learning more convincing. Besides proving theoretical links, experiments could also be helpful.\n\n- Section 6 is very hard to read (some concrete questions below under \"Questions for Authors\"). I'd suggest a major rewrite of this section to reduce the technical burden on the reader, and minimally avoid any undefined formal objects.", "other_comments_or_suggestions": "- around line 308 (right column): it is argued that PARITY is not expressible by transformers due to the AC0 bound. However, many C-RASP functions, such as Dyck-1, are also not in AC0. Relevant references re the difficulty of PARITY include [1,2]. I think state tracking problems believed to be outside of TC0 [3] might be a more apt example here.\n\n[1] Hahn and Rofin, Why are Sensitive Functions Hard for Transformers?, ACL 2024\n[2] Chiang and Cholak, Overcoming a theoretical limitation of self-attention, ACL 2022\n[3] Merrill and Sabharwal, The Parallelism Tradeoff: Limitations of Log-Precision Transformers, TACL 2023\n\n- what does the \"si\" in A_{si} in Lemma 3.1 stand for?", "questions_for_authors": "line 333, left column: why \"s_k\" not \"s_N\"?\n\nline 341, left column: \"they're in [0,1]\": does this mean \"both are subsets of [0,1]\"?\n\nline 356, right column: what does \"B\" range over?\n\nline 361, right column: the completeness equation is hard to grasp at this point, e.g. \"valid\" has not been introduced. A prose statement could be more comprehensible.\n\nline 413, left column: \"the linear constraint for the i-th face\" -- a \"constraint\" would be an equation, whereas here a number is referenced -- does \"constraint\" refer to the linear coefficient of the face?\n\nline 427, right column: \"and its higher-precision variants\" -- what does this refer to?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AMNxKo2ID1", "reviewer": "Reviewer_5Dit", "summary": "The paper considers the question of the theory of length generalization for abstract classes of models, with in mind applications to extending the theory underlying important questions about prevalent models such as transformers.\n\nHere length generalization denotes the property that if the model is perfectly accurate on length \\le L inputs, then it will be perfectly accurate on inputs of any length. The questions addressed are  \n1) Does my model/hypothesis class allow for length-generalization?\n2) If the answer to (1) is affirmative, then what is the value of L that guarantees this length-generalization?\n\nFor (1) the paper gives some negative results in line with work by Angluin on context-free grammars. \nImportantly, the paper shows that (1) has positive answer for finite automata and for 2-layer C-RASP programs (modelling 2-layer transformers). The case of deeper (3 or more layer) C-RASP is left for future work.\n\nWhen (1) has a positive answer, then the answer to (2) is formulated in terms of the complexity of models within the given class.\n\nThe guarantees are done in an abstract setting, using \"minimum-complexity interpolator\" algorithms, for which existence results are known, but which are in practice hard to find. Nevertheless, this is the first such result, and includes positive results for C-RASP, making this a possibly useful read for anyone interested in theoretical machine learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer 5Dit for their time, detailed comments, and constructive criticism.\n\n**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.\n- 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.\n- 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.\n- Results for DFAs and CFGs unchanged.\n\nSource of error:\n\n- Lemma A.24 in line 1557\n\nWe 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.\n\n**Addressing Reviewer Concerns:**\n\n> the main weakness is the areas with lack of clarity in the explanation in the paper.\n\nWe 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. \n\n> Line 109 second col: \"a complexity\" is supposed to have what properties? \n\nThe 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.\n\n> Algorithm 1: what does \"interpolator\" refer to\n\nWe 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$.\n\n> Line 119 second col; Explain \"are very nontrivial\"\n\nWe 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.\n\n> Line 124 second col \"the learner\" - what is the difference \n\n“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.\n\n> 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?\n\n(1) Yes; $A_{si}$ always refers to Algorithm 1.\n\n(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$.\n\n> Line 268-269 first col: be more precise with this (undecidability) statement\n\nThe 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)$.\n\n> Line 311-316 second col: \"This inability of the transformer … \"\n\nIf 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. \n\n> Definition 6.2 seems contradictory\n\nThe 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.\n\n> Length generalization to accuracy 99%\n\nThis 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.\nMore discussion in rebuttal to Reviewer YXKG at the bottom.", "claims_and_evidence": "I think that the claims and limitations are well balanced.\n\nIt is sometimes hard to parse the actual presentation of the claims, and one has to read the paper at least twice in order to understand the claims.", "methods_and_evaluation_criteria": "The paper does not have experiments.", "theoretical_claims": "I did not have a 100% read of the 50 pages of the paper, but I follow the proof sketches and they seem intuitively correct.\n\nI have read at 100% only the proof of theorem 5.1 which seems well argued, it is actually much better written than the first 5-6 pages of the paper. \nThis gave me confidence that the remainder of the proofs should also be well written.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "I think that this is an important step forward in the theory of length-generalization.", "essential_references_not_discussed": "I am not aware of any.", "other_strengths_and_weaknesses": "I think the main weakness is the areas with lack of clarity in the explanation in the paper. \n\nSomehow the results seem presented without much care, and this is surprising as it should be simpler to do than to produce proofs for the results.\n\nI will detail the above in the \"other comments\" section.", "other_comments_or_suggestions": "Line 109 second column: \"a complexity\" is supposed to have what properties? can you give the reader an idea about what you have in mind?\n\nLine 113 first column: \"takes in a training set\" would have to be \"takes as an input a training set\"\n\nLine 119 and rest of the paper: two functions are equal if they take the same value and have the same domain, so why don't you use that notion and instead rename it by saying \"they are equivalent\"? For functions this is just the notion of equality. For algorithms, two algorithms are equivalent if they induce equal functions. But here you introduce a new name for the usual equality of functions, and this is very confusing. Please be precise about this wording? \n\nLine 130-131 \"Identification is synonymous with exactly learning or recovering the ground truth\" -- it is not, the concept is more complicated than this summary.. perhaps try being precise with the descriptions, so that the reader doesn't have to guess what you were thinking there.\n\nLine 139 \"will allow you to correctly predict\" -- I guess it's not \"you\" or \"me\" or a specific person, so I'd remove the word \"you\" from this sentence\n\nLine 155, add \"where c is a natural number\"\n\nAbout algorithm 1 and in general: can you maybe spend a few words regarding what the term \"interpolator\" refers to? what is it interpolating?\n\nLine 119 second column \"are very nontrivial\" -- what does that mean exactly? I think you can be more specific/precise rather than handwaving it like that.\n\nLine 124 second column \"the learner\" -- what is the difference between that and the algorithm itself? Or how is \\mathcal A_{si} defined? In the paper this notion of \"learner\" is never defined, and to me it seems like there is no learning involved in your paper so I've been confused every time it talks about \"learner\" or \"learning\". Is it really necessary to use that kind of terminology?\n\nLine 127 second column I'd add \"in the following sense\", since Lemma 3.1 is making precise the idea (the adjective \"best\") hinted at in the preceding paragraph.\n\n Line 189 - 190 first column: Is A_{si} the same as before? and what does it mean for it to \"see inputs of length at least\" some number?\n\nAbout the definition of context-free grammars: Of course you know that this is not the correct definition. This is a definition of any grammar. For being context-free you have to put some restriction on the production rules, similarly to the case of linear CFG's that you wrote correctly.\n\nLine 171-172 second column: \"clean\" means what? what detergent was it cleaned with?\n\nIn definition 3.6, it would be better to introduce the parameters before writing the formulas, not at the end of the statement.. So the reader doesn't have to read twice in order to parse the statements.\n\nLine 268-269 first column \"it undecidable\" -- add the verb \"is\". Besides this typo, you should also be more precise with this statement.. do you mean that \na) there exist two CFGs for which it is undecidable whether they are equivalent, or \nb) for any CFG there exists another one for which it is undecidable whether the two are equivalent or\nc) there exists a pair of CFGs for which it is undecidable whether they are equivalent ?\n\nLine 232-233 second column: the sentence about \"Unfortunately [..] rather sudden\" seems useless, consider removing it. \n\nLine 311-316 second column: \"This inability of the transformer architecture to even express the ground truth should be part of the reason why empirical length generalization results only show limited length generalization\" -- what do you mean by \"should be part of the reason why\"? and why should it be part of that? this statement would be interesting if it were justified. But here it's stated a bit out of the blue, and without an actual argument it is empty. Please write the argument in some detail? (Also if you expand this a bit, it makes you careful about not mixing up cause with effect, a possible fallacy which is impossible to check with the current wording)\n\nDefinition 6.2 seems to be almost contradicting itself and a bit weird: the part about a tuple of rational numbers, when the tuple is a singleton, is a distinct definition than the case about single numbers. For example, 37/5 has 37-precision (as the larger between 37 and,5 is 37), whereas { 37/5 } has 5-precision (as the common denominator is 5)? And the fraction 370 / 50 has 370 precision or does it have 37 precision like 37/5 has? \n\nMaybe check that this definition being weird does not have consequences in the places in which it is used?", "questions_for_authors": "A question I have is if the authors can discuss a bit what are extensions of the notion of length generalization to real-life cases in which we don't check for \"perfect generalization\" but rather for \"generalization to accuracy 99%\", i.e. how would the methods extend to probabilistical guarantees as in PAC learning? This is important to know for practical reasons.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QYvfampYzu", "reviewer": "Reviewer_CEK9", "summary": "The paper provides new theoretical results related to criteria on a training set such that an idealized learner can learn a function that exhibits length generalization.\n\nThe paper considers an idealized learner, termed the Minimum-Complexity Interpolator. The learner is defined with respect to a hypothesis class (i.e. set of functions) and a complexity function defined over this set. The learner learns the lowest complexity function in the set that perfectly fits the training data.\n\nThe paper then studies, for several different tasks, what is the maximum input length required in the training set such that for any data generating function in the hypothesis class, the learner is guaranteed to learn a function that exhibits length generalization.\n\nThe paper derives results related to the upper bound on this maximum input length for three settings:\n\n* n-state Deterministic Finite Automata (DFA) – deriving a bound of 2n-2\n* Context-Free Grammars (CFGs) – deriving a negative result\n* C-RASP: a class of functions mapping binary strings to binary labels, using the RASP derivative defined by Yang & Chiang, 2024. Prior work has shown that this class of functions is related to those expressible by Transformers (with some caveats related to whether the Transformer is assumed to be finite vs. infinite precision). These results apply to the Dyck-1 language studied by prior work.\n\n## Update after rebuttal\n\nThank you for your response and for being transparent about the issue identified with theorems 5.4 and 5.6. As the main result of 5.1 still holds, this does not significantly affect my judgement.\n\nDespite the limitations with respect to the potential gap between the theory and empirically observed behavior with real models and optimizers (which are clearly acknowledged by the authors and noted by the other reviewers) I still recommend acceptance for this paper. I think it brings not only a novel perspective, but also non-trivial theoretical results. I can see this work having implications for not only future theory work in this area, but also influencing how we design \"fair\" (i.e. that, minimally, there exists a plausible minimum complexity interpolator that exhibits the desired generalization behavior) splits to assess length generalization and other OOD generalizations, as well as potentially inspiring new methods that seek to add inductive biases to bridge the gap between the minimum complexity interpolator and empirically observed behavior.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer CEK9 for their time, detailed comments, and constructive criticism.\n\n**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.\n- 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.\n- 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.\n- Results for DFAs and CFGs unchanged.\n\nSource of error:\n- Lemma A.24 in line 1557\n\nWe 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.\n\n**Addressing Reviewer Concerns:** \n\n> the paper could be made relevant to a wider audience by discussing a broader range of prior work\n\nWe thank the reviewer for the very detailed list of references. We will add them in.\n\n> Shaw et. al. induced synchronous CFGs... I assume the apparent contradiction is resolved because ...\n\nYes, 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)$.\n\nIn 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.\n\n> The results hold for a minimum complexity interpolator…\n\nWe 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.\n\n- Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].\n\n- Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].\n\n- The RASP-L conjecture [3] suggests that transformers are biased towards learning functions of short RASP-L program length.\n\n[1] Abbe et. al. arxiv.org/pdf/2301.13105\n\n[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316\n\n[3] Zhou et. al. arxiv.org/abs/2310.16028\n\n> (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.\n\n(1) We agree\n\n(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.\n\n(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]).\n\nDue 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.\n\n[4] Liu et. al. arxiv.org/abs/2210.10749\n\n> define “non-asymptotic” upper bound vs. “asymptotic” upper bound\n\nWill 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$.", "claims_and_evidence": "Yes, the limitations of the key claims are discussed, i.e. that they do not consider expressibility of real architectures (e.g. finite-precision Transformers) and the idealized learner may not closely relate to the functions learned in practice (e.g. by SGD).", "methods_and_evaluation_criteria": "N/A - Purely theoretical results.", "theoretical_claims": "I did not check the correctness of the proofs in detail.", "experimental_designs_or_analyses": "N/A - Purely theoretical results.", "relation_to_broader_scientific_literature": "As far as I am aware, the new results are novel. \n\nThe paper not only offers new theoretical results, but also offers a new perspective on assessing the feasibility (albeit under idealized assumptions) of length generalization from finite length training sets.", "essential_references_not_discussed": "As far as I'm aware, there are no essential references missing that directly relate to the theoretical results.\n\nHowever, I do think that the paper could be improved and made relevant to a wider audience by discussing a broader range of prior work for the camera ready, e.g.:\n\n* The connection with the RASP-L conjecture was good to see discussed. (Concurrent work) Shaw et al. 2024 (https://arxiv.org/abs/2410.18077) also discuss the RASP-L conjecture and define the notion of program minimality with respect to a training set, which might be relevant in this context. They connect this notion to the existence of a local optimum for a Universal Transformer that exhibits length generalization. They then similarly compute the minimum input length required for such an optimum to exist, e.g. for addition. While clearly not the same as the current work, there are similarities in the ambition to characterize necessary conditions on a training set that enable length generalization.\n* Empirical work that studies length generalization in Transformers related to Chomsky hierarchy complexity might be good to mention to provide context for the theoretical results in this paper: https://arxiv.org/abs/2207.02098, https://arxiv.org/abs/2305.16843, https://arxiv.org/abs/2009.11264  \n* Other theoretical work specific to Transformers: Hahn et al. 2020 (https://aclanthology.org/2020.tacl-1.11/) has negative theoretical findings for Transformers ability to express length invariant algorithms for parity and Dyck languages. Some of these results were subsequently discussed and extended in Chiang & Cholak, 2022 (https://arxiv.org/abs/2202.12172), providing a more positive result. \n* To provide more context for the negative results for CFG induction, it would be useful to understand how this relates to positive empirical results for inducing grammars that exhibit length generalization (using description length priors). For example, https://arxiv.org/abs/2010.12725 induced synchronous CFGs that exhibit length generalization on the SCAN benchmark using a description length prior over the grammars that appear similar to the complexity measure of CFGs studied in this paper. I assume the apparent contradiction is resolved because while the paper result holds for CFGs in general, many specific instances of CFGs may have a finite upper bound for identifying the underlying grammar? Or perhaps the difference between inducing CFGs and synchronous CFGs for transduction is critical here. Perhaps some discussion could help connect the results to the literature on linguistically-motivated models for length generalization.", "other_strengths_and_weaknesses": "(Note that my overall impression and score assume the correctness of the proofs, which I did not carefully verify)\n\nStrengths:\n\n* The paper offers a new perspective on the feasibility of inducing functions that exhibit length generalization from finite length training sets. Length-based splits have been popular to empirically probe the generalization capabilities of various models and learning algorithms, so it is useful to build a stronger theoretical foundation of when such generalization is even theoretically feasible (for an idealized learner).\n* The results on C-RASP are quite general, i.e. it is a very broad class of functions. It is also nice because it directly relates to the computational model of Transformers.\n* The negative CFG results could be of interest to the community working on linguistically-motived methods for compositional generalization.\n\nWeaknesses:\n\n* Although clearly acknowledged, the results hold for a “minimum complexity interpolator”, and there is no theoretical or empirical evidence that this learner behaves similarly to, e.g. Transformers trained with SGD. However, while some empirical results could relate various complexity measures to the actual inductive biases of Transformers, I don't think this is necessary for this paper, which already makes theoretical contributions.", "other_comments_or_suggestions": "Nits:\n\n* Section 1 - “(Zhou et al., 2023) make” > Use \\citet? This nit also applies to many other citations in the paper.\n* Section 1 - “A theoretical guarantee is particularly crucial here, as empirically verifying a model’s ability to generalize to arbitrarily long sequences is impractical, if not impossible.” > Nit: This claim seemed a bit strong. If such guarantees are “crucial”, then it seems problematic that the theoretical results do not hold for models trained in practice, e.g. with SGD. In practice, testing models on inputs that are arbitrarily longer than those seen during training seems sufficient for most applications.\n* It might be useful to clearly define what a “non-asymptotic” upper bound vs. “asymptomatic” upper bound in this context, given that it is such a key claim. Some readers might be familiar, but good to make explicit. Paragraph 2 of section 2 discusses this, but could maybe clarify this more directly and earlier.", "questions_for_authors": "None (see recommendations above)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "guYkShncak", "reviewer": "Reviewer_YXKG", "summary": "Summary: \nThe paper analyzes the minimum input-length required for learning length generalizable DFA, CFG and C-RASP programs and provides non-asymptotic bounds for the minimal length inputs to differentiate different DFA and C-RASP programs.\n \nStrengths:\nThe proof idea is quite interesting: the authors design a finite set of schemas that corresponds to the prefix behaviors of all possible inputs and maps them to convex polytopes. The analysis on binary sequences are then converted into geometric analysis in high-dimensional space, which provides an interesting perspective on how C-RASP programs process sequential inputs.\nThe proven C-RASP length generalization theorem and its proof idea can potentially serve as a critical step in showing how Transformers achieve length-generalization on certain classes of computational problems. This further strengthens the importance of the RASP-L conjecture.\n \nWeaknesses:\n \nThe proof sketch in the main content may be quite confusing without reading the supplementary materials. In particular, the author can provide more details on the “basis schemas” in the main content, which is a core contribution but quite confusing in the current way it’s written on page 7. In particular, it’s unclear what the $$Y_{\\{(y_1^i,y_2^i)\\}}$$ or $$m$$ refer to on page 7 since they are not properly explained. Figure 2 is also currently quite confusing since 1) the average prefix sums should be discrete instead of continuous for finite input lengths and 2) the “monotone” parts of the function are apparently not monotone. It is also not immediately clear why the number of basis schemas is finite. Although the exact meaning of the authors can be clarified by looking at the details of page 19 and 20, it would be better for readers if these confusions can be resolved by looking at the main paper and Figure 2 alone since these are critical parts of the paper’s contribution and should be made as explicit as possible. As such, I would recommend the authors spend more space explaining this portion of the paper.\n \nThe following concerns are regarding scope limitations rather than technical weaknesses:\nAlthough the authors showed an interesting perspective on length-generalization and C-RASP and provide a novel proof for a formal language theory result, there’s still a huge gap when viewed from the perspective of length-generalization of Transformers, which C-RASP is designed to model. Therefore, it is unclear whether the author’s main contributions can indeed lead to fundamental progress regarding Transformer models. In particular, according to my current understanding:\nIt is yet unclear whether there’s a training setting (i.e. loss function) for Transformers such that the optima correspond to the minimum C-RASP program interpolator on the training dataset.\nFor any given number of layers and heads, the C-RASP program have very restricted expressive capability compared to RASP or the full Transformer architecture\nThe proven results implies that, if ALL inputs of length at most O((KT)^{(O(K^2)}) are given to a minimum length C-RASP interpolator, then the resulting C-RASP program must be length-generalizable. However, since this require the dataset size to be exponential, this is highly unrealistic, so a more interesting result for the ML community might be probabilistic (i.e., the probability of a dataset of size D drawn according to some distribution over {0,1}^* to result in a length-generalizable C-RASP interpolator).\nThe exponential dependence on O(K^2) is also quite unrealistic for Transformer models, which would cause the length to explode even for K=5, for example.\nAs such, it is unclear whether the proven theorem can indeed be part of an a larger theorem regarding Transformer length generalization, or whether it would be easier to pursue a path without C-RASP as the intermediate language.\n \nDespite these limitations, the perspective introduced by the theorem and proof is quite interesting and may lead to further advancement in the general field of formal language theory and Transformers, and thus I recommend accepting the paper, especially after the proof clarification suggested earlier.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer YXKG for their time, detailed comments, and constructive criticism.\n\n**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.\n- 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.\n- 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.\n- Results for DFAs and CFGs unchanged.\n\nSource of error:\n- Lemma A.24 in line 1557\n\nWe 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.\n\n**Addressing Reviewer Concerns:**\n\n> The proof sketch in the main content may be quite confusing\n\nWe 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.\n\n> 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.\n\nThis 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.\n\n- Abbe et. al. find empirically that transformers are biased towards learning functions of low degree-profile [1].\n\n- Bhattamishra et. al. find empirically that transformers are biased towards learning functions of low sensitivity [2].\n\nIf 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.\n\n[1] Abbe et. al. arxiv.org/pdf/2301.13105\n\n[2] Bhattamishra et. al. arxiv.org/pdf/2211.12316\n\n[3] Zhou et. al. arxiv.org/abs/2310.16028\n\n> The C-RASP program have very restricted expressive capability\n\nWe agree.\n\n> The proven results imply that … since this require the dataset size to be exponential, this is highly unrealistic\n\nHaving 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)})}$).\n\n> A more interesting result might be probabilistic\n\nThis 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.\n\nIf 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.\n\nOne 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.", "claims_and_evidence": "There are 3 main theoretical claims of the paper, each of which is supported by corresponding theorems and proofs:\nnon-asymptomatic upper bound for length generalization for DFAs\nImpossibility result for non-asymptomatic upper bound for length generalization for CFGs\nnon-asymptomatic upper bound for length generalization for C-RASP", "methods_and_evaluation_criteria": "The paper uses the minimum length differentiating 2 C-RASP programs to study length-generalization of Transformer-based LLMs. There are apparent limitations in this approach, since it requires all inputs up to a given length to be given as training data for length generalization to occur. As a result, the training data size is exponential w.r.t. the length bound, which is already exponential w.r.t. the number of heads in the C-RASP program $K$. There paper also considers C-RASP programs of depth 2, which is a very limited setting. The paper also assumes that the learning process is a minimum complexity interpolator, but whether this indeed represents Transformer learning is unknown both theoretically or empirically. As such, there’s still a long way from this work towards solving the overarching problem.\nHaving the above said, since it’s the first work in this direction AFAIK, I believe the paper still provides decent contribution for the field.\nFor the proof, the authors design a finite set of schemas that corresponds to the prefix behaviors of all possible inputs and maps them to convex polytopes. The analysis on binary sequences are then converted into geometric analysis in high-dimensional space, which provides an interesting perspective on how C-RASP programs process sequential inputs.", "theoretical_claims": "The full proof (40 pages long) is apparently to long to be fully checked. I checked the main novel idea from page 19 to page 21, which makes sense assuming the correctness of lemmas in the first 8 pages. However, I would greatly appreciate if the authors can have a better proof sketch regarding the definition of test-functions and the proof of convexity in the main content.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper shows a condition for length-generalization of Transformer LLMs on simple computational problems (expressible by 2-layer C-RASP) assuming that the RASP-L conjecture is also true for C-RASP.\nPrevious works have mostly focused on expressiveness upper bounds and lower bounds, while this paper leverages the ideas and results (e.g., C-RASP) from these previous works work to approach the problem of length generalization.\nAlthough there any many limitations in the current work as discussed in “Methods”, the paper’s proof idea and perspective can be contributive for future work in the direction.", "essential_references_not_discussed": "I’m not aware of closely related works not mentioned in the paper", "other_strengths_and_weaknesses": "The proof sketch in the main content may be quite confusing without reading the supplementary materials. In particular, the author can provide more details on the “basis schemas” in the main content, which is a core contribution but quite confusing in the current way it’s written on page 7. In particular, it’s unclear what the $$Y_{\\{(y_1^i,y_2^i)\\}}$$ or $$m$$ refer to on page 7 since they are not properly explained. Figure 2 is also currently quite confusing since 1) the average prefix sums should be discrete instead of continuous for finite input lengths and 2) the “monotone” parts of the function are apparently not monotone. It is also not immediately clear why the number of basis schemas is finite. Although the exact meaning of the authors can be clarified by looking at the details of page 19 and 20, it would be better for readers if these confusions can be resolved by looking at the main paper and Figure 2 alone since these are critical parts of the paper’s contribution and should be made as explicit as possible. As such, I would recommend the authors spend more space explaining this portion of the paper.", "other_comments_or_suggestions": "I would suggest to drastically shorten the abstract to at most 1/2 the size. It currently sounds like an intro rather than a concise summary of results. I recommend only one sentence for motivation, once sentence for DFA+CFG results (since they are not the main contribution), 2 sentences for the C-RASP result, and once sentences on the proof method.\nSimilarly, the introduction section also contains too much motivation that are very far from the actual results shown in the paper.\nThe saved spaces can be use to provide a better description of the proof sketch.\nI believe that the paper would be good for acceptance with better organization and proof sketch", "questions_for_authors": "Are my following understanding of the current state of the problem and the practicality of the paper true?\nIt is yet unclear whether there’s a training setting (i.e. loss function) for Transformers such that the optima correspond to the minimum C-RASP program interpolator on the training dataset.\nFor any given number of layers and heads, the C-RASP program have very restricted expressive capability compared to RASP or the full Transformer architecture. Even though C-RASP is an upper bound on the expressiveness, it results in drastically larger number of heads and layers\nThe proven results implies that, if ALL inputs of length at most O((KT)^{(O(K^2)}) are given to a minimum length C-RASP interpolator, then the resulting C-RASP program must be length-generalizable. However, since this require the dataset size to be exponential, i.e. 2^O((KT)^{(O(K^2)})\nThe exponential dependence on O(K^2) is would cause the length to explode even for a Transformers with 5 heads, for example.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper develops an interesting theoretical perspective on length generalization in transformers using C-RASP models (a class of functions that is a superset of functions expressible by finite-precision transformers). All reviewers have commented on the technical novelty and rigour of the paper. There were some comments on improving the writing, which the authors are advised to incorporate in the camera-ready manuscript.
Decision: Accept (poster)