<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">

<head>  <title>[2408.04093] Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters</title>
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <link rel="apple-touch-icon" sizes="180x180" href="/static/browse/0.3.4/images/icons/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/static/browse/0.3.4/images/icons/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/static/browse/0.3.4/images/icons/favicon-16x16.png">
  <link rel="manifest" href="/static/browse/0.3.4/images/icons/site.webmanifest">
  <link rel="mask-icon" href="/static/browse/0.3.4/images/icons/safari-pinned-tab.svg" color="#5bbad5">
  <meta name="msapplication-TileColor" content="#da532c">
  <meta name="theme-color" content="#ffffff">
  <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/arXiv.css?v=20240822" />
  <link rel="stylesheet" type="text/css" media="print" href="/static/browse/0.3.4/css/arXiv-print.css?v=20200611" />
  <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/browse_search.css" />
  <script language="javascript" src="/static/browse/0.3.4/js/accordion.js" /></script>
  
    <link rel="stylesheet" type="text/css" media="screen" href="/static/browse/0.3.4/css/slider.css?v=1.14" />
    <script src="//code.jquery.com/jquery-latest.min.js" type="text/javascript"></script>
    <script type="text/javascript" src="/static/browse/0.3.4/js/donate.js?v=1.11"></script><link rel="canonical" href="/abs/2408.04093"/><meta property="og:type" content="website" />
<meta property="og:site_name" content="arXiv.org" />
<meta property="og:title" content="Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters" />
<meta property="og:url" content="https://arxiv.org/abs/2408.04093v3" />
<meta property="og:image" content="/static/browse/0.3.4/images/arxiv-logo-fb.png" />
<meta property="og:image:secure_url" content="/static/browse/0.3.4/images/arxiv-logo-fb.png" />
<meta property="og:image:width" content="1200" />
<meta property="og:image:height" content="700" />
<meta property="og:image:alt" content="arXiv logo"/>
<meta property="og:description" content="Self-attention is the core mathematical operation of modern transformer architectures and is also a significant computational bottleneck due to its quadratic complexity in the sequence length. In this work, we derive the scalar energy function whose gradient computes the self-attention block, thus elucidating the theoretical underpinnings of self-attention, providing a Bayesian interpretation of the operation and linking it closely with energy-based models such as Hopfield Networks. Our formulation reveals that the reduction across the sequence axis can be efficiently computed in parallel through a tree reduction. Our algorithm, for parallelizing attention computation across multiple GPUs enables cross-device decoding to be performed asymptotically faster (up to 8x faster in our experiments) than alternative approaches such as Ring Attention, while also requiring significantly less communication volume and incurring 2x less peak memory. Our code is publicly available here: \url{https://github.com/Zyphra/tree_attention}."/>
<meta name="twitter:site" content="@arxiv"/>
<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="Tree Attention: Topology-aware Decoding for Long-Context Attention..."/>
<meta name="twitter:description" content="Self-attention is the core mathematical operation of modern transformer architectures and is also a significant computational bottleneck due to its quadratic complexity in the sequence length. In..."/>
<meta name="twitter:image" content="https://static.arxiv.org/icons/twitter/arxiv-logo-twitter-square.png"/>
<meta name="twitter:image:alt" content="arXiv logo"/>
  <link rel="stylesheet" media="screen" type="text/css" href="/static/browse/0.3.4/css/tooltip.css"/><link rel="stylesheet" media="screen" type="text/css" href="https://static.arxiv.org/js/bibex-dev/bibex.css?20200709"/>  <script src="/static/browse/0.3.4/js/mathjaxToggle.min.js" type="text/javascript"></script>  <script src="//code.jquery.com/jquery-latest.min.js" type="text/javascript"></script>
  <script src="//cdn.jsdelivr.net/npm/js-cookie@2/src/js.cookie.min.js" type="text/javascript"></script>
  <script src="//cdn.jsdelivr.net/npm/dompurify@2.3.5/dist/purify.min.js"></script>
  <script src="/static/browse/0.3.4/js/toggle-labs.js?20230622" type="text/javascript"></script>
  <script src="/static/browse/0.3.4/js/cite.js" type="text/javascript"></script><meta name="citation_title" content="Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters" /><meta name="citation_author" content="Shyam, Vasudev" /><meta name="citation_author" content="Pilault, Jonathan" /><meta name="citation_author" content="Shepperd, Emily" /><meta name="citation_author" content="Anthony, Quentin" /><meta name="citation_author" content="Millidge, Beren" /><meta name="citation_date" content="2024/08/07" /><meta name="citation_online_date" content="2024/08/14" /><meta name="citation_pdf_url" content="http://arxiv.org/pdf/2408.04093" /><meta name="citation_arxiv_id" content="2408.04093" /><meta name="citation_abstract" content="Self-attention is the core mathematical operation of modern transformer architectures and is also a significant computational bottleneck due to its quadratic complexity in the sequence length. In this work, we derive the scalar energy function whose gradient computes the self-attention block, thus elucidating the theoretical underpinnings of self-attention, providing a Bayesian interpretation of the operation and linking it closely with energy-based models such as Hopfield Networks. Our formulation reveals that the reduction across the sequence axis can be efficiently computed in parallel through a tree reduction. Our algorithm, for parallelizing attention computation across multiple GPUs enables cross-device decoding to be performed asymptotically faster (up to 8x faster in our experiments) than alternative approaches such as Ring Attention, while also requiring significantly less communication volume and incurring 2x less peak memory. Our code is publicly available here: \url{https://github.com/Zyphra/tree_attention}." />
</head>

<body  class="with-cu-identity">
  
  <aside class="slider-wrapper bps-banner forum grey">
    <a class="close-slider bps-banner" href="#"><img src="/static/browse/0.3.4/images/icons/close-slider.png" alt="close this message"></a>
  	<div class="columns">
      <img role="presentation" class="bps-banner-image" src="/static/browse/0.3.4/images/events/arxiv-forum-logotype-title.png" alt="arXiv Accessibility Forum 2024">
      <div class="copy-donation bps-banner">
        <h2 id="forum-session-title"></h2>
        <p id="forum-session-link-small"></p>
      </div>
      <div class="amount-donation bps-banner">
          <div id="forum-session-link-box" class="donate-cta"></div>
      </div>
    </div>
  </aside>
  <script src="/static/browse/0.3.4/js/rotate_forum_info.js" type="text/javascript"></script>
  <div class="flex-wrap-footer">
    <header>
      <a href="#content" class="is-sr-only">Skip to main content</a>
      <!-- start desktop header -->
      <div class="columns is-vcentered is-hidden-mobile" id="cu-identity">
        <div class="column" id="cu-logo">
          <a href="https://www.cornell.edu/"><img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University" /></a>
        </div><div class="column banner-minimal forum">
            <!-- /from July 7 at 1:00 AM to Sept 2 at 1:00 AM --><p>This week: the arXiv Accessibility Forum</p>
            <a href="https://accessibility2024.arxiv.org/schedule" target="_blank">Forum Schedule</a></div><div class="column" id="support-ack">
          <span id="support-ack-url">We gratefully acknowledge support from the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors.</span>
          <a href="https://info.arxiv.org/about/donate.html" class="btn-header-donate">Donate</a>
        </div>
      </div>

      <div id="header" class="is-hidden-mobile">
<a aria-hidden="true" href="{url_path('ignore_me')}"></a>
  <div class="header-breadcrumbs is-hidden-mobile">
    <a href="/"><img src="/static/browse/0.3.4/images/arxiv-logo-one-color-white.svg" alt="arxiv logo" style="height:40px;"/></a> <span>&gt;</span> <a href="/list/cs/recent">cs</a> <span>&gt;</span> arXiv:2408.04093
  </div>
          <div class="search-block level-right">
    <form class="level-item mini-search" method="GET" action="https://arxiv.org/search">
      <div class="field has-addons">
        <div class="control">
          <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" />
          <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p>
        </div>
        <div class="control">
          <div class="select is-small">
            <select name="searchtype" aria-label="Field to search">
              <option value="all" selected="selected">All fields</option>
              <option value="title">Title</option>
              <option value="author">Author</option>
              <option value="abstract">Abstract</option>
              <option value="comments">Comments</option>
              <option value="journal_ref">Journal reference</option>
              <option value="acm_class">ACM classification</option>
              <option value="msc_class">MSC classification</option>
              <option value="report_num">Report number</option>
              <option value="paper_id">arXiv identifier</option>
              <option value="doi">DOI</option>
              <option value="orcid">ORCID</option>
              <option value="author_id">arXiv author ID</option>
              <option value="help">Help pages</option>
              <option value="full_text">Full text</option>
            </select>
          </div>
        </div>
        <input type="hidden" name="source" value="header">
        <button class="button is-small is-cul-darker">Search</button>
      </div>
    </form>
  </div>
     </div><!-- /end desktop header -->

      <div class="mobile-header">
        <div class="columns is-mobile">
          <div class="column logo-arxiv"><a href="https://arxiv.org/"><img src="/static/browse/0.3.4/images/arxiv-logomark-small-white.svg" alt="arXiv logo" style="height:60px;" /></a></div>
          <div class="column logo-cornell"><a href="https://www.cornell.edu/">
            <picture>
              <source media="(min-width: 501px)"
                srcset="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg  400w"
                sizes="400w" />
              <source srcset="/static/browse/0.3.4/images/icons/cu/cornell_seal_simple_black.svg 2x" />
              <img src="/static/browse/0.3.4/images/icons/cu/cornell-reduced-white-SMALL.svg" alt="Cornell University Logo" />
            </picture>
          </a></div>
          <div class="column nav" id="toggle-container" role="menubar">
            <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-white"><title>open search</title><path d="M505 442.7L405.3 343c-4.5-4.5-10.6-7-17-7H372c27.6-35.3 44-79.7 44-128C416 93.1 322.9 0 208 0S0 93.1 0 208s93.1 208 208 208c48.3 0 92.7-16.4 128-44v16.3c0 6.4 2.5 12.5 7 17l99.7 99.7c9.4 9.4 24.6 9.4 33.9 0l28.3-28.3c9.4-9.4 9.4-24.6.1-34zM208 336c-70.7 0-128-57.2-128-128 0-70.7 57.2-128 128-128 70.7 0 128 57.2 128 128 0 70.7-57.2 128-128 128z"/></svg></button>
            <div class="mobile-toggle-block toggle-target">
              <form class="mobile-search-form" method="GET" action="https://arxiv.org/search">
                <div class="field has-addons">
                  <input class="input" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" />
                  <input type="hidden" name="source" value="header">
                  <input type="hidden" name="searchtype" value="all">
                  <button class="button">GO</button>
                </div>
              </form>
            </div>

            <button class="toggle-control"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-white" role="menu"><title>open navigation menu</title><path d="M16 132h416c8.837 0 16-7.163 16-16V76c0-8.837-7.163-16-16-16H16C7.163 60 0 67.163 0 76v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16zm0 160h416c8.837 0 16-7.163 16-16v-40c0-8.837-7.163-16-16-16H16c-8.837 0-16 7.163-16 16v40c0 8.837 7.163 16 16 16z"/ ></svg></button>
            <div class="mobile-toggle-block toggle-target">
              <nav class="mobile-menu" aria-labelledby="mobilemenulabel">
                <h2 id="mobilemenulabel">quick links</h2>
                <ul>
                    <li><a href="https://arxiv.org/login">Login</a></li>
                    <li><a href="https://info.arxiv.org/help">Help Pages</a></li>
                    <li><a href="https://info.arxiv.org/about">About</a></li>
                </ul>
              </nav>
            </div>
          </div>
        </div>
      </div><!-- /end mobile-header -->
    </header>

    <main>
      <div id="content">
