Story of Attention — Part 1: Before the Transformer

Part 1 of 6 in the Story of Attention series.

1. Before the Transformer (this post) — how n-gram counting and RNN memory hit their ceilings, and how additive/multiplicative attention first let a decoder look back.
2. Attention All You Need — scaled dot-product attention, multi-head attention, and the four-year search for a way to encode position.
3. KV-Cache Bottleneck: MQA and GQA — sharing and grouping key/value heads to shrink inference memory.
4. Sparse Attention, Then and Now — fixed, windowed, hashed, and learned sparsity patterns, from 2019 to 2025.
5. Linear Attention: Kernels, Decay, and Gating — replacing softmax with decomposable kernels, decay, and gated recurrent state.
6. Where Attention Stands Today — latent compression, differential attention, and what frontier LLMs actually ship.

---

When ChatGPT came out at the end of 2022, a lot of people were surprised that a program could write out whole paragraphs of fluent text on its own. But the interesting thing is, what the model is doing underneath is actually quite simple. It predicts the next token, adds it to the text, and then predicts the next one after that, over and over. This idea of predicting the next word is not very new, people have been working on it in one form or another since the 1950s. The first part of this blog covers that older story, models that came before ChatGPT and before the Transformer.

---

1. Sequence Modeling Before Attention

On November 30, 2022, OpenAI released ChatGPT [1]. Within two months it had an estimated 100 million monthly users, which made it the fastest-growing consumer application in history [2]. What is so special about it? You ask a question and the system returns whole paragraphs of coherent text. The interesting thing is, it is not limited to some particular topic, it will write on more or less any topic you could think of. And this is what a large language model does. You give a prompt, and the model reads it as a sequence of tokens and predicts the next one. The prediction gets added to the sequence, the model predicts again, and if you keep repeating this you get a chatbot answer, or a completed function, or a translated paragraph.

But none of this started in 2022. People have been trying to make machines handle language almost since computers existed. Turing made open-ended conversation his test for machine intelligence back in 1950 [3]. The first major machine-translation attempts followed within the decade. For nearly thirty years, researchers tried to do this by writing out rules, grammars and dictionaries. But those systems turned out to break easily, because in the real world, text can be very messy in many ways, hence those rules never fully covered it. Then by the late 1980s the approach had changed, and instead of writing rules for language, people started learning it from data. To learn language from data, you need some mathematical process to do the learning. That process is known as sequence modeling, where a model reads a sentence or a piece of text word by word. And how it went from counting to recurrence to attention is the story before ChatGPT, and the story this series tells.

What Is a Language Model?

Consider two sentences built from the same words. "The dog bit the man" describes an incident. "The man bit the dog" uses the identical vocabulary but the meaning is completely different. Now just shuffled words like "bit the the man dog" do not make a sentence at all. So the words are exactly the same in all three, what changes the meaning is just the order. So whatever a model learns about language, it has to learn from order. And sequence modeling is the branch of machine learning that deals with exactly this kind of data, where the order carries the meaning [4].

A language model is a sequence model for text. It takes a sentence and gives it a probability, and this probability is a number that tells you how likely this sentence is as a piece of language. So a good model will give "the dog bit the man" a higher probability than "the man bit the dog". And shuffled words like "bit the the man dog" will get a probability close to zero. In simple words, probability is nothing but counting, how many times a word appeared in a sentence or in a chunk of text. Now where is this number useful? Let's take another example, speech recognition. When someone says "the apple and pear salad", the words "pear" and "pair" might sound the same, so from the audio alone the system cannot tell which one was pronounced. The language model fixes it, because "the apple and pear salad" is a more likely word sequence than "the apple and pair salad".

Now let's use the same idea into math. In terms of a model, a sentence is just a sequence of tokens $w_1, w_2, \dots, w_T$, one symbol per word (or word piece) taken from a fixed vocabulary, where $T$ is the sequence length. The language model gives this whole sequence a joint probability $P(w_1, \dots, w_T)$. But how do we compute one number for a whole sentence? The chain rule of probability breaks it into a product of next-word predictions:

$P(w_1, \dots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_1, \dots, w_{t-1})$

