Image de couverture de livre

Circuit Complexity Bounds for RoPE-based Transformer Architecture

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chen, Bo, Li, Xiaoyu, Liang, Yingyu, Long, Jiangxuan, Shi, Zhenmei, Song, Zhao
Format:	Preprint
Publié:	2024
Sujets:	Machine Learning Artificial Intelligence Computational Complexity Computation and Language
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers
par: Li, Xiaoyu, et autres
Publié: (2024)

RoPE Attention Can Be Trained in Almost Linear Time
par: Cao, Yang, et autres
Publié: (2024)

Circuit Complexity Bounds for Visual Autoregressive Model
par: Ke, Yekun, et autres
Publié: (2025)

The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
par: Chen, Yifang, et autres
Publié: (2024)

On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective
par: Li, Xiaoyu, et autres
Publié: (2025)

On Fine-Grained I/O Complexity of Attention Backward Passes
par: Li, Xiaoyu, et autres
Publié: (2024)

Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding
par: Chen, Yifang, et autres
Publié: (2025)

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers
par: Huang, Zekai, et autres
Publié: (2025)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
par: Cao, Yang, et autres
Publié: (2024)

Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix
par: Liang, Yingyu, et autres
Publié: (2024)

When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?
par: Li, Chenyang, et autres
Publié: (2025)

On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
par: Ke, Yekun, et autres
Publié: (2025)

Scaling Laws of RoPE-based Extrapolation
par: Liu, Xiaoran, et autres
Publié: (2023)

Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
par: Liang, Yingyu, et autres
Publié: (2024)

A Tighter Complexity Analysis of SparseGPT
par: Li, Xiaoyu, et autres
Publié: (2024)

Periodic RoPE for Infinite Context LLMs
par: Huo, Simin
Publié: (2026)

Universal Approximation of Visual Autoregressive Transformers
par: Chen, Yifang, et autres
Publié: (2025)

Towards Infinite-Long Prefix in Transformer
par: Liang, Yingyu, et autres
Publié: (2024)

Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
par: Chen, Bo, et autres
Publié: (2025)

On Computational Limits of FlowAR Models: Expressivity and Efficiency
par: Cao, Yang, et autres
Publié: (2025)

Rotary Positional Embeddings as Phase Modulation: Theoretical Bounds on the RoPE Base for Long-Context Transformers
par: Liu, Feilong
Publié: (2026)

Demystifying the Slash Pattern in Attention: The Role of RoPE
par: Cheng, Yuan, et autres
Publié: (2026)

On the token distance modeling ability of higher RoPE attention dimension
par: Hong, Xiangyu, et autres
Publié: (2024)

LinearARD: Linear-Memory Attention Distillation for RoPE Restoration
par: Yang, Ning, et autres
Publié: (2026)

HSR-Enhanced Sparse Attention Acceleration
par: Chen, Bo, et autres
Publié: (2024)

Resonance RoPE: Improving Context Length Generalization of Large Language Models
par: Wang, Suyuchen, et autres
Publié: (2024)

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time
par: Liang, Yingyu, et autres
Publié: (2024)

RoSA: Enhancing Parameter-Efficient Fine-Tuning via RoPE-aware Selective Adaptation in Large Language Models
par: Pan, Dayan, et autres
Publié: (2025)

Training Tensor Attention Efficiently: From Cubic to Almost Linear Time
par: Cao, Yang, et autres
Publié: (2024)

CoPE: Clipped RoPE as A Scalable Free Lunch for Long Context LLMs
par: Li, Haoran, et autres
Publié: (2026)

Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
par: Xu, Zhuoyan, et autres
Publié: (2024)

RoPE Distinguishes Neither Positions Nor Tokens in Long Contexts, Provably
par: Du, Yufeng, et autres
Publié: (2026)

Base of RoPE Bounds Context Length
par: Men, Xin, et autres
Publié: (2024)

CMAT: A Multi-Agent Collaboration Tuning Framework for Enhancing Small Language Models
par: Liang, Xuechen, et autres
Publié: (2024)

Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows
par: Gong, Chengyue, et autres
Publié: (2025)

Simulating Weighted Automata over Sequences and Trees with Transformers
par: Rizvi, Michael, et autres
Publié: (2024)

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
par: Chambon, Pierre, et autres
Publié: (2025)

EliteKV: Scalable KV Cache Compression via RoPE Frequency Selection and Joint Low-Rank Projection
par: Zhou, Yuhao, et autres
Publié: (2025)

Why Larger Language Models Do In-context Learning Differently?
par: Shi, Zhenmei, et autres
Publié: (2024)

RichSpace: Enriching Text-to-Video Prompt Space via Text Embedding Interpolation
par: Cao, Yuefan, et autres
Publié: (2025)