Sequence models before transformers

Before transformers, sequences were handled by reading them one step at a time and carrying a hidden state forward — a recurrent network. The architecture is worth understanding not as history but because the two problems that killed it are exactly what attention was invented to solve, and an interviewer asking why transformers won is asking whether you know what they replaced. This section shows the mechanism, measures the failure, and says how much of it is worth learning now.

Recurrent networks#

The idea is a loop. Start with a hidden state, and for each element of the sequence combine that state with the current input to produce a new state. The same weights are used at every step, so the network can handle sequences of any length, and the final state is a summary of everything it has read.

import numpy as np

def rnn(inputs, W_x, W_h, b):
    """The whole idea. h carries everything the model remembers."""
    h = np.zeros(W_h.shape[0])
    for x in inputs:                       # strictly one step at a time
        h = np.tanh(W_x @ x + W_h @ h + b)
    return h

rng = np.random.default_rng(0)
H, D, T = 4, 3, 10
h = rnn(rng.normal(size=(T, D)), rng.normal(size=(H, D)) * 0.3,
        rng.normal(size=(H, H)) * 0.3, np.zeros(H))
print(np.round(h, 3))

# [ 0.079 -0.337  0.24   0.065]

The two problems#

The first problem is that loop. A transformer sees every position at once and computes them in parallel, so a GPU is fully occupied; a recurrent network must walk the sequence in order, and the hardware sits idle waiting for the previous step. That is a hard architectural ceiling on training speed, and it is why scaling to the sizes modern models reach was never realistic.

The second problem is that the memory does not actually reach back very far. Learning that step 100 depends on step 1 requires the gradient to travel back through a hundred multiplications by the same matrix, and repeated multiplication by anything other than exactly one goes to zero or to infinity.

multiplier   after 50 steps   after 200 steps
   0.9         5.15e-03          7.06e-10      vanishes
   0.99        6.05e-01          1.34e-01      survives, barely
   1.0         1.0               1.0           the knife edge
   1.1         1.17e+02          1.90e+08      explodes

That is the intuition; here is the measurement. Push a 60-step sequence through each architecture, take a loss that depends only on the final step, and look at how much gradient reaches each input.

import torch, torch.nn as nn
torch.manual_seed(0)

T, H = 60, 32
x = torch.randn(1, T, H)

def grad_at_each_step(cell):
    """How much does a loss at the END of the sequence depend on each input?
    That dependence is what the model is able to learn from."""
    xx = x.clone().requires_grad_(True)
    out, _ = cell(xx)
    out[:, -1].sum().backward()            # the loss uses only the last step
    return xx.grad[0].norm(dim=1)          # gradient magnitude per timestep

for name, cell in [("RNN (tanh)", nn.RNN(H, H, batch_first=True)),
                   ("LSTM", nn.LSTM(H, H, batch_first=True)),
                   ("GRU", nn.GRU(H, H, batch_first=True))]:
    g = grad_at_each_step(cell)
    print(f"{name:11} last step {g[-1]:.3e}   50 steps back {g[-50]:.3e}")

# RNN (tanh)  last step 2.084e+00   50 steps back 5.540e-19
# LSTM        last step 6.649e-01   50 steps back 7.073e-12
# GRU         last step 1.309e+00   50 steps back 6.198e-11

LSTM and GRU#

These are the fix that made recurrent networks work for a decade. Instead of overwriting the hidden state at every step, an LSTM keeps a separate cell state that is modified additively, and learns gates deciding what to forget, what to write and what to read out. The additive path is the point: information can travel many steps without being repeatedly multiplied, so the gradient has a route that does not decay. A GRU is the same idea with two gates instead of three, and it is cheaper and usually as good.

And the measurement above says how well that works, which is the honest version rarely given. The LSTM and GRU gradients fifty steps back are around 1e-11 or 1e-12 — roughly ten million times larger than the plain RNN's, and still vanishingly small. They pushed the usable range from tens of steps to hundreds. They did not remove the limit, which is why a document of several thousand tokens was out of reach until attention replaced the recurrence entirely.

How much of this to learn#

Enough to answer that question and no more, unless you are working on something that needs it. Concretely: be able to describe the recurrence in a sentence, know that the hidden state is a fixed-size summary and that this is both its strength and its limit, know what the gates in an LSTM are for, and know the two reasons transformers replaced them. Implementing an LSTM cell from scratch is a reasonable afternoon if you enjoy it and is not something interviews ask for.

