REVIEW 5 cited by
How Sparse Attention Approximates Exact Attention? Your Attention is Naturally $n^C$-Sparse
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
abstract
Sparse Attention is a technique that approximates standard attention computation with sub-quadratic complexity. This is achieved by selectively ignoring smaller entries in the attention matrix during the softmax function computation. Variations of this technique, such as pruning KV cache, sparsity-based fast attention, and Sparse Transformer, have been extensively utilized for efficient Large Language Models (LLMs) deployment. Despite its widespread use, a theoretical understanding of the conditions under which sparse attention performs on par with traditional attention remains elusive. This work aims to $\textbf{bridge this gap by examining the inherent sparsity of standard attention processes}$. Our theoretical framework reveals several brand-new key insights: $\bullet$ Attention is $n^{C}$-sparse, implying that considering only the largest $\Omega(n^{C})$ entries out of all $n$ entries is sufficient for sparse attention to approximate the exact attention matrix with decreasing loss. Here, $n$ represents the input length and $C \in (0, 1)$ is a constant. $\bullet$ Stable $o(\log(n))$-sparse attention, which approximates attention computation with $\log(n)$ or fewer entries, may not be feasible since the error will persist at a minimum of $O(1)$. $\bullet$ An adaptive strategy ($\alpha \cdot n^C, \alpha \in \mathbb{R}$) for the window size of efficient attention methods rather than a fixed one is guaranteed to perform more accurately and efficiently in a task for inference on flexible context lengths.
Forward citations
Cited by 5 Pith papers
-
EARN: Efficient Inference Acceleration for LLM-based Generative Recommendation by Register Tokens
EARN inserts learnable register tokens at both ends of a user prompt, prunes prompt tokens after early layers, and achieves up to 3.79x faster LLM-based recommendation inference with comparable or better accuracy.
-
SALE : Low-bit Estimation for Efficient Sparse Attention in Long-context LLM Prefilling
SALE is a training-free sparse attention method that uses 4-bit quantized query-key estimates and a relative attention score to skip unimportant blocks, achieving over 3.36x prefill speedup on 64K+ token contexts with...
-
SPADE: An Input-Adaptive Sparse Attention Engine for Fast Video Diffusion Models Inference
SPADE combines static, semi-static, and dynamic block-sparse attention with a cheap SICS-based blocking heuristic to speed up video diffusion inference by up to 1.80x end-to-end.
-
DeltaLLM: A Training-Free Framework Exploiting Temporal Sparsity for Efficient Edge LLM Inference
DeltaLLM exploits temporal sparsity in key vectors (delta encoding) with a hybrid local-window attention to cut attention computation by up to 60% on 1-2B parameter LLMs with minimal accuracy loss.
-
Unifying Learning Dynamics and Generalization in Transformers Scaling Law
Claims a two-stage transformer scaling law (exponential then C^{-1/6}) with matching bounds, but the lower bounds are missing, the exponent is inconsistent (-1/7 vs -1/6), and the law is an artifact of hand-set M = Θ(...
Discussion (0). Continue with ORCID to comment.