<!--
rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
         xmlns:dc="http://purl.org/dc/elements/1.1/"
         xmlns:trackback="http://madskills.com/public/xml/rss/module/trackback/">
    <rdf:Description
        rdf:about="/abs/2408.04093"
        dc:identifier="/abs/2408.04093"
        dc:title="Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters"
        trackback:ping="/trackback/2408.04093" />
    </rdf:RDF>
--><div id="abs-outer">

  <div class="leftcolumn">
    <div class="subheader">
      <h1>Computer Science > Machine Learning</h1>
    </div>

    <div class="header-breadcrumbs-mobile">
      <strong>arXiv:2408.04093</strong> (cs)
    </div>
<link rel="stylesheet" type="text/css" href="/static/base/1.0.1/css/abs.css">
<div id="content-inner">
  <div id="abs">
    <div class="dateline">
  [Submitted on 7 Aug 2024 (<a href="https://arxiv.org/abs/2408.04093v1">v1</a>), last revised 14 Aug 2024 (this version, v3)]</div>
    <h1 class="title mathjax"><span class="descriptor">Title:</span>Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters</h1>
    <div class="authors"><span class="descriptor">Authors:</span><a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Shyam,+V">Vasudev Shyam</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Pilault,+J">Jonathan Pilault</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Shepperd,+E">Emily Shepperd</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Anthony,+Q">Quentin Anthony</a>, <a href="https://arxiv.org/search/cs?searchtype=author&amp;query=Millidge,+B">Beren Millidge</a></div>            <div id="download-button-info" hidden>View a PDF of the paper titled Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters, by Vasudev Shyam and 4 other authors</div>
    <a class="mobile-submission-download" href="/pdf/2408.04093">View PDF</a>
    <a class="mobile-submission-download" href="https://arxiv.org/html/2408.04093v3">HTML (experimental)</a>



    <blockquote class="abstract mathjax">
            <span class="descriptor">Abstract:</span>Self-attention is the core mathematical operation of modern transformer architectures and is also a significant computational bottleneck due to its quadratic complexity in the sequence length. In this work, we derive the scalar energy function whose gradient computes the self-attention block, thus elucidating the theoretical underpinnings of self-attention, providing a Bayesian interpretation of the operation and linking it closely with energy-based models such as Hopfield Networks. Our formulation reveals that the reduction across the sequence axis can be efficiently computed in parallel through a tree reduction. Our algorithm, for parallelizing attention computation across multiple GPUs enables cross-device decoding to be performed asymptotically faster (up to 8x faster in our experiments) than alternative approaches such as Ring Attention, while also requiring significantly less communication volume and incurring 2x less peak memory. Our code is publicly available here: \url{<a href="https://github.com/Zyphra/tree_attention" rel="external noopener nofollow" class="link-external link-https">this https URL</a>}.
    </blockquote>

    <!--CONTEXT-->
    <div class="metatable">
      <table summary="Additional metadata"><tr>
          <td class="tablecell label">Subjects:</td>
          <td class="tablecell subjects">
            <span class="primary-subject">Machine Learning (cs.LG)</span>; Computation and Language (cs.CL)</td>
        </tr><tr>
          <td class="tablecell label">Cite as:</td>
          <td class="tablecell arxivid"><span class="arxivid"><a href="https://arxiv.org/abs/2408.04093">arXiv:2408.04093</a> [cs.LG]</span></td>
        </tr>
        <tr>
          <td class="tablecell label">&nbsp;</td>
          <td class="tablecell arxividv">(or <span class="arxivid">
              <a href="https://arxiv.org/abs/2408.04093v3">arXiv:2408.04093v3</a> [cs.LG]</span> for this version)
          </td>
        </tr>
        <tr>
          <td class="tablecell label">&nbsp;</td>
          <td class="tablecell arxivdoi">              <a href="https://doi.org/10.48550/arXiv.2408.04093"  id="arxiv-doi-link">https://doi.org/10.48550/arXiv.2408.04093</a><div class="button-and-tooltip">
              <button class="more-info" aria-describedby="more-info-desc-1">
                <svg height="15" role="presentation" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path fill="currentColor" d="M256 8C119.043 8 8 119.083 8 256c0 136.997 111.043 248 248 248s248-111.003 248-248C504 119.083 392.957 8 256 8zm0 110c23.196 0 42 18.804 42 42s-18.804 42-42 42-42-18.804-42-42 18.804-42 42-42zm56 254c0 6.627-5.373 12-12 12h-88c-6.627 0-12-5.373-12-12v-24c0-6.627 5.373-12 12-12h12v-64h-12c-6.627 0-12-5.373-12-12v-24c0-6.627 5.373-12 12-12h64c6.627 0 12 5.373 12 12v100h12c6.627 0 12 5.373 12 12v24z" class=""></path></svg>
                <span class="visually-hidden">Focus to learn more</span>
              </button>
              <!-- tooltip description -->
              <div role="tooltip" id="more-info-desc-1">
                <span class="left-corner"></span>                  arXiv-issued DOI via DataCite</div>
            </div>
          </td>
        </tr></table>
    </div>
  </div>
</div>
    <div class="submission-history">
      <h2>Submission history</h2> From: Jonathan Pilault [<a href="/show-email/97f33bc9/2408.04093">view email</a>]      <br/>            <strong><a href="/abs/2408.04093v1">[v1]</a></strong>
        Wed, 7 Aug 2024 21:16:55 UTC (1,999 KB)<br/>
            <strong><a href="/abs/2408.04093v2">[v2]</a></strong>
        Fri, 9 Aug 2024 13:07:21 UTC (2,000 KB)<br/>
    <strong>[v3]</strong>
        Wed, 14 Aug 2024 12:47:31 UTC (2,000 KB)<br/>
</div>
  </div>
  <!--end leftcolumn-->
<div class="extra-services">    <div class="full-text">
      <a name="other"></a>
      <span class="descriptor">Full-text links:</span>
      <h2>Access Paper:</h2>
      <ul>
  <div id="download-button-info" hidden>
View a PDF of the paper titled Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters, by Vasudev Shyam and 4 other authors</div><li><a href="/pdf/2408.04093" aria-describedby="download-button-info" accesskey="f" class="abs-button download-pdf">View PDF</a></li><li><a href="https://arxiv.org/html/2408.04093v3" class="abs-button" id="latexml-download-link">HTML (experimental)</a></li><li><a href="/src/2408.04093" class="abs-button download-eprint">TeX Source</a></li><li><a href="/format/2408.04093" class="abs-button download-format">Other Formats</a></li></ul>
      <div class="abs-license"><a href="http://creativecommons.org/licenses/by/4.0/" title="Rights to this article" class="has_license">
          <img alt="license icon" role="presentation" src="https://arxiv.org/icons/licenses/by-4.0.png"/>
          <span>view license</span>
        </a></div>
    </div>
    <!--end full-text-->    <div class="browse">
    Current browse context: <div class="current">cs.LG</div>

  <div class="prevnext">
<span class="arrow">
      <a class="abs-button prev-url" href="/prevnext?id=2408.04093&amp;function=prev&amp;context=cs.LG"
         accesskey="p" title="previous in cs.LG (accesskey p)">&lt;&nbsp;prev</a>
    </span>
    <span class="is-hidden-mobile">&nbsp; | &nbsp;</span>    <span class="arrow">
      <a class="abs-button next-url" href="/prevnext?id=2408.04093&amp;function=next&amp;context=cs.LG" accesskey="n"
         title="next in cs.LG (accesskey n)">next&nbsp;&gt;</a>
    </span><br/>
  </div><div class="list">
    <a class="abs-button abs-button-grey abs-button-small context-new" href="/list/cs.LG/new">new</a>
    <span class="is-hidden-mobile"> | </span>
    <a class="abs-button abs-button-grey abs-button-small context-recent" href="/list/cs.LG/recent">recent</a>
    <span class="is-hidden-mobile"> | </span><a class="abs-button abs-button-grey abs-button-small context-id" href="/list/cs.LG/2024-08">2024-08</a>
  </div><div class="abs-switch-cat">
    Change to browse by:
    <div class="switch context-change">
        <a href="/abs/2408.04093?context=cs">cs</a><br class="is-hidden-mobile">
        <a class="subclass" href="/abs/2408.04093?context=cs.CL">cs.CL</a><br class="is-hidden-mobile">
    </div>
  </div>

    </div>

    <div class="extra-ref-cite">
      <h3>References &amp; Citations</h3>
      <ul>
        <li><a  class="abs-button abs-button-small cite-ads" href="https://ui.adsabs.harvard.edu/abs/arXiv:2408.04093">NASA ADS</a></li><li><a  class="abs-button abs-button-small cite-google-scholar" href="https://scholar.google.com/scholar_lookup?arxiv_id=2408.04093" target="_blank" rel="noopener">Google Scholar</a></li>
        <li><a  class="abs-button abs-button-small cite-semantic-scholar" href="https://api.semanticscholar.org/arXiv:2408.04093" target="_blank" rel="noopener">Semantic Scholar</a></li>
      </ul>
      <div style="clear:both;"></div>
    </div>

<div class='extra-ref-cite'>
    <a id='bib-cite-css' hidden='true' href='/static/browse/0.3.4/css/cite.css'>a</a>

    <span id='bib-cite-trigger' class="bib-cite-button abs-button">export BibTeX citation</span>
    <span id='bib-cite-loading' hidden='true'>Loading...</span>
</div>

