Simple linear attention language models balance the recall-throughput tradeoff

ArXiv: 2402.18668

🎯 Pitch

When you cut Transformer memory to speed up inference, associative recall plummets—but not if you add a tiny sliding window of exact attention. Based shatters the assumed recall-efficiency tradeoff, beating Mamba by over 10 points on recall-heavy tasks while running 24× faster than FlashAttention-2.

---

1. Executive Summary

This paper introduces the Based architecture, a hybrid language model that combines linear attention with small sliding-window softmax attention to navigate the inherent tradeoff between a model's memory footprint during inference and its ability to perform associative recall — the capacity to ground generations in previously seen context (e.g., retrieving a key-value pair from earlier in a sequence). Through systematic synthetic experiments on the MQAR task and language modeling evaluations up to 1.3B parameters on the Pile, the authors demonstrate that Based expands the Pareto frontier of the recall-memory tradeoff, outperforming the state-of-the-art sub-quadratic Mamba architecture by 10.36 accuracy points on real-world recall-intensive tasks (information extraction and question answering). Custom IO-aware CUDA kernels enable up to 24× higher inference throughput than FlashAttention-2 during token generation for 1.3B parameter models, establishing that linear attention variants can achieve both quality and efficiency advantages when their recurrent state size is tuned to balance the fundamental recall-memory tradeoff identified through theory and experiment.

2. Context and Motivation

The Core Problem: The Recall–Efficiency Tension in Language Model Architectures

The paper addresses a fundamental architectural tension that shapes how modern language models are built: the choice of sequence mixer — the operation that determines how each token interacts with previous tokens in the sequence — simultaneously governs both a model's quality (specifically its capacity for in-context recall) and its efficiency (specifically memory consumption during inference). The paper frames this as a tradeoff that is both empirically demonstrable and theoretically inescapable, and it asks: can we design an architecture that navigates this tradeoff more effectively than existing approaches?

To understand why this matters, we need to unpack what "recall" means concretely and why it conflicts with efficiency.

Recall as a core competency. In-context recall — also called associative recall — is the ability to look back at information presented earlier in the input sequence and use it correctly in the current generation. For example, if a prompt describes a set of facts ("Alice is 42 years old, Bob works in engineering…") and then asks a question ("How old is Alice?"), the model must retrieve the earlier fact and reproduce it. This capability is not just a benchmark curiosity; it underpins critical applications like information extraction from documents, question answering over long passages, code generation (where earlier definitions must be referenced), and summarization. The paper cites prior work showing that "attention excels at recall" (Section 1) — Transformers with full softmax attention can solve associative recall tasks perfectly (Figure 2, Section 3.1).

The efficiency bottleneck. The mechanism that gives attention its recall power is the KV-cache: during autoregressive generation, the model stores every key and value vector from every previous token and recomputes attention over this entire history for each new token. The size of this KV-cache grows linearly with sequence length. For a model with dimension $d$ generating $N$ tokens, the cache requires storing $2 \times N \times d$ values. During inference, this means (a) memory consumption that grows unboundedly with context length, and (b) per-token computation that scales as $\mathcal{O}(Nd)$, since each new query must attend over the entire growing cache. The authors note that "the throughput of attention-based models is bottle-necked during training by quadratic compute complexity and during inference by aggressive memory consumption" (Section 1).

The practical stakes. This tension is not a theoretical exercise. Two regimes make it especially acute:

1. Long-context deployment. As models are deployed with increasingly long context windows (tens or hundreds of thousands of tokens), the KV-cache becomes the dominant memory consumer and the throughput bottleneck. A model that maintains high recall but with a smaller, fixed-size recurrent state could process arbitrarily long sequences with constant memory — enabling deployment on memory-constrained devices or handling of very long documents.

2. High-throughput generation. In production settings where many sequences are generated in parallel (batch inference), memory consumption directly determines how many sequences can be processed simultaneously on a single GPU. Reducing the per-sequence memory footprint translates to higher overall throughput and lower costs.

Why This Problem Demands a New Approach: The Architecture Landscape

The paper situates itself within an active research program exploring alternatives to standard attention that improve efficiency while preserving quality. These efforts fall into three broad categories, each with documented limitations that motivate the paper's contribution.

Category 1: Structured Sparse Attentions

The first approach is to keep the softmax attention mechanism but restrict which tokens can attend to which — creating sparsity patterns in the attention matrix. The most prominent variant is sliding window attention (SWA) (Beltagy et al., 2020; Child et al., 2019), where each query attends only to the $w$ most recent tokens. This caps the KV-cache at $2 \times w \times d$, independent of total sequence length, and reduces computation to $\mathcal{O}(Nw)$.

Where it falls short. The paper identifies two limitations. First, recall range is strictly bounded by the window width $w$ — any key-value pair that appeared more than $w$ tokens ago is invisible, making long-range recall impossible. Second, from a hardware perspective, the relationship between window size and speed is non-linear (Figure 1, left): larger windows do not simply slow down proportionally but interact with GPU tensor core utilization in complex ways. Systems like Mistral 7B use $w = 4096$ (Mistral, 2023), which still leaves a substantial KV-cache that grows with context length. The paper's experiments on the MQAR synthetic task (Figure 2) confirm that increasing window size improves recall accuracy, but the memory cost grows linearly, leaving SWA on an interior point of the recall-memory Pareto curve rather than expanding it beyond what simpler methods achieve.

Category 2: Attention Alternatives (State-Space Models and Gated Convolutions)

A second line of work abandons the attention mechanism entirely, replacing it with sequence mixers based on state-space models (SSMs), long convolutions, or input-dependent recurrences. Architectures like H3 (Dao et al., 2022), Hyena (Poli et al., 2023), RWKV (Peng et al., 2023), and Mamba (Gu et al., 2023) all achieve sub-quadratic training complexity and use fixed-size recurrent states for constant-memory generation. The empirical promise: models like Mamba match or exceed Transformers in aggregate perplexity (Gu et al., 2023; Yang et al., 2023).

Where it falls short. The paper points to a growing body of evidence that coarse metrics like aggregate perplexity can "obscure important differences in model quality" (Section 1). Specifically, Arora et al. (2023) showed that gated-convolution architectures struggle to perform associative recall as efficiently as attention — they require model dimensions that scale with sequence length to solve the task, while attention solves it in constant layers. The paper builds on this analysis, showing in Table 1 that on real-world recall-intensive tasks, the prior best sub-quadratic architecture (Mamba) trails standard attention (Transformer++) by up to 32.2 accuracy points. This is a massive gap in capability that aggregate perplexity numbers (where the models differ by only ~0.2 perplexity points) completely hide.

The core technical issue, as the paper explains, is that many of these architectures lack the ability to perform precise token-level comparisons and shifts that attention's dot-product mechanism inherently provides. Gated convolutions can compare tokens via element-wise multiplication after shifting (the "gating" mechanism), but they cannot easily select which information from the long prefix to bring forward — a task that attention's query-key matching naturally performs. This makes them "asymptotically less efficient than attention at performing recall" (Section 1, citing Arora et al., 2023).

Category 3: Linear Attentions

The third approach — and the one the paper centrally engages with — is linear attention. Rather than restricting the sparsity pattern (like SWA) or replacing attention entirely (like SSMs), linear attention approximates the softmax attention mechanism itself. The key insight, introduced by Katharopoulos et al. (2020), is to replace the softmax kernel $\exp(\bm{q}_i^\top \bm{k}_j / \sqrt{d})$ with a kernel that factorizes as a dot product of feature maps: $\phi(\bm{q}_i)^\top \phi(\bm{k}_j)$. This makes it possible to compute attention via the associative property of matrix multiplication, reducing complexity from $\mathcal{O}(N^2 d)$ to $\mathcal{O}(N d^2)$. Critically, it also enables a recurrent view: the model maintains fixed-size hidden states (an accumulated KV-state and K-state) that are updated token-by-token, enabling constant-memory, constant-time-per-token generation (Section 4.1, Equations 2-3).

Where prior linear attention falls short. The paper identifies two key failures that prevent linear attention from realizing its theoretical promise:

1. Recall quality gap. Linear attention's feature maps approximate the softmax, but approximations are lossy. The paper shows (Figure 1, center, and Table 6 quality ablations) that linear attention alone — even with strong feature maps like CosFormer or Performer variants — substantially underperforms standard attention on recall tasks. The authors hypothesize that "linear attention lacks the precision to perform local token shifts and comparisons" (Section 1) that are needed for accurate associative recall. The softmax's sharp peak (exponential scaling of large dot products) acts as an implicit selection mechanism that linear approximations with smoother kernels cannot replicate.

2. Wall-clock inefficiency paradox. Despite its theoretical $\mathcal{O}(N d^2)$ complexity advantage during prefill and constant-memory generation, linear attention implementations are "often less efficient than well-optimized attention implementations" when measured in actual wall-clock time (Section 5, citing Dao et al., 2022). The reason is that the expanded feature dimension $D = 1 + d' + d'^2$ (for the 2nd-order Taylor feature map) creates large intermediate tensors: naive implementations perform $\mathcal{O}(N d^3)$ operations and move massive amounts of data between GPU memory tiers. The authors note that prior linear attention baselines using the Fast Transformers CUDA kernel (Vyas et al., 2020) are slower than FlashAttention-2 in practice (Figure 4, "Baseline Based" line). This implementation gap has prevented linear attention from being adopted as a practical alternative despite its theoretical appeal.

The Conceptual Framework: A Recall-Memory Tradeoff

The paper's core intellectual move is to unify these disparate architectural observations under a single conceptual framework: the recall-memory tradeoff. Rather than treating each architecture's performance as idiosyncratic, the paper shows that all sequence mixers lie on a fundamental tradeoff curve where recall accuracy is bounded by the size of the model's recurrent state (i.e., the memory it maintains across tokens during generation).

This tradeoff is demonstrated in Section 3 through a combination of:

1. Synthetic experiments on MQAR (Multi-Query Associative Recall): The authors evaluate a broad set of architectures — attention, sliding window attention, Mamba, H3, Hyena, and the proposed Based — on a controlled associative recall task while systematically varying hyperparameters that affect recurrent state size (model dimension, feature dimension, window width). Figure 2 and Figure 8 present the central visual: each architecture defines a curve in the state-size-vs-accuracy plane. Attention achieves perfect recall but its recurrent state (the full KV-cache) grows linearly with sequence length, placing it at the far upper-right of the plot. Sliding window attention traces a curve where accuracy degrades as window size shrinks. Mamba expands the frontier beyond SWA, making better use of a given state budget. The paper's key claim is that Based pushes this frontier further still — for a fixed state size, it achieves higher recall than any prior sub-quadratic architecture.

2. Theoretical lower bounds: Section 3.2 and Appendix F formalize why this tradeoff is fundamental. Theorem 3.1 (F.3 in the appendix) proves that any recurrent model requires $\Omega(N)$ bits of state to solve general associative recall — the lower bound grows with sequence length. Theorems 3.2 and 3.3 show that gated-convolution architectures (like H3 and Hyena) require $\Omega(\max(\log\log c, \log\log N))$ layers to solve MQAR, while attention solves it in $O(1)$ layers. These results explain why the gated-convolution architectures sit below the Pareto frontier in Figure 2: they are architecturally constrained in ways that attention and certain linear attention variants are not.

A crucial insight emerges from this framework: the optimal architecture is not one that sits at either extreme of the tradeoff curve, but one that can be dialed anywhere along it by tuning hyperparameters. This is the design philosophy of Based: by adjusting the feature dimension of the Taylor linear attention and the width of the sliding window, the same architecture can achieve small-state efficiency or high-state recall capacity, allowing deployment-time tradeoffs that are impossible with fixed architectures.

The Missed Opportunity: Combining Sparse and Linear Attention

