49 citations · 102 across the 60 of their papers we have counts for
28 papers · 1 filter
Theoretical Constraints on the Expressive Power of -based Tensor Attention Transformers
Xiaoyu Li, Yingyu Liang, Zhenmei Shi +2
Tensor Attention extends traditional attention mechanisms by capturing high-order correlations across multiple modalities, addressing the limitations of classical matrix-based atte…
RoPE Attention Can Be Trained in Almost Linear Time
Yang Cao, Jiayan Huo, Yingyu Liang +2
The Rotary Position Embedding (RoPE) mechanism has become a powerful enhancement to the Transformer architecture, which enables models to capture token relationships when encoding…
The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
Yifang Chen, Xiaoyu Li, Yingyu Liang +2
In this paper, we analyze the computational limitations of Mamba and State-space Models (SSMs) by using the circuit complexity framework. Despite Mamba's stateful design and recent…
Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond
Yekun Ke, Yingyu Liang, Zhenmei Shi +2
The application of transformer-based models on time series forecasting (TSF) tasks has long been popular to study. However, many of these works fail to beat the simple linear resid…
Modern Hopfield Networks Require Chain-of-Thought to Solve -Hard Problems
Yang Cao, Xiaoyu Li, Yuanpeng Li +3
Modern Hopfield Networks (MHNs) have emerged as powerful components in deep learning, serving as effective replacements for pooling layers, LSTMs, and attention mechanisms. While r…
Circuit Complexity Bounds for RoPE-based Transformer Architecture
Bo Chen, Xiaoyu Li, Yingyu Liang +3
Characterizing the express power of the Transformer architecture is critical to understanding its capacity limits and scaling law. Recent works provide the circuit complexity bound…
Advancing the Understanding of Fixed Point Iterations in Deep Neural Networks: A Detailed Analytical Study
Yekun Ke, Xiaoyu Li, Yingyu Liang +2
Recent empirical studies have identified fixed point iteration phenomena in deep neural networks, where the hidden state tends to stabilize after several layers, showing minimal ch…
Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descent
Bo Chen, Xiaoyu Li, Yingyu Liang +2
In-context learning has been recognized as a key factor in the success of Large Language Models (LLMs). It refers to the model's ability to learn patterns on the fly from provided…
Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix
Yingyu Liang, Jiangxuan Long, Zhenmei Shi +2
Large Language Models (LLMs) have shown immense potential in enhancing various aspects of our daily lives, from conversational AI to search and AI assistants. However, their growin…
HSR-Enhanced Sparse Attention Acceleration
Bo Chen, Yingyu Liang, Zhizhou Sha +2
Large Language Models (LLMs) have demonstrated remarkable capabilities across various applications, but their performance on long-context tasks is often limited by the computationa…
On Fine-Grained I/O Complexity of Attention Backward Passes
Xiaoyu Li, Yingyu Liang, Zhenmei Shi +3
Large Language Models (LLMs) exhibit exceptional proficiency in handling extensive context windows in natural language. Nevertheless, the quadratic scaling of attention computation…
Looped ReLU MLPs May Be All You Need as Practical Programmable Computers
Yingyu Liang, Zhizhou Sha, Zhenmei Shi +2
Previous work has demonstrated that attention mechanisms are Turing complete. More recently, it has been shown that a looped 9-layer Transformer can function as a universal program…
Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reduction
Zhenmei Shi, Yifei Ming, Xuan-Phi Nguyen +2
Large Language Models (LLMs) have demonstrated remarkable capabilities in handling long context inputs, but this comes at the cost of increased computational resources and latency.…
Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability
Zhuoyan Xu, Zhenmei Shi, Yingyu Liang
Large language models (LLMs) have emerged as powerful tools for many AI problems and exhibit remarkable in-context learning (ICL) capabilities. Compositional ability, solving unsee…
Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time
Yingyu Liang, Zhizhou Sha, Zhenmei Shi +2
The computational complexity of the self-attention mechanism in popular transformer architectures poses significant challenges for training and inference, and becomes the bottlenec…
A Tighter Complexity Analysis of SparseGPT
Xiaoyu Li, Yingyu Liang, Zhenmei Shi +1
In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from to for any $a \in […
Fast John Ellipsoid Computation with Differential Privacy Optimization
Xiaoyu Li, Yingyu Liang, Zhenmei Shi +2
Determining the John ellipsoid - the largest volume ellipsoid contained within a convex polytope - is a fundamental problem with applications in machine learning, optimization, and…
Provable Differentially Private Computation of the Cross-Attention Mechanism
Yekun Ke, Yingyu Liang, Zhenmei Shi +2
Cross-attention has emerged as a cornerstone module in modern artificial intelligence, underpinning critical applications such as retrieval-augmented generation (RAG), system promp…
Differential Privacy Mechanisms in Neural Tangent Kernel Regression
Jiuxiang Gu, Yingyu Liang, Zhizhou Sha +2
Training data privacy is a fundamental problem in modern Artificial Intelligence (AI) applications, such as face recognition, recommendation systems, language generation, and many…
Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Models
Jiayu Wang, Yifei Ming, Zhenmei Shi +4
Large language models (LLMs) and vision-language models (VLMs) have demonstrated remarkable performance across a wide range of tasks and domains. Despite this promise, spatial unde…
Towards Infinite-Long Prefix in Transformer
Yingyu Liang, Zhenmei Shi, Zhao Song +1
Prompting and context-based fine-tuning methods, which we call Prefix Learning, have been proposed to enhance the performance of language models on various downstream tasks. They a…
Why Larger Language Models Do In-context Learning Differently?
Zhenmei Shi, Junyi Wei, Zhuoyan Xu +1
Large language models (LLM) have emerged as a powerful tool for AI, with the key ability of in-context learning (ICL), where they can perform well on unseen tasks based on a brief…
Unraveling the Smoothness Properties of Diffusion Models: A Gaussian Mixture Perspective
Yingyu Liang, Zhenmei Shi, Zhao Song +1
Diffusion models have made rapid progress in generating high-quality samples across various domains. However, a theoretical understanding of the Lipschitz continuity and second mom…
Training Tensor Attention Efficiently: From Cubic to Almost Linear Time
Yang Cao, Yingyu Liang, Zhenmei Shi +1
Tensor Attention, a multi-view attention that is able to capture high-order correlations among multiple modalities, can overcome the representational limitations of classical matri…