Imagen de Portada

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Merrill, William, Sabharwal, Ashish
Formato:	Preprint
Publicado:	2025
Materias:	Machine Learning Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

The Expressive Power of Transformers with Chain of Thought
por: Merrill, William, et al.
Publicado: (2023)

Exact Expressive Power of Transformers with Padding
por: Merrill, William, et al.
Publicado: (2025)

A Logic for Expressing Log-Precision Transformers
por: Merrill, William, et al.
Publicado: (2022)

Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't
por: Svete, Anej, et al.
Publicado: (2026)

The Illusion of State in State-Space Models
por: Merrill, William, et al.
Publicado: (2024)

Why Are Linear RNNs More Parallelizable?
por: Merrill, William, et al.
Publicado: (2026)

The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
por: Brösamle, Moritz, et al.
Publicado: (2026)

On the Expressive Power and Limitations of Multi-Layer SSMs
por: Zubić, Nikola, et al.
Publicado: (2026)

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
por: Li, Xiaoyu, et al.
Publicado: (2024)

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers
por: Wang, Xiao
Publicado: (2026)

Context-Free Recognition with Transformers
por: Jerad, Selim, et al.
Publicado: (2026)

Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
por: Gui, Kaiwen, et al.
Publicado: (2023)

A Little Confidence Goes a Long Way
por: Scoville, John, et al.
Publicado: (2024)

A Little Human Data Goes A Long Way
por: Ashok, Dhananjay, et al.
Publicado: (2024)

Impossibility of Depth Reduction in Explainable Clustering
por: Deng, Chengyuan, et al.
Publicado: (2023)

A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention
por: Ye, Xiaowei, et al.
Publicado: (2026)

On the Computational Hardness of Transformers
por: Saha, Barna, et al.
Publicado: (2026)

A Little Help Goes a Long Way: Efficient LLM Training by Leveraging Small LMs
por: Rawat, Ankit Singh, et al.
Publicado: (2024)

Constant Bit-size Transformers Are Turing Complete
por: Li, Qian, et al.
Publicado: (2025)

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
por: Amiri, Alireza, et al.
Publicado: (2025)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
por: Li, Zhiyuan, et al.
Publicado: (2024)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
por: Li, Qian, et al.
Publicado: (2026)

Fundamental Limitations on Subquadratic Alternatives to Transformers
por: Alman, Josh, et al.
Publicado: (2024)

On Computational Limits of FlowAR Models: Expressivity and Efficiency
por: Cao, Yang, et al.
Publicado: (2025)

What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?
por: Xu, Ruihan, et al.
Publicado: (2025)

A Little Rank Goes a Long Way: Random Scaffolds with LoRA Adapters Are All You Need
por: Hazan, Hananel, et al.
Publicado: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
por: Shpilka, Amir, et al.
Publicado: (2026)

Catalytic Computing and Register Programs Beyond Log-Depth
por: Alekseev, Yaroslav, et al.
Publicado: (2025)

Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
por: London, Charles, et al.
Publicado: (2025)

Provably Overwhelming Transformer Models with Designed Inputs
por: Stambler, Lev, et al.
Publicado: (2025)

Additive Models Explained: A Computational Complexity Approach
por: Bassan, Shahaf, et al.
Publicado: (2025)

On the Power of Interactive Proofs for Learning
por: Gur, Tom, et al.
Publicado: (2024)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
por: Rohatgi, Dhruv, et al.
Publicado: (2025)

Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets
por: Jacot, Arthur
Publicado: (2025)

Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
por: Cao, Yang, et al.
Publicado: (2025)

Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
por: Hu, Jerry Yao-Chieh, et al.
Publicado: (2024)

Learning Tree Pattern Transformations
por: Neider, Daniel, et al.
Publicado: (2024)

Are Depth-2 Regular Expressions Hard to Intersect?
por: Ascone, Rocco, et al.
Publicado: (2025)

Optimal Depth-Three Circuits for Inner Product
por: Gurumukhani, Mohit, et al.
Publicado: (2026)

Efficient Turing Machine Simulation with Transformers
por: Li, Qian, et al.
Publicado: (2025)