What is worth more of your time is the property that made recurrence attractive in the first place, because it is coming back. A recurrent model processes a token in constant time and constant memory regardless of how much came before, where attention costs grow with the context. That trade is exactly what the state space models in the next section revisit, so the ideas here are not only historical.

Transformers won language modelling, and it is easy to file recurrent and convolutional sequence models under history. They are not, for a concrete reason: a recurrent model carries a fixed-size state, so the cost of each new input stays flat however long the stream has been running, while attention's cost grows with the context behind it. This section is where that trade still settles the design, meaning streaming audio, sensors and small devices, along with dilated 1D convolutions as a fast baseline and state space models such as Mamba.

The advantage, measured#

A transformer remembers by keeping every past key and value. A recurrent model remembers by folding the past into a fixed-size state. That single difference decides which one you can run on a phone, and the size of the difference is worth seeing rather than accepting. The configuration below is an ordinary 32-layer model with grouped-query attention, against a Mamba-style recurrent state of the same depth.

import torch

d_model, n_layers, kv_heads, head_dim, d_state = 4096, 32, 8, 128, 16

def nbytes(ts):
    return sum(t.nelement() * t.element_size() for t in ts)

one_token_kv = [torch.zeros(kv_heads, 1, head_dim, dtype=torch.float16)
                for _ in range(2 * n_layers)]        # a key and a value per layer
ssm_state = [torch.zeros(2 * d_model, d_state, dtype=torch.float16)
             for _ in range(n_layers)]

