A sparse-attention method from Zyphra that replaces the flat token indexer of DeepSeek-style sparse attention with a tree search over compressed summaries of the KV cache. Each query is routed top-down through the tree with top-p routing, so how much context it retrieves adapts to the query. Zyphra's argument is that indexers which score every past token (or every chunk at one resolution) only move the quadratic cost from attention into the indexer, while a hierarchical search can be subquadratic. It motivates this with a measurement on Qwen3.6-35B-A3B: the number of tokens holding a fixed share of attention mass grows as a sublinear power law in sequence length on long-form fiction.

ZHA is retrofitted rather than pretrained. A lightweight router is distilled from a frozen pretrained model with a KL objective on a few billion tokens at 32K context; on Qwen3.6-35B-A3B only the learned reference queries train, 81,920 parameters (about 0.00024% of the model). Zyphra says the deep router needed about a tenth of the 40B-token KL warm-up used for the MSA indexer it compares against. Reported results on Qwen3.6-35B-A3B: RULER-13 at 256K 96.2% for a wide tree against 96.0% dense and 77.1% for MSA (a deep six-level tree scores 93.3%); LongBench v2 63.4% against 58.0% dense while attending to about 1.1% of the KV cache, about 12.7 points above MSA at a similar attended fraction; SWE-bench Verified 67.4–68.4% against 67.4% dense. It also ran on Nemotron-3.5-Lightning-30B-A3B, whose NoPE attention held up on reasoning and agentic coding but lost more on RULER retrieval. Across 28 tree geometries, deeper trees often beat shallower ones at equal compression.

The speed claims are projected from a GPU roofline model, not measured, and the GPU is not named: a light configuration overtakes dense attention at about 48K tokens and MSA at about 480K, and the projection reaches 32–35× over dense and 4.7–5.1× over MSA at 10M tokens. Evaluations stop at 256K context. No code or kernels are linked from the post.

Paper

Authors: Leon Lufkin · Cutter Dawes · Alexander Speicher · Kamesh Krishnamurthy · Tomás Figliolia · Beren Millidge
attentionlong-contextefficiencyresearch

Related