Low-Dimension-to-High-Dimension Generalization and Its Implications for Length Generalization

## Abstract

Abstract Low-Dimension-to-High-Dimension (LDHD) generalization is a special case of Out-of-Distribution (OOD) generalization, where the training data are restricted to a low-dimensional subspace of the high-dimensional testing space. Assuming that each instance is generated from a latent variable and the dimension of the latent variable reflects the problem scale, the inherent scaling challenge in length generalization can be captured by the LDHD generalization in the latent space. We theoretically demonstrate that LDHD generalization is generally unattainable without exploiting prior knowledge to provide appropriate inductive bias. Specifically, we explore LDHD generalization in Boolean functions. We verify that different architectures trained with (S)GD converge to min-degree interpolators w.r.t. different independent sets . LDHD generalization is achievable if and only if the target function coincides with this inductive bias. Applying the insights from LDHD generalization to length generalization, we explain the effectiveness of CoT as changing the structure latent space to enable better LDHD generalization. We also propose a principle for position embedding design to handle both the inherent LDHD generalization and the nuisances such as the data format. Following the principle, we propose a novel position embedding called RPE-Square that remedies the RPE for dealing with the data format nuisance.

## 1 Introduction

The field of learning to reason has gained significant popularity in the machine learning community due to its impressive performance in reasoning tasks such as natural language processing [, ], mathematics [, ], coding [], symbolic logic [, ], and planning [, ]. Reasoning problems inherently require generalization beyond the training distribution, a challenge known as Out-of-Distribution (OOD) generalization [, ]. One of the most significant challenges in OOD generalization is scaling, also known as *length generalization* [, ], where models trained on small-scale instances must generalize to large-scale instances. Length generalization is crucial because the size of sample spaces often increases exponentially with the complexity of reasoning problems, leading to intractable sample complexity and computational costs for models that do not achieve length generalization.

Numerous works have investigated the length generalization problem in various tasks and proposed various techniques that help scaling in practice, including modifications to model architectures [, , ], transformations in data formats [, ], prompt engineering for Large Language Models (LLMs) Wei et al. [], Feng et al. [].
While some techniques work uniformly well across a wide class of problems, many are fragile and even ad-hoc, applicable only to specific problems with certain formats [].
This can be largely attributed to the mismatch between the inherent problem scale and the formal scale in the input domain (e.g., the length of the input string in language models). We further elaborate the statement in Example 1.

###### Example 1 .

Consider the addition learning problem in the language domain, where the input is a string. For an $N$-digit-plus-$N$-digit (written as $N$-addition) addition of two numbers $x$ and $y$, where $x=x_{N-1}\dots x_{0}$, $y=y_{N-1}\dots y_{0}$, $x_{i},y_{i}\in\{0,\dots,9\}$ ($x_{N-1}>0$ or $y_{N-1}>0$), consider two formats of the instance: the Aligned and Reverse Format (ARF), where the instance is represented as “$\mathtt{x_{0}\dots x_{n-1}+y_{0}\dots y_{n-1}=}$”;
and the Unaligned and Reverse Format (URF), where the instance is represented as “$\mathtt{x_{0}\dots x_{n_{x}-1}+y_{0}\dots y_{n_{y}-1}=}$”, $n_{c}=\operatorname*{arg\,max}_{i}\{c_{i}\neq 0\},c\in\{x,y\}$. The formal scale in the language domain is the length of the string. However, the length of the input strings in neither format faithfully reflects the inherent problem scale: in ARF, the length of the input strings is always invariant; in URF, a shorter string may correspond to a larger scale than a longer string (e.g., $s_{1}=$“$1+1234=$” is $4$-addition, $s_{2}=$“$123+123=$” is $3$-addition; however, $|s_{1}|<|s_{2}|$). Furthermore, we find in experiments that Relative Position Embedding (RPE) improves the length generalization performance of Transformers for ARF, while it provides little benefit for the length generalization of Transformers for URF.

To develop robust and transferable methods for scalable models, it requires a formulation that captures the inherent scaling challenge of length generalization and is invariant to the nuisances such as data format. To do so, we first notice that in the length generalization of a wide range of problems, the instances can be seen as generated from some latent space whose dimension reflects the scale.

###### Example 2 (Addition) .

Let $\Sigma=\{0,\dots,9\}\times\{0,\dots,9\}$. The instance of $n$-addition $x_{n-1}\dots x_{0}+y_{n-1}\dots y_{0}$ can be represented by the state vector $h_{n}=\left[\left(x_{0},y_{0}\right),\dots,\left(x_{n-1},y_{n-1}\right)\right]$. The $k$-th dimension of $h_{n}$ corresponds to the $(k-1)$-th digits of the two addenda (i.e., $x_{k-1}$ and $y_{k-1}$). The expansion of the state vector in the dimension corresponds to the increase in the addendum digits. Therefore, the length generalization from $N_{0}$-addition to $N$-addition can be seen as a generalization from the low-dimensional latent space $\Sigma^{N_{0}}$ to the high-dimensional latent space $\Sigma^{N}$.

To catch the above intuition, we make the following assumption about the underlying data generation.

###### Assumption 1 (Data Generation in Length Generalization) .

The data generation process of an instance of scale $n$ with the concept $c$ is as follows:

- 1.
A latent variable $h$ is sampled from a subspace $\Sigma^{n}$ of dimension $n$;
- 2.
The label $y$ is determined by the concept $c$ and the latent variable $h$, i.e., $y=c(h)$;
- 3.
The hidden variable $h$ is transformed to an input sequence by the data format mapping $\phi$.

According to Assumption 1, the inherent scaling challenge can be captured by Low-Dimension-to-High-Dimension (LDHD) generalization, a special scenario of OOD generalization with structural distributional shifts.
In an LDHD generalization problem, a model is trained with samples from a low-dimensional subspace while evaluated with samples from a higher-dimensional superspace. To further illustrate, we can consider that the training samples are from the space $\Sigma^{N_{0}}$ and the testing samples are from $\Sigma^{N}$, where $\Sigma$ is a field and the numbers $N_{0},N$ satisfy $N_{0}<N$. With slight abuse of notation, we also use $\Sigma^{n}$ to denote the embedding space of the subspace $\Sigma$ into a space $\Sigma^{\bar{N}}$ for some sufficiently large $\bar{N}\geq N>N_{0}$ (we use $\bar{N}=N$ below if there is no special statement).

The main challenge of LDHD generalization is that the testing space has extra dimensions compared to the training space. As a result, the testing space contains instances with orthogonal components to the training space. The training samples can reveal no information about how these components contribute to the results. For instance, in Example 2, learning with $N_{0}$-addition solely does not tell how $(N_{0}+1)$-th digits to $N$-th digits contribute to the result unless we have the prior knowledge that the addition of each digit shares the same process. We formally this challenge as No-Free-Lunch Theorem of LDHD Generalization in Section 3.

The No-Free-Lunch Theorem [, ] of LDHD Generalization necessitates the use of prior knowledge in the learning process in order to achieve LDHD generalization.
In practice, the prior knowledge is usually incorporated via the inductive bias of the learning algorithms and the models. Abbe et al. [] claimed that models with (S)GD converge to min-degree interpolators. However, the minimal degree-profile bias neither holds uniformly for all model architectures nor is sufficient for achieving LDHD generalization.
To develop LDHD generalizable models, we investigate different architectures whose inductive bias with (S)GD can potentially go beyond the min-degree interpolators.
While random feature models are shown to be min-degree interpolators, we prove that random feature models with projections, where inputs are transformed by projections before fed to the random feature models, converge to *min-degree interpolators under different independent sets*. We further consider Position-Only Linear Attentions with Advice (PLAA), i.e., linear attentions whose attention scores are determined only by positions, with additional hints about the scales of the instances. This model can be seen as a simplified abstraction of decoder-only transformers with a special focus on positional relations that are considered crucial for length generalization. We demonstrate the failure of PLAA models equipped with Absolute Position Embeddings (APEs) in general cases and show the PLAA models with Relative Position Embeddings (RPEs) are min-degree interpolators w.r.t. some independent sets. These results show that for models biased towards min-degree interpolators w.r.t. some independent sets, LDHD generalization can be achieved if and only if the target mapping is the min-degree interpolator w.r.t. the same set.

The LDHD generalization perspective further provides insights on how Chain-of-Thought (CoT) [] can help length generalization. We show that CoT can be seen as a change of the hidden space, where each dimension of the latent space is augmented with an additional middle state. This transformation could facilitate LDHD generalization in the latent space for some problems. Another implication is a principle of position embedding design for length generalization with Transformers: we need to handle both the inherent LDHD generalization and the nuisances such as the data format in the design of the position embeddings. Following this principle, we propose a novel position embedding named RPE-Square. The RPE-Square enhances the RPE with the ability to handle certain data format nuisances, evidently improving the length generalization of the URF addition over the Transformer with the RPE.

The main contributions of the paper are summarized as follows:

- •
We propose to study LDHD generalization, which captures the inherent scaling challenge of a wide range of length generalization problems. LDHD generalization provides a formulation under which we can perform theoretical analysis for general length generalization problems.
- •
We study the inductive bias of different model architectures under (S)GD, which can be exploited to incorporate prior knowledge to achieve LDHD generalization. In the context of Boolean functions, we show that different architectures under (S)GD can have inductive bias other than min-degree interpolators, which enables LDHD generalization for a wider class of problems.

Notations. We use $[n]$ to represent the set of numbers $\{1,\dots,N\}$. We denote the set of all functions from the set ${\mathcal{X}}$ to the set ${\mathcal{Y}}$ as ${\mathcal{F}}_{{\mathcal{X}},{\mathcal{Y}}}$. We define $\operatorname{Proj}(x,V)$ as the coordinate of the projection of $x$ onto the space spanned by $V$ with the basis $V=\left[v_{1},\dots,v_{r}\right]$, i.e., $\left[\operatorname{Proj}(x,V)\right]_{i}=\langle x,v_{i}\rangle$ for all $i=1,\dots,r$.
We use $A^{*}$ to denote the Kleene closure of the set $A$, i.e., $A^{*}=\bigcup_{k=0}^{\infty}A^{k}$.
We use $\deg(p)$ to denote the degree of the polynomial $p$.

###### Example 1 .

###### Example 2 (Addition) .

###### Assumption 1 (Data Generation in Length Generalization) .

## 2 Related Work

Length generalization in reasoning problems.
Length generalization is a key challenge in learning to reason, typically interpreted as the ability to learn with small-scale instances of a task and generalize to unseen large instances of the same task [, ]. Various reasoning tasks are considered to investigate length generalization, including arithmetic [, ], Boolean logic [, ], symbolic reasoning [], etc. Despite the rich literature on length generalization on specific reason tasks, few works have considered challenges and overconditions of length generalization for general problems. The existing works that analyze general length generalization mainly focus on the change of the input sequence length [, ], which does not precisely capture the difficulties of length generalization. Our work proposes to consider LDHD generalization, which characterizes the inherent challenges of length generalization in many tasks.