For the sentence "the dog bit the man" this reads: the probability of the whole sentence is the probability of "the" coming first, then "dog" coming after "the", then "bit" coming after "the dog", and so on till the last word, all multiplied together. Each of these probabilities asks the same question, given the words so far, what will be the next word? This breakdown is the most important idea of this whole series. Modeling language is nothing but predicting the next word, done over and over. And this is exactly what ChatGPT does in its loop, autoregressively. The equation above is just a formal way of writing the same thing. But there is one problem. The equation says each prediction should depend on all the words that came before it, and this history $w_1, \dots, w_{t-1}$ keeps growing as the text gets longer. Hence every sequence model in this story is just a different answer to one question, how much of the past do you want to keep, and in what form?

N-gram Language Models

One way to start is with n-gram models, the oldest working family of language models [5]. Their answer to the above question is to keep almost nothing from the past. Let's take a single probability, say $P(\text{dog} \mid \text{the})$, the probability that the next word is "dog" when the previous word is "the". How do we estimate this? Take a big chunk of text, count how many times "the" appeared in it, then count how many of those times the very next word was "dog", and divide the second count by the first, that's it. This is what we mentioned earlier, probability is nothing but counting how often something appeared.

An n-gram model builds an entire language model based on this. It truncates the history to the last $n-1$ words and estimates what is left by counting. One of the variants of the n-gram model is the bigram model ($n = 2$), which remembers exactly one word:

$P(w_t \mid w_{t-1}) = \frac{\text{count}(w_{t-1}, w_t)}{\text{count}(w_{t-1})}$

Let's try to understand it in a simple way with a tiny little example. Suppose the training data has three sentences: "the dog bit the man", "the dog ran", "the man fed the dog". The word "the" appears 5 times. Three of those times the next word is "dog", twice it is "man", so the model estimates $P(\text{dog} \mid \text{the}) = 3/5$ and $P(\text{man} \mid \text{the}) = 2/5$. Every other word gets zero. There is no training and there are no weights; the counts themselves are the model. Scaled up from three sentences to billions of words, this worked well enough to run speech recognition and statistical machine translation for decades.

But this small window becomes the biggest problem of n-gram models. Every time you extend the memory by one more word, the size of the count table gets multiplied by the vocabulary size. Let's say the vocabulary has $V = 50{,}000$ words. Then a bigram table has $V^2 = 2.5$ billion possible entries, a trigram table has $1.25 \times 10^{14}$, and a 5-gram table has about $3 \times 10^{23}$. So the cost grows exponentially while the memory grows one word at a time, and this is why in practice $n$ stopped at 4 or 5, anything further back the model simply could not see. And even before the count table gets too large to store (the $10^{14}$, $10^{23}$ entries problem), you face an earlier problem, most of its cells can never be filled because most word combinations never occur in the training text even once, so nearly the whole table sits at zero. In our toy example, "cat" already got a probability of exactly zero after "the", and this does not go away with scale. Therefore a raw count model treats such combinations as impossible, and researchers had to invent methods to give these unseen combinations some small probability instead of zero. There is one more problem, the counts do not share anything between words. "cat" and "dog" are two unrelated rows in the table, so a million sentences about cats teach the model nothing about dogs [6]. A model that could store less but understand more would fix all three problems at once. So the missing link here is not a bigger table, it is some form of learned memory that stays with the model across the whole sequence.

Recurrent Neural Networks and the Encoder–Decoder Bottleneck

This is where recurrent neural networks (RNNs) come into the picture [7]. An RNN provides that memory in a very direct way, the output of the network is fed back into the network itself. It reads the tokens one at a time and carries a hidden state forward,

$h_t = f(h_{t-1}, x_t)$

so the model reads every new token while keeping in mind whatever it has read so far, and all of that past is summarized in $h_{t-1}$. Compare this with the n-gram model. The n-gram model kept an exact record of a tiny window, but the RNN keeps a rough summary of the entire history, squeezed into one fixed-size vector. This design gives us two things. First, the input can be of any length, the model just keeps reading token by token. Second, we do not have to tell the model about the position of a word, because the order comes naturally from the way it reads, token 5 is simply whatever the network computes after token 4.

