Summary (Overview)

• FreeSolo introduces a native sparse attention mechanism designed for zero-shot length extrapolation, combining a short-range sliding window with a long-range sparse branch that selects keypoint cells for direct token attention.
• Two main variants are developed: FS-L (linear-time, $O(N)$) which prunes the prefix before query-dependent selection through short continued pretraining (CPT), and FS-B (subquadratic, $O(N \log^2 N)$) which searches balanced trees over a growing archive.
• Both variants demonstrate superior zero-shot extrapolation: at 800M parameters, RULER mean decreases only from 32.0 to 22.3 (FS-L) and 37.7 to 30.4 (FS-B) when extrapolating from 4k to 16k training length.
• Both models retrieve single needles at 256k context length—64× the training length—without any long-context fine-tuning.
• FS-B achieves the highest RULER mean in the superlinear group at 4k and beyond, while FS-L leads the linear group at every reported length.

---

Introduction and Theoretical Foundation

Background and Motivation

Long-context language modeling requires both efficient attention and reliable retrieval beyond training length. Traditional approaches face fundamental trade-offs:

• Full attention (Vaswani et al., 2017) has quadratic sequence cost $O(N^2)$.
• Recurrent models (Katharopoulos et al., 2020; Gu and Dao, 2023) compress history into fixed-size states, limiting how much information can be stored.
• Hybrid architectures that add full attention for better recall incur quadratic cost.
• Native Sparse Attention (NSA) (Yuan et al., 2025) and Mixture of Block Attention (MoBA) (Lu et al., 2025) preserve token access but score growing sets of blocks.

Neither compression nor sparsity alone ensures length extrapolation. Continued pretraining (CPT) on longer sequences can extend retrieval but at additional training cost.

Theoretical Foundation

The core insight of FreeSolo is that memory summaries need only locate evidence; the evidence can remain in original token values. The model learns token keys whose simple statistics make memory searchable, prunable, and hierarchically summarizable:

• Mean keys give a simple chunk representation for routing and hierarchical search.
• Maximum token-key norms provide pruning priorities.

Key architectural principle: RoPE (Su et al., 2021) stays within a fixed local window, while long-range routing and readout use unrotated queries and keys, avoiding unseen rotary offsets that cause extrapolation failures.

---

Methodology

3.1 Range Separation

FreeSolo combines local window attention with sparse long-range attention in each head. The local branch applies RoPE within a fixed window; the long-range branch selects top-K cells and applies NoPE attention to their tokens.

The outputs are combined as:

$$\mathbf{o}_i = \mathbf{o}_i^{\mathrm{sr}} + \alpha_h \mathbf{o}_i^{\mathrm{lr}}, \tag{2}$$

where $\alpha_h$ is a learned per-head scalar.

3.2 Local Branch

The local branch uses RoPE within a fixed look-back radius $w = 512$:

$$\ell_{ij}^{\mathrm{sr}} = \frac{(\mathbf{R}(i)\mathbf{q}_i)^{\top}(\mathbf{R}(j)\mathbf{k}_j)}{\sqrt{d}} = \frac{\mathbf{q}_i^{\top}\mathbf{R}(j-i)\mathbf{k}_j}{\sqrt{d}}, \tag{3}$$

with the readout:

$$(\mathbf{o}_i^{\mathrm{sr}})^{\top} = \mathrm{softmax}(\boldsymbol{\ell}_{i,\mathcal{L}_i}^{\mathrm{sr}})^{\top} \mathbf{V}_{\mathcal{L}_i}. \tag{4}$$

3.3 Long-Range Branch

Cells are groups of $s = 32$ consecutive token key/value pairs with summaries:

$$\bar{\mathbf{k}}_c = \frac{1}{s}\sum_{j \in \mathcal{I}_c} \mathbf{k}_j, \qquad p_c = (c + \frac{1}{2})s, \qquad a_c = \max_{j \in \mathcal{I}_c} \|\mathbf{k}_j\|_2. \tag{5}$$

Cell scoring combines mean-key content routing with a norm-weighted relative position bias:

$$r_{ic} = \frac{\mathbf{q}_i^{\top}\bar{\mathbf{k}}_c}{\sqrt{d}} + \lambda_h a_c g_h(i - p_c), \qquad c \in \mathcal{C}_i, \tag{7}$$

where $g_h(\Delta) = \mathrm{erf}(\Delta / (2\sigma_h))$, $\sigma_h > 0$, and $\lambda_h \geq 0$.

Query-independent pruning (FS-L) retains the $W$ most recent cells and the $P$ cells with largest norm priorities:

$$\mathcal{A}_i = \mathrm{Recent}_W(\mathcal{C}_i) \cup \mathrm{TopP}_{c \in \mathcal{C}_i}(a_c), \quad |\mathcal{A}_i| \leq W + P. \tag{8}$$

Token readout applies NoPE attention over selected cells:

$$\mathbf{u}_i^{\top} = \mathrm{softmax}(\boldsymbol{\ell}_{i,\mathcal{S}_i})^{\top} \mathbf{V}_{\mathcal{S}_i}, \qquad \mathbf{o}_i^{\mathrm{lr}} = \mathrm{RMSNorm}(\mathbf{u}_i). \tag{9}$$