Inductive Bias of Model Architectures and Algorithms.
In the situation of learning with overparatermization or incomplete information, proper inductive bias is essential to select the true model from the hypothesis [, ]. One of the most studied scenarios is the inductive bias of different model architectures under (S)GD. Previous research shows (S)GD combined with different model architectures lead to different effects of implicit regularization, such as different norms of the learnable parameters Gunasekar et al. [], Bartlett et al. [] and different complexity characterizations of the models [, , ]. We specially mention Abbe et al. [], which proposes that models trained with (S)GD are biased towards min-degree profile interpolators in the context of Boolean functions, which do not achieve general LDHD generalization. Our results show that the min-degree profile bias does not hold for all models. We further show that models with different architecture can converge to min-degree profile interpolators under different independent sets when trained with (S)GD. This partially explains how model architectures can affect length generalization in reasoning problems.

## 3 Low-Dimension-to-High-Dimension Generalization

###### Definition 1 (Low-Dimension-to-High-Dimension Generalization) .

Suppose that ${\mathcal{X}}$ is a sample space and ${\mathcal{X}}_{1},{\mathcal{X}}_{2}$ are two subspaces such that ${\mathcal{X}}_{1}\subset{\mathcal{X}}_{2}\subset{\mathcal{X}}$ and $\dim({\mathcal{X}}_{1})<\dim({\mathcal{X}}_{2})$. Consider a concept class ${\mathcal{C}}\subset{\mathcal{F}}_{{\mathcal{X}},{\mathcal{Y}}}$, two distributions ${\mathcal{D}}_{1},{\mathcal{D}}_{2}$ where $\operatorname{supp}({\mathcal{D}}_{1})={\mathcal{X}}_{1}$ and $\operatorname{supp}({\mathcal{D}}_{2})={\mathcal{X}}_{2}$, and a learning algorithm ${\mathcal{A}}:\left({\mathcal{X}}\times{\mathcal{Y}}\right)^{*}\mapsto{
\mathcal{F}}_{{\mathcal{X}},{\mathcal{Y}}}$. We say *low-dimension-to-high-dimension generalization* of the concept class ${\mathcal{C}}$ from ${\mathcal{D}}_{1}$ to ${\mathcal{D}}_{2}$ is achieved by the algorithm ${\mathcal{A}}$ with $m$ samples and $\epsilon$ error if

$$ $\mathbb{E}_{X^{m}\sim{\mathcal{D}}_{1}^{m},X_{m+1}\sim{\mathcal{D}}_{2}}\left[ \ell\left(\hat{f}_{X^{m},c}(X_{m+1}),c(X_{m+1})\right)\right]\leq\epsilon,$ (1) $$

where $\hat{f}_{X^{m},c}$ is the function learned by the algorithm ${\mathcal{A}}$ from the training samples $X^{m}$ labeled by the concept $c$ and $\ell:{\mathcal{Y}}\times{\mathcal{Y}}\mapsto{\mathbb{R}}$ is the loss function.

Definition 1 extends the Independent Identical Distribution (IID) assumption in PAC learning theory and considers a special shift between the training data and the testing data. This shift is particularly challenging because the testing space is of strictly higher dimension than the training space. Generally, it is impossible to fully capture the structure of the training space from the testing data as the training data reveal no information on how components in the orthogonal subspace contribute to the output. Therefore, there is no algorithm that can always guarantee to learn the concept from the training data. Theorem 1 formally states the nonexistence of universal algorithms for LDHD generalization.

###### Theorem 1 (No-Free-Lunch Theorem of LDHD Generalization) .

Suppose that the two sets ${\mathcal{X}}$ and ${\mathcal{Y}}$ are finite.
For some $N>N_{0}$, consider two subsets ${\mathcal{X}}_{N_{0}}$, ${\mathcal{X}}_{N}$ of ${\mathcal{X}}$ such that ${\mathcal{X}}_{N_{0}}\subsetneq{\mathcal{X}}_{N}\subseteq{\mathcal{X}}$ and $\dim({\mathcal{X}}_{N_{0}})=N_{0}<N=\dim({\mathcal{X}}_{N})$.
Let $c_{1},c_{2}\in{\mathcal{F}}(:={\mathcal{F}}_{{\mathcal{X}}_{N},{\mathcal{Y}}})$ be two concepts such that $c_{1}(x)=c_{2}(x)$ for all $x\in{\mathcal{X}}_{N_{0}}$.
For any $c\in{\mathcal{F}}$ and ${\mathcal{X}}^{\prime}\subseteq{\mathcal{X}}$, define ${\mathcal{F}}/\left(c\mid{\mathcal{X}}^{\prime}\right):=\left\{f\in{\mathcal{F
}}\mid f(x)=c(x)\text{ for all }x\in{\mathcal{X}}^{\prime}\right\}$. Let $\ell:{\mathcal{Y}}\times{\mathcal{Y}}\mapsto{\mathbb{R}}$ be the loss function. For any distribution ${\mathcal{D}}({\mathcal{X}}_{N})$ such that $\operatorname{supp}\left({\mathcal{D}}({\mathcal{X}}_{N})\right)={\mathcal{X}}
_{N}$:

$$ $\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}}\right)}\mathbb{E} _{x\sim{\mathcal{D}}({\mathcal{X}}_{N})}\left[\ell\left(c_{1}(x),f(x)\right) \right]=\sum_{f\in{\mathcal{F}}/\left(c_{2}|_{{\mathcal{X}}_{N_{0}}}\right)} \mathbb{E}_{x\sim{\mathcal{D}}({\mathcal{X}}_{N})}\left[\ell\left(c_{2}(x),f(x )\right)\right].$ $$

Theorem 1 necessitates the consideration of structural assumptions on the concept class such that a learning algorithm could identify the target concept from the hypothesis with the imperfect information provided by the low-dimensional training data.
For example, the concept class of linear classifiers with fixed weight vector on ${\mathcal{X}}={\mathbb{R}}^{d}$, i.e., ${\mathcal{C}}=\{\operatorname{sgn}\left(w_{0}^{\intercal}x+b\right)\mid w_{0}
\in{\mathbb{R}}^{d},b\in{\mathbb{R}}\}$ with the $d^{\prime}$-dimensional training sample space ${\mathcal{X}}_{1}={\mathbb{R}}^{d^{\prime}}\times\{0\}^{d-d^{\prime}}$ and the $d$-dimensional testing sample space where $d^{\prime}<d$. For any concept $c\in{\mathcal{C}}$, a learning algorithm could not identify the true concept $c$ solely from the training data from ${\mathcal{X}}_{1}$ and the hypothesis of all linear classifiers. However, if a linear algorithm exploits the structure of the concept class that the weight vector always equals $w_{0}$, it can compute the target bias from the training data in ${\mathcal{X}}_{1}$ and thus identify the target concept $c$.

We further investigate how model structures can affect LDHD generalization. We show in Section 4 that different models trained with (S)GD can be seen as min-degree interpolators under different functional bases in the context of Boolean functions, which is a joint inductive bias of the model structures and (S)GD. This suggests a principle for model design to achieve LDHD generalization: make the concept class “low-degree” under the independent set induced by the model structure.

Many generalization challenges in reasoning problems can be attributed to LDHD generalization inherently. Length generalization is representative of these challenges and of significance in reasoning problems. Intuitively, length generalization means that a model trained with small-scale instances of a reasoning problem can perform well on large-scale instances of the problem. To formalize the intuition, we consider a typical instance being generated from a hidden state variable $h$ that represents the core of the instance and is transformed to the model input by a data format mapping. The hidden state space is of the form $\Sigma^{*}$ for some field $\Sigma$. The dimension $n$ of the subspace from which the hidden state variable is sampled, $n=\operatorname*{arg\,max}_{k}\{h\in\Sigma^{k},h\not\in\Sigma^{k+1}\}$ , reflects the increase in the scale of the problem. Besides, we define the concept class on the hidden space, depicting that the change of the data format does not change the intrinsic logic of the concepts. Assumption 1 describes the pipeline of the data generation in length generalization.

###### Definition 1 (Low-Dimension-to-High-Dimension Generalization) .

###### Theorem 1 (No-Free-Lunch Theorem of LDHD Generalization) .

## 4 Main Results

We show theoretically how different models succeed or fail to achieve LDHD generalization as the effect of the inductive bias of the architectures under (S)GD. We focus on Boolean functions. More specifically, in the context of Boolean functions, we have $\Sigma=\{\pm 1\}$, ${\mathcal{X}}=\Sigma^{N}$, ${\mathcal{X}}_{n}=\Sigma^{n}\times\{1\}^{N-n}$ for $n=1,\dots,N$. The set of all Boolean functions potentially considered is ${\mathcal{F}}={\mathcal{F}}_{{\mathcal{X}},{\mathbb{R}}}$. We consider LDHD generalization from $N_{0}$ to $N$ for some $N_{0}<N$. Define $I(f)$ as the minimal set $I$ of indices that the function $f$ can be represented as a function of $x_{I}$, i.e., $I(f):=\operatorname*{arg\,min}_{I\subset[N]}|I|$ such that $f(x)=\tilde{f}(x_{I})$ for some function $\tilde{f}$ and all $x\in{\mathcal{X}}$. We say a function $f$ is $k$-sparse if $|I(f)|\leq k$.

Before presenting the theoretical results, we introduce two concepts *degree profile w.r.t. independent set* and *min-degree interpolator w.r.t. independent set*, which extend the concept *degree profile* and the concept *min-degree interpolator*, respectively. We use the two concepts to characterize the inductive bias of different model architectures under (S)GD.

###### Definition 2 (Degree Profile w.r.t. Independent Set ${\mathcal{B}}$ ) .

Suppose that ${\mathcal{B}}=\{b_{1},\dots,b_{R}\}$ is an independent set of functions in ${\mathcal{F}}$ and $D=\max_{b\in{\mathcal{B}}}\deg(b)$. Let $f\in{\mathcal{F}}$ be a function in the subspace spanned by ${\mathcal{B}}$, i.e., $f=\sum_{i=1}^{R}\hat{f}_{{\mathcal{B}}}(b_{i})b_{i}$ for some $\hat{f}_{{\mathcal{B}}}(b_{i})\in{\mathbb{R}},i=1,\dots,R$. The *degree profile* of the function w.r.t. ${\mathcal{B}}$, denoted by $\operatorname{DegP}_{{\mathcal{B}}}(f)$, is a $(D+1)$-tuple where $D_{i}=\sum_{b\in{\mathcal{B}},\deg(b)=D+1-i}\hat{f}_{{\mathcal{B}}}(b)^{2}$ for $i=1,\dots,D+1$. The order of degree profiles is identical to the lexicographic order of the corresponding $D$-tuples.

###### Definition 3 (Min-Degree Interpolator w.r.t. Independent Set ${\mathcal{B}}$ ) .

Suppose that ${\mathcal{B}}=\{b_{1},\dots,b_{R}\}$ is an independent set of functions in ${\mathcal{F}}$.
Let ${\mathcal{X}}^{\prime}$ be a subset of the sample space ${\mathcal{X}}=\{\pm 1\}^{N}$. Denote the set of all interpolators on ${\mathcal{X}}^{\prime}$ for the concept $c$ by ${\mathcal{G}}_{{\mathcal{X}}^{\prime},c}$, i.e., ${\mathcal{G}}_{{\mathcal{X}}^{\prime},c}=\{g\in{\mathcal{F}}\mid g(x)=c(x)
\text{ for all }x\in{\mathcal{X}}^{\prime}\}$.
A function $g$ is called the min-degree interpolator w.r.t. ${\mathcal{B}}$ on ${\mathcal{X}}_{0}$ for the concept $c$ if
$g\in{\mathcal{G}}_{{\mathcal{X}}^{\prime},c}$ and $\operatorname{DegP}(g)\leq\operatorname{DegP}(g^{\prime})$ for all $g^{\prime}\in{\mathcal{G}}_{{\mathcal{X}}^{\prime},c}$.