<div id='bib-cite-modal' class='bib-modal' hidden='true'>
    <div class='bib-modal-content'>
        <div class='bib-modal-title'>
            <h2>BibTeX formatted citation</h2>
            <span class='bib-modal-close' >&times;</span>
        </div>
        <div>
            <textarea id='bib-cite-target' class="bib-citation-content" aria-label="loading the citation">loading...</textarea>
        </div>
        <div>
            <span>Data provided by: </span>
            <a id='bib-cite-source-api'></a>
        </div>
    </div>
</div><div class="bookmarks">
  <div><h3>Bookmark</h3></div><a class="abs-button abs-button-grey abs-button-small" href="http://www.bibsonomy.org/BibtexHandler?requTask=upload&amp;url=https://arxiv.org/abs/2408.04093&amp;description=Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters"
     title="Bookmark on BibSonomy">
    <img src="/static/browse/0.3.4/images/icons/social/bibsonomy.png"
         alt="BibSonomy logo"/>
  </a>
  <a class="abs-button abs-button-grey abs-button-small" href="https://reddit.com/submit?url=https://arxiv.org/abs/2408.04093&amp;title=Tree Attention: Topology-aware Decoding for Long-Context Attention on GPU clusters"
     title="Bookmark on Reddit">
    <img src="/static/browse/0.3.4/images/icons/social/reddit.png"
         alt="Reddit logo"/>
  </a>
</div>  </div>
  <!--end extra-services-->
<!-- LABS AREA -->
<div id="labstabs">
  <div class="labstabs"><input type="radio" name="tabs" id="tabone"checked="checked">
    <label for="tabone">Bibliographic Tools</label>
    <div class="tab labs-display-bib">
      <h1>Bibliographic and Citation Tools</h1>
      <div class="toggle">
        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input id="bibex-toggle" type="checkbox" class="lab-toggle">
              <span class="slider"></span>
              <span class="is-sr-only">Bibliographic Explorer Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-bibex">Bibliographic Explorer</span> <em>(<a href="https://info.arxiv.org/labs/showcase.html#arxiv-bibliographic-explorer">What is the Explorer?</a>)</em>
          </div>
        </div>
<div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="litmaps-toggle"
                type="checkbox"
                class="lab-toggle"
                data-script-url="/static/browse/0.3.4/js/litmaps.js?20210617"
                aria-labelledby="label-for-litmaps">
              <span class="slider"></span>
              <span class="is-sr-only">Litmaps Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-litmaps">Litmaps</span> <em>(<a href="https://www.litmaps.co/" target="_blank">What is Litmaps?</a>)</em>
          </div>
        </div>
        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="scite-toggle"
                type="checkbox"
                class="lab-toggle"
                data-script-url="/static/browse/0.3.4/js/scite.js?20210617"
                aria-labelledby="label-for-scite">
              <span class="slider"></span>
              <span class="is-sr-only">scite.ai Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-scite">scite Smart Citations</span> <em>(<a href="https://www.scite.ai/" target="_blank">What are Smart Citations?</a>)</em>
          </div>
        </div>
      </div>
        <div class="labs-content-placeholder labs-display" style="display: none;"></div>
        <div style="min-height: 15px" id="litmaps-open-in"></div>
        <div style="min-height: 15px" id="scite-open-in"></div>
    </div>


    <input type="radio" name="tabs" id="tabtwo">
    <label for="tabtwo">Code, Data, Media</label>
    <div class="tab">
      <h1>Code, Data and Media Associated with this Article</h1>
      <div class="toggle">
        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input        
                id="catalyzex-toggle"
                data-script-url="/static/browse/0.3.4/js/catalyzex.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-cx">
              <span class="slider"></span>
              <span class="is-sr-only">Links to Code Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-cx">CatalyzeX Code Finder for Papers</span> <em>(<a href="https://www.catalyzex.com" target="_blank">What is CatalyzeX?</a>)</em>
          </div>
        </div>

        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="dagshub-toggle"
                data-script-url="/static/browse/0.3.4/js/dagshub.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-dagshub">
              <span class="slider"></span>
              <span class="is-sr-only">DagsHub Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-dagshub">DagsHub</span> <em>(<a href="https://dagshub.com/" target="_blank">What is DagsHub?</a>)</em>
          </div>
        </div>
  
        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="gotitpub-toggle"
                data-script-url="/static/browse/0.3.4/js/gotitpub.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-gotitpub">
              <span class="slider"></span>
              <span class="is-sr-only">GotitPub Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-gotitpub">Gotit.pub</span> <em>(<a href="http://gotit.pub/faq" target="_blank">What is GotitPub?</a>)</em>
          </div>
        </div>

        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="paperwithcode-toggle"
                data-script-url="/static/browse/0.3.4/js/paperswithcode.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-pwc">
              <span class="slider"></span>
              <span class="is-sr-only">Links to Code Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-pwc">Papers with Code</span> <em>(<a href="https://paperswithcode.com/" target="_blank">What is Papers with Code?</a>)</em>
          </div>
        </div>


        <div class="columns is-mobile lab-row">
          <div class="column lab-switch">
            <label class="switch">
              <input
                id="sciencecast-toggle"
                data-script-url="/static/browse/0.3.4/js/sciencecast.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-sciencecast">
              <span class="slider"></span>
              <span class="is-sr-only">ScienceCast Toggle</span>
            </label>
          </div>
          <div class="column lab-name">
            <span id="label-for-sciencecast">ScienceCast</span> <em>(<a href="https://sciencecast.org/welcome" target="_blank">What is ScienceCast?</a>)</em>
          </div>
        </div>
      </div>

      <div id="catalyzex-output" style="display:none"></div>
      <div id="dagshub-output" style="display:none"></div>
      <div id="gotitpub-output" style="display:none"></div>
      <div id="pwc-output" style="display:none"></div>
      <div id="pwc-data-output" style="display:none"></div>
      <div id="sciencecast-output" style="display:none"></div>
    </div>


      <input type="radio" name="tabs" id="labstabs-demos-input">
      <label for="labstabs-demos-input" id="labstabs-demos-label">Demos</label>
      <div class="tab">
        <h1>Demos</h1>
        <div class="toggle">
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input
                  id="replicate-toggle"
                  data-script-url="/static/browse/0.3.4/js/replicate.js"
                  type="checkbox" class="lab-toggle" aria-labelledby="label-for-replicate">
                <span class="slider"></span>
                <span class="is-sr-only">Replicate Toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-replicate">Replicate</span> <em>(<a href="https://replicate.com/docs/arxiv/about" target="_blank">What is Replicate?</a>)</em>
            </div>
          </div>
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input
                  id="spaces-toggle"
                  data-script-url="/static/browse/0.3.4/js/spaces.js"
                  type="checkbox" class="lab-toggle" aria-labelledby="label-for-spaces">
                <span class="slider"></span>
                <span class="is-sr-only">Spaces Toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-spaces">Hugging Face Spaces</span> <em>(<a href="https://huggingface.co/docs/hub/spaces" target="_blank">What is Spaces?</a>)</em>
            </div>
          </div>
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input
                  id="txyz-toggle"
                  data-script-url="/static/browse/0.3.4/js/txyz.js"
                  type="checkbox" class="lab-toggle" aria-labelledby="label-for-txyz">
                <span class="slider"></span>
                <span class="is-sr-only">Spaces Toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-txyz">TXYZ.AI</span> <em>(<a href="https://txyz.ai" target="_blank">What is TXYZ.AI?</a>)</em>
            </div>
          </div>
        </div>
        <div id="replicate-output"></div>
        <div id="spaces-output"></div>
        <div id="txyz-output"></div>
      </div>
      <input type="radio" name="tabs" id="tabfour">
      <label for="tabfour">Related Papers</label>
      <div class="tab">
        <h1>Recommenders and Search Tools</h1>
        <div class="toggle">
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input id="influenceflower-toggle"
                data-script-url="/static/browse/0.3.4/js/influenceflower.js"
                type="checkbox" class="lab-toggle" aria-labelledby="label-for-influenceflower">
                <span class="slider"></span>
                <span class="is-sr-only">Link to Influence Flower</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-influenceflower">Influence Flower</span> <em>(<a href="https://influencemap.cmlab.dev/" target="_blank">What are Influence Flowers?</a>)</em>
            </div>
          </div>
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input id="connectedpapers-toggle" type="checkbox" class="lab-toggle"
                       data-script-url="/static/browse/0.3.4/js/connectedpapers.js"
                       aria-labelledby="label-for-connected-papers" >
                <span class="slider"></span>
                <span class="is-sr-only">Connected Papers Toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-connected-papers">Connected Papers</span> <em>(<a href="https://www.connectedpapers.com/about" target="_blank">What is Connected Papers?</a>)</em>
            </div>
          </div>
          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input id="core-recommender-toggle" type="checkbox" class="lab-toggle" aria-labelledby="label-for-core">
                <span class="slider"></span>
                <span class="is-sr-only">Core recommender toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-core">CORE Recommender</span> <em>(<a href="https://core.ac.uk/services/recommender">What is CORE?</a>)</em>
            </div>
          </div>          <div class="columns is-mobile lab-row">
            <div class="column lab-switch">
              <label class="switch">
                <input id="iarxiv-toggle"
                       type="checkbox"
                       class="lab-toggle"
                       data-script-url="/static/browse/0.3.4/js/iarxiv.js"
                       aria-labelledby="label-for-iarxiv">
                <span class="slider"></span>
                <span class="is-sr-only">IArxiv recommender toggle</span>
              </label>
            </div>
            <div class="column lab-name">
              <span id="label-for-iarxiv">IArxiv Recommender</span>
              <em>(<a href="https://iarxiv.org/about">What is IArxiv?</a>)</em>
            </div>
          </div>
