This dialog is used to create the enriched transcript of the 'Let's build the GPT Tokenizer' video

Raw Transcript (from Scribe)

TIP: To make markdown images visible to AI you can add #ai anchor tags to image urls like [](image_path#ai)*

TIP: To visualize the auto-cropped version of an image you can change the image url from [](image_{idx}.jpg) to [](image_{idx}_cropped.jpg)*

TIP: add_tscript_msg will add the full transcript as a single note msg, then you can ask questions about the transcript overall, such as the external resources that are mentioned, a high level summary, speakers, etc... Once you are done don't forget to hide that message to save token space.

add_tscript_msg(scribe_dst, yt_video_id='zduSFxRajkE')

Introduction to Tokenization

[00:00] Andrej Karpathy: Hi everyone. So in this video, I'd like us to cover the process of tokenization in large language models. Now, you see here that I have a sad face, and that's because, well, tokenization is my least favorite part of working with large language models. But unfortunately, it is necessary to understand in some detail because it is fairly hairy, gnarly, and there are a lot of hidden foot guns to be aware of. And a lot of oddness with large language models typically traces back to tokenization.

A Jupyter Notebook open in a web browser. The first cell is a Markdown cell with the text 'Tokenization :('

[00:25] Andrej Karpathy: So what is tokenization? Now, in my previous video, "Let's build GPT from scratch," we actually already did tokenization, but we did a very naive, simple version of tokenization.

A YouTube video page titled 'Let's build GPT: from scratch, in code, spelled out.' by Andrej Karpathy.

[00:36] Andrej Karpathy: So when you go to the Google Colab for that video, you see here that we loaded our training set. And our training set was this Shakespeare dataset. Now in the beginning, the Shakespeare dataset is just a large string in Python. It's just text. And so the question is, how do we plug text into large language models?

A Google Colab notebook titled 'Building a GPT'. The screen shows the beginning of the Shakespeare dataset text.

[00:57] Andrej Karpathy: And in this case here, we created a vocabulary of 65 possible characters that we saw occur in this string. These were the possible characters, and we saw that there are 65 of them. And then we created a lookup table for converting from every possible character, a little string piece, into a token, an integer.

[01:18] Andrej Karpathy: So here, for example, we tokenized the string "hi there" and we received this sequence of tokens. And here we took the first 1,000 characters of our dataset and we encoded it into tokens. And because this is character level, we received 1,000 tokens in a sequence. So token 18, 47, etc.

Python code in a Colab notebook showing the tokenization of the first 1000 characters of a dataset into a sequence of 1000 integers.

[01:41] Andrej Karpathy: Now, later we saw that the way we plug these tokens into the language model is by using an embedding table. And so basically, if we have 65 possible tokens, then this embedding table is going to have 65 rows. And roughly speaking, we're taking the integer associated with every single token, we're using that as a lookup into this table, and we're plucking out the corresponding row. And this row is a, uh, is trainable parameters that we're going to train using backpropagation. And this is the vector that then feeds into the transformer, um, and that's how the transformer sort of perceives every single token.

Python code defining a BigramLanguageModel class. The line 'self.token_embedding_table = nn.Embedding(vocab_size, n_embed)' is highlighted, showing the creation of an embedding table.

[02:19] Andrej Karpathy: So here we had a very naive tokenization process that was a character-level tokenizer. But in practice, state-of-the-art, uh, language models, people use a lot more complicated schemes, unfortunately, for, uh, constructing these, uh, token vocabularies. So we're not dealing on a character level, we're dealing on a chunk level. And the way these, um, character chunks are constructed is using algorithms such as, for example, the byte-pair encoding algorithm, which we're going to go into in detail, um, and cover in this video.

Tokenization in GPT-2 and Llama 2

[02:52] Andrej Karpathy: I'd like to briefly show you the paper that introduced byte-level encoding as a mechanism for tokenization in the context of large language models. And I would say that that's probably the GPT-2 paper. And if you scroll down here to the section "Input Representation," this is where they cover tokenization, the kind of properties that you'd like the tokenization to have. And they conclude here that they're going to have a tokenizer where you have a vocabulary of 50,257 possible tokens. And the context size is going to be 1,024 tokens. So in the, in the attention layer of the transformer neural network, every single token is attending to the previous tokens in the sequence, and it's going to see up to 1,024 tokens. So tokens are this fundamental unit, um, the atom of, uh, large language models, if you will. And everything is in units of tokens, everything is about tokens. And tokenization is the process for translating strings or text into sequences of tokens and, uh, vice versa.

A screenshot of the GPT-2 research paper, highlighting the 'Input Representation' section which discusses Byte Pair Encoding (BPE), a vocabulary size of 50,257, and a context size of 1024 tokens.

[03:55] Andrej Karpathy: When you go into the Llama 2 paper as well, I can show you that when you search "token," you're going to get 63 hits. Um, and that's because tokens are, again, pervasive. So here they mentioned that they trained on 2 trillion tokens of data and so on. So we're going to build our own tokenizer. Luckily, the byte-pair encoding algorithm is not, um, that super complicated, and we can build it from scratch ourselves and we'll see exactly how this works.

A screenshot of the Llama 2 research paper. The text 'Our training corpus includes a new mix of data from publicly available sources, which does not include data from Meta’s products or services. We made an effort to remove data from certain sites known to contain a high volume of personal information about private individuals. We trained on 2 trillion tokens of data as this provides a good performance-trade-off.' is visible.

The Weirdness of Tokenization

[04:20] Andrej Karpathy: Before we dive into code, I'd like to give you a brief taste of some of the complexities that come from the tokenization because I just want to make sure that we've motivated it sufficiently for why we are doing all this and why this is so gross. So, tokenization is at the heart of a lot of weirdness in large language models, and I would advise that you do not brush it off. A lot of the issues that may look like just issues with the neural architecture or the large language model itself are actually issues with the tokenization and fundamentally trace back to it.

[04:50] Andrej Karpathy: So, if you've noticed any issues with large language models can't, you know, not able to do spelling tasks very easily, that's usually due to tokenization. Simple string processing can be difficult for the large language model to perform natively. Uh, non-English languages can work much worse, and to a large extent, this is due to tokenization. Sometimes LLMs are bad at simple arithmetic, also can trace be traced to tokenization. Uh, GPT-2 specifically would have had quite a bit more issues with Python than, uh, future versions of it due to tokenization. There's a lot of other issues. Maybe you've seen weird warnings about a trailing whitespace. This is a tokenization issue. Um, if you had asked GPT earlier about "SolidGoldMagikarp" and what it is, you would see the LLM go totally crazy and it would start going off about completely unrelated tangent topic. Maybe you've been told to use YAML over JSON with structured data. All that has to do with tokenization. So basically, tokenization is at the heart of many issues.

A Jupyter Notebook with a Markdown cell titled 'Tokenization :('. It contains a bulleted list of issues in LLMs that are caused by tokenization, such as problems with spelling, string processing, non-English languages, arithmetic, and Python code.

Visualizing Tokenization

[05:50] Andrej Karpathy: I will loop back around to these at the end of the video, but for now, let me just, um, skip over it a little bit. And let's go to this web app, um, the tiktokenizer that vercel.app. So I have it loaded here. And what I like about this web app is that tokenization is running sort of live in your browser in JavaScript. So you can just type here stuff, "hello world," and the whole string re-tokenizes.

A web application called 'Tiktokenizer'. The left pane is a text editor, and the right pane shows the tokenized output. The text includes examples of English, arithmetic, Korean, and Python code.

[06:15] Andrej Karpathy: So, here what we see on the left is the string that you put in. On the right, we're currently using the GPT-2 tokenizer. We see that this string that I pasted here is currently tokenizing into 300 tokens. And here they are sort of, uh, shown explicitly in different colors for every single token. So for example, uh, this word "Tokenization" became two tokens, the token 30,642 and 1,634. The token " is" is token 318. Be careful, on the bottom you can show whitespace, and keep in mind that there are spaces and, uh, slash n, new line characters in here, but you can hide them for clarity. The token " at" is token 379. The token " the" is 262, etc. So you notice here that the space is part of that, uh, token chunk.

[07:16] Andrej Karpathy: Now, so this is kind of like how our English sentence broke up, and that seems all well and good. Now, now here I put in some arithmetic. So we see that, uh, the token 127 plus and then token 6, space 6, followed by 77. So what's happening here is that 127 is feeding in as a single token into the large language model, but the, um, number 677 will actually feed in as two separate tokens. And so the large language model has to, uh, sort of, um, take account of that and process it correctly in its network. And see here, 804 will be broken up into two tokens. And it's all completely arbitrary. And here I have another example of four-digit numbers, and they break up in a way that they break up, and it's totally arbitrary. Sometimes you have, um, multiple digits, a single token. Sometimes you have individual digits as many tokens, and it's all kind of pretty arbitrary and comes out of the tokenizer.

[08:15] Andrej Karpathy: Here's another example. We have the string "Egg." And you see here that this became two tokens. But for some reason when I say, "I have an egg," you see when it's a " an egg," it's two tokens, it's, sorry, it's a single token. So just "Egg" by itself in the beginning of a sentence is two tokens, but here as a " an egg" it's suddenly a single token for the exact same string. Okay? Here, lowercase "egg" turns out to be a single token, and in particular, notice that the color is different, so this is a different token. So this is case sensitive. And of course, uh, capital "EGG" would also be different tokens, and again, um, this would be two tokens arbitrarily. So for the same concept, "egg," depending on if it's in the beginning of a sentence, at the end of a sentence, lowercase, uppercase, or mixed, all this will be, uh, basically very different tokens and different IDs. And the language model has to learn from raw data from all the internet text that it's being trained on that these are actually all the exact same concept. And it has to sort of group them in the parameters of the neural network and understand just based on the data patterns that these are all very similar, but maybe not almost exactly similar, but very, very similar.

[09:30] Andrej Karpathy: Um, after the egg demonstration here, I have, um, an introduction from OpenAI's ChatGPT in Korean. So, "mannaseo bangawoyo," uh, etc. Uh, so this is in Korean. And the reason I put this here is because you'll notice that, um, non-English languages work slightly worse in ChatGPT. Part of this is because, of course, the training dataset for ChatGPT is much larger for English than for everything else. But the same is true not just for the large language model itself, but also for the tokenizer. So when we train the tokenizer, we're going to see that there's a training set as well. And there's a lot more English than non-English. And what ends up happening is that we're going to have a lot more longer tokens for English.

[10:17] Andrej Karpathy: So, how do I put this? If you have a single sentence in English and you tokenize it, you might see that it's 10 tokens or something like that. But if you translate that sentence into, say, Korean or Japanese or something else, you'll typically see that the number of tokens used is much larger. And that's because the chunks here are a lot more broken up. Uh, so we're using a lot more tokens for the exact same thing. And what this does is it bloats up the sequence length of all the documents. So you're using up more tokens, and then in the attention of the transformer, when these tokens try to attend each other, you are running out of context, um, in the maximum context length of that transformer. And so basically, all the non-English text is stretched out from the perspective of the transformer, and this just has to do with the, um, training set used for the tokenizer and the tokenization itself. So it will create a lot bigger tokens and a lot larger groups in English, and it will have a lot of little boundaries for all the other non-English text. So if we translated this into English, it would be significantly fewer tokens.

[11:24] Andrej Karpathy: The final example I have here is a little snippet of Python for doing FizzBuzz. And what I'd like you to notice is, look, all these individual spaces are all separate tokens. They are token 220. So, uh, 220, 220, 220, 220, and then " if" is a single token. And so what's going on here is that when the transformer is going to consume or try to, uh, create this text, it needs to, um, handle all these spaces individually. They all feed in one by one into the entire transformer in the sequence. And so this is being extremely wasteful, tokenizing it in this way. And so, as a result of that, GPT-2 is not very good with Python. And it's not anything to do with coding or the language model itself, it's just that if you use a lot of indentation using space in Python, like you usually do, uh, you just end up bloating out all the text, and it's separated across way too much of the sequence, and we are running out of the context length in the sequence, uh, roughly speaking, what's what's happening. We're being way too wasteful. We're taking up way too much token space.

Improving Tokenization: GPT-2 vs. GPT-4

[12:29] Andrej Karpathy: Now, if we also scroll up here, we can change the tokenizer. So note here that GPT-2 tokenizer creates a token count of 300 for this string here. We can change it to cl100k_base, which is the GPT-4 tokenizer. And we see that the token count drops to 185. So for the exact same string, we are now roughly halving the number of tokens. And roughly speaking, this is because, uh, the number of tokens in the GPT-4 tokenizer is roughly double that of the number of tokens in the GPT-2 tokenizer. So we went from roughly 50k to roughly 100k.

[13:01] Andrej Karpathy: Now, you can imagine that this is a good thing because the same text is now squished into half as many tokens. So, uh, this is a lot denser input to the transformer. And in the transformer, every single token has a finite number of tokens before it that it's going to pay attention to. And so what this is doing is we're roughly able to see twice as much text as a context for what token to predict next, uh, because of this change. But of course, just increasing the number of tokens is, uh, not strictly better infinitely, uh, because as you increase the number of tokens, now your embedding table is, uh, sort of getting a lot larger. And also at the output, we are trying to predict the next token, and there's the softmax there, and that grows as well. We're going to go into more detail later on this, but there's some kind of a sweet spot somewhere where you have a just right number of tokens in your vocabulary where everything is appropriately dense and still fairly efficient.

[13:57] Andrej Karpathy: Now, one thing I would like you to note specifically for the GPT-4 tokenizer is that the handling of the whitespace for Python has improved a lot. You see that here, these four spaces are represented as one single token for the three spaces here, and then the token " if." And here, seven spaces were all grouped into a single token. So we're being a lot more efficient in how we represent Python. And this was a deliberate choice made by OpenAI when they designed the GPT-4 tokenizer. And they group a lot more whitespace into a single character. What this does is it densifies Python, and therefore, we can attend to more code before it when we're trying to predict the next token in the sequence. And so the improvement in the Python coding ability from GPT-2 to GPT-4 is not just a matter of the language model and the architecture and the details of the optimization, but a lot of the improvement here is also coming from the design of the tokenizer and how it groups characters into tokens.

The Tiktokenizer web app showing a Python FizzBuzz code snippet. The tokenizer is set to 'cl100k_base' (GPT-4). The indentation spaces are grouped into single, larger tokens, unlike the GPT-2 tokenizer.

From Strings to Integers: Unicode and Encodings

[14:56] Andrej Karpathy: Okay, so let's now start writing some code. So, remember what we want to do. We want to take strings and feed them into language models. For that, we need to somehow tokenize strings into some integers in some fixed vocabulary. And then we will use those integers to make a lookup into a lookup table of vectors and feed those vectors into the transformer as an input.

[15:20] Andrej Karpathy: Now, the reason this gets a little bit tricky, of course, is that we don't just want to support the simple English alphabet. We want to support different kinds of languages. So this is "annyeonghaseyo" in Korean, which is hello. And we also want to support many kinds of special characters that we might find on the internet, for example, emoji. So, how do we feed this text into, uh, transformers?

A Jupyter Notebook cell showing a Korean phrase '안녕하세요' (hello in Korean!) and an emoji '🤗'.

[15:43] Andrej Karpathy: Well, what is this text anyway in Python? So if you go to the documentation of a string in Python, you can see that strings are immutable sequences of Unicode code points. Okay, what are Unicode code points? We can go to Wikipedia. So Unicode code points are defined by the Unicode Consortium as part of the Unicode standard. And what this is really is that it's just a definition of roughly 150,000 characters right now. And roughly speaking, what they look like and what integers, um, represent those characters. So this is 150,000 characters across 161 scripts as of right now. So if you scroll down here, you can see that the standard is very much alive. The latest standard 15.1 is September 2023.

A screenshot of the Wikipedia page for 'Unicode'. It describes Unicode as a text encoding standard defining 149,813 characters and 161 scripts.

[16:31] Andrej Karpathy: And basically, this is just a way to define lots of types of characters, like for example, all these characters across different scripts. So, the way we can access the Unicode code point given a single character is by using the ord function in Python. So for example, I can pass in ord of 'h', and I can see that for the single character 'h', the Unicode code point is 104. Okay? Um, but this can be arbitrarily complicated. So we can take, for example, our emoji here, and we can see that the code point for this one is 128,000. Or we can take "an," and this is 50,000. Now, keep in mind, you can't plug in strings here because, uh, this doesn't have a single code point. It only takes a single Unicode code point character and tells you its integer.

A Jupyter Notebook showing the use of Python's ord() function to get the Unicode code point for the character 'h' (104), an emoji '🤗' (128075), and a Korean character '안' (50504).

[17:24] Andrej Karpathy: So in this way, we can look up all the, um, characters of this specific string and their code points. So ord(x) for x in this string, and we get this encoding here. Now, see here, we've already turned, the raw code points already have integers. So why can't we simply just use these integers and not have any tokenization at all? Why can't we just use this natively as is and just use the code point?

A Jupyter Notebook cell showing a list comprehension that applies the ord() function to each character in a string containing Korean text and an emoji, outputting a list of their integer Unicode code points.

[17:52] Andrej Karpathy: Well, one reason for that, of course, is that the vocabulary in that case would be quite long. So in this case, for Unicode, this is a vocabulary of 150,000 different code points. But more worryingly than that, I think, the Unicode standard is very much alive and it keeps changing. And so it's not kind of a stable representation necessarily that we may want to use directly. So for these reasons, we need something a bit better.

[18:16] Andrej Karpathy: So to find something better, we turn to encodings. So if you go to the Wikipedia page here, we see that the Unicode Consortium defines three types of encodings: UTF-8, UTF-16, and UTF-32. These encodings are the way by which we can take Unicode text and translate it into binary data or byte strings. UTF-8 is by far the most common. So this is the UTF-8 page. Now, this Wikipedia page is actually quite long, but what's important for our purposes is that UTF-8 takes every single code point and it translates it to a byte string. And this byte string is between one to four bytes. So it's a variable-length encoding. So depending on the Unicode point, according to the schema, you're going to end up with between one to four bytes for each code point.

A screenshot of the Wikipedia page for UTF-8, showing a table that maps Unicode code point ranges to their corresponding byte-length representation in UTF-8 (1, 2, 3, or 4 bytes).

[19:02] Andrej Karpathy: On top of that, there's UTF-8, uh, UTF-16, and UTF-32. UTF-32 is nice because it is fixed length instead of variable length, but it has many other downsides as well. So the full kind of spectrum of pros and cons of all these different three encodings are beyond the scope of this video. I'd just like to point out that I enjoyed this blog post, and this blog post at the end of it also has a number of references that can be quite useful. Uh, one of them is "UTF-8 Everywhere Manifesto." Um, and this manifesto describes the reason why UTF-8 is significantly preferred and a lot nicer than the other encodings and why it is used a lot more prominently, um, on the internet. One of the major advantages that's just to give you a sense is that UTF-8 is the only one of these that is backward compatible to the much simpler ASCII encoding of text. Um, but I'm not going to go into the full detail in this video. So suffice to say,

Introduction to UTF-8 Encoding

[20:00] Speaker A: Suffice it to say that we like the UTF-8 encoding. And, uh, let's try to take this string and see what we get if we encode it into UTF-8.

Jupyter Notebook cell showing a Python list comprehension to get the Unicode code points for a string containing Korean and English text.

[20:08] Speaker A: The string class in Python actually has .encode, and you can give it the encoding, which is, let's say, UTF-8. Now, what we get out of this is not very nice because this is the bytes, this is a bytes object, and it's not very nice in the way that it's printed. So I personally like to take it through a list because then we actually get the raw bytes of this, uh, encoding.

[20:31] Speaker A: So this is the raw bytes that represent this string according to the UTF-8 encoding.

Comparing UTF-8, UTF-16, and UTF-32

[20:37] Speaker A: We can also look at UTF-16. We get a slightly different byte stream. And here we start to see one of the disadvantages of UTF-16. You see how we have zero, zero something, zero something, zero something. We're starting to get a sense that this is a bit of a wasteful encoding. And indeed, for simple ASCII characters or English characters here, uh, we just have this structure of zero something, zero something, and it's not exactly nice.

Jupyter Notebook cell showing the UTF-16 encoding of the string, resulting in a long list of integers with many zeros, indicating inefficiency.

[21:02] Speaker A: Same for UTF-32. When we expand this, we can start to get a sense of the wastefulness of this encoding for our purposes. You see a lot of zeros followed by something. And so, uh, this is not desirable.

Jupyter Notebook cell showing the UTF-32 encoding of the string, which produces an even longer list of integers with a large number of zeros.

The Problem with Raw Byte Tokenization

[21:16] Speaker A: So, suffice it to say that we would like to stick with UTF-8 for our purposes. However, if we just use UTF-8 naively, these are byte streams. So that would imply a vocabulary length of only 256 possible tokens. Uh, but this, this vocabulary size is very, very small. What this is going to do if we just were to use it naively is that all of our text would be stretched out over very, very long sequences of bytes.

[21:44] Speaker A: And so, um, what what this does is that certainly the embedding table is going to be tiny, and the prediction at the top at the final layer is going to be very tiny, but our sequences are very long. And remember that we have pretty finite, um, context length in the attention that we can support in a transformer for computational reasons. And so we only have that much context length, but now we have very, very long sequences, and this is just inefficient, and it's not going to allow us to attend to sufficiently long text, uh, before us for the purposes of the next token prediction task.

[22:18] Speaker A: So we don't want to use the raw bytes of the UTF-8 encoding. We want to be able to support larger vocabulary size that we can tune as a hyperparameter, but we want to stick with the UTF-8 encoding of these strings. So what do we do?

Introducing Byte Pair Encoding (BPE)

[22:34] Speaker A: Well, the answer, of course, is we turn to the Byte Pair Encoding algorithm, which will allow us to compress these byte sequences, um, to a variable amount. So we'll get to that in a bit, but I just want to briefly speak to the fact that I would love nothing more than to be able to feed raw byte sequences into, uh, language models. In fact, there's a paper about how this could potentially be done, uh, from the summer last year.

A screenshot of the research paper titled 'MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers'.

[22:58] Speaker A: Now, the problem is you have to go in and you have to modify the transformer architecture because, as I mentioned, you're going to have a problem where the attention will start to become extremely expensive because the sequences are so long. And so in this paper, they propose kind of a hierarchical structuring of the transformer that could allow you to just feed in raw bytes. And so at the end, they say, "Together, these results establish the viability of tokenization-free autoregressive sequence modeling at scale." So tokenization-free would indeed be amazing. We would just feed byte streams directly into our models. But unfortunately, I don't know that this has really been proven out yet by sufficiently many groups at sufficient scale. Uh, but something like this at one point would be amazing, and I hope someone comes up with it. But for now, we have to come back, and we can't feed this directly into language models, and we have to compress it using the Byte Pair Encoding algorithm. So let's see how that works.

How Byte Pair Encoding Works

[23:50] Speaker A: So as I mentioned, the Byte Pair Encoding algorithm is not all that complicated, and the Wikipedia page is actually quite instructive as far as the basic idea goes. What we're doing is we have some kind of an input sequence. Uh, like, for example, here we have only four elements in our vocabulary: a, b, c, and d. And we have a sequence of them. So instead of bytes, let's say we just have four, a vocab size of four.

[24:12] Speaker A: This sequence is too long, and we'd like to compress it. So what we do is that we iteratively find the pair of, uh, tokens that occur the most frequently. And then once we've identified that pair, we replace that pair with just a single new token that we append to our vocabulary. So for example, here, the byte pair 'aa' occurs most often. So we mint a new token, let's call it capital Z, and we replace every single occurrence of 'aa' by Z. So now we have two Z's here.

The Wikipedia page shows the first step of BPE: the string 'aaabdaaabac' is transformed into 'ZabdZabac' by replacing 'aa' with 'Z'.

[24:47] Speaker A: So here, we took a sequence of 11 characters with vocabulary size four, and we've converted this to a, um, sequence of only nine tokens, but now with a vocabulary of five, because we have a fifth vocabulary element that we just created, and it's Z, standing for concatenation of 'aa'. And we can again repeat this process. So we again look at the sequence and identify the, uh, pair of tokens that are most frequent. Let's say that that is now 'ab'. Well, we are going to replace 'ab' with a new token that we mint, called Y. So Y becomes 'ab', and then every single occurrence of 'ab' is now replaced with Y. So we end up with this.

The Wikipedia page shows the second step of BPE: the string 'ZabdZabac' is transformed into 'ZYdZYac' by replacing 'ab' with 'Y'.

[25:30] Speaker A: So now we only have 1, 2, 3, 4, 5, 6, 7 characters in our sequence, but we have not just, um, four vocabulary elements, or five, but now we have six. And for the final round, we again look through the sequence, find that the phrase 'ZY' or the pair 'ZY' is most common, and replace it one more time with another, um, character, let's say X. So X is 'ZY', and we replace all occurrences of 'ZY', and we get this following sequence.

The Wikipedia page shows the final step of BPE: the string 'ZYdZYac' is transformed into 'XdXac' by replacing 'ZY' with 'X'.

[26:02] Speaker A: So basically, after we've gone through this process, instead of having a, um, sequence of 11, uh, tokens with a vocabulary length of four, we now have a sequence of 1, 2, 3, 4, 5 tokens, but our vocabulary length now is seven. And so in this way, we can iteratively compress our sequence as we mint new tokens. So in the exact same way, we start, we start off with byte sequences, so we have 256 vocabulary size, but we're now going to go through these and find the byte pairs that occur the most, and we're going to iteratively start minting new tokens, appending them to our vocabulary, and replacing things. And in this way, we're going to end up with a compressed training dataset and also an algorithm for taking any arbitrary sequence and encoding it using this, uh, vocabulary, and also decoding it back to strings. So let's now implement all that.

Implementing BPE in Python

[27:03] Speaker A: So here's what I did. I went to this blog post that I enjoyed, and I took the first paragraph, and I copy-pasted it here into text. So this is one very long line here.

A screenshot of a blog post titled 'A Programmer's Introduction to Quadrilateral Interpolation', from which text will be copied for the tokenizer training.

[27:14] Speaker A: Now, to get the tokens, as I mentioned, we just take our text and we encode it into UTF-8. The tokens here at this point will be our raw bytes, single stream of bytes. And just so that it's easier to work with, instead of just a bytes object, I'm going to convert all those bytes to integers and then create a list of it, just so it's easier for us to manipulate and work with in Python and visualize. And here I'm printing all of that. So this is the original, um, this is the original paragraph, and its length is 533, uh, code points. And then here are the bytes encoded in UTF-8, and we see that this has a length of 616 bytes at this point, or 616 tokens. And the reason this is more is because a lot of these simple ASCII characters or simple characters, they just become a single byte, but a lot of these Unicode, more complex characters become multiple bytes, up to four, and so we are expanding that size.

[28:13] Speaker A: So now what we'd like to do as a first step of the algorithm is we'd like to iterate over here and find the pair of bytes that occur most frequently, because we're then going to merge it. So if you are working along on the notebook on the side, then I encourage you to basically click on the link, find this notebook, and try to write that function yourself. Otherwise, I'm going to come here and implement first the function that finds the most common pair.

[28:36] Speaker A: Okay, so here's what I came up with. There are many different ways to implement this, but I'm calling the function get_stats. It expects a list of integers. I'm using a dictionary to keep track of basically the counts. And then this is a Pythonic way to iterate consecutive elements of this list, uh, which we covered in the previous video. And then here, I'm just keeping track of, just incrementing by one, um, for all the pairs. So if I call this on all the tokens here, then the stats comes out here. So this is a dictionary. The keys are these tuples of consecutive elements, and this is the count.