But this architecture comes with a cost, and it shows up during training. To train an RNN, the error signal has to travel backward through every step of the sequence, and at each step the gradients get multiplied together. So over a long sequence this product either shrinks toward zero or blows up, and this is known as the vanishing/exploding gradient problem. Long Short-Term Memory networks (LSTMs) [8] eased this problem with learned gates. At every step, the gates decide what to keep, what to forget and what to write, and this let the gradient, and hence a dependency between far-away words, reach much further back. But the gates only control what goes into the hidden state and what comes out of it. The deeper limitation is still there, everything the network has read must still fit in one fixed-size vector.

For a long time this limitation was not a big issue. In a next-word prediction task, the model uses the hidden state step by step as it reads. So the vector never has to hold an entire sentence at once. Machine translation was the first task that demanded exactly that. The sequence-to-sequence architecture [9, 10] uses two RNNs. The first RNN, called the encoder, reads the entire source sentence and keeps only its final hidden state. The second RNN, called the decoder, then generates the translation. The only thing it knows about the source sentence is the final hidden state that the encoder passes to it.

Now think about a 40-word sentence. To translate it, the decoder needs to know which words appeared in the source, what the subject and the object were, how the clauses connect, and the tense of the verbs. All of that has to fit inside that one final state, which is just a few hundred numbers. And this vector stays the same size whether the sentence has 5 words or 40, so the longer the sentence gets, the more information has to fight for the same limited space. This is why that final state is called a bottleneck.

The researchers came up with ideas to overcome this bottleneck in 2014. Sutskever et al. found a way, just reverse the source sentence [10]. Feed "C B A" instead of "A B C", and the translation quality improves noticeably. Why does this work? After reversing, the first words of the source become closer to the first words of the translation. So the earliest information, which is usually the most important part, travels a shorter distance inside the recurrence. It works because the model was struggling to carry information from far away. Although that worked, it was only a temporary fix to the problem. Encoder-decoder models did well on short sentences, but the quality dropped sharply as the sentences grew longer. The bilingual evaluation understudy (BLEU) score started falling even before the sentences reached fifty words [11]. And the decoder was not the real problem here. The problem was the summary, it simply had no space left for the details of a long sentence.

---

2. Attention in Neural Machine Translation

Additive Attention (Bahdanau et al., 2014)

In 2014, Bahdanau, Cho, and Bengio looked at this problem in a little different way [11]. Their diagnosis was simple, the fixed-length vector is the bottleneck, so why force the entire sentence through it? In their model, they proposed that the encoder keeps every hidden state it produces, not just the final one. Then at each decoding step, the decoder searches through these states and picks the ones that matter for the word it is currently producing. In their paper, they named the model RNNsearch, and compared it against the RNNencdec baseline [11]. To do this search, the model learns an alignment function, which gives each source position a score based on how relevant it is to the current word.

The mechanism has three steps. The first step computes the score. The score comes from a small feed-forward network, and this is why this version is called additive:

$e_{ij} = v^T \tanh(W_s s_{i-1} + W_h h_j)$

where $s_{i-1}$ is the decoder's previous hidden state, $h_j$ is the encoder state at source position $j$, and $W_s$, $W_h$, $v$ are learned during training. This whole thing is just a tiny neural network. It estimates how useful the source word $j$ is for the word the decoder is currently producing.

Second, softmax turns the raw scores into weights that sum to one:

$\alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k=1}^{T} \exp(e_{ik})}$

Third, we build the context vector. It is simply the weighted sum of all the encoder states, and this is the vector that goes to the decoder:

$c_i = \sum_{j=1}^{T} \alpha_{ij} h_j$

Key result: $c_i = \sum_j \alpha_{ij} h_j$ is a fresh, content-dependent summary of the source, rebuilt for every output word. The fixed bottleneck is gone. The decoder no longer has to remember the whole sentence, it consults it again at every step. Every attention mechanism in this series is a descendant of this weighted sum.

_{Bidirectional encoder producing forward and backward hidden states, per-step alignment weights at,1..T, and the decoder state chain that consumes the resulting context vector. Redrawn from Bahdanau et al., 2014 [11].}