###### Definition 2 (Degree Profile w.r.t. Independent Set ℬ ℬ {\mathcal{B}} caligraphic_B ) .

###### Definition 3 (Min-Degree Interpolator w.r.t. Independent Set ℬ ℬ {\mathcal{B}} caligraphic_B ) .

### 4.1 Random Feature Model with Projection

We first consider the random feature model (RFM) and a class of its variants, i.e., Random Feature Models with Projection (RFMP; see Definition 4). The original RFM can be seen as a special instance of RFMP with $V=I_{N}$.

###### Definition 4 (Random Feature Model with Projection) .

Suppose that $V=[v_{1},\dots,v_{r}]\in{\mathbb{R}}^{N\times r}$ satisfies $V^{\intercal}V=I_{r}$. A random feature model with projection w.r.t. $V$ is

$$ $f_{\text{RFMP}}^{V,K}(x;a)=\frac{1}{\sqrt{K}}\sum_{k=1}^{K}a_{k}\sigma\left( \left\langle w_{k},\operatorname{Proj}\left(x,V\right)\right\rangle+b_{k} \right),$ $$

where $K$ is the number of random features, $a=\left[a_{1},\dots,a_{K}\right]^{\intercal}$ is the learnable parameter, $w_{k}\sim{\mathcal{N}}(0,I_{r}/r)$, $b_{k}\sim{\mathcal{N}}(0,1/r)$ for $k=1,\dots,K$, and $\sigma$ is the activation function.

Technically, we follow the strongly expressive condition [] for the activation function $\sigma$. Abbe et al. [] shows that the RFM converges to the min-degree interpolator when initialized at 0 0 and trained with GD. However, this is not the case for all RFMP models. We show in Theorem 2 that an RFMP model converges to a min-degree interpolator w.r.t. an independent set determined by $V$.

###### Theorem 2 .

Suppose that $V=[v_{1},\dots,v_{r}]\in{\mathbb{R}}^{N\times r}$ satisfies $V^{\intercal}V=I_{r}$.
Define the set ${\mathcal{B}}(V)$ of independent functions as

$$ ${\mathcal{B}}(V)=\left\{\chi^{V}_{T}(x)\right\}_{T\subseteq[r]},\quad\text{ where }\chi^{V}_{T}(x)=\prod_{t\in T}\sum_{n=1}^{N}(v_{t})_{n}x_{n}$ $$

Let $a_{t}$ be the learnable parameter at the timestep $t$ in the training process where the learnable parameter $a$ is initialized at $a_{0}=0$ and optimized with gradient descent/gradient flow under $\ell_{2}$ loss on ${\mathcal{X}}_{N_{0}}$. Let ${\mathcal{G}}_{N_{0},c,V}$ be the set of all interpolators on ${\mathcal{X}}_{N_{0}}$ for the concept $c^{*}(x)=c\left(\operatorname{Proj}(x,V)\right)$ that is $O_{N}(1)$-sparse. Then we have

$$ $f_{\text{RFMP}}^{V,K}(x;a_{t})\to\arg\min_{g\in{\mathcal{G}}_{N_{0},c,V}} \operatorname{DegP}_{{\mathcal{B}}(V)}(g),\quad\text{as }K\to\infty,t\to\infty.$ $$

When $V=I_{N}$, the independent set ${\mathcal{B}}(V)$ is the Fourier basis of the Boolean functions, and Theorem 2 implies that the RFM converges to the min-degree interpolator.
From Theorem 2, we see that an RFMP model with the projection matrix $V$ can achieve LDHD generalization only if the target concept coincides with the min-degree interpolator w.r.t. ${\mathcal{B}}(V)$. Specially, for the RFM, we have:

###### Corollary 1 .

For any $f\in{\mathcal{F}}$ such that $I(f)\not\subset\left[N_{0}\right]$, the min-degree interpolator does not achieve LDHD generalization from ${\mathcal{X}}_{N_{0}}$ to ${\mathcal{X}}_{N}$ and thus the RFM initialized at 0 and trained with GD does not achieve LDHD generalization from ${\mathcal{X}}_{N_{0}}$ to ${\mathcal{X}}_{N}$.

Corollary 1 shows that the min-degree interpolator and thus the RFM model can only achieve LDHD generalization for a very restricted set of functions that are only dependent on $x_{[N_{0}]}$. To achieve LDHD generalization with RFMP models requires prior knowledge of the concept class to design a projection to align the concepts with the min-degree interpolator w.r.t. the projected Fourier basis.

###### Definition 4 (Random Feature Model with Projection) .

###### Theorem 2 .

###### Corollary 1 .

### 4.2 Position-Only Linear Attention with Advice

In this subsection, we investigate Position-Only Linear Attention with Advice (PLAA), which can be seen as a simplification of decoder-only Transformers (Definition 5), with a special focus position embeddings that are considered pivot to the length generalization of the Transformers [, ].

###### Definition 5 (PLAA) .

Define the advice function $n:{\mathcal{X}}\mapsto\{0,\dots,N\}$ such that $n(x)=\operatorname*{arg\,max}_{n}\{x_{n}=-1\}$ if there exists $k\in[N]$ such that $x_{k}=-1$ and $n(x)=0$ otherwise. We additionally define $e_{0}:=0$. A PLAA model is

$$ $f_{\text{PLAA}}(x;A)=x^{\intercal}Ae_{n(x)},$ $$

where $A\in{\mathcal{U}}_{N}$ is the learnable parameter and $e_{n}$ denotes the vector with a $1$ in the $n$-th coordinate and 0 0’s elsewhere.

We further elaborate on the intuition behind the PLAA models. In the generation process of a decoder-only (linear) Transformer with position embeddings given input $\mathtt{s=s_{1}\dots s_{n}}$, the attention is computed by the query at the position $n$ and the keys at the positions $i\leq n$. The position of the query is special, advising the length of the input and reflecting the scale of the instance ideally.
The PLAA model captures this feature and introduces the notation $n(x)$ to reflect the dimension of the subspace that $x$ belongs to. To further simplify and focus on the position embeddings, we assume that the value of each $x_{i}$ is identical to itself and the attention is only related to positions.
The contribution of the interaction between the position embeddings is $\left[e_{1},\dots,e_{n}\right]^{\intercal}A_{[n],[n]}e_{n}=A_{[n],n}$ for some upper triangle matrix $A$. When the input is embedded to length $N$ but the query is still made at the position $n$, the output of the model is $x^{\intercal}Ae_{n(x)}$, i.e., the output of the PLAA model. Therefore, the PLAA model is a simplification of decoder-only Transformers that enables theoretical analysis of the impact of the position embeddings on length generalization.

In Definition 5, we directly parameterize the PLAA model directly with the attention matrix. In practice, however, the attention matrix is typically computed by the interaction between the position embeddings. Therefore, we consider the PLAA models with the Absolute Position Embedding (APE) and the Relative Position Embedding (RPE), respectively. See Definitions 6 and 7. Note that we consider Generalized RPE (GPRE) in Definition 7 because the RPE can be seen as a special instance of the GRPE with ${\mathcal{U}}={\mathcal{U}}_{\text{RPE}}=\{D_{1},\dots,D_{N}\}$, where $D_{k}$ is a $k$-th upper diagonal matrix such that $(D_{k})_{ij}$ is $1$ if $j=i+k-1$ and 0 0 otherwise. We seek a more general result applicable to all similar parameterization methods to the RPE.

###### Definition 6 (PLAA with APE) .

A PLAA model with APE is

$$ $f_{\text{PLAA}}^{\text{APE}}(x;P)=x^{\intercal}\left(M_{N}^{u}\circ P^{ \intercal}P\right)e_{n(x)},$ $$

where $M_{N}^{u}{\mathbb{R}}^{N\times N}$ is the upper triangle mask, i.e., $(M_{N}^{u})_{ij}$ is $1$ if $i\leq j$ and 0 0 otherwise, and $P\in{\mathbb{R}}^{d_{P}\times N}$ is the learnable parameter of the model.

###### Definition 7 (PLAA with GRPE) .

For ${\mathcal{U}}=\{U_{1},\dots,U_{r}\}$, a PLAA moodel with GRPE is

$$ $f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p)=x^{\intercal}\left(\sum_{i=1} ^{r}U_{i}p_{i}\right)e_{n(x)},$ $$

where $U_{i}\in{\mathcal{U}}_{N},i=1,\dots,r$ are upper triangle matrices that satisfy $\left\langle U_{i},U_{i}\right\rangle=1$ for all $i=1,\dots,r$ and $\left(U_{i}\right)_{kl}\left(U_{j}\right)_{kl}=0$ for all $i\neq j$ and $1\leq k,l\leq N$, and $p=\left[p_{1},\dots,p_{r}\right]^{\intercal}\in{\mathbb{R}}^{r}$ is the learnable parameter of the model.

###### Remark 1 .

The condition $\left(U_{i}\right)_{kl}\left(U_{j}\right)_{kl}=0$ for all $i\neq j$ and $1\leq k,l\leq N$ in Definition 7 means each element in the position-only attention is characterized by at most one parameter. For example, in RPE, $A_{i,j}(i\leq j)$ is only parameterized by $p_{j-i}$. This condition naturally generalizes the intuition of RPE that
characterizes some “relative” relations between two positions.

We first consider the vanilla PLAA model, the direct parameterization with the attention matrix. Theorem 3 shows that the PLAA model converges to the min-degree interpolator w.r.t. the independent set ${\mathcal{B}}_{N}^{\text{PLAA}}$ that is defined in the theorem.

###### Theorem 3 .

Define the set ${\mathcal{B}}_{N}^{\text{PLAA}}$ as

$$ ${\mathcal{B}}_{N}^{\text{PLAA}}:=\{b_{ij}^{\text{PLAA}}(x)\}_{1\leq i\leq j \leq N},$ $$

where

$$ $b_{ij}^{\text{PLAA}}(x)=\begin{cases}-\frac{1-x_{j}}{2}\prod_{k=j+1}^{N}\frac{ 1+x_{k}}{2},&i=j,\\ x_{i}\frac{1-x_{j}}{2}\prod_{k=j+1}^{N}\frac{1+x_{k}}{2},&i<j.\end{cases}$ $$

Let $A_{t}$ be the learnable parameter at the timestep $t$ in the training process where the learnable parameter $A$ is initialized at $A_{0}=0$ and optimized with gradient descent/gradient flow under $\ell_{2}$ loss on ${\mathcal{X}}_{N_{0}}$.
Let ${\mathcal{G}}_{N_{0},A^{*}}^{\text{PLAA}}$ be the set of all interpolators on ${\mathcal{X}}_{N_{0}}$ for the concept $c(x)=f_{\text{PLAA}}(x;A^{*})$. Then we have

$$ $f_{\text{PLAA}}(x;A_{t})\to\arg\min_{g\in{\mathcal{G}}_{N_{0},A^{*}}^{\text{ PLAA}}}\operatorname{DegP}_{{\mathcal{B}}_{N}^{\text{PLAA}}}(g),\quad\text{as }t\to\infty.$ $$