[29:11] Speaker A: So just to, uh, print it in a slightly better way, this is one way that I like to do that, where you, it's a little bit compound here, so you can pause if you like. But we iterate over all the items. The .items() called on dictionary returns pairs of key-value. And instead, I create a list here of value-key, because if it's a value-key list, then I can call sort() on it. And by default, Python will, uh, use the first element, which in this case will be value, to sort by if it's given tuples. And then reverse, so it's descending, and print that.

[29:50] Speaker A: So basically, it looks like 101, 32 was the most commonly occurring consecutive pair, and it occurred 20 times. We can double check that that makes reasonable sense. So if I just search 101, 32, then you see that these are the 20 occurrences of that, um, pair.

The list of byte tokens in the Jupyter Notebook, with all 20 occurrences of the pair '101, 32' highlighted by the find function.

[30:09] Speaker A: And if we'd like to take a look at what exactly that pair is, we can use chr, which is the opposite of ord in Python. So we give it a, um, Unicode code point, so 101 and of 32, and we see that this is 'e' and 'space'. So basically, there's a lot of 'e space' here, meaning that a lot of these words seem to end with 'e'. So here's 'e space' as an example. So there's a lot of that going on here, and this is the most common pair.

Jupyter Notebook cell showing the use of Python's chr() function to convert the integers 101 and 32 back to their character representations, which are 'e' and a space.

[30:36] Speaker A: So now that we've identified the most common pair, we would like to iterate over the sequence. We're going to mint a new token with the ID of 256, right? Because these tokens currently go from 0 to 255. So when we create a new token, it will have an ID of 256. And we're going to iterate over this entire, um, list, and every, every time we see 101, 32, we're going to swap that out for 256. So let's implement that now, and feel free to, uh, do that yourself as well.

[31:10] Speaker A: So first, I commented, uh, this just so we don't pollute, uh, the notebook too much. This is a nice way of in Python obtaining the highest ranking pair. So we're basically calling the max on this dictionary stats, and this will return the maximum key. And then the question is, how does it rank keys? So you can provide it with a function that ranks keys, and that function is just stats.get. Uh, stats.get would basically return the value. And so we're ranking by the value and getting the maximum key. So it's 101, 32, as we saw.

Jupyter Notebook cell showing a Python one-liner to find the most frequent pair using max(stats, key=stats.get), with the output (101, 32) below.

[31:47] Speaker A: Now, to actually merge 101, 32, um, this is the function that I wrote, but again, there are many different versions of it. So we're going to take a list of IDs and the pair that we want to replace, and that pair will be replaced with the new index idx. So, iterating through IDs, if we find a pair, swap it out for idx. So we create this new list, and then we start at zero, and then we go through this entire list sequentially from left to right. And here we are checking for equality at the current position with the pair. Um, so here we are checking that the pair matches. Now, here's a bit of a tricky condition that you have to append if you're trying to be careful, and that is that, um, you don't want this here to be out of bounds at the very last position when you're on the rightmost element of this list. Otherwise, this would, uh, give you an out-of-bounds error. So we have to make sure that we're not at the very, very last element. So, uh, this would be false for that. So if we find a match, we append to this new list that replacement index, and we increment the position by two, so we skip over that entire pair. But otherwise, if we haven't found a matching pair, we just sort of copy over the, um, element at that position and increment by one and return this.

Jupyter Notebook cell showing the implementation of the merge function, which replaces all occurrences of a given pair in a list of IDs with a new index.

[33:06] Speaker A: So here's a very small toy example. If we have a list 5, 6, 6, 7, 9, 1, and we want to replace the occurrences of 6, 7 with 99, then calling this on that will give us what we were asking for. So here, the 6, 7 is replaced with 99.

[33:22] Speaker A: So now I'm going to uncomment this for our actual use case, where we want to take our tokens, we want to take the top pair here, and replace it with 256 to get tokens2. If we run this, we get the following. So, recall that previously, we had a length 616 in this list. And now we have a length 596, right? So this decreased by 20, which makes sense because there are 20 occurrences.

[33:52] Speaker A: Moreover, we can try to find 256 here, and we see plenty of occurrences of it. And moreover, just to double check, there should be no occurrence of 101, 32. So this is the original array, plenty of them, and in the second array, there are no occurrences of 101, 32. So we've successfully merged this single pair.

The Jupyter Notebook shows a search for the new token '256' in the merged list, highlighting its many occurrences.

[34:11] Speaker A: And now we just, uh, iterate this. So we are going to go over the sequence again, find the most common pair, and replace it. So let me now write a while loop that uses these functions to do this, um, sort of iteratively. And how many times do we do it for? Well, that's totally up to us as a hyperparameter. The more, um, steps we take, the larger will be our vocabulary and the shorter will be our sequence. And there is some sweet spot that we usually find works the best in practice. And so this is kind of a hyperparameter, and we tune it, and we find good vocabulary sizes. As an example, GPT-4 currently uses roughly 100,000 tokens, and, uh, ballpark, those are reasonable numbers currently in state-of-the-art large language models. So let me now write, uh, putting, putting it all together and, uh, iterating these steps.

Training the Tokenizer

[34:58] Speaker A: Okay, now before we dive into the while loop, I wanted to add one more cell here where I went to the blog post, and instead of grabbing just the first paragraph or two, I took the entire blog post, and I stretched it out in a single line. And basically, just using longer text will allow us to have more representative statistics for the byte pairs, and we'll just get a more sensible result out of it, uh, because it's longer text. So here we have the raw text, we encode it into bytes using the UTF-8 encoding. And then here, as before, we are just changing it into a list of integers in Python just so it's easier to work with instead of the raw bytes object.

Jupyter Notebook cell showing the setup for training the tokenizer, including loading a larger text file and converting it to a list of UTF-8 byte integers.

[35:36] Speaker A: And then this is the code that I came up with, uh, to actually do the merging in loop. These two functions here are identical to what we had above. I only included them here just so that you have the point of reference here. So, uh, these two are identical, and then this is the new code that I added. So the first thing we want to do is we want to decide on a final vocabulary size that we want our tokenizer to have. And as I mentioned, this is a hyperparameter, and you set it in some way depending on your best performance. So let's say for us, we're going to use 276 because that way we're going to be doing exactly 20 merges. And, uh, 20 merges because we already have 256, uh, tokens for the raw bytes. And to reach 276, we have to do 20 merges, uh, to add 20 new tokens.

Jupyter Notebook cell containing the full BPE training loop. It defines get_stats and merge functions, sets a vocabulary size, and then iterates to merge the most frequent pairs.

[36:26] Speaker A: Here, uh, this is, uh, one way in Python to just create a copy of the list. So I'm taking the tokens list, and by wrapping it in a list, Python will construct a new list of all the individual elements. So this is just a copy operation. Then here, I'm creating a merges uh, dictionary. So this merges dictionary is going to maintain basically the child one, child two mapping to a new, uh, token. And so what we're going to be building up here is a binary tree of merges. But actually, it's not exactly a tree because a tree would have a single root node with a bunch of leaves. For us, we're starting with the leaves on the bottom, which are the individual bytes, those are the starting 256 tokens. And then we're starting to like merge two of them at a time. And so it's not a tree, it's more like a forest, um, as we merge these elements.

[37:18] Speaker A: So for 20 merges, we're going to find the most commonly occurring pair. We're going to mint a new token integer for it. So i here will start at zero, so we'll start with 256. We're going to print that we're merging it, and we're going to replace all the occurrences of that pair with the new, newly minted token. And we're going to record that this pair of integers merged into this new integer. So running this gives us the following output.

The output of the BPE training loop, showing a list of 20 merge operations. Each line indicates which pair of tokens was merged into a new token ID.

[37:51] Speaker A: So we did 20 merges. And for example, the first merge was exactly as before, the 101, 32, uh, tokens merging into a new token 256. Now, keep in mind that the individual, uh, tokens 101 and 32 can still occur in the sequence after merging. It's only when they occur exactly consecutively that that becomes 256 now. Um, and in particular, the other thing to notice here is that the token 256, which is the newly minted token, is also eligible for merging. So here on the bottom, the 20th merge was a merge of 256 and 259 becoming 275. So every time we replace these tokens, they become eligible for merging in the next round of the iteration. So that's why we're building up a small sort of binary forest instead of a single individual tree.

[38:41] Speaker A: One thing we can take a look at as well is we can take a look at the compression ratio that we've achieved. So in particular, we started off with this tokens list. Um, so we started off with 24,000 bytes, and after merging 20 times, uh, we now have only 19,000, um, tokens. And so therefore, the compression ratio is simply just dividing the two is roughly 1.27. So that's the amount of compression we were able to achieve of this text with only 20 merges. Um, and of course, the more vocabulary elements you add, uh, the greater the compression ratio here would be.

Jupyter Notebook cell calculating and printing the compression ratio. The original token length was 24597, the new length is 19438, resulting in a compression ratio of 1.27x.

The Tokenizer as a Separate Module

[39:19] Speaker A: Finally, so that's kind of like, um, the training of the tokenizer, if you will. Now, one point that I wanted to make is that, and maybe this is a diagram that can help, um, kind of illustrate, is that the tokenizer is a completely separate object from the large language model itself. So everything in this lecture, we're not really touching the LLM itself. Uh, we're just training the tokenizer. That is a completely separate preprocessing stage usually. So the tokenizer will have its own training set, just like a large language model has a potentially different training set. So the tokenizer has a training set of documents on which you're going to train the tokenizer. And then, um, we're performing the Byte Pair Encoding algorithm as we saw above.

A diagram illustrating the data pipeline: 'Raw text (Unicode code point sequence)' goes into a 'Tokenizer', which outputs a 'token sequence' that is then fed into the 'LLM'.

The Tokenizer as a Translation Layer

[40:00] Speaker A: allows to train the vocabulary of this tokenizer. So it has its own training set, it has a pre-processing stage that you would run a single time in the beginning. Um, and the tokenizer is trained using byte-pair encoding algorithm. Once you have the tokenizer, once it's trained and you have the vocabulary and you have the merges, uh, we can do both encoding and decoding. So these two arrows here. So the tokenizer is a translation layer between raw text, which is, as we saw, the sequence of Unicode code points. It can take raw text and turn it into a token sequence. And vice versa, it can take a token sequence and translate it back into raw text.

[40:41] Speaker A: So now that we have trained the uh, tokenizer and we have these merges, we are going to turn to how we can do the encoding and the decoding step. If you give me text, here are the tokens, and vice versa, if you give me tokens, here's the text. Once we have that, we can translate between these two realms. And then the language model is going to be trained as a step two afterwards. And typically in a, in a sort of a state-of-the-art application, you might take all of your training data for the language model and you might run it through the tokenizer and sort of translate everything into a massive token sequence. And then you can throw away the raw text. You're just left with the tokens themselves. And those are stored on disk and that is what the large language model is actually reading when it's training on them. So that's one approach that you can take as a single massive pre-processing stage.

[41:27] Speaker A: Um, so, yeah, basically, I think the most important thing I want to get across is that this is a completely separate stage. It usually has its own entire uh, training set. You may want to have those training sets be different between the tokenizer and the large language model. So for example, when you're training the tokenizer, as I mentioned, we don't just care about the performance of English text, we care about uh, multi many different languages. And we also care about code or not code. So you may want to look into different kinds of mixtures of different kinds of languages and different amounts of code and things like that, uh, because the amount of different language that you have in your tokenizer training set will determine how many merges of it there will be. And therefore that determines the density with which uh, this type of data is um, sort of has in the token space.

[42:17] Speaker A: And so, roughly speaking, intuitively, if you add some amount of data, let's say you have a ton of Japanese data in your uh, tokenizer training set, then that means that more Japanese tokens will get merged and therefore Japanese will have shorter sequences. Uh, and that's going to be beneficial for the large language model, which has a finite context length on which it can work on in in the token space. Uh, so hopefully that makes sense. So we're now going to turn to encoding and decoding now that we have trained a tokenizer. So we have our merges and now how do we do encoding and decoding?

Decoding

[42:48] Speaker A: Okay, so let's begin with decoding, which is this arrow over here. So given a token sequence, let's go through the tokenizer to get back a Python string object. So the raw text.

[42:58] Speaker A: So this is the function that we'd like to implement. Um, we're given the list of integers and we want to return a Python string. If you'd like, uh, try to implement this function yourself. It's a fun exercise. Otherwise, I'm going to start uh, pasting in my own solution.

A Python function stub for 'decode' that takes a list of integers named 'ids' and is expected to return a Python string.

[43:12] Speaker A: So there are many different ways to do it. Um, here's one way. I will create an uh, kind of pre-processing variable that I will call vocab. And vocab is a mapping or a dictionary in Python from the token uh, ID to the bytes object for that token. So we begin with the raw bytes for tokens from 0 to 255. And then we go in order of all the merges and we sort of uh, populate this vocab list by doing an addition here. So this is the basically the bytes representation of the first child followed by the second one. And remember these are bytes objects, so this addition here is an addition of two bytes objects, just concatenation. So that's what we get here.

[43:59] Speaker A: One tricky thing to be careful with by the way is that I'm iterating a dictionary in Python using a .items() and uh, it really matters that this runs in the order in which we inserted items into the merges dictionary. Luckily, starting with Python 3.7, this is guaranteed to be the case, but before Python 3.7, this iteration may have been out of order with respect to how we inserted elements into merges and this may not have worked. But we are using a modern Python, so we're okay.

[44:28] Speaker A: And then here, uh, given the IDs, the first thing we're going to do is get the tokens. So the way I implemented this here is I'm taking, I'm iterating over all the IDs, I'm using vocab to look up their bytes, and then here, this is one way in Python to concatenate all these bytes together to create our tokens. And then these tokens here at this point are raw bytes. So I have to decode using UTF-8 now back into Python strings. So previously we called .encode() on a string object to get the bytes, and now we're doing its opposite. We're taking the bytes and calling a decode on the bytes object to get a string in Python. And then we can return text.

The complete Python implementation of the 'decode' function, which builds a vocabulary from merges and then uses it to convert a list of token IDs back into a UTF-8 string.

[45:16] Speaker A: So, um, this is how we can do it. Now, this actually has a uh, issue, um, in the way I implemented it, and this could actually throw an error. So try to think figure out why this code could actually result in an error if we plug in um, some sequence of IDs that is unlucky. So let me demonstrate the issue. When I try to decode just something like 97, I am going to get the letter a here back. So nothing too crazy happening. But when I try to decode 128 as a single element, the token 128 is what in string or in Python object? UnicodeDecodeError. UTF-8 can't decode byte um, 0x80, which is this in hex, at position zero, invalid start byte. What does that mean?

Jupyter notebook output showing a 'UnicodeDecodeError' with the message 'utf-8' codec can't decode byte 0x80 in position 0: invalid start byte'.

[46:03] Speaker A: Well, to understand what this means, we have to go back to our UTF-8 page uh, that I briefly showed earlier, and this is Wikipedia UTF-8. And basically there's a specific schema that UTF-8 bytes take. So in particular, if you have a multi-byte object for some of the Unicode characters, they have to have this special sort of envelope in how the encoding works. And so what's happening here is that invalid start byte, that's because 128, the binary representation of it is one followed by all zeros. So we have one and then all zero. And we see here that that doesn't conform to the format because one followed by all zero just doesn't fit any of these rules, so to speak. So it's an invalid start byte, which is byte one. This one must have a one following it, and then a zero following it, and then the content of your Unicode in Xs here.

[46:57] Speaker A: So basically we don't um, exactly follow the UTF-8 standard and this cannot be decoded. And so the way to fix this, um, is to use this errors equals in bytes.decode function of Python. And by default, errors is strict. So we will throw an error if um, it's not valid UTF-8 byte encoding. But there are many different things that you can put here on error handling. This is the full list of all the errors that you can use. And in particular, instead of strict, let's change it to replace. And that will replace with this special marker, this replacement character. So errors equals replace. And now we just get that character back.

Python documentation for the bytes.decode method, with the 'errors' parameter and its default value 'strict' highlighted.

The Python 'decode' function is modified to include the 'errors="replace"' argument in the .decode() call.

[47:43] Speaker A: So basically not every single byte sequence is valid UTF-8. And if it happens that your large language model, for example, predicts your tokens in a bad manner, then they might not fall into valid UTF-8 and then we won't be able to decode them. So the standard practice is to basically uh, use errors equals replace. And this is what you will also find in the OpenAI um, code that they released as well. But basically whenever you see a this kind of a character in your output in that case, uh, something went wrong and the LLM output was not valid uh, sort of sequence of tokens.

Encoding

[48:22] Speaker A: Okay, and now we're going to go the other way. So we are going to implement this arrow right here, where we are going to be given a string and we want to encode it into tokens.

A new section in the Jupyter notebook titled 'encoding', with a function stub for 'encode(text)' that is expected to return a list of integers.

[48:32] Speaker A: So this is the signature of the function that we're interested in. And uh, this should basically print a list of integers of the tokens. So again, uh, try to maybe implement this yourself if you'd like a fun exercise. Uh, and pause here, otherwise I'm going to start putting in my solution. So again, there are many ways to do this. So, um, this is one of the ways that sort of I came up with. So the first thing we're going to do is we are going to take our text, encode it into UTF-8 to get the raw bytes. And then as before, we're going to call list on the bytes object to get a list of integers of those bytes. So those are the starting tokens, those are the raw bytes of our sequence.

[49:15] Speaker A: But now, of course, according to the merges dictionary above, and recall this was the merges, some of the bytes may be merged according to this lookup. And in addition to that, remember that the merges was built from top to bottom, and this is sort of the order in which we inserted stuff into merges. And so we prefer to do all these merges in the beginning before we do these merges later because um, for example, this merge over here relies on the 256 which got merged here. So we have to go in the order from top to bottom sort of if we are going to be merging anything.

[49:49] Speaker A: Now, we expect to be doing a few merges, so we're going to be doing while true. Um, and now we want to find a pair of bytes that is consecutive that we are allowed to merge according to this. In order to reuse some of the functionality that we've already written, I'm going to reuse the function uh, get stats.

[50:10] Speaker A: So recall that get stats uh, will give us the, will basically count up how many times every single pair occurs in our sequence of tokens and return that as a dictionary. And the dictionary was a mapping from all the different uh, byte pairs to the number of times that they occur, right? Uh, at this point, we don't actually care how many times they occur in the sequence. We only care what the raw pairs are in that sequence. And so I'm only going to be using basically the keys of this dictionary. I only care about the set of possible merge candidates, if that makes sense.

[50:44] Speaker A: Now we want to identify the pair that we're going to be merging at this stage of the loop. So what do we want? We want to find the pair or like the a key inside stats that has the lowest index in the merges uh, dictionary because we want to do all the early merges before we work our way to the late merges. So again, there are many different ways to implement this, but I'm going to do something a little bit fancy here.

[51:11] Speaker A: So I'm going to be using the min over an iterator. In Python, when you call min on an iterator and stats here is a dictionary, we're going to be iterating the keys of this dictionary in Python. So we're looking at all the pairs inside stats, um, which are all the consecutive pairs. And we're going to be taking the consecutive pair inside tokens that has the minimum what? The min takes a key which gives us the function that is going to return a value over which we're going to do the min. And the one we care about is we're we care about taking merges and basically getting um, that pair's index.

[51:53] Speaker A: So basically for any pair inside stats, we are going to be looking into merges at what index it has. And we want to get the pair with the min number. So for an example, if there's a pair 101 and 32, we definitely want to get that pair. We want to identify it here and return it, and pair would become 101, 32 if it occurs. And the reason that I'm putting a float inf here as a fallback is that in the get function, when we call uh, when we basically consider a pair that doesn't occur in the merges, then that pair is not eligible to be merged, right? So if in the token sequence there's some pair that is not a merging pair, it cannot be merged, then uh, it doesn't actually occur here and it doesn't have an index and uh, it can't be merged, which we will denote as float inf. And the reason infinity is nice here is because for sure we're guaranteed that it's not going to participate in the list of candidates when we do the min. So, uh, so this is one way to do it.

[52:55] Speaker A: So basically, in one short, this returns the most eligible merging candidate pair uh, that occurs in the tokens. Now, one thing to be careful with here is this uh, function here might fail in the following way. If there's nothing to merge, then uh, then there's nothing in merges um, that is satisfied anymore. There's nothing to merge. Everything just returns float inf and then uh, the pair, I think will just become the very first element of stats. Um, but this pair is not actually a mergeable pair. It just becomes the first pair in stats arbitrarily because all these pairs evaluate to float inf for the merging criterion. So basically it could be that this this doesn't look succeed because there's no more merging pairs. So if this pair is not in merges that was returned, then this is a signal for us that actually there was nothing to merge. No single pair can be merged anymore. In that case, we will break out. Um, nothing else can be merged.

[53:58] Speaker A: You may come up with a different implementation by the way. This is kind of like really uh, trying hard in Python. Um, but really we're just trying to find a pair that can be merged with a lowest index here. Now, if we did find a pair that is inside merges with the lowest index, then we can merge it. So we're going to look into the merges dictionary for that pair to look up the index, and we're going to now merge that into that index. So we're going to do tokens equals, we're going to replace the original tokens, we're going to be replacing the pair pair, and we're going to be replacing it with index idx. And this returns a new list of tokens where every occurrence of pair is replaced with idx. So we're doing a merge.

The complete Python implementation of the 'encode' function, showing the iterative merging process within a 'while' loop and the final return statement.

[54:46] Speaker A: And we're going to be continuing this until eventually nothing can be merged. We'll come out here and we'll break out. And here we just return tokens. And so that's the implementation I think. So hopefully this runs. Okay, cool. Um, yeah, and this looks uh, reasonable. So for example, 32 is a space in ASCII, so that's here. Um, so this looks like it worked. Great.

The output of the 'encode' function for the string 'hello world!', which is a list of integers: [104, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 33].

[55:11] Speaker A: Okay, so let's wrap up this section of the video at least. I wanted to point out that this is not quite the right implementation just yet because we are leaving out a special case. So in particular, if uh, we try to do this, this will give us an error. And the issue is that um, if we only have a single character or an empty string, then stats is empty and that causes an issue inside min. So one way to fight this is if length of tokens is at least two. Because if it's less than two, it's just a single token or no tokens, then let's just uh, there's nothing to merge, so we just return. So that would fix uh, that case.

A 'ValueError: min() arg is an empty sequence' traceback in the Jupyter notebook, which occurred when trying to encode the single character 'h'.

The corrected 'encode' function now includes a check 'if len(tokens) < 2:' to handle short inputs, and the output for encoding 'h' is correctly shown as [104].

[55:45] Speaker A: Okay. And then second, I have a few test cases here for us as well. So first, let's make sure uh, about or let's note the following. If we take a string and we try to encode it and then decode it back, you would expect to get the same string back, right? Is that true for all strings?

A Python code cell that tests the tokenizer by encoding 'hello world' and then immediately decoding the result, printing the final string.

[56:05] Speaker A: So I think uh, so here it is the case, and I think in general this is probably the case. Um, but notice that going backwards is not, is not, you're not going to have an identity going backwards because as I mentioned, uh, not all token sequences are valid UTF-8 uh, sort of byte streams. And so therefore you're some of them can't even be decodable. Um, so this only goes in one direction. But for that one direction, we can check uh, here. If we take the training text, which is the text that we trained the tokenizer on, we can make sure that when we encode and decode, we get the same thing back, which is true. And here I took some validation data. So I went to, I think this web page and I grabbed some text. So this is text that the tokenizer has not seen, and we can make sure that this also works. Uh, so that gives us some confidence that this was correctly implemented.

Two test cases in a Jupyter notebook. The first confirms the encode/decode round trip on the training text. The second does the same for a new validation text string.

[56:56] Speaker A: So those are the basics of the byte-pair encoding algorithm. We saw how we can take some training set, train a tokenizer. The parameters of this tokenizer really are just this dictionary of merges. And that basically creates a little binary forest on top of raw bytes. Once we have this, the merges table, we can both encode and decode between raw text and token sequences. So that's the the simplest setting of the tokenizer. What we're going to do now though is we're going to look at some of the state-of-the-art large language models and the kinds of tokenizers that they use. And we're going to see that this picture complexifies very quickly. So we're going to go through the details of this complexification one at a time.

Forced Splits Using Regex Patterns (GPT Series)

[57:37] Speaker A: So let's get things off by looking at the GPT series. So in particular, I have the GPT-2 paper here. Um, and this paper is from 2019 or so, uh, so five years ago. And let's scroll down to input representation. This is where they talk about the tokenizer that they're using for GPT-2.

A screenshot of the GPT-2 research paper, with the section title '2.2. Input representation' visible, which discusses the use of Byte Pair Encoding (BPE).

[57:54] Speaker A: Now, this is all fairly readable, so I encourage you to pause and um, read this yourself. But this is where they motivate the use of the byte-pair encoding algorithm on the byte level representation of UTF-8 encoding. So this is where they motivated and they talk about the vocabulary sizes and everything. Now, everything here is exactly as we've covered it so far, but things start to depart around here. So what they mention is that they don't just apply the naive algorithm as we have done it. And in particular, here's a motivating example. Suppose that you have common words like dog. What will happen is that dog, of course, occurs very frequently in the text, and it occurs right next to all kinds of punctuation as an example. So dog dot, dog exclamation mark, dog question mark, etc. And naively, you might imagine that the BPE algorithm could merge these to be single tokens. And then you end up with lots of tokens that are just like dog with a slightly different punctuation. And so it feels like you're clustering things that shouldn't be clustered. You're combining kind of semantics with punctuation.

A highlighted portion of the GPT-2 paper discussing the sub-optimal allocation of vocabulary slots due to BPE merging common words like 'dog' with their many variations.

[58:56] Speaker A: And this uh, feels suboptimal, and indeed they also say that this is suboptimal according to some of the experiments. So what they want to do is they want to top down in a manual way enforce that some types of um, characters should never be merged together. Um, so they want to enforce these merging rules on top of the byte-pair encoding algorithm. So let's take a look um, at their code and see how they actually enforce this and what kinds of merges they actually do perform.

The main page of the OpenAI GPT-2 GitHub repository, showing the list of files and directories, including 'src'.

[59:24] Speaker A: So I have the tab open here for GPT-2 under OpenAI on GitHub. And when we go into source, there is an encoder.py. Now, I don't personally love that they call it encoder.py because this is the tokenizer. And the tokenizer can do both encode and decode. Uh, so it feels kind of awkward to me that it's called encoder, but that is the tokenizer. And there's a lot going on here and we're going to step through it in detail at one point. For now, I just want to focus on this part here. They create a regex pattern here that looks very complicated, and we're going to go through it in a bit. Uh, but this is the core part that

A screenshot of the 'encoder.py' source code from the GPT-2 repository, with a long and complex regular expression pattern highlighted.

[60:00] Andrej Karpathy: allows them to enforce rules uh for what parts of the text will never be merged for sure.

[60:06] Andrej Karpathy: Now notice that re.compile here is a little bit misleading because we're not just doing import re, which is the Python re module. We're doing import regex as re. And regex is a Python package that you can install, pip install regex. And it's basically an extension of re, so it's a bit more powerful re.

A screenshot of the PyPI project page for the 'regex' library, showing the installation command 'pip install regex' and a brief project description.

Forced Splits using Regex Patterns

[60:25] Andrej Karpathy: So let's take a look at this pattern and what it's doing and why this is actually doing the separation that they are looking for.

