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

Thank you for your valuable comments. Here are our responses.

Response to Weaknesses:

1. 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.

Example 1 demonstrates the motivation to consider LDHD generalization. Example 2 demonstrates the intuition behind LDHD generalization.

Example 1 illustrates why string length does not faithfully reflect the scale of the problem in addition. More specifically, in ARF and URF, a smaller-scale addition instance can have the same length or even larger length than a larger-scale one. This mismatch is because the string length is affected by both the scale and the data format.

Example 2 illustrates the typical length generalization in addition and motivates the LDHD perspective for length generalization. More concretely, in addition, an $n$-addition can be represented by an $n$-dimension state vector, where each dimension indicates one digit of the two addenda. The scale of an addition instance is reflected by the dimension of the state vector.

The line of the introduction goes as follows:

1. String length does not precisely capture the scaling challenge in length generalization.
2. Illustrate 1) by Example 1.
3. Due to 1), a new formulation of length generalization is required. But how?
4. Illustrate the intuition of length generalization in practice by Example 2.
5. According to the intuition, we then propose our LDHD framework to characterize the problem scaling.

2. 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.

The novelty of LDHD generalization cannot be captured by domain adaptation or OOD generalization.

• LDHD generalization is a special case of unseen generalization, which is focused on the generalization to the instances that are not in the support set of the training distribution. While unseen generalization can be seen as a type of OOD generalization, the general notion of OOD generalization is insufficient to capture the challenge of unseen generalization. Particularly, while previous works on domain adaptation typically assume the training distribution and the testing distribution are somewhat "close" (e.g., small distance), unseen generalization makes no such assumptions.
• LDHD generalization cannot be fully captured by the notation unseen generalization, either. The main point of LDHD generalization is to characterize a family of unseen generalization with a special structure, i.e., the testing instances can be of higher dimension than the training ones. This structure captures the inherent scaling challenge in length generalization.

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

The degree of a Boolean function is the degree of the Fourier expansion of the Boolean function, a polynomial. The degree profile can be roughly seen as the distribution of the degrees of the monomials in the polynomial. Intuitively, the degree profile reflects the "complexity" of the Boolean function. A lower-degree-profile Boolean function uses fewer variables or combines them more simply than a higher-degree-profile one.

In our work, we generalize the concept of the degree profile by defining it with respect to a set of linearly independent polynomials that are not necessarily the Fourier basis. Using this generalized degree profile, we demonstrate how different models converge to different Boolean functions, thereby determining whether they achieve LDHD generalization.

We appreciate your advice and will provide more background on Boolean analysis in our updated manuscript.

Thank you for your questions and valuable feedback.

The core of our paper is the LDHD generalization perspective for length generalization and all our results revolve around this perspective. Motivated by the lack of a proper framework for general length generalization, we introduce the LDHD generalization perspective in Section 3. We show LDHD generalization is inherently difficult due to the No-Free-Lunch Theorem of LDHD generalization, and thus prior knowledge is required to achieve this generalization. Since prior knowledge is necessary for LDHD generalization, in Section 4, we analyze how different models encode different prior knowledge as inductive biases, which decide when a model can or cannot achieve LDHD generalization. In Section 5, we further connect the LDHD generalization perspective to two practical techniques, i.e., CoT and PE. We will include more explanations about the LDHD generalization perspective for length generalization and the results in Section 4 and the implications in Section 5 accordingly. Here are our responses to the listed questions.

1. Thm 1 & Cor 1

• Can you explain why the min-degree interpolator cannot capture functions with $I(f)\not\subset [N_0]$?

This is because a min-degree interpolator $f$ on $\mathcal{X}_{N_0}$ always satisfies $I(f) \subset [N_0]$.

Otherwise, assume that $f$ is a min-degree interpolator on $\mathcal{X}_{N_0}$ but $I(f)\not\subset [N_0]$.

Let $\tilde{f}(x)$ be the function constructed by fixing all $x_i$, $i\not\in [N_0]$ to $1$. By the construction, we have $\tilde{f}(x)=f(x)$ for all $x$ in $\mathcal{X}_{N_0}$, which is thus also an interpolator.

