PaperlayerView exact revision on arXiv

Source-linked AI summary

Zoology: Measuring and Improving Recall in Efficient Language Models

Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, Christopher Ré

arXiv:2312.04927v1cs.CLcs.LG

TL;DR

Efficient gated-convolution language models still lag attention, particularly on recalling associations seen earlier in context. The paper introduces multi-query associative recall, analyzes the gap theoretically and empirically, and evaluates sparse-attention hybrids that substantially narrow it while retaining efficient scaling.

  • Problem

    Gated-convolution models retain a quality gap to attention, with associative recall of previously seen in-context information identified as a central missing capability.

    Source: §1 · pp. 1–2, §6 · p. 10

  • Method

    The paper formalizes multi-query associative recall, studies gated-convolution capacity theoretically and empirically, and evaluates convolution-attention hybrids with sparse attention.

    Source: §4 · p. 6, §5 · p. 9, §6 · p. 10

  • Results

    State-of-the-art convolution-based models remain up to 2.1 perplexity points behind strong Transformer baselines, while sparse hybrid attention closes substantial portions of the associative-recall gap.

    Source: §1 · p. 1, §5 · p. 10

  • Takeaways & Limitations

    Associative recall is a useful lens for explaining gated-convolution quality gaps, and minimal attention hybrids can close the gap on the Pile.

    Source: §6 · p. 10, §5 · p. 10

    Input-dependent convolution filters are difficult to make causal, and using an O(N log N) filter for each gap can be expensive.

    Source: §4.3 · p. 9

Abstract

from arXiv · show

Attention-free language models that combine gating and convolutions are growing in popularity due to their efficiency and increasingly competitive performance. To better understand these architectures, we pretrain a suite of 17 attention and "gated-convolution" language models, finding that SoTA gated-convolution architectures still underperform attention by up to 2.1 perplexity points on the Pile. In fine-grained analysis, we find 82% of the gap is explained by each model's ability to recall information that is previously mentioned in-context, e.g. "Hakuna Matata means no worries Hakuna Matata it means no" $\rightarrow$ "??". On this task, termed "associative recall", we find that attention outperforms gated-convolutions by a large margin: a 70M parameter attention model outperforms a 1.4 billion parameter gated-convolution model on associative recall. This is surprising because prior work shows gated convolutions can perfectly solve synthetic tests for AR capability. To close the gap between synthetics and real language, we develop a new formalization of the task called multi-query associative recall (MQAR) that better reflects actual language. We perform an empirical and theoretical study of MQAR that elucidates differences in the parameter-efficiency of attention and gated-convolution recall. Informed by our analysis, we evaluate simple convolution-attention hybrids and show that hybrids with input-dependent sparse attention patterns can close 97.4% of the gap to attention, while maintaining sub-quadratic scaling. Our code is accessible at: https://github.com/HazyResearch/zoology.

1 Introduction

Across 17 models, gated convolutions retain a substantial language-modeling gap to attention, largely because they recall previously seen in-context associations poorly. The paper introduces multi-query associative recall (MQAR) to explain this gap and motivates input-dependent sequence mixing as an efficient remedy.

1 Introduction

  • State-of-the-art convolution-based models remain up to 2.1 perplexity points worse than strong Transformer baselines on the Pile.The comparison uses 17 models spanning four scales and five architectures trained on the same data and infrastructure.Source: §1 · p. 1

AR Hit

  • 82% of the perplexity gap to attention comes from associative-recall hits, although they comprise only 6.4% of Pile tokens.A 70M Transformer predicts these tokens better than a 1.4B Hyena model, and the gap persists at 7B parameters.Source: AR Hit · p. 2
  • MQAR extends prior synthetic associative-recall tests by requiring multiple recalls at varying positions from vocabularies larger than the model dimension.This formulation better captures the quality gaps observed on synthetic and real-world data; prior work had shown gated convolutions matching attention on simpler synthetic tasks [Fu et al., 2023a, Poli et al., 2023a, Lutati et al., 2023].Source: AR Hit · p. 2
  • BaseConv model dimension must grow with sequence length to solve MQAR, while attention can solve it with dimension independent of sequence length.These claims are established theoretically in Theorem 4.4 and Proposition 4.3, respectively.Source: AR Hit · p. 3
  • Adding input-dependent operations to fewer than 10% of layers lets BaseConv outperform the Transformer baseline on Pile modeling and close more than 80% of the MQAR perplexity gap.Sparse attention or convolutional shifts targeted at repeated-bigram positions also succeed on synthetic MQAR tasks, while learned position selection closes the Pile gap.Source: AR Hit · p. 3

2 Background and Preliminaries

The paper studies autoregressive language models whose layers combine sequence mixers with state mixers, varying the sequence mixer to compare attention with gated convolutions. Attention offers flexible token aggregation but quadratic runtime, whereas convolutions and gating provide sub-quadratic alternatives that remain less established for language.

