Most models that avoid the quadratic cost of attention, such as Mamba and other state space models, read a sequence one token at a time and squeeze everything they have seen into a hidden state of fixed size. A long-standing workaround for attention's cost goes the other way: bundle several raw symbols into one larger "macro-symbol" (for example, 6 DNA letters into one of 4,096 tokens) so the sequence gets shorter. HyenaDNA argued that bundling is a necessary evil that sub-quadratic models no longer need. Coding theory says something different. In folded Reed-Solomon codes, bundling consecutive symbols into a larger alphabet is exactly what pushes codewords apart and lets decoding reach capacity. This proposal asks whether bundling, which we will call folding, does something similar for fixed-state models. The specific question is whether it changes how much the model can remember, and not only how much compute it uses.
The core bet is concrete. When a fixed-state model must store associations whose keys span several raw symbols, folding moves the work of assembling those keys out of the recurrence and into the embedding table. That should change both the hidden-state width needed for perfect recall and the narrow learning-rate window in which these models train at all. If this holds, the best fold factor for a recurrent model should be predictable from a known capacity bound, and it should differ from the best fold factor for a Transformer, where folding mainly buys compute. If it fails, and gains vanish once sequence length is held equal, then folding is only a length trick. That negative result would also be worth stating, because it would settle a design choice that genomics and byte-level modeling currently make by habit.
Core Claim
The claim draws on three papers. Understanding Input Selectivity in Mamba shows that Mamba solves associative recall by using a short convolution to bind each key to its value, then writing that pair into a column of its hidden state. Recall reaches 100% when state size meets a bound set by the task, and fails when state size falls just below it. This paper supplies our mechanism and our predictive model. Revisiting Associative Recall in Modern Recurrent Models shows two things on multi-query associative recall with an 8,192-token vocabulary. First, SSMs fix recall by growing width, while Transformers need depth. Second, SSMs only train inside a narrow learning-rate window. This paper motivates the work and also sets a constraint, because it tested only one alphabet size. Large Vocabulary Size Improves Large Language Models shows that growing a Transformer's vocabulary from 5k to 500k raised downstream accuracy from 49.4 to 58.6 at 680M parameters. It explains this as sequence compression under quadratic cost, and it explicitly leaves open whether fixed-state models benefit in the same way.
Our hypothesis follows. When keys are made of $L$ base symbols from an alphabet of size $q$, an unfolded recurrent model must assemble each key across $L$ steps before writing it. A model folded by a factor $k \ge L$ receives each key as a single token drawn from an alphabet of size $q^k$. We predict that the minimum state width for perfect recall drops toward the bound that holds for single-token keys, and that the learning-rate window widens. A Transformer gains far less from folding at fixed sequence length, because attention can compare multi-token keys directly. The cost of folding is that the embedding table grows as $q^k$. This mirrors the large-alphabet constants that remain the practical barrier for folded codes (Explicit capacity-achieving list-decodable codes). The proposal therefore treats table size as a measured cost, not a free lunch.
Research Program
The first piece of work is a controlled synthetic study. We will build a multi-query associative recall generator in which keys and values are strings of $L$ base symbols, with base alphabets $q \in \{2, 4, 16, 256\}$. Each task is presented to the model under fold factors $k \in \{1, 2, \dots, L\}$. We will train Mamba, Mamba-2, Hyena, and multi-layer Transformers across a grid of state widths and learning rates. For each combination of architecture, $q$, $L$, and $k$, we record two outcomes: the smallest width that reaches perfect recall, and the range of learning rates that succeed. We then fit the observed width threshold against the bound from Huang et al. The stored-pair count is computed in folded tokens, and the key-assembly overhead is counted in raw steps. The claim is supported if the fitted threshold tracks the folded count rather than the raw count.
The second piece of work separates "bigger alphabet" from "shorter sequence." Folding changes both at once. We therefore add a control that shortens the sequence by $k$ without creating a new alphabet. In this control, the $k$ symbols at each folded position are embedded separately and their embeddings are concatenated or summed. The input length then matches the folded model, but no single learned vector stands for the whole macro-symbol. A third variant uses a hashed lookup table, which caps parameter growth while keeping a macro-symbol identity. Together these controls tell us whether any benefit comes from the macro-symbol having its own embedding, as the coding-theory analogy suggests, or merely from fewer recurrence steps.
The third piece of work moves to real data with small base alphabets. DNA has $q = 4$, and it is where HyenaDNA (HyenaDNA) set aside $k$-mers in favor of single-nucleotide resolution. Raw bytes have $q = 256$, and they are where the Byte Latent Transformer groups bytes into patches but keeps a quadratic global Transformer. In both settings we run Hyena and Mamba with fixed folding at several $k$. Outputs are always predicted per base symbol through a small unfolding head, so that single-nucleotide resolution is kept at the output even when the input is folded. This answers HyenaDNA's objection that $k$-mers blind the model to single-nucleotide variants.
Baselines
The naive reference point is the unfolded model, $k = 1$. This means HyenaDNA-style Hyena and Mamba reading single nucleotides or single bytes, trained with the same data, token budget, and learning-rate sweep as every folded variant. Folding wins only if it reaches equal or better accuracy at equal or lower training FLOPs. It must also do so while the folded model's extra embedding parameters are counted against it.
The strongest competing remedy for recurrent recall failure is simply widening the hidden state, which Revisiting Associative Recall shows works for SSMs. We will sweep width for unfolded models up to the point where their total parameter count matches the largest folded model's embedding table plus backbone. Folding beats this baseline only if, at matched total parameters and matched FLOPs, it reaches perfect recall at a smaller backbone width or over a wider learning-rate range. The file reports no specific accuracy-versus-width numbers for this baseline at varied alphabet sizes, so we will establish them ourselves.
The strongest existing Transformer comparison is a $k$-mer Transformer in the style of the Nucleotide Transformer. HyenaDNA reports beating it on 12 of 18 Nucleotide Transformer benchmark datasets and on 7 of 8 GenomicBenchmarks datasets with 1.6M parameters against 2.5B. We found no per-dataset accuracy figures for these benchmarks on Lacuna, so we will rerun HyenaDNA at $k = 1$ under our protocol and treat its scores as the bar. A folded sub-quadratic model "beats" the field if it improves on these rerun scores at equal parameters and compute.
For bytes, the strongest data-adaptive alternative is entropy-based patching from BLT. We will reimplement its patcher and pair it with a Mamba global model, so that the comparison isolates fixed algebraic folding from learned variable patching on the same backbone.
The key ablation is the concatenated-embedding control described in the research program. It holds sequence length equal to the folded model while removing the macro-symbol identity. If this control matches full folding, the capacity claim is false, and whatever gain remains is just compute.
Why not just…?
Why not just widen the state? This is the most serious threat, because width is known to repair SSM recall (Revisiting Associative Recall). The two remedies have different cost profiles. Width raises per-step compute and memory for every token. A folded embedding table raises parameters but adds almost no per-step compute. The width sweep at matched parameters and FLOPs settles which remedy is cheaper. If width wins everywhere, we will report folding as dominated.
Why not just use a large BPE vocabulary, as Takase et al. did? Byte-pair encoding, which merges frequent symbol pairs into tokens, is a learned and frequency-weighted form of folding. Takase et al. showed that it helps Transformers but did not test recurrent models. We include byte-pair vocabularies matched in size to $q^k$ on the byte and DNA tasks. If they match fixed folding, the conclusion becomes "vocabulary expansion helps fixed-state models," which is still the new finding. The comparison then simply tells us which kind of expansion to use.
Why not just add a few attention layers? Hybrids of this kind work, as the Mamba–Transformer error-correction decoder ECCM shows. ECCM cut latency from 222.57 to 72.08 microseconds on LDPC(49,24), but only on binary codes of length up to 128, where attention is cheap. We will include a hybrid with one attention layer per four recurrent layers. On million-token DNA contexts, the quadratic layers dominate cost, and folding plus a pure recurrent model should win on throughput. If the hybrid wins on accuracy at long lengths despite that cost, we will report the trade-off honestly.
Proposed Experiments
The decisive synthetic check is a set of phase diagrams on the recall task. Each diagram plots width needed for perfect recall against fold factor, one per architecture and base alphabet. The prediction is that the SSM threshold falls sharply as $k$ approaches the key length $L$, while the Transformer threshold stays nearly flat. The concatenated control should track the unfolded curve, not the folded one. A second readout is the width of the successful learning-rate window as a function of $k$. If folding widens this window, that is direct evidence that it relieves the optimization brittleness Revisiting Associative Recall identified.
On real data, we evaluate pretraining perplexity per base symbol on hg38 and on a byte-level text corpus. Downstream evaluation uses the Nucleotide Transformer benchmarks, GenomicBenchmarks, and HyenaDNA's long-context species classification. For bytes, downstream evaluation uses noised HellaSwag and CUTE, on which BLT reports gains of roughly 8 and 25 points over Llama 3. All results are plotted against training FLOPs and total parameters. The result that would most change practice is a folded Mamba or Hyena that matches $k = 1$ accuracy on variant-sensitive genomic tasks at a fraction of the compute. The result that would most cleanly falsify the idea is the concatenated-embedding control matching full folding everywhere.
References
- Understanding Input Selectivity in Mamba: Impact on Approximation Power, Memorization, and Associative Recall Capacity
- Revisiting Associative Recall in Modern Recurrent Models
- Large Vocabulary Size Improves Large Language Models
- Explicit capacity-achieving list-decodable codes
- HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution
- Byte Latent Transformer: Patches Scale Better Than Tokens
- Hybrid Mamba–Transformer Decoder for Error-Correcting Codes