However, $\text{DegP}(\tilde{f}) < \text{DegP}(f)$, contradicting the assumption that $f$ is the min-degree interpolator. Therefore, for a target function $f^*$ with $I(f^*)\not\subset [N_0]$, the min-degree interpolator on $\mathcal{X}_{N_0}$ cannot be equal to $f^*$.

• 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 (line 287) enable LDHD generalization if the target function has a dependence on higher dimensions?

We require the columns of $V$, i.e., $v_1, \dots, v_r$, to be orthogonal to each other such that $\mathcal{V}$ is a linearly independent set. (To normalize, we suppose $V^\intercal V = I_r$ in the manuscript). Corollary 1 is implied by setting $V=I$ in Theorem 2.

1. We aim to illustrate two points of LDHD generalization via the random feature model with projection (RFMP):

• LDHD generalization is hard to achieve without good prior knowledge;
• Prior knowledge can be encoded by model design.

To elaborate, on the one hand, Theorem 2 implies one projection choice can only achieve LDHD for a very restricted set of problems. If we do not know the right projection, the model may converge to a min-degree interpolator w.r.t. to a different linearly independent set and not be equal to the target function. On the other hand, if we have a good knowledge of the target function, we can simply encode this prior knowledge by choosing a proper projection in the RFMP.

We choose RFM and its variant RFM because RFM is a classic model in the theoretical analysis. We think it beneficial to illustrate our points with such a classic model.

2. By choosing a different projection, the model can converge to a min-degree interpolator w.r.t. a different linearly independent set (denoted by $f$) such that $I(f)$ is not necessary a subset of $[N_0]$. This makes it possible to achieve LDHD generalization for the target function has a dependence on higher dimensions. If we have sufficient prior knowledge of the target function and design a $V$ such that the target function is of minimal degree profile w.r.t. $\mathcal{B}(V)$, then the RFMP with $V$ trained on $X_{N_0}$ is identical to the target function on $X_N$, achieving LDHD generalization.

For example, consider the target function $f(x)=4 x_1 + 3 x_2$ and $N_0=1, N=2$. The min-degree interpolator on $X_{N_0}$ is $f_1(x)=4 x_1\neq f(x)$ does not achieve LDHD generalization. When we add projection and choose $V=[[0.8, 0.6]^\intercal [0.6, -0.8]^\intercal]$, we have $B(V) = \\\{1, 0.8 x_1 + 0.6 x_2, 0.6 x_1 - 0.8 x_2, (0.8 x_1 + 0.6 x_2)(0.6 x_1 - 0.8 x_2)\\\}.$ The min-degree interpolator w.r.t. $B(V)$ is $f_2(x)=4 x_1 + 3 x_2=f(x)$, achieving LDHD generalization for the target function $f$ that has a dependence on the higher dimension than the training space $X_{N_0}$.

Thank you for your insightful feedback.

1. What is the motivation behind the random model with projections?... 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.

The motivation to consider the random model with projections includes two aspects:

1. LDHD generalization is hard to achieve without good prior knowledge;
2. Prior knowledge can be encoded by model design. We want to illustrate these two points with the classic random feature model and its variant, i.e., the random feature model with projection.

Intuitively, in Theorem 2, we show that the model will always converge to the "simplest" solution w.r.t. the given set $\mathcal{B}(V)$ of "projected" functions. We need to know under which set the target function is the "simplest" otherwise LDHD generalization cannot be achieved.

For example, consider the following two function: $f_1(x) = 4 x_1$ and $f_2(x) = 4 x_1 + 3 x_2$. We consider an LDHD generalization scenario where the training data are restricted to {\pm 1}\times{0} but the testing data can be sampled from {\pm 1}^2. Note that the training data for the two functions are the same but the training data cannot distinguish the two functions. Therefore, we have to rely on the prior knowledge, i.e., the choice of $V$ in the model design to achieve length generalization.

