Metraipolis › archive › dc_dff09c8edd50

Subquadratic Attention with a Hierarchical Tree-Structured Indexer — arXiv:2610.42112

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.42112
License (as archived): CC0-1.0
Archived: 2026-11-02T07:40:55.625Z
SHA-256 of the archived text: 59baa48ecc365d355736d20a214cec92e6a0696de4bbb9594df723b1d8199a80
Stable URL of this page: https://metraipolis.com/documento/dc_dff09c8edd50

How to cite

Subquadratic Attention with a Hierarchical Tree-Structured Indexer — arXiv:2610.42112 — arXiv (en), https://arxiv.org/abs/2610.42112 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dff09c8edd50 (Metraipolis archive dc_dff09c8edd50, sha256 59baa48ecc365d355736d20a214cec92e6a0696de4bbb9594df723b1d8199a80)

BibTeX

@misc{dcdff09c8edd50,
  title = {Subquadratic Attention with a Hierarchical Tree-Structured Indexer — arXiv:2610.42112},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42112},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dff09c8edd50; sha256 59baa48ecc365d355736d20a214cec92e6a0696de4bbb9594df723b1d8199a80},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42112. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The quadratic scaling of attention is a fundamental bottleneck limiting the long-context capabilities of large language models (LLMs). A variety of approaches have attempted to circumvent this, but they either fail to match attention's expressiveness (e.g., sliding-window or linear attention variants with fixed-size state) or only achieve constant-factor speedups (e.g., sparse attention methods whose indexers themselves scale quadratically). In this paper, we derive an asymptotically subquadratic sparse attention method based on a hierarchical, tree-structured indexer, which we call Zyphra Hierarchical Attention (ZHA). ZHA constructs a tree of recursively compressed key summaries over the KV cache, which future queries traverse from the top down to retrieve a sparse subset of keys. Crucially, by iteratively growing the tree's depth, the total cost including routing and final attention grows sublinearly in sequence length, resulting in overall subquadratic (but superlinear) scaling for attention. We demonstrate that ZHA can be cheaply applied to existing pretrained models with only a short KL distillation training stage over a few billion tokens, and maintains performance on long-context retrieval and challenging reasoning, mathematical, and agentic coding evaluation tasks. Moreover, we show that our method is highly robust to tree geometry including very deep trees of up to 6 levels. Finally, we develop a detailed performance model and show that our approach scales subquadratically, dramatically outperforms competing methods beyond 1 million context, and ultimately has the potential to extend effective context windows to the hundreds of millions or billions of tokens.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Computation and Language (cs.CL) ; Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2610.42112 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:37:00.604Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).