Zyphra Research has published a paper on a way to make long-context attention cost grow slower than quadratic, without throwing away what a pretrained model already knows. The method is called Zyphra Hierarchical Attention (ZHA). The paper, "Subquadratic Attention with a Hierarchical Tree-Structured Indexer," was submitted to arXiv on October 30, 2026. Its authors are Leon Lufkin, Cutter Dawes, Alexander Speicher, Kamesh Krishnamurthy, Tomás Figliolia and Beren Millidge. You can read the abstract on arXiv and the HTML version.
The paper's abstract points to huge speedups at very long contexts. This post separates what the paper measured from what it modeled.
At a glance
| Question | Answer from the paper |
|---|---|
| Core idea | A tree of compressed key summaries over the KV cache. Queries descend top-down and fetch a sparse set of keys |
| Training | Frozen base model. Only reference queries are learned, via KL distillation |
| Training cost in tests | 4B tokens at 32K context |
| Models converted | 4B to 35B parameters, including Qwen3.6-35B-A3B and Nemotron-3.5-Lightning-30B-A3B |
| Extra parameters | About 0.00024% for Qwen3.6-35B-A3B with 16 reference queries |
| Measured quality | Within noise of dense on most tests; RULER-13 93.3% vs 96.0% for the deep router |
| Speedups | From a roofline performance model, not wall-clock measurements |
The problem ZHA targets
Attention compares every token with every earlier token. That makes prefill cost grow quadratically, and during decoding each new token must re-read the whole KV cache. The paper reviews the options and their limits:
- Fixed-state models such as state-space models and sliding windows cut cost but saturate at long contexts.
- Hybrids keep a few full-attention layers, which still dominate at very long lengths.
- Compression and eviction methods are brittle because it is hard to know in advance which token will matter later.
- Fine-grained sparse attention such as DeepSeek Sparse Attention (DSA) and MiniMax Sparse Attention (MSA) lets each query choose its own keys. But the indexer that scores every key is itself quadratic. The paper cites that around 1M tokens, 60% to 90% of time in these layers is still spent on indexing.
So sparse attention often yields only a constant-factor speedup. ZHA aims for a better growth rate by making the indexer hierarchical. For a related look at the indexer problem, see our coverage of Meituan's LongCat sparse attention models.
How the tree works
The authors start from an observation: for natural language, the set of keys that carries most of a query's attention (the "top-p set") grows as a sublinear power law with context length. A power law hints at hierarchical structure.
Building the tree. ZHA compresses each chunk of keys into a summary key, then compresses groups of summaries again, level after level. A summary is an attention-weighted sum of keys, computed with a small set of learned reference queries. The paper explains the compression as approximating a chunk's total attention mass with tangent planes. During decoding, a new summary is added whenever a full chunk completes. The authors say tree construction adds about 1% or less latency in their model.
Routing. A query starts at the top level, scores the nodes there, keeps the top-p nodes (those holding at least a fraction p of estimated attention mass), and descends into their children. At the bottom it reaches raw KV entries. The union of leaves goes to ordinary attention. The first token is always kept as an attention sink.
Top-p, not top-K. The selection size adapts. If a few nodes hold most of the mass, few are chosen. If attention is flat, more are chosen. The authors argue this helps the method extrapolate to lengths longer than those seen in training.
Training. The base model is frozen, including its own attention. Only the reference queries are trained, by matching predicted chunk probabilities to the true dense attention pooled into chunks at each level. The reported runs used 4B tokens at 32K context, even though the models were trained for 256K to 512K contexts.
What was measured
The main test converted Qwen3.6-35B-A3B with a deep router (chunk size 4, six levels) and a wide router (chunk size 256, one level), each with 16 reference queries, p values of 0.8, 0.9 and 0.95, and 4B training tokens.
- Both routers performed "within noise of the dense baseline" on reasoning, agentic coding and long-context benchmarks.
- The exception: RULER-13 for the deep router scored 93.3% against 96.0% for dense, a 3-point drop while attending to 1% to 6% of the original KV cache.
- Against MSA, trained on the same backbone with 40B tokens (ten times the budget), MSA stayed close on AIME 2026, MMLU-Pro and GPQA Diamond but fell well behind on long-context retrieval. On LongBench v2, where MSA's fixed budget is roughly 1% of context, the deep router attended to about 1.1% of decode keys and scored 14 points higher.
- Nemotron-3.5-Lightning-30B-A3B, which has no positional encoding, performed comparably on agentic coding but "suffers moderately" on RULER. The authors note it did not show as robust a power law as the partial-RoPE Qwen model.
A geometry sweep of 28 configurations on RULER at 64K, 128K and 256K found retrieval robust to tree shape when attending to 10% to 30% of keys. Deeper trees at fixed compression held up better at high sparsity, which the authors present as evidence that depth is not the limiting factor. They say, "to our knowledge," this is the first hierarchical attention variant to show convincing scaling beyond one level while staying close to dense. That is their claim and has not been independently checked.
They also fit a four-parameter model that predicts RULER accuracy from tree settings, with an RMSE of 1.44 percentage points on held-out lengths.
What was modeled, not measured
The abstract says the authors "develop a detailed performance model" and that the method "dramatically outperforms competing methods beyond 1 million context." The text says they model speedups against dense attention and MSA with a roofline model, and that the model predicts a crossover against MSA around 0.5M tokens for a geometry with p = 0.75.
Two cautions follow.
- A roofline model estimates speed from compute and memory limits. It is not a measured kernel running on a cluster. Real speed depends on kernel quality, memory layout and batching.
- The quality tests ran up to hundreds of thousands of tokens. Claims about tens of millions or billions of tokens are extrapolations. The paper itself says ZHA can stay subquadratic "subject to careful top-p scaling" and "theoretically" outperform other sparse methods at those lengths.
At 1B tokens, the paper's modeled ranges are roughly 373x to 417x faster than dense attention and 52x to 58x faster than MSA. The paper states these are modeled latencies, not measured ones, and that the authors have not validated performance at these context lengths. Treat them as projections until Zyphra publishes measured kernel benchmarks.
Why it matters for builders
If the quality results hold in other labs, ZHA would let teams convert an existing open model for long context with a small training run instead of a new pretraining. Context length is a cost driver for agents and coding tools, where histories grow quickly. Our posts on the DeepSeek DeepInfer inference engine and on Nemotron 3.5 Super VL show how much weight labs now put on serving cost at long context.
Still, a few gaps remain before anyone can plan around it:
- No public kernels found. We saw no released code or converted weights in the pages we read. Zyphra's earlier Tree Attention repo is a different, earlier project, so check for a new release.
- Retrieval risk. The RULER drop for the deep router and the Nemotron RULER decline show the method is not free at the margin.
- One main backbone. The detailed results center on Qwen3.6-35B-A3B. Larger or dense-architecture models are untested in the sections we read.
- Serving complexity. A tree that grows during decoding, with per-query top-p routing, needs custom kernels. The paper's own data on how many keys are attended (10% to 30% for robust retrieval) hints at how sparse real use can be.
What "subquadratic but superlinear" means
The arXiv abstract uses a precise phrase: total cost grows "subquadratic (but superlinear)" with sequence length. That wording matters. ZHA does not promise linear cost, as fixed-state models do. It promises a growth rate between linear and quadratic. The authors say this holds as tree depth grows, and that it covers both routing and the final attention step.
This is the trade the paper chooses. Fixed-state models and sliding windows reach linear cost, but they give up the ability to look up any earlier token. Full dense attention keeps that ability at quadratic cost. ZHA tries to keep fine-grained lookup and still lower the growth rate. The abstract also says the approach "has the potential" to extend effective context windows to hundreds of millions or billions of tokens. The word "potential" is the authors' own hedge, and it fits the modeled status of those numbers.
The abstract names three further claims. First, a short KL distillation stage over a few billion tokens is enough to convert an existing model. Second, performance holds on long-context retrieval, reasoning, math and agentic coding tasks. Third, the method is robust to tree geometry, with trees up to six levels deep. The abstract does not list limitations. Based on the body, the open points are the distillation stage itself, the RULER drop for the deep router and the lack of measured kernels.
How to read this paper
Start with Figure 5 for the quality comparison, Figure 6 for geometry, and the performance-model section for the speed claims. Check the appendix on Nemotron if you care about models without positional encodings. When you see a headline multiplier, ask whether it is a measured latency or a model output.
Bottom line
ZHA is a serious attempt at a hard problem: making the indexer, not just the attention, scale well. The measured results on a 35B mixture-of-experts model are encouraging, especially against MSA on long-context retrieval. The giant speedups are projections. Wait for open kernels and third-party benchmarks before treating them as facts.