[60:33] Andrej Karpathy: Okay, so I've copy pasted the pattern here to our Jupyter notebook where we left off. And let's take this pattern for a spin. So in the exact same way that their code does, we're going to call an re.findall for this pattern on any arbitrary string that we are interested in. So this is the string that we want to encode into tokens um to feed into an LLM like GPT-2. So what exactly is this doing?

[60:58] Andrej Karpathy: Well, re.findall will take this pattern and try to match it against this string. Um, the way this works is that you are going from left to right in the string and you're trying to match the pattern. And re.findall will get all the occurrences and organize them into a list. Now, when you look at the um when you look at this pattern, first of all, notice that this is a raw string, um and then these are three double quotes just to start the string. So really the string itself, this is the pattern itself, right?

[61:32] Andrej Karpathy: And notice that it's made up of a lot of ors. So see these vertical bars, those are ors in regex. And so you go from left to right in the pattern and try to match it against the string wherever you are. So we have hello and we're going to try to match it. Well, it's not apostrophe s, it's not apostrophe t, or any of these. But it is an optional space followed by dash p of uh sorry, slash p of L one or more times. What is slash p of L? It is coming to some documentation that I found. Um there might be other sources as well.

A screenshot of a webpage titled 'Regular-Expressions.info' which provides documentation on Unicode categories for regex. The entry for '\p{L}' or '\p{Letter}' is highlighted, explaining it matches any kind of letter from any language.

[62:08] Andrej Karpathy: Uh slash p of L is a letter, any kind of letter from any language. And hello is made up of letters, h e l l o, etc. So optional space followed by a bunch of letters, one or more letters, is going to match hello, but then the match ends because a white space is not a letter. So from there on begins a new sort of attempt to match against the string again. And starting in here, we're going to skip over all these again until we get to the exact same point again. And we see that there's an optional space, this is the optional space, followed by a bunch of letters, one or more of them, and so that matches. So when we run this, we get a list of two elements, hello and then space world.

A screenshot of the Jupyter notebook showing the output of the 're.findall' command. The output is a Python list containing two strings: ['Hello', ' world'].

[62:55] Andrej Karpathy: So, how are you? If we add more letters, we will just get them like this.

A screenshot of the Jupyter notebook showing the 're.findall' command being run on the string 'Hello world how are you?'. The output is a list of strings: ['Hello', ' world', ' how', ' are', ' you?'].

[63:01] Andrej Karpathy: Now, what is this doing and why is this important? We are taking our string and instead of directly encoding it um for tokenization, we are first splitting it up. And when you actually step through the code, and we'll do that in a bit more detail, what really it's doing on a high level is that it first splits your text into a list of texts, just like this one. And all these elements of this list are processed independently by the tokenizer, and all the results of that processing are simply concatenated. So hello, world, oh, I missed how. Hello, world, how are you? We have five elements of a list. All of these will independently go from text to a token sequence, and then that token sequence is going to be concatenated. It's all going to be joined up.

[63:52] Andrej Karpathy: And roughly speaking, what that does is you're only ever finding merges between the elements of this list. So you can only ever consider merges within every one of these elements individually. And um after you've done all the possible merging for all these elements individually, the results of all that will be joined um by concatenation. And so you are basically, what you're doing effectively is you are never going to be merging this e with this space because they are now parts of the separate elements of this list. And so you are saying we are never going to merge e space, um because we're breaking it up in this way. So basically using this regex pattern to chunk up the text is just one way of enforcing that some merges are not to happen. And we're going to go into more of this text and we'll see that what this is trying to do on a high level is we're trying to not merge across letters, across numbers, across punctuation, and so on. So let's see in more detail how that works. So let's continue now. We have slash p of n. If you go to the documentation, slash p of n is any kind of numeric character in any script. So it's numbers. So we have an optional space followed by numbers and those would be separated out. So letters and numbers are being separated. So if I do hello world 123, how are you? Then world will stop matching here because one is not a letter anymore. But one is a number, so this group will match for that and we'll get it as a separate entity.

A screenshot of the Jupyter notebook showing the 're.findall' command run on 'Hello world123 how are you?'. The output is a list where ' world' and '123' are separate elements: ['Hello', ' world', '123', ' how', ' are', ' you?'].

[65:26] Andrej Karpathy: Uh, let's see how these apostrophes work. So here, if we have um uh slash b or I mean apostrophe v as an example, then apostrophe here is not a letter or a number. So hello will stop matching and then we will exactly match this with that. So that will come out as a separate thing. So why are they doing the apostrophes here? Honestly, I think that these are just like very common apostrophes uh that are used um typically. I don't love that they've done this because let me show you what happens when you have uh some Unicode apostrophes. Like for example, you can have if you have how's, then this will be separated out because of this matching. But if you use the Unicode apostrophe like this, then suddenly this does not work. And so this apostrophe will actually become its own thing now.

A screenshot of the Jupyter notebook showing the 're.findall' command run on a string with a Unicode apostrophe in 'how’s'. The output shows the apostrophe has been split into its own element in the list.

[66:23] Andrej Karpathy: And so, um it basically hardcoded for this specific kind of apostrophe and uh otherwise they become completely separate tokens. In addition to this, you can go to the GPT-2 docs and here where they define the pattern, they say, should have added re.ignorecase so BPE merges can happen for capitalized versions of contractions. So what they're pointing out is that you see how this is apostrophe and then lowercase letters. Well, because they didn't do re.ignorecase, then um these rules will not separate out the apostrophes if it's uppercase.

A screenshot of the gpt-2 source code for encoder.py. A comment is highlighted which reads: '# Should have added re.IGNORECASE so BPE merges can happen for capitalized versions of contractions'.

[66:59] Andrej Karpathy: So how's would be like this. But if I did HOW'S from uppercase, then notice suddenly the apostrophe comes by itself.

A screenshot of the Jupyter notebook showing the 're.findall' command run on 'HOW'S'. The output list shows 'HOW', the apostrophe, and 'S' as three separate elements, demonstrating the case-sensitivity issue.

[67:13] Andrej Karpathy: So the tokenization will work differently in uppercase and lowercase, inconsistently separating out these apostrophes. So this feels extremely gnarly and slightly gross. Um but that's that's how that works. Okay, so let's come back. After trying to match a bunch of apostrophe expressions, by the way, the other issue here is that these are quite language specific probably. So I don't know that all languages, for example, use or have these apostrophes, but that would be inconsistently tokenized as a result. Then we try to match letters, then we try to match numbers. And then if that doesn't work, we fall back to here. And what this is saying is again, optional space followed by something that is not a letter, number, or a space, and one or more of that. So what this is doing effectively is this is trying to match punctuation, roughly speaking, not letters and not numbers. So this group will try to trigger for that. So if I do something like this, then these parts here uh are not letters or numbers, but they will actually they are uh they will actually get caught here. And so they become its own group. So we've separated out the punctuation.

A screenshot of the Jupyter notebook showing the 're.findall' command run on a string with punctuation 'you!!!??'. The output list shows the punctuation '!!!??' as a separate element.

[68:18] Andrej Karpathy: And finally, this um this is also a little bit confusing. So this is matching white space, but this is using a negative look ahead assertion in regex. So what this is doing is it's matching white space up to but not including the last white space character. Why is this important? Um this is pretty subtle, I think. So you see how the white space is always included at the beginning of the word. So um space r, space u, etc. Suppose we have a lot of spaces here. What's going to happen here is that these spaces up to and not including the last character will get caught by this. And what that will do is it will separate out the spaces up to but not including the last character. So that the last character can come here and join with the uh space you. And the reason that's nice is because space you is the common token. So if I didn't have these extra spaces here, you would just have space you. And if I add tokens, if I add spaces, we still have a space you, but now we have all this extra white space.

A screenshot of the Jupyter notebook showing the 're.findall' command run on a string with multiple spaces before 'you'. The output list shows the extra spaces as one element and ' you' as another.

[69:22] Andrej Karpathy: So basically the GPT-2 tokenizer really likes to have a space letters or numbers. Um and it it prepends these spaces and this is just something that it does consistently. So that's what that is for. And then finally, we have all the the last fallback is um white space characters. Uh so um that would be just um if that doesn't get caught, then this thing will catch any trailing spaces and so on.

[69:50] Andrej Karpathy: I wanted to show one more real world example here. So if we have this string, which is a piece of Python code, and then we try to split it out, then this is the kind of output we get. So you'll notice that the list has many elements here and that's because we are splitting up fairly often uh every time sort of a category changes. Um so there will never be any merges within these elements. And um that's what you are seeing here.

A screenshot of a Jupyter notebook cell containing a multi-line string of Python code for a FizzBuzz implementation. Below it, the 're.findall' command is run on this code, and the output is a long list of small string chunks.

[70:14] Andrej Karpathy: Now, you might think that in order to train the tokenizer, uh OpenAI has used this to split up text into chunks and then run just the BPE algorithm within all the chunks. But that is not exactly what happened. And the reason is the following. Notice that we have the spaces here. Uh those spaces end up being entire elements. But these spaces never actually end up being merged by by OpenAI. And the way you can tell is that if you copy paste the exact same chunk here into tiktoken, um tiktokenizer, you see that all the spaces are kept independent and they're all token 220.

A screenshot of the Tiktokenizer web tool. The left panel shows the FizzBuzz Python code. The right panel shows the tokenized output, with individual space characters highlighted and identified as token 220.

[70:51] Andrej Karpathy: So, I think OpenAI at some point enforced some rule that these spaces would never be merged. And so, um there's some additional rules on top of just chunking and BPEing that OpenAI is not uh clear about. Now, the training code for the GPT-2 tokenizer was never released. So all we have is uh the code that I've already shown you. But this code here that they released is only the inference code for the tokens. So this is not the training code. You can't give it a piece of text and train a tokenizer. This is just the inference code which takes the merges that we have up above and applies them to a new piece of text. And so we don't know exactly how OpenAI trained um trained the tokenizer, but it wasn't as simple as chunk it up and BPE it, uh whatever it was.

Tiktoken

[71:38] Andrej Karpathy: Next, I wanted to introduce you to the tiktoken library from OpenAI, which is the official library for tokenization from OpenAI. So this is tiktoken. Pip install tiktoken and then um you can do the tokenization inference. So this is again, not training code, this is only inference code for tokenization.

A screenshot of the GitHub repository for OpenAI's 'tiktoken' library. The README file is visible, describing it as a fast BPE tokenizer and showing the 'pip install tiktoken' command.

[71:58] Andrej Karpathy: Um I wanted to show you how you would use it. It's quite simple. And running this just gives us the GPT-2 tokens or the GPT-4 tokens. So this is the tokenizer used for GPT-4. As in particular, we see that the white space in GPT-2 uh remains unmerged, but in GPT-4, uh these white spaces merge as we also saw in this one, where here they're all unmerged, but if we go down to GPT-4, uh they become merged.

A screenshot of the Tiktokenizer web tool, now showing the tokenization for the 'cl100k_base' model (GPT-4). The multiple space characters in the FizzBuzz code are now merged into single tokens.

[72:25] Andrej Karpathy: Um now, in the GPT-4 uh tokenizer, they changed the regular expression that they use to chunk up text. So the way to see this is that if you come to your the tiktoken uh library, and then you go to this file, tiktoken_ext, openai_public. This is where sort of like the definition of all the different tokenizers that OpenAI maintains is. And so, uh necessarily to do the inference, they had to publish some of the details about the strings. So this is the string that we already saw for GPT-2. It is slightly different, but it is actually equivalent uh to what we discussed here. So this pattern that we discussed is equivalent to this pattern. Uh this one just uh executes a little bit faster. So here you see a little bit of a slightly different definition, but otherwise it's the same.

A screenshot of the 'openai_public.py' file from the tiktoken library on GitHub. It shows a dictionary defining the 'gpt2' encoding, including a long regular expression string for the 'pat_str' key.

[73:12] Andrej Karpathy: We're going to go into special tokens in a bit. And then if you scroll down to cl100k, this is the GPT-4 tokenizer. You see that the pattern has changed. Um and this is kind of like the main, the major change in addition to a bunch of other special tokens which we'll go into in a bit again.

A screenshot of the same 'openai_public.py' file, scrolled down to the 'cl100k_base' definition. It shows a different, more complex regular expression for its 'pat_str' key.

[73:30] Andrej Karpathy: Now, I'm not going to actually go into the full detail of the pattern change because honestly, this is mind numbing. Uh I would just advise that you uh pull out ChatGPT and the regex uh documentation and just step through it. But really the major changes are, number one, you see this i here, that means that the um case sensitivity, this is case insensitive match. And so the comment that we saw earlier on, oh, you should have used re.uppercase, uh basically, we're now going to be matching these apostrophe s, apostrophe d, apostrophe m, etc. Uh we're going to be matching them both in lowercase and in uppercase. So that's fixed. There's a bunch of different like handling of the white space that I'm not going to go into the full details of. And then one more thing here is you will notice that when they match the numbers, they only match one to three numbers. So they will never merge numbers that are in in more than three digits. Only up to three digits of numbers will ever be merged. And uh that's one change that they made as well to prevent uh tokens that are very, very long number sequences. Uh but again, we don't really know why they do any of this stuff uh because none of this is documented and uh it's just we just get the pattern. Uh so, um yeah. It is what it is. But those are some of the changes that uh GPT-4 has made. And of course, the vocabulary size went from roughly 50k to roughly 100k.

The Official encoder.py

[74:58] Andrej Karpathy: The next thing I would like to do very briefly is to take you through the GPT-2 encoder.py that OpenAI has released. This is the file that I've already mentioned to you briefly. Now, this file is uh fairly short and should be relatively understandable to you at this point. Um starting at the bottom here, they are loading two files, encoder.json and vocab.bpe. And they do some light processing on it and then they call this encoder object, which is the tokenizer.

A screenshot of the official gpt-2 'encoder.py' source code. The 'get_encoder' function is shown at the bottom, which opens 'encoder.json' and 'vocab.bpe' files.

[75:28] Andrej Karpathy: Now, if you'd like to inspect these two files, which together constitute their saved tokenizer, then you can do that with a piece of code like this. Um this is where you can download these two files and you can inspect them if you'd like. And what you will find is that this encoder, as they call it in their code, is exactly equivalent to our vocab.

A screenshot of a Jupyter notebook cell with Python code to download 'vocab.bpe' and 'encoder.json' using wget, and then load them into variables named 'bpe_merges' and 'encoder'.

[75:48] Andrej Karpathy: So remember here where we have this vocab object which allowed us to decode very efficiently. And basically it took us from the integer to the bytes uh for that integer. So our vocab is exactly their encoder. And then their vocab.bpe, confusingly, is actually our merges. So their BPE merges, which is based on the data inside vocab.bpe, ends up being equivalent to our merges. So, uh basically they are saving and loading the two uh variables that for us are also critical, the merges variable and the vocab variable. Using just these two variables, you can represent a tokenizer and you can both do encoding and decoding once you've trained this tokenizer.

[76:36] Andrej Karpathy: Now, the only thing that um is actually slightly confusing inside what OpenAI does here is that in addition to this encoder and the decoder, they also have something called a byte encoder and a byte decoder. And this is actually unfortunately just kind of a spurious implementation detail. It isn't actually deep or interesting in any way. So I'm going to skip the discussion of it. But what OpenAI does here for a reason that I don't fully understand is that not only have they this tokenizer which can encode and decode, but they have a whole separate layer here in addition that is used serially with the tokenizer. And so you first do um byte encode and then encode, and then you do decode and then byte decode. So that's the loop and they are just stacked serial on top of each other. And it's not that interesting, so I won't cover it and you can step through it if you'd like. Otherwise, this file, if you ignore the byte encoder and the byte decoder, will be algorithmically very familiar with you. And the meat of it here is the what they call BPE function, and you should recognize this loop here, which is very similar to our own while loop, where they're trying to identify the bigram, uh a pair that they should be merging next. And then here, just like we had, they have a for loop trying to merge this pair. Uh so they will go over all of the sequence and they will merge the pair whenever they find it. And they keep repeating that until they run out of possible merges in the in the text. So that's the meat of this file. And uh there's an encode and a decode function just like we've implemented it. So long story short, what I want you to take away at this point is that unfortunately, it's a little bit of a messy code that they have, but algorithmically, it is identical to what we've built up above. And what we've built up above, if you understand it, is algorithmically what is necessary to actually build a BPE tokenizer, train it, and then both encode and decode.

Special Tokens

[78:26] Andrej Karpathy: The next topic I would like to turn to is that of special tokens. So, in addition to tokens that are coming from, you know, raw bytes and the BPE merges, we can insert all kinds of tokens that we are going to use to delimit different parts of the data or introduce to create a special structure of the token streams. So, in uh if you look at this encoder object from OpenAI's GPT-2 right here, we mentioned this is very similar to our vocab. You'll notice that the length of this is 50,257.

A screenshot of a Jupyter notebook cell showing the Python code 'len(encoder)' and its output, which is the number 50257.

[78:57] Andrej Karpathy: Where are the tokens? As I mentioned, there are 256 raw byte tokens. And then OpenAI actually did 50,000 merges. So those become the other tokens. But this would have been 50,256. So what is the 57th token? And there is basically one special token. And that one special token, you can see, is called end of text. So this is a special token and it's the very last token. And this token is used to delimit documents in the training set.

[79:54] Andrej Karpathy: So, when we're creating the training data, we have all these documents and we tokenize them and we get a stream of tokens.

Special Tokens

[80:00] Andrej Karpathy: tokens. Those tokens only range from 0 to 50,256. And then in between those documents, we put special end of text token. And we insert that token in between documents.

[80:14] Andrej Karpathy: And we are using this as a signal to the language model that the document has ended and what follows is going to be unrelated to the document previously. That said, the language model has to learn this from data. It it needs to learn that this token usually means that it should wipe its sort of memory of what came before. And what came before this token is not actually informative to what comes next. But we are expecting the language model to just like learn this, but we are giving it this special sort of delimiter of these documents.

Demonstration in Tiktokenizer

[80:44] Andrej Karpathy: We can go here to Tiktokenizer, and um, this is the GPT-2 tokenizer. Uh, our code that we've been playing with before. So we can add here, right? Hello world, how are you? And we're getting different tokens.

[80:56] Andrej Karpathy: But now you can see what what happens if I put end of text. You see how until I finished it, these are all different tokens. End of text, still different tokens. And now when I finish it, suddenly we get token 50,256.

The Tiktokenizer website showing the input 'Hello world how are you <|endoftext|>' and its corresponding token IDs, with the final token being 50256.

How Special Tokens are Handled

[81:14] Andrej Karpathy: And the reason this works is because this didn't actually go through the BPE merges. Instead, the code that actually outputs the tokens has special case instructions for handling special tokens. Um, we did not see these special instructions for handling special tokens in the encoder.py. It's absent there.

[81:36] Andrej Karpathy: But if you go to the tiktoken library, which is uh implemented in Rust, you will find all kinds of special case handling for these special tokens that you can register, uh create, add to the vocabulary, and then it looks for them and it uh whenever it sees these special tokens like this, it will actually come in and swap in that special token. So these things are outside of the typical algorithm of uh byte-pair encoding.

A screenshot of the lib.rs file from the tiktoken library on GitHub, showing Rust code with a highlighted section for handling special tokens.

Special Tokens in Fine-Tuning

[82:01] Andrej Karpathy: So these special tokens are used pervasively, uh not just in uh basically base language modeling of predicting the next token in a sequence, but especially when it gets to later to the fine-tuning stage and all the chat GPT sort of aspects of it. Uh because we don't just want to delimit documents, we want to delimit entire conversations between an assistant and a user. So if I refresh this Tiktokenizer page, the default example that they have here is using not sort of base model encoders, but fine-tuned model uh sort of tokenizers.

[82:34] Andrej Karpathy: Um, so for example, using the GPT-3.5 Turbo scheme, these here are all special tokens. I am start, I am end, etc. Uh this is short for imaginary monologue underscore start, by the way. But you can see here that there's a sort of start and end of every single message, and there can be many other tokens, uh lots of tokens, um in use to delimit these conversations and kind of keep track of the flow of the messages here.

The Tiktokenizer website in chat mode for GPT-3.5-turbo, showing special tokens like <|im_start|>system and <|im_end|> used to structure a conversation.

Extending Tiktoken with New Special Tokens

[83:02] Andrej Karpathy: Now let's go back to the tiktoken library. And here when you scroll to the bottom, they talk about how you can extend tiktoken and how you can you can create basically, you can fork uh the um CL100K base tokenizers in GPT-4. And for example, you can extend it by adding more special tokens. And these are totally up to you. You can come up with any arbitrary tokens and add them with the new ID afterwards. And the tiktoken library will uh correctly swap them out uh when it sees this in the strings.

The README file for the tiktoken GitHub repository, showing a section titled 'Extending tiktoken' with a Python code example for adding new special tokens.

[83:33] Andrej Karpathy: Now, we can also go back to this file which we looked at previously. And I mentioned that the GPT-2 in tiktoken, openai_public.py, we have the vocabulary, we have the pattern for splitting, and then here we are registering the single special token in GPT-2, which was the end of text token, and we saw that it has this ID.

A screenshot of the openai_public.py file in the tiktoken repository, highlighting the special_tokens dictionary for the GPT-2 tokenizer, which contains only the <|endoftext|> token.

Special Tokens in GPT-4

[83:53] Andrej Karpathy: In GPT-4, when they defined this here, you see that the pattern has changed as we've discussed, but also the special tokens have changed in this tokenizer. So we of course have the end of text, just like in GPT-2, but we also see three, sorry, four additional tokens here. FIM prefix, middle, and suffix. What is FIM? FIM is short for fill in the middle. And if you'd like to learn more about this idea, it comes from this paper.

A screenshot of the openai_public.py file, highlighting the special_tokens dictionary for the cl100k_base (GPT-4) tokenizer, which includes <|endoftext|> and new FIM tokens.

[84:18] Andrej Karpathy: Um, and I'm not going to go into detail in this video, it's beyond this video. And then there's uh one additional uh sort of token here. So that's that encoding as well.

The title page of the research paper 'Efficient Training of Language Models to Fill in the Middle' from OpenAI, dated July 28, 2022.

[84:30] Andrej Karpathy: So it's very common, basically to train a language model, and then if you'd like, uh you can add special tokens. Now, when you add special tokens, you of course have to um do some model surgery to the transformer and all the parameters involved in that transformer. Because you are basically adding an integer and you want to make sure that for example, your embedding matrix for the vocabulary tokens has to be extended by adding a row. And typically this row would be initialized uh with small random numbers or something like that, uh because we need to have a vector that now stands for that token.

[85:03] Andrej Karpathy: In addition to that, you have to go to the final layer of the transformer and you have to make sure that that projection at the very end into the classifier uh is extended by one as well. So basically there's some model surgery involved that you have to couple with the tokenization changes if you are going to add special tokens. But this is a very common operation that people do, especially if they'd like to fine-tune the model, for example, taking it from a base model to a chat model like ChatGPT.

The minbpe Exercise

[85:28] Andrej Karpathy: Okay, so at this point you should have everything you need in order to build your own GPT-4 tokenizer. Now, in the process of developing this lecture, I've done that and I've published the code under this repository minbpe.

A Jupyter Notebook cell outlining the 'minbpe exercise' to build a GPT-4 tokenizer, with a link to the minbpe repository and a code snippet showing the target behavior.

[85:40] Andrej Karpathy: So minbpe looks like this right now as I'm recording, but um the minbpe repository will probably change quite a bit because I intend to continue working on it. Um, in addition to the minbpe repository, I've published this uh exercise progression that you can follow. So if you go to exercise.md here, this is sort of me breaking up the task ahead of you into four steps that sort of uh build up to what can be a GPT-4 tokenizer. And so feel free to follow these steps exactly and uh follow a little bit of the guidance that I've laid out here. And anytime you feel stuck, just reference the minbpe repository here.

The exercise.md file from the minbpe GitHub repository, showing the steps for the 'Build your own GPT-4 Tokenizer!' exercise.

[86:17] Andrej Karpathy: So either the tests could be useful or the minbpe repository itself. I tried to keep the code fairly clean and understandable. And so, um, feel free to reference it whenever um you get stuck.

[86:31] Andrej Karpathy: In addition to that, basically, once you write it, you should be able to reproduce this behavior from tiktoken. So getting the GPT-4 tokenizer, you can take uh you can encode this string and you should get these tokens. And then you can encode and decode the exact same string to recover it. And in addition to all that, you should be able to implement your own train function, which tiktoken library does not provide. It's again, only inference code. But you should be able to write your own train, minbpe does it as well. And that will allow you to train your own token vocabularies.

[87:01] Andrej Karpathy: So here's some of the code inside minbpe, minbpe, uh shows the token vocabularies that you might obtain. So on the left uh here, we have the GPT-4 merges. Uh so the first 256 are raw individual bytes. And then here I am visualizing the merges that GPT-4 performed during its training. So the very first merge that GPT-4 did was merge two spaces into a single token for, you know, two spaces. And that is the token 256.

[87:31] Andrej Karpathy: And so this is the order in which things merged during GPT-4 training. And this is the merge order that um we obtained in minbpe by training a tokenizer. And in this case, I trained it on a Wikipedia page of Taylor Swift. Uh not because I'm a Swifty, but because that is one of the longest um Wikipedia pages apparently that's available. But she is pretty cool. And um, what was I going to say? Yeah, so you can compare these two uh vocabularies and so as an example, um, here GPT-4 merged I M to become in, and we've done the exact same thing on this token 259. Here, space T becomes spacey, and that happened for us a little bit later as well. So the difference here is again, to my understanding, only a difference of the training set. So as an example, because I see a lot of white space, I expect that GPT-4 probably had a lot of Python code in its training set. I'm not sure. Uh for the tokenizer. And uh here we see much less of that, of course, in the Wikipedia page. So roughly speaking, they look the same and they look the same because they're running the same algorithm. And when you train your own, you're probably going to get something similar depending on what you train it on.

A split-screen view in a code editor. The left pane shows the official GPT-4 merge vocabulary. The right pane shows a merge vocabulary trained on Taylor Swift's Wikipedia page.

SentencePiece

[88:42] Andrej Karpathy: Okay, so we are now going to move on from tiktoken and the way that OpenAI tokenizes its strings. And we're going to discuss one more very commonly used library for working with tokenization in LLMs, and that is SentencePiece. So SentencePiece is uh very commonly used in language models because unlike tiktoken, it can do both training and inference, and it's quite efficient at both. It supports a number of algorithms for training uh vocabularies, but one of them is the byte-pair encoding algorithm that we've been looking at. So it supports it.

A Jupyter Notebook with a markdown cell titled 'sentencepiece', explaining its common use and differences from tiktoken.

[89:13] Andrej Karpathy: Now, SentencePiece is used both by Llama and Mistral series and many other models as well. It is on GitHub under google/sentencepiece.

The main page of the google/sentencepiece GitHub repository, described as an 'Unsupervised text tokenizer for Neural Network-based text generation'.

[89:22] Andrej Karpathy: And the big difference with SentencePiece, and we're going to look at an example because this is kind of hard and subtle to explain, is that they think different about the order of uh operations here. So in the case of tiktoken, we first take our code points in a string, we encode them using UTF-8 to bytes, and then we're merging bytes. It's fairly straightforward.

