In 1984, someone named Mark V. Shaney started posting on net.singles Usenet (think 80s Reddit). According to one witness:
Mark was a member of a UseNet News group called net.singles, a users group chock full of dating tips, lonely heart chatter…Mr Shaney was a little goofy but he was always there. He chimed in with poetic opinions on romantic empathy: “A I’ve commented before, really relating to someone involves standing next to impossible.”
And he had a great Groucho Marx sense of humor: “One morning I shot an elephant in my arms and kissed him. So it was too small for a pill? Well, it was too small for a while.” And his idea of a good closing was: “Oh, sorry. Nevermind. I am afraid of it becoming another island in a nice suit.” ----Mark
Here are some other quotes from Mark:
- “I spent an interesting evening recently with a grain of salt.”
- “I hope that there are sour apples in every bushel.”
Source: wiki
As you can see, Mark’s messages were odd but grammatically correct. He sounds like a person who has been awake for 40 hours, lonely and wants to get off his chest about relationships.
Mark V. Shaney was a computer program. In fact, it was a fairly simple program. It read text (a book and some Usenet postings) and created a table with two columns: every pair of words that appeared next to each other, and the word that came right after them. That’s all it stored. To write a sentence, it looked up the last 2 words it had written, picked one of the words that had followed them in the table, added it, and repeated.
Here’s what it did. Suppose you “train” it on two sentences:
- “I am serious because it is critical.”
- “I am happy because it is funny.”
The program uses a sliding window that slides across words, 2 at a time and writes down what follows them. That is:
| Last 2 words | Followed by |
|---|---|
| I am | serious, happy |
| am serious | because |
| am happy | because |
| serious because | it |
| happy because | it |
| because it | is, is |
| it is | critical., funny. |
Now to generate new text, you pick a pair to start e.g. “I am”. It’s followed by 2 words in the table: “serious” and “happy”. Flip a coin and choose 1. Suppose “happy” wins. Now repeat with “am happy”, you get “because” (only choice). Keep going and you may get the following sentence:
I am happy because it is critical.
Notice that the output sentence wasn’t in your training example dataset of 2 lines (I use the word ‘training’ loosely here: training means running through each sentence and building the table above.) Your program generated something new. But what held Mark V. Shaney from taking over the world as an intelligent AI program. Well, 2 things in my opinion:
- Mark’s memory is severely limited to 2 words only. By the time Mark is picking “it is”, it has no memory that the sentence started with “I am serious”.
- Mark can only continue generating text it has seen before verbatim. E.g. If we ask Mark to continue “He is” in our example above, Mark will fail because he hasn’t seen “He is” in the training dataset.
And these problems fight with each other. Fix the 1st by giving Mark longer memory and the 2nd problem gets worse: with a 20 word window, almost no sequence typed by anyone will ever match in the table. You can’t algorithm your way out of these problems.
In some abstract sense, modern LLMs like ChatGPT or Bard work the same way. You give them some text, they predict the next word (token), append it to the sentence and repeat again. But the approach they take to predict the next word couldn’t be more different than Mark’s. Let’s look at how LLMs generate text in this post.
How LLMs guess the next word
Let’s massively simplify: strip everything away and think of an LLM as a single function. It takes a sequence of words (or tokens) as input and outputs a table of probabilities, one for every word it knows i.e. its vocabulary. The higher the probability the more likely it is that word is the one that comes next.
A quick word on ‘words’ and ‘tokens’: A token is a word in LLMs vocabulary. A token can be a word e.g. ‘cent’, part of a word ‘imeter’ or even punctuation.
Suppose you pas the following sequence of words as input to our LLM function:
The build broke on Friday because someone
The LLM functions returns output like the table below:
| Next word | Probability |
|---|---|
| forgot | 14% |
| pushed | 11% |
| merged | 9% |
| changed | 7% |
| deployed | 6% |
| … | … |
| banana | 0.0001% |
The probabilities add to 100% for every word in the table with higher probabilities at the top and very low ones at the bottom.
Unlike Mark, the LLM isn’t looking up anything. Mark had a table of every word pair he’d ever seen, with the words that followed. An LLM has no such table and doesn’t store its training text. What it stores instead is a few billion numbers (its parameters, or weights) that were adjusted during training and a fixed recipe for turning your input into a probability table using those numbers. Send it “The build broke on Friday because someone” and it computes the table from scratch, even though it has almost certainly never seen that exact sentence before. That’s the difference between remembering and generalizing, and it’s the whole reason an LLM can handle inputs Mark would choke on.
Tokens are not words
Expanding on our earlier definition: a token is the primary unit which the model reads and writes. It can be a whole word, a piece of a word, or a punctuation mark. There’s no universal list of tokens. Each model family builds its own vocabulary from its training data (before training starts), which is why the same sentence can be 12 tokens for one model and 15 for another. As a rule of thumb, common words get a token of their own and rare words get split into multiple.
Models work in tokens rather than words for practical reasons. A fixed vocabulary of 30,000 to 100,000 can represent any string, including words the model has never seen, code, URLs and other languages.
Note: For developers, tokens matter because this is how OpenAI bills you: usage is priced on input and output tokens. Also, tokens define context limits.
How LLMs generate a complete sentence
In the previous section, we looked at how LLMs predict the next word (list of probabilities highest to lowest). But how does it generate poems, answers to multiple-choice questions, etc.
Here’s the algorithm:
- Turn the input text into a list of tokens.
- Give the entire list to the model.
- The model returns a probability table: one number for every token in its vocabulary that it could produce next.
- Pick one token from the table.
- Add that token to the end of the list of input tokens.
- Stop if the token is special e.g. “end of text” or if the list has hit the length limit. Return the list.
- Otherwise, go back to step 2 with the longer list.
That’s it. Each pass through the loop produces exactly one token, and the model sees its own previous output as part of the input on the next pass.
This is also known as autoregressive generation: each output becomes part of the next input. There are few consequences of it:
- The model has no plan. It just starts without deciding how the sentence would end.
- The system could stream tokens as they are generated in each step of the loop. This is how you see words appear one by one when you ask ChatGPT to improve your email to your manager.
- Cost grows with length. Because it appends new tokens to all the previously generated tokens and repeats, conversations get slower and more expensive towards the end, which is one reason why context limits exist.
- The loop ends when the model outputs an end-of-text token or the sequence reaches the max limit you defined. There’s no step that looks at the output and decides whether to stop or continue.
Now let’s look at one thing we hand-waved: how to pick the next token from the table of probabilities. While it may sound obvious to pick the token with the highest probability, in reality if we did that, we’d get very boring outputs.
Don’t always choose the highest probability
The obvious approach is to always choose the word with the highest probability (also known as greedy decoding). It’s a bad idea for LLMs: the output comes out bland and after a few sentences it starts to repeat itself over and over again as I’m sure you’ve seen. There’s research showing that even strong models degenerate when you maximize probability for every step. Greedy decoding is also why 2 people asking the same question would get the same answer every time, which is what the repetitive and boring version looks like and honestly if this is how ChatGPT worked, it wouldn’t have been as huge as it is.
The fix is to add some randomness. Instead of always choosing the top word (highest probability), the model rolls a weighted dice: a word with 14% probability gets picked about 14% of the time, a word with 2% gets picked about 2% of the time. Most of the time you still get a likely word, but not always, and that’s enough to break the loops and bland-ness.
How much randomness to add? That’s controlled by a parameter called temperature which is a number between 0 and 2. Pass it as 0 and the dice will always favor the top word (greedy decoding). Pass it as 2 and the answers will stop making sense. Pass it as somewhere in between 0 and 1, and you start getting better outputs.
Usually, a value from 0.7 to 1 works best in most cases. For some use cases e.g. if you are using GPT API for classification of some text documents, you’d want to use lower values or even 0 because you’d want the same answer (label) each time.
Note: This is what people refer to as “determinism” in LLMs. At lower values of temperature, the LLM outputs “mostly deterministic” text. At higher values, the models become “less deterministic”.
Where do the probabilities come from?
Mark V. Shaney got his from its table: look at every pair of words to find out what followed.
LLMs replace Mark’s table with a neural network (actually a very large and complex architecture of neural networks). Instead of storing what followed each exact context, the network has billions of adjustable numbers (called parameters) that turn any input into a probability table.
Training is conceptually simple: show it a chunk of text e.g. “the sky is …” have it predict the next word e.g. it might predict “blue” or “gray”, measure how wrong it was based on the answer in the training text, and then nudge it towards the right answer. Repeat this process over a staggering amount of text. GPT-3 has 175 billion parameters and was trained on ~300 billion tokens.
So that’s the whole thing at a very high level. Hope you enjoyed the post.