</div>
        <div id="influenceflower-output"></div>
        <div id="influenceflower-output-graph" style="display:none">
          <ul class="flower-tabs">
            <li class="active"><a class="btn tab-btn" onclick="openTab(event, 'tab-author')">Author</a></li>
            <li><a class="btn tab-btn" onclick="openTab(event, 'tab-venue')">Venue</a></li>
            <li><a class="btn tab-btn" onclick="openTab(event, 'tab-inst')">Institution</a></li>
            <li><a class="btn tab-btn" onclick="openTab(event, 'tab-topic')">Topic</a></li>
          </ul>
          <div class="flower-tab-content">
            <div class="tab-flower active" id="tab-author"><svg id="flower-graph-author"></svg></div>
            <div class="tab-flower" id="tab-venue"><svg id="flower-graph-venue"></svg></div>
            <div class="tab-flower" id="tab-inst"><svg id="flower-graph-inst"></svg></div>
            <div class="tab-flower" id="tab-topic"><svg id="flower-graph-topic"></svg></div>
          </div>
        </div>
        <div style="min-height: 15px" id="connectedpapers-output"></div>
        <div id="coreRecommenderOutput"></div>
        <div id="iarxivOutput"></div>
      </div>

      <input type="radio" name="tabs" id="tabfive">
      <label for="tabfive">
        About arXivLabs
      </label>
      <div class="tab">
        <div class="columns">
          <div class="column">
            <h1>arXivLabs: experimental projects with community collaborators</h1>
            <p>arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.</p>
            <p>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.</p>
            <p>Have an idea for a project that will add value for arXiv's community? <a href="https://info.arxiv.org/labs/index.html"><strong>Learn more about arXivLabs</strong></a>.</p>
          </div>
          <div class="column is-narrow is-full-mobile">
            <p class="icon-labs"><svg xmlns="http://www.w3.org/2000/svg" role="presentation" viewBox="0 0 635.572 811"><path d="M175.6 676v27h-27v-27zm-54 27v27h27v-27zm-27 27v27h27v-27zm396-54v27h-27v-27zm0 27v27h27v-27zm27 27v27h27v-27zm-27-414h27v27h-27zm27 0h27v-27h-27zm27-27h27v-27h-27zm-396 45h-27v-27h27zm-27-54h-27v27h27zm-27-27h-27v27h27z"/><path d="M94.6 730v27h-27v-27zm477 0v27h-27v-27zm-27-495h27v27h-27zm-450 18h-27v-27h27zm477 9h27v27h-27zm-54 495h27v27h-27zm-423 0h27v27h-27zm-54-504h27v27h-27z" fill="#666"/><path d="M67.6 730v27h-27v-27zm54 54v27h-27v-27zm0-108v27h27v-27zm-27 27v27h27v-27zm-81 0v27h27v-27zm585 27v27h-27v-27zm-108-54v27h27v-27zm27 27v27h27v-27zm81 0v27h27v-27zm-54-495h27v27h-27zm-54 108h27v-27h-27zm27-27h27v-27h-27zm0-81h27v-27h-27zm-423 18h-27v-27h27zm54 54h-27v27h27zm-27-27h-27v27h27zm0-81h-27v27h27zm423 612v27h-27v-27zm81-522v27h-27v-27zm-585-9v27h-27v-27z" fill="#999"/><path d="M94.6 784v27h-27v-27zm-27-27v27h27v-27zm-27-54v27h27v-27zm27 0v27h27v-27zm0-27v27h27v-27zm27 0v27h27v-27zm0-27v27h27v-27zm27 0v27h27v-27zm-108 81v27h27v-27zm558 54v27h-27v-27zm-27-27v27h27v-27zm27-54v27h27v-27zm-27 0v27h27v-27zm0-27v27h27v-27zm-27 0v27h27v-27zm0-27v27h27v-27zm-27 0v27h27v-27zm108 81v27h27v-27zm0-495h27v27h-27zm-27 27h27v-27h-27zm-54-27h27v-27h-27zm0 27h27v-27h-27zm-27 0h27v-27h-27zm0 27h27v-27h-27zm-27 0h27v-27h-27zm0 27h27v-27h-27zm81-108h27v-27h-27zm-504 45h-27v-27h27zm27-27h-27v27h27zm54-27h-27v27h27zm0 27h-27v27h27zm27 0h-27v27h27zm0 27h-27v27h27zm27 0h-27v27h27zm0 27h-27v27h27zm-81-108h-27v27h27z" fill="#ccc"/><path d="M598.6 665.1H41.5C-76.5 667 176 280.2 176 280.2h53a46.5 46.5 0 0162.8-56.3 29.2 29.2 0 1128.5 35.9h-1a46.5 46.5 0 01-1.5 20.3l142.5-.1s255.3 387 138.3 385.1zM291 181a29.3 29.3 0 10-29.2-29.3A29.3 29.3 0 00291 181zm65.4-66.8a22.4 22.4 0 10-22.5-22.4 22.4 22.4 0 0022.5 22.4z" fill="#fc0"/><path d="M245.5 172V10h153v162s324 495 198 495h-558c-126 0 207-495 207-495zm126 54h56m-13 72h56m-9 72h56m-20 72h56m-22 72h56m-29 72h56m-457-45c20.8 41.7 87.3 81 160.7 81 72.1 0 142.1-38.2 163.4-81" fill="none" stroke="#000" stroke-miterlimit="10" stroke-width="20"/><path d="M273.3 421.7c0 31-9.8 56.3-21.9 56.3s-21.8-25.2-21.8-56.3 9.8-56.3 21.8-56.3 21.9 25.2 21.9 56.3zm114.4-56.3c-12 0-21.8 25.2-21.8 56.3s9.7 56.3 21.8 56.3 21.9-25.2 21.9-56.3-9.8-56.3-21.9-56.3zM150.1 526.6c-18.2 6.7-27.5 22.9-23.2 30.2s14.8-5.5 33-12.2 37.4-4.9 33-12.2-24.5-12.6-42.8-5.8zm296 5.8c-4.2 7.3 14.9 5.5 33.1 12.2s28.7 19.5 33 12.2-5-23.5-23.2-30.2-38.5-1.5-42.8 5.8z"/></svg></p>
          </div>
        </div>
      </div>

    </div>
</div>
<!-- END LABS AREA -->
  <div class="endorsers">
    <a href="/auth/show-endorsers/2408.04093" class="endorser-who">Which authors of this paper are endorsers?</a> |
    <a id="mathjax_toggle" href="javascript:setMathjaxCookie()">Disable MathJax</a> (<a href="https://info.arxiv.org/help/mathjax.html">What is MathJax?</a>)
    <span class="help" style="font-style: normal; float: right; margin-top: 0; margin-right: 1em;"></span>
  </div>
  <script type="text/javascript" language="javascript">mathjaxToggle();</script>
</div>
      </div>
    </main>

    <footer style="clear: both;">
      <div class="columns is-desktop" role="navigation" aria-label="Secondary" style="margin: -0.75em -0.75em 0.75em -0.75em">
        <!-- Macro-Column 1 -->
        <div class="column" style="padding: 0;">
          <div class="columns">
            <div class="column">
              <ul style="list-style: none; line-height: 2;">
                <li><a href="https://info.arxiv.org/about">About</a></li>
                <li><a href="https://info.arxiv.org/help">Help</a></li>
              </ul>
            </div>
            <div class="column">
              <ul style="list-style: none; line-height: 2;">
                <li>
                  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>
                  <a href="https://info.arxiv.org/help/contact.html"> Contact</a>
                </li>
                <li>
                  <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg>
                  <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a>
                </li>
              </ul>
            </div>
          </div>
        </div>
        <!-- End Macro-Column 1 -->
        <!-- Macro-Column 2 -->
        <div class="column" style="padding: 0;">
          <div class="columns">
            <div class="column">
              <ul style="list-style: none; line-height: 2;">
                <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li>
                <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li>
              </ul>
            </div>
            <div class="column sorry-app-links">
              <ul style="list-style: none; line-height: 2;">
                <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li>
                <li>
                  <p class="help">
                    <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br>
                    Get status notifications via
                    <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a>
                    or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a>
                  </p>
                </li>
              </ul>
            </div>
          </div>
        </div> <!-- end MetaColumn 2 -->
        <!-- End Macro-Column 2 -->
      </div>
    </footer>
  </div>

  <script src="/static/base/1.0.1/js/member_acknowledgement.js"></script>

</body>

</html>
2408.04093
 The self-attention operation is the core computational building block of the transformer architecture [1, 2], which has become an ubiquitous and highly effective workhorse architecture currently applied at scale to language [3–7], vision [8], audio [9], and decision-making [10, 11]. Nonetheless, the quadratic time complexity of self-attention means that significant resources are required to train and generate from transformer-based Large Language Models (LLMs), especially for models with large context lengths.  During inference, the attention block largely determines the computational and memory requirements, which become more demanding as the input sequence length increases. Although LLMs generate one token at a time, the entire sequence of past tokens must still be stored in memory and used to compute attention scores during generation. Since attention performs a similarity matching of every token representation with every other, it incurs quadratic computational complexity in terms of flops.  There have been recent advances in training LLMs to handle extremely long contexts (up to 1M tokens)[12– 14].Such models attain qualitatively new capabilities such as extremely large-scale in-context learning of entire small datasets held in the prompt [15–17]. They can also avoid putting multi-modal continuous data through a lossy tokenization scheme [15, 18] by directly operating at the byte level [19, 20]. The issue however is that performing inference on such long contexts is very expensive.  To speed up inference and alleviate memory requirements, recent works have attempted to alter the attention mechanism itself, either by linearizing it [21], or approximating it by a kernel map [22–24], which reduces the complexity to linear at the cost of reduced expressiveness.  Others have invented alternative sequence mixing architectures such as state-space models which are designed to be efficiently computable in linear time and constant memory [25–29]. Other approaches utilize efficient algorithms to reduce the computational burden of attention while keeping the core computation the same. These include memory-efficient attention [30], Flash Attention [31] and Flash Decoding [32], which provide a set of IOaware kernels to map the attention operation to the GPU hardware resources in an extremely efficient way, significantly reducing the memory overhead required. Further works [33–36] explore compressing or otherwise reducing the KV cache required in generation. Finally, Ring Attention [37] proposes a way to parallelize the attention computation across the sequence axis between GPUs, thus enabling significantly longer contexts than can be served on a single GPU. This is the regime of primary interest of this paper. By leveraging the exact energy function for the self-attention block, we develop a method to speed up inference for long context use-cases when keys and values are sharded across multiple GPUs along the sequence axis.  Our proposed algorithm for computing attention via the gradient of the energy function is built on top of an efficient parallel computation and tree reduction communication strategy. In particular, this formulation lets us devise an asymptotically faster algorithm for performing decoding in which the number of communication steps scales logarithmically with the number of devices, instead of linearly in alternatives such as Ring Attention [37].  Our topology-aware approach illustrated in Fig. 1 significantly outperforms leading attention parallelization methods such as Ring Attention on multiple devices.  In this work, we make three core contributions: - We provide a mathematical form for the energy function of self-attention.  - From this theory, we develop an algorithm for parallelizing the attention computation across devices, leveraging tree-reduction topology.  ![1_image_0.png](1_image_0.png)  - Finally, we show empirically that our algorithm provides *asymptotic* speedups when decoding across many GPUs on long sequence lengths, as well as large reductions in communication volume and peak memory usage. 