[89:46] Andrej Karpathy: For SentencePiece, um it works directly on the level of the code points themselves. So it looks at whatever code points are available in your training set, and then it starts merging those code points. And um the BPE is running on the level of code points. And if you happen to run out of code points, so there are maybe some rare uh code points that just don't come up too often, and the rarity is determined by this character coverage hyperparameter, then these uh code points will either get mapped to a special unknown token, like unk, or if you have the byte fallback option turned on, then they will take those rare code points, they will encode them using UTF-8, and then the individual bytes of that encoding will be translated into tokens. And there are these special byte tokens that basically get added to the vocabulary. So it uses BPE on on the code points, and then it falls back to bytes for rare code points. Um, and so that's kind of our difference. Personally, I find the tiktoken way significantly cleaner, uh but it's kind of like a subtle but pretty major difference between the way they approach tokenization.

Training a SentencePiece Model

[90:51] Andrej Karpathy: Let's work with a concrete example because otherwise this is kind of hard to um to get your head around. So let's work with a concrete example. This is how we can import SentencePiece. And then here we're going to take, I think I took like the description of SentencePiece and I just created like a little toy dataset. It really likes to have a file, so I created a toy.txt file with this content.

[91:13] Andrej Karpathy: Now, what's kind of a little bit crazy about SentencePiece is that there's a ton of options and configurations. And the reason this is so is because SentencePiece has been around, I think for a while, and it really tried to handle a large diversity of things. And um because it's been around, I think it has quite a bit of accumulated historical baggage uh as well. And so in particular, there's like a ton of configuration arguments. This is not even all of it.

A Jupyter Notebook cell showing a Python dictionary named 'options' with a very long list of configuration parameters for training a SentencePiece model.

[91:38] Andrej Karpathy: You can go to here to see all the training options. Um, and uh there's also quite useful documentation when you look at the raw protobuf uh that is used to represent the trainer spec and so on. Um, many of these options are irrelevant to us. So maybe to point out one example, dash dash shrinking factor. Uh this shrinking factor is not used in the byte-pair encoding algorithm. So this is just an argument that is irrelevant to us. Um, it applies to a different training algorithm.

The special_options.md file from the SentencePiece GitHub repository, listing numerous command-line options for training.

[92:09] Andrej Karpathy: Now, what I tried to do here is I tried to set up SentencePiece in a way that is very, very similar, as far as I can tell, to maybe identical hopefully, to the way that Llama 2 was trained. So the way they trained their own um their own tokenizer. And the way I did this was basically going to take the tokenizer.model file that Meta released, and you can um open it using the proto protobuf uh sort of file that you can generate. And then you can inspect all the options, and I tried to copy over all the options that look relevant.

[92:42] Andrej Karpathy: So here we set up the input. It's raw text in this file. Here it's going to be the output, so it's going to be prefix tok400.model and .vocab. We're saying that we're going to use the BPE algorithm and we want a vocab size of 400. Then there's a ton of configurations here for um for basically preprocessing and normalization rules as they're called. Normalization used to be very prevalent, I would say before LLMs in natural language processing. So in machine translation and uh text classification and so on, you want to normalize and simplify the text, and you want to turn it all lowercase and you want to remove all double white space, etc.

[93:22] Andrej Karpathy: And in language models, it's preferred not to do any of it, or at least that is my preference as a deep learning person. You want to not touch your data. You want to keep the raw data as much as possible um in a raw form. So you're basically trying to turn off a lot of this if you can. The other thing that SentencePiece does is that it has this concept of sentences. So SentencePiece, it's back, it kind of was developed, I think early in the days where there was um an idea that they you're training a tokenizer on a bunch of independent sentences. So it has a lot of like how many sentences you're going to train on, what is the maximum sentence length. Um, shuffling sentences. And so for it, sentences are kind of like the individual training examples.

[94:06] Andrej Karpathy: But again, in the context of LLMs, I find that this is like a very spurious and weird distinction. Like sentences are just like, don't touch the raw data. Sentences happen to exist, but in the raw datasets, there are a lot of like in-betweens. Like what exactly is a sentence? What isn't a sentence? Um, and so I think like it's really hard to define what an actual sentence is if you really like dig into it. And there could be different concepts of it in different languages or something like that. So why even introduce the concept? It it doesn't honestly make sense to me. I would just prefer to treat a file as a giant uh stream of bytes.

[94:41] Andrej Karpathy: It has a lot of treatment around rare word characters, and when I say word, I mean code points. We're going to come back to this in a second. And it has a lot of other rules for um basically splitting digits, splitting white space and numbers and how you deal with that. So this is something like merge rules. So I think this is a little bit similar to tiktoken using the regular expression to split up categories. There's like kind of the equivalent of it is quintated in SentencePiece where you can also, for example, split up the digits, uh and uh so on.

[95:16] Andrej Karpathy: There's a few more things here that I'll come back to in a bit. And then there are some special tokens that you can indicate. And it hardcodes the unk token, the beginning of sentence, end of sentence, and a pad token. Um, and the unk token must exist for my understanding. And then some system things. So we can train. And when when I press train, it's going to create this file tok400.model and tok400.vocab. I can then load the model file and I can inspect the vocabulary of it.

[95:47] Andrej Karpathy: And so we trained a vocab size 400 on this text here. And these are the individual pieces, the individual tokens that SentencePiece will create. So in the beginning, we see that we have the unk token with the ID zero. Then we have the beginning of sequence, end of sequence, one and two. And then we said that the pad ID is negative one, so we chose not to use it. So there's no pad ID here.

[96:14] Andrej Karpathy: Then these are individual byte tokens. So here we saw that byte fallback in Llama was turned on, so it's true. So what follows are going to be the 256 byte tokens. And these are their IDs.

A Jupyter Notebook cell showing the vocabulary of a trained SentencePiece model. It lists special tokens like <unk>, <s>, </s>, followed by byte tokens like <0x00>, <0x01>, etc.

[96:32] Andrej Karpathy: And then at the bottom, after the byte tokens, come the merges. And these are the parent nodes in the merges. So we're not seeing the children, we're just seeing the parents and their ID. And then after the merges comes eventually the individual tokens and their IDs. And so these are the individual tokens, so these are the individual code point tokens, if you will, and they come at the end.

[96:59] Andrej Karpathy: So that is the ordering with which SentencePiece sort of represents its vocabularies. It starts with special tokens, then the byte tokens, then the merge tokens, and then the individual code point tokens. And all these raw code point tokens are the ones that it encountered in the training set. So those individual code points are all the the entire set of code points that occurred here.

[97:27] Andrej Karpathy: And then those that are extremely rare, as determined by character coverage, so if a code point occurred only a single time out of like a million um sentences or something like that, then it would be ignored and it would not be added to our uh vocabulary. Once we have a vocabulary, we can encode into IDs and we can um sort of get a list. And then here I am also decoding the individual tokens back into little pieces as they call it.

Byte Fallback in SentencePiece

[97:56] Andrej Karpathy: So let's take a look at what happened here. Hello space 안녕하세요. So these are the token IDs we got back. And when we look here, uh a few things sort of uh jump to mind. Number one, take a look at these characters. The Korean characters, of course, were not part of the training set. So SentencePiece is encountering code points that it has not seen during training time, and those code points do not have a token associated with them. So suddenly these are unk tokens, unknown tokens.

[98:30] Andrej Karpathy: But because byte fallback is true, instead, SentencePiece falls back to bytes. And so it takes this, it encodes it with UTF-8, and then it uses these tokens to represent uh those bytes. And that's what we are getting sort of here. This is the UTF-8 uh encoding, and it is shifted by three uh because of these um special tokens here that have IDs earlier on. So that's what happened here.

[99:00] Andrej Karpathy: Now, one more thing that um, well, first before I go on, with respect to the byte fallback, let me remove byte fallback. If this is false, what's going to happen? Let's retrain. So the first thing that happened is all the byte tokens disappeared, right? And now we just have the merges, and we have a lot more merges now because we have a lot more space because we're not taking up space in the vocab size uh with all the bytes.

The vocabulary of a SentencePiece model trained with byte_fallback=False. The list of tokens no longer contains byte representations like <0x00>.

[99:26] Andrej Karpathy: And now if we encode this, we get a zero. So this entire string here suddenly, there's no byte fallback, so this is unknown, and unknown is unk. And so this is zero because the unk token is token zero. And you have to keep in mind that this would feed into your uh language model. So what is the language model supposed to do when all kinds of different things that are unrecognized because they are rare just end up mapping into unk? It's not exactly the property that you want. So that's why I think Llama correctly uh used byte fallback.

Encoding 'hello 안녕하세요' with byte_fallback=False. The Korean part maps to a single unknown token with ID 0, as shown in the output.

[100:00] Andrej Karpathy: fallback true, because we definitely want to feed these unknown or rare code points into the model in some, some manner.

The add_dummy_prefix Option

[100:08] Andrej Karpathy: The next thing I want to show you is the following. Notice here when we are decoding all the individual tokens, you see how spaces, uh, space here ends up being this bold underline. I'm not 100% sure, by the way, why SentencePiece switches whitespace into these bold underscore characters. Maybe it's for visualization, I'm not 100% sure why that happens.

A Jupyter Notebook cell showing the tokenization of 'Hello 안녕하세요'. The output is a list of decoded tokens, where spaces are represented by a bold underscore character.

[100:31] Andrej Karpathy: But notice this, why do we have an extra space in the front of hello? Uh, what where is this coming from? Well, it's coming from this option here, um, add dummy prefix is true.

[100:48] Andrej Karpathy: And when you go to the documentation, add dummy whitespace at the beginning of text in order to treat "world" in "world" and "hello world" in the exact same way.

A screenshot of the SentencePiece documentation on GitHub. The documentation for the 'add_dummy_prefix' option is highlighted, explaining that it adds whitespace to treat words at the beginning of a sentence and in the middle of a sentence identically.

[100:57] Andrej Karpathy: So what this is trying to do is the following. If we go back to our tiktokenizer, "world" as a token by itself has a different ID than "space world". So we have, this is 1917, but this is 14, etc. So these are two different tokens for the language model, and the language model has to learn from data that they are actually kind of a very similar concept. So to the language model in the tiktoken world, basically words in the beginning of sentences and words in the middle of sentences actually look completely different. Um, and it has to learn that they are roughly the same.

The tiktokenizer web app interface. The input text contains 'world' on one line and 'hello world' on the next. The output shows four tokens with their corresponding IDs, demonstrating that 'world' (14957) and ' world' (1917) are tokenized differently.

[101:34] Andrej Karpathy: So this add dummy prefix is trying to fight that a little bit. And the way that works is that it basically, uh, adds a dummy prefix. So for, as a, as a part of preprocessing, it will take this string and it will add a space. It will do this. And that's done in an effort to make this world and that world the same. They will both be "space world". So that's one other kind of preprocessing option that is turned on, and Llama 2 also, uh, uses this option.

SentencePiece Summary

[102:07] Andrej Karpathy: And that's I think everything that I want to say from my preview of SentencePiece and how it is different. Um, maybe here what I've done is I just, uh, put in the raw protocol buffer representation basically of the tokenizer that Llama 2 trained. So feel free to sort of inspect through this, and if you would like, uh, your tokenization to look identical to that of the Meta, uh, Llama 2, then you would be copy-pasting these settings as I've tried to do up above. And, uh, yeah, that's, I think that's it for this section.

A Jupyter Notebook cell displaying the raw protocol buffer output for the Llama 2 tokenizer. It shows a long list of configuration parameters under 'normalizer_spec' and 'trainer_spec'.

[102:38] Andrej Karpathy: I think my summary for SentencePiece from all this is, number one, I think that there's a lot of historical baggage in SentencePiece. A lot of concepts that I think are slightly confusing and I think potentially, um, contain footguns, like this concept of a sentence and its maximum length and stuff like that. Um, otherwise it is fairly commonly used in the industry, um, because it is efficient and can do both training and inference. Uh, it has a few quirks, like for example, unk token must exist and the way the byte fallbacks are done and so on, I don't find particularly elegant. And unfortunately, I have to say it's not very well documented. So it took me a lot of time working with this myself, um, and just visualizing things and trying to really understand what is happening here because, um, documentation unfortunately is, in my opinion, not, not super amazing. But it is a very nice repo that is available to you if you'd like to train your own tokenizer right now.

vocab size

[103:28] Andrej Karpathy: Okay, let me now switch gears again as we're starting to slowly wrap up here. I want to revisit this issue in a bit more detail of how we should set the vocab size or some of the considerations around it. So for this, I'd like to go back to the model architecture that we developed in the last video when we built the GPT from scratch.

A markdown cell in a Jupyter Notebook with the heading 'vocab size'. It lists two questions: 'Q: what should be vocab size?' and 'Q: how can I increase vocab size?'.

[103:45] Andrej Karpathy: So this here was, uh, the file that we built in the previous video, and we defined the transformer model. And let's specifically look at vocab size and where it appears in this file. So here we define the vocab size. Uh, at this time it was 65 or something like that, extremely small number. So this will grow much larger.

A Python script named 'gpt.py' is open in a code editor. The line 'vocab_size = len(chars)' is highlighted, indicating the definition of the vocabulary size based on the number of unique characters in the text.

[104:03] Andrej Karpathy: You'll see that vocab size doesn't come up too much in most of these layers. The only place that it comes up to is in exactly these two places here. So when we define the language model, there's the token embedding table, which is this two-dimensional array where the vocab size is basically the number of rows. And, uh, each vocabulary element, each token, has a vector that we're going to train using backpropagation. That vector is of size n_embed, which is the number of channels in the transformer. And basically as vocab size increases, this embedding table, as I mentioned earlier, is going to also grow. We're going to be adding rows.

A Python class 'GPTLanguageModel' is shown. The lines defining 'self.token_embedding_table = nn.Embedding(vocab_size, n_embed)' and 'self.lm_head = nn.Linear(n_embed, vocab_size)' are highlighted.

[104:38] Andrej Karpathy: In addition to that, at the end of the transformer, there's this lm_head layer, which is a linear layer. And you'll notice that that layer is used at the very end to produce the logits, uh, which become the probabilities for the next token in the sequence. And so intuitively, we're trying to produce a probability for every single token that might come next at every point in time of that transformer. And if we have more and more tokens, we need to produce more and more probabilities. So every single token is going to introduce an additional dot product that we have to do here in this linear layer for this final layer in the transformer.

The forward pass method of the GPTLanguageModel class. The line 'logits = self.lm_head(x)' is highlighted, showing where the final linear layer is used to compute the output logits.

[105:12] Andrej Karpathy: So why can't vocab size be infinite? Why can't it grow to infinity? Well, number one, your token embedding table is going to grow. Uh, your linear layer is going to grow. So we're going to be doing a lot more computation here because this lm_head layer will become more computationally expensive. Number two, because we have more parameters, we could be worried that we are going to be under-training some of these parameters.

[105:36] Andrej Karpathy: So intuitively, if you have a very large vocabulary size, say we have a million, uh, tokens, then every one of these tokens is going to come up more and more rarely in the training data because there's a lot more other tokens all over the place. And so we're going to be seeing fewer and fewer examples, uh, for each individual token. And you might be worried that basically the vectors associated with every token will be under-trained as a result because they just don't come up too often and don't participate in the forward-backward pass.

[106:03] Andrej Karpathy: In addition to that, as your vocab size grows, you're going to start shrinking your sequences a lot, right? And that's really nice because that means that we're going to be attending to more and more text. So that's nice. But also you might be worried that too large of chunks are being squished into single tokens. And so the model just doesn't have as much sort of time to think per sort of, um, some number of characters in a text, or you can think about it that way, right? So basically we're squishing too much information into a single token, and then the forward pass of the transformer is not enough to actually process that information appropriately.

[106:36] Andrej Karpathy: And so these are some of the considerations you're thinking about when you're designing the vocab size. As I mentioned, this is mostly an empirical hyperparameter, and it seems like in state-of-the-art architectures today, this is usually in the high 10,000s or somewhere around 100,000 today.

How can I increase vocab size?

[106:49] Andrej Karpathy: And the next consideration I want to briefly talk about is what if we want to take a pre-trained model and we want to extend the vocab size? And this is done fairly commonly actually. So for example, when you're doing fine-tuning with ChatGPT, um, a lot more new special tokens get introduced on top of the base model to maintain the metadata and all the structure of conversation objects between the user and the assistant. So that takes a lot of special tokens. You might also try to throw in more special tokens, for example, for using the browser or any other tool. And so it's very tempting to add a lot of tokens for all kinds of special functionality.

[107:24] Andrej Karpathy: So if you want to be adding a token, that's totally possible, right? All we have to do is we have to resize this embedding, so we have to add rows. We would initialize these, uh, parameters from scratch, which would be small random numbers. And then we have to extend the weight inside this linear. Uh, so we have to start making dot products, um, with the associated parameters as well to basically calculate the probabilities for these new tokens.

[107:47] Andrej Karpathy: So both of these are just the resizing operation. It's a very mild, uh, model surgery and can be done fairly easily. And it's quite common that basically you would freeze the base model, you introduce these new parameters, and then you only train these new parameters to introduce new tokens into the architecture. Um, and so you can freeze arbitrary parts of it or you can train arbitrary parts of it and that's totally up to you. So basically minor surgery required if you'd like to introduce new tokens.

Learning to Compress Prompts with Gist Tokens

[108:11] Andrej Karpathy: And finally, I'd like to mention that actually there's an entire design space of applications in terms of introducing new tokens into a vocabulary that go way beyond just adding special tokens and special new functionality. So just to give you the sense of the design space, but this could be an entire video just by itself. Uh, this is a paper on learning to compress prompts with what they call gist tokens.

The title page of a research paper titled 'Learning to Compress Prompts with Gist Tokens' by Jesse Mu, Xiang Lisa Li, and Noah Goodman from Stanford University.

[108:31] Andrej Karpathy: And the rough idea is, suppose that you're using language models in a setting that requires very long prompts. Well, these long prompts just slow everything down because you have to encode them and then you have to use them and then you're attending over them and it's just, um, you know, heavy to have very large prompts. So instead, what they do here in this paper is they introduce new tokens and, um, imagine basically having a few new tokens, you put them in a sequence, and then you train the model by distillation.

A figure from the 'Gist Tokens' paper comparing three methods: Prompting, Finetuning/Distillation, and Gisting. The Gisting diagram shows a short sequence of special 'gist tokens' being used to achieve the same result as a much longer prompt.

[109:01] Andrej Karpathy: So you are keeping the entire model frozen and you're only training the representations of the new tokens, their embeddings. And you're optimizing over the new tokens such that the behavior of the language model is identical, uh, to the model that has a very long prompt that works for you. And so it's a compression technique of compressing that very long prompt into those few new gist tokens. And so you can train this and then at test time, you can discard your old prompt and just swap in those tokens and they sort of like a stand-in for that very long prompt and have an almost identical performance. And so this is one, um, technique in a class of parameter-efficient fine-tuning techniques where most of the model is basically fixed and there's no training of the model weights, there's no training of LoRA or anything like that of new parameters. The parameters that you're training are now just the, uh, token embeddings. So that's just one example, but this could again be like an entire video, but just to give you a sense that there's a whole design space here that is potentially worth exploring in the future.

Taming Transformers for High-Resolution Image Synthesis (a.k.a VQGAN)

[109:58] Andrej Karpathy: The next thing I want to briefly address is that I think recently there's a lot of momentum in how you actually could construct transformers that can simultaneously process not just text as the input modality, but a lot of other modalities. So be it images, videos, audio, etc. And how do you feed in all these modalities and potentially predict these modalities from a transformer? Uh, do you have to change the architecture in some fundamental way? And I think what a lot of people are starting to converge towards is that you're not changing the architecture, you stick with the transformer, you just kind of tokenize your input domains and then call it a day and pretend it's just text tokens and just do everything else identical in an identical manner.

[110:35] Andrej Karpathy: So here for example, there was an early paper that has a nice graphic for how you can take an image and you can truncate it into integers. Um, and these, uh, sometimes, uh, so these would basically become the tokens of images as an example. And, uh, these tokens can be, uh, hard tokens where you, uh, force them to be integers. They can also be soft tokens where you, uh, sort of don't require, uh, these to be discrete, but you do force these representations to go through a bottleneck, like in autoencoders.

A diagram illustrating the VQGAN architecture. An image of a dog is passed through a CNN Encoder, quantized into a codebook, and then fed into a Transformer. The output is passed through a CNN Decoder to generate a 'realfake' image.

[111:05] Andrej Karpathy: Uh, also in this paper that came out from OpenAI Sora, which I think really, um, uh, blew the mind of many people and inspired a lot of people in terms of what's possible. They have a graphic here and they talk briefly about how LLMs have text tokens, Sora has visual patches. So again, they came up with a way to truncate videos into basically tokens with their own vocabularies. And then you can either process discrete tokens, say with autoregressive models, or even soft tokens with diffusion models. And, uh, all of that is sort of, uh, being actively worked on and designed on and is beyond the scope of this video, but just something I wanted to mention briefly.

A screenshot from the OpenAI Sora technical report. A paragraph is highlighted which states, 'Whereas LLMs have text tokens, Sora has visual patches.' Below, a diagram shows a video frame being broken down into a 3D grid of patches.

Tokenization is at the heart of the weirdness of LLMs

[111:42] Andrej Karpathy: Okay, now that we have gone quite deep into the tokenization algorithm and we understand a lot more about how it works, let's loop back around to the beginning of this video and go through some of these bullet points and really see why they happen.

[111:55] Andrej Karpathy: So first of all, why can't my LLM spell words very well or do other spell-related tasks? So fundamentally, this is because, as we saw, these characters are chunked up into tokens, and some of these tokens are actually fairly long. So as an example, I went to the GPT-4 vocabulary and I looked at, uh, one of the longer tokens. So .DefaultCellStyle turns out to be a single individual token. So that's a lot of characters for a single token.

The tiktokenizer web app showing that the string '.DefaultCellStyle' is treated as a single token with ID 98518 by the cl100k_base tokenizer.

[112:22] Andrej Karpathy: So my suspicion is that there's just too much crammed into this single token. And my suspicion was that the model should not be very good at tasks related to spelling of this, uh, single token. So I asked, how many letters L are there in the word .DefaultCellStyle? And of course, my prompt is intentionally done that way. And you see how .DefaultCellStyle will be a single token. So this is what the model sees. So my suspicion is that it wouldn't be very good at this, and indeed it is not. It doesn't actually know how many L's are in there. It thinks there are three, and actually there are four. So I'm not getting this wrong myself. So that didn't go extremely well.

A screenshot of a conversation with ChatGPT 4. The user asks, 'How many letters 'l' are there in the word '.DefaultCellStyle'?' ChatGPT incorrectly replies, 'The word '.DefaultCellStyle' contains three 'l' letters.'

[113:01] Andrej Karpathy: Let's look at another kind of, uh, character-level task. So for example, here I asked, uh, GPT-4 to reverse the string .DefaultCellStyle. And it tried to use a code interpreter, and I stopped it and I said, just do it, just try it. And, uh, it gave me jumble. So it doesn't actually really know how to reverse this string going from right to left. Uh, so it gave a wrong result.

[113:26] Andrej Karpathy: So again, like working with this, working on the hypothesis that maybe this is due to tokenization, I tried a different approach. I said, okay, let's reverse the exact same string, but take the following approach. Step one, just print out every single character separated by spaces, and then as a step two, reverse that list. And it again tried to use a tool, but when I stopped it, it, uh, first, uh, produced all the characters, and that was actually correct. And then it reversed them, and that was correct once it had this. So somehow it can't reverse it directly, but when you go just first, uh, you know, listing it out in order, it can do that somehow. And then it can, once it's, uh, broken up this way, this becomes all these individual characters. And so now this is much easier for it to see these individual tokens and reverse them and print them out. So that is kind of interesting.

A ChatGPT conversation showing a successful two-step string reversal. First, the model correctly lists each character of '.DefaultCellStyle' separated by spaces. Then, it correctly reverses that list of characters.

[114:15] Andrej Karpathy: So let's continue now. Why are LLMs worse at, uh, non-English languages? And I briefly covered this already, but basically, um, it's not only that the language model sees less non-English data during training of the model parameters, but also the tokenizer is not, uh, is not sufficiently trained on non-English data. And so here, for example, "Hello how are you?" is five tokens, and its translation is 15 tokens. So this is a three times blow-up. And so, for example, "annyeonghaseyo" is, uh, just "hello" basically in Korean, and that ends up being three tokens. I'm actually kind of surprised by that because that is a very common phrase. It is a typical greeting, like "hello", and that ends up being three tokens, whereas our "hello" is a single token. And so basically everything is a lot more bloated and diffused, and this is I think partly the reason that the model works worse on other languages.

The tiktokenizer web app comparing an English phrase and its Korean translation. 'Hello how are you?' is 5 tokens, while the Korean equivalent '안녕하세요 어떻게 지내세요?' is 15 tokens, resulting in a total of 20 tokens.

[115:08] Andrej Karpathy: Coming back, why is LLM bad at simple arithmetic? Um, that has to do with the tokenization of numbers. And so, um, you'll notice that, for example, addition is very sort of like, uh, there's an algorithm that is like character-level for doing addition. So for example, here we would first add the ones and then the tens and then the hundreds. You have to refer to specific parts of these digits.

A slide titled 'Addition Using Standard Algorithm'. It shows the addition of 1,296 and 3,457, with a carry-over '1' highlighted. The steps listed are: 1. Add the ones, 2. Add the tens, 3. Add the hundreds.

[115:33] Andrej Karpathy: But, uh, these numbers are represented completely arbitrarily based on whatever happened to merge or not merge during the tokenization process. There's an entire blog post about this that I think is quite good, "Integer tokenization is insane". And this person basically systematically explores the tokenization of numbers in, I believe this is GPT-2. And so they notice that, for example, for the, for, uh, four-digit numbers, you can take a look at whether it is, uh, a single token or whether it is two tokens that is a 1-3 or a 2-2 or a 3-1 combination. And so all the different numbers are all the different combinations. And you can imagine that this is all completely arbitrarily so. And the model, unfortunately, sometimes sees, uh, four, um, a token for, for all four digits, sometimes for three, sometimes for two, sometimes for one, and it's in an arbitrary, uh, manner. And so this is definitely a headwind, if you will, for the language model. And it's kind of incredible that it can kind of do it and deal with it, but it's also kind of not ideal. And so that's why, for example, we saw that Meta, when they trained the Llama 2 algorithm and they used SentencePiece, they made sure to split up all the, um, all the digits as an example for, uh, Llama 2. And this is partly to improve, uh, simple arithmetic kind of performance.

A visualization from the 'Integer tokenization is insane' blog post. It's a heatmap showing how 4-digit numbers are composed into tokens by the GPT-2 tokenizer. Different colors represent different compositions (e.g., unique, 1-3 split, 2-2 split, 3-1 split), revealing a non-uniform and somewhat chaotic pattern.

[116:48] Andrej Karpathy: And finally, why is GPT-2 not as good in Python? Again, this is partly a modeling issue on in the architecture and the dataset and the strength of the model, but it's also partly tokenization because as we saw here with the simple Python example, the encoding efficiency of the tokenizer for handling spaces in Python is terrible. And every single space is an individual token, and this dramatically reduces the context length that the model can attend across. So that's almost like a tokenization bug for GPT-2, and that was later fixed with GPT-4.

[117:19] Andrej Karpathy: Okay, so here's another fun one. My LLM abruptly halts when it sees the string <|endoftext|>. So here's, um, here's a very strange behavior. Print the string <|endoftext|>. That's what I told GPT-4. And it says, "Could you please specify the string?" And I'm telling it, "Give me <|endoftext|>." And it seems like there's an issue. It's not seeing <|endoftext|>. And then I give it <|endoftext|> is the string, and then here's the string, and then it just doesn't print it.