For the PLAA model with APE, Theorem 4 shows that the model converges to the interpolator whose attention matrix is of the minimal nuclear norm if the minimal-nuclear-norm-solution conjecture (Assumption 2 about the implicit regularization in matrix factorization holds. While the conjecture has not been theoretically justified in general cases, it is proved correct under some specific conditions and supported by empirical evidence [, ].

###### Assumption 2 (Minimal-Nuclear-Norm-Solution Conjecture [ 10 ] ) .

Consider the optimization

$$ $\min_{U\in{\mathbb{R}}^{n\times n}}f(U)=\left\|{\mathcal{A}}\left(UU^{ \intercal}\right)-y\right\|_{2}^{2},$ $$

where ${\mathcal{A}}:{\mathbb{R}}^{n\times n}\mapsto{\mathbb{R}}^{m}$ is a linear operator specified by ${\mathcal{A}}(\cdot)_{i}=\left\langle A_{i},\cdot\right\rangle$
for symmetric linearly independent $A_{i}\in{\mathbb{R}}^{n\times n},1\leq i\leq m$, and $y\in{\mathbb{R}}^{m}$. Define $X=X(U):=UU^{\intercal}$. Let $U_{t}$ be the parameter reached by gradient flow in the timestep $t$ and $X_{t}$ be $U_{t}U_{t}^{\intercal}$. Define $X_{\infty}(X_{\text{init}}):=\lim_{t\to\infty}X_{t}$ for $U_{0}U_{0}^{\intercal}=X_{\text{init}}$. For any full rank $X_{0}$, if $\hat{X}=\lim_{\alpha\to 0}X_{\infty}(\alpha X_{0})$ exists and ${\mathcal{A}}\left(\hat{X}\right)=y$, then $\hat{X}\in\operatorname*{arg\,min}_{{\mathcal{X}}\succ\|X\|_{*}}$ s.t. ${\mathcal{A}}(X)=y$.

###### Theorem 4 .

Suppose that Assumption 2 holds and $d_{P}=N$.
Let $P_{t}$ be the learnable parameter at the timestep $t$ in the training process where the learnable parameter $P$ is initialized at $P_{0}$ such that $(P_{0})_{ij}\sim{\mathcal{N}}(0,\alpha)$ for $(i,j)\in[d_{P}]\times[N]$ and $\alpha$ sufficiently small, and optimized with gradient descent/gradient flow under $\ell_{2}$ loss on ${\mathcal{X}}_{N_{0}}$.
Let ${\mathcal{G}}_{N_{0},P^{*}}^{\text{APE}}$ be the set of all PLAA interpolators on ${\mathcal{X}}_{N_{0}}$ for the concept $c(x)=f_{\text{PLAA}}^{\text{APE}}(x;P^{*})$. Then we have

$$ $f_{\text{PLAA}}^{\text{APE}}(x;P_{t})\to\arg\min_{g\in{\mathcal{G}}_{N_{0},P^{ *}}^{\text{APE}}}\|A_{g}\|_{*},\quad\text{as }t\to\infty,$ $$

where $A_{g}$ is the attention matrix in the PLAA model $g$.

Theorem 4 shows that APE leads to a low-rank attention matrix in the PLAA model.
Therefore, when the training data is restricted to ${\mathcal{X}}_{N_{0}}$, the rank of the attention matrix learned by the model with APE is no higher than $N_{0}$. This leads to length generalization failure when the target concept requires higher-rank attention to be represented.
We have the following direct corollary of Theorem 4 that partially explains the limitation of APE for length generalization.

###### Corollary 2 .

The PLAA with APE fails to achieve LDHD generalization for the concept $c(x)=f_{\text{PLAA}}(x;A^{*})$ if $\operatorname{rank}(A^{*})>N_{0}$.

Theorem 5 characterizes that the PLAA converges to the interpolator that minimizes the degree-profile w.r.t. to the independent set ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$, which can be seen as the projections of ${\mathcal{U}}$ onto ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$. Theorem 3 is a special case of Theorem 5 for ${\mathcal{U}}=\left\{E_{ij}\right\}_{1\leq i\leq j\leq N}$, where $E_{ij}\in{\mathbb{R}}^{N\times N}$ is the elementary matrix that has a 1 at the $(i,j)$-th position and 0 everywhere else.

###### Theorem 5 .

For the ${\mathcal{U}}=\{U_{1},\dots,U_{r}\}$, define

$$ ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}:=\left\{\sum_{1\leq i \leq j\leq N}(U_{k})_{ij}b_{ij}^{\text{PLAA}}(x)\right\}_{1\leq k\leq r}.$ $$

Let $p_{t}$ be the learnable parameter at the timestep $t$ in the training process where the learnable parameter $p$ is initialized at $p_{0}=0$ and optimized with gradient descent/gradient flow under $\ell_{2}$ loss on ${\mathcal{X}}_{N_{0}}$.
Let ${\mathcal{G}}_{N_{0},p^{*}}^{\text{GRPE},{\mathcal{U}}}$ be the set of all interpolators on ${\mathcal{X}}_{N_{0}}$ for the concept $c(x)=f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p^{*})$. Then we have

$$ $f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p_{t})\to\arg\min_{g\in{\mathcal {G}}_{N_{0},p^{*}}^{\text{GRPE},{\mathcal{U}}}}\operatorname{DegP}_{{\mathcal{ B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}(g),\quad\text{as }t\to\infty.$ $$

With the inductive bias of the PLAA with GRPE, Corollary 3 states that LDHD generalization can be achieved if and only if the target concept can be represented by the elements in ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$ that have dependence on ${\mathcal{X}}_{N_{0}}$.

###### Corollary 3 .

Consider the concept $c(x)=f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p^{*})=\sum_{k=1}^{r}c_{k}
\sum_{1\leq i\leq j\leq N}(U_{k})_{ij}b_{ij}^{\text{PLAA}}(x)$. Under the conditions of Theorem 5, the PLAA with GRPE achieves LDHD generalization from ${\mathcal{X}}_{N_{0}}$ to ${\mathcal{X}}_{N}$ if and only if

$$ $\left\{k\mid(U_{k})_{[N_{0}],[N_{0}]}=0\right\}\subseteq\left\{k\mid c_{k}=0 \right\}.$ $$

###### Remark 2 .

While the projection in the RFM and the position embeddings in the PLAA may introduce a stronger inductive bias that benefits LDHD generalization, they can also reduce the expressiveness of the models. The critical point is to align the models with the concept class in such a way that we can incorporate a strong inductive bias for LDHD generalization while maintaining sufficient expressiveness for the concept class.

###### Definition 5 (PLAA) .

###### Definition 6 (PLAA with APE) .

###### Definition 7 (PLAA with GRPE) .

###### Remark 1 .

###### Theorem 3 .

###### Assumption 2 (Minimal-Nuclear-Norm-Solution Conjecture [ 10 ] ) .

###### Theorem 4 .

###### Corollary 2 .

###### Theorem 5 .

###### Corollary 3 .

###### Remark 2 .

## 5 Further Implications for Length Generalization

We discuss further implications of the LDHD generalization perspective for length generalization.

### 5.1 Chain-of-Thought for Length Generalization

While the Chain-of-Thought (CoT) can lead to more variety in the length of testing samples, it is widely used as an effective technique to improve the length generalization in various reasoning tasks. This seems contradictory if considered in the original space of the input sequence. However, when considering the abstraction of the data generating process from the hidden space, we can see that CoT intrinsically changes the underlying hidden space by extending each dimension with a “middle” variable and does not lead to the dimensional increase in the hidden space. For example, consider the $n$-addition without CoT and the $n$-addition with CoT. In the case without CoT, the instance $x_{n-1}\dots x_{0}+y_{n-1}\dots y_{0}=z_{n}\dots z_{0}$ corresponds to the latent state $h_{n}=\left[\left(x_{0},y_{0}\right),\dots,(x_{n-1},y_{n-1})\right]\in\Sigma^{n}$ for $\Sigma=\{0,\dots,9\}\times\{0,\dots,9\}$. In the case with CoT, one step of predicting $z_{t}$ in solving the instance corresponds to the latent state $h_{n}=\left[\left(x_{0},y_{0},z_{0}\right),\dots,\left(x_{t-1},y_{t-1},z_{t-1}
\right),\left(x_{t},y_{t},*\right)\dots,(x_{n-1},y_{n-1},*)\right]\in\bar{
\Sigma}^{n}$ for $\bar{\Sigma}=\Sigma\times\{*,0,\dots,9\}$, where $*$ is a special element indicating undetermined values. CoT does not cause the LDHD generalization challenge but extends the field $\Sigma$, which could potentially lead to a more easily learnable target concept under the model architecture.

### 5.2 Position Embeddings for Length Generalization

Position embeddings are considered closely related to the length generalization in Transformers
Our analysis suggests a principle to consider both the inherent LDHD generalization and the nuisances such as the data format in the design of the position embeddings. To further elaborate, consider the length generalization of the URF addition with CoT. While RPE can capture the recursive structure of the addition problem and could lead to LDHD generalization in the latent space, it fails to work for the URF addition with CoT. The failure of RPE is attributed to the nuisance of the URF.

Following the principle, we design a novel position embedding called RPE-Square to handle the nuisance of the URF. On the one hand, we keep the RPE structure for the inherent LDHD generalization. On the other hand, we deal with the unalignment by considering the distances to several special tokens (i.e., $\mathtt{[BOS]}$, $\mathtt{+}$, and $\mathtt{=}$). These considerations lead to the RPE-Square, in which we compute the relative values between the distances to the special tokens. More concretely, the $\text{RPE-Square}_{i,j}$ for the query at $j$ and the key at $i$ is

$$ $\sum_{1\leq k\leq j,1\leq l\leq i}\frac{\exp\left((W_{Q}x_{j})^{\intercal}(W_{ K}x_{l})\right)}{\sum_{1\leq l^{\prime}\leq j}\exp\left((W_{Q}x_{j})^{ \intercal}(W_{K}x_{l^{\prime}})\right)}\frac{\exp\left((W_{Q}x_{i})^{\intercal }(W_{K}x_{k})\right)}{\sum_{1\leq k^{\prime}\leq i}\exp\left((W_{Q}x_{i})^{ \intercal}(W_{K}x_{k^{\prime}})\right)}R_{(j-l)-(i-k)},$ $$

where $W_{Q}$ and $W_{K}$ are the weight matrices for the query and the key, respectively.
We replace $\text{RPE}_{j-i}$ with $\text{RPE-Square}_{i,j}$ in the Transformer. The experiment shows that RPE-Square effectively improves the length generalization in the URF addition with CoT. The design of RPE-Square illustrates how the principle can lead to position embeddings for better length generalization.

Figure: (a)
Refer to caption: x1.png

## 6 Conclusion and Discussion

We propose considering LDHD generalization, which captures the inherent scaling challenge of length generalization in various reasoning tasks. We introduce the No-Free-Lunch Theorem for LDHD generalization, demonstrating the necessity of inductive bias for achieving length generalization. We further investigate the inductive biases of different model architectures trained with (S)GD in the context of Boolean functions. LDHD generalization can only be achieved if the inductive bias aligns with the structure of the target concept. As implications for length generalization in practical problems, our perspective on LDHD generalization elucidates the role of CoT in extending the latent space and leads to the principle that both inherent LDHD generalization and nuisances must be addressed to achieve length generalization.

For future work, while our theory is established with simplified models, it is crucial to further investigate inductive bias in more practical and complex models. Additionally, developing a paradigm for position embedding design based on the proposed principles is a valuable avenue for exploration.

## Appendix A Proofs

### A.1 Proof for Theorem 1

Let ${\mathcal{D}}_{1}:={\mathcal{D}}\left({\mathcal{X}}_{N}\mid x\in{\mathcal{X}}_
{N_{0}}\right)$ be the conditional distribution given that $x\in{\mathcal{X}}_{N_{0}}$ and
${\mathcal{D}}_{2}:={\mathcal{D}}\left({\mathcal{X}}_{N}\mid x\not\in{\mathcal{
X}}_{N_{0}}\right)$ be the conditional distribution given that $x\not\in{\mathcal{X}}_{N_{0}}$

$$ $\displaystyle\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}({\mathcal{X}}_{N})}\left[\ell\left(c_{1 }(x),f(x)\right)\right]$ $\displaystyle=$ $\displaystyle P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\in{\mathcal{X}}_{N_{0}}) \sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}}\right)}\mathbb{E} _{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c_{1}(x),f(x)\right)\right]$ $\displaystyle+P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\not\in{\mathcal{X}}_{N_{0 }})\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}}\right)}\mathbb {E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{1}(x),f(x)\right)\right]$ $\displaystyle=$ $\displaystyle P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\in{\mathcal{X}}_{N_{0}})V _{1}(c_{1})+P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\not\in{\mathcal{X}}_{N_{0}} )V_{2}(c_{1}),$ $$