Language modeling

  • The models predict each next token from preceding tokens, embed inputs in d dimensions, process them through L sequence-mixer/state-mixer layers, and project final embeddings to vocabulary logits.Unless specified, implementations follow LLaMA details while varying the sequence mixer [Touvron et al., 2023].Source: §2 · pp. 3–4

Sequence mixers

  • Sequence mixers aggregate token embeddings using weighted sums, and this work compares attention against gated-convolution mixers.The general aggregation is represented as y[i, :] = sum_j ω(i, j)u[j, :].Source: §2 · p. 4

Attention

  • Attention computes query-, key-, and value-based weighted aggregation in O(N^2d) time, making it expensive for long sequences.Attention is the de facto language-model sequence mixer [Vaswani et al., 2017].Source: §2 · p. 4

Gated-convolutions

3 Identifying the associative recall problem

Attention outperforms gated convolutions on the Pile, with associative recall accounting for 82% of their average quality gap. To reconcile this with gated convolutions’ success on synthetic recall, the paper introduces Multi-Query Associative Recall (MQAR), which models multiple recalls at varying sequence positions.

3.1 Fine-grained analysis of downstream quality

  • The gap is largest on rare associative-recall hits, while attention and gated convolutions show no gap on other tokens.AR Hits are identified as repeated bigram-final tokens, adjusted for training frequency, enabling analysis of over 10 million Pile validation tokens.Source: §3.1 · p. 5
  • 82% of the average quality gap between gated convolutions and attention is attributable to the associative-recall token slice.Across 70M, 160M, and 360M parameters, attention’s minimum perplexity advantages are +2.14, +0.59, and +0.35 PPL, respectively.Source: §3 · p. 4, §3.1 · p. 5
  • A 70M attention model achieves 2.41 PPL on the associative-recall slice versus 3.43 PPL for a 1.4B Hyena model, despite being 20× smaller.The comparison comes from models trained for 50 billion tokens on the Pile.Source: §3.1 · p. 5

3.2 Formalizing the problem: Multi-Query Associative Recall

  • MQAR formalizes real-language recall as answering multiple associative queries at varying positions in one forward pass, unlike prior single-query synthetic tasks.The task checks each query for an earlier matching token and outputs the token following its earliest match; MQAR is used to explain the gated-convolution versus attention quality gap.Source: §3.2 · pp. 5–6

4 Explaining the associative recall problem

The section explains associative-recall performance gaps through BaseConv’s theoretical capacity and empirical scaling on MQAR. Gated convolutions require dimension growing with sequence length, whereas attention and input-dependent filters achieve substantially better scaling under specified conditions.

4.1 BaseConv: a minimal gated convolution operator

  • BaseConv can represent any arithmetic circuit with only poly-logarithmic parameter and layer overhead, thereby providing a general analysis model for gated convolutions.BaseConv is universal for arithmetic circuits and generalizes prior linear-function equivalence results to all polynomial functions; BaseConv and Hyena can also simulate each other with only constant parameter overhead.Source: §4.1 · p. 7

4.2 Theoretical analysis of gated convolution capacity and associative recall

  • Attention solves MQAR with O(c2) parameters, O(Nc2 + N2c) time, and O(1) layers; data-independent BaseConv solves it with ˜O(N log c) parameters, time, and ˜O(1) layers.For a subclass with at most t distinct interaction distances, input-dependent convolution filters can achieve constant many layers.Source: §4.2 · pp. 7–8

4.3 Empirical analysis of gated convolution capacity and associative recall

  • Attention solves MQAR perfectly with constant dimension 64, whereas gated convolutions require d ≥ N to exceed 0.9 accuracy as sequence length grows.This empirical result holds for two-layer BaseConv, RWKV, H3, and Hyena models evaluated on synthetic MQAR; Figure 2 summarizes the comparison.Source: Figure 2 · p. 8, §4.3 · p. 8
  • Input-dependent filters improve gated-convolution scaling, with programmatic filters achieving near-constant dimension scaling and autocorrelation filters outperforming input-independent aggregation.Because such filters complicate causality and may be expensive, a small amount of attention in a BaseConv hybrid offers a simpler alternative and improves synthetic-MQAR scaling.Source: §4.3 · pp. 8–9

5 Closing the Associative Recall Gap

BaseConv-attention hybrids substantially close the associative-recall and language-modeling gaps to attention, with input-dependent sparse attention preserving sub-quadratic scaling. These hybrids can also outperform attention-only models while using fewer FLOPs and simpler implementations.

Closing the Associative Recall Gap

  • Input-dependent sparse attention closes most of the attention gap while maintaining sub-quadratic scaling, and BaseConv hybrids are simpler to implement and analyze than prior hybrids [Fu et al., 2023a].The learned selector computes attention in O(ndk) time, and the hybrids can outperform attention-only models by up to a full perplexity point.Source: §5 · p. 9

Sparse BaseConv-Attention Hybrids

  • The hybrids use mostly BaseConv layers plus three selective attention layers, whose input-dependent selection can target tokens that may be associative-recall hits.The evaluated architectures use attention in 6.3% of layers at 354M parameters and 10% at 168M parameters; programmatic selection marks tokens previously seen in the sequence, while learned selection scores and selects the top-k tokens.Source: §5 · p. 9