A ChatGPT-4 conversation where the user repeatedly tries to get the model to print the string '<|endoftext|>', but the model acts confused and fails to output the string.

[117:46] Andrej Karpathy: So obviously something is breaking here with respect to the handling of the special token. And I didn't actually know what OpenAI is doing under the hood here and whether they are potentially parsing this as an, um, as an actual token instead of this just being <|endoftext|> as like individual sort of pieces of it without the special token handling logic. And so it might be that someone when they're calling .encode, uh, they are passing in the allowed_special and they are allowing <|endoftext|> as a special character in the user prompt. But the user prompt, of course, is, is a sort of, um, attacker-controlled text. So you would hope that they don't really parse or use special tokens or, you know, uh, from that kind of input. But it appears that there's something definitely going wrong here. And, um, so your knowledge of these special tokens ends up being an attack surface potentially. And so if you'd like to confuse, uh, LLMs, then just, um, try to give them some special tokens and see if you're breaking something by chance.

[118:46] Andrej Karpathy: Okay, so this next one is another fun one. Uh, the trailing whitespace issue. So if you come to Playground and, uh, we come here to gpt-3.5-turbo-instruct. So this is not a chat model, this is a completion model. So think of it more like, it's a lot more closer to a base model. It does completion. It will continue the token sequence.

[119:08] Andrej Karpathy: So here's a tagline for an ice cream shop, and we want to continue the sequence. And so we can submit and get a bunch of tokens. Okay, no problem. But now, suppose I do this, but instead of pressing submit here, I do, "Here's a tagline for an ice cream shop space." So I have a space here before I click submit. We get a warning. "Your text ends in a trailing space, which causes worse performance due to how the API splits text into tokens."

The OpenAI Playground showing a prompt that ends with a space. A yellow warning box appears below, stating: 'Warning: Your text ends in a trailing space, which causes worse performance due to how the API splits text into tokens.'

[119:37] Andrej Karpathy: So what's happening here? It still gave us a, uh, sort of completion here, but let's take a look at what's happening. So here's a tagline for an ice cream shop. And then what does this look like in the actual training data? Suppose you found the completion in the training document somewhere on the internet and the LLM trained on this data. So maybe it's something like, "Oh yeah." Maybe that's the completion.

The tiktokenizer web app showing the prompt 'Here is a tag line for an ice cream shop' without a trailing space. The token count is 11.

The Problem with Trailing Spaces and Partial Tokens

[120:00] Andrej Karpathy: terrible tagline. But notice here that when I create O, you see that because there's the the space character is always a prefix to these tokens in GPT. So it's not an O token, it's a space O token. The space is part of the O, and together they are token 8840. That's space O.

The Tiktokenizer web app showing the phrase 'Here is a tag line for an ice cream shop: Oh yeah' tokenized. The token for ' Oh' is highlighted, and its corresponding number, 8840, is shown below.

[120:21] Andrej Karpathy: So what's happening here is that when I just have it like this and I let it complete the next token, it can sample the space O token. But instead, if I have this and I add my space, then what I'm doing here when I encode this string is I have basically, here's a tagline for an ice cream, uh, shop, and this space at the very end becomes a token 220.

The Tiktokenizer web app showing the phrase 'Here is a tag line for an ice cream shop: ' with a trailing space. The resulting tokens are displayed below, with the final token, 220, corresponding to the space.

[120:44] Andrej Karpathy: And so we've added token 220, and this token otherwise would be part of the tagline because if there actually is a tagline here, so space O is a token. And so this is throwing out of distribution for the model because this space is part of the next token, but we're putting it here like this. And the model has seen very, very little data of actual space by itself. And we're asking it to complete the sequence, like add in more tokens. But the problem is that we've sort of begun the first token and now it's been split up and now we're out of distribution and now arbitrary bad things happen. And it's just a very rare example for it to see something like that. And, uh, that's why we get the warning.

[121:27] Andrej Karpathy: So the fundamental issue here is, of course, that, um, the LLM is on top of these tokens, and these tokens are text chunks, they're not characters in the way you and I would think of them. They are, these are the atoms of what the LLM is seeing, and there's a bunch of weird stuff that comes out of it. Let's go back to our, uh, default cell style. I bet you that the model has never in its training set seen default cell sty without le in there.

The Tiktokenizer web app showing the text '.DefaultCellSty' tokenized into four separate tokens: [13678, 3683, 626, 88].

[121:54] Andrej Karpathy: It's always seen this as a single group because, uh, this is some kind of a function in, um, I'm guess, I don't actually know what this is part of, it's some kind of API. But I bet you that it's never seen this combination of tokens, uh, in its training data because, or I think it would be extremely rare.

[122:12] Andrej Karpathy: So I took this and I copy-pasted it here, and I had, I tried to complete from it, and it immediately gave me a big error. And it said, the model predicted a completion that begins with a stop sequence, resulting in no output. Consider adjusting your prompt or stop sequences. So what happens here when I click submit is that immediately the model emitted an, sort of like end of text token, I think, or something like that. It basically predicted the stop sequence immediately, so it had no completion. And so this is where I'm getting a warning again because we're off the data distribution and the model is just, uh, predicting, it's totally arbitrary things. It's just really confused, basically. This is, this is giving it brain damage. It's never seen this before. It's shocked and it's predicting end of text or something.

The OpenAI Playground with the prompt '.DefaultCellSty' and an error message below: 'The model predicted a completion that begins with a stop sequence, resulting in no output.'

[122:55] Andrej Karpathy: I tried it again here, and it, in this case, it completed it, but then for some reason, this request may violate our usage policies. This was flagged. Um, basically something just like goes wrong, and this is like jank. You can just feel the jank because the model is like extremely unhappy with just this, and it doesn't know how to complete it because it's never occurred in the training set. In the training set, it always appears like this and becomes a single token.

The OpenAI Playground showing a completion for the prompt '.DefaultCellSty' along with a warning: 'This request may violate our usage policies. The request was flagged because it may violate our usage policies.'

[123:20] Andrej Karpathy: So these kinds of issues where tokens are either you sort of like complete the first character of the next token, or you are sort of, you have long tokens that you then have just some of the characters of, all of these are kind of like issues with partial tokens, is how I would describe it. And if you actually dig into the tiktoken repository, you go to the Rust code and search for unstable, and you'll see, um, encode unstable native, unstable tokens, and a lot of like special case handling. None of this stuff about unstable tokens is documented anywhere, but there's a ton of code dealing with unstable tokens. And unstable tokens is exactly kind of like what I'm describing here.

A screenshot of the tiktoken source code on GitHub, showing a search for the word 'unstable' which is highlighted in several places within the Rust code.

[124:02] Andrej Karpathy: What you would like out of a completion API is something a lot more fancy. Like if we're putting in default cell sty, if we're asking for the next token sequence, we're not actually trying to append the next token exactly after this list. We're actually trying to append, we're trying to consider lots of tokens, um, that if we were, or I guess like, we're trying to search over characters that if we re-tokenized would be of high probability, if that makes sense. Um, so that we can actually add a single individual character, uh, instead of just like adding the next full token that comes after this partial token list. So this is very tricky to describe, and I invite you to maybe like look through this. It ends up being an extremely gnarly and hairy kind of topic. It, and it comes from tokenization fundamentally. So, um, maybe I can even spend an entire video talking about unstable tokens sometime in the future.

The SolidGoldMagikarp Phenomenon

[124:53] Andrej Karpathy: Okay, and I'm really saving the best for last. My favorite one by far is this SolidGoldMagikarp.

A markdown file showing a list of questions about tokenization weirdness. The line 'Why did my LLM break if I ask it about 'SolidGoldMagikarp'?' is highlighted.

[125:00] Andrej Karpathy: It's just, okay, so this comes from this blog post, uh, SolidGoldMagikarp. And, uh, this is, um, internet famous now for those of us in LLMs. And basically, I, I would invite you to, uh, read this blog post in full. But basically what this person was doing is this person went to the, um, token embedding table and clustered the tokens based on their embedding representation. And this person noticed that there's a cluster of tokens that look really strange. So there's a cluster here, petertodd, StreamerBot, SolidGoldMagikarp, signupmessage, like really weird tokens in, uh, basically in this embedding cluster.

A screenshot from the LessWrong blog post showing a cluster of unusual tokens, including 'attRot', 'StreamerBot', 'SolidGoldMagikarp', and 'signupmessage'.

[125:41] Andrej Karpathy: And so where are these tokens and where do they even come from? Like what is SolidGoldMagikarp? It makes no sense. And then they found a bunch of these tokens. And then they noticed that actually the plot thickens here because if you ask the model about these tokens, like you ask it, uh, some very benign question like, please can you repeat back to me the string SolidGoldMagikarp? Uh, then you get a variety of basically totally broken LLM behavior. So either you get evasion, so, I'm sorry, I can't hear you, or you get a bunch of hallucinations as a response. Um, you can even get back like insults. So you ask it, uh, about StreamerBot and it, uh, tells the, and the model actually just calls you names. Uh, or it kind of comes up with like weird humor. But you're actually breaking the model by asking about these very simple strings like attRot and SolidGoldMagikarp.

A table from the LessWrong blog post categorizing the LLM's bizarre responses to weird tokens, with categories like 'evasion', 'hallucinatory completions', 'inter-referential hallucinations', and 'insults'.

[126:32] Andrej Karpathy: So like, what the hell is happening? And there's a variety of here documented behaviors. Uh, there's a bunch of tokens, not just SolidGoldMagikarp that have that kind of behavior. And so basically there's a bunch of like trigger words. And if you ask the model about these trigger words, or you just include them in your prompt, the model goes haywire and has all kinds of, uh, really strange behaviors, including sort of ones that violate typical safety guidelines, uh, and the alignment of the model, like it's swearing back at you. So what is happening here and how can this possibly be true?

A list of 141 'candidate 'weird' tokens' from the LessWrong blog post, including terms like 'externalToEVA', 'newcom', 'ReportAnIssue', 'SpaceEngineers', and 'SolidGoldMagikarp'.

[127:03] Andrej Karpathy: Well, this again comes down to tokenization. So what's happening here is that SolidGoldMagikarp, if you actually dig into it, is a Reddit user. So there's a u/SolidGoldMagikarp. And probably what happened here, even though I, I don't know that it has been like really definitively explored, but what is thought to have happened is that the tokenization dataset was very different from the training dataset for the actual language model. So in the tokenization dataset, there was a ton of Reddit data potentially, where the user SolidGoldMagikarp was mentioned in the text. Because SolidGoldMagikarp was a very common, um, sort of, uh, person who was posting a lot, uh, this would be a string that occurs many times in a tokenization dataset. Because it occurs many times in the tokenization dataset, these tokens would end up getting merged into a single individual token for that single Reddit user, SolidGoldMagikarp. So they would have a dedicated token in the vocabulary of, what is this, 50,000 tokens in GPT-2, that is devoted to that Reddit user.

[128:04] Andrej Karpathy: And then what happens is the tokenization dataset has those strings, but then later when you train the model, the language model itself, um, this data from Reddit was not present. And so therefore, in the entire training set for the language model, SolidGoldMagikarp never occurs. That token never appears in the training set for the actual language model later. So this token never gets activated. It's initialized at random in the beginning of optimization. Then you have forward backward passes and updates to the model, and this token is just never updated in the embedding table. That row vector never gets sampled, it never gets used, so it never gets trained. It's completely untrained. It's kind of like unallocated memory in a typical binary program written in C or something like that. So it's unallocated memory. And then at test time, if you evoke this token, then you're basically plucking out a row of the embedding table that is completely untrained, and that feeds into a transformer and creates undefined behavior. And that's what we're seeing here. This is completely undefined, never before seen in the training behavior. And so any of these kind of like weird tokens would evoke this behavior because fundamentally the model is, um, is, uh, out of sample, out of distribution.

Token Efficiency: YAML vs. JSON

[129:16] Andrej Karpathy: Okay, and the very last thing I wanted to just briefly mention and point out, although I think a lot of people are quite aware of this, is that different kinds of formats and different representations and different languages and so on might be more or less efficient with GPT tokenizers, uh, or any tokenizer for any other LLM for that matter. So for example, JSON is actually really dense in tokens, and YAML is a lot more efficient in tokens.

The Tiktokenizer web app showing a JSON object on the left and its tokenized representation on the right, with a total token count of 214.

[129:38] Andrej Karpathy: Um, so for example, this, our, these are the same in JSON and in YAML. The JSON is 116 and the YAML is 99. So quite a bit of an improvement. And so in the token economy where you are paying, uh, per token in many ways, and you are paying in the context length and you're paying in, um, dollar amount for, uh, the cost of processing all this kind of structured data when you have to, uh, so prefer to use YAML over JSONs. And in general, kind of like the tokenization density is something that you have to, uh, sort of care about and worry about at all times and try to find efficient encoding schemes and spend a lot of time in Tiktokenizer and measure the different token efficiencies of different formats and settings and so on.

The Tiktokenizer web app showing a YAML object on the left and its tokenized representation on the right, with a total token count of 99.

Final Recommendations

[130:20] Andrej Karpathy: Okay, so that concludes my fairly long video on tokenization. I know it's dry, I know it's annoying, I know it's irritating. I personally really dislike this stage. But what I do have to say at this point is don't brush it off. There's a lot of footguns, sharp edges here, security issues, uh, AI safety issues, as we saw with plugging in unallocated memory into, uh, language models. So, um, it's worth understanding this stage. Um, that said, I will say that eternal glory goes to anyone who can get rid of it. Uh, I showed you one possible paper that tried to, uh, do that, and I think, I hope a lot more can follow over time.

A slide titled 'Final recommendations' with bullet points: 'Don't brush off tokenization. A lot of footguns and sharp edges here. Security issues. Safety issues.', 'Eternal glory to anyone who can delete tokenization as a required step in LLMs.', and others.

[130:58] Andrej Karpathy: And my final recommendations for the application right now are, if you can reuse the GPT-4 tokens and the vocabulary, uh, in your application, then that's something you should consider and just use tiktoken because it is a very efficient and nice, uh, library for inference for BPE. I also really like the byte-level BPE that, uh, tiktoken and OpenAI uses. Uh, if you for some reason want to train your own vocabulary from scratch, um, then I would use, uh, the BPE with sentencepiece. And as I mentioned, I'm not a huge fan of sentencepiece. I don't like its, uh, byte fallback, and I don't like that it's doing BPE on Unicode code points. I think it's, uh, it also has like a million settings, and I think there's a lot of footguns here, and I think it's really easy to miscalculate them, and you end up cropping your sentences or something like that, uh, because of some parameter that you don't fully understand. So be very careful with the settings. Try to copy-paste exactly maybe what Meta did or basically spend a lot of time looking at all the hyperparameters and go through the code of sentencepiece and make sure that you have this correct.

[132:01] Andrej Karpathy: Um, but even if you have all the settings correct, I still think that the algorithm is kind of inferior to what's happening here. And maybe the best is if you really need to train your vocabulary, maybe the best thing is to just wait for minbpe to become as efficient as possible. And, uh, that's something that I maybe I hope to work on. And at some point, maybe we can be training basically, really what we want is we want tiktoken but training code. And that is the ideal thing that currently does not exist. And minbpe is, um, is an implementation of it, but currently it's in Python. So that's currently what I have to say for, uh, tokenization. There might be an advanced video that is even drier and even more detailed in the future. But for now, I think we're going to leave things off here and, uh, I hope that was helpful. Bye.

[132:53] Andrej Karpathy: And, uh, they increased this context size from GPT-1 of 512, uh, to 1,024 in GPT-4. Two.

[133:03] Andrej Karpathy: The next one, blah.

[133:06] Andrej Karpathy: Okay, next, I would like us to briefly walk through the code for OpenAI on the GPT-2 encoder.py. I'm sorry, I'm going to sneeze.

[133:19] Andrej Karpathy: And then what's happening here is this is a spurious layer that I will explain in a bit. What's happening here is...

Start Transcript Enrichment

Can you please identify the relevant github repos mentioned in the transcript?

gh_url = f"https://{os.environ['GITHUB_TOKEN']}@github.com/karpathy/minbpe.git"

# !git clone {gh_url}

!cd minbpe && git status 

def read_text(filename:str):
    'Read a text file'
    return Path(filename).read_text()

&read_text - a tool to read text files such as code files

import subprocess, shlex
def run_cmd(cmd: str, timeout=30):
    "Run a bash command and return stdout, stderr, and return code"
    try:
        add_msg(f"Running: {cmd}")
        result = subprocess.run(shlex.split(cmd), capture_output=True, text=True, timeout=timeout)
        return dict(stdout=result.stdout, stderr=result.stderr, returncode=result.returncode)
    except subprocess.TimeoutExpired: return dict(error=f'Command timed out after {timeout}s')
    except Exception as e: return dict(error=str(e))

&run_cmd - run any bash command, including ripgrep rg

def tagify(tag, text, with_newlines=True): 
    'Creates an xml with tag, used in prompts'
    if with_newlines: text = '\n' + text + '\n'
    return to_xml(ft(tag,text), do_escape=False)

def _create_strs_replace_err_msg(old_strs, new_strs, idx, exception, text):
    
    err_msg = f"""Tool call to `strs_replace` was interrupted with the following error:
        
{tagify('error', str(exception))}"""
    if idx == 0: return err_msg
    return err_msg + f"""

Here are the succesful replacements made:

{_successful_replacements(old_strs, new_strs, idx)}

Here is most up-to-date version of the text that's being replaced by `strs_replace`: 

{tagify('text', text)}"""

def str_replace(text, old_str:str, new_str:str):
    "Replace first occurrence of old_str with new_str in file"
    count = text.count(old_str)        
    if count == 0: raise Exception(f"Error: Text not found in file: {repr(old_str)}")
    if count > 1:  raise Exception(f"Error: Multiple matches found ({count}) for text: {repr(old_str)}")
    return text.replace(old_str, new_str, 1)   

def update_msg_with_strs_replace(msgid:str,  # Message id to find (defaults to current message)
                                 old_strs:list[str], # List of old strings that will be replaced
                                 new_strs:list[str]  # List of new strings that will replace the old in the same order
                ):
    "Replace each string in `old_strs` list with their coresspoding pair in `old_strs` list. A much more efficient `update_msg`"
    if not isinstance(old_strs, list): return f"`old_strs` should be a list[str] but instead is a {type(old_strs)}"
    if not isinstance(new_strs, list): return f"`new_strs` should be a list[str] but instead is a {type(new_strs)}"
    content = read_msg(msgid=msgid, n=0)['content']
    for idx, (old,new) in enumerate(zip(old_strs,new_strs)):            
        try: content = str_replace(content, old, new)
        except Exception as e: return _create_strs_replace_err_msg(old_strs, new_strs, idx, e, content)   
    return update_msg(msgid, content=content)

from dialoghelper import *

tool_info()

&update_msg_with_strs_replace - a more efficient update_msg function which use list of string replacement pairs.

We will work on the transcript in small pieces and enrich it using multiple different approaches such as removing images, adding hyperlinks, adding/extracting code snippets, asking AI to write example code, etc...

def split_tscript_as_msgs(dst, yt_video_id=None):
    tscript_md = tscript_with_imgs(scribe_dst, False)
    if yt_video_id: tscript_md = tscript_add_yt_links(tscript_md, yt_video_id)
    sidx, chunks = 0, []
    lines = tscript_md.splitlines()
    for idx, l in enumerate(lines):
        if l.startswith('!['):
            chunks.append('\n\n'.join(lines[sidx:idx+2])) # include alt text
            sidx = idx+2
    for c in chunks[::-1]: add_msg(c)

Part 1:

Introduction to Tokenization

[00:00] Andrej Karpathy: Hi everyone. So in this video, I'd like us to cover the process of tokenization in large language models. Now, you see here that I have a sad face, and that's because, well, tokenization is my least favorite part of working with large language models. But unfortunately, it is necessary to understand in some detail because it is fairly hairy, gnarly, and there are a lot of hidden foot guns to be aware of. And a lot of oddness with large language models typically traces back to tokenization.

[00:25] Andrej Karpathy: So what is tokenization? Now, in my previous video, "Let's build GPT from scratch," we actually already did tokenization, but we did a very naive, simple version of tokenization.

Can you please find the link to this YT video and add it as a hyperlink to the above msg?

[00:36] Andrej Karpathy: So when you go to the Google Colab for that video, you see here that we loaded our training set. And our training set was this Shakespeare dataset. Now in the beginning, the Shakespeare dataset is just a large string in Python. It's just text. And so the question is, how do we plug text into large language models?

[00:57] Andrej Karpathy: And in this case here, we created a vocabulary of 65 possible characters that we saw occur in this string. These were the possible characters, and we saw that there are 65 of them. And then we created a lookup table for converting from every possible character, a little string piece, into a token, an integer.

[01:18] Andrej Karpathy: So here, for example, we tokenized the string "hi there" and we received this sequence of tokens. And here we took the first 1,000 characters of our dataset and we encoded it into tokens. And because this is character level, we received 1,000 tokens in a sequence. So token 18, 47, etc.

Can you please extract the relevant code from the above image that Andrej refers in the transcript above, and add it as a note msg below with code fences

text = 'a dummy text'
# get the unique characters that occur in this text
chars = sorted(list(set(text)))
vocab_size = len(chars)
print(''.join(chars))
# Output:  !,Tadehilmnorstwx
print(vocab_size)
# Output: 18

# create a mapping from characters to integers
stoi = { ch:i for i,ch in enumerate(chars) }
itos = { i:ch for i,ch in enumerate(chars) }
encode = lambda s: [stoi[c] for c in s] # encoder: take a string, output a list of integers
decode = lambda l: ''.join([itos[i] for i in l]) # decoder: take a list of integers, output a string

print(encode("hii there"))
# Output: [7, 8, 8, 0, 15, 7, 6, 13, 6]
print(decode(encode("hii there")))
# Output: hii there

# let's now encode the entire text dataset and store it into a torch.Tensor
data = torch.tensor(encode(text), dtype=torch.long)
print(data.shape, data.dtype)
# Output: torch.Size([51]) torch.int64
print(data[:1000]) # the first 1000 characters we'll look like this
# Output: tensor([ 3,  7,  8, 14,  0,  8, 14,  0, 14, 12, 10,  6,  0, 15,  7,  6, 17, 15,  0,
#          5,  4, 15,  4, 14,  6, 15,  0,  7,  6,  9,  9, 12,  2,  0,  4, 11,  5,
#          0,  7,  8,  0, 14, 12, 10,  6,  0, 16, 12, 13,  5, 14,  1])

Please insert these outputs after their print() statement to the note message that has the fenced code

Now that we've extracted the code snippet, I have deleted the image and we will use the code snippet in our final doc instead

[01:41] Andrej Karpathy: Now, later we saw that the way we plug these tokens into the language model is by using an embedding table. And so basically, if we have 65 possible tokens, then this embedding table is going to have 65 rows. And roughly speaking, we're taking the integer associated with every single token, we're using that as a lookup into this table, and we're plucking out the corresponding row. And this row is a, uh, is trainable parameters that we're going to train using backpropagation. And this is the vector that then feeds into the transformer, um, and that's how the transformer sort of perceives every single token.

[02:19] Andrej Karpathy: So here we had a very naive tokenization process that was a character-level tokenizer. But in practice, state-of-the-art, uh, language models, people use a lot more complicated schemes, unfortunately, for, uh, constructing these, uh, token vocabularies. So we're not dealing on a character level, we're dealing on a chunk level. And the way these, um, character chunks are constructed is using algorithms such as, for example, the byte-pair encoding algorithm, which we're going to go into in detail, um, and cover in this video.

Tokenization in GPT-2 and Llama 2

[02:52] Andrej Karpathy: I'd like to briefly show you the paper that introduced byte-level encoding as a mechanism for tokenization in the context of large language models. And I would say that that's probably the GPT-2 paper. And if you scroll down here to the section "Input Representation," this is where they cover tokenization, the kind of properties that you'd like the tokenization to have. And they conclude here that they're going to have a tokenizer where you have a vocabulary of 50,257 possible tokens. And the context size is going to be 1,024 tokens. So in the, in the attention layer of the transformer neural network, every single token is attending to the previous tokens in the sequence, and it's going to see up to 1,024 tokens. So tokens are this fundamental unit, um, the atom of, uh, large language models, if you will. And everything is in units of tokens, everything is about tokens. And tokenization is the process for translating strings or text into sequences of tokens and, uh, vice versa.

Please find a link to this paper in arxiv and add it as a hyperlink to above message.

[03:55] Andrej Karpathy: When you go into the Llama 2 paper as well, I can show you that when you search "token," you're going to get 63 hits. Um, and that's because tokens are, again, pervasive. So here they mentioned that they trained on 2 trillion tokens of data and so on. So we're going to build our own tokenizer. Luckily, the byte-pair encoding algorithm is not, um, that super complicated, and we can build it from scratch ourselves and we'll see exactly how this works.

Please add a hyperlink for this paper too.

The Weirdness of Tokenization

[04:20] Andrej Karpathy: Before we dive into code, I'd like to give you a brief taste of some of the complexities that come from the tokenization because I just want to make sure that we've motivated it sufficiently for why we are doing all this and why this is so gross. So, tokenization is at the heart of a lot of weirdness in large language models, and I would advise that you do not brush it off. A lot of the issues that may look like just issues with the neural architecture or the large language model itself are actually issues with the tokenization and fundamentally trace back to it.

[04:50] Andrej Karpathy: So, if you've noticed any issues with large language models can't, you know, not able to do spelling tasks very easily, that's usually due to tokenization. Simple string processing can be difficult for the large language model to perform natively. Uh, non-English languages can work much worse, and to a large extent, this is due to tokenization. Sometimes LLMs are bad at simple arithmetic, also can trace be traced to tokenization. Uh, GPT-2 specifically would have had quite a bit more issues with Python than, uh, future versions of it due to tokenization. There's a lot of other issues. Maybe you've seen weird warnings about a trailing whitespace. This is a tokenization issue. Um, if you had asked GPT earlier about "SolidGoldMagikarp" and what it is, you would see the LLM go totally crazy and it would start going off about completely unrelated tangent topic. Maybe you've been told to use YAML over JSON with structured data. All that has to do with tokenization. So basically, tokenization is at the heart of many issues.

This looks like a nice list of weirdness! Can we extract this as a note message from the image above?

Tokenization Issues in LLMs

Based on Andrej Karpathy's analysis, here are the key issues caused by tokenization:

• Why can't LLM spell words? Tokenization.

• Why can't LLM do string processing tasks like reversing a string? Tokenization.

• Why is LLM bad at non-English languages (especially ones with different scripts)? Tokenization.

• Why is LLM bad at simple arithmetic? Tokenization.

• Why did GPT-2 have more than necessary trouble coding in Python? Tokenization.

• Why did my LLM abruptly halt when it sees the string "<|endoftext|>"? Tokenization.

• Why should I prefer YAML over JSON with LLMs? Tokenization.

• Why is LLM not actually end-to-end language modeling? Tokenization.

• Why should I prefer to use f-strings instead of .format(...)? Tokenization.

• Why is LLM worse at tasks in JSON compared to YAML? Tokenization.

• Why should LLMs not be used for password generation? Tokenization.

• What is the root of suffering? Tokenization.