For $V_1=I$, $B(V_1)=\\\{1, x_1, x_2, x_1 x_2\\\}$ and the learned model is $f_3(x) = 4 x_1 = f_1(x)$.

For $V_2=[[0.8, 0.6]^\intercal\\ [0.6, -0.8]^\intercal]$, $B(V_2) = \\\{1, 0.8 x_1 + 0.6 x_2, 0.6 x_1 - 0.8 x_2, (0.8 x_1 + 0.6 x_2)(0.6 x_1 - 0.8 x_2)\\\}$ and the learned model is $f_4(x)= 4 x_1 + 3 x_2 = f_2(x)$.

Neither of the designs can achieve LDHD generalization for $f_1(x)$ and $f_2(x)$ simultaneously. On the one hand, this reflects that LDHD generalization is challenging without sufficient prior knowledge of the target; on the other hand, the random model with projections demonstrates how different prior knowledge can be encoded via model design.

Theorem 2 can be seen as a generalization of the Theorem in Abbe et al's paper. While Corollary 1 aims to demonstrate the challenge of LDHD generalization with a concrete example, we understand your concern that it may not fully show the contribution of Theorem 2 because it can be derived from the Theorem in Abbe et al's paper. We'd like to add another example (like the above one), which cannot be implied by Abbe et al's Theorem, to show the role of Theorem 2.

Thank you for your additional comments and for taking the time to carefully review our rebuttal and updated manuscript. We greatly appreciate your constructive feedback and your acknowledgment of the improvements made so far.

1. the significance of the results

We emphasize that the primary contribution of our work is the LDHD perspective for length generalization, which disentangles the inherent scaling generalization and the data format nuisance. Under the LDHD framework, we highlight varying string length is not a good characterization for length generalization and explain certain techniques can help with length generalization or not in different scenarios. We believe our results help to better understand the core of length generalization.

2. the obstacles originating from the format (URF) vs the challenge of subspace generalization and if/how those are related.

The obstacles originating from the format (URF) and the challenge of subspace generalization are two independent aspects of the addition's length generalization.

The challenge of subspace generalization. When we learn to solve the addition from only simple (small-scale) instances, the key is to learn the rule of how the next digit is determined from certain previous digits. Otherwise, we would not be able to solve more complex instances. This rule is solely determined by the type of the operator (i.e., the addition), remaining invariant w.r.t. the format in which the addition instances are presented. (In other words, if the rule changes, then it becomes another operator instead of addition.)

The challenge of subspace generalization is to learn the rule of the addition from samples corresponding to low-dimension subspaces. This is highly non-trivial and requires prior knowledge to encode proper inductive bias. For the addition, "relative distance" introduces the right inductive bias independent of the format.

For example, in the instance "4 5 6 + 7 8 9 = 1 4 6 1", when we are to predict "6" in the sum, we need to consider the digits "5" "6" in the first addend, the digits "8" "9" in the second addend, the digit "4" in the sum, and the result "6" is computed from these digits. We need to learn the rule about which digits are of interest and how these digits decide the result. Only by this rule can we generalize to more complex addition instances. This rule can be effectively represented in the subspace and is invariant to the addition format.

The obstacles originating from the format (URF) Since the model processes a string rather than the latent variable, we cannot apply the rule characterized in the latent space directly but consider the correspondence between the latent variable and the input string, i.e., the data format mapping from latent space to the input space. The data format can be chosen independent of the rule defined in the latent space, i.e., the operator. For example, both ARF and URF are data formats that transform a latent variable representing an addition instance to a string, respectively. While the ARF and URF strings are different, they both correspond to the same operator, the addition.

While the ARF mapping from the latent space to the string space is simple and can be handled by RPE simultaneously, the URF mapping is much more complex. The redundant zeros in the URF are omitted and the instances of the same scale can have different lengths, which cannot be simply captured by relative distance on the string. As a result, it requires extra design to cope with this obstacle originating from the format (URF).

If there are any further concerns or specific points that require additional clarification, we would be more than happy to address them. We respectfully ask you to kindly consider revising your score if the remaining concerns are satisfactorily addressed.

