按年被提到
20232024 · 2 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2310.01655 · cs.LG

PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels

Praneeth Kacham, Vahab Mirrokni, Peilin Zhong · 2023
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2023-10-04 · 最近 2024-01-18
2不同的人
2活跃月份
3讨论串
10被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论SmartestUnknown · 2024-01

“This is not a new algorithm. The same algorithm is described in Figure 4 (Theorem 3.1) of https://arxiv.org/pdf/2310.01655.pdf (Disclaimer: I am an author on the linked paper)”

Linear transformers are faster after all原评论 ↗
被提交为 story · 2 次