[05:50] Andrej Karpathy: I will loop back around to these at the end of the video, but for now, let me just, um, skip over it a little bit. And let's go to this web app, um, the tiktokenizer that vercel.app. So I have it loaded here. And what I like about this web app is that tokenization is running sort of live in your browser in JavaScript. So you can just type here stuff, "hello world," and the whole string re-tokenizes.

A web application called 'Tiktokenizer'. The left pane is a text editor, and the right pane shows the tokenized output. The text includes examples of English, arithmetic, Korean, and Python code.

Please add a link to this web app

I am keeping this image and using its cropped version which looks pretty good, if it wasn't we could've just kept the original version

[06:15] Andrej Karpathy: So, here what we see on the left is the string that you put in. On the right, we're currently using the GPT-2 tokenizer. We see that this string that I pasted here is currently tokenizing into 300 tokens. And here they are sort of, uh, shown explicitly in different colors for every single token. So for example, uh, this word "Tokenization" became two tokens, the token 30,642 and 1,634. The token " is" is token 318. Be careful, on the bottom you can show whitespace, and keep in mind that there are spaces and, uh, slash n, new line characters in here, but you can hide them for clarity. The token " at" is token 379. The token " the" is 262, etc. So you notice here that the space is part of that, uh, token chunk.

[07:16] Andrej Karpathy: Now, so this is kind of like how our English sentence broke up, and that seems all well and good. Now, now here I put in some arithmetic. So we see that, uh, the token 127 plus and then token 6, space 6, followed by 77. So what's happening here is that 127 is feeding in as a single token into the large language model, but the, um, number 677 will actually feed in as two separate tokens. And so the large language model has to, uh, sort of, um, take account of that and process it correctly in its network. And see here, 804 will be broken up into two tokens. And it's all completely arbitrary. And here I have another example of four-digit numbers, and they break up in a way that they break up, and it's totally arbitrary. Sometimes you have, um, multiple digits, a single token. Sometimes you have individual digits as many tokens, and it's all kind of pretty arbitrary and comes out of the tokenizer.

[08:15] Andrej Karpathy: Here's another example. We have the string "Egg." And you see here that this became two tokens. But for some reason when I say, "I have an egg," you see when it's a " an egg," it's two tokens, it's, sorry, it's a single token. So just "Egg" by itself in the beginning of a sentence is two tokens, but here as a " an egg" it's suddenly a single token for the exact same string. Okay? Here, lowercase "egg" turns out to be a single token, and in particular, notice that the color is different, so this is a different token. So this is case sensitive. And of course, uh, capital "EGG" would also be different tokens, and again, um, this would be two tokens arbitrarily. So for the same concept, "egg," depending on if it's in the beginning of a sentence, at the end of a sentence, lowercase, uppercase, or mixed, all this will be, uh, basically very different tokens and different IDs. And the language model has to learn from raw data from all the internet text that it's being trained on that these are actually all the exact same concept. And it has to sort of group them in the parameters of the neural network and understand just based on the data patterns that these are all very similar, but maybe not almost exactly similar, but very, very similar.

[09:30] Andrej Karpathy: Um, after the egg demonstration here, I have, um, an introduction from OpenAI's ChatGPT in Korean. So, "mannaseo bangawoyo," uh, etc. Uh, so this is in Korean. And the reason I put this here is because you'll notice that, um, non-English languages work slightly worse in ChatGPT. Part of this is because, of course, the training dataset for ChatGPT is much larger for English than for everything else. But the same is true not just for the large language model itself, but also for the tokenizer. So when we train the tokenizer, we're going to see that there's a training set as well. And there's a lot more English than non-English. And what ends up happening is that we're going to have a lot more longer tokens for English.

[10:17] Andrej Karpathy: So, how do I put this? If you have a single sentence in English and you tokenize it, you might see that it's 10 tokens or something like that. But if you translate that sentence into, say, Korean or Japanese or something else, you'll typically see that the number of tokens used is much larger. And that's because the chunks here are a lot more broken up. Uh, so we're using a lot more tokens for the exact same thing. And what this does is it bloats up the sequence length of all the documents. So you're using up more tokens, and then in the attention of the transformer, when these tokens try to attend each other, you are running out of context, um, in the maximum context length of that transformer. And so basically, all the non-English text is stretched out from the perspective of the transformer, and this just has to do with the, um, training set used for the tokenizer and the tokenization itself. So it will create a lot bigger tokens and a lot larger groups in English, and it will have a lot of little boundaries for all the other non-English text. So if we translated this into English, it would be significantly fewer tokens.

[11:24] Andrej Karpathy: The final example I have here is a little snippet of Python for doing FizzBuzz. And what I'd like you to notice is, look, all these individual spaces are all separate tokens. They are token 220. So, uh, 220, 220, 220, 220, and then " if" is a single token. And so what's going on here is that when the transformer is going to consume or try to, uh, create this text, it needs to, um, handle all these spaces individually. They all feed in one by one into the entire transformer in the sequence. And so this is being extremely wasteful, tokenizing it in this way. And so, as a result of that, GPT-2 is not very good with Python. And it's not anything to do with coding or the language model itself, it's just that if you use a lot of indentation using space in Python, like you usually do, uh, you just end up bloating out all the text, and it's separated across way too much of the sequence, and we are running out of the context length in the sequence, uh, roughly speaking, what's what's happening. We're being way too wasteful. We're taking up way too much token space.

Improving Tokenization: GPT-2 vs. GPT-4

[12:29] Andrej Karpathy: Now, if we also scroll up here, we can change the tokenizer. So note here that GPT-2 tokenizer creates a token count of 300 for this string here. We can change it to cl100k_base, which is the GPT-4 tokenizer. And we see that the token count drops to 185. So for the exact same string, we are now roughly halving the number of tokens. And roughly speaking, this is because, uh, the number of tokens in the GPT-4 tokenizer is roughly double that of the number of tokens in the GPT-2 tokenizer. So we went from roughly 50k to roughly 100k.

[13:01] Andrej Karpathy: Now, you can imagine that this is a good thing because the same text is now squished into half as many tokens. So, uh, this is a lot denser input to the transformer. And in the transformer, every single token has a finite number of tokens before it that it's going to pay attention to. And so what this is doing is we're roughly able to see twice as much text as a context for what token to predict next, uh, because of this change. But of course, just increasing the number of tokens is, uh, not strictly better infinitely, uh, because as you increase the number of tokens, now your embedding table is, uh, sort of getting a lot larger. And also at the output, we are trying to predict the next token, and there's the softmax there, and that grows as well. We're going to go into more detail later on this, but there's some kind of a sweet spot somewhere where you have a just right number of tokens in your vocabulary where everything is appropriately dense and still fairly efficient.

[13:57] Andrej Karpathy: Now, one thing I would like you to note specifically for the GPT-4 tokenizer is that the handling of the whitespace for Python has improved a lot. You see that here, these four spaces are represented as one single token for the three spaces here, and then the token " if." And here, seven spaces were all grouped into a single token. So we're being a lot more efficient in how we represent Python. And this was a deliberate choice made by OpenAI when they designed the GPT-4 tokenizer. And they group a lot more whitespace into a single character. What this does is it densifies Python, and therefore, we can attend to more code before it when we're trying to predict the next token in the sequence. And so the improvement in the Python coding ability from GPT-2 to GPT-4 is not just a matter of the language model and the architecture and the details of the optimization, but a lot of the improvement here is also coming from the design of the tokenizer and how it groups characters into tokens.

The Tiktokenizer web app showing a Python FizzBuzz code snippet. The tokenizer is set to 'cl100k_base' (GPT-4). The indentation spaces are grouped into single, larger tokens, unlike the GPT-2 tokenizer.

From Strings to Integers: Unicode and Encodings

[14:56] Andrej Karpathy: Okay, so let's now start writing some code. So, remember what we want to do. We want to take strings and feed them into language models. For that, we need to somehow tokenize strings into some integers in some fixed vocabulary. And then we will use those integers to make a lookup into a lookup table of vectors and feed those vectors into the transformer as an input.

[15:20] Andrej Karpathy: Now, the reason this gets a little bit tricky, of course, is that we don't just want to support the simple English alphabet. We want to support different kinds of languages. So this is "annyeonghaseyo" in Korean, which is hello. And we also want to support many kinds of special characters that we might find on the internet, for example, emoji. So, how do we feed this text into, uh, transformers?

Extract this notebook cell in the image as a note message

text = "안녕하세요 👋 hello world 🤗"
print(text)
# Output: 안녕하세요 👋 hello world 🤗

[15:43] Andrej Karpathy: Well, what is this text anyway in Python? So if you go to the documentation of a string in Python, you can see that strings are immutable sequences of Unicode code points. Okay, what are Unicode code points? We can go to Wikipedia Unicode page. So Unicode code points are defined by the Unicode Consortium as part of the Unicode standard. And what this is really is that it's just a definition of roughly 150,000 characters right now. And roughly speaking, what they look like and what integers, um, represent those characters. So this is 150,000 characters across 161 scripts as of right now. So if you scroll down here, you can see that the standard is very much alive. The latest standard 15.1 is September 2023.

Please add a hyperlink to this wiki page

please extract the first paragraph as a quoted note message

Unicode, formally The Unicode Standard, is a text encoding standard maintained by the Unicode Consortium designed to support the use of text written in all of the world's major writing systems. Version 15.1 of the standard defines 149,813 characters and 161 scripts used in various ordinary, literary, academic, and technical contexts.

[16:31] Andrej Karpathy: And basically, this is just a way to define lots of types of characters, like for example, all these characters across different scripts. So, the way we can access the Unicode code point given a single character is by using the ord function in Python. So for example, I can pass in ord of 'h', and I can see that for the single character 'h', the Unicode code point is 104. Okay? Um, but this can be arbitrarily complicated. So we can take, for example, our emoji here, and we can see that the code point for this one is 128,000. Or we can take "an," and this is 50,000. Now, keep in mind, you can't plug in strings here because, uh, this doesn't have a single code point. It only takes a single Unicode code point character and tells you its integer.

Please create code for section that Andrej talks about above

# Get Unicode code point for English character
print(f"ord('h') = {ord('h')}")

# Get Unicode code point for emoji
print(f"ord('🤗') = {ord('🤗')}")

# Get Unicode code point for Korean character
print(f"ord('안') = {ord('안')}")

Add hyperlink to built-in python functions/modules mentioned above in the transcript

Actually also add the docstring from that documentation page as a quoted note msg.

ord(character, /)

Return the ordinal value of a character.

If the argument is a one-character string, return the Unicode code point of that character. For example, ord('a') returns the integer 97 and ord('€') (Euro sign) returns 8364. This is the inverse of chr().

If the argument is a bytes or bytearray object of length 1, return its single byte value. For example, ord(b'a') returns the integer 97.

[17:24] Andrej Karpathy: So in this way, we can look up all the, um, characters of this specific string and their code points. So ord(x) for x in this string, and we get this encoding here. Now, see here, we've already turned, the raw code points already have integers. So why can't we simply just use these integers and not have any tokenization at all? Why can't we just use this natively as is and just use the code point?

Extract his example in the above image as code msg

# Get Unicode code points for each character in the string
text = "안녕하세요 👋 hello world 🤗"
L([ord(x) for x in text])

[17:52] Andrej Karpathy: Well, one reason for that, of course, is that the vocabulary in that case would be quite long. So in this case, for Unicode, this is a vocabulary of 150,000 different code points. But more worryingly than that, I think, the Unicode standard is very much alive and it keeps changing. And so it's not kind of a stable representation necessarily that we may want to use directly. So for these reasons, we need something a bit better.

[18:16] Andrej Karpathy: So to find something better, we turn to encodings. So if you go to the Wikipedia page here, we see that the Unicode Consortium defines three types of encodings: UTF-8, UTF-16, and UTF-32. These encodings are the way by which we can take Unicode text and translate it into binary data or byte strings. UTF-8 is by far the most common. So this is the UTF-8 page. Now, this Wikipedia page is actually quite long, but what's important for our purposes is that UTF-8 takes every single code point and it translates it to a byte string. And this byte string is between one to four bytes. So it's a variable-length encoding. So depending on the Unicode point, according to the schema, you're going to end up with between one to four bytes for each code point.

A screenshot of the Wikipedia page for UTF-8, showing a table that maps Unicode code point ranges to their corresponding byte-length representation in UTF-8 (1, 2, 3, or 4 bytes).

[19:02] Andrej Karpathy: On top of that, there's UTF-8, uh, UTF-16, and UTF-32. UTF-32 is nice because it is fixed length instead of variable length, but it has many other downsides as well. So the full kind of spectrum of pros and cons of all these different three encodings are beyond the scope of this video. I'd just like to point out that I enjoyed this blog post, and this blog post at the end of it also has a number of references that can be quite useful. Uh, one of them is "UTF-8 Everywhere Manifesto." Um, and this manifesto describes the reason why UTF-8 is significantly preferred and a lot nicer than the other encodings and why it is used a lot more prominently, um, on the internet. One of the major advantages that's just to give you a sense is that UTF-8 is the only one of these that is backward compatible to the much simpler ASCII encoding of text. Um, but I'm not going to go into the full detail in this video. So suffice to say,

Introduction to UTF-8 Encoding

[20:00] Speaker A: Suffice it to say that we like the UTF-8 encoding. And, uh, let's try to take this string and see what we get if we encode it into UTF-8.

Can you add hyperlink to the blogs posts mentioned above

[20:08] Speaker A: The string class in Python actually has .encode, and you can give it the encoding, which is, let's say, UTF-8. Now, what we get out of this is not very nice because this is the bytes, this is a bytes object, and it's not very nice in the way that it's printed. So I personally like to take it through a list because then we actually get the raw bytes of this, uh, encoding.

[20:31] Speaker A: So this is the raw bytes that represent this string according to the UTF-8 encoding.

Comparing UTF-8, UTF-16, and UTF-32

[20:37] Speaker A: We can also look at UTF-16. We get a slightly different byte stream. And here we start to see one of the disadvantages of UTF-16. You see how we have zero, zero something, zero something, zero something. We're starting to get a sense that this is a bit of a wasteful encoding. And indeed, for simple ASCII characters or English characters here, uh, we just have this structure of zero something, zero something, and it's not exactly nice.

[21:02] Speaker A: Same for UTF-32. When we expand this, we can start to get a sense of the wastefulness of this encoding for our purposes. You see a lot of zeros followed by something. And so, uh, this is not desirable.

Can you please add minimal code examples for UTF comparisons mentioned above.

text = "안녕하세요 👋 hello world 🤗"

# UTF-8 encoding
utf8_bytes = list(text.encode('utf-8'))
print(f"UTF-8: {utf8_bytes}")

# UTF-16 encoding  
utf16_bytes = list(text.encode('utf-16'))
print(f"UTF-16: {utf16_bytes}")

# UTF-32 encoding  
utf32_bytes = list(text.encode('utf-32'))
print(f"UTF-32: {utf32_bytes}")

[21:16] Speaker A: So, suffice it to say that we would like to stick with UTF-8 for our purposes. However, if we just use UTF-8 naively, these are byte streams. So that would imply a vocabulary length of only 256 possible tokens. Uh, but this, this vocabulary size is very, very small. What this is going to do if we just were to use it naively is that all of our text would be stretched out over very, very long sequences of bytes.

[21:44] Speaker A: And so, um, what what this does is that certainly the embedding table is going to be tiny, and the prediction at the top at the final layer is going to be very tiny, but our sequences are very long. And remember that we have pretty finite, um, context length in the attention that we can support in a transformer for computational reasons. And so we only have that much context length, but now we have very, very long sequences, and this is just inefficient, and it's not going to allow us to attend to sufficiently long text, uh, before us for the purposes of the next token prediction task.

[22:18] Speaker A: So we don't want to use the raw bytes of the UTF-8 encoding. We want to be able to support larger vocabulary size that we can tune as a hyperparameter, but we want to stick with the UTF-8 encoding of these strings. So what do we do?

Introducing Byte Pair Encoding (BPE)

[22:34] Speaker A: Well, the answer, of course, is we turn to the Byte Pair Encoding algorithm, which will allow us to compress these byte sequences, um, to a variable amount. So we'll get to that in a bit, but I just want to briefly speak to the fact that I would love nothing more than to be able to feed raw byte sequences into, uh, language models. In fact, there's a paper about how this could potentially be done, uh, from the summer last year.

[22:58] Speaker A: Now, the problem is you have to go in and you have to modify the transformer architecture because, as I mentioned, you're going to have a problem where the attention will start to become extremely expensive because the sequences are so long. And so in this paper, they propose kind of a hierarchical structuring of the transformer that could allow you to just feed in raw bytes. And so at the end, they say, "Together, these results establish the viability of tokenization-free autoregressive sequence modeling at scale." So tokenization-free would indeed be amazing. We would just feed byte streams directly into our models. But unfortunately, I don't know that this has really been proven out yet by sufficiently many groups at sufficient scale. Uh, but something like this at one point would be amazing, and I hope someone comes up with it. But for now, we have to come back, and we can't feed this directly into language models, and we have to compress it using the Byte Pair Encoding algorithm. So let's see how that works.

MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers

add an hyperlink for the MEGABYTE paper

How Byte Pair Encoding Works

[23:50] Speaker A: So as I mentioned, the Byte Pair Encoding algorithm is not all that complicated, and the Wikipedia page is actually quite instructive as far as the basic idea goes. What we're doing is we have some kind of an input sequence. Uh, like, for example, here we have only four elements in our vocabulary: a, b, c, and d. And we have a sequence of them. So instead of bytes, let's say we just have four, a vocab size of four.

[24:12] Speaker A: This sequence is too long, and we'd like to compress it. So what we do is that we iteratively find the pair of, uh, tokens that occur the most frequently. And then once we've identified that pair, we replace that pair with just a single new token that we append to our vocabulary. So for example, here, the byte pair 'aa' occurs most often. So we mint a new token, let's call it capital Z, and we replace every single occurrence of 'aa' by Z. So now we have two Z's here.

[24:47] Speaker A: So here, we took a sequence of 11 characters with vocabulary size four, and we've converted this to a, um, sequence of only nine tokens, but now with a vocabulary of five, because we have a fifth vocabulary element that we just created, and it's Z, standing for concatenation of 'aa'. And we can again repeat this process. So we again look at the sequence and identify the, uh, pair of tokens that are most frequent. Let's say that that is now 'ab'. Well, we are going to replace 'ab' with a new token that we mint, called Y. So Y becomes 'ab', and then every single occurrence of 'ab' is now replaced with Y. So we end up with this.

[25:30] Speaker A: So now we only have 1, 2, 3, 4, 5, 6, 7 characters in our sequence, but we have not just, um, four vocabulary elements, or five, but now we have six. And for the final round, we again look through the sequence, find that the phrase 'ZY' or the pair 'ZY' is most common, and replace it one more time with another, um, character, let's say X. So X is 'ZY', and we replace all occurrences of 'ZY', and we get this following sequence.

[26:02] Speaker A: So basically, after we've gone through this process, instead of having a, um, sequence of 11, uh, tokens with a vocabulary length of four, we now have a sequence of 1, 2, 3, 4, 5 tokens, but our vocabulary length now is seven. And so in this way, we can iteratively compress our sequence as we mint new tokens. So in the exact same way, we start, we start off with byte sequences, so we have 256 vocabulary size, but we're now going to go through these and find the byte pairs that occur the most, and we're going to iteratively start minting new tokens, appending them to our vocabulary, and replacing things. And in this way, we're going to end up with a compressed training dataset and also an algorithm for taking any arbitrary sequence and encoding it using this, uh, vocabulary, and also decoding it back to strings. So let's now implement all that.

Please add a hyperlink to BPE wiki page

add the examples in the wiki page as a note msg

Step 1: Initial sequence

aaabdaaabac

Most frequent pair: aa (occurs 2 times) Replace aa with Z:

Zabdaabac → ZabdZabac

Step 2: Continue compression

ZabdZabac

Most frequent pair: ab (occurs 2 times)
Replace ab with Y:

ZYdZYac

Step 3: Final merge

ZYdZYac

Most frequent pair: ZY (occurs 2 times) Replace ZY with X:

XdXac

Final result: XdXac

Final vocabulary: {a, b, c, d, Z=aa, Y=ab, X=ZY} Original length: 11 tokens → Compressed length: 5 tokens

You forgot the final merge ZY please update the note msg

[27:03] Speaker A: So here's what I did. I went to this blog post that I enjoyed, and I took the first paragraph, and I copy-pasted it here into text. So this is one very long line here.

add hyperlink to the blog post

[27:14] Speaker A: Now, to get the tokens, as I mentioned, we just take our text and we encode it into UTF-8. The tokens here at this point will be our raw bytes, single stream of bytes. And just so that it's easier to work with, instead of just a bytes object, I'm going to convert all those bytes to integers and then create a list of it, just so it's easier for us to manipulate and work with in Python and visualize. And here I'm printing all of that. So this is the original, um, this is the original paragraph, and its length is 533, uh, code points. And then here are the bytes encoded in UTF-8, and we see that this has a length of 616 bytes at this point, or 616 tokens. And the reason this is more is because a lot of these simple ASCII characters or simple characters, they just become a single byte, but a lot of these Unicode, more complex characters become multiple bytes, up to four, and so we are expanding that size.

[28:13] Speaker A: So now what we'd like to do as a first step of the algorithm is we'd like to iterate over here and find the pair of bytes that occur most frequently, because we're then going to merge it. So if you are working along on the notebook on the side, then I encourage you to basically click on the link, find this notebook, and try to write that function yourself. Otherwise, I'm going to come here and implement first the function that finds the most common pair.

[28:36] Speaker A: Okay, so here's what I came up with. There are many different ways to implement this, but I'm calling the function get_stats. It expects a list of integers. I'm using a dictionary to keep track of basically the counts. And then this is a Pythonic way to iterate consecutive elements of this list, uh, which we covered in the previous video. And then here, I'm just keeping track of, just incrementing by one, um, for all the pairs. So if I call this on all the tokens here, then the stats comes out here. So this is a dictionary. The keys are these tuples of consecutive elements, and this is the count.

[29:11] Speaker A: So just to, uh, print it in a slightly better way, this is one way that I like to do that, where you, it's a little bit compound here, so you can pause if you like. But we iterate over all the items. The .items() called on dictionary returns pairs of key-value. And instead, I create a list here of value-key, because if it's a value-key list, then I can call sort() on it. And by default, Python will, uh, use the first element, which in this case will be value, to sort by if it's given tuples. And then reverse, so it's descending, and print that.

[29:50] Speaker A: So basically, it looks like 101, 32 was the most commonly occurring consecutive pair, and it occurred 20 times. We can double check that that makes reasonable sense. So if I just search 101, 32, then you see that these are the 20 occurrences of that, um, pair.

[30:09] Speaker A: And if we'd like to take a look at what exactly that pair is, we can use chr, which is the opposite of ord in Python. So we give it a, um, Unicode code point, so 101 and of 32, and we see that this is 'e' and 'space'. So basically, there's a lot of 'e space' here, meaning that a lot of these words seem to end with 'e'. So here's 'e space' as an example. So there's a lot of that going on here, and this is the most common pair.

[30:36] Speaker A: So now that we've identified the most common pair, we would like to iterate over the sequence. We're going to mint a new token with the ID of 256, right? Because these tokens currently go from 0 to 255. So when we create a new token, it will have an ID of 256. And we're going to iterate over this entire, um, list, and every, every time we see 101, 32, we're going to swap that out for 256. So let's implement that now, and feel free to, uh, do that yourself as well.

[31:10] Speaker A: So first, I commented, uh, this just so we don't pollute, uh, the notebook too much. This is a nice way of in Python obtaining the highest ranking pair. So we're basically calling the max on this dictionary stats, and this will return the maximum key. And then the question is, how does it rank keys? So you can provide it with a function that ranks keys, and that function is just stats.get. Uh, stats.get would basically return the value. And so we're ranking by the value and getting the maximum key. So it's 101, 32, as we saw.

I would like you to find and bring in the code that Andrej would like us to follow here as a code msg. You can search the minbpe repo and read the colab notebook.

def get_stats(ids, counts=None):
    """
    Given a list of integers, return a dictionary of counts of consecutive pairs
    Example: [1, 2, 3, 1, 2] -> {(1, 2): 2, (2, 3): 1, (3, 1): 1}
    Optionally allows to update an existing dictionary of counts
    """
    counts = {} if counts is None else counts
    for pair in zip(ids, ids[1:]): # iterate consecutive elements
        counts[pair] = counts.get(pair, 0) + 1
    return counts

Can you also add a hyperlink to get_stats function in the above transcript which will be the git url with the commit hash we've been using. First make sure of the line number and then add the link by updating the msg

Can you create and add step by step code msgs that follow Andrej's steps until the start of merge funciton. Code msgs should be able to be run step by step. Use add_msg with placement=add_before

# Step 1: Get the sample text from Nathan Reed's blog post
text = """Unicode is a standard for encoding and representing text in computers. It was created to solve the problem of multiple incompatible character encodings that existed before it. In the early days of computing, different regions and manufacturers developed their own ways to encode text, leading to a fragmented landscape where text that looked fine on one system would appear as gibberish on another."""

print(f"Text: {text}")
print(f"Length in characters: {len(text)}")

# Step 2: Encode the text to UTF-8 bytes and convert to list of integers
tokens = list(text.encode("utf-8"))
print(f"UTF-8 encoded bytes: {tokens[:50]}...")  # Show first 50 bytes
print(f"Length in bytes: {len(tokens)}")

# Step 3: Find the most common consecutive pair using get_stats
stats = get_stats(tokens)
print(f"Total number of unique pairs: {len(stats)}")

# Show top 10 most frequent pairs
top_pairs = sorted([(count, pair) for pair, count in stats.items()], reverse=True)[:10]
print("\nTop 10 most frequent pairs:")
for count, pair in top_pairs:
    print(f"  {pair}: {count} times")

# Step 3a: Understand how zip(ids, ids[1:]) works for consecutive pairs
sample_list = [1, 2, 3, 4, 5]
consecutive_pairs = list(zip(sample_list, sample_list[1:]))
print(f"Sample list: {sample_list}")
print(f"Consecutive pairs: {consecutive_pairs}")
print("This is the 'Pythonic way' Andrej mentions for iterating consecutive elements")

# Step 4: Get the most frequent pair using max() function
most_frequent_pair = max(stats, key=stats.get)
print(f"Most frequent pair: {most_frequent_pair}")
print(f"Occurs {stats[most_frequent_pair]} times")

# Convert bytes back to characters to see what this pair represents
char1 = chr(most_frequent_pair[0])
char2 = chr(most_frequent_pair[1])
print(f"This represents: '{char1}' + '{char2}'")

# Step 4a: Verify the most frequent pair by finding its occurrences in the text
pair_to_find = most_frequent_pair  # (101, 32) which is 'e' + ' '

# Find all positions where this pair occurs
occurrences = []
for i in range(len(tokens) - 1):
    if tokens[i] == pair_to_find[0] and tokens[i + 1] == pair_to_find[1]:
        occurrences.append(i)

print(f"Found {len(occurrences)} occurrences of pair {pair_to_find} ('e' + ' ') at positions:")
print(f"Positions: {occurrences}")

# Step 5: Prepare to merge - create new token ID
# Current tokens are 0-255 (256 possible values), so new token will be 256
new_token_id = 256
print(f"Will replace pair {most_frequent_pair} with new token ID: {new_token_id}")
print(f"Ready to implement merge function...")

"Because these tokens currently go from 0 to 255" - why this is the case can you briefly explain?

Anything missing in terms of steps to follow that was covered in the transcript section above?

Please update / add steps to reflect these changes