where

$$ $\displaystyle V_{1}(c):=\sum_{f\in{\mathcal{F}}/\left(c|_{{\mathcal{X}}_{N_{0} }}\right)}\mathbb{E}_{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c(x),f(x)\right) \right],$ $\displaystyle V_{2}(c):=\sum_{f\in{\mathcal{F}}/\left(c|_{{\mathcal{X}}_{N_{0} }}\right)}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c(x),f(x)\right) \right].$ $$

Similarly, we have

$$ $\sum_{f\in{\mathcal{F}}/\left(c_{2}|_{{\mathcal{X}}_{N_{0}}}\right)}\mathbb{E} _{x\sim{\mathcal{D}}({\mathcal{X}}_{N})}\left[\ell\left(c_{2}(x),f(x)\right) \right]=P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\in{\mathcal{X}}_{N_{0}})V_{1}(c _{2})+P_{{\mathcal{D}}({\mathcal{X}}_{N})}(x\not\in{\mathcal{X}}_{N_{0}})V_{2} (c_{2}).$ $$

To prove the theorem, it remains to show that $V_{1}(c_{1})=V_{1}(c_{2})$
and $V_{2}(c_{1})=V_{2}(c_{2})$.

By the definition of ${\mathcal{F}}/\left(c|_{{\mathcal{X}}_{N_{0}}}\right)$, we have

$$ $\displaystyle V_{1}(c_{1})$ $\displaystyle=\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c_{1}(x),f(x)\right )\right]$ $\displaystyle=\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c_{1}(x),c_{1}(x) \right)\right]$ $\displaystyle\overset{(a)}{=}\sum_{f\in{\mathcal{F}}/\left(c_{2}|_{{\mathcal{X }}_{N_{0}}}\right)}\mathbb{E}_{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c_{2}(x) ,c_{2}(x)\right)\right]$ $\displaystyle=\sum_{f\in{\mathcal{F}}/\left(c_{2}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}_{1}}\left[\ell\left(c_{2}(x),f(x)\right )\right]=V_{1}(c_{2}),$ $$

where the equality (a) is due to that $c_{1}(x)=c_{2}(x)$ for all $x\in{\mathcal{X}}_{N_{0}}$.

By the no-free-lunch theorem [, ] for ${\mathcal{X}}_{N}\setminus{\mathcal{X}}_{N_{0}}$, ${\mathcal{Y}}$, and ${\mathcal{F}}_{{\mathcal{X}}_{N}\setminus{\mathcal{X}}_{N_{0}},{\mathcal{Y}}}$, we have

$$ $\sum_{f\in{\mathcal{F}}_{{\mathcal{X}}_{N}\setminus{\mathcal{X}}_{N_{0}},{ \mathcal{Y}}}}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{1}(x),f(x) \right)\right]=\sum_{f\in{\mathcal{F}}_{{\mathcal{X}}_{N}\setminus{\mathcal{X} }_{N_{0}},{\mathcal{Y}}}}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_ {2}(x),f(x)\right)\right].$ $$

Then we have

$$ $\displaystyle V_{2}(c_{1})$ $\displaystyle=\sum_{f\in{\mathcal{F}}/\left(c_{1}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{1}(x),f(x)\right )\right]$ $\displaystyle=\sum_{f\in{\mathcal{F}}_{{\mathcal{X}}_{N}\setminus{\mathcal{X}} _{N_{0}},{\mathcal{Y}}}}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{ 1}(x),f(x)\right)\right]$ $\displaystyle=\sum_{f\in{\mathcal{F}}_{{\mathcal{X}}_{N}\setminus{\mathcal{X}} _{N_{0}},{\mathcal{Y}}}}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{ 2}(x),f(x)\right)\right]$ $\displaystyle=\sum_{f\in{\mathcal{F}}/\left(c_{2}|_{{\mathcal{X}}_{N_{0}}} \right)}\mathbb{E}_{x\sim{\mathcal{D}}_{2}}\left[\ell\left(c_{2}(x),f(x)\right )\right]=V_{2}(c_{2}).$ $$

### A.2 Proof for Theorem 2

Let $z=z(x)=\operatorname{Proj}(x,V)$ and ${\mathcal{Z}}_{N_{0}}=\left\{\operatorname{Proj}(x,V)\mid x\in{\mathcal{X}}_{N
_{0}}\right\}$.
Let ${\mathcal{G}}^{\prime}_{N_{0},c}$ be the set of all RFM interpolators on ${\mathcal{Z}}_{N_{0}}$ for the concept $c(z)$, i.e.,

$$ ${\mathcal{G}}^{\prime}_{N_{0},c}=\{f_{\text{RFM}}(z;a)\mid f_{\text{RFM}}(z;a) =c(z)\text{ for all }z\in{\mathcal{Z}}_{N_{0}}\},$ $$

where

$$ $f_{\text{RFM}}(z;a)=\frac{1}{\sqrt{K}}\sum_{k=1}^{K}a_{k}\sigma(\langle w_{k}, z\rangle+b_{k}).$ $$

According to the proof of Theorem 3.8 in Abbe et al. [], the RFM model $f_{\text{RFM}}(z;a)$ converges to the min-degree interpolator (w.r.t. the variable $z$) in ${\mathcal{G}}^{\prime}_{N_{0},c}$, i.e.,

$$ $f_{\text{RFM}}(z;a_{t})\to\operatorname*{arg\,min}_{g^{\prime}\in{\mathcal{G}} ^{\prime}_{N_{0},c}}\operatorname{DegP}_{B^{\prime}}(g^{\prime}),\quad\text{as }K\to\infty,t\to\infty,$ $$

where $B^{\prime}=\{\chi_{T}(z)\}_{T\subseteq[r]}$.

By the definition of $z=z(x)=\operatorname{Proj}(x,V)$, we have

$$ $f_{\text{RFMP}}^{V,K}(x;a_{t})=f_{\text{RFM}}(z;a_{t})\to\operatorname*{arg\, min}_{g^{\prime}\in{\mathcal{G}}^{\prime}_{N_{0},c}}\operatorname{DegP}_{B^{ \prime}}(g^{\prime})=\arg\min_{g\in{\mathcal{G}}_{N_{0},c,V}}\operatorname{ DegP}_{{\mathcal{B}}(V)}(g),$ $$

as $K\to\infty,t\to\infty$.

### A.3 Proof for Theorem 5

Since Theorem 3 is a special case of Theorem 5 for ${\mathcal{U}}=\{E_{ij}\}_{1\leq i\leq j\leq N}$,
we only need to prove Theorem 5.

Note that

$$ $f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p)=x^{\intercal}\left(\sum_{k=1} ^{r}p_{k}U_{k}\right)e_{n(x)}=\left\langle xe_{n(x)}^{\intercal},\sum_{k=1}^{r }p_{k}U_{k}\right\rangle.$ $$

Let $D_{N_{0}}$ be the size of the training set in ${\mathcal{X}}_{N_{0}}$. Then the loss can be represented as

$$ $L(p)=\frac{1}{2D_{N_{0}}}\sum_{x\in{\mathcal{X}}_{N_{0}}}\left(\left\langle xe _{n(x)}^{\intercal},\sum_{k=1}^{r}p_{k}U_{k}\right\rangle-c^{*}(x)\right)^{2}.$ $$

Without loss of generality, we use the notation of gradient flow in this proof.
Then we have

$$ $\dot{A}=-\frac{1}{D_{N_{0}}}\sum_{x\in{\mathcal{X}}_{N}}\left(\left\langle xe_ {n(x)}^{\intercal},A\right\rangle-c^{*}(x)\right)\sum_{k=1}^{r}\left\langle xe _{n(x)}^{\intercal},U_{k}\right\rangle U_{k}.$ $$

Since $p(0)=0$, we have $A(0)=0$ and thus $A(t)\in\operatorname{span}\left\{\sum_{k=1}^{r}\left\langle xe_{n(x)}^{
\intercal},U_{k}\right\rangle U_{k}\right\}_{x\in{\mathcal{X}}_{N_{0}}}$.
Then the convergence point $\hat{A}$ can be represented as $\hat{A}=\sum_{x\in{\mathcal{X}}_{N_{0}}}\hat{a}(x)\sum_{k=1}^{r}\left\langle xe
_{n(x)}^{\intercal},U_{k}\right\rangle U_{k}$. The convergence function $\hat{f}$ is

$$ $\displaystyle\hat{f}(x)$ $\displaystyle=\sum_{x^{\prime}\in{\mathcal{X}}_{N_{0}}}\hat{a}(x^{\prime})\sum _{k=1}^{r}\left\langle x^{\prime}e_{n(x^{\prime})}^{\intercal},U_{k}\right \rangle\left\langle xe_{n(x)}^{\intercal},U_{k}\right\rangle$ $\displaystyle=\sum_{k=1}^{r}\sum_{x^{\prime}\in{\mathcal{X}}_{N_{0}}}\hat{a}(x ^{\prime})\left\langle x^{\prime}e_{n(x^{\prime})}^{\intercal},U_{k}\right \rangle\left\langle xe_{n(x)}^{\intercal},U_{k}\right\rangle$ $$

###### Lemma 1 .

For any upper triangle matrix $U\in{\mathbb{R}}^{N\times N}$, we have

$$ $\langle xe_{n(x)}^{\intercal},U\rangle=\sum_{1\leq i\leq j\leq N}U_{ij}b_{ij}^ {\text{PLAA}}(x).$ $$

###### Proof for Lemma 1 .

We first prove that $\langle xe_{n(x)}^{\intercal},E_{mn}\rangle=b_{ij}^{\text{PLAA}}(x)$ for any $1\leq i\leq j\leq N$.
Notice that

$$ $\langle xe_{n(x)}^{\intercal},E_{ij}\rangle=\begin{cases}x_{i}&x_{j}=-1\land x _{j+1}=1\land\dots\land x_{N}=1,\\ 0&\text{otherwise}.\end{cases}$ $$

Therefore, we have