per_token = nbytes(one_token_kv)
fixed = nbytes(ssm_state)
print("KV cache per token: %d bytes" % per_token)
print("recurrent state:    %d bytes, and it does not grow" % fixed)
print("they are equal at %d tokens" % (fixed // per_token))
print()
print(" context     KV cache   recurrent")
for ctx in (1024, 8192, 32768, 131072, 1048576):
    print("%8d  %9.1f MiB  %7.1f MiB" % (ctx, per_token * ctx / 2**20, fixed / 2**20))

# KV cache per token: 131072 bytes
# recurrent state:    8388608 bytes, and it does not grow
# they are equal at 64 tokens
#
#  context     KV cache   recurrent
#     1024      128.0 MiB      8.0 MiB
#     8192     1024.0 MiB      8.0 MiB
#    32768     4096.0 MiB      8.0 MiB
#   131072    16384.0 MiB      8.0 MiB
#  1048576   131072.0 MiB      8.0 MiB

The crossover at 64 tokens is the honest other half of the story. A recurrent state is a fixed overhead you pay from the first token, so for short inputs it is the more expensive design. Everything people say about linear scaling only starts to matter past the length where a constant beats a line, and for chat-length prompts that line has barely left the origin. The argument for recurrence is about long streams, not about short ones.

Compute follows the same shape. Attention at step t does work proportional to t, because the new query is compared against every stored key. A recurrent update does the same fixed amount of work at step one and step one million. For a model transcribing a microphone for eight hours, that is the difference between a device that stays warm and one that gets slower every minute it runs.

What the fixed state costs you#

Nothing is free, and the price of a constant-size memory is that it has a capacity. A linear-attention layer, which is the clearest version of the mechanism, keeps one matrix and writes every token into it by adding an outer product of its value and its key. Reading back is a matrix-vector product. Nothing is stored separately, so the entries interfere as they pile up, and the point where interference wins is measurable.

torch.manual_seed(0)
d = 64                                          # the size of the state

print("stored pairs   read-back accuracy")
for n_pairs in (8, 32, 64, 128, 512):
    hits = 0
    for trial in range(200):
        K = torch.nn.functional.normalize(torch.randn(n_pairs, d), dim=1)
        V = torch.randn(n_pairs, d)
        S = V.T @ K                             # the entire history, d x d
        probe = trial % n_pairs
        read = S @ K[probe]                     # ask for one of them back
        best = torch.argmin((V - read).pow(2).sum(dim=1))
        hits += int(best == probe)
    print("%12d   %17.3f" % (n_pairs, hits / 200))

# stored pairs   read-back accuracy
#            8               1.000
#           32               1.000
#           64               1.000
#          128               0.975
#          512               0.380

That table is the whole recall trade-off, and it is why benchmarks that ask a model to retrieve one specific detail from far back are the ones where pure recurrent architectures still lag. It is also why the practical answer has been hybrids: interleave a few full attention layers among many recurrent ones, so the model has a small number of places where exact lookup is possible and pays linear cost everywhere else.

Convolutions over time#

A one-dimensional convolution slides a filter along a sequence. Causal means the filter only looks left, so position t never sees t plus one. Stacking causal convolutions with the spacing between the inputs doubling each layer, which is called dilation, buys an exponentially growing view of the past for a linear number of layers, and unlike recurrence it trains fully in parallel.

The receptive field is the thing to be able to compute, because it is what decides whether the model can see the pattern you care about. With kernel size 2 and dilations 1, 2, 4, 8, it is 1 plus the sum of the dilations. Rather than trust the formula, measure it: push a gradient back from the last output and see which inputs it reaches.

torch.manual_seed(0)

layers = [torch.nn.Conv1d(1, 1, kernel_size=2, dilation=2 ** i, bias=False)
          for i in range(4)]
for layer in layers:
    torch.nn.init.constant_(layer.weight, 1.0)   # so nothing cancels to zero

T = 64
x = torch.zeros(1, 1, T, requires_grad=True)
h = x
for i, layer in enumerate(layers):
    h = layer(torch.nn.functional.pad(h, (2 ** i, 0)))   # left pad keeps it causal
h[0, 0, -1].backward()

touched = (x.grad[0, 0] != 0).nonzero().flatten()
print("output position", T - 1, "depends on inputs", int(touched.min()), "to", int(touched.max()))
print("receptive field measured:", len(touched))
print("receptive field predicted:", 1 + sum(2 ** i for i in range(4)))

# output position 63 depends on inputs 48 to 63
# receptive field measured: 16
# receptive field predicted: 16

This is worth running against your own architecture before you train it, because the failure mode is silent. A model whose receptive field is 16 steps cannot learn a dependency 40 steps back, and it will not tell you so; it will simply train to a mediocre loss and stop. Dilated causal convolutions remain strong, fast baselines for time series and audio, and beating one with a transformer on a small dataset is harder than people expect.

State space models#

A state space model is a recurrence written so it can be computed two ways. Train time uses a parallel scan or a convolution, so the whole sequence goes through at once as with a transformer; inference time uses the step-by-step recurrence, so memory per token is the constant you measured above. That dual form is the trick, and it is what earlier recurrent networks could not do.

The first generation, S4 and its relatives, used a fixed state transition, which made the scan efficient but meant the model could not decide what to remember. Mamba's change was to make the transition depend on the input, so the model can hold on to a token or forget one based on what it is. That is what selective means in the papers, and it is the reason Mamba closed most of the quality gap on language tasks that earlier state space models could not.

• The recurrence and the parallel form compute the same function, so you train fast and deploy with constant memory.
• Selectivity, meaning input-dependent gates, is the difference between the first generation and the ones people actually use.
• Cost is linear in sequence length rather than quadratic, and memory per generated token is constant rather than growing.
• Recall of a specific earlier token is the weak point, for the reason the read-back experiment showed.
• Most shipped models that use this are hybrids, mixing a minority of attention layers in.

Whether this family replaces attention broadly is still open, and you should say so rather than pick a side. What is settled is that it is no longer a curiosity: several released models use it, and the memory argument is arithmetic rather than opinion.

Where recurrence actually wins today#

• Streaming speech recognition, where a transcript must appear while someone is still talking and the audio never ends.
• Keyword spotting on a microcontroller, where the whole model has a few hundred kilobytes and a battery budget.
• Sensor and control loops, where a fixed per-step latency matters more than the last point of accuracy.
• Very long single sequences such as genomics or raw audio, where the quadratic term is the whole cost.
• Anything where the per-step cost must be predictable, because a growing cache means a growing and eventually unacceptable tail latency.

How much to learn#

• Learn why recurrence struggles to train: sequential computation and vanishing gradients. That explains attention.
• Be able to describe an LSTM's gates at a high level, and say why a gate helps the gradient survive.
• Be able to compute a dilated receptive field and a KV cache size. Both come up in interviews and neither takes long.
• Know what selective means in Mamba, and that hybrids are the common shipped form.
• Do not spend weeks deriving LSTM equations, or the HiPPO initialisation behind S4, unless you work on streaming or on-device models.