Downstream Evaluations

  • 0.85 perplexity points separate hybrid attention-BaseConv models from attention-only models, while they reduce total FLOPs by 18% and can outperform the Transformer.At 360M parameters, BaseConv with three attention layers requires fewer FLOPs than the Transformer; Table 2 evaluates these hybrid and selective-look-up models.Source: Table 2 · p. 10, §5 · p. 10
  • 85% of the pure-BaseConv-to-attention AR gap is closed by programmatic selection, while learned selection closes 72% using k = 256 sub-quadratic attention positions.Random selection is used as a control and does not achieve the same AR-gap closure.Source: §5 · p. 10

6 Discussion and Conclusion … A.2 Efficient Language Modeling Architectures

The paper attributes the quality gap between gated convolutions and attention primarily to associative recall, formalizes multi-query associative recall (MQAR), and uses it to motivate efficient architectures that close the gap. The appendices extend the related work, implementation, experimental, synthetic, scaling, and theoretical analyses underlying these conclusions.

6 Discussion and Conclusion

  • The study identifies associative recall as the main failure mode behind the persistent quality gap between efficient gated convolutions and attention, and shows minimal architectures can close it on the Pile.MQAR correlates with downstream associative-recall quality, while theoretical and empirical analyses attribute the gap to insufficient data-dependent mixing in gated convolutions.Source: §6 · p. 10
  • The authors position MQAR and real-language-modeling tasks as useful alternatives to treating attention as the universal architectural goalpost.They connect this perspective to prior efforts improving attention efficiency [Dao et al., 2022, Dao, 2023, Katharopoulos et al., 2020a] and studying its theoretical power [Hahn, 2020, Merrill et al., 2022, Keles et al., 2023].Source: §6 · p. 10

Appendix

  • The appendix documents extended related work, BaseConv implementation, experimental architectures and hyperparameters, real-data MQAR analyses, formal MQAR definitions, synthetic experiments, scaling studies, and theoretical proofs.These materials are organized across Appendices A–H, including additional analysis of MQAR across language distributions and gated-convolution versus attention scaling.Source: Appendix · p. 16

A Extended Related Work

  • The extended related-work discussion situates the paper within mechanistic interpretability, efficient architecture design, and input-dependent architectures.The authors state that their work is inspired by and builds on these three research areas.Source: A Extended Related Work · p. 16

A.1 Mechanistic Interpretability, Synthetic Languages, and Associative Recall

  • Associative recall connects the paper to mechanistic interpretability, synthetic-language studies, associative-memory models, recurrent mechanisms, and claims that attention supports in-context learning through recall.Relevant precedents include Hopfield networks, neural Turing machines, LSTMs, fast-weight RNNs, and attention-based interpretations [Elhage et al., 2021, Olsson et al., 2022].Source: §A.1 · p. 16

A.2 Efficient Language Modeling Architectures

  • Efficient language-modeling architectures are motivated by lower sequence-length complexity: attention scales as O(N^2), convolutions as O(N log N), and recurrent inference can be O(1).State-space models can use convolution or recurrence to combine sub-quadratic training with constant inference complexity [Gu et al., 2021].Source: §A.2 · p. 16
  • Implicit convolutional filters can be converted into state-space models through a simple distillation step [Massaroli et al., 2023].This conversion further links convolution-based architectures with efficient state-space formulations.Source: §A.2 · p. 17

A.3 Input-Dependence in Sequence Modeling Architectures · B Code Listing · C Downstream Experimental Details

The paper argues that existing sub-quadratic sequence models do not efficiently solve MQAR because recall requirements expose limitations in their input-dependent mechanisms. It also documents BaseConv implementations and the training setup used for downstream Pile experiments.

A.3 Input-Dependence in Sequence Modeling Architectures

  • Attention performs input-dependent sequence mixing through input-derived Q, K, and V terms, whereas long-convolution filters in S4 and related architectures are input-independent and cannot alone perform MQAR.Gating introduces input dependence through element-wise multiplication while leaving the convolution filters input-independent.Source: §A.3 · p. 17
  • Input-dependent RNNs improve over gated convolutions on MQAR and Pile quality, but their required hidden-state dimensionality grows with the number of key-value pairs recalled.Linear attention can also be expressed as an input-dependent RNN, while attention avoids this recall-dependent complexity.Source: §A.3 · p. 18
  • The proposed sparse hybrid selects top-k attention positions with an auxiliary sparsity loss, unlike SeqBoat, which can fall back to full quadratic attention.Prior hybrids such as H3 without attention and MEGA underperform attention on language modeling.Source: §A.3 · p. 18
  • Subquadratic models do not efficiently solve MQAR, while gated-convolution recall requires hidden dimensions that scale with sequence length.The authors contrast this with attention, whose complexity does not scale with the number of key-value pairs to recall.Source: §A.3 · pp. 17–18

