Towards Sampling Data Structures for Tensor Products in Turnstile Streams

2025/10/04 by Zhao Song, Song, Zhao, Shenghao Xie +3
Computer Science · #FOS: Computer and information sciences #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Multimodal Machine Learning Applications #Topic Modeling

paper · pdf · doi:10.48550/arxiv.2510.03678

openalex publication_date 2025/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper studies the computational challenges of large-scale attention-based models in artificial intelligence by utilizing importance sampling methods in the streaming setting. Inspired by the classical definition of the ℓ₂ sampler and the recent progress of the attention scheme in Large Language Models (LLMs), we propose the definition of the attention sampler. Our approach significantly reduces the computational burden of traditional attention mechanisms. We analyze the effectiveness of the attention sampler from a theoretical perspective, including space and update time. Additionally, our framework exhibits scalability and broad applicability across various model architectures and domains.

Citations

• Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
• Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
• Perfect Sampling in Turnstile Streams Beyond Small Moments
• LLMVoX: Autoregressive Streaming Text-to-Speech Model for Any LLM
• FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference
• DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads
• Universal Perfect Samplers for Incremental Streams
• ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Tools
• SirLLM: Streaming Infinite Retentive LLM
• Challenges in Deploying Long-Context Transformers: A Theoretical Peak Performance Analysis
• Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone
• Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context
• DéjàVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Serving
• The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
• HyperAttention: Long-context Attention in Near-Linear Time
• How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
• Improving Length-Generalization in Transformers via Task Hinting
• Efficient Streaming Language Models with Attention Sinks
• Streaming Semidefinite Programs: O(√(n)) Passes, Small Space and Fast Runtime
• Convergence of Two-Layer Regression with Nonlinear Units
• Llama 2: Open Foundation and Fine-Tuned Chat Models
• Zero-th Order Algorithm for Softmax Attention Optimization
• Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration
• An Iterative Algorithm for Rescaled Hyperbolic Functions Regression
• Attention Scheme Inspired Softmax Regression
• Solving Tensor Low Cycle Rank Approximation
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension
• Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
• An Over-parameterized Exponential Regression
• Solving Regularized Exp, Cosh and Sinh Regression Problems
• A General Algorithm for Solving Rank-one Matrix Sensing
• Do Transformers Parse while Predicting the Masked Word?
• LLaMA: Open and Efficient Foundation Language Models
• Fast Attention Requires Bounded Entries
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
• KDEformer: Accelerating Transformers via Kernel Density Estimation
• Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations
• Dynamic Kernel Graph Sparsifiers
• A Faster Small Treewidth SDP Solver
• Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
• Dynamic Tensor Product Regression
• A Sublinear Adversarial Training Algorithm
• Adaptive Sketches for Robust Regression with Importance Sampling
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
• SimA: Simple Softmax-free Attention for Vision Transformers
• Fast Distance Oracles for Any Symmetric Norm
• OPT: Open Pre-trained Transformer Language Models
• A very preliminary analysis of DALL-E 2
• Speeding Up Sparsification using Inner Product Search Data Structures
• PaLM: Scaling Language Modeling with Pathways
• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• Inductive Biases and Variable Creation in Self-Attention Mechanisms
• Truly Perfect Samplers for Data Streams and Sliding Windows
• Fast Sketching of Polynomial Kernels of Polynomial Degree
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Approximating How Single Head Attention Learns
• Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
• SMYRF: Efficient Attention using Asymmetric Clustering
• A Mathematical Theory of Attention
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
• Linformer: Self-Attention with Linear Complexity
• Language Models are Few-Shot Learners
• Non-Adaptive Adaptive Sampling on Turnstile Streams
• Faster Dynamic Matrix Inverse for Faster LPs
• Reformer: The Efficient Transformer
• Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
• RoBERTa: A Robustly Optimized BERT Pretraining Approach
• Sampling Sketches for Concave Sublinear Functions of Frequencies
• XLNet: Generalized Autoregressive Pretraining for Language Understanding
• Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm
• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• Generating Long Sequences with Sparse Transformers
• Solving Linear Programs in the Current Matrix Multiplication Time
• Perfect L_p Sampling in a Data Stream
• Composable Core-sets for Determinant Maximization Problems via Spectral Spanners
• Sketching for Kronecker Product Regression and P-splines
• Attention Is All You Need
• Relative Error Tensor Low Rank Approximation
• Singular Vectors of Orthogonally Decomposable Tensors
• Fast and Guaranteed Tensor Decomposition via Sketching
• A New Sampling Technique for Tensors
• Orthogonal Decomposition of Symmetric Tensors
• DFacTo: Distributed Factorization of Tensors
• Online Tensor Methods for Learning Latent Variable Models
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC
• Compressed Matrix Multiplication
• Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems
• Identifiability of Large Phylogenetic Mixture Models
• Streaming Algorithms from Precision Sampling
• MACH: Fast Randomized Tensor Decompositions
• Identifiability of 2-tree mixtures for group-based models
• Random sampling with a reservoir
• SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
• PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

Related

• Efficient Attention Mechanisms for Large Language Models: A Survey
• Streaming Attention Approximation via Discrepancy Theory
• Attention Needs to Focus: A Unified Perspective on Attention Allocation
• Tensor Product Attention Is All You Need
• Unveiling and Harnessing Hidden Attention Sinks: Enhancing Large Language Models without Training through Attention Calibration