Intro to AI : Part 2

RNNs and Transformers

Mehmet Kerem Turkcan
Associate Research Scientist
Center for Smart Streetscapes, Columbia University
New York, USA
keremturkcan.com;  mkt2126@columbia.edu

Move with the arrow keys, a presentation clicker, or the buttons at the bottom left; the gear at the bottom right opens the slide settings.

Where Part 1 left us

  1. Tokens: text is cut into pieces the size of syllables, and each piece carries a whole number ID.
  2. The game: next token prediction, scored with a probability for every token in the vocabulary.
  3. Markov chains: probabilities counted from neighboring pairs; the counting is maximum likelihood estimation.
  4. The wall: because longer context multiplies the count table by 50,000 per token, the counts a longer chain needs never appear in any corpus.

Today we cross that wall twice: with a network that reads token by token and carries a memory, and with a network that reads the whole window at once.

From count tables to learned functions

A neural network computes next token probabilities with arithmetic: multiplications and additions arranged in layers, steered by millions of adjustable numbers, called weights.

The girl who fed the network millions of weights the 0.31 her 0.24 a 0.11
Context in, probabilities out; the bars are illustrative. Changing the weights changes the probabilities.

Training shows the network a context from the corpus, compares its probabilities with the token that actually came next, and nudges every weight so that the true token scores higher. After millions of such nudges, made by a procedure called gradient descent, the corpus becomes probable under the network.

Because the weights are shared across all contexts, similar contexts receive similar predictions: the network can score contexts it has never seen.

Reading with a running summary

Question for the class: you read a story aloud, one word at a time. Between two words, what is in your head?

A compressed summary of everything so far: who the characters are, what just happened, how the current sentence is shaped. Each new word updates the summary; the summary, and only the summary, carries the past forward.

A recurrent neural network, RNN for short, is built on exactly this plan.

For the classroom: read three sentences of any story aloud, stop, and ask students to write down what they are holding in mind; their notes are a hidden state.

The RNN step

The RNN keeps a memory, called the hidden state: a list of numbers of fixed length.

\text{memory}_{\text{new}} = f(\text{memory}_{\text{old}},\ \text{token})

The same function f, with the same weights, runs at every step. A second function maps the memory to next token probabilities at any point.

Each step feeds on the result of the step before it. This looping pattern is called recurrence, a form of recursion, and it gives the network its name.

f the memory loops back: hidden state next token in probabilities out
One cell, reused forever.

Unrolling the loop

Unrolling the loop draws one copy of f for every token; all copies share the same weights. The memory persists and is updated from copy to copy.

f f f f f empty the memory persists and is updated from cell to cell The girl who fed the predict token 6
For the first token to matter at the end, its trace must survive every memory update.

Pressure on a memory of fixed size

The hidden state has a fixed length, so a long document must fit into it: early details fade as new tokens keep arriving.

Training operates the same way. Because the correction signal must travel backward through every step, it weakens along the way; this behavior is known as the vanishing gradient problem.

Gated designs, among them the LSTM from 1997, guard the memory with learned gates and hold information across many more steps.

f f f f f token 1 enters here its trace, many steps later the training signal travels backward through every cell, and it fades too

One step at a time

Each RNN step needs the memory produced by the step before it, so a text of 1,000 tokens takes 1,000 steps in order. The order cannot be broken; every step waits.

Modern AI hardware, the GPU, performs enormous batches of arithmetic at the same time. Because a computation that must proceed step by step leaves most of that capacity idle, training an RNN on a very large corpus becomes slow.

step 1 step 2 step 3 step 4 step 5 step 6 step 7 step 8 time: each step waits for the one before it

2017: the transformer

In 2017, a research team at Google published Attention Is All You Need, the paper that introduced the transformer.

The transformer, a neural network for sequences, has two defining properties: (i) it processes every token in its window at the same time; (ii) it uses no recurrence: no step waits for a previous step.

Every position can look directly at every other position in the window. The component that chooses where to look is called attention; today we only need its name, and a later lesson opens it up.

The window has a fixed maximum size, called the context window; Gemini 1.5, a 2024 model from Google, fits one million tokens in it.

Direct looks at any distance

Part 1 ended with a verb that depends on a word seven tokens back. A transformer position reads all earlier positions directly, near or far; the arcs below sketch one such set of looks.

The girl who fed the three noisy cats ____ smiling. the strongest look lands on girl
Line opacity sketches the strength of each look; the values are illustrative. The mechanics of attention belong to a later lesson.

No recursion: direct connections

RNNs think one step at a time, relying on memory and the last token girl who fed cats ____ 4 steps here; 999 for a window of 1,000 Transformer: one direct step, at any distance girl who fed cats _ 1 step every position also computes at the same time Short paths between tokens that sit far apart; parallel work that keeps GPUs busy. These two properties made training on very large text collections practical.
Within each transformer layer, all positions compute at once; a real model stacks such layers.

The large language model

A large language model, LLM for short, is a transformer with a very large number of weights, trained on next token prediction over a very large collection of text.

To write, the model predicts probabilities for the next token, samples one, and, after appending it to the window, predicts again.

predict sample append one new token per cycle

This loop matches the Markov chain walk from Part 1: the game never changed. The probabilities now come from a deep network that reads a very long window.

Check for understanding

1. A model predicts the next token by reading only the current token. Which family does it belong to?

A Markov chain; the Markov property says the next state depends only on the current state.

2. What does an RNN carry from one step to the next, and what limits it?

The hidden state, a list of numbers with a fixed length; everything read so far must fit inside it.

3. In a transformer window of 1,000 tokens, how many sequential steps does information from token 1 cross to reach position 1,000?

None along the sequence: any position reads any other position directly through attention.

For the classroom: reveal each answer only after the class commits; the three questions map to the three model families of this unit.

Part 2 Overview

  1. Learned functions: weights replace count tables, and gradient descent tunes them so that the corpus becomes probable.
  2. RNNs: read token by token while carrying a hidden state of fixed length; recurrence defines them, the memory fades, and the steps wait in line.
  3. Transformers: read the whole window at once through attention, with no recurrence, short paths, and parallel work.
  4. LLMs: very large transformers trained on next token prediction; they write by the loop of predict, sample, append.

Next lesson: the transformer's two ends: how tokens become lists of numbers, and how a small feedforward machine reads the answer out.

Sources and further reading

  • J. L. Elman, 1990: Finding Structure in Time; an early recurrent network for sequence learning.
  • S. Hochreiter and J. Schmidhuber, 1997: the LSTM architecture; gated memory for long sequences.
  • A. Karpathy, 2015: The Unreasonable Effectiveness of Recurrent Neural Networks; a readable blog tour of RNN text generation.
  • A. Vaswani and colleagues, 2017: Attention Is All You Need; the paper that introduced the transformer.
  • Google DeepMind, 2024: the Gemini 1.5 technical report; the one million token context window.

Slides: Mehmet Kerem Turkcan, Center for Smart Streetscapes, Columbia University; keremturkcan.com; mkt2126@columbia.edu

Intro to AI, Part 2: RNNs and TransformersM. K. Turkcan, Columbia University