introduction
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Introduction
2408.04093
 Following the ubiquitous success of the transformer architecture, there has been significant effort to mathematically understand the nature and meaning of the attention operation and link it to related architectures, such as recurrent networks and Hopfield Networks. A number of recent works have attempted to study self-attention mathematically through the lens of energy functions. Ramsauer et al. [38] pioneered this field by performing a similar but distinct analysis to relate self-attention with the modern Hopfield networks [39], providing a novel and insightful interpretation of self-attention as performing hetero-associative memory lookups using a high-powered nonlinear similarity function [40, 41]. This work was later extended by Hoover *et al.* [42], who derived a modified version of the transformer based off an energy function.  Beyond this, other recent work attempted a Bayesian reformulation of attention by deriving a probabilistic generative model which matches the operations performed in a self-attention operation [43].  However, while it has long been known that the softmax operation can be derived as the gradient of the following scalar function:  $$\partial_{z_{j}}\log\sum_{a=1}^{n}\exp(z_{a})={\frac{e^{z_{j}}}{\sum_{a=1}^{n}e^{z_{a}}}}=\operatorname{softmax}(z_{j}),\quad(1)$$  known as the log-sum-exp, an equivalent function for the self-attention block has not yet been derived.  In particular, consider the energy function proposed in [42], which is the logsumexp. Since the gradient in the update rule of that paper is taken with respect to the input to the block, the resulting function is a modified version of the self-attention operation. Similarly, the update rule in [38] requires the tying of certain weights (K and V) in the attention operation. This restricts the Hopfield derivation to modelling auto-associative retrieval networks, while transformer attention is hetero-associative.  To advance beyond this, our energy function depends on an auxiliary source vector  (see section 4.). Taking the gradient with respect to  yields the exact self-attention operation, as we show below. Consequently, this formulation enables us to express self-attention with no weight tying.  Another notable related work is [44], where the authors made similar observations as we do in section 5. about how the associative operations within the attention computation can be efficiently parallelized to motivate an attention-based modified RNN architecture for sequence modeling.  While this energy function by itself is primarily a mathematical and theoretical curiosity, we demonstrate below that when combined with automatic differentiation, our formulation naturally leads to highly efficient parallel algorithms for computing attention and performing decoding, especially across multiple devices. 
introduction
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Related Work
2408.04093
 The self-attention operation can be represented as a set of dot product similarity searches between queries and keys. These similarity scores are then reduced along the sequence axis and softmaxed, so that for a given query, there is a probability distribution of the similarities of each given key. We then take the expectation of the value vectors against this distribution. We denote the queries assigned to a sequence of length  as {,  = 1, · · · }, where each query is a vector of size  that stands for hidden dimension,  ∈ R  , and similarly the keys and values {(, ),  = 1, · · · }. Attention can be written as  $$z^{a}=\sum_{i=1}^{N}\mathrm{softmax}(q_{a}\cdot k_{i}^{T})v_{i}\,.$$  The dot product, more explicitly, reads:  $$q_{a}\cdot k_{i}=\sum_{A=1}^{d}q_{a,A}k_{i,A},\forall A\in\{1,\cdots,d_{h}\}.$$  The capital Latin indices () span the hidden dimension ℎ. Naively computing attention in this way requires materializing the  matrix with computational and memory cost quadratic in the sequence length. Memory-efficient attention [30] is an iterative way to compute the softmax similarities without ever having to materialize the full attention matrix. It performs the following operations, one query (or a chunk of queries) at a time: $$s_{i}^{(j)}=\exp(q_{j}\cdot k_{i})\tag{2}$$ $$n_{i}^{(j)}=n_{i-1}^{(j)}+v_{i}s_{i}^{(j)}$$ (3) $$d_{i}^{(j)}=d_{i-1}^{(j)}+s_{i}^{(j)}\tag{4}$$ 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Self-Attention
2408.04093
Computed, We Divide To Get The Final Softmaxed Scores  ( ) =  ( )  ( )For Every Query Index . Computing Attention In This Iterative Manner Significantly Reduces The Required Memory. Flash Attention [31] Utilizes A Similar Approach To Reduce The Memory And Computational Cost Of Attention, But The Algorithm Is Not Adapted For Multi-Gpu Computation. Flash Attention Performs The Iterative Algorithm Of [30] In A Blockwise Manner, Utilizing The Block-Parallel Computational Primitives Available Inside Single Gpu Tensor Cores. Additionally, It Precisely Sizes The Blocks Such That They Can Fit Into The Sram Of The Gpu For The Entire Attention Computation, Effectively Performing Kernel Fusion And Preventing Many Unnecessary Io Operations. 4. Self-Attention As A Gradient  Here, we show how the self-attention operation can be written as the gradient of a certain scalar function. In particular, we define a scalar function that depends on the keys, queries, values and additionally on an auxiliary vector that we refer to as the *source* . The source is the parameter with respect to which we compute the gradient of the scalar function to obtain the self-attention operation. We need the source in order to write down the generating function of the moments of the distribution above. It is also the variable with respect to which we can Taylor-expand the generating function and extract the moments as the coefficients of the monomials of appearing in the Taylor series. Explicitly, we want to find a function (*, , ,* ) such that:  $$\sum_{a=1}^{N}\mathrm{softmax}(q\cdot k_{a})v_{a}=\left.\frac{\partial F}{\partial\zeta}\right|_{\zeta=0}.$$  This terminology is inspired by work on energy-based models in machine learning [45–47]. A summary of variables and indices is provided in appendix 12. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Then, Once The Values  And Softmax Denominator  Are
2408.04093
 Here, we show how the energy function is given by the cumunlant-generating function associated to the distribution given by attention scores. Taking inspiration from statistical mechanics, where an analogous cumulantgenerating function defines the Helmholtz Free energy [48], we dub our cumulant-generating function the *energy* function for self-attention.  Let us focus on the case with a single query. As noted above, we leverage the fact that the attention operation can be seen as the computation of the expectation value of the vectors  in the distribution set by the attention scores :  $$z=\langle v\rangle=\sum_{a=1}^{N}P_{a}v_{a}={\frac{\sum_{a=1}^{N}e^{q\cdot k_{a}^{T}}v_{a}}{\sum_{i=1}^{N}e^{q\cdot k_{i}^{T}}}}.$$  $$\quad(6)$$  . (6) The probability density is given by:  $$P_{a}={\frac{e^{q\cdot k_{a}^{2}}}{\sum_{i=1}^{N}e^{q\cdot k_{i}^{T}}}},$$  and satisfies:  $$\quad(7)$$ $$\sum_{a=1}^{N}P_{a}=1.$$  $$(8)$$  Typically, the denominator or normalization factor is identified with the so-called partition function:  $$Z=\sum_{a=1}^{N}e^{q\cdot k_{a}^{T}}.$$  $$({\mathfrak{g}})$$  We can now compute the first moment of the probability distribution given above by introducing a source,  ∈ R  .  In our case, with , we can extend the partition function to the function:  $$Z(\zeta)=\sum_{a=1}^{N}e^{q\cdot k_{a}^{T}+\zeta\cdot v_{a}^{T}}.$$  $$(10)$$  Now, we can compute any moment of the distribution as the -th Taylor coefficient of () ∀1, 2, · · · ∈ {1, · · · , ℎ} :  $$\left\langle v_{A_{1}}\cdots v_{A_{n}}\right\rangle=\frac{1}{Z}\frac{\partial^{n}Z(\zeta)}{\partial\zeta_{A_{1}}\cdots\partial\zeta_{A_{n}}}\bigg|_{\zeta=0}.$$ $$(11)$$ $$(12)$$  . (11)  In other words, we can write () as:  $$Z(\zeta)=Z\left(1+\langle v\rangle\zeta+\frac{1}{2!}\langle v_{A_{1}}v_{A_{2}}\rangle\zeta_{A_{1}}\zeta_{A_{2}}+\cdots\right)$$ $$\mathbf{\dot{\theta}}$$  Therefore, the first moment can be written as:  $$\langle v\rangle=\frac{1}{Z}\frac{\partial Z}{\partial\zeta}\bigg|_{\zeta=0}\,,$$ $$(13)$$  which can be written as the gradient of the log of ():  $$\langle v\rangle=\frac{\partial}{\partial\zeta}\log Z(\zeta)\bigg|_{\zeta=0}.$$  . (14) This quantity is the generating function, a.k.a. the free energy:  $$F=\log\sum_{a}\exp\left(q\cdot k_{a}^{T}+\zeta\cdot v_{a}^{T}\right).$$  . (15) To compute causal self-attention, we introduce sources each ∈ R  and take  $$F_{tot}=\sum_{i=1}^{N}F_{i}=\sum_{i=1}^{N}\log\sum_{a=1}^{i}\exp\Bigl{(}q_{i}\cdot k_{a}^{T}+\zeta_{i}\cdot v_{a}^{T}\Bigr{)}.\tag{16}$$  The truncation of the inner sum up to index  is due to causal masking.  Now, in order to compute the -th element of causal self-attention, we differentiate with respect to  and set it to zero:  $$\left.\frac{\partial F_{t o t}}{\partial\zeta_{i,A}}\right|_{\zeta_{i}=0,\forall i}=\frac{\sum_{a=1}^{i}\exp\bigl{(}q^{i}\cdot k_{a}^{T}\bigr{)}v_{a,A}}{\sum_{a=1}^{i}\exp\bigl{(}q^{i}\cdot k_{a}^{T}\bigr{)}}.\qquad(17)$$  The generalization to the multi-head attention case is straightforward. In this case, there is one key, query and value per head. For ℎ total heads, the generating function takes the form:  $$F_{t o t}=\sum_{i=1}^{N}\sum_{h=1}^{n_{h}}F^{i,h},$$  , (18) where  $$F_{i,h}=\log\sum_{a=1}^{i}\exp\left(q_{i,h}\cdot k_{h,a}^{T}+\zeta_{h,i}\cdot v_{h,a}^{T}\right).\tag{19}$$  The output projection weight is included in the definition of   here, meaning that  $$\nu_{b,A}=x_{b,\bar{B}}(W_{O}W_{V})_{A,\bar{B}}$$ , = ,¯( ),¯ (20) where  ∈ R ℎ × R  denotes a head size slice of the output projection weight and ¯ ∈ {1, · · · , ℎ} spans the intra-head indices. In the index notation above, the head indices are barred whereas the embedding space indices are unbarred. We proceed focusing on the single-head case, as it makes the presentation simpler, and the multi-head generalization is immediate. Note that we demonstrate that our energy function approach also can account for safe softmax in Appendix 11. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