B Code Listing

  • BaseConv is provided in explicit and implicit long-convolution variants, including FFT convolution, residual connections, and an MLP-parameterized filter.The implicit variant uses complex-exponential positional embeddings and an MLP to generate the convolution filter.Source: B Code Listing · pp. 18–20

C Downstream Experimental Details

  • The experiments use A100 80GB Nvidia GPUs and GPT-NeoX infrastructure, with GPT2BPETokenizer tokenization and identical data order across models.The appendix specifies architecture-specific hyperparameters and settings for training on the real-world Pile data.Source: C Downstream Experimental Details · p. 20
  • The downstream appendix details how the associative-recall quality gap is measured and describes the pure gated-convolution, attention-baseline, and hybrid architectures evaluated.These settings are organized across Appendix C.1 and C.2.Source: C Downstream Experimental Details · p. 20

C.1 Measuring the Mqar Gap on Real Language Data

The protocol estimates how much of the convolution–attention quality gap is attributable to associative recall by evaluating rare recurring bigrams and comparing their log-probabilities. It measures explicit token-level recall only, covering approximately 6.4% of validation tokens under the submission’s training-frequency threshold.

C.1 Measuring the Mqar Gap on Real Language Data

  • The protocol identifies recurring bigrams and retains only those seen fewer than 1, 250 times during pretraining, reducing contamination from memorized frequent patterns.For each qualifying occurrence, the true repeated completion is evaluated as an AR Hit.Source: §C.1 · p. 20
  • The method attributes part of model m’s quality gap to associative recall by comparing its AR-Hit and overall validation log-probabilities with those of attention model M.The calculation uses the average AR-Hit log-probabilities, average all-token log-probabilities, and the proportion of AR-Hit tokens.Source: §C.1 · p. 20
  • If m is better than attention overall but attention is better on associative recall, the protocol ascribes 100% of the quality gap to associative recall.The gap is computed using log-probabilities rather than perplexity so the metric remains independent of validation-slice length.Source: §C.1 · pp. 20–21
  • The evaluation measures only explicit token-id bigram repetition and therefore excludes fuzzy recall between related concepts, such as synonym-based or contextual semantic associations.Approximately 6.4% of validation tokens are AR Hits at the stated training-frequency threshold.Source: §C.1 · pp. 20–21

C.2 Gated Convolution Downstream Architectures · D Extended Downstream Analysis of Mqar · D.1 Additional Discussion of Mqar in the Pile

The appendix details downstream architecture evaluations and hybrid designs for testing input-dependent attention, then extends MQAR analysis to real language data in the Pile and RedPajama. These analyses support studying where associative recall occurs and how input-dependent sequence mixers can target it efficiently.

C.2 Gated Convolution Downstream Architectures

  • The downstream comparison covers four previously proposed architectures plus BaseConv and the canonical BaseConv representation, totaling 14 training runs.The evaluated architectures include attention, Hyena, H3, RWKV-V4, pure long convolution, and BaseConv.Source: §C.2 · p. 21
  • Hybrid models retain the pure gated-convolution depth, replace selected gated-convolution layers, and evenly intersperse gated and replacement layers.Replacement options include full attention and sparse attention variants.Source: §C.2 · p. 21
  • Programmatic selection causally identifies repeated bigrams to construct sparse-attention patterns on associative-recall hit tokens.The method determines whether a bigram of raw token ids is repeated while processing the input sequence.Source: §C.2 · p. 21
  • Learned selection uses a sigmoid-scored linear layer to identify attention positions, with top-k selection controlling computational complexity.The selector is trained to assign high scores where attention should be applied.Source: §C.2 · pp. 21–22
  • Input-dependent hybrid architectures are used to test whether they can address the associative-recall gap while offering varied ways to incorporate input dependence.The study evaluates full attention, randomly selected sparse attention, programmatically selected attention on associative-recall hits, and learned top-k attention positions.Source: §C.2 · pp. 21–22

D Extended Downstream Analysis of Mqar

  • The extended MQAR analysis examines how associative recall manifests in real language data from the Pile, ArXiv, and StackOverflow.It extends the Pile discussion and adds analyses of RedPajama sources.Source: D Extended Downstream Analysis of Mqar · p. 22

D.1 Additional Discussion of Mqar in the Pile

  • Appendix examples demonstrate associative recall in the Pile by comparing next-token predictions from Attention, RWKV, and Hyena models.Tokens are color-coded to highlight prediction differences in real examples.Source: §D.1 · p. 22
  • The analysis locates where associative-recall hits occur in sequences to guide efficient input-dependent sequence mixers.If hits concentrate in specific positions, a mixer may avoid computing all N^2 token-to-token interactions for every sequence.Source: §D.1 · p. 22

D.1.1 Pile Examples · D.1.2 Distribution of Mqar Hit Positions in Sequences · D.2 Analyzing Mqar across Varied Language Distributions

Pile examples show attention recovering repeated information across long gaps more reliably than gated-convolution models, while MQAR hits in real data are mostly local but include a long-range tail. Across language sources, structured corpora contain more repeated bigrams because terminology, citations, code identifiers, and formatting recur within documents.