$$ $\displaystyle\langle xe_{n(x)}^{\intercal},E_{ij}\rangle$ $\displaystyle=x_{i}\cdot\frac{1-x_{j}}{2}\cdot\frac{1+x_{j+1}}{2}\cdot\dots \cdot\frac{1+x_{N}}{2}$ $\displaystyle=\begin{cases}-\frac{1-x_{j}}{2}\prod_{k=j+1}^{N}\frac{1+x_{k}}{2 },&i=j,\\ x_{i}\frac{1-x_{j}}{2}\prod_{k=j+1}^{N}\frac{1+x_{k}}{2},&i<j.\end{cases}$ $\displaystyle=b_{ij}^{\text{PLAA}}(x).$ $$

For any upper triangle matrix $U=\sum_{1\leq i\leq j\leq N}U_{ij}E_{ij}$, we have

$$ $\langle xe_{n(x)}^{\intercal},U\rangle=\langle xe_{n(x)}^{\intercal},\sum_{1 \leq i\leq j\leq N}U_{ij}E_{ij}\rangle=\sum_{1\leq i\leq j\leq N}U_{ij}\langle xe _{n(x)}^{\intercal},E_{ij}\rangle=\sum_{1\leq i\leq j\leq N}U_{ij}b_{ij}^{ \text{PLAA}}(x).$ $$

∎

Define $b_{k}(x):=\langle xe_{n(x)}^{\intercal},U_{k}\rangle$. By Lemma 1, we have $b_{k}(x)=\sum_{1\leq i\leq j\leq N}(U_{k})_{ij}b_{ij}^{\text{PLAA}}(x)$.
Then the convergence function $\hat{f}$ can be represented as

$$ $\hat{f}(x)=\sum_{k=1}^{r}\sum_{x^{\prime}\in{\mathcal{X}}_{N_{0}}}\hat{a}(x^{ \prime})b_{k}(x^{\prime})b_{k}(x)=\sum_{k=1}^{r}\hat{p}_{k}b_{k}(x),$ $$

where $\hat{p}_{k}=\sum_{x^{\prime}\in{\mathcal{X}}_{N_{0}}}\hat{a}(x^{\prime})b_{k}(
x^{\prime})$.

For any interpolator $g(x)=\sum_{k=1}^{r}p_{k}b_{k}(x)$ on ${\mathcal{X}}_{N_{0}}$:

- •
If $b_{k}(x)=0$ for all $x\in{\mathcal{X}}_{0}$, we have $\hat{p}_{k}=0$ and $p_{k}^{2}\geq 0=\hat{p}_{k}^{2}$;
- •
If $b_{k}(x)\neq 0$ for some $x\in{\mathcal{X}}_{0}$, we have $\hat{p}_{k}=p_{k}$ and thus $\hat{p}_{k}^{2}=p_{k}^{2}$. To show this, without loss of generality, we suppose that for $1\leq k\leq m$, there exists some $x\in{\mathcal{X}}_{N_{0}}$ such that $b_{k}(x)\neq 0$, and for $m+1\leq k\leq r$, $b_{k}(x)=0$ for all $x\in{\mathcal{X}}_{N_{0}}$. It suffices to show that the following equation has a unique solution:
$\begin{bmatrix}b_{1}(x_{1})&\dots&b_{m}(x_{1})\\
\vdots&\vdots&\vdots\\
b_{1}(x_{M})&\dots&b_{m}(x_{M})\end{bmatrix}\begin{bmatrix}p_{1}\\
\vdots\\
p_{m}\end{bmatrix}=\begin{bmatrix}c^{*}(x_{1})\\
\vdots\\
c^{*}(x_{M})\end{bmatrix},$
where $M=|{\mathcal{X}}_{N_{0}}|$ and ${\mathcal{X}}_{N_{0}}=\{x_{1},\dots,x_{M}\}$.
Since $p_{1}=\hat{p}_{1},\dots,p_{m}=\hat{p}_{m}$ is a solution, it remains to prove the uniqueness.
Let
$B_{m}=\begin{bmatrix}b_{1}(x_{1})&\dots&b_{m}(x_{1})\\
\vdots&\vdots&\vdots\\
b_{1}(x_{M})&\dots&b_{m}(x_{M})\end{bmatrix}.$
It suffices to show $\operatorname{rank}(B_{m})=m$. Note that
$\left(B_{m}^{\intercal}B_{m}\right)_{ii}=\sum_{x\in{\mathcal{X}}_{N_{0}}}b_{i}
(x)^{2}>0$ and
$\left(B_{m}^{\intercal}B_{m}\right)_{ij}=\sum_{x\in{\mathcal{X}}_{N_{0}}}b_{i}
(x)b_{j}(x)=0$. We have $\operatorname{rank}(B_{m}^{\intercal}B_{m})=m$ and thus $\operatorname{rank}(B_{m})=m$.

Hence, for any interpolator $g$ on ${\mathcal{X}}_{N_{0}}$, we have

$$ $\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}( \hat{f})\leq\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{ \mathcal{U}}}}(g),$ $$

or equivalently,

$$ $f_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}(x;p_{t})\to\arg\min_{g\in{\mathcal {G}}_{N_{0},p^{*}}^{\text{GRPE},{\mathcal{U}}}}\operatorname{DegP}_{{\mathcal{ B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}(g),\quad\text{as }t\to\infty.$ $$

###### Lemma 1 .

###### Proof for Lemma 1 .

### A.4 Proof for Corollary 3

By Theorem 5, the PLAA with GRPE achieves LHDH generalization from ${\mathcal{X}}_{N_{0}}$ to ${\mathcal{X}}_{N}$ if and only if the target concept $c(x)$ is the min-degree interpolator w.r.t. the independent set ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$. Therefore, it is equivalent to prove the target concept $c(x)$ is the min-degree interpolator w.r.t. the independent set ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$ if and only if

$$ $\left\{k\mid(U_{k})_{[N_{0}],[N_{0}]}=0\right\}\subseteq\left\{k\mid c_{k}=0 \right\}.$ $$

We denote $\left\{k\mid(U_{k})_{[N_{0}],[N_{0}]}=0\right\}$ by ${\mathcal{K}}_{1}$ and
$\left\{k\mid c_{k}=0\right\}$ by ${\mathcal{K}}_{2}$ in this proof.

We first show the sufficiency. Assume that $c(x)$ is not the min-degree interpolator w.r.t. the independent set ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$ on ${\mathcal{X}}_{N_{0}}$. In other words, there exists an interpolator $\tilde{c}(x)=\sum_{k=1}^{r}\tilde{c}_{k}\sum_{1\leq i\leq j\leq N}(U_{k})_{ij}
b_{ij}^{\text{PLAA}}(x)$
on ${\mathcal{X}}_{N_{0}}$ such that

$$ $\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}( \tilde{c})<\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{ \mathcal{U}}}}(c).$ $$

Since both $c(x)$ and $\tilde{c}(x)$ are interpolators on ${\mathcal{X}}_{N_{0}}$, we have

$$ $\sum_{k=1}^{r}c_{k}(U_{k})_{[N_{0}],[N_{0}]}=\sum_{k=1}^{r}\tilde{c}_{k}(U_{k} )_{[N_{0}],[N_{0}]},$ $$

or equivalently,

$$ $\sum_{k\not\in{\mathcal{K}}_{1}}c_{k}(U_{k})_{[N_{0}],[N_{0}]}=\sum_{k\not\in{ \mathcal{K}}_{1}}\tilde{c}_{k}(U_{k})_{[N_{0}],[N_{0}]}.$ $$

Since $(U_{i})_{kl}(U_{j})_{kl}=0$ for all $i\neq j$ and $1\leq k,l\leq N$, we have $\left\{(U_{k})_{[N_{0}],[N_{0}]}\right\}_{k\not\in{\mathcal{K}}}$ are linearly independent. This implies $c_{k}=\tilde{c}_{k}$ for all $k\not\in{\mathcal{K}}_{1}$.

Since ${\mathcal{K}}_{1}\subseteq{\mathcal{K}}_{2}$, we have $c_{k}=0$ and thus $c_{k}^{2}\leq\tilde{c}_{k}^{2}$ for all $k\in{\mathcal{K}}_{1}$. Hence, we have

$$ $\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}( c)\leq\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{ U}}}}(\tilde{c}),$ $$

which contradicts the assumption.

We then prove the necessity. Assume that ${\mathcal{K}}_{1}\not\subseteq{\mathcal{K}}_{2}$. Then there exists some $k_{0}\in{\mathcal{K}}_{1}$ but $k_{0}\not\in{\mathcal{K}}_{2}$.
Define $\tilde{\tilde{c}}(x)=\sum_{k=1}^{r}\tilde{\tilde{c}}_{k}\sum_{1\leq i\leq j
\leq N}(U_{k})_{ij}b_{ij}^{\text{PLAA}}(x)$ where

$$ $\tilde{\tilde{c}}_{k}=\begin{cases}0,&k=k_{0},\\ c_{k},&k\neq k_{0}.\\ \end{cases}$ $$

By the definition of ${\mathcal{K}}_{1}$, $\tilde{\tilde{c}}(x)=c(x)$ for all $x\in{\mathcal{X}}_{N_{0}}$ and thus $\tilde{\tilde{c}}(x)$ is also an interpolator on ${\mathcal{X}}_{0}$. Note that $c_{k_{0}}\neq 0$. By the definition of $\tilde{\tilde{c}}(x)$, we have

$$ $\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}}( \tilde{\tilde{c}})\leq\operatorname{DegP}_{{\mathcal{B}}_{\text{PLAA}}^{\text{ GRPE},{\mathcal{U}}}}(c),$ $$

which contradicts that the target concept $c(x)$ is the min-degree interpolator w.r.t. the independent set ${\mathcal{B}}_{\text{PLAA}}^{\text{GRPE},{\mathcal{U}}}$ on ${\mathcal{X}}_{N_{0}}$.

## Appendix B Experiments

### B.1 Position Embeddings for Length Generalization

For the URF $n$-addition training data, we first sample the lengths of two addends uniformly from $\{1,\dots,n\}\times\{1,\dots,n\}$. For two addends of lengths $(n_{1},n_{2})$, we then samples from $[10^{n_{1}-1},10^{n_{1}}-1]\times[10^{n_{2}-1},10^{n_{2}}-1]$ (If $n_{i}=0$, then the corresponding sample interval is $[0,9]$). This is to guarantee the addends are length-uniform. For the addition
$x_{n_{1}-1}\dots x_{0}+y_{n_{2}-1}\dots y_{0}=z_{n_{3}}z_{n_{3}-1}\dots z_{0}$, the training instance is

$$ $\mathtt{b\,x_{0}\,\dots\,x_{n_{1}-1}\,+\,y_{0}\,\dots\,y_{n_{2}-1}\,=\,z_{0}\, \dots\,z_{n_{3}-1}\,z_{n_{3}}\,e}.$ $$

Here, we add spaces between the characters to ensure each is tokenized separately. We use “$\mathtt{b}$” and “$\mathtt{e}$” instead of “$\mathtt{[BOS]}$” and “$\mathtt{[EOS]}$” for a simpler implementation with the GPT-2 tokenizer. In our experiments, we train with $10000$ URF $4$-addition samples.

We choose GPT-2 with key-only position embeddings as our model. For the RPE and RPE-Square settings, we augment the GPT-2 model with RPE and RPE-Square, respectively. The implementation is adapted from HuggingFace [].

