Cover Image

The Condensate Theorem: Transformers are O(n), Not $O(n^2)$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Williams, Jorge L. Ruiz
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Artificial Intelligence Computation and Language
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

When Can Transformers Count to n?
by: Yehudai, Gilad, et al.
Published: (2024)

GPG: Generalized Policy Gradient Theorem for Transformer-based Policies
by: Mao, Hangyu, et al.
Published: (2025)

Transformers Can Represent $n$-gram Language Models
by: Svete, Anej, et al.
Published: (2024)

Most Likely Sequence Generation for $n$-Grams, Transformers, HMMs, and Markov Chains, by Using Rollout Algorithms
by: Li, Yuchao, et al.
Published: (2024)

How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse
by: Deng, Yichuan, et al.
Published: (2024)

Steering LLMs for Formal Theorem Proving
by: Kirtania, Shashank, et al.
Published: (2025)

PRISM: Breaking the O(n) Memory Wall in Long-Context LLM Inference via O(1) Photonic Block Selection
by: Park, Hyoseok, et al.
Published: (2026)

Learning to Reason with Insight for Informal Theorem Proving
by: Li, Yunhe, et al.
Published: (2026)

miniCTX: Neural Theorem Proving with (Long-)Contexts
by: Hu, Jiewen, et al.
Published: (2024)

BrokenMath: A Benchmark for Sycophancy in Theorem Proving with LLMs
by: Petrov, Ivo, et al.
Published: (2025)

ATLAS: Autoformalizing Theorems through Lifting, Augmentation, and Synthesis of Data
by: Liu, Xiaoyang, et al.
Published: (2025)

QED-Nano: Teaching a Tiny Model to Prove Hard Theorems
by: LM-Provers, et al.
Published: (2026)

From $\mathcal{O}(n^{2})$ to $\mathcal{O}(n)$ Parameters: Quantum Self-Attention in Vision Transformers for Biomedical Image Classification
by: Boucher, Thomas, et al.
Published: (2025)

An evolutionary perspective on modes of learning in Transformers
by: Ku, Alexander Y., et al.
Published: (2025)

Ineq-Comp: Benchmarking Human-Intuitive Compositional Reasoning in Automated Theorem Proving on Inequalities
by: Zhao, Haoyu, et al.
Published: (2025)

FVEL: Interactive Formal Verification Environment with Large Language Models via Theorem Proving
by: Lin, Xiaohan, et al.
Published: (2024)

TPTT: Transforming Pretrained Transformers into Titans
by: Furfaro, Fabien
Published: (2025)

M2R2: Mixture of Multi-Rate Residuals for Efficient Transformer Inference
by: Bhendawade, Nikhil, et al.
Published: (2025)

Easy Problems That LLMs Get Wrong
by: Williams, Sean, et al.
Published: (2024)

The Cursive Transformer
by: Greydanus, Sam, et al.
Published: (2025)

DINT Transformer
by: Cang, Yueyang, et al.
Published: (2025)

mini-vec2vec: Scaling Universal Geometry Alignment with Linear Transformations
by: Dar, Guy
Published: (2025)

Three-Phase Transformer
by: Ayyash, Mohammad R. Abu
Published: (2026)

The Belief State Transformer
by: Hu, Edward S., et al.
Published: (2024)

NVIDIA Nemotron Nano 2: An Accurate and Efficient Hybrid Mamba-Transformer Reasoning Model
by: NVIDIA, et al.
Published: (2025)

Fast Byte Latent Transformer
by: Kallini, Julie, et al.
Published: (2026)

On the Ability of Transformers to Verify Plans
by: Sarrof, Yash, et al.
Published: (2026)

Selective Attention Improves Transformer
by: Leviathan, Yaniv, et al.
Published: (2024)

Algorithmic Capabilities of Random Transformers
by: Zhong, Ziqian, et al.
Published: (2024)

Transformers Struggle to Learn to Search
by: Saparov, Abulhair, et al.
Published: (2024)

An Evolved Universal Transformer Memory
by: Cetin, Edoardo, et al.
Published: (2024)

Your Transformer is Secretly Linear
by: Razzhigaev, Anton, et al.
Published: (2024)

TransformLLM: Adapting Large Language Models via LLM-Transformed Reading Comprehension Text
by: Arbel, Iftach, et al.
Published: (2024)

Less is More: Understanding Word-level Textual Adversarial Attack via n-gram Frequency Descend
by: Lu, Ning, et al.
Published: (2023)

"I've Seen How This Goes": Characterizing Diversity via Progressive Conditional Surprise
by: Khoriaty, Matthew, et al.
Published: (2026)

The Geometric Anatomy of Capability Acquisition in Transformers
by: Billa, Jayadev
Published: (2026)

Momentum Streams for Optimizer-Inspired Transformers
by: Gai, Jingchu, et al.
Published: (2026)

On the Spatial Structure of Mixture-of-Experts in Transformers
by: Bershatsky, Daniel, et al.
Published: (2025)

Transformer Circuit Faithfulness Metrics are not Robust
by: Miller, Joseph, et al.
Published: (2024)

Representing Rule-based Chatbots with Transformers
by: Friedman, Dan, et al.
Published: (2024)