D.1.1 Pile Examples

  • Attention correctly recalls repeated tokens across long gaps where RWKV or Hyena fails, including names, phrases, and multi-token entities in Pile examples.Hyena succeeds when repeated tokens are close but fails when the gap exceeds 1,000 tokens; attention correctly recalls “SubSpace” and “sequential centrifugation.”Source: §D.1.1 · pp. 22–23

D.1.2 Distribution of Mqar Hit Positions in Sequences

  • Most MQAR hits occur within 100 token positions of their prior bigram occurrence, but a power-law tail requires long-range interactions.The distribution suggests sub-full-sequence interaction windows may suffice for much of real-data MQAR, motivating sliding-window attention and related local-attention approaches.Source: §D.1.2 · p. 24, Figure 3 · p. 24

D.2 Analyzing Mqar across Varied Language Distributions

  • The language-distribution analysis uses 2,048-token RedPajama sequences from ArXiv, Books, C4, Common Crawl, GitHub, Stack Exchange, and Wikipedia.Repeated bigrams are counted after excluding bigrams containing NLTK stop words or punctuation, and both hit prevalence and distances are compared across sources.Source: §D.2 · p. 24
  • The cross-source prevalence and distance patterns are reported in Figures 4 and 5, measuring repeated bigrams and distances to prior n-gram occurrences.Figure 5 describes a power-law frequency distribution across distances for sequences from each source.Source: §D.2 · p. 24, Figure 4 · p. 25, Figure 5 · p. 25
  • ArXiv, GitHub, and Stack Exchange have relatively high MQAR-hit prevalence because their documents repeatedly use domain terminology, citations, commands, equations, functions, and variable names.By contrast, C4, Common Crawl, Books, and Wikipedia contain more variable bigrams across diverse, relatively unstructured documents.Source: §D.2 · p. 24
  • A GitHub example illustrates MQAR through repeated code identifiers and API-related substrings such as “IllegalArgumentException,” “roadType,” “GeographicPoint,” and “containsKey.”These repetitions exemplify why structured code data produces many repeated bigrams and substrings within a sequence.Source: §D.2 · pp. 24, 26

E Synthetic Mqar Experimental Details · E.1 Mqar Generation Procedure

The paper introduces MQAR synthetic data to explain architectural differences among attention, convolutions, and recurrences, and provides a generation procedure that varies key-value-map size and the number of recall gaps. The design targets real-language demands involving many recalls, diverse token-interaction distances, and larger vocabularies than prior synthetic tasks.

E Synthetic Mqar Experimental Details

  • MQAR is proposed as a tool for explaining language-modeling gaps among Transformers or Sparse Transformers, convolutions, and recurrences.The synthetic analysis connects architectural behavior on recall tasks to differences observed on real-world language modeling.Source: E Synthetic Mqar Experimental Details · p. 26, §E.1 · p. 27

E.1 Mqar Generation Procedure

  • Attention solves recall with a sequence-length-independent bound, whereas gated convolutions require dimension growing with sequence length and recurrences face a single-hidden-state bottleneck.The paper argues that convolutions struggle to compute many token-interaction distances and recurrences struggle to store many key-value pairs in low-dimensional states.Source: §E.1 · p. 27
  • Procedure 1 toggles the number of unique key-value pairs and the number of unique token-interaction distances to expose differences among architecture families.The parameters D, N, and α control these properties, with interaction distances sampled from a power-law distribution.Source: §E.1 · p. 27
  • Unlike prior recall tasks with one query per example, MQAR tests multiple token-interaction distances by varying sequence length N while holding α and D constant.This design reveals whether architectures can support multiple recalls at different distances within one example.Source: §E.1 · p. 27
  • MQAR uses vocabularies of 30k–50k tokens, much larger than the model dimension and prior synthetic-task vocabularies of at most 40 tokens.The larger vocabulary reflects typical language-modeling conditions and addresses vocabulary dependence in theoretical bounds.Source: §E.1 · p. 27
  • The generation algorithm splits the vocabulary into keys and values, randomly pairs them, selects D pairs, places them first, and repeats each key at a power-law-sampled distance.The first occurrences consume the initial 2D positions, while second occurrences are placed within positions [2D..N].Source: §E.1 · p. 27

E.2 Training Details

The synthetic MQAR experiments compare attention, gated convolutions, gated recurrences, and sparse-attention architectures under a standardized training protocol. Architectural variants differ in positional encoding and local-attention structure, while model depth, optimization, data volume, and batch size follow fixed settings.