3.4 Balanced Tree Search (FS-B)

FS-B uses two causal forests per head with admitted sets:

$$\mathcal{A}_i^0 = \mathcal{C}_i, \qquad \mathcal{A}_i^{\tau} = \{c \in \mathcal{C}_i: a_c \geq \tau_{\ell h}\}, \tag{10}$$

with beam search ranking nodes by:

$$U_v = \frac{\mathbf{q}_i^{\top}\boldsymbol{\mu}_v + c\|\mathbf{q}_i\|_2\rho_v}{\sqrt{d}} + \lambda_h A_v g_h(i - p_v^{\min}). \tag{11}$$

Token-level reranking rescues individual useful tokens hidden by mean keys:

$$\tilde{r}_{ic} = \log \sum_{j \in \mathcal{I}_c} \exp\left(\frac{\mathbf{q}_i^{\top}\mathbf{k}_j}{\sqrt{d}}\right) + \lambda_h a_c g_h(i - p_c). \tag{12}$$

Retrieval-weighted CPT uses a weighted next-token loss:

$$\mathcal{L} = -\frac{\sum_t w_t \log p_\theta(x_{t+1} \mid x_{\leq t})}{\sum_t w_t}, \qquad w_t = 1 + \beta f_t + \beta_{\mathrm{sw}}\chi_t. \tag{13}$$

3.5 Computational Cost

---

Empirical Validation / Results

RULER Extrapolation Results (Table 1, Key Results)

At 800M scale, 16k context (4× training length):

At 340M scale, 16k context:

Key Findings

• Single-needle retrieval at 256k: FS and FS-L score 96/85 at 800M, compared to zero for NAtS-L; Raven scores 92.
• FS-L trades some S-NIAH-1 recall for higher S-NIAH-2/3 scores at 16k–64k relative to base FS.
• FS-B's two-forest search significantly improves retrieval: at 800M/16k scores 100/88/84 on S-NIAH-1/2/3.
• On MK-NIAH-1, FS-L scores 23 vs. 3 for both linear baselines; on MV-NIAH, 17 vs. 9/0.5.

Short-Context Quality (Table 2)

At 340M, FS averages 51.9 and FS-L 51.0, compared with 51.8 for TF++ and 51.4 for Raven. At 800M, FS reaches 56.5 (close to TF++'s 56.8), while FS-L reaches 55.2. Both FS-L checkpoints retain similar short-context quality after CPT.

Empirical Scaling

• FS-L's attention buffers remain constant: 766 MiB (340M model) and 1149 MiB (800M model) from 4k to 256k context.
• CUDA-graph decoding runs at ~89 and ~75 tokens/s respectively.
• Prefill throughput stays near 2.1–2.2K tokens/s, with processing time growing approximately linearly.

---

Theoretical and Practical Implications

Information-Bottleneck View

The paper analyzes length generalization through an information-bottleneck perspective:

• FS routes through cell summaries: The router identifies useful cells from mean keys and maximum key norms; token attention then reads the selected cells' original keys and values.
• FS-L adds a second bottleneck: Cells are discarded before queries arrive, which works when useful information remains concentrated in the retained state but fails for dense, independently queryable facts.
• CPT adapts the model to restricted access: At 340M/4k, CPT recovers S-NIAH-1 from 62 (immediate pruning) to 76–90 across runs.

Position Independence

The design avoids positional extrapolation failures:

• RoPE only within trained local offsets
• NoPE for long-range token attention
• The erf prior depends only on relative offsets, so shifting tokens, cells, and query blocks together preserves the operator

Practical Implications

1. Separates memory capacity from read bandwidth: FS-L's pruning rule (high-norm cells + recent cells) decouples how much can be stored from how much a query reads.
2. Short CPT suffices: Only ~5% of pretraining tokens are needed for CPT (0.73B/1.57B at 340M/800M), all at 4k context—no long-context training required.
3. Bounded memory: FS-L's streaming cache keeps $O((P+W)s + w + B + s)d$ token state per head, independent of sequence length.

---

Conclusion

Main Takeaways

FreeSolo's central thesis is that memory summaries need only locate evidence; the evidence can remain in original token values. Mean summaries of learned token keys support hierarchical search, maximum token-key norms support pruning, and local-only RoPE keeps distant retrieval free of unseen rotary offsets.

The two variants demonstrate how this representation supports different memory regimes:

• FS-L: bounded memory with linear-time attention after short CPT
• FS-B: growing archive with subquadratic search using balanced trees

Both achieve zero-shot retrieval at 16k and single-needle recall at 256k from 4k training, separating the problem of learning useful memory keys from choosing capacity, search effort, and read bandwidth.

Limitations and Future Directions

• Experiments stop at 800M scale; larger-scale validation is needed.
• FS-L's fixed retention budget can discard evidence before a query arrives; finding a CPT objective that improves the suite mean within the memory budget remains open.
• FS-B trails Raven-full on 800M multi-query and multi-value retrieval tasks.
• Learning the search policy (rather than using a fixed inference algorithm) is a promising direction.
• Faster kernels for pruning, gathering, and sparse readout are future work—training at 340M/4k is slower than full attention (98.4K vs. 303K tokens/s across eight GPUs).