# On the Mirage of Long-Range Dependency, with an Application to Integer Multiplication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 33 references that are in the map.
- First posted on arXiv 30 Mar 2026.

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Chain of Code: Reasoning with a Language Model-Augmented Code Emulator](https://mlsanity.com/paper/2312.04474/) (2023)
- [Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Tasks](https://mlsanity.com/paper/2402.04248/) (2024)
- [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [Cellular automata as convolutional neural networks](https://mlsanity.com/paper/1809.02942/) (2018)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [Length Extrapolation of Transformers: A Survey from the Perspective of Positional Encoding](https://mlsanity.com/paper/2312.17044/) (2023)
- [Language Models Do Hard Arithmetic Tasks Easily and Hardly Do Easy Arithmetic Tasks](https://mlsanity.com/paper/2406.02356/) (2024)
- [Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count](https://mlsanity.com/paper/2410.15787/) (2024)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [Dissecting Multiplication in Transformers: Insights into LLMs](https://mlsanity.com/paper/2407.15360/) (2024)
- [Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls](https://mlsanity.com/paper/2510.00184/) (2025)
- [Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks](https://mlsanity.com/paper/2502.16763/) (2025)
- [On the Spatiotemporal Dynamics of Generalization in Neural Networks](https://mlsanity.com/paper/2602.01651/) (2026)
- [Solving the multiplication problem of a large language model system using a graph-based method](https://mlsanity.com/paper/2310.13016/) (2023)

## Abstract (arXiv)

Integer multiplication has long been considered a hard problem for neural networks, with the difficulty widely attributed to the O(n) long-range dependency induced by carry chains. We argue that this diagnosis is wrong: long-range dependency is not an intrinsic property of multiplication, but a mirage produced by the choice of computational spacetime. We formalize the notion of mirage and provide a constructive proof: when two n-bit binary integers are laid out as a 2D outer-product grid, every step of long multiplication collapses into a 3 × 3 local neighborhood operation. Under this representation, a neural cellular automaton with only 321 learnable parameters achieves perfect length generalization up to 683× the training range. Five alternative architectures -- including Transformer (6,625 params), Transformer+RoPE, and Mamba -- all fail under the same representation. We further analyze how partial successes locked the community into an incorrect diagnosis, and argue that any task diagnosed as requiring long-range dependency should first be examined for whether the dependency is intrinsic to the task or induced by the computational spacetime.