Yingyu Liang

On Fine-Grained I/O Complexity of Attention Backward Passes

Retrieval-Augmented Generation as Noisy In-Context Learning: A Unified Theory and Risk Bounds

Text-to-Image Diffusion Models Cannot Count, and Prompt Refinement Cannot Help

Can Language Models Compose Skills In-Context?

RoPE Attention Can Be Trained in Almost Linear Time

Theoretical Constraints on the Expressive Power of RoPE-based Tensor Attention Transformers

Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond

Training Tensor Attention Efficiently: From Cubic to Almost Linear Time

Advancing the understanding of fixed point iterations in deep neural networks: a detailed analytical study

Circuit Complexity Bounds for Visual Autoregressive Model

Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers

HOFAR: High-Order Augmentation of Flow Autoregressive Transformers

RichSpace: Enriching Text-to-Video Prompt Space via Text Embedding Interpolation

Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows

DPBloomfilter: Securing Bloom Filters with Differential Privacy

Training Multi-Layer Transformers in Almost Linear Time

On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis

Visual Autoregressive Transformers Must Use $\Omega(n^2 d)$ Memory

Modern Hopfield Networks Cannot Solve $\mathsf{NC}^1$-Hard Problems

High-Order Matching for One-Step Shortcut Diffusion Models

Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning

Fine-grained Attention I/O Complexity: Comprehensive Analysis for Backward Passes

Dissecting Submission Limit in Desk-Rejections: A Mathematical Analysis of Fairness in AI Conference Policies

Differential Privacy of Cross-Attention with Provable Guarantee

Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix

Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time

Tensor Attention Training: Provably Efficient Learning of Higher-order Transformers

Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reduction

Towards Infinite-Long Prefix in Transformer

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities

Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers

HSR-Enhanced Sparse Attention Acceleration