We train the models by AdamW, with the initial learning rate $0.0005$, the weight decay $1.0$, and the cosine scheduler. The warmup ratio is $0.05$.
The gradient accumulation steps is $2$.
The per-device training batch size is $128$. We train the models for $20000$ steps and $200000$ steps. The experiments are run on a server with Ubuntu. All the models are trained on two NVIDIA GeForce RTX 3090 GPUs.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: Broader Task Validation for LDHD Generalization:
Question: Have you considered validating LDHD generalization on a wider set of tasks beyond Boolean functions and addition problems? For instance, tasks involving more complex arithmetic, symbolic reasoning, or planning tasks?
Suggestion: Expanding the evaluation to include a broader range of reasoning-intensive tasks would demonstrate the generality and practical applicability of LDHD generalization. Additionally, comparing your findings with those of other approaches to length generalization, such as Kazemnejad et al. (2024) and Lee et al. (2023), could add value by highlighting their relative strengths and limitations.

Justification and Generality of Assumptions:
Question: Can you provide more insights into the practical applicability of the minimal nuclear norm solution conjecture (Assumption 2) and other key assumptions? Are there scenarios in which these assumptions may not hold, and how might that affect LDHD generalization?
Suggestion: It would be helpful to clarify the scope of these assumptions, perhaps by discussing or empirically validating their generality across different architectures. Exploring whether alternative assumptions or regularization techniques could produce similar results would provide a more robust foundation for your theoretical contributions.

Improving Theoretical Accessibility:
Question: Would you consider adding intuitive explanations or diagrams alongside the formal theoretical sections to enhance accessibility, especially for concepts like the degree-profile bias and min-degree interpolators?
Suggestion: While the formal proofs are well-structured, additional explanations or illustrations could help a broader audience appreciate the theoretical underpinnings of LDHD generalization. Visual aids representing the concept of low-to-high dimensional shifts, for example, might clarify these ideas.

Implications of LDHD Generalization for Other Architectures:
Question: Do you envision LDHD generalization principles applying to architectures beyond transformers, such as Graph Neural Networks (GNNs) or Recursive Neural Networks (RNNs)? If so, could you provide insights on how LDHD generalization might be adapted to these structures?
Suggestion: Discussing the potential applicability of LDHD generalization principles to other architectures could broaden the relevance of your contributions. Exploring cases where GNNs or RNNs might also benefit from LDHD-inspired inductive biases would make the work more versatile and impactful.



Broader Analysis of RPE-Square Design Choices:
Question: Could you provide more details on the design decisions for RPE-Square, such as the choice of distance metrics or the arrangement of special tokens? Have you tested alternative configurations? If so, how do they affect performance?
Suggestion: Analyzing the impact of design choices within RPE-Square, possibly through an ablation study, would provide a deeper understanding of what makes this embedding effective. Additionally, extending RPE-Square evaluations to other domains (e.g., symbolic logic or planning tasks) would clarify its generalizability.
Explicit Discussion on Potential Limitations:
Question: Are there specific conditions or model architectures where LDHD generalization might fail, even with well-designed inductive biases? Could you outline any known limitations or failure modes?
Suggestion: A section explicitly discussing possible limitations or boundary conditions for LDHD generalization would provide a more balanced perspective on the approach’s applicability. This could include insights into cases where training and testing distributions diverge significantly or where high-dimensional testing distributions have features not represented in low-dimensional training data.
Relation to Recent Work in Length Generalization:
Question: How does LDHD generalization relate to recent studies on length generalization, such as Ahuja & Mansouri (2024) and Zhou et al. (2024)? Could you provide a deeper comparison of LDHD positions relative to these approaches?
Suggestion: Discussing how LDHD generalization contrasts with or complements other length generalization strategies would provide a clearer contextual foundation. This would also help highlight your framework’s unique contributions, especially regarding scaling challenges and inductive bias requirements.

Addressing these questions and suggestions would clarify the framework’s applicability, limitations, and comparative advantages, helping to deepen the impact and reach of the paper’s contributions.
soundness: 2
strengths: Broader Empirical Validation:
While the theoretical analysis and specific experiments (e.g., RPE-Square’s impact) are well-supported. However, the paper would benefit from a broader empirical evaluation across different models and datasets, especially complex reasoning tasks beyond Boolean functions. The current examples, while illustrative, may not fully capture the diversity of real-world data distributions. Including results from larger-scale datasets, such as multi-step arithmetic tasks or complex symbolic logic problems, would more effectively validate LDHD generalization and highlight its practical applicability.
Additionally, comparisons with alternative approaches to length generalization (such as recent Transformer variants or other positional encoding methods) would provide a more comprehensive view of where LDHD generalization stands in practice.

Explicit Justification of Assumptions:
Certain assumptions, such as those in the matrix factorization regularization conjecture (Assumption 2), are crucial to the theoretical claims but have not been fully explored. While empirical results partially support these assumptions, more discussion of their generalizability and limitations would be helpful. For example, analyzing situations where Assumption 2 may not hold could offer insights into potential failure cases, enhancing the robustness of the claims.

Increased Clarity in Technical Sections:
Some theoretical sections, particularly regarding the degree-profile bias and proofs for the PLAA models, are dense and may be challenging for readers less familiar with these concepts. Adding more intuitive explanations alongside formal definitions could make these sections more accessible. Diagrams illustrating key ideas, such as the shift from low-dimensional to high-dimensional spaces or the impact of different inductive biases, would also aid comprehension.
Furthermore, clarifying how specific model components contribute to LDHD generalization in practical tasks (beyond theoretical guarantees) could make the theoretical claims more relatable and actionable for practitioners.

Deeper Analysis of LDHD Limitations:
The LDHD generalization framework is theoretically strong, but discussing limitations or boundary conditions more explicitly would be beneficial. For instance, scenarios where LDHD generalization may fail—even with the proposed inductive biases—or limitations in scaling to very high dimensions could be explored. This would provide a balanced perspective on the framework’s applicability.

More Contextualization within Prior Work:
While the paper acknowledges related literature, it could provide a deeper comparison with recent works on length generalization (e.g., Ahuja & Mansouri 2024, Zhou et al. 2024) and other inductive bias approaches in Transformer architectures. Explaining how LDHD generalization and RPE-Square offer improvements or distinct advantages over these approaches would strengthen the contextual foundation. Additionally, discussing whether existing models like Recursive Neural Networks (RNNs) or Graph Neural Networks (GNNs) could benefit from LDHD generalization principles would broaden the relevance of the contributions.

Position Embedding Design Evaluation:
The RPE-Square embedding demonstrates promise, but a more thorough ablation study evaluating its impact under various configurations (e.g., different distance metrics or special token arrangements) would provide a more detailed understanding of its robustness. Testing RPE-Square in domains beyond the addition task, such as symbolic reasoning or multi-step logical tasks, could further establish its versatility and performance consistency across data formats.

In summary, enhancing empirical validation, refining theoretical assumptions, and providing further clarity and contextualization would elevate the strength and reach of this paper’s contributions. These additions would also help bridge the gap between theoretical insights and practical applicability in diverse model architectures and reasoning tasks.
summary: This paper introduces Low-Dimension-to-High-Dimension (LDHD) generalization, a framework addressing the challenge of generalizing from low-dimensional training data to high-dimensional testing data, which is relevant in Out-of-Distribution (OOD) generalization scenarios. LDHD generalization captures the scaling issues in reasoning tasks, where models trained on small-scale data must generalize to larger, more complex cases. The authors theoretically demonstrate that LDHD generalization is unattainable without incorporating inductive biases, formalized through a version of the “No-Free-Lunch Theorem.”

The paper explores LDHD generalization specifically in Boolean functions and presents findings that different architectures under Stochastic Gradient Descent (SGD) can achieve LDHD generalization if the model’s inductive bias aligns with the target function. It introduces Random Feature Models with Projection (RFMP) and position-only linear attention with Advice (PLAA) models and examines how their biases support LDHD generalization.

In practical applications, the authors propose the RPE-Square position embedding as an enhancement of the standard Relative Position Embedding (RPE). RPE-Square is designed to improve length generalization in cases with unaligned data formats. Additionally, the paper provides insight into Chain-of-Thought (CoT) reasoning, suggesting that it extends the latent space without increasing dimensionality, thus supporting LDHD generalization.

The paper contributes a new perspective on generalization challenges in reasoning tasks. It emphasizes the role of inductive biases and offers practical methods for achieving length generalization in complex models.
weaknesses: The paper introduces a valuable perspective with LDHD generalization; however, it could be strengthened by addressing certain weaknesses in both its theoretical and experimental approaches.

Limited Empirical Scope:
While the theoretical contributions are strong, the experimental validation is limited in scope. The paper primarily demonstrates LDHD generalization through RPE-Square on specific cases, such as addition tasks. Testing a broader range of tasks, such as multi-step logical reasoning, symbolic manipulation, or mathematical operations, would provide a more convincing demonstration of the applicability of LDHD generalization. Expanding beyond Boolean functions to real-world data sets in NLP or other reasoning tasks would further validate the practicality of the approach.

Additionally, comparing the performance of RPE-Square with other recent advances in length generalization, such as transformer variants designed for reasoning (e.g., Kazemnejad et al., 2024) or models trained on complex arithmetic tasks (e.g., Lee et al., 2023), would highlight RPE-Square’s strengths and limitations.

Assumption Dependence and Generality:
Certain key assumptions in the theoretical framework, like those in the minimal-nuclear-norm-solution conjecture (Assumption 2), may not hold universally, potentially limiting the framework’s generality. The assumptions play a significant role in supporting the theoretical findings, so the paper could benefit from a more detailed examination of their applicability and limitations. For instance, providing empirical tests or theoretical discussions on where these assumptions might fail would offer a more balanced understanding of LDHD generalization’s robustness.

Exploring whether alternative assumptions or regularization methods could yield similar results would help generalize the framework. This would make the theoretical claims more robust and adaptable to a wider range of models.

Theoretical Accessibility and Clarity:
The paper’s dense theoretical sections, especially those regarding the degree-profile bias and proofs for the PLAA model, may be challenging for readers without a strong background in this area. Adding intuitive explanations or visual aids alongside the formal proofs could significantly improve readability and accessibility. A step-by-step breakdown of key concepts, particularly for the degree profile and min-degree interpolator, would make these sections easier to understand.

Diagrams illustrating key ideas, such as low-to-high dimensional shifts or how different inductive biases support LDHD generalization, would also help clarify the framework’s mechanisms.

Deeper Analysis of LDHD Generalization’s Practical Implications:
The paper would benefit from a more explicit discussion of the practical limitations of LDHD generalization. While LDHD is theoretically promising, acknowledging potential challenges—such as cases where the high-dimensional space differs fundamentally from training distributions—would strengthen the work. Highlighting when LDHD generalization may fail, even with well-designed inductive biases, would provide a balanced perspective.
Furthermore, discussing the implications of the LDHD framework for models beyond transformers, such as Graph Neural Networks (GNNs) or Recursive Neural Networks (RNNs), would broaden its relevance and demonstrate the approach's flexibility.

Limited Contextualization within Recent Length Generalization Research:
Although the paper addresses related work, it could better contextualize LDHD generalization relative to recent advances. Comparing LDHD with other generalization frameworks, especially recent developments in length generalization (e.g., Ahuja & Mansouri, 2024; Zhou et al., 2024), would clarify its unique contributions and limitations.
Providing insights into whether the LDHD framework could be adapted for methods beyond transformers, such as RNNs or CNN-based architectures, would also enrich the discussion. Additionally, examining whether other position encoding methods, such as rotary embeddings, would benefit from an LDHD perspective could reveal additional practical insights.

