by Mark Liffiton, generated using multiple large language models and a repeated, iterative process of review and refinement.
Markov chains provide an early, simple way to generate text by choosing what comes next from patterns in a source text. Modern language models build on a related next-token idea, but use much more capable methods.
1. The Big Illusion: How Does AI Actually “Write”?¶
When you type a prompt into ChatGPT and watch complete sentences glide across your screen, it feels as if you are conversing with a conscious, thoughtful digital brain.
However, the underlying process in an autoregressive language model is simpler than it may appear: it does not write a whole sentence all at once. It repeatedly predicts what token should come next. This is a useful description of how large language models such as ChatGPT generate text.
The idea has a long history. Andrey Markov developed the mathematical framework for Markov chains in the early 1900s. Later researchers applied related statistical methods to language. A modern autoregressive language model performs a much more sophisticated version of one repetitive task:
The Next-Token Rule of Autoregressive Language Models
“Look at the tokens written so far, estimate how likely every possible next token is, then pick one — the likeliest tokens win most often, but they don’t always win.”
That rule hides one important choice: which next token should the language model actually pick? The most conservative answer is always the single most likely token. But if a generator did that, the same prompt would produce the exact same response every time — no variety at all. So language models can treat the probabilities like a weighted lottery instead: the likeliest tokens usually win, but sometimes a less obvious token gets picked. That deliberate randomness — called sampling — is why the same prompt can produce many different replies, and we will see it in action when we generate text in Section 4.
Once that next token is picked, the language model adds it to the text and asks the same question again. To understand this next-token idea, we can study a much simpler text generator: the Markov Chain.
2. Building a Markov Chain: From Text to Probability¶
How do we turn a collection of sentences into a mathematical model? The process is mechanical and follows a few key steps: Tokenization, Counting, and Normalization.
Starting Point: The Corpus (Source Text)¶
Imagine we want to train our AI on a small “corpus” of 5 cafe reviews:
- “I love iced coffee.”
- “I love iced coffee.”
- “I love hot coffee.”
- “I drink iced tea.”
- “I drink hot coffee.”
Step 1: Tokenization (Breaking Text Into Pieces)¶
Before counting, the computer splits each sentence into individual units called tokens. In our simple example, each word is its own token:
- “I love iced coffee.” →
["I", "love", "iced", "coffee."]
In larger models, tokens can be whole words, parts of words, or even single characters. For now, we’ll treat each word (including attached punctuation) as one token.
Step 2: The Sliding Window (Counting)¶
The computer does not understand meaning. To “train,” it slides a window across the text and tallies up which words follow which. This window size is known as an N-Gram:
- 1-Gram (Unigram): No context at all. Just counts how often each word appears. Cannot predict the next word.
- 2-Gram (Bigram): Uses 1 word of context. The model looks at the previous word to predict the next one.
- 3-Gram (Trigram): Uses 2 words of context. The model looks at the two previous words to predict the next one.
- N-Gram: The general term. An N-Gram uses N-1 words of context to predict the next word.
To put it another way: an N-gram is a run of N words, and the first N-1 of those words are the context the model uses to predict the last one. That is why a “2-Gram” provides only 1 word of context, a “3-Gram” provides 2, and so on.
In our example, we are using a 2-Gram (Bigram) model, meaning the computer looks at the previous word and asks: “In my text, what word comes immediately after this one?”
- It sees “I” → followed by “love” (3 times)
- It sees “I” → followed by “drink” (2 times)
- It sees “love” → followed by “iced” (2 times)
- It sees “love” → followed by “hot” (1 time)
- It sees “drink” → followed by “iced” (1 time)
- It sees “drink” → followed by “hot” (1 time)
- It sees “iced” → followed by “coffee.” (2 times)
- It sees “iced” → followed by “tea.” (1 time)
- It sees “hot” → followed by “coffee.” (2 times)
Step 3: The Probability Table (Normalization)¶
Finally, the computer converts these counts into probabilities. It divides the number of times a specific transition happened by the total number of times the starting word appeared.
| Current Word | Next Word Candidate | Count | Probability |
|---|---|---|---|
| I | love | 3 of 5 | 60% |
| I | drink | 2 of 5 | 40% |
| love | iced | 2 of 3 | 67% |
| love | hot | 1 of 3 | 33% |
| drink | iced | 1 of 2 | 50% |
| drink | hot | 1 of 2 | 50% |
| iced | coffee. | 2 of 3 | 67% |
| iced | tea. | 1 of 3 | 33% |
| hot | coffee. | 2 of 2 | 100% |
3. Visualizing the Model: The Transition Map¶
Once the counting is done, the model is organized into a “roadmap” of interconnected circles (States) and one-way roads with percentages (Transitions). Each circle represents a word, and each arrow shows how likely it is to transition from one word to the next. Thicker arrows represent higher probabilities.
The “Memoryless” Rule (The Markov Property) This is the defining characteristic of a Markov Chain: the probability of the next state depends only on the current state, not on the history of how you got there. Once the AI lands on the word “iced”, it completely forgets whether it arrived via “love iced” or “drink iced”. All it knows is the probabilities for what follows “iced”. You can widen the context window (e.g., to 2 or 3 words), and the property still holds — the next word simply depends on that wider “current state” of recent words, and nothing before them.
4. Generating Text: The Act of Sampling¶
How do we make the AI write a brand new sentence? We perform a process called Sampling.
Imagine every word has a custom prize wheel. The slices on the wheel are sized to match the probabilities we calculated. When it is time to pick the next word, the AI “spins the wheel.”
Step-by-Step: A Sentence is Born¶
Let’s follow a single generation from scratch:
- Start: We begin with the word “I”.
-
The First Spin: The AI looks at the “I” wheel. It has a 60% chance for “love” and 40% for “drink”. Let’s say the wheel stops with the pointer over “love”.
- Current sentence: “I love”
-
The Second Spin: Now we look at the “love” wheel (67% iced, 33% hot). The wheel stops with the pointer over “hot”.
- Current sentence: “I love hot”
-
The Third Spin: We look at the “hot” wheel (100% coffee.). The wheel stops with the pointer over “coffee.”.
- Current sentence: “I love hot coffee.”
- The End: In the source text, “coffee.” only ever appeared at the end of a review — no word ever follows it. So the model has no “coffee.” wheel to spin, and the AI stops.
5. The Memory Trade-off: Context vs. Complexity¶
While we can increase the “context” by using a larger window (looking at 2, 3, or more previous words at a time), this introduces a massive technical challenge known as the Combinatorial Explosion.
Why More Context Helps (and Hurts)¶
Imagine a model trained on a large collection of English text. Consider the word “ran”:
- 1-word context (only looking at “ran”): The model has seen “ran” followed by hundreds of different words — “fast”, “away”, “out of”, “for president”, “the business”, “through the house”, “dry”, “low”, “into my arms”. The predictions are grammatically valid but wildly unpredictable.
- 2-word context (looking at “She ran”): The possibilities narrow — “fast”, “away”, “to the store”, “for president”. More coherent.
- 3-word context (looking at “The business ran”): Completely different predictions — “profitably”, “into debt”, “out of supplies”, “for years”.
Two words of context resolved the ambiguity that one word could not. But here is the catch:
These are the N-Grams from Section 2 — remember, an N-Gram uses N-1 words of context, so a 2-Gram (bigram) looks back 1 word, a 3-Gram (trigram) looks back 2 words, and so on. With a vocabulary of 10,000 common English words, here is how many distinct contexts of each length the model must be able to recognize:
| Context Size (words looked back) | N-Gram Name | Possible Distinct Contexts |
|---|---|---|
| 1 word | 2-Gram (Bigram) | 10,000 |
| 2 words | 3-Gram (Trigram) | 100,000,000 |
| 3 words | 4-Gram | 1,000,000,000,000 |
That’s one trillion possible unique 3-word phrases — a truly massive number.
Most of those combinations never appear in any training data. So a basic 3-word context model could encounter phrases it has never seen — and have no directly observed prediction to make.
The Big Dilemma:
- Window too small: The AI produces grammatically okay phrases but rambles because it forgets what it was talking about just a few words ago.
- Window too large: Most phrase combinations never appear in the training data, so a model has no directly observed transition. When it does find a match, it may copy the source text word-for-word instead of generating anything new.
This is a fundamental limitation of fixed-order Markov Chains: they can only look back a fixed number of words. Longer contexts are possible, but they become increasingly sparse and expensive to model. Modern language models use mechanisms including Attention to make better use of a much larger context, which we discuss next.
6. How Attention Helps With the Memory Problem¶
Modern language models use a mechanism called Attention to help use more context than a small fixed-order Markov model. Within the model’s finite context window, attention lets each token compare itself with other tokens and calculate how strongly to use information from them.
Think of it like reading a long paragraph and being asked a question about the first sentence. You don’t need to re-read every word equally — you focus on the relevant parts. That is what Attention does:
- It weighs each previous word by how relevant it is to predicting the next one.
- Distant but important words (like a character’s name mentioned 50 words ago) get high attention.
- Nearby but irrelevant words get low attention.
This helps the model use distant information without requiring every possible long phrase to be stored as a separate table entry. Notice the difference from a basic Markov model: after “The old man who lived in the blue house…”, that model would need a matching context in its training data to have a directly observed transition. A language model can use learned representations to relate parts of the context and generalize, even when that exact string has never appeared before. Attention helps make those relationships available, but it does not provide unlimited memory or eliminate all computational complexity; the model also relies on its learned parameters and other neural-network components.
This is one of the important differences between modern LLMs and simple Markov chains, even though both can be used to predict what comes next.
7. Markov Chains vs. Modern LLMs¶
| Concept | Markov Chain (1906) | Large Language Model (Today) |
|---|---|---|
| Core Task | Predict next word based on probability | Predict next token based on probability |
| Memory Span | A fixed number of previous tokens | A much larger context window, weighted by relevance (Attention) |
| Understanding | ❌ None. Exact word matches only. | ✅ Deep semantic vectors (works with meanings) |
| Learning | Manual tallying of word pairs | Billions of parameters in a neural network |
8. Key Takeaways¶
- The shared idea is next-token prediction: Both a Markov chain and an autoregressive language model generate text one token at a time by estimating a probability distribution for what comes next.
- A Markov chain has a short, fixed memory: Its next prediction depends only on the current state, such as the previous word or a fixed-size phrase. More context can help, but the number of possible phrases grows quickly and most will be rare or unseen.
- Sampling controls variety: Choosing the highest-probability token every time is predictable; sampling from the distribution allows multiple possible continuations. A likely token is not necessarily a true or reliable one.
- Modern language models generalize beyond lookup tables: Learned neural representations and Attention help them relate relevant parts of a larger context, even when the exact phrase was not in the training data. They still have finite context and can produce fluent errors.