E.2 Training Details

  • The experiments evaluate four architecture categories: one-head GPT-2-style attention, gated convolutions, gated recurrences, and sparse attention.The gated-convolution category includes Hyena and RWKV; gated recurrences use RetNet’s Chunked RNN, and sparse attention includes sliding- and blocked-window variants.Source: §E.2 · pp. 27–28
  • RetNet is evaluated with chunk sizes of 32 and 8, while sliding-window attention attends to the prior w tokens and blocked-window attention applies causal attention within blocks of size w.RetNet uses chunked attention combined with recurrence; its input-dependent matrices distinguish it from standard state-space models.Source: §E.2 · p. 28
  • All synthetic runs use two layers, sweep four AdamW learning rates from 10^-4 to 10^-2, train for 64 epochs, and apply 0.1 weight decay with 10% linear warmup.Each layer contains one sequence mixer and one MLP interleaved with layer normalization.Source: §E.2 · p. 28
  • Global batch size is 8, 16, or 64 according to whether sequence length or model dimension is at least 512, at least 256, or smaller, respectively.Model dimension, sequence length, and KV-pair count vary by experiment.Source: §E.2 · p. 28
  • Pure convolution runs omit positional embeddings, attention variants use them, and every model trains on 100,000 data points and evaluates on 3,000 with fixed data order.The data and ordering are constant across runs.Source: §E.2 · p. 28

F Extended Results on Mqar Across Architectures

This section further validates MQAR as a diagnostic across architecture families. It shows how recall efficiency varies for gated convolutions, gated recurrences, and sparse attention, and connects MQAR performance to downstream associative recall on the Pile.

Extended validation

  • MQAR diagnoses architectural behavior across gated convolutions, gated recurrences, sparse attention, and downstream associative recall on the Pile.The experiments use the synthetic and downstream protocols described in Appendices E and C.Source: F Extended Results on Mqar Across… · p. 28

Gated convolutions and recurrences

  • As required token-interaction distances or stored key-value pairs increase, input-independent gated convolutions and gated recurrences require larger dimensionality than attention.Figure 6 evaluates gated recurrent RetNet (Sun et al. [2023]) across different key-value-pair counts, with Hyena and attention as references.Source: F Extended Results on Mqar Across… · p. 28, Figure 6 · p. 29

Sparse attention

  • Sliding-window attention narrows the MQAR gap at short interaction distances but degrades at longer distances, whereas blocked-window attention struggles to close the gap.The section also reports that repeated bigrams in the Pile and RedPajama occur near one another, and that architectures strong on MQAR perform well on downstream associative recall.Source: F Extended Results on Mqar Across… · p. 28, Figure 6 · p. 29

F.1 Synthetic Experiments · F.2 Demonstrating Mqar as a Tool for Architecture Development

Synthetic MQAR experiments show that gated convolutions require increasing dimensionality as recall complexity grows, while sparse attention can match full attention under suitable locality conditions. These synthetic trends also carry to downstream Pile validation, supporting MQAR as an architecture-development tool.

F.1 Synthetic Experiments

  • Synthetic MQAR results show gated convolutions use larger dimensionality than attention as the number of required token-interaction distances increases.The experiment varies N ∈ {64, 128, 256, 512} and model dimensions ∈ {64, 128, 256, 512}.Source: §F.1 · p. 29
  • Varying the number of key-value pairs per example directly tests recall capacity by fixing N = 256 and increasing the number of pairs through D ∈ {N/32, N/16, N/8, N/4}.Model dimensions ∈ {64, 128, 256} are evaluated for each setting.Source: §F.1 · p. 29
  • As associative-recall key-value pairs exceed the window size, gated models again require increased dimensionality relative to full O(N^2) attention.The result is illustrated with RetNet, a special case of Mamba Anonymous [2023a] and GateLoop Anonymous [2023b].Source: §F.1 · p. 29
  • The gated recurrence theoretically uses Ω(N) bits to solve MQAR, making large key-value sets difficult to store in low-dimensional hidden states.This explains why dimensionality requirements rise as recall demands increase.Source: §F.1 · p. 29
  • Sliding-window attention closes the gap to full attention when all key-value pairs fit within its window, but performance degrades once they exceed that window.With 16 KVs, a window size of 32 performs well; beyond that point it degrades relative to same-dimensionality attention models.Source: §F.1 · p. 29
  • A sliding-attention window of size 8 performs poorly across settings, while blocked attention also underperforms because early-block tokens lack sufficient prior context.These findings qualify when sparse attention patterns can reproduce full-attention recall.Source: §F.1 · p. 29

F.2 Demonstrating Mqar as a Tool for Architecture Development

  • The downstream Pile results follow the same RetNet-versus-sparse-attention trends observed on synthetic MQAR data.Table 4 reports validation perplexity after pretraining on 10B Pile tokens, including overall and AR versus non-AR slices.Source: Table 4 · p. 30, §F.2 · p. 30
  • These corresponding synthetic and downstream trends motivate MQAR as a useful tool for future architectural development.The section explicitly proposes MQAR synthetic data for evaluating and designing architectures.Source: §F.2 · p. 30

G Mqar Perplexity Gap and Model Size … H.4 Linear Arithmetic Circuits

This section examines the persistent MQAR gap between gated convolutions and attention across model scales and develops BaseConv as a framework for analyzing gated-convolution operations and representational power. It establishes realizations of key convolutional primitives and shows how BaseConv composes to simulate Hyena and represent linear arithmetic circuits.