Broader Evaluation of RPE-Square Design Choices:

While RPE-Square demonstrates improvements in the addition task, a more comprehensive evaluation of its design would be valuable. The current analysis could be strengthened by testing RPE-Square under various conditions, such as different distance metrics, transformations, or arrangements of special tokens. This would provide a deeper understanding of its robustness across task variations.

Extending RPE-Square’s evaluation to additional domains, such as symbolic logic, planning, or other reasoning-intensive tasks, would demonstrate its versatility and generalizability. Additionally, an ablation study to understand the specific impact of each component (e.g., relative vs. absolute position aspects) would clarify the primary drivers of its performance gains.

The paper would benefit from broader empirical validation, expanded theoretical clarity, and deeper contextualization. These enhancements would make LDHD generalization’s theoretical and practical implications more robust, accessible, and impactful, better aligning the work with its stated goals.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See above
soundness: 3
strengths: - This subspace-centric perspective on length generalization is interesting.
- The results on decoder-only transformers build nicely on previous work and provide a nice connection to the rank of the attention.
- rpe squared encodings seem to work for URF.
summary: By studying length generalization through the lens of generalization from lower to higher dimensional subspaces, the paper provides results that explain why this length generalization is hard to achieve with modern architectures.

More specifically, the paper tackles the problem of length generalization in modern deep learning architectures. A representative example is the addition of numbers that are larger than any numbers that have appeared in the training data. The paper's main approach is to frame this kind of generalization as a generalization ability to embeddings that come from a subspace of larger dimension than the dimension of the training data and is termed Low-Dimension-to-High-Dimension (LDHD) generalization.

Theorem 1 establishes a no free lunch theorem stating that, without introducing additional assumptions (e.g., by having priors on the function that is being learned by incorporating some kind of inductive bias), it's not possible to generalize to a higher dimensional subspace. Intuitively, this is because the additional dimensions appearing in the test set are orthogonal to those in the training set and therefore it's by construction impossible to infer anything about them from the training data. The paper then looks at different models and studies their structural biases.

Theorem 2 establishes that, in the limit, the random feature model with projection converges to a minimum degree interpolator with respect to an independent set defined by the projection. This  implies that LDHD generalization is only achievable for a restricted set of functions that depend on the subspace of the training set. A similar result is shown for a certain class of decoder only transformers. An additional result is provided for transformers with absolute positional encodings, where it is shown that if the rank of the attention matrix required for the target function exceeds the dimension of the subspace that the training data live in, then LDHD generalization is not possible. Finally, a result is given for generalized relational positional encodings where again we are shown that in the limit, training converges to a minimum degree interpolator with respect to the independent sets induced by the positional encodings. These results all reinforce the idea that generalizing to arbitrary length sequences with some standard ML models is going to be challenging.
These ideas are used to argue that Chain of Thought is potentially effective in length generalization partly because it doesn't increase the dimensionality of the space for test data.

Finally, some positional encodings are proposed to alleviate the challenges that arise from using an URF encoding.
weaknesses: I find confusing the way certain sections of this paper are written which makes the overall story and contribution hard to tease out:

- What is the motivation behind the random model with projections? The result about the Fourier basis has been established in previous work. The paper claims around line 262 that not all RFMP models converge to the min-degree interpolator. However, theorem 2 esentially establishes that if we do a change of basis for the data then the min-degree interpolator is achieved on the projected fourier basis. 
I don't see why theorem 2 is necessary to state corollary 1. Doesn't corollary 1 follow from the theorem in Abbe et al's paper?
I think it's unclear what exactly theorem 2 contributes to the discussion since it follows straightforwardly from the original result.

- Since chain of thought appears to improve results in those kinds of tasks, it seems important to understand how it fits into the LDHD generalization perspective. The paper provides a short discussion suggesting that CoT avoids increasing the dimensionality of the hidden space in which the data lie on and says that it 'extends the field' that is used by allowing for a symbol with undetermined values. It is not explained why this could be helpful (though it is suggested in the paper) to learn the correct target concept nor what quantitative predictions one can extract from this framing of CoT.  Why isn't CoT enough to deal with the generalization issue?

- I don't see how the proposed positional encodings connect to the contributions of this paper and the analysis that precedes them (line 431 claims that's the case). The subspace-centric view as I understand it is introduced so that the generalization problem is characterized in the hidden space. On the other hand, the paper seems to suggest that URF format makes generalization harder, or no? How does that connect with the comments about CoT being able to deal with the dimensionality of the hidden space? Why is CoT not enough and why are rpe-squared encodings needed? Do they somehow address the rank deficiency that is discussed in Corollary 2?

- The paper states in line 471: The design of RPE-Square illustrates how the principle can lead to position embeddings for better length generalization. What principle?  It addressed the URF formatting issue, but that seems orthogonal to the previous discussion.

Overall, I find the contribution of the paper potentially interesting, but it is quite hard to disentangle what the actual takeaways are from the paper. This is exacerbated by the writing being confusing and/or unclear in certain places that I have indicated. Until some of those things are cleared up I cannot recommend acceptance but I am obviously open to changing my score after the rebuttal.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: 1.  **Thm 1 & Cor 1**: 
    - Can you explain why the min-degree interpolator cannot capture functions with $I(f)\not\subset [N_0]$?  
    - Does Cor. hold for any projection $V$? Then, 1) what's the purpose of adding the projection to the RFM? and 2) how can designing $V$ (line 287) enable LDHD generalization if the target function has a dependence on higher dimensions?
2.  **Sec 4.2**: I don't understand the intuition behind the PLAA model:
    - on notations: 1) i didn't find $\mathcal{U}_N$ in notations. Is it referring to upper triangular matrices? 2) Is $x$ a sequence of $\{\pm1\}$? Then what does it mean "value of $x_i$ is identical to itself" (line 307)?
    - What is the motivation for defining PLAA this way? One thing that confuses me is that if the input is a sequence of all 1s, then PLAA always outputs zero by definition.
    - In Defn 6, the only difference to PLAA, is adding an upper triangular mask on top of the weights. while in PLAA, the learnable parameters are already constrained to be upper triangular. Where is the APE here?

3.  Can you also explain your proposed RPE-squared positional encoding? How do your previous results explain the improvement in the performance? Do you characterize how this PE changes the inductive bias which leads to generalization or is this just a heuristic suggestion?
soundness: 3
strengths: The paper's perspective on length generalization is interesting. The authors look at different theoretical models to show how solutions to the LDHD problem can change as the models are refined. Although the empirical examples are limited, they have brief results on the empirical implications of their theoretical analysis.
summary: This paper frames the length generalization problem in tasks like addition as a low-dimensional to high-dimensional (LDHD) generalization problem. With this motivation, the paper studies LDHD generalization in two theoretical setups on Boolean functions, with Boolean input sequences of length $N$. Here, the data dimensionality is controlled by the number of final positions fixed to 1—that is, sequences coming from a low-dimensional space of size  $N_0 < N$ have the last $N - N_0$ positions set to 1. 

In the first setup, the authors consider a random feature model *with projection* (RFMP), where the inputs are first projected into a subspace defined by matrix $V$ before being passed through an RFM. Extending the result in Abbe et al. (2023), they show gradient descent (GD) converges to a minimum degree interpolator, now with respect to a basis that depends on the choice of $V$. They use this result to argue that if the ground truth Boolean function depends on the higher dimensions of the input, the min-norm interpolator of the low-dimensional data will fail to capture it. 

The second setup considers variations of linear attention models, simplified to focus on the role of positional embedding. Here, they show that different positional embedding changes the inductive bias of GD by changing the bases with respect to which the min degree interpolator is chosen. Motivated by these findings, they suggest adjustments to the relative positional encoding that helps with length generalization for addition.
weaknesses: I found the paper a bit hard to parse and making connections between different parts of the results was challenging to me. I believe if the authors use some of the remaining space within the page limit to discuss the high-level/intuitive connections of their results in more detail or discuss proof sketches, it would improve the paper's clarity. As it stands, I find it difficult to fully grasp the results.

I will list some of the points I had trouble following as questions below. It’s possible that I missed some aspects of the paper. Thus, I'm open to reconsidering my score if needed.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
questions: More specifically, I think the authors should address these following points to make the introduction more understandable:

L052: I don't understand Example 1. How does this example illustrate LDHD?
L062: What does relative position embedding have to do with the main thesis of this paper? I find this remark to be distracting.

L076: What is a "concept"? How does this show up in Example 1 and 2? Neither example 1 nor 2 have a label. Also, the notation phi is completely new. If the examples are meant to motivate Assumption 1, it should be made clear.

L088: Why is Sigma a field now? In example 1 and 2, Sigma is the set of tuple of digits.

L096: How is the No-Free Lunch theorem relevant here? The No-Free Lunch Theorem says that there's no learning algorithm is can be optimal for all problem instances. I don't see the relevance to LDHD.

L102: What is "minimal degree-profile bias"?
L107: What are "independent sets"? Do you mean "linearly independent"?
soundness: 4
strengths: This is an important problem. The authors made commendable efforts in understanding LDHD for Boolean functions and connections to the implicit regularization line of research to decipher what kind of inductive may or may not be helpful for LDHD.
summary: This paper is about a notion similar to domain adaption, but tailored to scenarios found in large language models, that the authors named low-dimension-to-high-dimension (LDHD) generalization. The authors give generic impossibility results in the style of the No-Free-Lunch theorem, and also specific impossibility results for several models, drawing attention to the issue that LDHD cannot happen without inductive bias.
weaknesses: The main issue for me is with the presentation and the writing. There is a big conceptual gap between the introduction, especially the two examples given involving addition, with the rest of the paper. After reading examples 1 and 2, I still don't have sense of the relevance toward LDHD that they are intending to convey. Due to this, I find the introduction to be difficult to understand.

It is not clear how the notion of LDHD relates to previous works on domain adaptation e.g., [1]. The only novelty in Definition 1 seems to be that the two domains are nested and both are included inside a larger ambient space. This scenario can be captured by previous notions of OOD generalization.

Given that Boolean functions play an important role, there should be more discussions about what is degree, what is the intuition behind degree profiles.

Assumption 2 has been refuted in [2]. While this doesn't invalidate results from Sec 4.2, I feel that this should be discussed.

[1] David, Shai Ben, et al. "Impossibility theorems for domain adaptation." Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2010.

[2] Li, Zhiyuan, Yuping Luo, and Kaifeng Lyu. "Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning." International Conference on Learning Representations.

Meta-review: This paper investigates the Low-Dimension-to-High-Dimension (LDHD) generalization, where the training data is assumed to live in a low-dimensional subspace of the high-dimensional testing space. 
The paper presents a "hardness result" for Boolean functions, showing that LDHD generalization is generally unattainable unless some form of inductive bias is introduced based on prior information.

While the paper offers some interesting insights into LDHD generalization, **all reviewers** agreed that the presentation could be significantly improved to help readers better understand the contributions of this work. 
The authors actively engaged with the reviewers during the rebuttal phase; however, they were unable to convince all reviewers that the paper is ready for publication in its current form.

As a result, I recommend rejecting the paper.

Decision: Reject