The Energy Function
2408.04093
 The fact that it is possible to derive the self-attention operation as the minimization of an energy function implies  $$(14)$$  that it is possible to provide a Bayesian gloss on selfattention by identifying a likelihood function and showing that we can obtain the forward pass of the attention block from computing the maximum a posteriori estimate of this likelihood.  In particular, we propose the following for the loglikelihood function:  $$\Gamma(\zeta,z)=\sum_{i=1}^{N}\sum_{A=1}^{d}\left(z_{i,A}\zeta_{i,A}-F(\zeta,x)\right).$$  . (21) $$\left(15\right)$$  We denote by  the input to the self-attention block from which we obtain *, ,*  from multiplying it by the weights ,  ,  respectively. Let us minimize the above with respect to  and  simultaneously: $$\begin{array}{c}{{\frac{\partial\Gamma}{\partial\zeta_{i,A}}=0,}}\\ {{\frac{\partial\Gamma}{\partial z_{i,A}}=0.}}\end{array}$$  $$\quad(22)$$  $$\quad(23)$$ $$(24)$$  These conditions written explicitly read  $$\zeta_{i,A}*=0,\;\;\;z_{i,A}*=\frac{\partial F}{\partial\zeta_{i,A}}.$$  . (24) Plugging the first condition into the second leads to the attention forward pass:  $$\Sigma_{i\,*,A}={\frac{\sum_{a=1}^{i}\,e^{q_{i}\cdot k_{a}^{T}}v_{a,A}}{\sum_{b=1}^{i}\,e^{q_{i}\cdot k_{b}^{T}}}}.$$ $$(25)$$  $$(18)$$  In all, this means we can obtain the gradient w.r.t.   from MAP estimation of the following likelihood:  $$\mathbf{x}_{\zeta,z}e^{-1\,(z\,,z)}.$$ $$z_{i\,*,A},\zeta_{i\,*,A}=\arg\arg$$   ∗,,  ∗, = argmax ,  −Γ( ,). (26) Moreover, such a procedure enables us to identify the energy-based model associated with the self-attention function. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Bayesian Interpretation
2408.04093
 $$(20)^{\frac{1}{2}}$$  In this section we show how the formulation of the attention operation as the gradient of an energy function suggests an efficient parallel strategy for computing it.  The key insight is to leverage an efficient algorithm to compute the energy, and then differentiate it in order to obtain an efficient algorithm to compute attention. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Tree Attention
2408.04093
 Let us focus on the case of decoding with a KV cache in a causal language model where we have one query and keys and values. In this case, the energy function is:  $$F_{dec}=\log\sum_{a=1}^{N}\exp\Bigl{(}q\cdot k_{a}^{T}+\zeta\cdot v_{a}^{T}\Bigr{)}\tag{27}$$  $\equiv$ logsumexp${}_{a}(\{q\cdot k_{a}^{T}+\zeta\cdot v_{a}^{T},a=1,\cdots,N\})$. (28)  $$(21)$$  4 A crucial fact is that both logsumexp and max are associative operations:  ``` logsumexp                     ({, logsumexp                                                  ({, })}) =  logsumexp                        ({logsumexp                                                ({, }), }),  ```  $$\operatorname*{max}(\{\operatorname*{max}(\{T_{a},R_{a}\}),S_{a}\})=$$  $$=\operatorname*{max}_{a}(\{T_{a},\operatorname*{max}_{a}(\{R_{a},S_{a}\})\}).$$  We can prove that this associative property allows these reductions to be performed efficiently in parallel with logarithmic time complexity, provided we have adequately many parallel workers: Theorem 1. *The time complexity of a reduction operation* involving an associative function, such as *logsumexp* or max, over an array of size  using  *parallel processors* is   + log  . When the number of processors  is equal to *, the time complexity is reduced to* (log ).  The proof of Theorem 1 is in Appendix 10.. Putting this result together, and for , ˆ ˆ ∈ {1, · · · , } intra-chunk indices, we get the following highly parallel Algorithm 1: 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Computing The Energy Efficiently
2408.04093
 1: Divide k, v ∈ R  ×ℎ into  chunks {kˆ, vˆ, ˆ ∈ {1, · · · , /}} of size  = / 2: Scatter a copy of q, , and each kˆ, vˆ to each of the processors.  3: In parallel compute ˆ = q · k ˆ +  · v ˆ 4: Compute  = Reduce(max, ) by doing a tree reduction.  5: Scatter  to every device and update ˆ → ˆ − .  6: Compute  = Reduce(logsumexp, ) by doing a tree reduction.  7: Save ,  for gradient w.r.t .  8: Return  
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Algorithm 1 Single Query Energy Forward
2408.04093
 One of the core insights of automatic differentiation is that the gradient of a function ∇  () can be computed with the same time complexity as computing  () [49]. The caveat however is that if the function has a deep computational graph, then the memory footprint of computing the gradient grows with that depth as backpropagation requires storing the values of the intermediate tensors.  In our case, the computational graph involved in computing the energy is shallow and therefore the memory overhead is negligible. This means that if we can compute the energy efficiently, we obtain an efficient algorithm for computing its gradient (i.e. the self-attention operation) automatically.  In our case, we want to compute the gradient of the energy function with respect to  and then set it to zero. This can be done with automatic differentiation engines having set  to be a tensor of zeros from the very outset. We can however manually implement a gradient with respect to  pass of the above Algorithm 1 that doesn't materialize  in Algorithm 2 below. Note in particular that when we set  = 0, ∀ ∈ {1, · · · , ℎ} then  involves only the logsumexp of the dot product between queries and keys.  Algorithm 2 Single Query Energy Gradient w.r.t   1: Divide k, v ∈ R  ×ℎ into  chunks {kˆ, vˆ, ˆ ∈ {1, · · · , /}} of size  = / 2: Scatter a copy of q,  and , and each kˆ, vˆ to each of the  processors.  3: In parallel compute ˆ = q · k ˆ −  4: Compute ˆ = exp(ˆ − ) · ˆ 5: Compute  = Reduce(sum, ) 6: Return  Notice here that by storing ,  for backward, the only remaining reduction operation that needs to be performed is the one in line 5 of the above algorithm. This single reduction takes (/) time to compute the local sums on each device and log  time to communicate and combine partial results, and therefore we get the same asymptotic complexity as the logsumexp calculation.  In practice, we implement the forward and gradient w.r.t.  in a single function which returns both the value and the gradient of the energy function. We can therefore put together Algorithms 1 and 2 into the following efficient parallel decoding Algorithm 3: 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Efficient Parallel Decoding
2408.04093
 1: Divide k, v ∈ R  ×ℎ among  GPUs where each GPU has a chunk {kˆ, vˆ, ˆ ∈ {1, · · · , /}} of size  = /.  2: Scatter q to each GPU.  3: On each GPU, use Flash Attention 2 to compute o = Íˆ expq·k ˆ vˆ Íˆ expq·k ˆ  and lse = log Íˆ expq · k ˆ .  4: Recompute the global max  = Allreduce(max, lse).  5: Obtain the local numerator and denominator by then computing: n = o ∗ exp(lse − ), d = exp(lse − ).  6: Compute global numerator and denominator n = Allreduce(sum, n), d = Allreduce(sum, d).  7: Return result  = n d  . This algorithm requires three Allreduce operations in total, meaning that the required time complexity is (3(/ + log )). 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Algorithm 3 Tree Decoding
2408.04093
 While the theoretical analysis above indicates that we should see speedups when using tree-based reductions, this is not necessarily guaranteed in practice due to various potential overheads. However, importantly, beyond its asymptotic benefits, Tree Attention benefits from taking advantage of the two-level topology which is standard in modern GPU clusters.  ![5_image_0.png](5_image_0.png)  Ring Attention is inherently not topology-aware, and only scales within a network of homogeneous bandwidth. However, this is in conflict with the two-level network topology of modern GPU clusters, which use high-bandwidth interconnects within nodes (NVLINK or PCIe) and comparatively lower-bandwidth interconnects across nodes (InfiniBand or Ethernet). The interconnects greatly differ in bandwidth and latency (see Figure 2). Therefore, Ring Attention is bottlenecked by the slowest interconnect, and cannot always overlap the attention computation with communication. We discuss this point further in 6. 6.3. Tree Attention improves on Ring Attention by using network topology-aware communication patterns to increase overlap of computation and communication, and decrease this scalability bottleneck on communication from the distributed attention computation.  In practice, collective communication libraries like NCCL attempt to automatically detect what the right communication strategy is based on considerations such as data volume and network topology. In DGX clusters, for collective operations within a node, ring reduce is performed whereas a tree reduction is performed across nodes. We see that therefore using built-in collective operations such as Allreduce leads to a better performance when decoding from long contexts across multiple GPUs than enforcing the Ring Attention's point to point communication pattern. We show how the following strategy outperforms Ring Attention when decoding from very long contexts across multiple GPUs.  In our empirical experiments , we use Flash Attention 2 [50] within each device, both for our algorithm and for Ring Attention1. We provide a simple JAX implementation of our method in Appendix 9.. Note that our method mirrors Flash Decoding [32] except in that case, the parallelization happens at the level of different streaming multiprocessors (SMs) within a GPU whereas we parallelize between different GPUs. All computations are performed in BF16. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Implementation And Topology-Awareness
2408.04093
 Similar to Ring Attention, Tree Attention is an exact computation of attention. Since training and evaluation metrics are the same as for attention, our experimental results are focused primarily on latency in section 6. 6.1., peak memory usage in section 6. 6.2. and communication volumes in section 6. 6.3.. Since our algorithm computes numerically identical results as the forward pass of standard attention, our performance results transfer seamlessly to transformer architectures.  We performed all experiments on a DGX H100 cluster consisting of 16 nodes, each containing 8 H100 GPUs.  All GPUs within the node are connected via an all-to-all NVLINK 4.0 (900GBps) topology. Nodes are connected to each other via 8 InfiniBand NDR interconnects per node (1 per GPU), each of which provides 400 Gbps (leading to an aggregate 3.2 Tbps node injection bandwidth). 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Results
