REVIEW 11 cited by
Circuit Complexity Bounds for RoPE-based Transformer Architecture
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
Characterizing the express power of the Transformer architecture is critical to understanding its capacity limits and scaling law. Recent works provide the circuit complexity bounds to Transformer-like architecture. On the other hand, Rotary Position Embedding ($\mathsf{RoPE}$) has emerged as a crucial technique in modern large language models, offering superior performance in capturing positional information compared to traditional position embeddings, which shows great potential in application prospects, particularly for the long context scenario. Empirical evidence also suggests that $\mathsf{RoPE}$-based Transformer architectures demonstrate greater generalization capabilities compared to conventional Transformer models. In this work, we establish a circuit complexity bound for Transformers with $\mathsf{RoPE}$ attention. Our key contribution is that we show that unless $\mathsf{TC}^0 = \mathsf{NC}^1$, a $\mathsf{RoPE}$-based Transformer with $\mathrm{poly}(n)$-precision, $O(1)$ layers, hidden dimension $d \leq O(n)$ cannot solve the Arithmetic formula evaluation problem or the Boolean formula value problem. This result significantly demonstrates the fundamental limitation of the expressivity of the $\mathsf{RoPE}$-based Transformer architecture, although it achieves giant empirical success. Our theoretical result not only establishes the complexity bound but also may instruct further work on the $\mathsf{RoPE}$-based Transformer.
Forward citations
Cited by 11 Pith papers
-
Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond
A theoretical analysis claims attention networks fail to learn residual features when time series steps have opposite signs, giving a possible explanation for the known advantage of linear residual models.
-
Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
With teacher forcing that reveals pairwise products of the relevant bits, one gradient step lets a single-head attention recover the support of a k-bit AND/OR; the paper's claimed end-to-end hardness lower bound is in...
-
Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
A new algorithm computes RoPE attention in n^{1+o(1)} time under bounded entries by decomposing the attention matrix into a small sum of rescaled Toeplitz matrices, then using FFT.
-
LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers
LazyDiT learns small gates that decide when to reuse cached layer outputs, cutting diffusion transformer compute by up to half while matching or beating DDIM quality.
-
Numerical Pruning for Efficient Autoregressive Models
A Newton's method derived importance score plus a constrained least-squares compensation prunes LLaMA and LlamaGen models with reported gains over LLM-Pruner, SliceGPT, and FLAP.
-
The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
Mamba and state-space models with constant depth and poly(n) precision are shown to lie in DLOGTIME-uniform TC0, the same circuit class as Transformers, so their expressiveness is bounded unless TC0=NC1.
-
Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
A residual self-attention network with all weight entries bounded by a small η can be approximated by one layer to error O(η)‖X‖∞, so skip connections do not prevent layer collapse.
-
Universal Approximation of Visual Autoregressive Transformers
The paper's headline claim that VAR transformers universally approximate all Lipschitz image maps is not supported, because the theorem restricts the target class and its key lemma has an invalid linearity step.
-
High-Order Matching for One-Step Shortcut Diffusion Models
HOMO extends shortcut diffusion with acceleration and jerk supervision, but the proof of superior approximation is not supported and experiments lack error bars.
-
Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation
VLFM models video latent patches as a HiPPO-LegS polynomial flow and trains a flow matching model to generate frames, claiming bounded interpolation and extrapolation error.
-
Circuit Complexity Bounds for Visual Autoregressive Model
The authors show that a simplified formalization of the VAR image generation model lies in DLOGTIME-uniform TC0, meaning it can be simulated by constant-depth threshold circuits with polynomial size and precision.
Discussion (0). Continue with ORCID to comment.