Nested Sparsity for Scalable Pretraining and Continual Learning

Tianzhe Chu, Druv Pai, Yi MaarXiv 2026 · arXiv

TL;DR

NESTOR (Nested Sparse Transformer) is a novel architecture that extends the "mixture-of-experts" (MoE) concept to the attention operator. By hierarchically nesting sparse attention and sparse MLP layers, NESTOR achieves significantly better compute efficiency during pretraining and demonstrates a remarkable ability to learn new domains or longer contexts without the "catastrophic forgetting" that plagues traditional models.

What Problem Does This Paper Address?

Modern Large Language Models (LLMs) rely heavily on conditional computation via Mixture-of-Experts (MoE) layers to scale efficiently. However, in standard MoE transformers, this sparsity is lopsided: while the MLP (Multi-Layer Perceptron) layers are sparse, the attention mechanism remains "dense." Every token is processed by the same attention parameters, and as context lengths grow, the quadratic cost of attention becomes a massive bottleneck.

Furthermore, LLMs struggle with continual learning. When you fine-tune a model on a new domain (like legal documents or code) or extend its context window, it often "forgets" its original pretraining knowledge. The authors of NESTOR argue that this is partly because the shared attention parameters are constantly being overwritten, leading to interference between different types of data.

Methods

The core innovation is Nested Sparsity. Instead of a single global attention mechanism, NESTOR organizes layers into blocks containing multiple "columns."

  1. Column-Routed Attention: A router assigns each token to a small subset of available columns ($K_c$ out of $C$). Each column has its own unique attention parameters. This means tokens only attend to other tokens routed to the same column, naturally sparsifying the attention map.
  2. Hierarchical Experts: Within each column, there is a second level of routing to specific MLP experts. Because the experts are "nested" within columns, the model can develop highly specialized sub-networks for different data distributions.
  3. Sparsity Schedule: The model uses a "local-to-global" approach. In early layers, tokens are routed to very few columns (highly sparse/local), while in later layers, more columns become active, eventually converging to full global attention in the final block.
Figure 1: Nested sparsity in NESTOR. (a) The NESTOR architecture. In each block, the column router sends the token xj to Kc = 2 of the C = 4 columns. Each column has M layers, each with its own attention and its own E = 4 experts, of which a per-layer expert router selects Ke = 2. The token uses only the colored parameters. (b) The causal attention map computed by each column for S = 8 tokens, shown in terms of the whole sequence: column c computes attention only among the tokens Uc routed to it.

Datasets

The authors evaluated NESTOR across several scales (100M to 1B active parameters) using:

  • Pretraining: The DCLM-baseline dataset, a high-quality subset of Common Crawl.
  • Domain Adaptation: Four specialized target domains: PG-19 (Books), OpenWebMath (Mathematics), AlgebraicStack (Code), and FineWeb-2 (German).
  • Context Extension: Long-document subsets of DCLM-baseline to test context windows from 4k up to 64k tokens.

Key Insights and Ideas

  • Mirroring Data Structure: The authors hypothesize that natural language has a hierarchical latent structure (e.g., a document has a "topic" and then specific "concepts"). NESTOR’s nested routing (Column -> Expert) is designed to mirror this hierarchy.
  • Parameter vs. Map Sparsity: Unlike "sparse attention" methods that just mask the attention matrix, NESTOR provides parameter sparsity. Different tokens literally use different weights for their attention calculations.
  • Stability in Routing: Interestingly, the authors found that column routing is extremely stable across different domains. This stability acts as a "buffer," allowing the model to adapt to new information in the experts without disrupting the fundamental way it relates tokens in the attention layers.

Key Results

  • Superior Scaling: NESTOR is consistently more compute-efficient than both dense and MoE baselines. At the 1B parameter scale, a standard MoE would require 1.22x more compute, and a dense transformer would require 4.1x more compute to reach the same loss as NESTOR.
Scaling laws showing NESTOR reaching lower held-out loss than MoE and Dense baselines at every compute budget.
  • Reduced Forgetting: In domain adaptation tasks, NESTOR adapted as well as the baselines but forgot significantly less. On average, NESTOR forgot 3% less than the MoE baseline and 21% less than the dense model.
Figure 3: Domain adaptation and forgetting relative to the MoE transformer. Top: reduction in held-out loss on the target corpus. Bottom: increase in held-out loss on the pretraining corpus. Both are measured relative to each model before adaptation and shown as a percentage of the MoE transformer’s value.
  • Long Context Efficiency: Because NESTOR only computes attention within columns, its FLOPs per token decrease relative to baselines as the context length grows. This allows it to train on more tokens for the same compute budget, leading to much better performance on long-context tasks.

Limitations and Future Work

While promising, the study has a few bounds:

  • Maximum Scale: The experiments topped out at 1B active parameters. While the scaling laws look favorable, the "real-world" test of 100B+ parameter models remains for future work.
  • Meta-Architecture Potential: NESTOR is described as a "meta-architecture." In this paper, each column used standard causal attention. Future iterations could use even more efficient operators (like linear attention or state-space models) within the columns to further push the efficiency envelope.
  • Downstream Benchmarks: The evaluation focused on "held-out loss" (perplexity). While loss is a great proxy for model quality, testing on specific reasoning or coding benchmarks after post-training is a necessary next step.

Summary updated

Abstract

Mixture-of-experts (MoE) transformers, the standard backbone for modern large-scale deep learning, employ conditional computation: only a sparse subset of model weights is used in each forward pass. In MoE transformers, this sparsity arises in the MoE operator, which generalizes the multi-layer perceptron in the classical transformer. In this work, we explore an alternative mechanism for conditional computation that analogously generalizes the attention operator. The sparsity induced by this mechanism naturally nests (i.e., hierarchically composes) with the sparsity induced by the MoE operator. We show that a transformer employing this nested sparsity mechanism, which we call Nestor, performs better than a conventional MoE transformer at equal compute and equal sparsity in language model pretraining. We also show that Nestor is well-suited for continual pretraining: it can be adapted to longer contexts more effectively than conventional MoEs, as well as adapt more efficiently to new domains while forgetting less on old domains. Furthermore, we demonstrate that these benefits persist as model size, dataset size, and context length grow. Our results demonstrate the potential of alternative conditional computation mechanisms for deep neural network architectures. Code and checkpoints are available on GitHub at https://github.com/Ma-Lab-Berkeley/Nestor .
BibTeX
@misc{chu2026nested,
  author = {Tianzhe Chu and Druv Pai and Yi Ma},
  title = {{Nested Sparsity for Scalable Pretraining and Continual Learning}},
  year = {2026},
  eprint = {2610.31818},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31818},
}
Figure