REVIEW 7 cited by
PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
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
read the original abstract
The quadratic time and memory complexity inherent to self-attention mechanisms, with respect to sequence length, presents a critical computational bottleneck in the training and deployment of large-scale Transformer-based language models. Recent theoretical results indicate the intractability of sub-quadratic softmax attention approximation under reasonable complexity assumptions. This paper addresses this challenge by first demonstrating that polynomial attention with high degree can effectively replace softmax without sacrificing model quality. Next, we develop polynomial sketching techniques from numerical linear algebra to achieve linear-time polynomial attention with approximation guarantees. Crucially, our approach achieves this speedup without requiring the sparsification of attention matrices. We also present a block-based algorithm to apply causal masking efficiently. Combining these techniques, we provide \emph{PolySketchFormer}, a practical linear-time Transformer architecture for language modeling that offers provable guarantees. We validate PolySketchFormer empirically by training language models capable of handling long contexts. These experiments utilize both synthetic and real-world datasets (PG19, Wikipedia and C4) on Google Cloud TPUs. For context lengths of 32k and GPT-2 style models, our model achieves a 2.5-4x speedup in training compared to FlashAttention, with no observed degradation in quality across our experiments.
Forward citations
Cited by 7 Pith papers
-
Selective Rotary Position Embedding
Selective RoPE replaces RoPE's fixed rotation angles with input-dependent, learnable angles and improves recall-focused tasks in gated linear and softmax transformers.
-
Norming Sets for Tensor and Polynomial Sketching
Norming sets are used to bound sketching dimensions for algebraic varieties and polynomial images under arbitrary sketch operators, including a new median sketch that needs only about dim(V) structured measurements.
-
ELiTeFormer: An Efficient Transformer for FPGAs
Hybrid linear attention plus ternary projections, co-designed with a multiplier-free PE, deliver 10× weight and 12.8× KV-cache compression with competitive MMLU and FPGA speedups over LLaMA 3 on A100.
-
A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization
Single-layer linear self-attention can represent, train on, and length-generalize pairwise interaction functions under data-versatility and exact-realizability assumptions, and the paper introduces higher-order HyperA...
-
Neural Interpretable PDEs: Harmonizing Fourier Insights with Attention for Scalable and Interpretable Physics Discovery
NIPS is a neural operator that uses linear attention and Fourier kernels to simultaneously predict PDE solutions and recover hidden material properties from limited data.
-
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 = Θ(...
-
Scaling Context Requires Rethinking Attention
On 64k-token natural language training, power attention with degree 2 achieves lower loss per FLOP than both softmax attention and existing linear attention, and its GPU kernels run faster than Flash Attention at long...
Discussion (0). Sign in to comment.