2408.04093
 In terms of practical usefulness, our study of the energy function brought to light a previously unnoted parallelizability inside the attention computation - that of the reduction of the logsumexp across the sequence dimension, which can be implemented as a parallel Allreduce.  As stated in Theorem 1, it becomes theoretically possible to implement attention, per query as an / + log() parallel operations rather than , where the logarithmic term is proportional to the number of devices available for parallelization. When the attention is sharded across multiple devices, this asymptotic speedup creates a considerable speedup over alternative methods for decoding.  To empirically test the theoretical benefits of our Tree Attention method, we compute latency by measuring the time required to perform decoding for different sequence lengths and varying number of H100 nodes. We compare Tree Attention to our own Ring Attention execution times in Fig. 3. Both methods use Flash Attention 2 [50] for the individual-GPU attention computation. For our experiments, we benchmark on a standard attention block consisting of 16 heads of dimension 128 across different sequence lengths.  ![6_image_1.png](6_image_1.png)  ![6_image_0.png](6_image_0.png)  ![6_image_2.png](6_image_2.png)  Our latency results shows how Tree Attention improves over Ring Attention as we increase the sequence length in Fig. 3(a) and increase the number of GPUs in Fig. 3(b). As the plots demonstrate, as we scale the sequence length or the number of GPUs, the gap between Tree Attention and Ring Attention execution time widens asymptotically. Remarkably, Tree Attention achieves close x8 speedups when we use 128 GPUs on a sequence length of 5.12M. We expect this trend to continue for larger sequence lengths. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Latency
2408.04093
 To perform Ring Attention with a distributed KV cache, it is necessary to broadcast the query corresponding to the final element of the sequence back to all devices, as outlined in step 2 of our Algorithm 1 . Each device will then hold a tuple (q, k a , v a ), where a is the chunk index, which includes the query vector and a local chunk of the keys and values specific to the sequence chunk on that device.  The memory cost to store these objects is the same as for Tree Decoding. Additionally, Ring Attention must store the k a , v a , coming from the neighbouring device and the chunk of the output o that has the same shape as the query held by that device. In contrast, our method requires storing the communicated chunk of the numerator n, denominator d and max m . We do not pre-allocate an output tensor but instead just return the result of doing the Allreduce to the numerator divided by the Allreduced denominator. In summary we have the following peak memory costs for Ring and Tree attention:  $$\begin{array}{llll}\mbox{Mem}_{\rm ring}&=4btd+2bd&(29)\\ \mbox{Mem}_{\rm tree}&=2btd+2bd+2bn_{h},&(30)\end{array}$$  where d = d h × n h , for head size d h and n h number of heads, b denotes the batch size and t = N/p . As such, so long as 2 bn h ≤ 2 btd , which will almost always be the case in realistic scenarios, our method always has a lower peak memory cost compared to Ring Attention .  We empirically measure peak memory utilization for our approach and Ring Attention to show that indeed memory usage is significantly less for Tree Attention in Figure 4 . As predicted by theory, scaling hidden size or sequence length scales Ring Attention peak memory usage about 2x faster than Tree Attention . For example, doubling the hidden size from 2048 to 4096, doubles the gap in peak memory between two methods, going from 524MB to 1040MB. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Memory Cost
2408.04093
 For Ring Attention's P2P communication strategy, the total volume of data being communicated between devices (in units of number of tensor elements) per iteration is given by: Vring = 2btd × p (31) where p is the number of devices. The first factor comes from counting the total number of communicated elements  ![7_image_0.png](7_image_0.png)  corresponding to $\{(\mathbf{k}_{\hat{a}},\mathbf{v}_{\hat{a}}),\hat{a}=1,\cdots,t\}$, i.e., $${\mathrm{numel}}\left(\{(\mathbf{k}_{\hat{a}},\mathbf{v}_{\hat{a}}),{\hat{a}}=1,\cdots,t\}\right)=2b t d.$$ The Allreduce strategy we use in Tree Decoding requires the following volume [51]:  $$(32)^{\frac{1}{2}}$$  $$V_{\mathrm{All\,reduce}}=2\times{\frac{p-1}{p}}\times\mathrm{numel}.$$ $$(33)$$ $\left(34\right)^{2}$  We communicate a shard of the numerator, denominator and max, requiring: numel (n, d, ) =  + 2ℎ. (34) Note that we first perform on device the local reductions to obtain the local numerator and denominator on each device which consequently makes it so that , i.e. the size of the local sequence chunk doesn't appear in the above expression. We then obtain:  $$V_{T r e e}=2{\frac{p-1}{p}}\times(b d+2b n_{h})\;.$$ $$(35)$$  Our theoretical analysis shows that per iteration our algorithm maintains a lower communication volume than Ring Attention. Note however that Ring Attention when performed in the training setting with many queries overlaps communication and computation so as to hide it's communication costs. However, overlapping communication and computation in the decoding case is infeasible because of how fast the attention computation on a single GPU is relative to how long it takes to communicate the chunk of keys and values between two devices.  Concretely, let us take the example of decoding from a context of length 640000 split between 8 GPUs within one node. Let us take a hidden size of 2048 and fix our data type to be bfloat16. Each device for decoding takes (10−5) seconds to perform the Flash Attention computation. The time it takes to move the keys and values of the corresponding size between adjacent GPUs as per Fig. 2 is roughly (10−3) seconds. The latency incurred between nodes is even greater and therefore overlapping isn't feasible due to this disparity in timescales. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Communication Volume 6.3.
2408.04093
 In this paper, we have derived the energy function for self-attention and demonstrated how the computation of the derivative of this function provides a novel and efficient method for computing attention in parallel. This advantage is especially apparent when performing decoding across multiple devices, in which case our Tree Attention enables us to substantially outperform Ring Attention with an *asymptotically* superior algorithm, with ×8 speedups when we use 128 GPUs on a sequence length of 5.12M. We also see that the AllReduce operation that we use involves sending partially reduced objects, which greatly reduces the volume of communicated data as well as the peak memory requirement.  Our introduction of a unique energy function for selfattention develops interesting connections between attention and other related models such as Hopfield networks and the general notion of associative memories. Given this energy function, it is possible to mathematically analyze its loss landscape and dynamics, as well as begin to understand how the attention operation could potentially be improved. Additionally, since the energy function can be framed as a variational free energy, it becomes possible to interpret the attention operation through a Bayesian lens and understand the generative model that is implicit in its operation. We hope that these mathematical derivations aid research in understanding the properties of transformer networks, as a deep understanding of the Hopfield energy function has done for Hopfield networks.  Theoretical asymptotic improvements should be demonstrable in the single-device case, but in practice, this advantage is not realized. SMs in H100 and older architectures communicate through shared global memory, not in a peer-to-peer fashion like individual GPUs in a multi-device setup, making the reduced communication negligible. However, recent experimental instructions in the H100 have enabled peer-to-peer SM communication [52], suggesting that these instructions could lead to speedups over Flash Attention on a single device.  [1] D. Bahdanau, K. Cho, and Y. Bengio, arXiv preprint arXiv:1409.0473 (2014).  [2] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, Advances in neural information processing systems 30 (2017).  [3] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, *et al.*, Advances in neural information processing systems 33, 1877 (2020).  [4] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei, arXiv preprint arXiv:2001.08361 (2020).  [5] J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, A. Clark, *et al.*, arXiv preprint arXiv:2203.15556 (2022).  [6] G. Team, R. Anil, S. Borgeaud, Y. Wu, J.-B. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, et al., arXiv preprint arXiv:2312.11805 (2023).  [7] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, *et al.*, arXiv preprint arXiv:2303.08774 (2023).  [8] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, *et al.*, arXiv preprint arXiv:2010.11929 (2020).  [9] J. Betker, arXiv preprint arXiv:2305.07243 (2023).  [10] L. Chen, K. Lu, A. Rajeswaran, K. Lee, A. Grover, M. Laskin, P. Abbeel, A. Srinivas, and I. Mordatch, Advances in neural information processing systems 34, 15084 (2021).  [11] S. Reed, K. Zolna, E. Parisotto, S. G. Colmenarejo, A. Novikov, G. Barth-Maron, M. Gimenez, Y. Sulsky, J. Kay, J. T. Springenberg, *et al.*, arXiv preprint arXiv:2205.06175 (2022).  [12] S. Chen, S. Wong, L. Chen, and Y. Tian, arXiv preprint arXiv:2306.15595 (2023).  [13] "Things i'm learning while training superhot," (2023).  [14] B. Peng, J. Quesnelle, H. Fan, and E. Shippole, arXiv preprint arXiv:2309.00071 (2023).  [15] M. Reid, N. Savinov, D. Teplyashin, D. Lepikhin, T. Lillicrap, J.-b. Alayrac, R. Soricut, A. Lazaridou, O. Firat, J. Schrittwieser, *et al.*, arXiv preprint arXiv:2403.05530 (2024).  [16] J. Lee, A. Chen, Z. Dai, D. Dua, D. S. Sachan, M. Boratko, Y. Luan, S. M. Arnold, V. Perot, S. Dalmia, *et al.*, arXiv preprint arXiv:2406.13121 (2024).  [17] A. Bertsch, M. Ivgi, U. Alon, J. Berant, M. R. Gormley, and G. Neubig, arXiv preprint arXiv:2405.00200 (2024).  [18] C. Team, arXiv preprint arXiv:2405.09818 (2024).  [19] L. Xue, A. Barua, N. Constant, R. Al-Rfou, S. Narang, M. Kale, A. Roberts, and C. Raffel, Transactions of the Association for Computational Linguistics 10, 291 (2022).  [20] S. Wu, X. Tan, Z. Wang, R. Wang, X. Li, and M. Sun, arXiv preprint arXiv:2402.19155 (2024).  [21] A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret, in *International conference on machine learning* (PMLR, 2020) pp. 5156–5165.  [22] K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser, *et al.*, arXiv preprint arXiv:2009.14794 (2020).  [23] H. Peng, N. Pappas, D. Yogatama, R. Schwartz, N. A.  Smith, and L. Kong, arXiv preprint arXiv:2103.02143 (2021).  [24] S. Arora, S. Eyuboglu, M. Zhang, A. Timalsina, S. Alberti, D. Zinsley, J. Zou, A. Rudra, and C. Ré, arXiv preprint arXiv:2402.18668 (2024).  [25] A. Gu and T. Dao, arXiv preprint arXiv:2312.00752 (2023).  [26] T. Dao and A. Gu, arXiv preprint arXiv:2405.21060 (2024).  [27] T. Katsch, arXiv preprint arXiv:2311.01927 (2023).  [28] Y. Sun, L. Dong, S. Huang, S. Ma, Y. Xia, J. Xue, J. Wang, and F. Wei, arXiv preprint arXiv:2307.08621 (2023).  [29] P. Glorioso, Q. Anthony, Y. Tokpanov, J. Whittington, J. Pilault, A. Ibrahim, and B. Millidge, arXiv preprint arXiv:2405.16712 (2024).  [30] M. N. Rabe and C. Staats, arXiv e-prints , arXiv:2112.05682 (2021), arXiv:2112.05682 [cs.LG].  [31] T. Dao, D. Fu, S. Ermon, A. Rudra, and C. Ré, Advances in Neural Information Processing Systems 35, 16344 (2022).  [32] "Flash-decoding for long-context inference," (2024).  [33] Character AI, "Optimizing inference," (2024).  [34] H. Kang, Q. Zhang, S. Kundu, G. Jeong, Z. Liu, T. Krishna, and T. Zhao, "Gear: An efficient kv cache compression recipe for near-lossless generative inference of llm," (2024), arXiv:2403.05527 [cs.LG].  [35] A. Liu, J. Liu, Z. Pan, Y. He, G. Haffari, and B. Zhuang, "Minicache: Kv cache compression in depth dimension for large language models," (2024), arXiv:2405.14366 [cs.CL].  [36] P. Nawrot, A. Łańcucki, M. Chochowski, D. Tarjan, and E. M. Ponti, "Dynamic memory compression: Retrofitting llms for accelerated inference," (2024), arXiv:2403.09636 [cs.CL].  [37] H. Liu, M. Zaharia, and P. Abbeel, arXiv e-prints , arXiv:2310.01889 (2023), arXiv:2310.01889 [cs.CL].  [38] H. Ramsauer, B. Schäfl, J. Lehner, P. Seidl, M. Widrich, T. Adler, L. Gruber, M. Holzleitner, M. Pavlović, G. Kjetil Sandve, V. Greiff, D. Kreil, M. Kopp, G. Klambauer, J. Brandstetter, and S. Hochreiter, arXiv e-prints , arXiv:2008.02217 (2020), arXiv:2008.02217 [cs.NE].  [39] D. Krotov and J. J. Hopfield, Advances in neural information processing systems 29 (2016).  [40] D. Krotov, arXiv e-prints , arXiv:2107.06446 (2021), arXiv:2107.06446 [cs.NE].  [41] B. Millidge, T. Salvatori, Y. Song, T. Lukasiewicz, and R. Bogacz, in *International Conference on Machine Learning* (PMLR, 2022) pp. 15561–15583.  [42] B. Hoover, Y. Liang, B. Pham, R. Panda, H. Strobelt, D. H. Chau, M. J. Zaki, and D. Krotov, arXiv e-prints , arXiv:2302.07253 (2023), arXiv:2302.07253 [cs.LG].  [43] R. Singh and C. L. Buckley, arXiv preprint arXiv:2304.04556 (2023).  [44] L. Feng, F. Tung, H. Hajimirsadeghi, M. Osama Ahmed, Y. Bengio, and G. Mori, arXiv e-prints , arXiv:2405.13956 (2024), arXiv:2405.13956 [cs.LG].  [45] M. J. Beal, *Variational algorithms for approximate* Bayesian inference (University of London, University College London (United Kingdom), 2003). [46] Y. LeCun, S. Chopra, R. Hadsell, M. Ranzato, F. Huang, et al., Predicting structured data1 (2006).  [47] Y. Song and D. P. Kingma, arXiv preprint arXiv:2101.03288 (2021).  [48] Wikipedia, "Helmholtz free energy - Wikipedia, the free encyclopedia," http://en.wikipedia.org/w/ index.php?title=Helmholtz%20free%20energy&oldid= 1180032120 (2024), "[Online; accessed 31-July-2024]".  [49] T. Vieira, "Evaluating∇() is as fast as()," (2016), https://timvieira.github.io/blog/post/2016/09/ 25/evaluating-fx-is-as-fast-as-fx/.  [50] T. Dao, arXiv preprint arXiv:2307.08691 (2023).  [51] Q. Anthony, B. Michalowicz, L. X. J. Hatef, M. Abduljabbar, H. S. A. Shafi, and D. Panda (2024).  [52] NVIDIA, "Nvidia hopper architecture indepth," https://developer.nvidia.com/ blog/nvidia-hopper-architecture-in-depth/ \#distributed_shared_memory (2024), "Online; accessed 5-August-2024". 
