# Toaster: Nonlinear Memory from Cascaded Linear Memories and Target Propagation

> TOASTER achieves nonlinear-memory quality at near-linear-memory speed by converting a two-layer recurrent memory into cascaded delta-rule kernels via target propagation, outperforming KDA across all scales.

- **Source:** [arXiv](https://arxiv.org/abs/2611.23648)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/3kO0Gq
- **Whiteboard:** https://picx.dev/p/3kO0Gq/image

## Summary

## Summary (Overview)

- **TOASTER** is a novel recurrent memory architecture that bridges linear memories (e.g., DeltaNet, KDA) and deep nonlinear memories (e.g., TTT-MLP, Titans) by cascading two linear memories with a pointwise activation between them.
- The key insight is that a gradient step on a linear layer is a delta-rule write, enabling **target propagation** to convert the hidden layer's training into an unmodified delta-rule kernel problem.
- TOASTER achieves **exact WY-form chunkwise parallelism per layer** (given cross-layer signals approximated once per chunk), combining the training efficiency of linear memories with the expressivity of nonlinear memories.
- Across a scaling ladder (0.2B–1.6B non-embedding parameters), TOASTER achieves **lower perplexity than KDA** on both C4 and PG19 at all five sizes, and matches or slightly improves on softmax attention on C4.
- In a 3:1 hybrid with global attention at 1.2B, TOASTER achieves the **lowest perplexity among four hybrids tested** (0.18 below attention on C4, 0.44 on PG19) and the **highest mean three-shot accuracy** (52.11%) on 13 downstream tasks.

---

## Introduction and Theoretical Foundation

### Background: Two Families of Recurrent Memory

Recurrent memories process long sequences with a fixed-size state, replacing or supplementing softmax attention (Vaswani et al., 2017) whose key-value cache grows with context. Two design questions separate memory architectures:

1. **How much of the past** can be packed into a given number of state parameters?
2. **How cheaply** can it be trained?

### Linear Memory and the WY Representation

A linear memory stores a matrix $\mathbf{S}_t \in \mathbb{R}^{d_k \times d_v}$, reads with $o_t = \mathbf{S}_t^\top q_t$, and writes via a gradient step on the reconstruction loss:

$$\mathcal{L}_t(\mathbf{S}) = \frac{1}{2}\|\mathbf{S}^\top k_t - v_t\|^2$$

with step size $\beta_t \in (0, 1]$ and optional forget gate $\alpha_t$:

$$\mathbf{S}_t = \alpha_t\left(\mathbf{I} - \beta_t \boldsymbol{k}_t \boldsymbol{k}_t^\top\right)\mathbf{S}_{t-1} + \beta_t \boldsymbol{k}_t \boldsymbol{v}_t^\top. \tag{1}$$

The factor $\mathbf{I} - \beta_t \boldsymbol{k}_t \boldsymbol{k}_t^\top$ is a **generalized Householder matrix**. Over a chunk of $C$ tokens, the product of $C$ such factors has the compact **WY form** $\mathbf{I} - \sum_{r=1}^{C} k_r \boldsymbol{w}_r^\top$, enabling exact chunkwise parallel training via a few dense matrix multiplications. The chunkwise kernel is written as:

$$\left(\mathbf{S}_{[j+1]}, \mathbf{O}_{[j]}\right) = \text{LINMEM}\left(\mathbf{S}_{[j]}; \mathbf{K}_{[j]}, \mathbf{V}_{[j]}, \mathbf{Q}_{[j]}\right). \tag{2}$$

**Limitation**: A linear memory represents only a single linear map $k \mapsto \mathbf{S}^\top k$ with $d_k d_v$ numbers.

### Deep Memory and the Loss of WY Form

Test-time-training memories (Sun et al., 2025; Behrouz et al., 2025b) replace the matrix with a neural network $\mathcal{M}(\cdot; \mathcal{W}_t)$, typically a two-layer MLP, updated by gradient descent. The stored map is nonlinear and more expressive, but the gradient update passes through the activation and is **not affine in the state**, so no WY form exists. Training falls back to mini-batch gradient descent evaluated at a stale chunk-initial state:

$$\mathcal{W}_{[j+1]} = \alpha_{[j]} \mathcal{W}_{[j]} - \sum_{r=1}^{C} \beta_{[j],r} \nabla_{\mathcal{W}} \mathcal{L}_{[j],r}(\mathcal{W}_{[j]}), \tag{3}$$

which is only accurate for small chunks and leaves accelerators mostly idle.

---

## Methodology

### 3.1 Cascade of Linear Memories

TOASTER keeps two matrix states, $\mathbf{S}_t^{(1)} \in \mathbb{R}^{d_k \times d_h}$ and $\mathbf{S}_t^{(2)} \in \mathbb{R}^{d_h \times d_v}$, each governed by a gated delta-rule recurrence (Eq. 1). A key $\boldsymbol{k}_t$ passes through the cascade:

$$\boldsymbol{z}_t = \mathbf{S}_{t-1}^{(1)\top} \boldsymbol{k}_t, \qquad \boldsymbol{h}_t = \sigma(\boldsymbol{z}_t), \qquad \hat{\boldsymbol{v}}_t = \mathbf{S}_{t-1}^{(2)\top} \boldsymbol{h}_t. \tag{4}$$

The composite map $k \mapsto \mathbf{S}^{(2)\top}\sigma(\mathbf{S}^{(1)\top}k)$ is a two-layer MLP—the same kind of deep memory used by TTT-MLP and Titans.

### 3.2 Target Propagation Makes Every Layer a Linear Memory

The output layer $\mathbf{S}^{(2)}$ is already a linear-memory problem: the delta rule with key $h_t$ and value $v_t$ is exactly a gradient step on $\mathcal{L}_t$ with respect to $\mathbf{S}^{(2)}$.

For the hidden layer, **target propagation** (Bengio, 2014; Lee et al., 2015) introduces a target $\tilde{\boldsymbol{v}}_t \in \mathbb{R}^{d_h}$ with local loss $\mathcal{L}_t^{(1)} = \frac{1}{2}\|z_t - \tilde{v}_t\|^2$. Equating the local gradient with the true gradient $\nabla_{z_t}\mathcal{L}_t = (\mathbf{S}_{t-1}^{(2)} \boldsymbol{e}_t) \odot \sigma'(z_t)$ yields the **exact target**:

$$\boxed{\tilde{\boldsymbol{v}}_t = \boldsymbol{z}_t - \left(\mathbf{S}_{t-1}^{(2)} \boldsymbol{e}_t\right) \odot \sigma'(\boldsymbol{z}_t), \quad \boldsymbol{e}_t = \hat{\boldsymbol{v}}_t - \boldsymbol{v}_t.} \tag{5}$$

**Remark 1 (Per-token equivalence)**: With scalar step sizes, no forgetting, and the exact target, updating $\mathbf{S}^{(1)}$ by Eq. (1) with $(k_t, \tilde{v}_t)$ and $\mathbf{S}^{(2)}$ by Eq. (1) with $(h_t, v_t)$ is **identical to one step of gradient descent** on $\mathcal{L}_t(\mathbf{S}^{(1)}, \mathbf{S}^{(2)})$ evaluated at $(\mathbf{S}_{t-1}^{(1)}, \mathbf{S}_{t-1}^{(2)})$.

### 3.3 Chunkwise-Parallel Training (Algorithm 1)

**Phase I** computes cross-layer signals at frozen chunk-initial states (all rows in parallel):
- Hidden pre-activations: $\mathbf{Z}_{[j]} = \mathbf{K}_{[j]} \mathbf{S}_{[j]}^{(1)}$
- Hidden keys: $\mathbf{H}_{[j]} = \sigma(\mathbf{Z}_{[j]})$
- Output errors: $\mathbf{E}_{[j]} = \mathbf{H}_{[j]} \mathbf{S}_{[j]}^{(2)} - \mathbf{V}_{[j]}$
- Hidden targets: $\widetilde{\mathbf{V}}_{[j]} = \mathbf{Z}_{[j]} - \mathcal{N}(\mathbf{E}_{[j]} \mathbf{S}_{[j]}^{(2)\top}) \odot \sigma'(\mathbf{Z}_{[j]})$

**Phase II** advances the hidden memory (two options):
- (a) WY kernel: $(\mathbf{S}_{[j+1]}^{(1)}, \mathbf{Z}_{[j]}^q) \leftarrow \text{LINMEM}(\mathbf{S}_{[j]}^{(1)}; \mathbf{K}_{[j]}, \widetilde{\mathbf{V}}_{[j]}, \mathbf{Q}_{[j]})$
- (b) **Apply-then-update (default)**: $\mathbf{Z}_{[j]}^q \leftarrow \mathbf{Q}_{[j]} \mathbf{S}_{[j]}^{(1)}$; $\mathbf{S}_{[j+1]}^{(1)} \leftarrow \mathbf{S}_{[j]}^{(1)} - \mathbf{K}_{[j]}^\top \text{Diag}(\boldsymbol{\beta}^{(1)}) \mathbf{G}_{[j]}$

**Phase III** advances the output memory with one LINMEM call using hidden keys $\mathbf{H}_{[j]}$, values $\mathbf{V}_{[j]}$, and queries $\sigma(\mathbf{Z}_{[j]}^q)$.

### 3.4 Design Choices for Stability and Speed

1. **Bias through homogeneous coordinates**: A constant input coordinate is appended ($\bar{\mathbf{k}}_t = [k_t; 1]$, $\bar{\mathbf{h}}_t = [h_t; 1]$) to prevent hidden-unit collapse at zero pre-activations.

2. **Bounded, rescaled back-projected error**: The back-projected error passes through a bounded pointwise normalization:

$$\tilde{\boldsymbol{v}}_t = \boldsymbol{z}_t - \mathcal{N}(\mathbf{S}_{t-1}^{(2)} \boldsymbol{e}_t) \odot \sigma'(\boldsymbol{z}_t), \qquad \mathcal{N}(x) = \gamma\,\text{softsign}(x) = \frac{\gamma x}{1 + |x|}, \tag{6}$$

with fixed scale $\gamma = 0.01$. This prevents target-scale drift from the compounding norm of the transporting matrix $\mathbf{S}^{(2)}$.

3. **Apply-then-update for the hidden memory**: Queries read the chunk-initial state; writes take effect at chunk end. Trade-off of 0.05 perplexity (15.69 vs. 15.64 with WY kernel) for 1.3–1.4× faster training.

---

## Empirical Validation / Results

### Language Modeling Across Scales (Table 2)

| Model | C4 145M | C4 300M | C4 550M | C4 850M | C4 1.2B | PG19 145M | PG19 1.2B |
|-------|---------|---------|---------|---------|---------|------------|-----------|
| Attention | 15.92 | 13.52 | 11.94 | 10.78 | 9.96 | 22.41 | 13.19 |
| KDA | 16.00 | 13.57 | 11.97 | 10.83 | 10.00 | 22.64 | 13.37 |
| **TOASTER** | **15.69** | **13.40** | **11.85** | **10.76** | **9.94** | **22.21** | **13.29** |

TOASTER has the **lowest perplexity at every size on C4** and is **below KDA at every size on both corpora**. On C4, Attention needs 12% more compute than TOASTER to reach the same loss at 145M (1% at 1.2B).

### Hybrid Results at 1.2B (Table 3, bottom)

In the 3:1 hybrid (one attention layer after every three mixer layers):

| Model | C4 PPL ↓ | PG19 PPL ↓ | Avg. Accuracy (%) ↑ |
|-------|----------|------------|-------------------|
| SWA | 9.91 | 13.19 | 51.62 |
| KDA | 9.82 | 12.99 | 50.85 |
| Titans | 9.90 | 13.08 | 50.55 |
| **TOASTER** | **9.78** | **12.75** | **52.11** |

TOASTER's hybrid is **0.18 (C4) and 0.44 (PG19) below the attention baseline**, and 0.04/0.24 below the KDA hybrid.

### All-Layers-Replaced Results at 1.2B (Table 3, top)

TOASTER achieves the lowest C4 perplexity (9.94, vs. 9.96 Attention, 10.00 KDA, 10.09 Titans) and highest downstream average (51.84%, vs. 50.69 Attention, 50.52 KDA, 50.04 Titans).

### Length Extrapolation (Figure 3)

- TOASTER's loss stays **below KDA's at every position** beyond the first thousand tokens, up to 20K tokens (5× training length).
- The advantage is 0.008–0.014 nats averaged over each 4K window, including the final window (16–20K: 0.009 nats).
- Attention degrades sharply beyond its 4K training context.

### Needle-in-a-Haystack (Table 4)

| Task | Attention @4K | KDA @4K | TOASTER @4K |
|------|---------------|---------|-------------|
| S-NIAH-1 (passkey) | 96.3% | 100.0% | 100.0% |
| S-NIAH-2 (number) | 79.0% | 37.3% | **62.7%** |
| S-NIAH-3 (UUID) | 85.7% | 28.0% | 27.3% |

### Throughput (Figure 4)

At hidden width matched to Titans' memory ($d_h = d_k = 64$):
- TOASTER is **1.2–1.8× faster than Titans at 2K** and **2.8–5.5× faster at 32K**.
- TOASTER's step time stays **within 1.33× of KDA's** at every context length.

### Ablations at 145M (Table 5)

| Configuration | C4 PPL | Δ |
|---------------|--------|---|
| KDA (reference) | 16.00 | +0.31 |
| **TOASTER (default)** | **15.69** | — |
| $d_h = d_k$ | 15.90 | +0.22 |
| $d_h = 2d_k$ | 15.76 | +0.07 |
| identity activation | 15.80 | +0.11 |
| leaky ReLU | 15.71 | +0.02 |
| γ = 0 | 15.71 | +0.02 |
| WY kernel (hidden) | 15.64 | −0.05 |
| w/o bias | 15.86 | +0.17 |

Key findings: most of the gain over KDA (0.31) comes from a **wide nonlinear memory** (+0.20 from state size, +0.11 from nonlinearity, +0.02 from target propagation).

---

## Theoretical and Practical Implications

### Theoretical Contributions

1. **Bridging the expressivity–efficiency gap**: TOASTER demonstrates that nonlinear memory capacity is not inherently incompatible with WY-form chunkwise parallelism. The key insight—move the nonlinearity into the targets rather than the state transitions—applies to **any linear recurrence with a chunkwise kernel**.

2. **Per-token equivalence to gradient descent**: With the exact target and no forgetting, TOASTER's per-token dynamics coincide with gradient descent on a two-layer memory network (Remark 1), providing a principled theoretical foundation.

3. **Target propagation as a training signal**: The paper shows that target propagation can supply hidden-layer values by projecting output error back through the second memory, avoiding the need for learned inverses or nonlinear gradient updates.

### Practical Implications

1. **Production-ready efficiency**: TOASTER reuses existing KDA kernels unchanged, requiring no new specialized kernels. At 1.2B, memory kernels are only 8–9% of a block's multiply–accumulate operations.

2. **Hybrid architecture benefits**: The 3:1 hybrid with global attention provides the largest gains on long documents (PG19), suggesting that a few global attention layers supply long-range recall that fixed-size states lack, allowing the nonlinear memory's advantages to show fully.

3. **Scaling considerations**: The gain over KDA narrows with scale (compute-efficiency gain drops from 6% at 145M to −6% at 1.2B on PG19), suggesting memory capacity should be scaled together with model size—a direction for future work.

---

## Conclusion

TOASTER bridges two families of recurrent memory by writing a two-layer memory as two linear memories with an activation in between, giving the hidden memory its own targets through target propagation. This preserves each layer's Householder transition (affine in the state) while confining nonlinearity to the choice of what is written. The result: **nonlinear-memory quality at close to linear-memory speed**.

On a five-point scaling ladder (0.2B–1.6B), TOASTER improves on KDA in every setting, matches softmax attention in-domain, and achieves the best performance among four hybrids in a 3:1 hybrid with global attention at 1.2B.

### Limitations

1. **Efficiency evidence is limited**: One throughput profile at a single model size; with $d_h = 4d_k$, TOASTER costs 6–13% more per token than KDA.
2. **Scale of study**: Stops at 1.6B parameters, 63.7B tokens, and 4,096-token context; single runs with one seed.
3. **Thin downstream evidence**: No per-task significance tests; six of 13 tasks near chance for all models.
4. **Design choices ablated only at 145M**; KDA not retuned with TOASTER's gate scales.
5. **Depth two only**; deeper cascades (Appendix C) are untested.

### Future Directions

- Scaling memory capacity together with model size (the capacity hypothesis)
- Fused kernels for the cascade to reduce the 7–9× kernel arithmetic overhead
- Deeper cascades (more than two layers) with target propagation
- Testing at larger scales, wider-head baselines, and longer contexts
- Applying the "keep transitions affine, move nonlinearity into targets" recipe to other linear recurrences

---

_Markdown view of https://picx.dev/p/3kO0Gq, served by PicX — AI-generated visual whiteboard summaries of research papers._