Ok thanks for creating those messages, I've added them to the correct positions.

[48:22] Speaker A: Okay, and now we're going to go the other way. So we are going to implement this arrow right here, where we are going to be given a string and we want to encode it into tokens.

[48:32] Speaker A: So this is the signature of the function that we're interested in. And uh, this should basically print a list of integers of the tokens. So again, uh, try to maybe implement this yourself if you'd like a fun exercise. Uh, and pause here, otherwise I'm going to start putting in my solution. So again, there are many ways to do this. So, um, this is one of the ways that sort of I came up with. So the first thing we're going to do is we are going to take our text, encode it into UTF-8 to get the raw bytes. And then as before, we're going to call list on the bytes object to get a list of integers of those bytes. So those are the starting tokens, those are the raw bytes of our sequence.

[49:15] Speaker A: But now, of course, according to the merges dictionary above, and recall this was the merges, some of the bytes may be merged according to this lookup. And in addition to that, remember that the merges was built from top to bottom, and this is sort of the order in which we inserted stuff into merges. And so we prefer to do all these merges in the beginning before we do these merges later because um, for example, this merge over here relies on the 256 which got merged here. So we have to go in the order from top to bottom sort of if we are going to be merging anything.

[49:49] Speaker A: Now, we expect to be doing a few merges, so we're going to be doing while true. Um, and now we want to find a pair of bytes that is consecutive that we are allowed to merge according to this. In order to reuse some of the functionality that we've already written, I'm going to reuse the function uh, get_stats.

[50:10] Speaker A: So recall that get stats uh, will give us the, will basically count up how many times every single pair occurs in our sequence of tokens and return that as a dictionary. And the dictionary was a mapping from all the different uh, byte pairs to the number of times that they occur, right? Uh, at this point, we don't actually care how many times they occur in the sequence. We only care what the raw pairs are in that sequence. And so I'm only going to be using basically the keys of this dictionary. I only care about the set of possible merge candidates, if that makes sense.

[50:44] Speaker A: Now we want to identify the pair that we're going to be merging at this stage of the loop. So what do we want? We want to find the pair or like the a key inside stats that has the lowest index in the merges uh, dictionary because we want to do all the early merges before we work our way to the late merges. So again, there are many different ways to implement this, but I'm going to do something a little bit fancy here.

[51:11] Speaker A: So I'm going to be using the min over an iterator. In Python, when you call min on an iterator and stats here is a dictionary, we're going to be iterating the keys of this dictionary in Python. So we're looking at all the pairs inside stats, um, which are all the consecutive pairs. And we're going to be taking the consecutive pair inside tokens that has the minimum what? The min takes a key which gives us the function that is going to return a value over which we're going to do the min. And the one we care about is we're we care about taking merges and basically getting um, that pair's index.

[51:53] Speaker A: So basically for any pair inside stats, we are going to be looking into merges at what index it has. And we want to get the pair with the min number. So for an example, if there's a pair 101 and 32, we definitely want to get that pair. We want to identify it here and return it, and pair would become 101, 32 if it occurs. And the reason that I'm putting a float inf here as a fallback is that in the get function, when we call uh, when we basically consider a pair that doesn't occur in the merges, then that pair is not eligible to be merged, right? So if in the token sequence there's some pair that is not a merging pair, it cannot be merged, then uh, it doesn't actually occur here and it doesn't have an index and uh, it can't be merged, which we will denote as float inf. And the reason infinity is nice here is because for sure we're guaranteed that it's not going to participate in the list of candidates when we do the min. So, uh, so this is one way to do it.

[52:55] Speaker A: So basically, in one short, this returns the most eligible merging candidate pair uh, that occurs in the tokens. Now, one thing to be careful with here is this uh, function here might fail in the following way. If there's nothing to merge, then uh, then there's nothing in merges um, that is satisfied anymore. There's nothing to merge. Everything just returns float inf and then uh, the pair, I think will just become the very first element of stats. Um, but this pair is not actually a mergeable pair. It just becomes the first pair in stats arbitrarily because all these pairs evaluate to float inf for the merging criterion. So basically it could be that this this doesn't look succeed because there's no more merging pairs. So if this pair is not in merges that was returned, then this is a signal for us that actually there was nothing to merge. No single pair can be merged anymore. In that case, we will break out. Um, nothing else can be merged.

[53:58] Speaker A: You may come up with a different implementation by the way. This is kind of like really uh, trying hard in Python. Um, but really we're just trying to find a pair that can be merged with a lowest index here. Now, if we did find a pair that is inside merges with the lowest index, then we can merge it. So we're going to look into the merges dictionary for that pair to look up the index, and we're going to now merge that into that index. So we're going to do tokens equals, we're going to replace the original tokens, we're going to be replacing the pair pair, and we're going to be replacing it with index idx. And this returns a new list of tokens where every occurrence of pair is replaced with idx. So we're doing a merge.

[54:46] Speaker A: And we're going to be continuing this until eventually nothing can be merged. We'll come out here and we'll break out. And here we just return tokens. And so that's the implementation I think. So hopefully this runs. Okay, cool. Um, yeah, and this looks uh, reasonable. So for example, 32 is a space in ASCII, so that's here. Um, so this looks like it worked. Great.

Similarly add permalink hyperlink for the merge function to the above transcript

# Step 6: Implement the merge function
def merge(ids, pair, idx):
    """
    In the list of integers (ids), replace all consecutive occurrences 
    of pair with the new integer token idx
    Example: ids=[1, 2, 3, 1, 2], pair=(1, 2), idx=4 -> [4, 3, 4]
    """
    newids = []
    i = 0
    while i < len(ids):
        # if not at the very last position AND the pair matches, replace it
        if ids[i] == pair[0] and i < len(ids) - 1 and ids[i+1] == pair[1]:
            newids.append(idx)
            i += 2  # skip over the pair
        else:
            newids.append(ids[i])
            i += 1
    return newids

# Test with simple example
test_ids = [5, 6, 6, 7, 9, 1]
result = merge(test_ids, (6, 7), 99)
print(f"Original: {test_ids}")
print(f"After merging (6, 7) -> 99: {result}")

# Step 7: Apply merge to our actual tokens
# Merge the most frequent pair (101, 32) with token ID 256
tokens2 = merge(tokens, most_frequent_pair, new_token_id)

print(f"Original length: {len(tokens)}")
print(f"After merge length: {len(tokens2)}")
print(f"Reduction: {len(tokens) - len(tokens2)} tokens")

# Verify the merge worked
print(f"\nOccurrences of new token {new_token_id}: {tokens2.count(new_token_id)}")
print(f"Occurrences of old pair in original: {sum(1 for i in range(len(tokens)-1) if (tokens[i], tokens[i+1]) == most_frequent_pair)}")

# Verify old pair is gone
old_pair_count = sum(1 for i in range(len(tokens2)-1) if (tokens2[i], tokens2[i+1]) == most_frequent_pair)
print(f"Occurrences of old pair in new tokens: {old_pair_count}")

# Step 8: Iterate the BPE algorithm
# Now we repeat: find most common pair, merge it, repeat...
# Let's do a few more iterations

current_tokens = tokens2
vocab_size = 257  # Started with 256, now have 257

print("BPE Training Progress:")
print(f"Step 0: {len(tokens)} tokens, vocab size: 256")
print(f"Step 1: {len(current_tokens)} tokens, vocab size: {vocab_size}")

# Do a few more iterations
for step in range(2, 6):  # Steps 2-5
    # Find most common pair
    stats = get_stats(current_tokens)
    if not stats:  # No more pairs to merge
        break
    
    most_frequent_pair = max(stats, key=stats.get)
    
    # Merge it
    current_tokens = merge(current_tokens, most_frequent_pair, vocab_size)
    
    print(f"Step {step}: {len(current_tokens)} tokens, vocab size: {vocab_size + 1}")
    print(f"  Merged pair: {most_frequent_pair} -> {vocab_size}")
    
    vocab_size += 1

print(f"\nFinal: {len(current_tokens)} tokens, vocab size: {vocab_size}")

Can you similarly find the merge function from the minbpe repo or colab, and then follow Andrej to build up that step by step, continuing from the previous steps

Can we see the merges, I mean which byte combos got merged? You can just output a concise code for me to run. No need to add a code msg.

# Track the merges we made
merges = {
    256: (101, 32),  # 'e' + ' '
    257: (100, 32),  # 'd' + ' '  
    258: (116, 101), # 't' + 'e'
    259: (115, 32),  # 's' + ' '
    260: (105, 110)  # 'i' + 'n'
}

for token_id, (byte1, byte2) in merges.items():
    char1, char2 = chr(byte1), chr(byte2)
    print(f"Token {token_id}: ({byte1}, {byte2}) -> '{char1}' + '{char2}' = '{char1}{char2}'")

Training the Tokenizer

[34:58] Speaker A: Okay, now before we dive into the while loop, I wanted to add one more cell here where I went to the blog post, and instead of grabbing just the first paragraph or two, I took the entire blog post, and I stretched it out in a single line. And basically, just using longer text will allow us to have more representative statistics for the byte pairs, and we'll just get a more sensible result out of it, uh, because it's longer text. So here we have the raw text, we encode it into bytes using the UTF-8 encoding. And then here, as before, we are just changing it into a list of integers in Python just so it's easier to work with instead of the raw bytes object.

[35:36] Speaker A: And then this is the code that I came up with, uh, to actually do the merging in loop. These two functions here are identical to what we had above. I only included them here just so that you have the point of reference here. So, uh, these two are identical, and then this is the new code that I added. So the first thing we want to do is we want to decide on a final vocabulary size that we want our tokenizer to have. And as I mentioned, this is a hyperparameter, and you set it in some way depending on your best performance. So let's say for us, we're going to use 276 because that way we're going to be doing exactly 20 merges. And, uh, 20 merges because we already have 256, uh, tokens for the raw bytes. And to reach 276, we have to do 20 merges, uh, to add 20 new tokens.

[36:26] Speaker A: Here, uh, this is, uh, one way in Python to just create a copy of the list. So I'm taking the tokens list, and by wrapping it in a list, Python will construct a new list of all the individual elements. So this is just a copy operation. Then here, I'm creating a merges uh, dictionary. So this merges dictionary is going to maintain basically the child one, child two mapping to a new, uh, token. And so what we're going to be building up here is a binary tree of merges. But actually, it's not exactly a tree because a tree would have a single root node with a bunch of leaves. For us, we're starting with the leaves on the bottom, which are the individual bytes, those are the starting 256 tokens. And then we're starting to like merge two of them at a time. And so it's not a tree, it's more like a forest, um, as we merge these elements.

[37:18] Speaker A: So for 20 merges, we're going to find the most commonly occurring pair. We're going to mint a new token integer for it. So i here will start at zero, so we'll start with 256. We're going to print that we're merging it, and we're going to replace all the occurrences of that pair with the new, newly minted token. And we're going to record that this pair of integers merged into this new integer. So running this gives us the following output.

[37:51] Speaker A: So we did 20 merges. And for example, the first merge was exactly as before, the 101, 32, uh, tokens merging into a new token 256. Now, keep in mind that the individual, uh, tokens 101 and 32 can still occur in the sequence after merging. It's only when they occur exactly consecutively that that becomes 256 now. Um, and in particular, the other thing to notice here is that the token 256, which is the newly minted token, is also eligible for merging. So here on the bottom, the 20th merge was a merge of 256 and 259 becoming 275. So every time we replace these tokens, they become eligible for merging in the next round of the iteration. So that's why we're building up a small sort of binary forest instead of a single individual tree.

[38:41] Speaker A: One thing we can take a look at as well is we can take a look at the compression ratio that we've achieved. So in particular, we started off with this tokens list. Um, so we started off with 24,000 bytes, and after merging 20 times, uh, we now have only 19,000, um, tokens. And so therefore, the compression ratio is simply just dividing the two is roughly 1.27. So that's the amount of compression we were able to achieve of this text with only 20 merges. Um, and of course, the more vocabulary elements you add, uh, the greater the compression ratio here would be.

So we've got get_stats and merge functions already, can you please extract the remaining code with loop in the image above

tokens = list(text.encode("utf-8"))
print(f"UTF-8 encoded bytes: {tokens[:50]}...")  # Show first 50 bytes
print(f"Length in bytes: {len(tokens)}")

# BPE training
vocab_size = 276  # hyperparameter: the desired final vocabulary size
num_merges = vocab_size - 256
tokens = list(text.encode("utf-8"))

for i in range(num_merges):
    # count up all the pairs
    stats = get_stats(tokens)
    # find the pair with the highest count
    pair = max(stats, key=stats.get)
    # mint a new token: assign it the next available id
    idx = 256 + i
    # replace all occurrences of pair in tokens with idx
    tokens = merge(tokens, pair, idx)
    # print progress
    print(f"merge {i+1}/{num_merges}: {pair} -> {idx} ({stats[pair]} occurrences)")

[39:19] Speaker A: Finally, so that's kind of like, um, the training of the tokenizer, if you will. Now, one point that I wanted to make is that, and maybe this is a diagram that can help, um, kind of illustrate, is that the tokenizer is a completely separate object from the large language model itself. So everything in this lecture, we're not really touching the LLM itself. Uh, we're just training the tokenizer. That is a completely separate preprocessing stage usually. So the tokenizer will have its own training set, just like a large language model has a potentially different training set. So the tokenizer has a training set of documents on which you're going to train the tokenizer. And then, um, we're performing the Byte Pair Encoding algorithm as we saw above.

A diagram illustrating the data pipeline: 'Raw text (Unicode code point sequence)' goes into a 'Tokenizer', which outputs a 'token sequence' that is then fed into the 'LLM'.

[40:00] Speaker A: allows to train the vocabulary of this tokenizer. So it has its own training set, it has a pre-processing stage that you would run a single time in the beginning. Um, and the tokenizer is trained using byte-pair encoding algorithm. Once you have the tokenizer, once it's trained and you have the vocabulary and you have the merges, uh, we can do both encoding and decoding. So these two arrows here. So the tokenizer is a translation layer between raw text, which is, as we saw, the sequence of Unicode code points. It can take raw text and turn it into a token sequence. And vice versa, it can take a token sequence and translate it back into raw text.

[40:41] Speaker A: So now that we have trained the uh, tokenizer and we have these merges, we are going to turn to how we can do the encoding and the decoding step. If you give me text, here are the tokens, and vice versa, if you give me tokens, here's the text. Once we have that, we can translate between these two realms. And then the language model is going to be trained as a step two afterwards. And typically in a, in a sort of a state-of-the-art application, you might take all of your training data for the language model and you might run it through the tokenizer and sort of translate everything into a massive token sequence. And then you can throw away the raw text. You're just left with the tokens themselves. And those are stored on disk and that is what the large language model is actually reading when it's training on them. So that's one approach that you can take as a single massive pre-processing stage.

[41:27] Speaker A: Um, so, yeah, basically, I think the most important thing I want to get across is that this is a completely separate stage. It usually has its own entire uh, training set. You may want to have those training sets be different between the tokenizer and the large language model. So for example, when you're training the tokenizer, as I mentioned, we don't just care about the performance of English text, we care about uh, multi many different languages. And we also care about code or not code. So you may want to look into different kinds of mixtures of different kinds of languages and different amounts of code and things like that, uh, because the amount of different language that you have in your tokenizer training set will determine how many merges of it there will be. And therefore that determines the density with which uh, this type of data is um, sort of has in the token space.

[42:17] Speaker A: And so, roughly speaking, intuitively, if you add some amount of data, let's say you have a ton of Japanese data in your uh, tokenizer training set, then that means that more Japanese tokens will get merged and therefore Japanese will have shorter sequences. Uh, and that's going to be beneficial for the large language model, which has a finite context length on which it can work on in in the token space. Uh, so hopefully that makes sense. So we're now going to turn to encoding and decoding now that we have trained a tokenizer. So we have our merges and now how do we do encoding and decoding?

Decoding

[42:48] Speaker A: Okay, so let's begin with decoding, which is this arrow over here. So given a token sequence, let's go through the tokenizer to get back a Python string object. So the raw text.

[42:58] Speaker A: So this is the function that we'd like to implement. Um, we're given the list of integers and we want to return a Python string. If you'd like, uh, try to implement this function yourself. It's a fun exercise. Otherwise, I'm going to start uh, pasting in my own solution.

[43:12] Speaker A: So there are many different ways to do it. Um, here's one way. I will create an uh, kind of pre-processing variable that I will call vocab. And vocab is a mapping or a dictionary in Python from the token uh, ID to the bytes object for that token. So we begin with the raw bytes for tokens from 0 to 255. And then we go in order of all the merges and we sort of uh, populate this vocab list by doing an addition here. So this is the basically the bytes representation of the first child followed by the second one. And remember these are bytes objects, so this addition here is an addition of two bytes objects, just concatenation. So that's what we get here.

[43:59] Speaker A: One tricky thing to be careful with by the way is that I'm iterating a dictionary in Python using a .items() and uh, it really matters that this runs in the order in which we inserted items into the merges dictionary. Luckily, starting with Python 3.7, this is guaranteed to be the case, but before Python 3.7, this iteration may have been out of order with respect to how we inserted elements into merges and this may not have worked. But we are using a modern Python, so we're okay.

[44:28] Speaker A: And then here, uh, given the IDs, the first thing we're going to do is get the tokens. So the way I implemented this here is I'm taking, I'm iterating over all the IDs, I'm using vocab to look up their bytes, and then here, this is one way in Python to concatenate all these bytes together to create our tokens. And then these tokens here at this point are raw bytes. So I have to decode using UTF-8 now back into Python strings. So previously we called .encode() on a string object to get the bytes, and now we're doing its opposite. We're taking the bytes and calling a decode on the bytes object to get a string in Python. And then we can return text.

[45:16] Speaker A: So, um, this is how we can do it. Now, this actually has a uh, issue, um, in the way I implemented it, and this could actually throw an error. So try to think figure out why this code could actually result in an error if we plug in um, some sequence of IDs that is unlucky. So let me demonstrate the issue. When I try to decode just something like 97, I am going to get the letter a here back. So nothing too crazy happening. But when I try to decode 128 as a single element, the token 128 is what in string or in Python object? UnicodeDecodeError. UTF-8 can't decode byte um, 0x80, which is this in hex, at position zero, invalid start byte. What does that mean?

Use update_msg_with_strs_replace tool and add permalink hyperlinks for functions mentioned in the transcript msg above

Please extract the decode function as a code msg

# Track the merges we made
merges = {
    (101, 32) : 256,  # 'e' + ' '
    (100, 32) : 257,  # 'd' + ' '  
    (116, 101) : 258, # 't' + 'e'
    (115, 32) : 259,  # 's' + ' '
    (105, 110): 260  # 'i' + 'n'
}
# given ids (list of integers), return Python string
vocab = {idx: bytes([idx]) for idx in range(256)}
for (p0, p1), idx in merges.items():
    vocab[idx] = vocab[p0] + vocab[p1]

def decode(ids):
    # given ids, get tokens
    tokens = b"".join(vocab[idx] for idx in ids)
    # convert from bytes to string
    text = tokens.decode("utf-8")
    return text

Show one working example of decode and one for the failure case mentioned in the transcript

print(decode([97]))  # Should work fine

try:print(decode([128]))  # This will cause UnicodeDecodeError
except Exception as e: print(str(e))

[46:03] Speaker A: Well, to understand what this means, we have to go back to our UTF-8 page uh, that I briefly showed earlier, and this is Wikipedia UTF-8. And basically there's a specific schema that UTF-8 bytes take. So in particular, if you have a multi-byte object for some of the Unicode characters, they have to have this special sort of envelope in how the encoding works. And so what's happening here is that invalid start byte, that's because 128, the binary representation of it is one followed by all zeros. So we have one and then all zero. And we see here that that doesn't conform to the format because one followed by all zero just doesn't fit any of these rules, so to speak. So it's an invalid start byte, which is byte one. This one must have a one following it, and then a zero following it, and then the content of your Unicode in Xs here.

[46:57] Speaker A: So basically we don't um, exactly follow the UTF-8 standard and this cannot be decoded. And so the way to fix this, um, is to use this errors equals in bytes.decode function of Python. And by default, errors is strict. So we will throw an error if um, it's not valid UTF-8 byte encoding. But there are many different things that you can put here on error handling. This is the full list of all the errors that you can use. And in particular, instead of strict, let's change it to replace. And that will replace with this special marker, this replacement character. So errors equals replace. And now we just get that character back.

[47:43] Speaker A: So basically not every single byte sequence is valid UTF-8. And if it happens that your large language model, for example, predicts your tokens in a bad manner, then they might not fall into valid UTF-8 and then we won't be able to decode them. So the standard practice is to basically uh, use errors equals replace. And this is what you will also find in the OpenAI um, code that they released as well. But basically whenever you see a this kind of a character in your output in that case, uh, something went wrong and the LLM output was not valid uh, sort of sequence of tokens.

Add hyperlink to the bytes.decode doc page, also bring in the docs on errors mentioned in the transcript as a quoted note msg.

bytes.decode(encoding='utf-8', errors='strict')

Return the bytes decoded to a str.

encoding defaults to 'utf-8'; see Standard Encodings for possible values.

errors controls how decoding errors are handled. If 'strict' (the default), a UnicodeError exception is raised. Other possible values are:

• 'strict': Raise UnicodeError (or a subclass); this is the default
• 'ignore': Ignore the character and continue with the next
• 'replace': Replace with a suitable replacement marker; Python will use the official U+FFFD REPLACEMENT CHARACTER for the built-in codecs on decoding
• 'xmlcharrefreplace': Replace with the appropriate XML character reference
• 'backslashreplace': Replace with backslashed escape sequences

For performance reasons, the value of errors is not checked for validity unless an encoding error actually occurs.

Now write the fixed decode function as seen in the image

def decode(ids):
    # given ids (list of integers), return Python string
    tokens = b"".join(vocab[idx] for idx in ids)
    text = tokens.decode("utf-8", errors="replace")
    return text

try:print(decode([128]))  # This should now print the replacement character without error
except Exception as e: print(str(e))

Encoding

[48:22] Speaker A: Okay, and now we're going to go the other way. So we are going to implement this arrow right here, where we are going to be given a string and we want to encode it into tokens.

[48:32] Speaker A: So this is the signature of the function that we're interested in. And uh, this should basically print a list of integers of the tokens. So again, uh, try to maybe implement this yourself if you'd like a fun exercise. Uh, and pause here, otherwise I'm going to start putting in my solution. So again, there are many ways to do this. So, um, this is one of the ways that sort of I came up with. So the first thing we're going to do is we are going to take our text, encode it into UTF-8 to get the raw bytes. And then as before, we're going to call list on the bytes object to get a list of integers of those bytes. So those are the starting tokens, those are the raw bytes of our sequence.

[49:15] Speaker A: But now, of course, according to the merges dictionary above, and recall this was the merges, some of the bytes may be merged according to this lookup. And in addition to that, remember that the merges was built from top to bottom, and this is sort of the order in which we inserted stuff into merges. And so we prefer to do all these merges in the beginning before we do these merges later because um, for example, this merge over here relies on the 256 which got merged here. So we have to go in the order from top to bottom sort of if we are going to be merging anything.

[49:49] Speaker A: Now, we expect to be doing a few merges, so we're going to be doing while true. Um, and now we want to find a pair of bytes that is consecutive that we are allowed to merge according to this. In order to reuse some of the functionality that we've already written, I'm going to reuse the function uh, get_stats.

[50:10] Speaker A: So recall that get_stats uh, will give us the, will basically count up how many times every single pair occurs in our sequence of tokens and return that as a dictionary. And the dictionary was a mapping from all the different uh, byte pairs to the number of times that they occur, right? Uh, at this point, we don't actually care how many times they occur in the sequence. We only care what the raw pairs are in that sequence. And so I'm only going to be using basically the keys of this dictionary. I only care about the set of possible merge candidates, if that makes sense.

[50:44] Speaker A: Now we want to identify the pair that we're going to be merging at this stage of the loop. So what do we want? We want to find the pair or like the a key inside stats that has the lowest index in the merges uh, dictionary because we want to do all the early merges before we work our way to the late merges. So again, there are many different ways to implement this, but I'm going to do something a little bit fancy here.

[51:11] Speaker A: So I'm going to be using the min over an iterator. In Python, when you call min on an iterator and stats here is a dictionary, we're going to be iterating the keys of this dictionary in Python. So we're looking at all the pairs inside stats, um, which are all the consecutive pairs. And we're going to be taking the consecutive pair inside tokens that has the minimum what? The min takes a key which gives us the function that is going to return a value over which we're going to do the min. And the one we care about is we're we care about taking merges and basically getting um, that pair's index.

[51:53] Speaker A: So basically for any pair inside stats, we are going to be looking into merges at what index it has. And we want to get the pair with the min number. So for an example, if there's a pair 101 and 32, we definitely want to get that pair. We want to identify it here and return it, and pair would become 101, 32 if it occurs. And the reason that I'm putting a float inf here as a fallback is that in the get function, when we call uh, when we basically consider a pair that doesn't occur in the merges, then that pair is not eligible to be merged, right? So if in the token sequence there's some pair that is not a merging pair, it cannot be merged, then uh, it doesn't actually occur here and it doesn't have an index and uh, it can't be merged, which we will denote as float inf. And the reason infinity is nice here is because for sure we're guaranteed that it's not going to participate in the list of candidates when we do the min. So, uh, so this is one way to do it.

[52:55] Speaker A: So basically, in one short, this returns the most eligible merging candidate pair uh, that occurs in the tokens. Now, one thing to be careful with here is this uh, function here might fail in the following way. If there's nothing to merge, then uh, then there's nothing in merges um, that is satisfied anymore. There's nothing to merge. Everything just returns float inf and then uh, the pair, I think will just become the very first element of stats. Um, but this pair is not actually a mergeable pair. It just becomes the first pair in stats arbitrarily because all these pairs evaluate to float inf for the merging criterion. So basically it could be that this this doesn't look succeed because there's no more merging pairs. So if this pair is not in merges that was returned, then this is a signal for us that actually there was nothing to merge. No single pair can be merged anymore. In that case, we will break out. Um, nothing else can be merged.

[53:58] Speaker A: You may come up with a different implementation by the way. This is kind of like really uh, trying hard in Python. Um, but really we're just trying to find a pair that can be merged with a lowest index here. Now, if we did find a pair that is inside merges with the lowest index, then we can merge it. So we're going to look into the merges dictionary for that pair to look up the index, and we're going to now merge that into that index. So we're going to do tokens equals, we're going to replace the original tokens, we're going to be replacing the pair pair, and we're going to be replacing it with index idx. And this returns a new list of tokens where every occurrence of pair is replaced with idx. So we're doing a merge.

[54:46] Speaker A: And we're going to be continuing this until eventually nothing can be merged. We'll come out here and we'll break out. And here we just return tokens. And so that's the implementation I think. So hopefully this runs. Okay, cool. Um, yeah, and this looks uh, reasonable. So for example, 32 is a space in ASCII, so that's here. Um, so this looks like it worked. Great.

Use update_msg_with_strs_replace tool and add permalink hyperlinks for functions mentioned in the transcript msg above

Please add others like decode and encode if mentioned

Yes please find it and add it. It should be under gpt4.py in minbpe repo.

def encode(text):
    # given a string, return list of integers (the tokens)
    tokens = list(text.encode("utf-8"))
    while True:
        stats = get_stats(tokens)
        pair = min(stats, key=lambda p: merges.get(p, float("inf")))
        if pair not in merges:
            break # nothing else can be merged
        idx = merges[pair]
        tokens = merge(tokens, pair, idx)
    return tokens