G Mqar Perplexity Gap and Model Size

  • 1 perplexity point separates the 70M attention model from the 1.4B Hyena model on associative recall, showing that scale alone does not eliminate the gap.Larger models improve memorization of training-data bigrams but do not rapidly improve in-context learning on rare bigrams.Source: G Mqar Perplexity Gap and Model Size · p. 30
  • At 7B parameters, RWKV remains behind Llama 2, and its gap increases as each sequence requires more recalls.Synthetic MQAR evaluation uses P ∈ {16, 32, 64, 128, 256} key-value pairs and 1,000 samples per P value; RWKV quality degrades on the AR slice as P grows.Source: G Mqar Perplexity Gap and Model Size · p. 31, Figure 7 · p. 31
  • Rare-bigram evaluation exposes much larger gated-convolution deficits: at 350M parameters, the Hyena and RWKV gaps are 1.85 and 1.84 points for bigrams seen < 1,250×, versus 12.0 and 13.2 points for bigrams seen 1×.These results indicate that gated convolutions struggle when recall depends on using context rather than memorization.Source: G Mqar Perplexity Gap and Model Size · p. 32

H.1.2 Summary of the Results

  • The theoretical appendix introduces formal definitions and proofs for gated-convolution architectures, then uses BaseConv to analyze their operations and MQAR representational power.It shows that general arithmetic circuits can be simulated by BaseConv and extends the analysis from individual proposals such as Hyena to the broader gated-convolution class.Source: H Details on Theoretical Analysis · p. 32, §H.1.2 · p. 33

H.2 Gated Attention-Free Models

  • Gated attention-free models are defined as stacked sequence-to-sequence systems whose layers use element-wise gating, convolution, and linear projection, including Hyena, RWKV, RetNet, and BaseConv.The theoretical linear projections use structured matrices with approximately linear parameter and matrix-vector runtime costs, although experiments use dense projections.Source: §H.2 · pp. 33–34

H.2.4 BaseConv

  • BaseConv combines a linear map, convolution, and element-wise gating, with a single layer requiring approximately O~(N′d′) parameters and runtime.The appendix shows that BaseConv can emulate each of these basic operations, providing the primitive construction used in later theoretical results.Source: §H.2.4 · pp. 35–36
  • BaseConv can compute element-wise gating between matrices by convolving one input with an identity filter and multiplying it with a fixed factor.The construction yields v ⊙ u.Source: §H.2.4 · p. 36

H.3 Primitives

  • The primitives formalize shift, add, and remember operations as building blocks for subsequent gated-convolution proofs.Shift moves a sequence by s entries; add combines x with a running sum S; remember applies gated convolution to x while retaining v in the input sequence.Source: §H.3 · pp. 36–38
  • BaseConv realizes shift down and shift up in one and three layers, respectively, computes running-sum addition in two layers, and implements remembering in five layers.The shift constructions support any s ≤ N, while the running-sum and remembering propositions specify their required sequence layouts and convolution outputs.Source: §H.3 · pp. 38–40
  • BaseConv supports compositional computation by stacking models with matching dimensions, so composing depths L1 and L2 yields depth L1 + L2.The primitives use convolutions and Hadamard products and generalize to d > 1.Source: §H.3 · p. 42

H.3.1 BaseConv-Hyena Equivalence

  • BaseConv and Hyena simulate each other using constant-factor layers, with Hyena layers reproduced by five BaseConv layers and augmented internal dimension N′ + N.The construction uses input augmentation and a remembering primitive to preserve the original Hyena input across BaseConv layers.Source: §H.3.1 · pp. 42–43

H.4 Linear Arithmetic Circuits

  • BaseConv represents any (nd, s, Δ, w)-linear arithmetic circuit with an equivalent depth Δ′ = O(Δlog(w)) model.The result applies when the circuit is represented by matrix multiplication Mx, with x reshaped row-major into u ∈ R^n×d.Source: §H.4 · p. 45

H.5 General Arithmetic Circuits … H.7.6 Conversion to Arithmetic Circuit

This section develops sequential and parallel constructions for solving MQAR, including an efficient attention solution and BaseConv-based approaches. It establishes their arithmetic-circuit representations and corresponding complexity bounds in size, depth, and width.

H.5 General Arithmetic Circuits

  • BaseConv simulates any (n, s, ∆, w)-arithmetic circuit with N = n, ∆′ = O(∆log w), N′ = O(w), and d′ = d.The construction layers addition and multiplication gates, using linear maps for additions and remembered Hadamard products for multiplications, while keeping internal dimension w.Source: §H.5 · p. 46

H.6 The Retnet Reduction and Space Complexity for AR

  • RetNet with O(d2) parameters and N layers has an equivalent BaseConv model using O(Nd) parameters and O(N log d) layers.Each RetNet state is represented by an arithmetic circuit of depth O(N) and width d2, then converted via the arithmetic-circuit simulation theorem.Source: §H.6 · pp. 48–49
  • RetNet requires Ω(N)-bits to solve associative recall for d ≤ N.The lower bound follows by reducing the one-way randomized index problem, whose communication complexity is Ω(N), to associative recall.Source: §H.6 · p. 49