I thank the authors for their detailed responses. After reading these carefully, I can't help but feel that those clarifications that have been provided need to be incorporated in the text. I noticed that other reviewers had similar issues with parsing the text and understanding the rationale/motivation behind some of the results. I believe the paper will benefit from some restructuring and from clearly organizing the main ideas that are needed to achieve length generalization.

This along with stronger evaluations as some of the other reviewers have recommended will probably be sufficient to get this paper over the acceptance threshold. As it is, I find the contribution presented here potentially interesting but it's hard to ultimately figure out the significance of the results, partly because of the way they are written and explained. The updated manuscript is an improvement but in my opinion more work needs to be done, e.g., clearly explaining the obstacles originating from the format (URF) vs the challenge of subspace generalization and if/how those are related.

OK, in my view those explanations need to be added in the text to clearly distinguish between the challenges originating from the format and those that come from LDHD subspace generalization. The impression I was given by reading the text was that LDHD generalization allows us to bypass any format considerations, but based on your explanation that isn't quite the case, since mappings like URF are non-trivial and they need additional care so that the model can handle them (e.g., specific positional encodings). This also relates to CoT since it can in some sense address LDHD but not the formatting issue.

I will increase my score, but I don't think some of the details of the explanations provided in the rebuttal are communicated well in the actual paper.

Thank you for your very detailed review and constructive suggestions.

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?

Since LDHD generalization is a general framework, it can be applied to the length generalization of various reasoning tasks.

To show this, we additionally consider the length generalization in the copy task. In the copy task, given an input sequence $x_1 \dots x_n =$, the goal is to predict the copy of $x$. An instance is like "$x_1 \dots x_n = x_1 \dots x_n$. For length generalization, the training data only include instances whose $n \leq N_0$, while the model is evaluated on data with $N_0 < n \leq N$. In our experiment, we examine the scenario where $N_0=5$ and $N=10$. We compare the length generalization performance of the models with RPE and RPE-Square. The result is presented in the anonymous link: https://www.dropbox.com/scl/fi/6k2jdk1a4hecx55grypdy/length_generalization_copy.pdf?rlkey=y2dkdy16sxgqh882r05werbro&st=6j8w5kfb&dl=0. The results show that RPE-Square achieves near-perfect length generalization while RPE fails. The superiority of RPE-Square over RPE in the length generalization of the copy task demonstrates that LDHD generalization is valid beyond the addition task.

More applications of LDHD generalization are left for future work.

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?

The minimal nuclear norm solution conjecture depicts the inductive bias of the parameterization as matrix factorization, which tends to be low-rank. (Roughly, the matrix nuclear norm can be seen as a good reflection of the matrix rank. There are extensive technical discussions on the relations between the two quantities in the literature of low-rank optimization, which is beyond the scope of this work.) While theoretical conditions under which the assumption holds are technical, some works find this tendency exists in various practical scenarios.

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?

We appreciate your advice and are happy to add intuitive explanations and diagrams. Here, we'd like to illustrate some of the most important concepts intuitively.

• Low-Dimension-to-High-Dimension Shift: Low-dimension-to-high-dimension shift is a type of out-of-distribution shift with the special structure that the testing domain is higher-dimensional than the training domain. For an intuitive illustration, we compare the in-distribution generalization, a typical OOD generalization with distributional shift, and the LDHD generalization in Figure 1 of the anonymous link: https://www.dropbox.com/scl/fi/r8jstagj1dkk0reqeo7vr/comparison_generalization.pdf?rlkey=enzv67jum577bfgtmvgtnlx2j&st=9a4ro5lr&dl=0.
• Degree Profile: Intuitively, a degree profile depicts the overall distribution of the coefficients of items with different degrees in the Fourier expansion of a Boolean function, which is a polynomial. Roughly, the degree profile reflects the complexity of the Boolean function.
• Min-Degree Interpolator: A min-degree interpolator of a dataset is the interpolator of the minimal degree-profile. Intuitively, a min-degree interpolator is the "simplest" function that fits the data.