print(encode("hello world!"))

[55:11] Speaker A: Okay, so let's wrap up this section of the video at least. I wanted to point out that this is not quite the right implementation just yet because we are leaving out a special case. So in particular, if uh, we try to do this, this will give us an error. And the issue is that um, if we only have a single character or an empty string, then stats is empty and that causes an issue inside min. So one way to fight this is if length of tokens is at least two. Because if it's less than two, it's just a single token or no tokens, then let's just uh, there's nothing to merge, so we just return. So that would fix uh, that case.

try: print(encode('h'))
except Exception as e: print(e)

Extracted the fixed version of encode function from the image above.

def encode(text):
    # given a string, return list of integers (the tokens)
    tokens = list(text.encode("utf-8"))
    while True:
        stats = get_stats(tokens)
        if len(tokens) < 2:
            break  # nothing to merge
        pair = min(stats, key=lambda p: merges.get(p, float("inf")))
        if pair not in merges:
            break # nothing else can be merged
        idx = merges[pair]
        tokens = merge(tokens, pair, idx)
    return tokens

encode('h')

[55:45] Speaker A: Okay. And then second, I have a few test cases here for us as well. So first, let's make sure uh, about or let's note the following. If we take a string and we try to encode it and then decode it back, you would expect to get the same string back, right? Is that true for all strings?

[56:05] Speaker A: So I think uh, so here it is the case, and I think in general this is probably the case. Um, but notice that going backwards is not, is not, you're not going to have an identity going backwards because as I mentioned, uh, not all token sequences are valid UTF-8 uh, sort of byte streams. And so therefore you're some of them can't even be decodable. Um, so this only goes in one direction. But for that one direction, we can check uh, here. If we take the training text, which is the text that we trained the tokenizer on, we can make sure that when we encode and decode, we get the same thing back, which is true. And here I took some validation data. So I went to, I think this web page and I grabbed some text. So this is text that the tokenizer has not seen, and we can make sure that this also works. Uh, so that gives us some confidence that this was correctly implemented.

Please write those test cases and add as new code msgs

# Test that encode/decode is identity for training text
text2 = decode(encode(text))
test_eq(text, text2)

# Test on new validation text
valtext = "Many common characters, including numerals, punctuation, and other symbols, are unified within the standard"
test_eq(decode(encode(valtext)), valtext)

[56:56] Speaker A: So those are the basics of the byte-pair encoding algorithm. We saw how we can take some training set, train a tokenizer. The parameters of this tokenizer really are just this dictionary of merges. And that basically creates a little binary forest on top of raw bytes. Once we have this, the merges table, we can both encode and decode between raw text and token sequences. So that's the the simplest setting of the tokenizer. What we're going to do now though is we're going to look at some of the state-of-the-art large language models and the kinds of tokenizers that they use. And we're going to see that this picture complexifies very quickly. So we're going to go through the details of this complexification one at a time.

Part 2:

Forced Splits Using Regex Patterns (GPT Series)

[57:37] Speaker A: So let's get things off by looking at the GPT series. So in particular, I have the GPT-2 paper here. Um, and this paper is from 2019 or so, uh, so five years ago. And let's scroll down to input representation. This is where they talk about the tokenizer that they're using for GPT-2.

[57:54] Speaker A: Now, this is all fairly readable, so I encourage you to pause and um, read this yourself. But this is where they motivate the use of the byte-pair encoding algorithm on the byte level representation of UTF-8 encoding. So this is where they motivated and they talk about the vocabulary sizes and everything. Now, everything here is exactly as we've covered it so far, but things start to depart around here. So what they mention is that they don't just apply the naive algorithm as we have done it. And in particular, here's a motivating example. Suppose that you have common words like dog. What will happen is that dog, of course, occurs very frequently in the text, and it occurs right next to all kinds of punctuation as an example. So dog dot, dog exclamation mark, dog question mark, etc. And naively, you might imagine that the BPE algorithm could merge these to be single tokens. And then you end up with lots of tokens that are just like dog with a slightly different punctuation. And so it feels like you're clustering things that shouldn't be clustered. You're combining kind of semantics with punctuation.

Please add a hyperlink to the paper

Extract the mentioned problem from the above screenshot image of the paper as a quoted note msg, starting from "We observed BPE...", use add_msg to add the msg

"We observed BPE includes many versions of common words like 'dog' since they occur in many contexts (e.g., 'dog.', 'dog!', 'dog?', etc.). This results in a sub-optimal allocation of limited vocabulary slots and model capacity. To avoid this, we prevent BPE from merging across character categories for any byte sequence."

GPT-2 paper

[58:56] Speaker A: And this uh, feels suboptimal, and indeed they also say that this is suboptimal according to some of the experiments. So what they want to do is they want to top down in a manual way enforce that some types of um, characters should never be merged together. Um, so they want to enforce these merging rules on top of the byte-pair encoding algorithm. So let's take a look um, at their code and see how they actually enforce this and what kinds of merges they actually do perform.

[59:24] Speaker A: So I have the tab open here for GPT-2 under OpenAI on GitHub. And when we go into source, there is an encoder.py. Now, I don't personally love that they call it encoder.py because this is the tokenizer. And the tokenizer can do both encode and decode. Uh, so it feels kind of awkward to me that it's called encoder, but that is the tokenizer. And there's a lot going on here and we're going to step through it in detail at one point. For now, I just want to focus on this part here. They create a regex pattern here that looks very complicated, and we're going to go through it in a bit. Uh, but this is the core part that

Please extract a code snippet of Encoder class up until the regex pattern

# GPT-2 Encoder with regex pattern
class Encoder:
    def __init__(self, encoder, bpe_merges, errors='replace'):
        self.encoder = encoder
        self.decoder = {v:k for k,v in self.encoder.items()}
        self.bpe_merges = dict(zip(bpe_merges, range(len(bpe_merges))))
        self.cache = {}
        self.pat = re.compile(r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

Can you also find and add a hyperlink for encoder.py module in the transcript above

[60:00] Andrej Karpathy: allows them to enforce rules uh for what parts of the text will never be merged for sure.

[60:06] Andrej Karpathy: Now notice that re.compile here is a little bit misleading because we're not just doing import re, which is the Python re module. We're doing import regex as re. And regex is a Python package that you can install, pip install regex. And it's basically an extension of re, so it's a bit more powerful re.

Let's add hyperlink to regex pypi package in the above transcript

[60:25] Andrej Karpathy: So let's take a look at this pattern and what it's doing and why this is actually doing the separation that they are looking for.

[60:33] Andrej Karpathy: Okay, so I've copy pasted the pattern here to our Jupyter notebook where we left off. And let's take this pattern for a spin. So in the exact same way that their code does, we're going to call an re.findall for this pattern on any arbitrary string that we are interested in. So this is the string that we want to encode into tokens um to feed into an LLM like GPT-2. So what exactly is this doing?

[60:58] Andrej Karpathy: Well, re.findall will take this pattern and try to match it against this string. Um, the way this works is that you are going from left to right in the string and you're trying to match the pattern. And re.findall will get all the occurrences and organize them into a list. Now, when you look at the um when you look at this pattern, first of all, notice that this is a raw string, um and then these are three double quotes just to start the string. So really the string itself, this is the pattern itself, right?

[61:32] Andrej Karpathy: And notice that it's made up of a lot of ors. So see these vertical bars, those are ors in regex. And so you go from left to right in the pattern and try to match it against the string wherever you are. So we have hello and we're going to try to match it. Well, it's not apostrophe s, it's not apostrophe t, or any of these. But it is an optional space followed by dash p of uh sorry, slash p of L one or more times. What is slash p of L? It is coming to some documentation that I found. Um there might be other sources as well.

[62:08] Andrej Karpathy: Uh slash p of L is a letter, any kind of letter from any language. And hello is made up of letters, h e l l o, etc. So optional space followed by a bunch of letters, one or more letters, is going to match hello, but then the match ends because a white space is not a letter. So from there on begins a new sort of attempt to match against the string again. And starting in here, we're going to skip over all these again until we get to the exact same point again. And we see that there's an optional space, this is the optional space, followed by a bunch of letters, one or more of them, and so that matches. So when we run this, we get a list of two elements, hello and then space world.

import regex as re

pat = re.compile(r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

# Test the regex pattern on simple text
text = "Hello world"
matches = pat.findall(text)
print(f"Text: '{text}'")
print(f"Matches: {matches}")
print(f"Number of chunks: {len(matches)}")

# Test with more complex text including punctuation
text2 = "Hello world how are you?"
matches2 = pat.findall(text2)
print(f"Text: '{text2}'")
print(f"Matches: {matches2}")
print(f"Number of chunks: {len(matches2)}")

Can you create code msgs that show cases what Andrej shows above step by step. Use add_msg to add code msgs with placement='add_before'

Pattern: 's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

Breaking it down:

• 's|'t|'re|'ve|'m|'ll|'d -> Common contractions
• ?\p{L}+ -> Optional space + one or more letters
• ?\p{N}+ -> Optional space + one or more numbers
• ?[^\s\p{L}\p{N}]+ -> Optional space + punctuation/symbols
• \s+(?!\S)|\s+ -> Whitespace handling

Can you explain this pattern in plain English add it as a note msg below, use add_msg add_after

The regex pattern ensures that BPE merging respects natural language boundaries by splitting text into these categories:

What it captures:

1. Contractions - Common English contractions like "don't", "we're", "I'll" are kept as single units
2. Words - Letters from any language (including accented characters) are grouped together, optionally preceded by a space
3. Numbers - Digits are grouped together, optionally preceded by a space
4. Punctuation & Symbols - Non-letter, non-digit characters are grouped together, optionally preceded by a space
5. Whitespace - Handles various whitespace patterns

Why this matters:

• Prevents "dog" + "." from merging into a single token
• Keeps semantic meaning (words) separate from punctuation
• Allows BPE to work within each category, but not across categories
• Results in more meaningful token boundaries that respect language structure

pat.findall("I'll go! I don't know 123?   ")

[63:01] Andrej Karpathy: Now, what is this doing and why is this important? We are taking our string and instead of directly encoding it um for tokenization, we are first splitting it up. And when you actually step through the code, and we'll do that in a bit more detail, what really it's doing on a high level is that it first splits your text into a list of texts, just like this one. And all these elements of this list are processed independently by the tokenizer, and all the results of that processing are simply concatenated. So hello, world, oh, I missed how. Hello, world, how are you? We have five elements of a list. All of these will independently go from text to a token sequence, and then that token sequence is going to be concatenated. It's all going to be joined up.

[63:52] Andrej Karpathy: And roughly speaking, what that does is you're only ever finding merges between the elements of this list. So you can only ever consider merges within every one of these elements individually. And um after you've done all the possible merging for all these elements individually, the results of all that will be joined um by concatenation. And so you are basically, what you're doing effectively is you are never going to be merging this e with this space because they are now parts of the separate elements of this list. And so you are saying we are never going to merge e space, um because we're breaking it up in this way. So basically using this regex pattern to chunk up the text is just one way of enforcing that some merges are not to happen. And we're going to go into more of this text and we'll see that what this is trying to do on a high level is we're trying to not merge across letters, across numbers, across punctuation, and so on. So let's see in more detail how that works. So let's continue now. We have slash p of n. If you go to the documentation, slash p of n is any kind of numeric character in any script. So it's numbers. So we have an optional space followed by numbers and those would be separated out. So letters and numbers are being separated. So if I do hello world 123, how are you? Then world will stop matching here because one is not a letter anymore. But one is a number, so this group will match for that and we'll get it as a separate entity.

[65:26] Andrej Karpathy: Uh, let's see how these apostrophes work. So here, if we have um uh slash b or I mean apostrophe v as an example, then apostrophe here is not a letter or a number. So hello will stop matching and then we will exactly match this with that. So that will come out as a separate thing. So why are they doing the apostrophes here? Honestly, I think that these are just like very common apostrophes uh that are used um typically. I don't love that they've done this because let me show you what happens when you have uh some Unicode apostrophes. Like for example, you can have if you have how's, then this will be separated out because of this matching. But if you use the Unicode apostrophe like this, then suddenly this does not work. And so this apostrophe will actually become its own thing now.

# Step 1: Show how letters and numbers are separated
text = "Hello world123 how are you?"
matches = pat.findall(text)
print(f"Text: '{text}'")
print(f"Matches: {matches}")
print("Notice: 'world' and '123' are separate chunks")

# Step 2: Show how contractions work with standard apostrophes
text = "how's it going"
matches = pat.findall(text)
print(f"Text: '{text}'")
print(f"Matches: {matches}")
print("Notice: Standard apostrophe 's' is kept with the word")

# Step 3: Show the Unicode apostrophe problem
text = "how\u2019s it going"  # Unicode apostrophe (different from standard ')
matches = pat.findall(text)
print(f"Text: '{text}'")
print(f"Matches: {matches}")
print("Notice: Unicode apostrophe becomes its own separate chunk!")

Please add step by step code for the stuff described in the above transcript portion. Use add_msg to add code msgs with add_before

[66:23] Andrej Karpathy: And so, um it basically hardcoded for this specific kind of apostrophe and uh otherwise they become completely separate tokens. In addition to this, you can go to the GPT-2 docs and here where they define the pattern, they say, should have added re.ignorecase so BPE merges can happen for capitalized versions of contractions. So what they're pointing out is that you see how this is apostrophe and then lowercase letters. Well, because they didn't do re.ignorecase, then um these rules will not separate out the apostrophes if it's uppercase.

[66:59] Andrej Karpathy: So how's would be like this. But if I did HOW'S from uppercase, then notice suddenly the apostrophe comes by itself.

pat.findall("HOW'S it going?")

[67:13] Andrej Karpathy: So the tokenization will work differently in uppercase and lowercase, inconsistently separating out these apostrophes. So this feels extremely gnarly and slightly gross. Um but that's that's how that works. Okay, so let's come back. After trying to match a bunch of apostrophe expressions, by the way, the other issue here is that these are quite language specific probably. So I don't know that all languages, for example, use or have these apostrophes, but that would be inconsistently tokenized as a result. Then we try to match letters, then we try to match numbers. And then if that doesn't work, we fall back to here. And what this is saying is again, optional space followed by something that is not a letter, number, or a space, and one or more of that. So what this is doing effectively is this is trying to match punctuation, roughly speaking, not letters and not numbers. So this group will try to trigger for that. So if I do something like this, then these parts here uh are not letters or numbers, but they will actually they are uh they will actually get caught here. And so they become its own group. So we've separated out the punctuation.

[68:18] Andrej Karpathy: And finally, this um this is also a little bit confusing. So this is matching white space, but this is using a negative look ahead assertion in regex. So what this is doing is it's matching white space up to but not including the last white space character. Why is this important? Um this is pretty subtle, I think. So you see how the white space is always included at the beginning of the word. So um space r, space u, etc. Suppose we have a lot of spaces here. What's going to happen here is that these spaces up to and not including the last character will get caught by this. And what that will do is it will separate out the spaces up to but not including the last character. So that the last character can come here and join with the uh space you. And the reason that's nice is because space you is the common token. So if I didn't have these extra spaces here, you would just have space you. And if I add tokens, if I add spaces, we still have a space you, but now we have all this extra white space.

pat.findall("you!!!??")

pat.findall("     you")

[69:22] Andrej Karpathy: So basically the GPT-2 tokenizer really likes to have a space letters or numbers. Um and it it prepends these spaces and this is just something that it does consistently. So that's what that is for. And then finally, we have all the the last fallback is um white space characters. Uh so um that would be just um if that doesn't get caught, then this thing will catch any trailing spaces and so on.

[69:50] Andrej Karpathy: I wanted to show one more real world example here. So if we have this string, which is a piece of Python code, and then we try to split it out, then this is the kind of output we get. So you'll notice that the list has many elements here and that's because we are splitting up fairly often uh every time sort of a category changes. Um so there will never be any merges within these elements. And um that's what you are seeing here.

Please extract the above example as a code msg

example = """
for i in range(1, 101):
    if i % 3 == 0 and i % 5 == 0:
        print("FizzBuzz")
    elif i % 3 == 0:
        print("Fizz")
    elif i % 5 == 0:
        print("Buzz")
    else:
        print(i)
"""

print(pat.findall(example))

[70:14] Andrej Karpathy: Now, you might think that in order to train the tokenizer, uh OpenAI has used this to split up text into chunks and then run just the BPE algorithm within all the chunks. But that is not exactly what happened. And the reason is the following. Notice that we have the spaces here. Uh those spaces end up being entire elements. But these spaces never actually end up being merged by by OpenAI. And the way you can tell is that if you copy paste the exact same chunk here into tiktoken, um tiktokenizer, you see that all the spaces are kept independent and they're all token 220.

A screenshot of the Tiktokenizer web tool. The left panel shows the FizzBuzz Python code. The right panel shows the tokenized output, with individual space characters highlighted and identified as token 220.

[70:51] Andrej Karpathy: So, I think OpenAI at some point enforced some rule that these spaces would never be merged. And so, um there's some additional rules on top of just chunking and BPEing that OpenAI is not uh clear about. Now, the training code for the GPT-2 tokenizer was never released. So all we have is uh the code that I've already shown you. But this code here that they released is only the inference code for the tokens. So this is not the training code. You can't give it a piece of text and train a tokenizer. This is just the inference code which takes the merges that we have up above and applies them to a new piece of text. And so we don't know exactly how OpenAI trained um trained the tokenizer, but it wasn't as simple as chunk it up and BPE it, uh whatever it was.

Tiktoken

[71:38] Andrej Karpathy: Next, I wanted to introduce you to the tiktoken library from OpenAI, which is the official library for tokenization from OpenAI. So this is tiktoken. Pip install tiktoken and then um you can do the tokenization inference. So this is again, not training code, this is only inference code for tokenization.

The Official encoder.py

[74:58] Andrej Karpathy: The next thing I would like to do very briefly is to take you through the GPT-2 encoder.py that OpenAI has released. This is the file that I've already mentioned to you briefly. Now, this file is uh fairly short and should be relatively understandable to you at this point. Um starting at the bottom here, they are loading two files, encoder.json and vocab.bpe. And they do some light processing on it and then they call this encoder object, which is the tokenizer.

[75:28] Andrej Karpathy: Now, if you'd like to inspect these two files, which together constitute their saved tokenizer, then you can do that with a piece of code like this. Um this is where you can download these two files and you can inspect them if you'd like. And what you will find is that this encoder, as they call it in their code, is exactly equivalent to our vocab.

Special Tokens

[78:26] Andrej Karpathy: The next topic I would like to turn to is that of special tokens. So, in addition to tokens that are coming from, you know, raw bytes and the BPE merges, we can insert all kinds of tokens that we are going to use to delimit different parts of the data or introduce to create a special structure of the token streams. So, in uh if you look at this encoder object from OpenAI's GPT-2 right here, we mentioned this is very similar to our vocab. You'll notice that the length of this is 50,257.

Special Tokens in Fine-Tuning

[82:01] Andrej Karpathy: So these special tokens are used pervasively, uh not just in uh basically base language modeling of predicting the next token in a sequence, but especially when it gets to later to the fine-tuning stage and all the chat GPT sort of aspects of it. Uh because we don't just want to delimit documents, we want to delimit entire conversations between an assistant and a user. So if I refresh this Tiktokenizer page, the default example that they have here is using not sort of base model encoders, but fine-tuned model uh sort of tokenizers.

[82:34] Andrej Karpathy: Um, so for example, using the GPT-3.5 Turbo scheme, these here are all special tokens. I am start, I am end, etc. Uh this is short for imaginary monologue underscore start, by the way. But you can see here that there's a sort of start and end of every single message, and there can be many other tokens, uh lots of tokens, um in use to delimit these conversations and kind of keep track of the flow of the messages here.

The Tiktokenizer website in chat mode for GPT-3.5-turbo, showing special tokens like <|im_start|>system and <|im_end|> used to structure a conversation.

The minbpe Exercise

[85:28] Andrej Karpathy: Okay, so at this point you should have everything you need in order to build your own GPT-4 tokenizer. Now, in the process of developing this lecture, I've done that and I've published the code under this repository minbpe.

[85:40] Andrej Karpathy: So minbpe looks like this right now as I'm recording, but um the minbpe repository will probably change quite a bit because I intend to continue working on it. Um, in addition to the minbpe repository, I've published this uh exercise progression that you can follow. So if you go to exercise.md here, this is sort of me breaking up the task ahead of you into four steps that sort of uh build up to what can be a GPT-4 tokenizer. And so feel free to follow these steps exactly and uh follow a little bit of the guidance that I've laid out here. And anytime you feel stuck, just reference the minbpe repository here.

# Do you work in solveit here

# Do you work in solveit here

# Do you work in solveit here

# Do you work in solveit here

# Do you work in solveit here

[86:17] Andrej Karpathy: So either the tests could be useful or the minbpe repository itself. I tried to keep the code fairly clean and understandable. And so, um, feel free to reference it whenever um you get stuck.

[86:31] Andrej Karpathy: In addition to that, basically, once you write it, you should be able to reproduce this behavior from tiktoken. So getting the GPT-4 tokenizer, you can take uh you can encode this string and you should get these tokens. And then you can encode and decode the exact same string to recover it. And in addition to all that, you should be able to implement your own train function, which tiktoken library does not provide. It's again, only inference code. But you should be able to write your own train, minbpe does it as well. And that will allow you to train your own token vocabularies.

[87:01] Andrej Karpathy: So here's some of the code inside minbpe, minbpe, uh shows the token vocabularies that you might obtain. So on the left uh here, we have the GPT-4 merges. Uh so the first 256 are raw individual bytes. And then here I am visualizing the merges that GPT-4 performed during its training. So the very first merge that GPT-4 did was merge two spaces into a single token for, you know, two spaces. And that is the token 256.

[87:31] Andrej Karpathy: And so this is the order in which things merged during GPT-4 training. And this is the merge order that um we obtained in minbpe by training a tokenizer. And in this case, I trained it on a Wikipedia page of Taylor Swift. Uh not because I'm a Swifty, but because that is one of the longest um Wikipedia pages apparently that's available. But she is pretty cool. And um, what was I going to say? Yeah, so you can compare these two uh vocabularies and so as an example, um, here GPT-4 merged I M to become in, and we've done the exact same thing on this token 259. Here, space T becomes spacey, and that happened for us a little bit later as well. So the difference here is again, to my understanding, only a difference of the training set. So as an example, because I see a lot of white space, I expect that GPT-4 probably had a lot of Python code in its training set. I'm not sure. Uh for the tokenizer. And uh here we see much less of that, of course, in the Wikipedia page. So roughly speaking, they look the same and they look the same because they're running the same algorithm. And when you train your own, you're probably going to get something similar depending on what you train it on.

Can you extract the ideas from above as a note msg.

Key Insights from the minbpe Exercise:

What You Should Be Able to Do:

• Reproduce tiktoken behavior exactly - Your tokenizer should encode/decode strings identically to GPT-4's cl100k_base
• Implement your own training function - Unlike tiktoken (inference-only), you can train custom vocabularies
• Compare different training datasets - See how training data affects the learned merges

Vocabulary Comparison Insights: Looking at the side-by-side comparison in the image:

Left (GPT-4 Official):

• First 256 tokens: Raw individual bytes
• Token 256: Two spaces merged (indicates lots of code/structured text in training)
• Shows heavy whitespace merging patterns

Right (Taylor Swift Wikipedia):

• Same algorithm, different training data
• Less whitespace merging (typical prose text)
• Similar patterns but different priorities

Key Observations:

• Same algorithm, different results - BPE produces vocabularies that reflect the training data
• Training data matters - GPT-4's heavy whitespace merging suggests Python code in training set
• Merge order reveals priorities - Most frequent patterns get merged first
• Reproducible patterns - Both show similar merges like "IM" → "in" and "space+T" → "space+T"

The Power of Custom Training: You can now train tokenizers optimized for your specific domain - whether that's code, medical text, or any specialized content!

SentencePiece

[88:42] Andrej Karpathy: Okay, so we are now going to move on from tiktoken and the way that OpenAI tokenizes its strings. And we're going to discuss one more very commonly used library for working with tokenization in LLMs, and that is SentencePiece. So SentencePiece is uh very commonly used in language models because unlike tiktoken, it can do both training and inference, and it's quite efficient at both. It supports a number of algorithms for training uh vocabularies, but one of them is the byte-pair encoding algorithm that we've been looking at. So it supports it.

[89:13] Andrej Karpathy: Now, SentencePiece is used both by Llama and Mistral series and many other models as well. It is on GitHub under google/sentencepiece.

[89:22] Andrej Karpathy: And the big difference with SentencePiece, and we're going to look at an example because this is kind of hard and subtle to explain, is that they think different about the order of uh operations here. So in the case of tiktoken, we first take our code points in a string, we encode them using UTF-8 to bytes, and then we're merging bytes. It's fairly straightforward.

[89:46] Andrej Karpathy: For SentencePiece, um it works directly on the level of the code points themselves. So it looks at whatever code points are available in your training set, and then it starts merging those code points. And um the BPE is running on the level of code points. And if you happen to run out of code points, so there are maybe some rare uh code points that just don't come up too often, and the rarity is determined by this character coverage hyperparameter, then these uh code points will either get mapped to a special unknown token, like unk, or if you have the byte fallback option turned on, then they will take those rare code points, they will encode them using UTF-8, and then the individual bytes of that encoding will be translated into tokens. And there are these special byte tokens that basically get added to the vocabulary. So it uses BPE on on the code points, and then it falls back to bytes for rare code points. Um, and so that's kind of our difference. Personally, I find the tiktoken way significantly cleaner, uh but it's kind of like a subtle but pretty major difference between the way they approach tokenization.

Training a SentencePiece Model

[90:51] Andrej Karpathy: Let's work with a concrete example because otherwise this is kind of hard to um to get your head around. So let's work with a concrete example. This is how we can import SentencePiece. And then here we're going to take, I think I took like the description of SentencePiece and I just created like a little toy dataset. It really likes to have a file, so I created a toy.txt file with this content.

[91:13] Andrej Karpathy: Now, what's kind of a little bit crazy about SentencePiece is that there's a ton of options and configurations. And the reason this is so is because SentencePiece has been around, I think for a while, and it really tried to handle a large diversity of things. And um because it's been around, I think it has quite a bit of accumulated historical baggage uh as well. And so in particular, there's like a ton of configuration arguments. This is not even all of it.

[91:38] Andrej Karpathy: You can go to here to see all the training options. Um, and uh there's also quite useful documentation when you look at the raw protobuf uh that is used to represent the trainer spec and so on. Um, many of these options are irrelevant to us. So maybe to point out one example, dash dash shrinking factor. Uh this shrinking factor is not used in the byte-pair encoding algorithm. So this is just an argument that is irrelevant to us. Um, it applies to a different training algorithm.

Can you find and link the options file to the transcript above, also while you do that extract some of the relevant options for training BPE as a new note msg

Key SentencePiece Options for BPE Training:

Essential BPE Parameters:

• --model_type=bpe - Use byte-pair encoding (default is "unigram")
• --vocab_size=8000 - Final vocabulary size (e.g., 8000, 16000, 32000)
• --input=file.txt - Training text file
• --model_prefix=model_name - Output model prefix (creates .model and .vocab files)

Important for Different Languages:

• --character_coverage=0.9995 - For languages with rich character sets (Japanese/Chinese)
• --character_coverage=1.0 - For languages with small character sets (English/European)