Subquadratic Attention with a Hierarchical Tree-Structured Indexer
| Source: arXiv AI
Tags: Zyphra, Zyphra Hierarchical Attention, sparse attention, KV cache, KL distillation, long context
Zyphra researchers present ZHA, a tree-structured sparse attention indexer with overall subquadratic cost that can be retrofitted onto pretrained LLMs via short distillation and targets context windows far beyond 1 million tokens.
Details
Attention's quadratic cost limits long-context LLMs. Prior fixes either lose expressiveness (sliding-window or fixed-state linear attention) or give only constant-factor speedups because their sparse indexers still scale quadratically. The authors, including Beren Millidge and Tomas Figliolia, propose Zyphra Hierarchical Attention (ZHA). It builds a tree of recursively compressed key summaries over the KV cache that queries traverse top-down to fetch a sparse set of keys. Growing tree depth keeps routing plus attention cost sublinear per query, giving subquadratic but superlinear scaling overall. ZHA is applied to existing pretrained models with a short KL distillation stage over a few billion tokens and keeps performance on long-context retrieval, reasoning, math and agentic coding evaluations. It stays robust with trees up to 6 levels deep. A performance model indicates it outperforms competing methods beyond 1 million tokens, with potential to reach hundreds of millions of tokens.