belladoreai

These are both great questions.

> I take it if you do greedily go from left to right, you end up with different tokenization and the model doesn't work properly because that isn't what it was trained with?

The way that the LLaMA tokenizer works is, a word is tokenized one way within a certain context, and a different way within a different context. If you go greedily from left to right, you will find mostly the same tokenizations for words, but occasionally the tokenization will be different. It will still be a legitimate tokenization for the word, though, so the model will not spew nonsense if you feed these tokens into it. I assume the outputs of the model would be slightly suboptimal, but the difference might be so small that nobody notices anything.

Anyway, I don't expect anyone to use this library in a manner where they will turn text to tokens with this library, and then feed the tokens to the model. I expect people to use this library to count tokens, dynamically iterate on the prompt to fit within the token limit, and then eventually send raw text to the model, which performs the tokenization by itself. If we think about this use case, and we consider what would happen if we just greedily tokenized from left to right, it would be mostly fine, because our token counts would be pretty close to the real token count. But occasionally it wouldn't be fine: occasionally our greedy tokenizer would say that we are below the token limit, when actually we're beyond the token limit. In this case the model would either return an error, or it would automatically trim some part of the prompt. If the prompt is automatically trimmed, it might be trimmed from the wrong place. For example, oobabooga trims the prompt from the beginning, when you typically would want to trim the prompt from the middle.

> Did the model designers choose this 'difficult' tokenization because it performs better?

I'm not sure. LLaMA is using a SentencePiece BPE tokenizer, and the most-often touted benefit of this tokenizer is that it can fluently deal with multiple different languages. So it's possible that they chose this to support multiple different languages, not to maximize the quality of output in the English language.

I think it would take quite a bit of work for someone to grab that BPE implementation and make it work for LLaMA. Less work than rewriting the whole tokenizer from scratch, for sure, but a non trivial amount of work anyway.

> if I am ok with slightly suboptimal efficiency (keeping slightly less tokens than the model supports) ... multiply the length of the result of splitting on spaces by 1.55 for OpenAI and 1.7 for Claude

This sounds reasonable to me. You might also want to consider estimates based on the number of characters. And you also need a fallback for what to do when the user inputs some weird input that doesn't fall inside your safety margin, but instead causes OpenAI API to return an error (maybe in that case you aggressively trim the input and retry?)

I'll answer with an example.

Consider the input string " grabbed".

If we wanted to map this string to tokens by greedily going from left to right and choosing tokens from the vocabulary with the strategy of minimizing the number of tokens, our algorithm would be very simple. We would end up with the following tokenization: [17229, 2580] == [" grab", "bed"]

Surprisingly, the LLaMA tokenizer does not work this way. It actually finds a "worse" tokenization for this input string: [2646, 1327, 287] == [" gra", "bb", "ed"]

The tokenizer arrives at this 3 token output by applying "merges" in a priority order. For example, this is a merge: [" g", "r"] -> " gr". The trained data contains tens of thousands of these merges. When we apply the merges in the priority order, we end up with 3 tokens.

Now you might be thinking, that's easy, we'll just iterate the list of merges and see if any of them apply. Only problem with that approach is that applying a merge can open up a new opportunity to merge something else that wasn't possible before. This right here is the key thing that makes this problem complicated. We can solve this problem by iterating all possible merges from the beginning after every time we apply a merge. This would produce the correct solution. Only problem is: our algorithm is now very slow and takes minutes to run...

Hi HN! I was looking for a tokenizer that would accurately(!) count tokens in browser, and I couldn't find one. So I thought "how hard can it be", and here we are 2 weeks later...

Published now: https://github.com/belladoreai/llama-tokenizer-js

That's what I thought when I started working on this, but it turns out the answer is no! This approach - "minimal mapping of character sequences to numbers" - can be described as a greedy algorithm. Using this approach will often produce correct results, but not always. I can provide an example:

Input string: " grabbed"

Tokenize that with the greedy algorithm, you get [17229, 2580] == [" grab", "bed"]

Tokenize that with actual LLaMA tokenizer, you get [2646, 1327, 287] == [" gra", "bb", "ed"]

Note that the correct tokenizer represents this string with 3 tokens, even though it would be more efficient to represent this string with 2 tokens (yes, those 2 tokens exist in the vocabulary).

LLaMA uses SentencePiece Byte-Pair Encoding for tokenization, and it has many weird quirks like this.

Sure. Check back to this comment after the weekend. I will post it here.

TikToken doesn't provide a tokenizer that's compatible with LLaMA.

Tangentially related to what you ask: LLaMA tokenizer has fallback to byte-level tokens.

You are almost correct, though it doesn't happen at character level, it happens at byte level. Most characters are in LLaMA tokenizer's vocabulary, but all characters aren't. So if you use a character that was uncommon in the training material, it will fall back to byte-level tokens. In most cases 1 character can be represented as 1 byte (and thus 1 byte-level token). However, some characters require more than 1 byte in UTF-8; those characters might end up with as much as 4 tokens.

> The token lists are just text files that consist of the characters base64 encoded followed by the numeric ID. If you want to explore the list you can just download them and decode them yourself.

If you want to look at mappings for individual tokens, sure, but if you actually want to tokenize text that contains more than 1 token, the process is very non trivial. I've been writing my own JavaScript LLaMA tokenizer for several days now (just the encode and decode functions, not training). I hope to release it this weekend. It's currently 400 lines of code + data.