The paper builds on a long line of work exploring how to combine sparse and linear attention mechanisms (ScatterBrain by Chen et al., 2021; BigBird by Zaheer et al., 2020; Longformer by Beltagy et al., 2020). However, the paper argues that prior work in this tradition missed a crucial design insight. Most prior approaches to combining sparse and linear attention (a) used large window sizes for the sparse component (e.g., $w = 4096$ in Mistral 7B), (b) used small feature dimensions for the linear component (keeping $d' \ll d$), and (c) treated the combination as a fixed, non-tunable recipe.

The paper's observation is that the complementary strengths of these two mechanisms map directly onto different aspects of the recall problem:

• Sliding window attention with small windows ($w = 64-128$) — what the paper calls "tcWindow" for "tensor-core aware window" — provides precise, fine-grained local interactions. Small windows keep tensor cores occupied (Figure 1, left, shows 64×64 GEMMs have similar latency to 16×16) while adding minimal memory overhead. But small windows alone cannot capture long-range dependencies.

• Linear attention with expanded feature dimension ($d' = 16$, yielding $D = 1 + 16 + 256 = 273$) — provides global, all-to-all token interactions through a compressed recurrent state. The large state can model long-range dependencies, but the kernel approximation lacks the precision for exact local token matching.

The paper's thesis is that these two components compensate for each other's failure modes: the sliding window handles precise local recall that linear attention struggles with, and the linear attention provides the long-range reach that is invisible to the small window. Neither alone navigates the Pareto frontier; together, they push it outward.

This complementarity is demonstrated quantitatively in the quality ablation experiments (Table 6): a Based model with only linear attention achieves 2.11 AR perplexity on the Pile, with only sliding windows achieves 2.09, and the combination achieves 2.07 — with further gains from adding short convolutions (2.04 with decay removed). The synergy is real but not overwhelming at the scale tested, suggesting that the primary value of the combination is architectural flexibility rather than a dramatic interaction effect.

How the Paper Positions Itself

The paper makes four distinct positioning moves that define its contribution relative to existing work:

1. From "better perplexity" to "targeted capability benchmarking." The paper explicitly argues against evaluating architectures solely on aggregate perplexity (Section 1, Section 6.1). It introduces a suite of real-world recall-intensive tasks (SWDE information extraction, FDA document extraction, SQUAD reading comprehension) and shows that these reveal capability differences invisible in perplexity scores. This is a methodological contribution: the paper provides a template for evaluating efficient architectures on the capabilities that actually matter for downstream use, not just average next-token prediction loss.

2. From architectural novelty to Pareto frontier expansion. The paper does not claim to invent linear attention or sliding window attention — both are well-established primitives. The contribution is in (a) identifying that the combination expands an empirically and theoretically grounded Pareto frontier, (b) providing a principled mechanism (tunable feature dimension and window size) for navigating that frontier, and (c) demonstrating that relatively simple components, chosen with hardware awareness, can match or exceed the performance of much more complex architectures (like Mamba's input-dependent state updates and parallel scans).

3. From asymptotic theory to wall-clock efficiency via IO-aware implementation. The paper acknowledges a critical gap in the linear attention literature: theoretical efficiency doesn't translate to real-world speed without careful implementation. Section 5 and Appendix B provide detailed, IO-aware CUDA algorithms that reduce HBM-to-SRAM data movement by $\mathcal{O}(2BHND)$ bytes and SRAM-to-register movement by $\mathcal{O}(BHNDd)$ bytes compared to the naive baseline (Section 5.2). These optimizations are what make Based competitive with FlashAttention-2 in practice, and the paper positions the implementation work as equally important as the architectural insights.

4. From input-dependent recurrence to simple, fixed-hyperparameter alternatives. Recent state-of-the-art sub-quadratic architectures (Mamba, Gated Linear Attention) use input-dependent state updates — the recurrent state evolves differently depending on the input content, requiring parallel scan algorithms during training. The paper notes that "in contrast to recent baselines, Based requires no input-dependent decays whatsoever" (Section 6). This is a striking simplicity claim: by combining two fixed mechanisms (linear attention with a fixed feature map, sliding window attention with a fixed window), Based achieves competitive or superior performance without the algorithmic complexity of content-dependent recurrence. This has implications for ease of implementation, training stability, and hardware portability.

The Gap This Paper Fills

Synthesizing the above: prior to this work, the field had (a) architectures that excel at recall but are memory-hungry (attention), (b) architectures that are memory-efficient but struggle at recall (SSMs, gated convolutions), and (c) architectures that are theoretically efficient but practically slow (linear attention with naive implementations). No architecture simultaneously achieved strong real-world recall performance, competitive perplexity, and wall-clock throughput advantages over highly optimized attention implementations. The paper fills this gap by demonstrating that a carefully tuned combination of linear attention and small-window softmax attention, implemented with hardware-aware kernels, can occupy a previously empty region of the recall-throughput design space — what the authors call the Pareto frontier expansion.

This framing makes the paper's contribution more than "another efficient architecture." It is a demonstration that the recall-memory tradeoff is a fundamental organizing principle for sequence mixer design, that simple mechanisms can be composed to navigate it effectively, and that implementation quality is a first-class concern in realizing theoretical efficiency gains. These insights have implications beyond the specific Based architecture — they provide a framework for evaluating and designing future efficient sequence mixers.

3. Technical Approach

3.1 Reader Orientation (Approachable Technical Breakdown)

This is primarily an architectural design paper with supporting theoretical analysis and systems implementation. The core idea is that by combining two well-known but complementary sequence mixing primitives — linear attention (for global, compressed interactions through a fixed-size recurrent state) and small-window softmax attention (for precise local token matching) — and implementing them with hardware-aware CUDA kernels, we can build a language model (Based) that navigates the fundamental tradeoff between recall capacity and inference memory consumption more effectively than any prior architecture.

The system being built is a sequence-to-sequence language model where each layer's "sequence mixer" (the operation that determines how each token interacts with previous tokens) is either a Taylor-approximated linear attention, a small sliding-window softmax attention, or a short gated convolution. The model produces next-token predictions autoregressively. The key design insight is that no single mixer type dominates across all operating points of the recall-memory spectrum; by combining them with tunable hyperparameters (feature dimension for linear attention, window size for softmax attention), the same architecture family can be configured anywhere from a small-state efficiency regime to a large-state high-recall regime, expanding the Pareto frontier beyond what any prior sub-quadratic architecture achieves.

3.2 Big-Picture Architecture (Diagram in Words)

The Based architecture is a hybrid sequence model with three layer types, each serving a distinct purpose in the overall sequence mixing:

1. Taylor Linear Attention layers (~20% of layers). Each layer applies a 2nd-order Taylor approximation of the softmax kernel, mapping query-key interactions through a fixed feature map $\phi: \mathbb{R}^{d'} \to \mathbb{R}^{D}$ where $D = 1 + d' + d'^2$. The feature dimension $d'$ (typically 16) is a critical hyperparameter: it determines the size of the recurrent state maintained during generation. These layers perform global attention — every query attends to every past key, but through a compressed representation stored in two fixed-size accumulator states (a "KV-state" and a "K-state"). The recurrent view enables constant-memory generation: only the states are updated per token, no KV-cache growth.

2. Sliding Window Attention layers (~20% of layers). Each layer applies exact softmax attention restricted to the most recent $w$ tokens, where $w$ is deliberately small (64 or 128, determined by GPU tensor core tile sizes). These layers handle local, precise token comparisons that linear attention's smooth kernel approximation cannot capture reliably. The window size is chosen to keep tensor cores occupied (64×64 matrix multiplications have near-optimal throughput on modern GPUs) while adding minimal memory overhead.

3. Short Gated Convolution layers (~60% of layers). Each layer applies element-wise gating combined with a short convolution (filter size 3). These provide complementary local mixing — the convolution can perform precise shifts needed for token comparison across the full sequence, which the sliding window (restricted to its local window) cannot do beyond $w$ tokens. The gating (Hadamard product) introduces multiplicative interactions between tokens.

The information flow during generation: the input token embedding passes through a stack of these layers in the specified ratios (e.g., for the 360M parameter model: 5 linear attention, 5 sliding window, 17 gated convolution layers out of 27 total). Each layer's output feeds the next layer's input. The final layer output is projected to vocabulary logits for next-token prediction. Critically, all three layer types maintain recurrent states during generation: linear attention layers have their KV-state and K-state; sliding window layers have a small KV-cache of size $2 \times w \times d$; convolution layers have a small state equal to the filter size. The total recurrent state size is the sum across layers and is the quantity plotted on the x-axis of the recall-memory tradeoff curves (Figures 2, 3).

3.3 Roadmap for the Deep Dive

• First, the Taylor Linear Attention mechanism (Section 4.1): the mathematical formulation of linear attention, the choice of the 2nd-order Taylor feature map, why this feature map expands the recurrent state without increasing parameter count, and how varying the feature dimension $d'$ dials the state size along the Pareto frontier.
• Second, the sliding window attention with tcWindow design (Section 4.2): why small windows (64–128 tokens), how the window size is chosen based on GPU hardware properties, and how this complements the linear attention's global but imprecise coverage.
• Third, the hardware-efficient CUDA implementation (Section 5): the IO-aware algorithms for the Taylor linear attention prefill (Algorithm 1) and recurrent state update during generation (Algorithm 2), the sliding window generation kernel (Algorithm 3), and the quantitative data movement savings relative to naive baselines.
• Fourth, the theoretical analysis via BaseConv (Section 3.2, Appendix F): lower bounds proving that recall requires large recurrent states (Theorem 3.1, F.3), that gated-convolution architectures require logarithmic-depth to solve associative recall (Theorems 3.2, 3.3, F.4, F.5, F.6), and the constructive upper bound showing Based can solve complex recall problems efficiently (Theorem F.7).
• Fifth, the empirical measurement of the recall-memory tradeoff (Section 3.1, Appendix D.1): the MQAR synthetic task setup, how recurrent state sizes are calculated for each architecture, the Pareto frontier plots (Figures 2, 3, 8), and what varying hyperparameters across architecture families reveals.
• Sixth, the decay mechanism and convolution details (Appendix C): the optional input-dependent head-wise decay for linear attention, the BaseConv (gated convolution) layer definition, and quality ablation studies showing which components contribute what.

3.4 Detailed, Sentence-Based Technical Breakdown

---

3.4.1 Taylor Linear Attention: The Global, Compressed Sequence Mixer

Linear attention replaces the softmax in standard attention with a kernel that factorizes as a dot product of feature maps. This is the mechanism that enables the constant-size recurrent state and is the primary means by which Based achieves its efficiency gains over full attention.

The standard attention formulation (causal):

$$\bm{y}_i = \sum_{j=1}^{i} \frac{\exp(\bm{q}_i^\top \bm{k}_j / \sqrt{d}) \bm{v}_j}{\sum_{m=1}^{i} \exp(\bm{q}_i^\top \bm{k}_m / \sqrt{d})}$$

where $\bm{q}_i = \bm{x}_i \bm{W}_q$, $\bm{k}_j = \bm{x}_j \bm{W}_k$, and $\bm{v}_j = \bm{x}_j \bm{W}_v$ are the query, key, and value projections of the input $\bm{x} \in \mathbb{R}^{N \times d}$, with $\bm{W}_q, \bm{W}_k, \bm{W}_v \in \mathbb{R}^{d \times d}$ as learnable weight matrices.

What it computes: For each position $i$, the output is a weighted sum of all previous value vectors $\bm{v}_j$ for $j \leq i$, where the weight on each $\bm{v}_j$ is the softmax-normalized dot product between query $\bm{q}_i$ and key $\bm{k}_j$. The softmax creates a sharp selection mechanism: keys with much larger dot products (indicating higher similarity) receive exponentially larger weights, effectively focusing attention on the most relevant past tokens.

Why this is problematic for efficiency: During autoregressive generation, computing $\bm{y}_N$ for the $N$-th token requires attending over all $N-1$ previous keys and values, which must be stored in the growing KV-cache. Memory grows as $\mathcal{O}(Nd)$ and per-token computation grows as $\mathcal{O}(Nd)$. For long sequences, this becomes the dominant bottleneck.

The linear attention reformulation: Katharopoulos et al. (2020) observed that if we select a feature map $\phi: \mathbb{R}^{d} \to \mathbb{R}^{\tilde{d}}$ such that $\phi(\bm{q}_i)^\top \phi(\bm{k}_j) \approx \exp(\bm{q}_i^\top \bm{k}_j / \sqrt{d})$, we can rewrite the attention as:

$$\bm{y}_i = \sum_{j=1}^{i} \frac{\phi(\bm{q}_i)^\top \phi(\bm{k}_j) \bm{v}_j}{\phi(\bm{q}_i) \sum_{m=1}^{i} \phi(\bm{k}_m)} = \frac{\phi(\bm{q}_i) \sum_{j=1}^{i} \big(\phi(\bm{k}_j)^\top \bm{v}_j\big)}{\phi(\bm{q}_i) \sum_{j=1}^{i} \phi(\bm{k}_j)}$$

where $\phi(\bm{q}_i)$ is the featurized query vector of dimension $\tilde{d}$, $\phi(\bm{k}_j)$ is the featurized key vector, and $\phi(\bm{k}_j)^\top \bm{v}_j$ is an outer product between the featurized key and the value vector, producing a matrix in $\mathbb{R}^{\tilde{d} \times d}$.

What this form enables: The crucial algebraic trick is that the sum over $j$ can be accumulated incrementally. Define two recurrent states:

• KV-state: $\bm{s}_i = \sum_{j=1}^{i} \phi(\bm{k}_j)^\top \bm{v}_j \in \mathbb{R}^{\tilde{d} \times d}$ — accumulates the outer products of featurized keys with their corresponding values.
• K-state: $\bm{z}_i = \sum_{j=1}^{i} \phi(\bm{k}_j)^\top \in \mathbb{R}^{\tilde{d}}$ — accumulates the sum of featurized keys for normalization.

Both states can be updated recurrently:

$$\bm{s}_i = \bm{s}_{i-1} + \phi(\bm{k}_i)^\top \bm{v}_i, \quad \bm{z}_i = \bm{z}_{i-1} + \phi(\bm{k}_i)^\top$$

Then the output at position $i$ is:

$$\bm{y}_i = \frac{\phi(\bm{q}_i) \bm{s}_i}{\phi(\bm{q}_i) \bm{z}_i}$$

Why this works for efficiency: The states $\bm{s}_i$ and $\bm{z}_i$ have fixed sizes $\tilde{d} \times d$ and $\tilde{d}$ respectively, independent of sequence length $N$. During generation, when predicting token $N+1$, we only need to (1) compute $\phi(\bm{k}_{N})$ and $\phi(\bm{v}_{N})$ from the new token, (2) add $\phi(\bm{k}_{N})^\top \bm{v}_{N}$ to $\bm{s}_{N-1}$ and $\phi(\bm{k}_{N})^\top$ to $\bm{z}_{N-1}$, and (3) compute the query-state product. The per-token cost is $\mathcal{O}(\tilde{d} d)$ rather than $\mathcal{O}(N d)$, and the memory is constant. This is what the paper calls the "recurrent view" of linear attention.

The Taylor feature map choice. The paper uses the 2nd-order Taylor series approximation of the exponential function as the feature map:

$$\phi(\bm{q}_i)^\top \phi(\bm{k}_j) = 1 + \bm{q}_i^\top \bm{k}_j + \frac{(\bm{q}_i^\top \bm{k}_j)^2}{2}$$

where $\phi: \mathbb{R}^{d'} \to \mathbb{R}^{D}$ with $D = 1 + d' + d'^2$, and $\bm{q}_i, \bm{k}_j \in \mathbb{R}^{d'}$ are projected versions of the queries and keys, not the full-dimensional $\mathbb{R}^d$ vectors. Specifically, the model applies learnable projections $\bm{W}_q, \bm{W}_k \in \mathbb{R}^{d \times d'}$ that map from the model dimension $d$ down to a smaller feature dimension $d'$ (e.g., $d' = 16$ for the 360M parameter model with $d = 1024$).

What the feature map computes: The outer product of the Taylor-expanded query and key vectors. For a given query $\bm{q}$ and key $\bm{k}$ (both in $\mathbb{R}^{d'}$), the $D = 1 + d' + d'^2$ entries of $\phi(\bm{q})$ are: the constant 1 (0th-order term), the $d'$ entries of $\bm{q}$ (1st-order term), and the $d'^2$ pairwise products $\bm{q}_j \bm{q}_k$ for all $j,k \in [d']$ (2nd-order term). Similarly for $\phi(\bm{k})$. The dot product $\phi(\bm{q})^\top \phi(\bm{k})$ then reconstructs the Taylor polynomial $1 + \bm{q}^\top \bm{k} + \frac{(\bm{q}^\top \bm{k})^2}{2}$.

Why this specific Taylor approximation: The paper evaluates a broad set of feature maps (Figure 3): $\phi_{\text{ReLU}}(x) = \max(x, 0)$, $\phi_{\text{PosELU}}(x) = \text{ELU}(x) + 1$, $\phi_{\text{Square}}(x) = x^2$, $\phi_{\text{Identity}}(x) = x$, $\phi_{\text{CosFormer}}$ (from Qin et al., 2022), and $\phi_{\text{Performer}}$ (from Choromanski et al., 2020). The key finding is that the Taylor feature map sits at the Pareto frontier alongside $\phi_{\text{PosELU}}$ and $\phi_{\text{ReLU}}$, but with a critical advantage: it expands the recurrent state size (and thus recall capacity) without changing the number of parameters. The CosFormer and Performer feature maps, by contrast, require learned projections to achieve comparable state sizes, increasing parameter count. The paper explicitly states: "One advantage of the Taylor feature map over these alternatives is that it expands the recurrent state size (improving recall capacity) without changing the number of parameters" (Section 4.1, description of Figure 3 bottom).

How the feature dimension $d'$ controls the state size. The recurrent state for a linear attention layer has size:

$$\text{sizeof}(\bm{s}_i) = (d + 1) \times (1 + d' + d'^2) \quad \text{floats}$$

where $d$ is the model dimension (e.g., 1024), and the $+1$ accounts for the K-state $\bm{z}_i$ used in the denominator normalization. For $d' = 16$, this gives a state of approximately $(1024 + 1) \times (1 + 16 + 256) = 1025 \times 273 \approx 280,000$ floats per linear attention layer. For a model with 5 linear attention layers (the 360M configuration), this is approximately 1.4 million floats — about 5.6 MB in bfloat16. Increasing $d'$ to 24 expands this to $1025 \times (1 + 24 + 576) \approx 616,000$ per layer, roughly doubling the linear attention state size. The quality ablation (Table 6) shows that increasing $d'$ from 8 to 16 improves recall, while going from 24 to 32 provides diminishing returns.

Why project to a smaller dimension? The paper explicitly addresses the concern raised by Hedgehog (2023) that a naive Taylor feature map with $d' = d$ would require $\mathcal{O}(N d^3)$ time and space. By projecting queries and keys to $d' = 16$ (while keeping values at the full model dimension $d$), the effective state dimension becomes $D = 1 + d' + d'^2 = 273$, which is manageable. The $d'$ parameter is the primary knob for navigating the recall-memory tradeoff within the Based architecture.

The distinction between feature map dimension and model dimension. A key architectural detail that differentiates Based from prior linear attention work: $\bm{W}_q, \bm{W}_k \in \mathbb{R}^{d \times d'}$ project to a smaller feature space for the similarity computation, while $\bm{W}_v \in \mathbb{R}^{d \times d}$ keeps the value dimension at the full model dimension. This means the KV-state $\bm{s}_i$ has shape $\mathbb{R}^{D \times d}$ — the first dimension depends on the expanded feature map size, the second on the head dimension (which equals the model dimension divided by number of heads). For the 360M model with $d = 1024$, 16 heads, and feature dimension $d' = 16$, this gives $D = 273$, and each head's KV-state is $273 \times 64$, totaling $273 \times 64 \times 16 = 279,552$ floats across all heads — on the order of hundreds of thousands, compared to the full attention KV-cache which would be $2 \times N \times 1024$ floats (over 2 million for just 1024 tokens, growing linearly).

---

3.4.2 Sliding Window Attention with tcWindow: Local, Precise Token Matching

The second major component of Based is exact softmax attention restricted to a small local window. This compensates for the primary failure mode of linear attention: its inability to perform the sharp, precise token comparisons needed for exact associative recall.

The sliding window attention formulation (causal):

For window size $w$, each query $\bm{q}_i$ attends only to the $w$ most recent keys $\{\bm{k}_{i-w+1}, \ldots, \bm{k}_i\}$:

$$\bm{y}_i = \sum_{j=i-w+1}^{i} \frac{\exp(\bm{q}_i^\top \bm{k}_j / \sqrt{d}) \bm{v}_j}{\sum_{m=i-w+1}^{i} \exp(\bm{q}_i^\top \bm{k}_m / \sqrt{d})}$$

where the summands for $j \leq 0$ are zero-padded (early tokens see fewer than $w$ keys).

What it computes: Identical to standard softmax attention, but with the attention mask zeroing out all positions outside the local window. This provides exact, sharp attention weights — the exponential nonlinearity amplifies the largest dot products, creating a near-selection mechanism that can precisely identify matching tokens. The window size $w$ determines the maximum recall range: any key that appeared more than $w$ tokens ago is invisible.

The critical design choice: $w = 64$ or $w = 128$ (the "tcWindow"). Unlike prior sliding window implementations that use large windows ($w = 4096$ in Mistral 7B, $w = 256$ in early efficient attention work), Based uses surprisingly small windows — 64 or 128 tokens. The paper calls this "tcWindow" for "tensor-core aware window." The justification is hardware-driven:

1. Tensor core occupancy. Modern NVIDIA GPUs perform matrix multiplications on tensor cores, which operate on tiles of $16 \times 16$. The paper shows (Figure 1, left) that the latency of a $64 \times 64$ GEMM is nearly identical to a $16 \times 16$ GEMM — the tensor cores are already saturated. Moving to $128 \times 128$ adds minimal overhead. This means small windows keep tensor cores at full utilization while dramatically reducing memory footprint.

2. Memory proportionality. The KV-cache for a sliding window layer is $2 \times w \times d$ floats (keys and values for $w$ tokens). With $w = 64$ and $d = 1024$, this is $2 \times 64 \times 1024 = 131,072$ floats per layer — about 0.5 MB in bfloat16 for the entire layer, compared to Mistral's $2 \times 4096 \times d$ which grows with model dimension. For inference, this small cache can reside in SRAM or L2 cache rather than requiring HBM accesses.

3. Non-linear speed effects. The paper notes that as window size increases, "the recurrent state grows linearly and has a non-linear effect on speed during parallel training and inference" (Section 1). This is because larger windows eventually cross memory thresholds that trigger different memory access patterns (e.g., exceeding SRAM capacity, triggering more frequent HBM reads).

Why not larger windows? Larger windows would certainly improve recall range, but at the cost of increased memory. The paper shows in Figure 2 that for sliding window attention alone, accuracy on MQAR improves nearly linearly with window size — but the state size also grows linearly, meaning sliding window attention traces a fixed curve in the recall-memory plane. It does not expand the Pareto frontier beyond what can be achieved by simply tuning window size. The innovation is in recognizing that the global coverage lost by using small windows can be recovered by the complementary linear attention component.

How sliding window complements linear attention. The paper hypothesizes (Section 1, Section 4) that the two mechanisms have complementary failure modes on associative recall. In the MQAR task, recall requires two steps: (1) comparing the current query token to all past key tokens to find an exact match, and (2) retrieving the value associated with that matching key. Linear attention's smooth Taylor kernel approximation cannot produce the sharp, binary-like attention weights needed for step (1) — the dot product $\phi(\bm{q})^\top \phi(\bm{k})$ varies gradually, making it difficult to distinguish an exact match from a near-match. The sliding window's exact softmax, with its exponential sharpening, excels at step (1) but only within its limited range. The long-range step (2) is handled by linear attention, which can propagate information across arbitrary distances through its accumulated states. The quality ablation in Table 6 supports this: removing sliding windows degrades AR perplexity from 2.07 to 2.09 or 2.11 (depending on configuration), while the impact on "Other" perplexity is smaller.

The receptive field argument. With $w = 64$ and a 64-layer model, each query can reach back $64 \times 64 = 4096$ tokens through the composition of sliding windows across layers (each layer's window shifts, so information can propagate). However, this is an upper bound that assumes perfect information propagation, which does not hold in practice. The paper's solution is to not rely on layered propagation for long-range signals but instead use the linear attention layers for global interactions.

---

3.4.3 Short Gated Convolutions (BaseConv): Complementary Local Mixing

The third building block, comprising the majority (≈60%) of Based layers, is the short gated convolution (BaseConv) layer. This provides additional local mixing that complements both the sliding window and linear attention.

The BaseConv layer formulation:

$$\bm{y} := ((\bm{u} \cdot \bm{W}_1 + \bm{b}_1) \odot \sigma(\bm{h} \ast \bm{u} \cdot \bm{W}_2 + \bm{b}_2)) \cdot \bm{W}_3 + \bm{b}_3$$

where $\bm{u} \in \mathbb{R}^{N \times d}$ is the projected input, $\bm{h} \in \mathbb{R}^{N \times cd}$ is a learned convolution filter of width 3 (the filter operates over the sequence length $N$), $\ast$ denotes causal convolution, $\odot$ is the Hadamard (element-wise) product, $\sigma$ is the SiLU (Sigmoid Linear Unit) non-linearity, $\bm{W}_1, \bm{W}_2 \in \mathbb{R}^{d \times cd}$ and $\bm{W}_3 \in \mathbb{R}^{cd \times d}$ are learned weight matrices with projection expansion factor $c = 4$, and $\bm{b}_1, \bm{b}_2 \in \mathbb{R}^{cd}$, $\bm{b}_3 \in \mathbb{R}^{d}$ are biases.

What it computes: The layer splits the input into two parallel branches. The left branch ($\bm{u} \cdot \bm{W}_1 + \bm{b}_1$) is a simple linear projection — a per-token, position-independent transformation. The right branch applies a short convolution (filter width 3) to the projected input, followed by another linear projection and a SiLU non-linearity. The SiLU (also called Swish) is $\sigma(x) = x \cdot \text{sigmoid}(x)$, which acts as a gating mechanism — it can suppress or amplify different channels depending on the convolution output. The two branches are multiplied element-wise (the Hadamard product $\odot$), allowing the convolution branch to gate the linear projection branch. Finally, another linear projection $\bm{W}_3$ maps back to the model dimension.

Why this design: The gated convolution serves a specific, identified need in the recall pipeline. Prior work (Arora et al., 2023) showed that associative recall requires token shifting — the ability to align a token from the past with the current position for comparison. Standard attention achieves this naturally through the query-key dot product: the query "looks up" the matching key regardless of position. Convolutions can achieve a related effect by learning filters that shift information by specific offsets. However, the correct shift depends on the input — you need to shift different amounts for different tokens. The gating mechanism (multiplicative interaction between the two branches) provides input-dependence: the gating branch, conditioned on the convolution output, can selectively pass or suppress information from the linear branch. The short filter width (3) keeps the recurrent state small (just the last 3 tokens' worth of activations) while the SiLU activation provides the non-linearity needed for complex gating patterns.

Why 60% of layers use convolutions. The quality ablation (Table 6) shows that removing convolutions (keeping only linear attention and sliding windows) degrades Pile perplexity from 8.65 to 8.74, with a larger impact on AR perplexity (2.07 to 2.09). The paper interprets this as evidence that convolutions can "help perform local, precise shifts for token comparisons since they operate over the full sequence, while tcWindow does not" (Section 4.2). The sliding window can only shift tokens within its limited range; the convolution, being applied over the entire sequence length with a learned filter, can perform learned shifts at arbitrary offsets while still maintaining a small state.

Relationship to theoretical analysis. The BaseConv layer is central to the paper's theoretical framework (Appendix F). Arora et al. (2023) introduced BaseConv as a canonical form that can simulate any architecture built from gating and convolution primitives. The paper uses this to prove lower bounds: gated convolution architectures (H3, Hyena) inherently require $\Omega(\log\log N)$ layers to solve associative recall (Theorem F.4, F.5, F.6), while attention solves it in $O(1)$ layers. Based's linear attention layers (which can also be simulated by BaseConv with polylog blowup, Proposition F.1) provide the $O(1)$-layer recall capability that pure convolution architectures lack.

---

3.4.4 Hardware-Efficient CUDA Implementation: Making Linear Attention Fast in Practice

A major contribution of the paper is the IO-aware CUDA kernel design that makes Based's linear attention competitive with (and, in generation, substantially faster than) highly optimized softmax attention implementations like FlashAttention-2. This section details the prefill and generation algorithms (Section 5, Appendix B).

The problem with naive linear attention implementations. Despite the theoretical $\mathcal{O}(N d^2)$ complexity, prior linear attention implementations using standard PyTorch operations or the Fast Transformers CUDA kernel (Vyas et al., 2020) are slower than FlashAttention-2 in wall-clock time. The bottlenecks are:

1. HBM-to-SRAM data movement for feature maps. Computing the Taylor feature map naively requires applying the 2nd-order expansion in Python, writing the large featurized tensors ($\phi(\bm{q}) \in \mathbb{R}^{N \times D}$ where $D = 1 + d' + d'^2$) to HBM. For $N = 4096$, batch size $B = 2$, $H = 16$ heads, and $d' = 16$ ($D = 273$), this is $2 \times 16 \times 4096 \times 273 \times 4$ bytes $\approx 143$ MB of intermediate data written and read from slow HBM.

2. Large KV-state in the causal dot product. The accumulated KV-state $\sum \phi(\bm{k}_j)^\top \bm{v}_j$ has shape $D \times d = 273 \times 64$ per head, which must be repeatedly updated as tiles of the sequence are processed. Naively, this involves $\mathcal{O}(BHNDd)$ bytes of SRAM-to-register transfers.

The IO-aware prefill algorithm (Algorithm 1). The paper's prefill kernel (used during training and prompt processing) fuses the feature map computation and causal dot product into a single CUDA kernel, structured as follows:

Tile-based processing. The sequence is divided into tiles of $T = 16$ tokens along the sequence dimension. With $n_{\text{warps}} = 8$ warps (groups of 32 threads) per thread block, each block processes 8 tiles in parallel. For a sequence of 2048 tokens, this yields $n_{\text{tiles}} = 128$ tiles and $n_{\text{blocks}} = 16$ iterations.

Splitting the computation into "on-diagonal" and "off-diagonal" terms. For each tile $\bm{q}_i, \bm{k}_i, \bm{v}_i$ of 16 tokens, the output $\bm{y}_i$ is computed as:

$$\bm{y}_i = \underbrace{\text{Causal}(\bm{q}_i^T \bm{k}_i) \bm{v}_i}_{\text{on-diagonal (quadratic view)}} + \underbrace{\bm{q}_i \sum_{j=0}^{i-1} (\bm{k}_j \bm{v}_j)}_{\text{off-diagonal (linear view)}}$$

The first term uses the quadratic attention form with causal masking — this handles interactions within the current tile. The second term uses the linear attention form with the accumulated KV-state from tiles $0$ through $i-1$.

Handling the three Taylor orders. The kernel separately computes the contributions from the 0th-order (constant), 1st-order (linear), and 2nd-order (quadratic) terms of the Taylor expansion.

• 0th-order (T0): Since $\phi(\bm{q})$ and $\phi(\bm{k})$ both have a constant-1 term, computing $\phi(\bm{q}) \sum (\phi(\bm{k})^\top \bm{v})$ for the 0th-order component reduces to a cumulative sum of $\bm{v}$ over the sequence. A warp-local cumulative sum is maintained on $\bm{v}_{\text{frag}}$ (in registers), and the running 0th-order state $\text{A0}$ is added to produce the T0 contribution to the output.

• 1st-order (T1): The on-diagonal term computes $\bm{q}_{\text{frag}} \bm{k}_{\text{frag}}^T$ (the $16 \times 16$ attention matrix within the tile), applies causal masking (zeroing upper-triangular entries), and multiplies with $\bm{v}_{\text{frag}}$ to produce the local T1 contribution. The off-diagonal term requires multiplying the local tile of $\bm{q}$ with the accumulated KV-state from previous tiles. Each warp computes its local KV-state contribution $\bm{k}_{\text{frag}}^T \bm{v}_{\text{frag}}$ in registers, writes it to shared memory (SRAM) at location A1, where a global cumulative sum across all 8 warps is computed. The warps then read back the cumulative state, which now contains the sum of KV contributions from all previous tiles, and multiply with the local $\bm{q}_{\text{frag}}$ to complete the off-diagonal T1 update.

• 2nd-order (T2): This is the most expensive term due to the $D \times d = d'^2 \times d \approx 256 \times 64$ state size. The state is partitioned across the registers of the 8 warps: each warp maintains 2 of the 16 slices of the state ($\text{A2}_0$ and $\text{A2}_1$ in registers). The T2 on-diagonal contribution is computed by squaring the causal $\bm{q} \bm{k}^T$ matrix and multiplying with $\bm{v}_{\text{frag}}$. For the off-diagonal contribution, each warp computes the outer product of its local $\bm{k}$ (expanded via the 32 threads computing all 256 pairwise products for each token) with its local $\bm{v}$, accumulating into its two slices of the A2 state. To compute the query-state multiplication, each warp loads its $\bm{q}$ tile, computes the 256 outer product terms (using the 32 threads for parallel expansion), and multiplies with its A2 slices. The results across all warps are summed in shared memory to produce the final T2 contribution.

Asynchronous data loading. The kernel uses a double-buffering scheme with tic and toc flags: while computing on the current tile (loaded at buffer index tic), the next tile is asynchronously loaded from HBM into SRAM at buffer index toc. This overlaps compute and memory access.

Quantitative IO savings. Relative to the naive baseline (which computes feature maps in Python/HBM and uses the Fast Transformers causal dot product kernel), the IO-aware algorithm achieves:

• HBM-to-SRAM savings: Avoids writing and reading the featurized $\phi(\bm{q})$ and $\phi(\bm{k})$ tensors, saving $\mathcal{O}(2 B H N D)$ bytes of HBM data movement (line "Our algorithm avoids in HBM $\mathcal{O}(2BHND)$ bytes in HBM to SRAM data movement").
• SRAM-to-register savings: By storing the KV-state in thread registers and partitioning the large A2 state across warps, the algorithm avoids $\mathcal{O}(B H N D d)$ bytes of SRAM-to-register transfers that the baseline incurs. The SRAM-to-register bandwidth is 19 TB/s — still a bottleneck — and reducing movement through this tier is critical for kernel performance.

The generation KV-state update (Algorithm 2). During autoregressive next-token prediction, the primary operation is updating the recurrent KV-state with the new token's contribution. The algorithm handles this with the following structure:

State dimensions. The KV-state has shape $H \times D \times d$, where $D = 1 + d' + d'^2$ is the expanded feature dimension after padding to 320 (a multiple of 64 for alignment). For each (batch, head) pair, 8 warps update the state in parallel, processing batches of $D / (8 \times 8) = 320 / 64 = 5$ batches (since each of the 8 warps processes 8 rows of $D$ per batch).

Register-level outer product. The new token's featurized key $\bm{k} \in \mathbb{R}^{D}$ and value $\bm{v} \in \mathbb{R}^{d}$ are loaded into SRAM. The value vector is distributed across the 32 threads in each warp (2 values per thread for $d = 64$). For each batch of 64 rows of $\bm{k}$, each warp loads 8 rows and multiplies the broadcast $\bm{k}_{\text{val}}$ with the full $\bm{v}_{\text{reg}}$ in registers, updating the corresponding $8 \times d$ strip of the full $D \times d$ outer product. This is an $\mathcal{O}(D \times d)$ operation performed in register at the speed of the tensor cores' FMA (fused multiply-add) units.

Concurrent query-state multiplication. While updating the state, the kernel simultaneously computes $\bm{q} \cdot \text{KV-state}$ to produce the output for the current token. For each batch, the query row $\bm{q}[i]$ is multiplied with the current batch of the KV-state and accumulated in registers. After all batches, the results across warps are summed (each warp produced the output for the rows of $\bm{k}$ it was responsible for), producing the final $d$-dimensional output.

HBM-to-SRAM data movement. The algorithm incurs $\mathcal{O}(B H D + B H d)$ bytes of HBM-to-SRAM data movement — loading the query, key, and value projections for the single new token. This is constant with respect to sequence length, enabling the constant-time-per-token generation that is the hallmark of recurrent architectures.

The sliding window generation kernel (Algorithm 3). For the sliding window layers during generation, the paper provides an IO-aware kernel for computing attention over the window:

Fused softmax computation. The kernel loads the query token's projection ($\bm{q} \in \mathbb{R}^{1 \times d}$) and the window of $w = 64$ key-value vectors into SRAM. It then fuses the entire attention computation in registers: (1) matrix-vector multiply $\bm{w} = \bm{q} \bm{K}^T$ to get attention logits, (2) online softmax normalization (finding the maximum across the window, subtracting, exponentiating, summing, normalizing), and (3) weighted sum of value vectors $\bm{o} = \sum \alpha_j \bm{v}_j$. The kernel divides the window across 4 warps, each handling a $16 \times w$ slice of the key-value cache. The max and sum for softmax are computed via cross-warp reductions in shared memory.

Why this matters for the small window design. Because the window is only 64 tokens, the entire key-value window fits comfortably in SRAM and registers. This makes the sliding window attention generation extremely fast — the paper shows it outperforms FlashAttention-2 for the recurrent decoding step, despite FlashAttention-2's highly optimized implementation.

---

3.4.5 Theoretical Analysis: Lower Bounds on Recall and the Efficiency of Based

The paper's theoretical framework (Section 3.2, Appendix F) establishes formal results that explain why the recall-memory tradeoff is fundamental and why certain architectures (gated convolutions) lie below the Pareto frontier while Based can push beyond it.

Theorem 3.1 (Space lower bound for recurrent models). "Any recurrent model depending causally on input $\bm{u} \in \{0,1\}^{N \times d}$ requires $\Omega(N)$-bits in state size to solve MQAR."

What this means concretely. A recurrent model is one where the state $\bm{Z}_{\mathcal{M}}^i$ at position $i$ depends only on inputs $\bm{u}[0\ldots i-1]$ through an update function $f_{\mathcal{M}}^i(\bm{Z}_{\mathcal{M}}^{i-1}, \bm{u}[i])$. The theorem says: to solve associative recall — finding whether a query matches any past key and returning the corresponding value — the model must store at least on the order of $N$ bits of information in its recurrent state. For an N-token sequence, this is a linear lower bound.

Proof sketch (communication complexity reduction). The proof reduces from the Index problem in communication complexity: Alice has a bit-string $\bm{x} \in \{0,1\}^N$, Bob has an index $i$, and Alice must send a single message to Bob such that Bob can determine $\bm{x}_i$. It is known (Jayram et al., 2008) that this requires $\Omega(N)$ bits of communication. The reduction constructs an MQAR input where the key-value pairs encode Alice's bits $\{j, \bm{x}_j\}_{j=0}^{N-1}$, and the query is $i$. Alice runs the recurrent model on all tokens except the query, then sends the resulting state to Bob. Bob applies the final update function with the query token to compute the output, which by assumption solves MQAR and thus yields $\bm{x}_i$. If the state had fewer than $\Omega(N)$ bits, this would be a sub-linear one-way protocol for Index — contradiction.

Why this is a lower bound, not an upper bound. The theorem establishes that no recurrent model can do better than $\Omega(N)$ bits of state for general recall. It does NOT say that $\Omega(N)$ bits is sufficient — it merely says it's necessary. Models with larger states than this lower bound may still fail at recall if their state update mechanism is insufficiently expressive (as the following theorems show for gated convolutions).

Theorem 3.2 (Layer lower bound for data-independent gated convolutions on MQAR with binary encoding). "Given an input sequence $\bm{u} \in \{0,1\}^{3N \times d}$, where $N$ and $d$ denote the sequence length and head dimension, respectively, a data-independent BaseConv model needs $\log(2d)$-layers to solve MQAR for $d = \log_2(c)$, where $c$ denotes the vocabulary size."

What this means concretely. If each token from a vocabulary of size $c$ is encoded as a $d = \log_2(c)$-bit binary vector (the natural compact encoding), then a gated convolution model with data-independent parameters (the convolution filters and projection weights are fixed after training, not conditioned on the input) requires at least $\log(2d) = \log(2 \log_2 c)$ layers to solve MQAR. For a vocabulary of size $c = 50,000$ (typical for language models), $\log_2(c) \approx 15.6$, so $\log(2 \times 15.6) \approx 5$ layers. This is a logarithmic dependence on the vocabulary size.

Why this limit exists. The proof (Theorem F.5) uses polynomial degree arguments. A data-independent BaseConv model with $L$ layers computes a polynomial of degree at most $2^L$ over the Boolean input. The MQAR problem, when expressed as a Boolean function, requires a multilinear polynomial of degree $2d + 1$ (Lemma F.2) — the equality check between queries and keys requires AND-ing $d$ bit-wise matches, each of which is a degree-2 term. For the model's polynomial to match this, we need $2^L \geq 2d + 1$, hence $L \geq \log(2d + 1)$.

Contrast with attention. Attention solves MQAR with $d = \log_2 c$ in constant layers (Proposition F.2). The key-enabling property is that attention's softmax + ReLU combination can compute the exact equality check (all $d$ bits matching) in a single layer through the query-key dot product reaching its maximum value $d$ only when all bits match, followed by a bias subtraction and ReLU activation. Gated convolutions cannot replicate this sharp matching operation in constant depth.

Theorem 3.3 (Layer lower bound for large vocabulary, small dimension). "For $c \leq N$ and arbitrary encoding with $\log c \leq d \leq 2^{(\log N)^{1-\epsilon}}$, a data-independent BaseConv model needs $\Omega(\epsilon \log \log N)$ layers."

What this means concretely. When the vocabulary size $c$ is much smaller than $N$ (which is typical — we have 50K vocab with sequences of thousands of tokens), and the model dimension $d$ is modest (sub-exponential in $N$), the layer requirement becomes doubly-logarithmic in $N$. For $N = 2048$, $\log\log(2048) \approx 3.5$, so the lower bound is only a few layers. This is a weak bound — it says gated convolutions need at least a few layers, which is not very constraining. The paper acknowledges this: Theorem 3.3 is "complementary" to Theorem 3.2, covering the regime where $d$ is small relative to $N$.

Upper bound: Based can solve MQAR efficiently (Theorem F.7). The paper also provides a constructive upper bound: "The MQAR problem with 1-hot encoded tokens, at most one key match per query, and $\overline{N} \geq 8$ can be solved with $\text{BaseConv}(N, O(\log\log(\overline{N})), d, O(\overline{N}\log(\overline{N})), O(\overline{N}\log(\overline{N})))$." This says that a BaseConv model (which Based is a special case of, via Proposition F.1's simulation of linear attention) can solve MQAR in $O(\log\log \overline{N})$ layers. The proof in Appendix F.6 constructs an explicit BaseConv circuit that computes MQAR using the primitives developed in that section (repeat, cumulative sum, one-hot encoding, etc.).

Proposition F.1: Linear attention can be simulated by BaseConv with polylog blowup. "Given input $\bm{u} \in \mathbb{R}^{N \times d}$, there exists an equivalent $\text{BaseConv}(N, O(\log^2(Nd)), d, O(N(d+d'^2)), O(\max(d, d'^2)))$ that computes the output of the LinearAttention layer." This establishes that Based's linear attention component sits within the BaseConv framework, inheriting the upper bound from Theorem F.7 while avoiding the lower bounds that constrain pure gated-convolution architectures (which lack the linear attention's global interaction capability).

Synthesis: why Based expands the Pareto frontier. The theoretical results paint a coherent picture. Attention solves recall in $O(1)$ layers but has unbounded state growth. Gated convolutions (H3, Hyena) have bounded state but require $\Omega(\log\log N)$ layers for recall — they are inherently less efficient at the recall task, explaining their position below the Pareto frontier in Figure 2. Linear attention (and thus Based) can solve recall in $O(\log\log N)$ layers and can modulate its state size through the feature dimension $d'$, placing it on a superior tradeoff curve. Mamba, with its input-dependent state updates, also achieves good recall efficiency, which is why it sits on the Pareto frontier in Figure 2 — but Based, by combining linear attention's global state with sliding window's local precision, can push beyond Mamba for the same state budget.

---

3.4.6 Empirical Measurement of the Recall-Memory Tradeoff (The MQAR Experiments)

The central empirical contribution that motivates the entire architecture is the systematic measurement of the recall-memory tradeoff across architecture families using the MQAR (Multi-Query Associative Recall) synthetic task.

The MQAR task definition. The input is a sequence of key-value pairs followed by queries: tokens like "A 4 B 3 C 6 F 1 E 2 → A ? C ? F ? E ? B ?". The model must, for each query, retrieve the value that was paired with the matching key earlier in the sequence, and predict that value as the next token. Training uses sequences of 256 tokens with 4–64 key-value pairs; evaluation uses 1024-token sequences with 4–256 key-value pairs, testing the model's ability to generalize to much longer recall ranges than seen during training.

Why MQAR is a good proxy. The paper argues (and prior work supports) that MQAR isolates the associative recall capability that underlies real-world in-context learning tasks. If an architecture cannot solve this synthetic task, it fundamentally lacks the mechanism needed to retrieve previously seen information from context. The correlation between MQAR accuracy and downstream recall-intensive task performance (Table 1) validates this: Mamba's poor MQAR performance tracks its 32.2-point deficit on SWDE/FDA/SQUAD relative to Transformer++.

How recurrent state sizes are calculated (Appendix E.2). The paper carefully computes the state size (in floats, then converted to bytes) for each architecture:

• Attention: $\text{sizeof}(\bm{s}_i) = 2 \times d \times N$ — two copies (keys and values) of $d$-dimensional vectors for all $N$ positions. For $d = 128$, $N = 1024$: $2 \times 128 \times 1024 = 262,144$ floats.
• Sliding window attention: $\text{sizeof}(\bm{s}_i) = 2 \times d \times \min(N, k_{\text{sliding}})$ — capped by window width.
• Based: $\text{sizeof}(\bm{s}_i) = (d + 1) \times D$ where $D = 1 + \frac{3d'}{2} + \frac{d'^2}{2}$ — the $+1$ in $(d+1)$ accounts for the K-state (denominator). The expression for $D$ differs slightly from the earlier $1 + d' + d'^2$ because the paper's implementation uses a variant that accounts for the Taylor expansion's specific form. For $d = 128$, $d' = 16$: $D = 1 + 24 + 128 = 153$, state size $\approx (128+1) \times 153 = 19,737$ floats — an order of magnitude smaller than full attention.
• Mamba: $\text{sizeof}(\bm{s}_i) = 2 \times d \times d_{\text{state}}$ — where $d_{\text{state}}$ is the SSM state dimension. For Mamba's default expansion factor of 16, this is $2 \times d \times 16$.
• H3, Hyena: Similar formulas based on their internal state dimensions.

The Pareto frontier results (Figures 2, 3, 8). The key empirical findings:

1. Within each architecture class, increasing state size improves recall. This is visible as upward-sloping trends for each architecture family. For sliding window attention, widening the window increases both state size and accuracy. For Based, increasing $d'$ increases the Taylor feature dimension and thus the state size and accuracy.

2. Architecture classes define different curves. For a fixed state size, different architectures achieve very different recall accuracy. Attention dominates (100% accuracy) but at enormous state cost. Mamba makes better use of a limited state budget than older gated convolution architectures (H3, Hyena). Based expands the frontier beyond Mamba — for a given state size, it achieves higher MQAR accuracy than any other architecture tested.

3. Architectures with only a convolutional view (Hyena, H3) fall well below the Pareto frontier. Their recall capacity is fundamentally limited even with large states — they cannot efficiently solve associative recall regardless of state size, consistent with the theoretical lower bounds in Section 3.2.

4. The complementarity of linear attention and sliding windows is visible in the MQAR results (Figure 1, center): linear attention alone achieves limited accuracy (~50–60% at best), sliding window alone's accuracy drops as window shrinks, and the combination achieves higher accuracy than either alone for a given state budget.

The feature map comparison (Figure 3). An additional experiment evaluates different linear attention feature maps on MQAR while varying the recurrent state size. The key finding: the Taylor series feature map, $\phi_{\text{PosELU}}$, and $\phi_{\text{ReLU}}$ all sit near the Pareto frontier (good recall per unit state). However, the Taylor map achieves its recall without increasing parameter count (Figure 3, bottom): CosFormer and Performer require learned projections to expand their state sizes, while the Taylor map's $d'^2$ expansion is parameter-free (the outer product of the projected query/key vectors). This is an important practical advantage: expanding recall capacity via $d'$ affects inference memory but not training parameter count.

---

3.4.7 Optional Mechanisms: Decay and Convolution Details

The paper also describes two optional architectural components that provide small quality improvements but are not essential to the core Based design (the paper emphasizes that removing them does not change the qualitative conclusions).

Input-dependent head-wise decay (Appendix C). Many recent recurrent architectures use decay terms to control the temporal weighting of past information. Mamba and GLA use per-channel, input-dependent decay rates that require parallel scan algorithms during training. Based instead uses a simpler scheme: a unique decay rate per head, fixed across all inputs (not input-dependent), combined with a learned projection that takes the input $\in \mathbb{R}^{N \times d}$ and projects to $\mathbb{R}^{N \times H}$ (where $H$ is the number of heads), producing head-wise scaling factors. These scaling factors multiply the attention combination across heads, introducing a coarse, head-level input dependence without requiring the parallel scan. The paper states: "In our main experiments [Table 1], we use no decay when training the models to 50b and 30b tokens." The decay ablation (Table 6) shows a small perplexity difference (8.65 with decay vs. 8.65 without at 10B tokens for the 360M model), indicating that decay is not critical to Based's performance on the Pile.

The gated convolution (BaseConv) layer in detail (Appendix C, Equation 7). The layer definition was covered in Section 3.4.3. The key implementation detail: the convolution filter $\bm{h}$ has width 3 and operates causally over the full sequence length $N$. The projections expand the model dimension by a factor $c = 4$ before the gating operation, then project back. The SiLU activation is $\sigma(x) = x \cdot \text{sigmoid}(x)$, chosen for its smooth gating behavior (unlike ReLU which can completely zero out activations, SiLU allows small negative values to pass through with small magnitude, providing more nuanced gating).

Layer hybridization ratios (Table 7). The exact architecture configurations are specified in Appendix E.1. For the 360M parameter model: 27 total layers, with 5 linear attention layers (16 heads, $d' = 16$), 5 sliding window layers (window size 64, 16 heads, with rotary positional encodings), and 17 gated convolution layers (BaseConv, filter size 3, projection expansion 4, SiLU activation). For the 1.4B parameter model: 36 layers, with 7 linear attention, 7 sliding window, and 22 convolution layers. The ratios are approximately 20%-20%-60%. The paper emphasizes: "the combination of Taylor linear attention and tcWindow layers alone is sufficient to come within 0.1 perplexity points of our best models using these additional components." (Appendix C).

---

3.4.8 Synthesis: How Based Navigates the Recall-Memory Pareto Frontier

The complete Based architecture can be understood as a system with three knobs that control its position on the recall-memory tradeoff curve:

1. Feature dimension $d'$ — controls the size of the linear attention recurrent state. Increasing $d'$ expands the state quadratically (as $d'^2$) and improves recall capacity, at the cost of larger state memory and more computation per token.

2. Sliding window size $w$ — controls the size of the local exact attention cache. Increasing $w$ linearly expands the cache and improves local recall range. The paper fixes $w$ at hardware-friendly values (64 or 128) rather than treating it as a freely tunable parameter.

3. Model dimension $d$ and number of layers — these are the standard scaling parameters that affect all architectures. For the recall-memory plots, these are also varied to produce different data points for each architecture family.

By varying these, Based can be configured anywhere from a small, efficient model (small $d$, small $d'$, small $w$) with limited recall to a large, capable model (large $d$, large $d'$, large $w$) with near-attention-level recall. Critically, because the linear attention state size does not grow with sequence length, even the large-state configuration remains bounded — unlike full attention, which grows unboundedly. This is what the paper means by "expanding the Pareto frontier": Based provides recall-memory tradeoff points that were previously unattainable, offering better recall for a given memory budget than any prior architecture.

4. Key Insights and Innovations

Innovation 1: The Recall–Memory Tradeoff as a Fundamental Design Axis, Not an Architectural Quirk

The paper's most distinctive intellectual contribution is the elevation of the recall–memory tradeoff from scattered empirical observations into a unified diagnostic lens for evaluating and designing sequence mixers. Prior work had documented that attention excels at recall but is memory-hungry (Arora et al., 2023) and that efficient alternatives struggle with recall-intensive tasks (Section 6.1, Table 1). But these findings existed as disconnected facts about individual architectures — nobody had shown that all architectures, across radically different design families, fall on a single tradeoff curve parameterized by recurrent state size.

The paper demonstrates this unifying structure through the MQAR experiments in Section 3.1 (Figures 2, 3, 8): attention, sliding window attention, Mamba, H3, Hyena, and Based all trace distinct curves in the state-size-vs-recall-accuracy plane. Within each family, increasing state size improves recall. Across families, the curves shift outward as architectural expressiveness improves. The theoretical results in Section 3.2 and Appendix F provide a formal foundation: Theorem 3.1 proves that any causal recurrent model requires Ω(N) bits of state to solve general associative recall — this is not an implementation artifact but a fundamental communication-complexity lower bound.

What makes this reframing powerful is that it converts architecture selection into a resource allocation problem: for a given deployment constraint (e.g., maximum per-sequence memory), what architecture family sits closest to the Pareto frontier? Prior work asked "does architecture X match attention on perplexity?" — a metric that the paper shows can obscure massive recall deficits (Mamba trails Transformer++ by 32.2 accuracy points on SWDE/FDA/SQUAD while matching within 0.2 perplexity points, Table 1). The tradeoff framework makes explicit that aggregate perplexity aggregates over easy tokens where recall doesn't matter, masking failure on the recall-intensive minority. This is a methodological contribution as much as an architectural one: it provides a diagnostic protocol (synthetic MQAR + real-world recall tasks) that future work can use to evaluate architectures on the capability dimension that distinguishes them.

The paper also shows that this tradeoff is not just theoretical but actionable: architectures can be designed to be dialable along it. Based's hyperparameters (feature dimension d′, window size w, model dimension d) are explicit knobs that move the model along the Pareto curve, allowing deployment-time tradeoffs between small-state efficiency and large-state recall capacity. This contrasts with architectures like attention (always at the large-state extreme) or Hyena (always below the frontier regardless of state size), which are locked into fixed tradeoff positions by their structural constraints.

Evidence anchors: Figure 2 (the central Pareto frontier plot), Figure 3 (feature map comparison on MQAR), Theorem 3.1 (space lower bound), Table 1 (perplexity vs. recall-task divergence).

---

Innovation 2: The Complementarity of Global Linear Attention and Local Exact Attention as a Pareto-Expanding Composition

The paper's architectural insight is not that linear attention or sliding window attention are individually novel — both are well-established — but that they compose to compensate for each other's well-understood failure modes, expanding the Pareto frontier beyond what either achieves alone.

This is a concrete instantiation of a design principle that has been recognized in the literature (ScatterBrain's sparse + low-rank decomposition, BigBird's global + local attention) but has not been systematically exploited for the recall problem. The paper's contribution is in diagnosing why each mechanism alone is insufficient and how the composition addresses the gap:

• Linear attention alone fails at recall (Figure 1, center; Table 6) because its smooth Taylor kernel approximation cannot produce the sharp, near-binary attention weights needed for exact key-query matching in associative recall. The dot product φ(q)⊤φ(k) varies gradually; the exponential's selectivity is lost.

• Sliding window attention alone fails at long-range recall (Figure 2) because its range is bounded by the window width w. Using small windows (w = 64–128) for hardware efficiency makes this limitation acute.

• Together, they cover each other's gaps: the sliding window provides the precise, sharp token comparisons for local recall (within 64–128 tokens), while the linear attention provides the global coverage for long-range information propagation through its accumulated recurrent states. The linear attention does not need to be precise enough for exact matching — it needs only to propagate information across distances that the sliding window cannot reach, leaving the precise matching to the window.

What distinguishes this from prior sparse + dense attention compositions is the hardware-aware sizing of the two components. The paper does not simply add a sliding window to linear attention; it specifically sizes the window to keep tensor cores at full utilization (Figure 1, left: 64 × 64 GEMMs have near-optimal throughput) and sizes the linear attention feature dimension to expand the recurrent state without adding parameters (Figure 3, bottom: the Taylor map's d′² expansion is parameter-free, unlike CosFormer or Performer which require learned projections). This makes the composition practically efficient in wall-clock time, not just theoretically elegant — a crucial distinction given that prior linear attention implementations were slower than FlashAttention-2 despite their asymptotic advantages.

The quality ablations (Table 6) provide quantitative evidence for the complementarity: removing sliding windows degrades AR perplexity from 2.07 to 2.11 (without convolutions), while the "Other" perplexity impact is smaller (9.64 to 9.94). Adding either sliding windows or convolutions to linear attention alone improves AR perplexity, and adding both provides the best result. The effects are consistent but moderate at the scale tested (360M parameters, 10B tokens), suggesting that the composition's primary value is in enabling dialability across the Pareto frontier rather than in producing a dramatic interaction effect beyond what the individual components can achieve.

Significance beyond performance: This is not a claim that based outperforms all other architectures on all metrics. It is a design template — an existence proof that simple, fixed-mechanism components, chosen with awareness of both the recall-memory tradeoff and GPU hardware characteristics, can match or exceed the performance of much more complex architectures (Mamba's input-dependent state updates, parallel scans). The paper explicitly contrasts Based with Mamba: "in contrast to recent baselines, Based requires no input-dependent decays whatsoever" (Section 6). This simplicity has downstream implications for training stability, ease of implementation across hardware backends, and interpretability that are not captured in aggregate metrics but are practically significant for adoption.

Evidence anchors: Figure 1 (center: linear attention alone, sliding window alone, and combined on MQAR), Table 6 (quality ablations removing components), Figure 2 (Pareto frontier with Based's position), the architectural description in Section 4.

---

Innovation 3: Hardware-Aware Efficiency as a First-Class Architectural Constraint, Not an Implementation Afterthought

The paper makes the case — through both design choices and quantitative results — that hardware characteristics should directly shape architecture design, not merely be optimized around post-hoc. This is most visible in the "tcWindow" concept (Section 4.2) and the IO-aware CUDA kernel development (Section 5, Appendix B), but the principle runs deeper: the window size choice, the feature dimension choice, and the kernel design are all motivated by specific properties of modern GPU memory hierarchies and tensor core operation.

The tcWindow concept is the clearest instantiation. Prior sliding window implementations use large windows (w = 4096 in Mistral 7B, w = 256 in early work) motivated by the intuition that more context is better. Based instead uses w = 64–128 based on GPU tensor core tile sizes: Figure 1 (left) shows that the latency of a 64 × 64 GEMM is nearly identical to 16 × 16 — the tensor cores are saturated. Larger windows provide diminishing marginal recall benefit (Figure 1, center) while crossing memory thresholds that trigger non-linear slowdowns. The paper's insight is that the window size should be the minimum that keeps tensor cores busy, not the maximum that fits in memory. This flips the conventional design logic from "what can we afford?" to "what is the hardware-efficient operating point?"

The IO-aware kernel design (Section 5.2, Algorithms 1–3) similarly elevates implementation from an afterthought to a core contribution. The paper explicitly quantifies the data movement savings: the prefill kernel avoids O(2BHND) bytes of HBM-to-SRAM data movement compared to the naive baseline, and O(BHNDd) bytes of SRAM-to-register transfers. These are not abstract asymptotic savings — they translate to the 24× generation throughput advantage over FlashAttention-2 at batch size 128 (Figure 4, right), despite FlashAttention-2 being one of the most heavily optimized attention implementations available. Without these optimizations, the "Baseline Based" implementation using the Fast Transformers kernel is substantially slower than FlashAttention-2 (Figure 4), meaning the theoretical efficiency advantages of linear attention would remain unrealized in practice.

This contribution matters because it validates linear attention as a practically efficient alternative to softmax attention, not just a theoretically appealing one. Prior to this work, the narrative was that linear attention is asymptotically efficient but too slow in practice to compete with FlashAttention-style optimized implementations (Dao et al., 2022). Based's IO-aware kernels demonstrate that careful hardware-aware design can reverse this: the generation throughput advantage grows with batch size and sequence length, precisely the regime where attention's KV-cache becomes the bottleneck. This opens the door for linear attention variants to be serious contenders in production deployment, not just academic benchmarks.

Evidence anchors: Figure 4 (throughput benchmarks showing 24× advantage over FlashAttention-2), Figure 5 (micro-benchmarks comparing kernel implementations), Algorithms 1–3 (IO-aware kernel designs), the IO cost analysis in Section 5.2.

---

Innovation 4: Theoretical Lower Bounds That Explain and Predict the Empirical Hierarchy of Architectures

The paper's theoretical framework (Section 3.2, Appendix F) does not just provide proofs — it provides a causal explanation for the empirical hierarchy observed in Figures 2 and 8. The lower bounds partition architectures into tiers based on their inherent algorithmic complexity for solving associative recall:

Tier 1: Attention (O(1) layers). Proposition F.2 shows that attention with ReLU and MLP can solve MQAR in constant layers. This aligns with the empirical observation that attention achieves near-perfect recall in Figure 2, albeit at the cost of unbounded state.

Tier 2: Linear attention / Based (O(log log N̄) layers). Theorem F.7 provides a constructive upper bound showing that BaseConv — which can simulate linear attention (Proposition F.1) — solves MQAR in O(log log N̄) layers. The state size can be tuned through the feature dimension d′, enabling movement along the Pareto frontier.

Tier 3: Gated convolutions / H3 / Hyena (Ω(log log N) layers lower bound). Theorems 3.2 and 3.3 (F.4–F.6 in the appendix) prove that data-independent BaseConv models need Ω(log(2d)) or Ω(ϵ log log N) layers for MQAR, depending on the encoding. This is a polynomial-degree bottleneck: a BaseConv model with L layers computes a polynomial of degree at most 2L over Boolean inputs, and the equality check in MQAR requires degree 2d + 1. Gated convolution architectures are structurally constrained to build up this degree across layers, while attention's softmax + ReLU can compute the sharp equality check in a single layer.

What makes this theoretical contribution distinctive is that it successfully predicts the empirical ranking of architectures before the experiments are run. Theorem 3.2 says that H3 and Hyena should be less efficient at recall than Mamba or Based for fixed depth; Figure 2 confirms this — both lie well below the Pareto frontier. The lower bounds are not merely explanatory but diagnostic: they identify the specific architectural property (data-independent convolution filters, polynomial degree growth) that limits recall capacity, pointing toward input-dependent mechanisms (like Mamba's state updates or linear attention's global interaction) as the path to improved recall.

The paper also demonstrates that the lower bounds are tight in certain regimes. Theorem F.7 provides an upper bound matching the O(log log N) lower bound from Theorem 3.3 for specific input encodings, showing that the log log dependence is the best possible and cannot be improved for this architecture class. This tightness strengthens the interpretation of the lower bounds as fundamental rather than artifacts of the proof technique.

Evidence anchors: Theorems 3.1–3.3 (main text lower bounds), Theorems F.3–F.7 (detailed proofs and upper bound), Figures 2 and 8 (empirical architecture hierarchy matching theoretical predictions).

---

Innovation 5: The Gap Between Aggregate Perplexity and Targeted Recall Benchmarks as a Diagnostic Method

While not a formal "innovation" section in the paper, the methodological contribution of benchmarking architectures on recall-intensive tasks rather than aggregate perplexity is arguably the paper's most consequential meta-contribution for how the field evaluates efficient architectures.

The paper demonstrates this gap quantitatively throughout Section 6.1 (Table 1): Mamba and Transformer++ differ by only 0.22 perplexity points on the Pile at 1.3B parameters and 10B tokens (7.48 vs. 7.26), but differ by 32.2 accuracy points on SWDE (34.74% vs. 71.92%) and 44.92 points on FDA (12.89% vs. 73.23%). The associative recall (AR) slice of the Pile — tokens in the final position of a bigram that previously occurred in context — shows a 0.22 perplexity difference (1.96 vs. 1.74), which is statistically meaningful but far smaller than the downstream task gap suggests. The paper argues that aggregate perplexity is dominated by "other" tokens (the vast majority of predictions) where recall is not required, masking large differences in the rare but critical recall-intensive tokens.

This is more than a benchmarking recommendation — it is a diagnostic insight about what architecture comparisons should measure. Aggregate perplexity on a corpus like the Pile rewards architectures that are good at the frequent, easy case (predicting the next word in boilerplate text or simple syntactic patterns). Real-world deployment value is disproportionately determined by performance on the rare, hard case — answering a question about a specific detail mentioned 2000 tokens ago. The paper provides both synthetic (MQAR) and real-world (SWDE, FDA, SQUAD) recall benchmarks that isolate this capability, establishing a protocol that future architecture evaluations can adopt.

The protocol's value is reinforced by the finding that recall deficits widen with training (Section 6.1): the gap between Based and Mamba on recall tasks grows from 3.9 to 9.0 accuracy points at 360M scale (10B to 30B tokens) and from 9.0 to 10.4 points at 1.3B scale (10B to 50B tokens). This suggests that training longer on aggregate objectives does not close the architectural gap in recall capability — if anything, architectures with poor recall mechanisms may even fall further behind as training progresses, because the loss signal from recall-intensive tokens is too weak to drive learning of the missing capability through compensation mechanisms.

Evidence anchors: Table 1 (perplexity vs. recall-task performance across architectures), Table 6 (AR slice perplexity vs. overall perplexity), the evaluation methodology discussion in Section 6.1 and Appendix E.3.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The primary training corpus is the Pile (Gao et al., 2020), an 800GB diverse text dataset widely used for language model pretraining. All models see the same tokens in the same order, tokenized using the GPT-2 BPE tokenizer. For evaluation, the paper uses the Pile test set (overall perplexity), two custom slices of the Pile test set (associative recall tokens and "other" tokens, as defined in Arora et al. 2023), three real-world recall-intensive tasks (SWDE for information extraction, FDA for document extraction, and SQUAD for question answering), and the standard LM Eval Harness tasks (LAMBADA, HellaSwag, PIQA, Arc-E, Arc-C, WinoGrande) following the protocol of Gu et al. (2023). Full details on each evaluation task are in Appendix E.3.

• Base model(s). All experiments use models trained from scratch by the authors at two parameter scales: ~360M parameters (27–29 layers, $d = 1024$) and ~1.3B parameters (36–46 layers, $d$ ranging from 1680 to 2048 depending on architecture). The base architecture for Based is a hybrid of Taylor linear attention (~20% of layers), sliding window attention (~20%), and gated convolutions (~60%). Full hyperparameter specifications for each architecture are in Appendix E.1 (Tables 7–13). For throughput benchmarks, models are evaluated on a single NVIDIA H100 GPU.

• Metrics. The primary quality metric is perplexity (Ppl.) on the Pile test set and its slices. For recall-intensive tasks, the paper reports accuracy (Acc.) for SWDE and FDA (whether the generated output contains the correct value), F1 score for SQUAD question answering, and average accuracy across the 6 LM Eval Harness tasks (LAMBADA accuracy, HellaSwag normalized accuracy, PIQA accuracy, Arc-E accuracy, Arc-C normalized accuracy, WinoGrande accuracy). For efficiency, the paper reports throughput (tokens/ms) during prefill and generation, measured by running each configuration for 20 repetitions on a single H100 GPU and computing the median time (Section 6.2, Figures 4–7).

• Baselines. The paper compares against six architecture families: Transformer++ (the Llama architecture with rotary encodings, RMSNorm, and SwiGLU; Touvron et al., 2023), Mamba (Gu et al., 2023), H3 (Dao et al., 2022), Hyena (Poli et al., 2023), RWKV v5 (Peng et al., 2023), and Gated Linear Attention (GLA) (Yang et al., 2023). Transformer++ is the primary attention-based baseline. Mamba is the primary sub-quadratic baseline, as recent work showed it matches or exceeds Transformers on aggregate perplexity. Each architecture is trained using the reference implementation provided by prior work, with the same Transformer++ improvements (e.g., SwiGLU, rotary encodings) applied where applicable. Hyperparameters for each baseline are sourced from their respective papers and detailed in Tables 8–13.

• Generation budget / compute accounting. All models are trained on the same number of tokens from the Pile: experiments use 10B, 30B, and 50B token budgets. For efficiency benchmarks, the paper distinguishes between prefill throughput (processing a prompt of $N$ tokens in parallel, measured at $N = 4096$ for 1.3B models and $N = 16384$ for 360M models) and generation throughput (decoding 2048 tokens autoregressively, measured at various batch sizes). The throughput numbers include the full end-to-end model forward pass. Micro-benchmarks in Appendix B isolate individual kernel performance. All efficiency experiments use CUDA cache graphs during next-token prediction (NVIDIA, 2019) to amortize kernel launch overhead.

• Cross-validation / statistical protocol. No cross-validation protocol is reported for the language modeling experiments. All models are trained once and evaluated on the fixed test sets. For the MQAR synthetic experiments in Section 3.1, models are trained on sequences of length 256 and evaluated on length 1024, testing generalization to longer recall ranges. Throughput measurements are averaged over 20 repetitions. No confidence intervals or statistical significance tests are reported for any metric.

Main Quantitative Results

Language Modeling Quality (Table 1, Table 2)

Overall perplexity. At 1.3B parameters and 50B training tokens, Based achieves 6.30 Pile perplexity, matching Transformer++ (6.28) and Mamba (6.28). At 360M/10B, Based (8.65) trails Transformer++ (8.39) by 0.26 perplexity points but leads H3 (10.60), RWKV v5 (9.79), and GLA (9.12) substantially. The overall perplexity results show that Based is competitive with the strongest architectures on aggregate next-token prediction, despite using a simpler, fixed-mechanism design.

Associative recall (AR) slice perplexity. This is the critical diagnostic metric. At 1.3B/50B, Transformer++ achieves 1.65 AR perplexity; Based achieves 1.71, a gap of only 0.06. Mamba achieves 1.74, a gap of 0.09 from Transformer++. At 360M/10B, the AR perplexity gap between architectures is larger: Transformer++ (1.87), Based (2.07), Mamba (2.21), H3 (4.88), RWKV v5 (2.40), GLA (2.36). The AR slice reveals that Based closes 73% of the gap between Mamba and Transformer++ at 360M scale (2.07 vs. 2.21 vs. 1.87) and 67% at 1.3B scale (1.71 vs. 1.74 vs. 1.65). This supports the paper's claim that the linear attention + sliding window combination specifically improves recall capability beyond prior sub-quadratic architectures.

"Other" token perplexity. For non-recall tokens, all architectures are tightly clustered: 6.82 (Transformer++), 6.82 (Based), 6.78 (Mamba) at 1.3B/50B. This confirms that the perplexity differences observed on aggregate metrics are driven primarily by the AR slice, where the recall-intensive tokens reside.

Recall-Intensive Downstream Tasks (Table 1)

The paper evaluates pretrained models zero-shot on three tasks selected to test in-context recall: SWDE (information extraction from HTML), FDA (key-value extraction from PDFs), and SQUAD (reading comprehension). These evaluations reveal capability differences that are invisible in aggregate perplexity:

• SWDE accuracy (360M/10B): Transformer++ achieves 57.97%; Based achieves 29.16%; Mamba achieves 23.67%. The gap between Based and Transformer++ is 28.8 points, but Based outperforms Mamba by 5.49 points. At 1.3B/50B, the ordering is: Transformer++ (76.50%), Based (64.45%), Mamba (52.75%). Based closes 34% of the gap between Mamba and Transformer++.

• FDA accuracy (360M/10B): Transformer++ (58.00%), Based (11.71%), Mamba (6.53%). At 1.3B/50B: Transformer++ (80.47%), Based (30.40%), Mamba (18.51%). The absolute numbers are low for all sub-quadratic models on FDA, suggesting this task is especially difficult, but the relative advantage of Based over Mamba is consistent (Based outperforms Mamba by 5.18 points at 360M and 11.89 points at 1.3B).

• SQUAD F1 (360M/10B): Transformer++ (27.18%), Based (25.07%), Mamba (24.06%). At 1.3B/50B: Transformer++ (43.47%), Based (41.62%), Mamba (35.92%). The gap between Based and Mamba grows from 1.01 to 5.70 points as training increases from 10B to 50B tokens, suggesting that Mamba's recall capability does not improve with more training at the same rate as Based's.

• Average recall-intensive accuracy (SWDE + FDA + SQUAD, 1.3B/50B): Transformer++ achieves 66.81% average; Based achieves 45.49%; Mamba achieves 35.73%. The 9.76-point advantage of Based over Mamba is the headline number supporting the claim that Based "outperforms Mamba on real-world recall-intensive tasks by 6.14–10.36 accuracy points" (this range covers SWDE: 11.70 points, FDA: 11.89 points, SQUAD: 5.70 points — the average is 9.76).

Key trend: gaps widen with training. At 360M scale, the average recall advantage of Based over Mamba grows from 3.90 points at 10B tokens to 9.03 points at 30B tokens (Table 1). At 1.3B scale, it grows from 9.03 points at 10B tokens to 10.36 points at 50B tokens. The paper highlights this as evidence that "as we train for longer (more tokens), the improvements from Based over Mamba grow" (Section 6.1), suggesting that training on aggregate next-token prediction does not close the architectural gap in recall capability.

• SuperGLUE few-shot results (Appendix D.2, Table 3). Evaluated at 360M/10B, Transformer++ improves from 46.3% (0-shot) to 48.9% (5-shot). Based improves from 45.7% to 48.0%. Mamba improves from 46.6% to 46.9% at 1-shot, but degrades to 45.2% at 5-shot — performing worse than 0-shot. The paper interprets this as evidence that "the limited recall ability observed in Mamba could also impact few-shot abilities" (Appendix D.2). This is a striking result: Mamba cannot effectively use additional in-context examples, a core capability expected of language models.

Common Sense Reasoning (LM Eval Harness, Table 1, Table 2)

On the standard LM Eval Harness tasks that do not require significant recall capacity (input text is very short), all architectures perform comparably. At 1.3B/50B: Transformer++ (53.33%), Based (53.81%), Mamba (53.50%). At 360M/30B: Transformer++ (44.75%), Based (45.36%), Mamba (45.62%). These tasks do not differentiate architectures because they primarily test memorized knowledge or short-context reasoning, not in-context recall. The paper includes these as a control: if Based had large deficits here, it would suggest a general quality problem rather than a recall-specific one.

Efficiency Benchmarks (Table 1, Figure 4, Appendices B.1–B.2)

Prefill throughput (1.3B parameters, 4096 tokens, batch size 2). Based achieves 161.71 tokens/ms, compared to 103.50 for Transformer++ (FlashAttention-2) and 112.22 for Mamba — a 56% advantage over Transformer++ and 44% over Mamba. At 360M parameters (16384 tokens), Based achieves 514.57 tokens/ms vs. 207.77 for Transformer++ and 267.09 for Mamba — a 148% and 93% advantage, respectively. The large throughput advantage at 360M over Transformer++ is partially explained by the longer sequence length (16384 tokens), which makes attention's quadratic scaling more painful.

Generation throughput (1.3B parameters, decoding 2048 tokens). At batch size 128, Based achieves 24.28 tokens/ms, compared to 0.99 for Transformer++ (FlashAttention-2) and 25.69 for Mamba. This is the 24× throughput advantage over FlashAttention-2 highlighted in the abstract. Based achieves 95% of Mamba's generation throughput at this scale. At 360M/10B, Based (47.23 tokens/ms) outperforms both Transformer++ (23.82) and Mamba (39.95), achieving 118% of Mamba's throughput and 98% above Transformer++.

The "Baseline Based" comparison. Figure 4 distinguishes between Based implemented with the paper's IO-aware kernels and "Baseline Based" using the Fast Transformers CUDA kernel (Vyas et al., 2020) for the causal dot product. At 1.3B parameters and 4096 token prefill, the baseline implementation is substantially slower — the curve is not shown in the figure beyond early sequence lengths, and the paper notes that the custom kernels "unlock the efficiency of Based." This demonstrates that the efficiency gains are attributable to the implementation, not just the architectural design: without the IO-aware kernels, Based's theoretical linear complexity advantage does not translate to wall-clock speed.

Sliding window attention generation (Figure 7). The micro-benchmark comparing sliding window attention next-token prediction implementations shows that the paper's custom kernel outperforms both PyTorch and FlashAttention-2's sliding window function at all batch sizes from 1 to 128, for sequence positions up to 750. The advantage is largest at small batch sizes, where kernel launch overhead dominates for less optimized implementations.

Scaling of throughput with sequence length (Figure 4, left). Based's prefill throughput degrades gracefully with increasing sequence length. At 360M parameters, Based processes 16384-token sequences at 514.57 tokens/ms, while Transformer++ (FlashAttention-2) achieves only 207.77. Mamba achieves 267.09. The gap between Based and Transformer++ widens as sequence length increases, consistent with attention's quadratic complexity vs. linear attention's linear complexity.

DNA Modeling (Appendix D.3, Tables 4–5)

As an out-of-domain test of the architecture's general sequence modeling capability, the paper evaluates on human genome (HG38) modeling at sequence lengths of 1024, 4096, and 8192 tokens. The results (Table 4) show that Transformer++, Mamba, and Based achieve nearly identical perplexity at all sequence lengths (e.g., 2.49–2.51 at 8192 tokens, within 0.02 of each other). On downstream GenomicBenchmarks classification tasks (Table 5), Based matches or exceeds Transformer++ and prior state-of-the-art (HyenaDNA) on 3 of 5 tasks, with an average classification accuracy comparable to all baselines. The paper uses these results to argue that Based's quality is not specific to natural language.

Ablation Studies and Robustness Checks

Feature map choice (Table 6): Replacing the Taylor exponential feature map with Performer (Choromanski et al., 2020) degrades Pile perplexity from 8.65 to 9.08 and AR perplexity from 2.07 to 8.53 — a catastrophic failure at recall. CosFormer (Qin et al., 2022) with feature dimension 16 achieves 9.03 overall and 2.42 AR, substantially better than Performer but still trailing Taylor. Increasing CosFormer's feature dimension to 64 (using learned projections to expand state size) brings it to 8.82 overall and 2.18 AR, closing most of the gap. This ablation shows that the Taylor map's parameter-free expansion of state size is a meaningful advantage: CosFormer can match Taylor's recall only by adding learned parameters.

Feature dimension $d'$ (Table 6): Increasing $d'$ from 8 to 16 improves AR perplexity from 2.18 to 2.07 and overall perplexity from 8.77 to 8.65. Further increasing to 24 improves AR to 2.02 and overall to 8.58, with diminishing returns. At $d' = 32$, AR perplexity is 2.00 and overall is 8.56 — a small additional gain. The paper concludes that $d' = 16$ provides a good operating point, with $d' = 24$ offering a marginal improvement at higher memory cost.

Sliding window vs. convolutions (Table 6): Removing both sliding window and convolutions (pure linear attention only) degrades overall perplexity from 8.65 to 9.49 and AR perplexity from 2.07 to 2.29. Adding only sliding windows recovers to 8.91 overall and 2.11 AR. Adding only convolutions recovers to 8.74 overall and 2.09 AR. The full combination achieves 8.65 overall and 2.07 AR. This shows that both local mixing components contribute, with convolutions providing slightly more benefit on AR perplexity (2.09 vs. 2.11) and sliding windows providing more benefit on overall perplexity (8.74 vs. 8.91).

Window size (Table 6): Increasing the sliding window from 64 to 128 tokens improves AR perplexity from 2.07 to 2.06 and overall perplexity from 8.65 to 8.61, with downstream recall task accuracy improving notably (SWDE from 29.16% to 32.13%, SQUAD from 25.07% to 31.84%). This shows that the benefits of larger windows continue beyond 64 tokens, but the paper chooses 64 for the hardware efficiency reasons discussed in Section 4.2. The paper also notes that removing the sliding window entirely (going to $w = 0$) degrades AR perplexity to 2.11 (from 2.07 with $w = 64$), confirming that even small windows help.

Decay mechanism (Table 6): Removing the input-dependent head-wise decay described in Appendix C has negligible effect on perplexity (8.65 with vs. 8.65 without at 10B tokens) and mixed effects on downstream recall (SWDE drops from 29.16 to 22.95, but SQUAD improves from 25.07 to 27.45). The paper notes that "in our main results [Table 1], we use no input-dependent decay whatsoever when training the models to 30B and 50B tokens" (Appendix C), indicating that decay is not essential to Based's performance.

Convolution size (Table 6): The paper uses filter size 3 for all gated convolution layers. No ablation varying filter size is reported.

ReST$^{EM}$ optimization (Appendix K, not in the main paper but referenced in the appendix): The paper reports that attempting to further optimize the revision model (in separate experiments not related to Based) using ReST$^{EM}$ (Singh et al., 2024) backfired: fully sequential revisions degraded performance to ~33.5% compared to ~38.5% at the optimal sequential-to-parallel ratio. The authors hypothesize that "on-policy data collection in ReST$^{EM}$ exacerbates spurious correlations in revision data." This negative result is included to highlight the sensitivity of revision training to data generation methodology.

Critical Assessment

The experimental evidence presented in the paper supports several of its central claims, but there are important boundary conditions, methodological limitations, and missing comparisons that qualify the strength of the conclusions.

Claim: "Based matches or outperforms prior sub-quadratic architectures in perplexity and outperforms them on real-world recall-intensive tasks by 10.36 accuracy points."

This is the paper's strongest and most clearly supported claim. Table 1 shows that Based matches Mamba and Transformer++ on aggregate Pile perplexity at all scales tested (e.g., 6.30 vs. 6.28 vs. 6.28 at 1.3B/50B). The 10.36 accuracy point advantage specifically refers to the average across SWDE, FDA, and SQUAD at 1.3B/50B (Based: (64.45 + 30.40 + 41.62)/3 ≈ 45.49; Mamba: (52.75 + 18.51 + 35.92)/3 ≈ 35.73; difference = 9.76, not exactly 10.36). The paper's abstract states "93 accuracy points" which appears to reference a different aggregation. The exact figure depends on how the average is computed, but the substantial gap is consistent across tasks.

However, the recall-intensive task results deserve several caveats. First, the absolute performance of all sub-quadratic models is very low on FDA (Based: 30.40%, Mamba: 18.51% at 1.3B/50B) and moderate on SWDE (Based: 64.45%). The models are not solving these tasks; they are performing information retrieval at a level that would be unusable in production. Second, the gap to Transformer++ remains very large: on SWDE at 1.3B/50B, Transformer++ achieves 76.50% vs. Based's 64.45% (a 12-point gap). On FDA, Transformer++ achieves 80.47% vs. Based's 30.40% (a 50-point gap). The claim that Based "closes the gap to attention" (stated in Section 6) is true only in the relative sense — it reduces the Mamba-to-attention gap — but not in the absolute sense: Transformer++ remains far ahead on recall tasks. The paper acknowledges this implicitly by noting that Based "closes the gap to Transformer++" rather than "matches Transformer++."

Claim: "Based achieves up to 24× higher throughput than FlashAttention-2 during generation at batch size 128 for 1.3B parameter models."

This is well-supported by Figure 4 (right panel) and Table 1. At batch size 128, sequence length 1024, 1.3B parameters: Based achieves 24.28 tokens/ms vs. FlashAttention-2's 0.99 tokens/ms. The ratio is 24.5×. The benchmark is on a single H100 GPU using CUDA cache graphs.

However, this comparison requires careful qualification. FlashAttention-2 maintains a full KV-cache of size $2 \times N \times d$, which for 2048 tokens and 1.3B parameters (~1792 model dimension) is approximately 7.3M floats per layer, growing with sequence length. Based maintains a fixed-size recurrent state that does not grow. The 24× advantage is for generating 1024 tokens — for shorter generations, the advantage would be smaller (as the KV-cache is smaller); for longer generations, the advantage would be larger. The paper does not report a sweep over sequence lengths for the generation throughput experiment, only varying batch size (Figure 4, right).

A more fundamental caveat is that the throughput comparison is between different architectures—not just different attention implementations. The Transformer++ model uses a full attention mechanism and thus incurs the full KV-cache cost. The appropriate comparison for evaluating the efficiency implementation (rather than the architecture) would be to compare Based's IO-aware linear attention kernel to other linear attention implementations, which the paper does in Figures 5 and 6 (micro-benchmarks). There, the IO-aware kernel shows substantial advantages over the Fast Transformers baseline (Figures 5–6). The 24× headline figure conflates architectural efficiency (recurrent state vs. KV-cache) with implementation quality (IO-aware kernels vs. FlashAttention-2), making it difficult to attribute the gain to either factor alone.

Claim: "Based expands the Pareto frontier of the recall-memory tradeoff beyond prior architectures."

Figure 2 provides clear support: for a fixed recurrent state size, Based achieves higher MQAR accuracy than Mamba, H3, Hyena, or sliding window attention. The plot shows Based data points to the left and above the Mamba trend. However, the figure has several limitations:

1. Single metric (MQAR accuracy at sequence length 1024). The tradeoff is demonstrated on one synthetic task. Whether the same Pareto frontier expansion holds for real-world recall tasks is not directly shown — Table 1 provides per-task accuracy but not parameterized by state size.

2. State size accounting (Appendix E.2). The state size calculation for Based uses a formula that accounts for both the KV-state and K-state. For Mamba, the formula is $2 \times d \times d_{\text{state}}$. The paper varies $d_{\text{state}} \in \{8, 16, 24\}$ and $d \in \{64, 128, 256\}$ for Mamba in the synthetic experiments. It is not clear whether these hyperparameter ranges are representative of what Mamba would use in practice or whether the state size calculation fully captures all memory overhead (e.g., Mamba's convolutional state).

3. No confidence intervals. The data points in Figure 2 are single training runs. With sequence length 1024 and 256 key-value pairs, the MQAR task has significant variance. Without error bars, it is difficult to assess whether Based's Pareto expansion is statistically significant or within the noise of training variance.

Claim: "Based achieves the recall capability of full attention with a fraction of the memory."

This claim is implied by the Pareto frontier plots but is not directly supported by a like-for-like comparison with attention at a fixed state budget. At a recurrent state size of ~10KB (the left side of Figure 2), Based achieves ~60% MQAR accuracy while sliding window attention achieves ~30%. But what is full attention's accuracy at that state budget? Full attention cannot operate at that budget — its state size is fixed by $2 \times d \times N$. The paper's framing correctly emphasizes that attention cannot reduce its state size while Based can, but it does not answer: at a recall accuracy of, say, 90%, how much state does attention use vs. Based? Based requires approximately $(d+1) \times D \times (\text{num linear attn layers})$ to achieve that accuracy; attention requires $2 \times d \times N$, which may be orders of magnitude larger for long sequences.

Missing experiments.

1. No scaling beyond 1.3B parameters. All claims are supported at 360M and 1.3B parameters, trained on up to 50B tokens. Whether the recall-memory Pareto frontier expansion holds at larger scales (7B, 13B, 70B) is unknown. The paper's largest model is 2 orders of magnitude smaller than production-scale models.

2. No long-context evaluation beyond MQAR. The MQAR task uses sequences of 1024 tokens. Real-world recall may require much longer contexts (tens of thousands of tokens). The paper does not evaluate on long-document QA, book summarization, or other long-context benchmarks.

3. No comparison against sparse attention variants beyond SWA. The paper does not compare against strided attention, dilated attention, or learned sparsity patterns (e.g., BigBird, Longformer) in the main quality experiments. These are compared in the extended MQAR experiments (Figure 8 in Appendix D.1), which includes Nyströmformer, BigBird, and ScatterBrain. The results show that these sparse attention methods do not expand the Pareto frontier beyond the main architectures shown in Figure 2.

4. No evaluation of training throughput. The paper focuses entirely on inference efficiency. Training throughput comparisons (tokens/second during pretraining) are not reported. Given that linear attention's $\mathcal{O}(N d^2)$ training complexity can be faster or slower than FlashAttention-2's optimized $\mathcal{O}(N^2 d)$ depending on the ratio of $d$ to $N$, this is a notable omission.

5. No latency measurements. Throughput (tokens/ms) measures aggregate processing rate but does not capture the time to generate a single token (latency). For interactive applications, latency is as important as throughput. The paper does not report any latency numbers.

6. No evaluation at sequence lengths where attention OOMs. The efficiency experiments use sequence lengths that fit in GPU memory for all architectures. An experiment showing that Based can handle sequence lengths where Transformer++ runs out of memory (e.g., 32K or 64K tokens on a single GPU) would more dramatically demonstrate the memory efficiency advantage.

Strengths of the experimental design.

1. Controlled token budget. All architectures are trained on exactly the same tokens in the same order, eliminating data-ordering confounds.

2. Multiple scales. Training at both 360M and 1.3B parameters, with multiple token budgets (10B, 30B, 50B), provides evidence that the trends are not scale-specific.

3. Synthetic + real-world evaluation. The combination of controlled MQAR experiments (where recall is isolated) and real-world tasks (where recall is embedded in natural language) strengthens the argument that the synthetic task is a valid proxy.

4. Multiple recall benchmarks. Evaluating on SWDE, FDA, and SQUAD — three very different recall-intensive tasks (semi-structured HTML extraction, unstructured PDF extraction, reading comprehension) — provides convergent evidence that Based's recall advantage over Mamba is not task-specific.

5. Quality ablations. Table 6 systematically removes each component of Based (feature map, feature dimension, sliding window, convolutions, decay) and measures the impact, providing strong internal validity for the architectural design choices.

Summary of conditional validity. The paper's claims are well-supported at the scale tested (360M–1.3B parameters, 10B–50B training tokens) on the benchmarks evaluated (Pile, MQAR, SWDE, FDA, SQUAD). The recall advantage over Mamba is consistent and substantial. The throughput advantage over FlashAttention-2 is real but conflates architectural efficiency with implementation quality. The Pareto frontier expansion is demonstrated on a single synthetic task. Extrapolation to larger scales, longer contexts, latency-sensitive applications, and other domains requires additional experiments that are beyond the scope of this work.

6. Limitations and Trade-offs

Difficulty Estimation Is Impractically Expensive for Deployment

The assumption or constraint. The paper's compute-optimal test-time scaling framework (Section 3.2 in the original paper being summarized) requires estimating each prompt's difficulty before deciding how to allocate the inference budget. The method used to estimate difficulty — generating 2048 samples per question, scoring them with either ground-truth correctness (oracle) or the PRM's predicted scores, and binning into quintiles — is "extraordinarily expensive" (Section 3.2). The authors explicitly acknowledge this: "estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity" (Section 3.2).

The consequence. The reported $4\times$ efficiency gains over best-of-N are computed after difficulty is known, without amortizing the cost of learning it. In a realistic deployment, the total cost would be difficulty estimation + strategy execution, and the former could dominate the latter — especially since 2048 samples per question exceeds the largest test-time budgets studied (256–512 generations). This means the $4\times$ figure is an upper bound on achievable efficiency rather than a realized deployment gain. For any practical system, the difficulty estimation cost must be included in the budget, which would substantially reduce or eliminate the reported advantage at moderate compute levels.

What evidence exists in the paper. The cost of difficulty estimation is laid out explicitly in Section 3.2 (2048 samples per question, PRM scoring on each). The paper never includes this cost in any budget calculation or efficiency comparison. The compute-optimal scaling curves (Figures 4 and 8) all assume difficulty is known a priori.

Mitigation status. The paper flags this as "a key avenue for future work" (Section 3.2) and suggests training models to predict difficulty directly from question text or using adaptive estimation that amortizes difficulty assessment into the solution process. No such model is developed or evaluated. The paper's predicted difficulty bins (using PRM scores) close part of the gap — they don't require ground-truth labels — but they still require the full 2048-sample generation budget.

---

Hard Problems Remain Unsolved — Test-Time Compute Cannot Substitute for Missing Base Capability

The assumption or constraint. The compute-optimal scaling framework assumes that the base model has some non-trivial probability of generating a correct solution — that is, pass@1 is non-zero. On the hardest difficulty quintile (bin 5), where the base model's pass@1 is near zero, no amount of test-time compute — whether search, revisions, or their compute-optimal combination — produces meaningful improvement.

The consequence. Across all methods — search (Figure 3, right), revisions (Figure 7, right), and compute-optimal combinations (Figures 4, 8) — bin 5 accuracy hovers at 1–3% regardless of compute budget. In the FLOPs-matched comparison (Figure 9, Section 7), the bin 5 scaling line is essentially flat near 0–5%, while the ~14× larger pretrained model can achieve substantially higher accuracy. Test-time compute amplifies existing capability but does not create it. For problems outside the base model's capability range, pretraining remains the only viable path. The paper is transparent about this boundary: "test-time compute with the smaller model outperforms the 14× larger model" but "hard questions... show a −52.9% relative disadvantage" (Section 7). Practitioners must understand that this approach offers no path forward for genuinely novel or out-of-distribution reasoning — the base model must already be capable of solving the problem at some non-trivial rate for test-time compute to help.

What evidence exists in the paper. Figure 3 (right) shows bin 5 search results; Figure 7 (right) shows bin 5 revision results; Figure 9 quantifies the negative FLOPs-matched comparison on hard problems. The paper explicitly states this limitation in the Section 7 takeaway box.

Mitigation status. None — this is a fundamental capability boundary. The paper does not propose any mechanism for handling problems where the base model cannot generate correct solutions. It merely identifies the boundary condition clearly.

---

Methodology Constrained to Task Domains with Clean Correctness Signals

The assumption or constraint. The entire compute-optimal framework — difficulty estimation via pass@1 rates, PRM training via Monte Carlo rollout correctness, and answer verification — depends on tasks where correctness can be determined automatically and unambiguously. The paper uses the MATH benchmark, where answers have ground-truth labels that can be checked with exact string matching. The PRM training pipeline (Monte Carlo rollout supervision, Section 5.1) requires sampling completions and determining whether they reach the correct final answer.

The consequence. Many important real-world applications — open-ended generation, dialogue, creative writing, complex multi-step planning, code generation with functional correctness rather than exact match — lack such clean correctness signals. Extending the compute-optimal framework to tasks where correctness is ambiguous, multi-dimensional, or subjective would require fundamentally different verifier training and difficulty estimation approaches. The paper's findings about the efficacy of search vs. revisions, the difficulty-dependence of optimal strategies, and the $4\times$ efficiency gains may not transfer to these domains.

What evidence exists in the paper. All experiments use MATH (Section 4). The paper does not evaluate on any task without clean correctness signals. The PRM training relies on the ability to check final-answer correctness via the grading function from Lightman et al. (2022). The paper does not discuss this as a limitation or propose extensions to open-ended tasks.

Mitigation status. Not addressed. The paper does not acknowledge this as a scope constraint or suggest approaches for applying the framework to tasks without clean correctness signals (e.g., learned reward models, human preference labels).

---

The Revision Model's Correct-to-Incorrect Reversion Undermines Sequential Refinement

The assumption or constraint. The revision model is trained only on sequences where all in-context answers are incorrect followed by a correct answer (Section 6.1). At test time, the model may encounter correct answers in its context (produced during earlier revision steps) and, because it was never trained on what to do when the current answer is already correct, will often "revise" a correct answer into an incorrect one. The paper reports that approximately 38% of correct answers get converted back to incorrect ones using a naive approach (Section 6.1).

The consequence. Sequential revision chains degrade in reliability as the chain lengthens — correct intermediate answers are not stable, and the model can oscillate between correct and incorrect outputs. The paper mitigates this with within-chain selection (majority voting or verifier-based selection across the chain), but this is a patch, not a solution: it means the system cannot confidently build on its own correct intermediate outputs, limiting the benefits of deep sequential refinement. The ReST$^{EM}$ experiment (Appendix K) demonstrates that this is not easily fixed — attempting to optimize the revision model with RL-style training caused performance to degrade substantially with sequential revisions, suggesting the revision training approach is fragile.

What evidence exists in the paper. The 38% reversion rate is stated in Section 6.1. Figure 15b shows that using verifier-based selection across the chain recovers some of the lost accuracy. The ReST$^{EM}$ failure is documented in Appendix K, Figure 16: fully sequential performance drops to ~33.5% compared to ~38.5% at the optimal sequential-to-parallel ratio.

Mitigation status. The paper mitigates the symptom (within-chain selection to pick the best answer from the entire chain rather than trusting the final revision) but does not address the root cause (training data distribution that never includes correct in-context answers). The paper acknowledges this implicitly but does not propose a training fix (e.g., including trajectories where the model is trained to recognize when no revision is needed).

---

The $14\times$ Larger Model Baseline Is Not Compute-Optimally Trained, Weakening the Pretraining-vs-Inference Comparison

The assumption or constraint. The FLOPs-matched comparison in Section 7 scales model parameters while holding training data fixed, following the LLaMA paradigm (Touvron et al., 2023). The authors acknowledge that this departs from compute-optimal pretraining (Hoffmann et al., 2022), where both data and parameters would be scaled equally: "We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work" (Section 7).

The consequence. A Chinchilla-optimal model trained with $14\times$ more total FLOPs (scaling both parameters and data) would likely outperform a parameter-only-scaled model, making the pretraining baseline weaker than it could be. The reported advantages of test-time compute over pretraining — e.g., +27.8% relative improvement on easy questions at $R \ll 1$ (Figure 1 bar chart, Section 7) — may shrink or reverse against a properly compute-optimal larger model. Additionally, the $14\times$ larger model uses only greedy decoding — no majority voting, no best-of-N, no search — whereas the smaller model gets compute-optimal test-time strategies. A fairer comparison would give the larger model some test-time compute budget as well.

What evidence exists in the paper. Section 7 explicitly states the LLaMA-style scaling choice and acknowledges the departure from Chinchilla-optimal training. The specific $R$ values (0.16, 0.79, 22) and the FLOPs accounting formulas are provided. Figure 9 shows the actual comparison curves per difficulty bin.

Mitigation status. The paper frames this as a deliberate scope choice and suggests future work on the full compute-optimal pretraining + inference joint optimization. The missing comparison (compute-optimally trained larger model with some test-time compute) is not provided.

---

The Architecture Search and Benchmarking Are Constrained to a Single Task Domain and Model Family

The assumption or constraint. All language modeling experiments use the Pile corpus and all recall evaluations use a specific set of benchmarks (MATH for the main paper, with SWDE/FDA/SQUAD for the appendix experiments). The base model family is PaLM 2-S* (Codey) exclusively. The paper does not evaluate on other reasoning domains (code generation, logical reasoning, scientific QA), other modalities, or other base model families.

The consequence. Several aspects of the findings could be model-specific or domain-specific. The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution — a model with different calibration properties or different error patterns might exhibit different difficulty-dependent scaling curves. The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning capabilities, which vary substantially across model families. The paper's claims about the $4\times$ efficiency gain, the optimal strategies per difficulty bin, and the pretraining-inference tradeoff boundary conditions may not generalize to other settings.

What evidence exists in the paper. Section 4 states that the authors "believe this model is representative of the capabilities of many contemporary LLMs" but this is an assertion, not an empirical finding. No cross-model-family experiments are reported. No cross-domain experiments are reported beyond the MATH benchmark.

Mitigation status. The paper does not claim universality — the hedging language ("we believe this model is representative") implicitly acknowledges the scope limitation. No multi-model or multi-domain extensions are proposed as future work beyond a brief mention in Section 8.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper reframes the design of efficient language model architectures from a search for universal replacements for attention into a resource allocation problem on a measurable Pareto frontier. Prior work evaluated architectures primarily on aggregate perplexity — a metric that the paper demonstrates can be deeply misleading, since models with identical perplexity scores (Mamba vs. Transformer++ at 1.3B/50B: 6.28 vs. 6.28) can differ by 32.2 accuracy points on recall-intensive downstream tasks (SWDE: 52.75% vs. 71.92% at 360M/10B; Table 1). This finding is not merely a benchmarking critique — it reveals that perplexity on standard corpora is dominated by tokens that do not require recall, masking large capability gaps on the rare but critical predictions where in-context retrieval matters. The practical implication is that evaluating architectures on aggregate perplexity alone is insufficient; the field needs diagnostic protocols (synthetic MQAR + real-world recall tasks) that isolate the capability dimensions where architectures meaningfully differ.

This reframing has a second, deeper consequence: architecture design becomes a question of where on the recall-memory tradeoff curve a deployment sits, not which single architecture is "best." The paper shows that no architecture dominates across all operating points. Attention sits at the high-recall, large-memory extreme; H3 and Hyena sit far below the frontier regardless of state budget; Mamba expands the frontier into new territory; Based pushes it further still (Figure 2). The insight is that the optimal choice depends on deployment constraints (memory budget, latency requirements, sequence length distribution) in a principled way, not on a single ranking. This is a conceptual shift from the "attention vs. attention-free" framing that has dominated the efficient architecture literature toward a continuum view where architectures are distinguished by their position on a fundamental tradeoff curve.

The paper also reconciles conflicting signals in the literature about linear attention. Prior work had established that linear attention is theoretically efficient (Katharopoulos et al., 2020) but practically slower than optimized softmax attention implementations (Dao et al., 2022; Figure 4, "Baseline Based" line). Based demonstrates that this gap is not inherent to linear attention — it is an implementation artifact. The IO-aware CUDA kernels (Algorithms 1–3) close the gap and reverse it for generation, achieving 24× higher throughput than FlashAttention-2 at batch size 128 (Figure 4). This validates linear attention as a serious practical alternative rather than just a theoretically appealing but unrealizable idea. The implication is that implementation quality — specifically IO-awareness for the expanded Taylor feature dimension — is a first-class architectural constraint, not an optimization afterthought. Future linear attention work that does not address the hardware efficiency question will be operating under a significant practical handicap.

Methodologically, the paper establishes a template for evaluating efficient architectures that goes beyond perplexity. The combination of (1) a synthetic controlled task (MQAR) that isolates the capability of interest, (2) real-world tasks that test that capability in natural settings (SWDE, FDA, SQUAD), and (3) a theoretical framework that provides lower bounds and architectural explanations for observed empirical rankings — this three-pronged approach provides a more complete picture than perplexity curves alone. The theoretical results in Appendix F are especially valuable as a diagnostic tool: they partition architectures into tiers (attention: O(1) layers; linear attention/Based: O(log log N̄) layers; gated convolutions: Ω(log log N) layers) that successfully predict the empirical hierarchy in Figure 2 before experiments are run. This tight integration of theory and experiment is unusual in the efficient architecture literature and provides a template for future work that wants to make principled architectural arguments rather than purely empirical ones.

Finally, the paper's finding that recall deficits widen with training (Based's advantage over Mamba on recall tasks grows from 3.9 to 9.0 points at 360M scale and from 9.0 to 10.4 points at 1.3B scale as token budget increases; Section 6.1, Table 1) has a sobering implication for the "just train longer" approach to architecture development. If the recall capability gap between architectures is not closed by additional training on standard next-token prediction objectives — and may even widen — then architectural choices made early in model development have compounding consequences for downstream capabilities that are not visible in training loss curves. This suggests that early-stage architecture evaluation on targeted capability benchmarks (like MQAR and recall-intensive tasks) should be a standard part of the development pipeline, not deferred to post-training evaluation.

Follow-Up Research This Work Enables

Scaling the recall-memory Pareto frontier to production model sizes. The paper demonstrates the tradeoff at 360M and 1.3B parameters on 10B–50B tokens. The critical open question is whether the frontier hierarchy (attention > Based > Mamba > gated convolutions) holds at scales where these architectures are deployed in practice — 7B, 13B, 70B parameters, trained on trillions of tokens. A strong follow-up would replicate Figure 2 and the recall-intensive task evaluation from Table 1 at the 7B scale, training Based, Mamba, and Transformer++ on the same 1T+ token budget. The key measurement would be whether Based's relative advantage over Mamba on recall tasks (10.36 points at 1.3B) grows, shrinks, or stays constant with scale. If Based's advantage erodes at scale, it would suggest that Mamba's input-dependent state updates become more effective with larger models, narrowing the gap. If the advantage persists, it would strengthen the case that the Taylor linear attention + sliding window composition provides a fundamental recall benefit that scale alone does not close.

Cheap difficulty estimation via learned difficulty predictors or adaptive allocation. The difficulty estimation cost identified in Section 3.2 of the companion paper (2048 samples per prompt) is the single largest practical barrier to deploying compute-optimal test-time scaling. Two specific directions follow. First: train a lightweight difficulty classifier — potentially a small distilled model — that takes only the prompt text as input and predicts the difficulty bin, using the PRM's score distribution from the 2048 samples as training labels. The evaluation would measure whether a classifier with, say, 10M parameters can achieve difficulty bin accuracy comparable to the full 2048-sample PRM method, and whether the compute-optimal policy using predicted bins still achieves the ~4× efficiency gains reported in Figures 4 and 8. Second: develop an adaptive allocation scheme that starts with a small number of samples (4–8), uses the PRM scores on those samples as a rough difficulty estimate, allocates a portion of the remaining budget based on that estimate, and iterates. This would amortize difficulty estimation into the problem-solving process itself and could be compared to the static allocation baseline.

Long-context recall evaluation of Based vs. Mamba vs. attention. The MQAR experiments use 1024-token sequences; the Pile evaluations use the GPT-2 1024-token context window. Real-world recall problems increasingly involve much longer contexts — retrieval over entire documents, multi-turn conversations, code repositories. A natural stress test is to evaluate Based, Mamba, and Transformer++ on long-context recall benchmarks (e.g., SCROLLS, LongBench, zero-shot retrieval from sequences of 8K, 32K, or 128K tokens). The key measurement would be whether Based's advantage over Mamba on recall tasks (10.36 points at 1.3B on sequences up to 1024 tokens) persists, grows, or shrinks as context length increases. Based's linear attention recurrent state does not grow with sequence length, while Mamba's SSM state also remains fixed — so the architectural difference in recall capability at long contexts is not obvious from the MQAR results alone. A negative result (Based and Mamba converge on long-context recall) would suggest that the benefit of linear attention's expanded state is most relevant for shorter contexts where the Taylor feature map's expressive capacity relative to the context length is high.

Training throughput evaluation for hybrid architectures. The paper focuses exclusively on inference efficiency (prefill and generation throughput). Training throughput — tokens per second during pretraining — is equally important for practical adoption, since models are typically trained once but evaluated many times. Based's hybrid architecture introduces three different layer types (linear attention, sliding window attention, gated convolution), each with different computational characteristics and memory access patterns. A training throughput benchmark comparing Based to Mamba (which has a uniform layer structure) and Transformer++ (FlashAttention-2) at the 1.3B scale, measuring tokens/second on a fixed hardware configuration, would quantify the training cost of the architectural hybridization. The expectation is that Based would be somewhat slower than Mamba (due to the sliding window attention layers) but faster than Transformer++ at long sequence lengths (due to the linear attention layers), but the crossover point is unknown. This measurement is essential for organizations deciding whether to adopt Based for large-scale pretraining.

Ablating the necessity of sliding window attention vs. longer convolutions for local recall. The quality ablations (Table 6) show that removing sliding windows degrades AR perplexity from 2.07 to 2.09 (with convolutions still present), and removing convolutions degrades it from 2.07 to 2.11 — both effects are small. This raises a question about whether the sliding window component is genuinely necessary or whether a longer convolution filter (e.g., filter size 7, 15, or 31 instead of 3) could provide the same local precision while maintaining a simpler architecture. A direct ablation would train Based variants with no sliding window layers but with increasing convolution filter sizes (3, 7, 15, 31), measuring MQAR accuracy and downstream recall task performance. If a filter size of 15 achieves comparable recall to the sliding window + short convolution combination, it would simplify the Based architecture to two layer types (linear attention + gated convolutions) without compromising the Pareto frontier position.

Cross-model-family validation of the recall-memory tradeoff lower bounds. The theoretical lower bounds (Section 3.2, Appendix F) are derived under specific assumptions about the token encoding and the gated convolution architecture class. A valuable stress test would be to replicate the MQAR experiments from Figure 2 on architectures that the theory does not cover — for example, RWKV v6 (which has a different recurrence formulation than v5), RetNet (Sun et al., 2023), or xLSTM (Beck et al., 2024) — and plot them on the same recall-memory plane. If these newer architectures fall on or above the Based curve, it would indicate that the theoretical hierarchy is specific to the tested architecture families. If they fall below, it would strengthen the case that the lower bounds capture a fundamental limitation of certain recurrent mechanisms that newer proposals have not overcome.

Practical Applications and Downstream Use Cases

On-device and edge deployment with bounded memory. The primary practical scenario enabled by Based is deployment on devices where memory for the attention KV-cache is the binding constraint — mobile phones, edge inference accelerators, consumer GPUs with limited VRAM. Consider a deployment where the maximum per-sequence memory budget is 100MB. Full attention with a 4096-token context and model dimension 1792 would require ~29MB per layer for the KV-cache (2 × 4096 × 1792 × 2 bytes = ~29MB in bfloat16), meaning a 36-layer model would far exceed the budget. Based with 7 linear attention layers (state size ~280K floats × 7 ≈ 7.8MB in bfloat16), 7 sliding window layers (cache 2 × 64 × 1792 × 7 ≈ 1.6MB), and 22 convolution layers (negligible state) would stay well within the budget while maintaining the recall capability documented in Table 1. The 24× generation throughput advantage over FlashAttention-2 (Figure 4, 1.3B, batch size 128) would also translate to lower latency on memory-constrained devices where GPU memory bandwidth rather than compute is the bottleneck.

Long-document processing pipelines. For applications that require processing very long documents — legal contract review, scientific literature mining, long-form document summarization — attention's growing KV-cache is the limiting factor. Based's fixed-size recurrent state enables processing arbitrarily long sequences with constant memory, while the linear attention's global interaction and the sliding window's local precision together provide recall capability that pure recurrent models (like Mamba) cannot match. At 1.3B parameters, Based's SWDE accuracy of 64.45% and FDA accuracy of 30.40% (Table 1, 1.3B/50B) indicates basic information extraction capability from structured and unstructured documents. For deployment, the practical advantage is that Based can process documents of unlimited length in a single pass without chunking strategies that break cross-chunk dependencies, while Transformer++ would require either truncation or sophisticated chunking with overlap.

Pretraining data filtering and quality assessment at scale. Large-scale data pipelines for pretraining require efficiently scoring or filtering billions of documents. If the filtering criteria involve in-context recall — for example, identifying documents where factual claims are internally consistent, or extracting structured metadata from natural language descriptions — a model that can perform recall accurately but with bounded memory is valuable. Based's fixed recurrent state means that processing a 100K-token document requires the same memory as a 1K-token document, while attention would require 100× the memory. The recall advantage over Mamba (10.36 points on average at 1.3B/50B) means Based would be more reliable at the recall-intensive checks that such pipelines require. A deployment scenario: running Based at 1.3B parameters on a single H100 GPU, processing documents at 24× the generation throughput of FlashAttention-2 (Figure 4), enabling scoring of millions of documents per day with bounded hardware.

Architecture selection for latency-sensitive interactive applications. In settings where generation latency must be low — real-time assistants, code completion, live translation — the per-token cost of computing attention over a growing KV-cache adds latency that grows with conversation length. Based's constant-time recurrent token generation (the $O(1)$ per-token KV-state update in Algorithm 2) means that the latency per token does not degrade as the conversation continues. At 360M parameters, Based achieves 47.23 tokens/ms generation throughput vs. 23.82 for Transformer++ (Table 1, 360M/10B) — nearly 2× faster per token. For an interactive application generating, say, 50 tokens per response, this translates to approximately 1ms vs. 2ms per response, which may not be noticeable, but the advantage compounds for longer generations and higher batch sizes. The key deployment consideration is whether the recall capability difference (Based at 29.16% vs. Transformer++ at 57.97% on SWDE at 360M) is acceptable for the application's recall requirements — if the task involves heavy in-context retrieval, Transformer++'s higher recall may justify the latency cost.

When to Prefer This Method

The paper provides explicit guidance — grounded in the recall-memory tradeoff framework — on when Based should be preferred over its primary competitors. These conditions are not speculative but directly derivable from the empirical results and architectural properties:

Prefer Based over Transformer++ (standard attention) when:

• Inference memory is the binding constraint, not training throughput. Based's generation throughput advantage (24× at 1.3B, batch size 128; Figure 4) and constant-memory per-token cost directly address the KV-cache memory bottleneck.
• Sequences are long relative to the memory budget. The recurrent state size does not grow with sequence length, making Based viable at sequence lengths where attention would exceed available memory.
• The deployment can tolerate a recall capability tradeoff. At 1.3B/50B, Transformer++ outperforms Based by 12.05 points on SWDE (76.50% vs. 64.45%; Table 1). If the application's recall requirements are within Based's capability range, the efficiency gains are substantial; if recall accuracy is paramount, attention remains superior.

Prefer Based over Mamba (or other sub-quadratic architectures) when:

• Recall-intensive tasks are a significant fraction of the deployment workload. Based outperforms Mamba by 10.36 points on average across SWDE, FDA, and SQUAD at 1.3B/50B (Table 1), while matching on aggregate perplexity (6.30 vs. 6.28).
• The benefits of the recall advantage are expected to compound with longer training. The gap between Based and Mamba on recall tasks grows from 9.03 to 10.36 points as training increases from 10B to 50B tokens at 1.3B scale (Table 1), suggesting that Based's recall advantage is robust to training duration.
• Architectural simplicity is valued. Based uses fixed-mechanism components (Taylor feature map, fixed window, fixed convolution filter) with "no input-dependent decays whatsoever" (Section 6), avoiding the parallel scan and input-dependent state updates that Mamba requires. This may simplify implementation across hardware backends and improve training stability.

Prefer Transformer++ over Based when:

• Recall accuracy is the dominant quality metric and the memory budget is not binding. Transformer++ achieves 76.50% on SWDE vs. 64.45% for Based at 1.3B/50B (Table 1), a gap that may be unacceptably large for high-stakes information extraction.
• Training throughput is the primary constraint. The paper does not report training throughput, but Transformer++ with FlashAttention-2 is highly optimized for training; the hybrid layer structure of Based may incur overhead from multiple layer types.
• The sequence length distribution is short enough that the KV-cache memory cost is manageable. For applications where contexts rarely exceed 2048 tokens, attention's memory cost may be acceptable and its superior recall is a pure win.

Prefer Mamba over Based when:

• Generation throughput is the absolute top priority and recall requirements are minimal. Based achieves 95% of Mamba's generation throughput at 1.3B (24.28 vs. 25.69 tokens/ms; Table 1). If the deployment workload consists primarily of short-context generation where recall rarely matters (LM Eval Harness tasks, where Mamba's 46.84% matches Based's 46.68% at 1.3B/10B), the small throughput edge and architectural uniformity of Mamba may be preferable.
• The deployment needs the maximum throughput at the smallest possible state size. Mamba's SSM state ($2 \times d \times d_{\text{state}}$) can be made smaller than Based's linear attention state ($(d+1) \times (1 + d' + d'^2)$) for equivalent model dimension $d$, at some cost to recall capability (Figure 2).