Subquadratic Algorithms and Hardness for Attention with Any Temperature

Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye · 2025

Read Subquadratic Algorithms and Hardness for Attention with Any Temperature by Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-14840.txt.

Description

Gupta, Huang, Saha, Xu, and Ye present a paper from twenty twenty-five on faster attention sums in language models. Attention, the core step in transformer models, takes time that grows with the square of text length. Past work ties fast attention to tight limits on input size or heat settings. The team ask when fast attention works at any heat setting. They give the first sub-quadratic method for fixed small head size. Its run time grows only mildly with input size.

The method also covers the training gradient step at like speed. That extends the gain to full model training. Hardness results show big further gains are unlikely under standard guesses. For very large head sizes, the standard method is already optimal, they prove.

Catalog record

CREATORShreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, Christopher Ye
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14840

Browse the full library · About the Tower of Babel