conclusion
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Discussion And Conclusion
2408.04093
 We would like to thank Skye Wanderman-Milne for answering our questions on JAX multi-device programming and Anna Golubeva for proof-reading our manuscript.  We are also grateful to all those who contributed their expertise and support throughout the course of this work, including our colleagues at Zyphra and friends whose encouragement and insightful feedback were invaluable. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Acknowledgement
2408.04093
 Below is the *tree_flash_decode* method. Our full code base is available here: https://github.com/Zyphra/ tree_attention.  import jax from jax import lax import jax.numpy as jnp from functools import partial from jax.sharding import Mesh,NamedSharding, PartitionSpec as P from jax.experimental import mesh_utils from jax.experimental.shard_map import shard_map from flash_attn_jax.flash import _flash_mha_vjp @jax.jit @partial(shard_map, mesh=mesh, in_specs=(P(None, None, None, None), P(None, 'i', None, None), P(None, 'i', None, None)), out_specs=P(None, None, None), check_rep=False) def tree_flash_decode(q, k, v): def flash_num_lse(q, k, v, config=dict(softmax_scale=1.0, is_causal=False, window_size=(-1, -1))): tup = _flash_mha_vjp.fwd(q, k, v, config) res,lse = tup[1][3],tup[1][4] return res,lse loc_res, loc_lse = flash_num_lse(q, k, v) a_max_global = lax.pmax(loc_lse, axis_name='i') num_global = lax.psum(loc_res * jnp.exp(loc_lse - a_max_global), axis_name='i') den_global = lax.psum(jnp.exp(loc_lse - a_max_global), axis_name='i') return (num_global / den_global) The function uses Flash Attention 2 [50] to compute the local numerator and denominator, both of which are accumulated between devices using an Allreduce (which is what psum and pmax call). NCCL determines in what pattern these results are communicated. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Appendix: Jax Code
2408.04093
 We prove theorem 1 below. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
0. Theorem 1 Proof
2408.04093
 Sequential Case: On a single GPU, the reduction operation over an array of size  has a time complexity of () since the processor must sequentially process each element.  Parallel Processing with  Processors: Divide the array of size  into  chunks, each of size   . Each processor performs the reduction operation on its chunk independently. The time complexity for each processor is  .  Combining Partial Results: The partial results from the  processors need to be combined. Using a tree pattern for reduction, the partial results can be reduced in (log ) steps. Each step involves combining pairs of results, halving the number of results at each step until only one result remains.  Total Time Complexity: The total time complexity is the sum of the time complexities for processing the chunks and combining the results:  $$O\left({\frac{N}{p}}\right)+O(\log p).$$  This proves that the time complexity of a reduction involving an associative operation over an array of size is   + log when using  parallel processors, and it reduces to (log ) when the number of processors is equal to the size of the array. □  $$\begin{array}{l}{{=1\,.\,0\,,}}\\ {{\mathrm{ize}=\left(\,-1\,,\,\,\,-1\right)\,\}}\\ {{\mathrm{4,\,\,\,k\,,\,\,\,v\,,\,\,\,\,conf r}}}\end{array}$$ 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Proof.
2408.04093
 $i_{\star}$, v) While, mathematically, attention utilizes the softmax operation, in practice this is often numerically unstable using relatively low precision operations. To address this, a mathematically equivalent function, the 'safe softmax' is instead used which subtracts all dot products in the exponential by the max. This ensures that all values being exponentiated are less than 1 and hence less likely to explode and cause numerical instability. Here, we demonstrate that our energy function approach also can account for safe softmax.  Let us suppose we compare our generating function  $$F_{t o t}=\sum_{i}\log\sum_{a=1}^{i}\exp\left(q_{i}\cdot k_{a}^{T}+\xi_{a}\cdot v_{a}^{T}\right)\tag{36}$$  and a slightly modified one:  $$F_{t o t}^{\prime}=\sum_{i}\log\sum_{a=1}^{i}\exp\left(q_{i}\cdot k_{a}^{T}+\zeta_{i}\cdot v_{a}^{T}-m_{i}\right).\tag{37}$$  When we take the derivative of these two quantities, we see that we get the same result:  $$\left.\frac{\partial F_{t o t}}{\partial\zeta_{i}}\right|_{\zeta_{i}=0}=\left.\frac{\partial F_{t o t}^{\prime}}{\partial\zeta_{i}}\right|_{\zeta_{i}=0}.$$  . (38) To see it explicitly:  $$\left.{\frac{\partial F_{t o t}^{\prime}}{\partial\zeta_{i}}}\right|_{\zeta_{i}=0}={\frac{\sum_{a=1}^{i}\exp(q_{i}\cdot k_{a}^{T}-m_{i})v_{a}}{\sum_{a=1}^{i}\exp(q_{i}\cdot k_{a}^{T}-m_{i})}}$$   (39) $$={\frac{\sum_{a=1}^{i}\exp\left(q_{i}\cdot k_{a}^{T}\right)v_{a}}{\sum_{a=1}^{i}\exp\left(q_{i}\cdot k_{a}^{T}\right)}}.$$  Normally, when computing the softmax in an online fashion, this procedure is performed where is the row max of  ·   . This shift makes it so that the sum of exponentials doesn't lead to overflows. 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Computing Safe Softmax
2408.04093
 $$(38) $$  Here is a summary of the various variables and indices that will be used in the coming sections:  | 𝑥         | Attention Input                     | |------------|-------------------------------------| | 𝑞, 𝑘, 𝑣 | Query, key and value vectors        | | Γ          | Attention Log-likelihood            | | 𝜁         | Source vector                       | | 𝑚         | Max of 𝑞 · 𝑘 𝑇                   | | 𝑍         | Partition function                  | | 𝑧         | Activation vector                   | | n          | Attention numerator                 | | d          | Attention denominator               | | lse        | Attention score logsumexp           | | 𝐹         | Generating function                 | | 𝑃         | Attention score probability density |  $$(40) $$ $$(39) $$  | 𝑁                                | Sequence length     | |-----------------------------------|---------------------| | 𝑑                                | Embedding dimension | | 𝑑ℎ                               | Head dimension      | | 𝑝                                | Number of devices   | | 𝑡                                | Chunk size N/p      | | 𝑏                                | Batch size          | | 𝑎, 𝑖, 𝑗 ∈ {1, · · · , 𝑁}      | Sequence Indices    | | 𝐴, 𝐵 ∈ {1, · · · , 𝑑}          | Embedding indices   | | 𝐴, ¯ 𝐵¯ ∈ {1, · · · , 𝑑ℎ}      | Intra-head indices  | | ℎ ∈ {1, · · · , 𝑛ℎ}              | Head indices        | | 𝑎, ˆ 𝑏ˆ ∈ {1, · · · , 𝑡}       | Intra chunk indices | | TABLE II: Index names and ranges. |                     |  $$(41) $$ 
body
Tree Attention: Topology-Aware Decoding For Long-Context Attention On Gpu Clusters
Notations For Equations