# Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization

arXiv: https://arxiv.org/abs/2410.08898 · HTML: https://mlsanity.com/paper/2410.08898/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 39 references that are in the map.
- First posted on arXiv 11 Oct 2024.

## Builds on (most cited first, 30 of 33)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Out-of-Distribution Generalization via Risk Extrapolation (REx)](https://mlsanity.com/paper/2003.00688/) (2020)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Mathematical Capabilities of ChatGPT](https://mlsanity.com/paper/2301.13867/) (2023)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Planning with Large Language Models for Code Generation](https://mlsanity.com/paper/2303.05510/) (2023)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Towards a Theoretical Framework of Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.04496/) (2021)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Neural Redshift: Random Networks are not Random Functions](https://mlsanity.com/paper/2403.02241/) (2024)

## Built on by (most cited first, 2 of 2)

- [Number Cookbook: Number Understanding of Language Models and How to Improve It](https://mlsanity.com/paper/2411.03766/) (2024)
- [On the Limitations and Capabilities of Position Embeddings for Length Generalization](https://mlsanity.com/paper/2510.04130/) (2025)

## Abstract (arXiv)

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.