H.7.1 Introduction

  • MQAR asks each query to return the value associated with any earlier matching key, generalizing the original associative-recall formulation with constant parameter blowup.Inputs are streaming key-value-query tuples, with tokens embedded using d ≈ log(c) dimensions for vocabulary size c.Source: §H.7.1 · p. 50

H.7.2 Mqar Solution via Attention

  • Attention solves MQAR with O(c2) parameters, O(Nc2 + N 2c) time complexity, and O(1) layers, even without softmax.The construction uses ALiBi linear biases to shift values and pair queries with matching keys through two attention layers.Source: §H.7.2 · pp. 50–52
  • A parallel MQAR algorithm uses O(Nd · log2 N) work and O(d · log2 N) time, converting to BaseConv with ˜O(1) layers and ˜O(Nd) parameters.The conversion proceeds through arithmetic circuits.Source: §H.7.2 · p. 52

H.7.3 Initial Attempt: A Sequential Algorithm

  • The initial sequential MQAR approach uses an associative array to solve the problem.Source: §H.7.3 · p. 52
  • The initial sequential MQAR algorithm uses an associative data structure for insertion and lookup and runs in O(dN log N) time.Each step queries previously stored keys and inserts the current key-value pair.Source: §H.7.3 · p. 52

H.7.4 Algorithm via Parallel Binary Search

  • Parallel binary search solves MQAR with work complexity O(Nd · log2 N) and time O(d · log2 N).The algorithm uses dyadic intervals, sorting, prefix-index organization, and parallel pbs-key-values calls.Source: §H.7.4 · pp. 53–54, §H.7.5 · p. 54

H.7.5 Correctness and Complexity

  • The parallel algorithm is correct because its prefix-based subproblems collectively check every preceding key for each query.The proof establishes Ii = [i−1] for every relevant index, implying that Algorithm 11 solves MQAR.Source: §H.7.5 · p. 54

H.7.6 Conversion to Arithmetic Circuit

  • The arithmetic-circuit construction solves multiple-query associative recall with size O(Nd · log2 N), depth O(log d log2 N), and width O(Nd log N).The construction combines sorting networks with parallel pbs-key-values circuits.Source: §H.7.6 · p. 57
  • The resulting arithmetic circuit has size O(Nd log^2 N), depth O(log d log^2 N), and width O(Nd log N).The construction uses 3 log N 3 parallel comparisons on d-bit strings, contributing size and width O(N log N · d) and depth O(log d).Source: §H.7.6 · p. 57

H.7.7 The Resulting BaseConv Model … H.8.2 BaseConv with kernels generated using Auto-Correlation

The paper gives BaseConv constructions for MQAR with provable parameter and depth bounds, then uses input-dependent autocorrelation kernels to target the sequence’s most relevant interaction distances. The resulting model solves recall for up to t distinct distances in O(1) layers with O(t · Nc) parameters.

H.7.7 The Resulting BaseConv Model

  • A fixed BaseConv circuit also solves MQAR with ˜O(N log c) parameters and ˜O(1) layers.This follows by invoking Theorem H.21 on the arithmetic circuit for MQAR.Source: §H.7.7 · p. 57

H.8.1 Introduction

  • Unlike the fixed circuit, the autocorrelation approach adapts sequence-mixing weights to each input by measuring token distances and constructing corresponding data-dependent convolutions.Autocorrelation provides the mathematical mechanism for identifying relevant shifts in the input sequence.Source: §H.8.1 · pp. 58–59
  • The input is modeled as N key-value-query tokens, and each query retrieves a matching earlier value when its key exists at one of at most t distinct interaction distances.Interaction distance is i − j for query position i and matching key position j; the one-hot setup assumes d = c.Source: §H.8.1 · p. 58

H.8 Data-Dependent Convolutions

  • Autocorrelation identifies the top t shifts with highly overlapping sequence values, enabling convolution filters that perform those shifts and target matching query-key interactions.The method derives data-dependent kernels from the particular input sequence rather than using a fixed sequence-mixing pattern.Source: §H.8.1 · p. 58, §H.8.2 · p. 59

H.8.2 BaseConv with kernels generated using Auto-Correlation

  • O(1) layers and O(t · Nc) parameters suffice for BaseConv to solve MQAR when inputs have at most t distinct interaction distances.The construction uses gated data-dependent convolutions on inputs from {0, 1}3N×c.Source: §H.8.2 · pp. 59, 64
  • For a single selected distance, the convolution, gating, and value-retrieval operations solve associative recall for every query whose matching key lies exactly at that distance.The general construction applies the same argument independently across the t selected shifts.Source: §H.8.2 · pp. 61, 63, 64
  • The general model retrieves the top t interaction distances by autocorrelation, applies one shift kernel per distance, gates matches with queries, and uses the resulting mask to select values.The construction increases the internal dimension to process all t shifts in parallel before summing their outputs.Source: §H.8.2 · pp. 61, 64

Related papers

Loading 2312.04927v1…