There was one more thing that made this idea popular, the learned weights turned out to be interpretable. If you plot $\alpha_{ij}$ for an English-French sentence pair, you get a soft alignment matrix. Most of it follows the diagonal, because the two languages mostly follow the same word order. But wherever the order differs, the matrix crosses. For example, when "the European Economic Area" becomes "la zone économique européenne", the adjectives move to the other side of the noun, and the alignment shows exactly that flip [11]. The model found this soft alignment on its own and learned the French adjective order from it. Attending to the right source word made the next word prediction easier. And the fix worked on the length problem too. On long sentences, RNNsearch kept its translation quality roughly flat, while the quality of the fixed-vector baseline dropped sharply [11].

For the next two years, this additive attention was the default mechanism in neural machine translation.

Multiplicative Attention (Luong et al., 2015)

In 2015, Luong, Pham, and Manning asked a simple question, do we really need this whole extra network just to compute the scores [12]? It turned out we do not. They proposed a multiplicative variant, which scores the relevance with a plain dot product between the decoder and encoder states:

$e_{ij} = s_i^T h_j$

There are no weight matrices here and no $\tanh$, just a raw dot product between two vectors. A dot product is high when the two vectors point in the same direction, so it directly measures how similar the two states are. It is also cheaper: a dot product needs no extra weight matrices or a $\tanh$, unlike the small feed-forward network the additive form requires. And this same operation, with one small rescaling, becomes the core of the Transformer two years later.

Both of these mechanisms still share one assumption, that attention has to sit on top of a recurrent architecture. The RNN still does the sequential work, and attention only tells it where to look. The open question at the end of 2016 was whether this division of work should be changed.

---

What comes next

In this part, we saw three answers to the same memory problem. N-gram models could only see a few words back. RNNs could see everything, but they had to squeeze all of it into one fixed-size vector. And finally attention let the decoder look back at the whole input and pick what mattered. But both Bahdanau and Luong attention still worked inside an RNN. The recurrence still carried the sequence, token by token, with no parallelism yet, and that remained the bottleneck. The only thing that changed was that attention now told the RNN where to look.

The next part answers this question, is there a way to avoid the one-by-one sequence processing, the gradients that fade over long sequences, and the fixed-size vector that the whole history has to squeeze through?

Continue to Part 2: Attention All You Need →

---

References

[1] OpenAI (2022). Introducing ChatGPT. OpenAI Blog, November 30, 2022. https://openai.com/index/chatgpt/

[2] Hu, K. (2023). ChatGPT sets record for fastest-growing user base - analyst note. Reuters, February 1, 2023.

[3] Turing, A. M. (1950). Computing Machinery and Intelligence. Mind, 59(236).

[4] Ng, A. (2018). Sequence Models. Course 5 of the Deep Learning Specialization, DeepLearning.AI. Lecture notes compiled by A. Patel: https://github.com/ashishpatel26/Andrew-NG-Notes/blob/master/andrewng-p-5-sequence-models.md

[5] Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3).

[6] Bengio, Y., Ducharme, R., Vincent, P., & Jauvin, C. (2003). A Neural Probabilistic Language Model. Journal of Machine Learning Research, 3.

[7] Elman, J. L. (1990). Finding Structure in Time. Cognitive Science, 14(2), 179-211.

[8] Hochreiter, S., & Schmidhuber, J. (1997). Long Short-Term Memory. Neural Computation, 9(8).

[9] Cho, K., van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., & Bengio, Y. (2014). Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation. EMNLP 2014. arXiv:1406.1078.

[10] Sutskever, I., Vinyals, O., & Le, Q. V. (2014). Sequence to Sequence Learning with Neural Networks. NeurIPS 2014. arXiv:1409.3215.

[11] Bahdanau, D., Cho, K., & Bengio, Y. (2014). Neural Machine Translation by Jointly Learning to Align and Translate. ICLR 2015. arXiv:1409.0473.

[12] Luong, M.-T., Pham, H., & Manning, C. D. (2015). Effective Approaches to Attention-based Neural Machine Translation. EMNLP 2015. arXiv:1508.04025.