https://arxiv.org/abs/2310.05869

Skip to main content
Cornell University
We gratefully acknowledge support from the Simons Foundation, member
institutions, and all contributors. Donate
 
arxiv logo > cs > arXiv:2310.05869
[                    ]

Help | Advanced Search

[All fields        ]
Search
arXiv logo
Cornell University Logo
[                    ] GO
quick links

  * Login
  * Help Pages
  * About

Computer Science > Machine Learning

arXiv:2310.05869 (cs)
[Submitted on 9 Oct 2023]

Title:HyperAttention: Long-context Attention in Near-Linear Time

Authors:Insu Han, Rajesh Jarayam, Amin Karbasi, Vahab Mirrokni, David
P. Woodruff, Amir Zandieh
Download a PDF of the paper titled HyperAttention: Long-context
Attention in Near-Linear Time, by Insu Han and 5 other authors
Download PDF

    Abstract:We present an approximate attention mechanism named
    HyperAttention to address the computational challenges posed by
    the growing complexity of long contexts used in Large Language
    Models (LLMs). Recent work suggests that in the worst-case
    scenario, quadratic time is necessary unless the entries of the
    attention matrix are bounded or the matrix has low stable rank.
    We introduce two parameters which measure: (1) the max column
    norm in the normalized attention matrix, and (2) the ratio of row
    norms in the unnormalized attention matrix after detecting and
    removing large entries. We use these fine-grained parameters to
    capture the hardness of the problem. Despite previous lower
    bounds, we are able to achieve a linear time sampling algorithm
    even when the matrix has unbounded entries or a large stable
    rank, provided the above parameters are small. HyperAttention
    features a modular design that easily accommodates integration of
    other fast low-level implementations, particularly
    FlashAttention. Empirically, employing Locality Sensitive Hashing
    (LSH) to identify large entries, HyperAttention outperforms
    existing methods, giving significant speed improvements compared
    to state-of-the-art solutions like FlashAttention. We validate
    the empirical performance of HyperAttention on a variety of
    different long-context length datasets. For example,
    HyperAttention makes the inference time of ChatGLM2 50\% faster
    on 32k context length while perplexity increases from 5.6 to 6.3.
    On larger context length, e.g., 131k, with causal masking,
    HyperAttention offers 5-fold speedup on a single attention layer.

Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
Cite as:  arXiv:2310.05869 [cs.LG]
          (or arXiv:2310.05869v1 [cs.LG] for this version)
          https://doi.org/10.48550/arXiv.2310.05869
          Focus to learn more
          arXiv-issued DOI via DataCite

Submission history

From: Insu Han [view email]
[v1] Mon, 9 Oct 2023 17:05:25 UTC (552 KB)
Full-text links:

Access Paper:

    Download a PDF of the paper titled HyperAttention: Long-context
    Attention in Near-Linear Time, by Insu Han and 5 other authors
  * Download PDF
  * PostScript
  * Other Formats

[zero-1]
Current browse context:
cs.LG
< prev   |   next >
new | recent | 2310
Change to browse by:
cs
cs.AI

References & Citations

  * NASA ADS
  * Google Scholar
  * Semantic Scholar

a export BibTeX citation Loading...

BibTeX formatted citation

x
[loading...          ]
Data provided by:

Bookmark

BibSonomy logo Reddit logo
(*) Bibliographic Tools

Bibliographic and Citation Tools

[ ] Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
[ ] Litmaps Toggle
Litmaps (What is Litmaps?)
[ ] scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
( ) Code, Data, Media

Code, Data and Media Associated with this Article

[ ] Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
[ ] DagsHub Toggle
DagsHub (What is DagsHub?)
[ ] Links to Code Toggle
Papers with Code (What is Papers with Code?)
[ ] ScienceCast Toggle
ScienceCast (What is ScienceCast?)
( ) Demos

Demos

[ ] Replicate Toggle
Replicate (What is Replicate?)
[ ] Spaces Toggle
Hugging Face Spaces (What is Spaces?)
( ) Related Papers

Recommenders and Search Tools

[ ] Link to Influence Flower
Influence Flower (What are Influence Flowers?)
[ ] Connected Papers Toggle
Connected Papers (What is Connected Papers?)
[ ] Core recommender toggle
CORE Recommender (What is CORE?)
[ ] IArxiv recommender toggle
IArxiv Recommender (What is IArxiv?)

  * Author
  * Venue
  * Institution
  * Topic

( ) About arXivLabs

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and
share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have
embraced and accepted our values of openness, community, excellence,
and user data privacy. arXiv is committed to these values and only
works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community?
Learn more about arXivLabs.

Which authors of this paper are endorsers? | Disable MathJax (What is
MathJax?)

  * About
  * Help

  * Click here to contact arXiv Contact
  * Click here to subscribe Subscribe

  * Copyright
  * Privacy Policy

  * Web Accessibility Assistance
  * arXiv Operational Status
    Get status notifications via email or slack