Lesson 50 of 73
A Real Tokenizer from GGUF Metadata
A language model does not read text. It reads a list of integers called token ids, and a tokenizer is the program that converts text into those ids and back. Every model has its own tokenizer, and the engine must use exactly the one the model was trained with. If the ids differ by even one token, the model sees a different prompt than the one it learned from, and its answers get worse.
A GGUF file carries its tokenizer inside the file as metadata: the token strings, a type for each token, the merge list, the name of the pre-tokenizer, and the special token ids. This lesson turns those tokenizer.ggml.* entries into a working byte-level BPE (byte pair encoding) tokenizer in Java. It produces the same token ids as llama.cpp, which this lesson checks against the llama-tokenize tool and against llama.cpp's own tokenizer test files. Afterwards you can explain every step between a string and its token ids for Llama 3 and Qwen2 models, and you can tell why two engines sometimes disagree on a prompt. The lesson ends with Project 17, the GgufTokenizer class.
The table gives the steps of the tokenizer, where each rule comes from, and which example shows it.
| Step | Source of the rule | Example |
|---|---|---|
| Read token, type, and merge arrays | GGUF metadata | 1 |
| Bytes to vocabulary characters | the GPT-2 byte-to-unicode map | 2 |
| Merge priority | position in tokenizer.ggml.merges |
3, 5 |
| Pre-tokenizer regex | tokenizer.ggml.pre, table in src/llama-vocab.cpp |
4 |
| Special tokens | token types 3 (control) and 4 (user-defined) | 6 |
| BOS, EOS, end of generation | metadata keys and llama.cpp defaults | 7 |
| Ids back to text | reverse byte map, streaming UTF-8 | 8 |
| Same ids as llama.cpp | llama-tokenize, models/*.inp and *.out |
9 |
| Speed | a cache of word encodings | 10 |
| SentencePiece vocabularies | tokenizer.ggml.model = "llama" |
11 |
| Project 17 | GgufTokenizer |
12 |
The algorithm itself was built in Building a BPE Tokenizer: training merges, encoding by merge rank, the byte-to-unicode map, and special tokens. Tokens, Vocabularies, and Special Tokens explained why vocabularies look the way they do. This lesson adds the exact rules llama.cpp applies at the pinned commit, read from src/llama-vocab.cpp and src/unicode.cpp, so that a Java engine can feed a GGUF model the same token ids llama.cpp would. The file is read with the FFM (Foreign Function and Memory) loader from Loading GGUF with the FFM API.
Example 1: reading the tokenizer.ggml.* arrays
The tokenizer of a GGUF file lives in a handful of keys. Here is what each one holds:
tokenizer.ggml.modelnames the algorithm:gpt2for byte-level BPE,llamafor SentencePiece.tokenizer.ggml.prenames the pre-tokenizer, the step that cuts text into pieces before BPE runs (Example 4).tokenizer.ggml.tokensholds the token strings in id order.tokenizer.ggml.token_typeholds one type number per token.tokenizer.ggml.mergesholds the merge rules.- The
tokenizer.ggml.*_token_idkeys name special tokens, such as the end-of-sequence token.
This program writes a 9-token vocabulary in that form and reads it back with the cursor from lesson 49 (a cursor is an object that reads values one after another from a memory segment and remembers its position). Look at the printed scalar keys first, then at the id lines, then at the merge list.
import java.io.ByteArrayOutputStream;
import java.lang.foreign.Arena;
import java.lang.foreign.MemorySegment;
import java.lang.foreign.ValueLayout;
import java.nio.ByteOrder;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class TokenizerArrays {
static final ValueLayout.OfInt U32 = ValueLayout.JAVA_INT_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN);
static final ValueLayout.OfLong U64 = ValueLayout.JAVA_LONG_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN);
static byte[] le(long v, int n) { byte[] b = new byte[n]; for (int i = 0; i < n; i++) b[i] = (byte) (v >>> (8 * i)); return b; }
static void str(ByteArrayOutputStream o, String s) { byte[] b = s.getBytes(StandardCharsets.UTF_8); o.writeBytes(le(b.length, 8)); o.writeBytes(b); }
// Reads the key-value pairs of a GGUF file (the cursor from lesson 46, with the types a tokenizer uses).
static Map<String, Object> metadata(MemorySegment s) {
long[] pos = {24};
long nKv = s.get(U64, 16);
Map<String, Object> kv = new LinkedHashMap<>();
for (long i = 0; i < nKv; i++) kv.put(readStr(s, pos), value(s, pos, u32(s, pos)));
return kv;
}
static int u32(MemorySegment s, long[] pos) { int v = s.get(U32, pos[0]); pos[0] += 4; return v; }
static String readStr(MemorySegment s, long[] pos) {
long n = s.get(U64, pos[0]);
String v = new String(s.asSlice(pos[0] + 8, n).toArray(ValueLayout.JAVA_BYTE), StandardCharsets.UTF_8);
pos[0] += 8 + n;
return v;
}
static Object value(MemorySegment s, long[] pos, int type) {
return switch (type) {
case 4 -> u32(s, pos) & 0xFFFFFFFFL;
case 5 -> u32(s, pos);
case 7 -> s.get(ValueLayout.JAVA_BYTE, pos[0]++) != 0;
case 8 -> readStr(s, pos);
case 9 -> {
int elementType = u32(s, pos);
long n = s.get(U64, pos[0]);
pos[0] += 8;
List<Object> list = new ArrayList<>();
for (long i = 0; i < n; i++) list.add(value(s, pos, elementType));
yield list;
}
default -> throw new IllegalStateException("type " + type);
};
}
public static void main(String[] args) {
List<String> tokens = List.of("<|endoftext|>", "a", "b", "c", "Ġ", "ab", "Ġab", "abc", "[PAD0]");
int[] types = {3, 1, 1, 1, 1, 1, 1, 1, 4};
List<String> merges = List.of("a b", "Ġ ab", "ab c");
ByteArrayOutputStream o = new ByteArrayOutputStream();
o.writeBytes("GGUF".getBytes(StandardCharsets.US_ASCII)); o.writeBytes(le(3, 4)); o.writeBytes(le(0, 8)); o.writeBytes(le(6, 8));
str(o, "tokenizer.ggml.model"); o.writeBytes(le(8, 4)); str(o, "gpt2");
str(o, "tokenizer.ggml.pre"); o.writeBytes(le(8, 4)); str(o, "qwen2");
str(o, "tokenizer.ggml.tokens"); o.writeBytes(le(9, 4)); o.writeBytes(le(8, 4)); o.writeBytes(le(tokens.size(), 8));
for (String t : tokens) str(o, t);
str(o, "tokenizer.ggml.token_type"); o.writeBytes(le(9, 4)); o.writeBytes(le(5, 4)); o.writeBytes(le(types.length, 8));
for (int t : types) o.writeBytes(le(t, 4));
str(o, "tokenizer.ggml.merges"); o.writeBytes(le(9, 4)); o.writeBytes(le(8, 4)); o.writeBytes(le(merges.size(), 8));
for (String m : merges) str(o, m);
str(o, "tokenizer.ggml.eos_token_id"); o.writeBytes(le(4, 4)); o.writeBytes(le(0, 4));
try (Arena arena = Arena.ofConfined()) {
MemorySegment seg = arena.allocate(o.size());
MemorySegment.copy(o.toByteArray(), 0, seg, ValueLayout.JAVA_BYTE, 0, o.size());
Map<String, Object> md = metadata(seg);
System.out.println("model " + md.get("tokenizer.ggml.model") + ", pre " + md.get("tokenizer.ggml.pre") + ", eos " + md.get("tokenizer.ggml.eos_token_id")
+ ", bos " + md.get("tokenizer.ggml.bos_token_id") + ", add_bos " + md.get("tokenizer.ggml.add_bos_token"));
List<?> toks = (List<?>) md.get("tokenizer.ggml.tokens"), typ = (List<?>) md.get("tokenizer.ggml.token_type");
String[] typeNames = {"", "normal", "unknown", "control", "user-defined", "unused", "byte"};
for (int id = 0; id < toks.size(); id++) System.out.printf("id %d %-15s %s%n", id, toks.get(id), typeNames[(Integer) typ.get(id)]);
System.out.println("merges " + md.get("tokenizer.ggml.merges"));
}
}
}model gpt2, pre qwen2, eos 0, bos null, add_bos null
id 0 <|endoftext|> control
id 1 a normal
id 2 b normal
id 3 c normal
id 4 Ġ normal
id 5 ab normal
id 6 Ġab normal
id 7 abc normal
id 8 [PAD0] user-defined
merges [a b, Ġ ab, ab c]The first line shows the scalar keys. model gpt2 selects byte-level BPE, and pre qwen2 selects the Qwen2 pre-tokenizer regex (Example 4). eos 0 is the end-of-sequence token id, read from tokenizer.ggml.eos_token_id. The keys tokenizer.ggml.bos_token_id and tokenizer.ggml.add_bos_token are absent from this file, so the map returns null. Example 7 shows the defaults llama.cpp uses in that case.
The id lines show that a vocabulary is two parallel arrays: the token text at index id of tokenizer.ggml.tokens, and its type at the same index of tokenizer.ggml.token_type. The type numbers are those of gguf-py's TokenType: 1 normal, 2 unknown, 3 control, 4 user-defined, 5 unused, 6 byte. Here <|endoftext|> is a control token, [PAD0] is user-defined, and the rest are normal tokens produced by BPE.
The last line is the merge list. Each entry is two token strings separated by one space, in priority order. a b comes first, so a followed by b merges before anything else. Every merge result is itself a token: a + b is ab (id 5), Ġ + ab is Ġab (id 6), and ab + c is abc (id 7). The id of a merged token does not have to equal its merge rank, and in real vocabularies it rarely does.
Example 2: the byte-to-unicode map applied to vocabulary strings
Byte-level BPE works on bytes, so it can encode any text, including emoji and any language. But GGUF stores tokens as text, and some bytes (the newline, the tab, the space) are invisible or awkward in text. The GPT-2 byte-to-unicode map fixes this. It writes each of the 256 byte values as one visible character. For example, the space (byte 32) is written as Ġ, and the newline (byte 10) is written as Ċ. This map was taught in Building a BPE Tokenizer, Example 8.
A tokenizer applies the map in both directions: text to vocabulary characters before lookups, and vocabulary characters to bytes when decoding. This program decodes five real entries of the Qwen2 vocabulary (ids checked with llama-tokenize on ggml-vocab-qwen2.gguf) and encodes two strings. For each line, compare the vocabulary string with the bytes it stands for.
import java.nio.charset.StandardCharsets;
import java.util.HexFormat;
public class VocabStrings {
static final char[] BYTE_TO_CHAR = new char[256];
static final int[] CHAR_TO_BYTE = new int[512];
static { // the GPT-2 map from the BPE lesson
int n = 0;
for (int b = 0; b < 256; b++) {
boolean printable = (b >= '!' && b <= '~') || (b >= 0xA1 && b <= 0xAC) || (b >= 0xAE && b <= 0xFF);
BYTE_TO_CHAR[b] = printable ? (char) b : (char) (256 + n++);
CHAR_TO_BYTE[BYTE_TO_CHAR[b]] = b;
}
}
static String encode(String text) { // text -> vocabulary form
StringBuilder sb = new StringBuilder();
for (byte b : text.getBytes(StandardCharsets.UTF_8)) sb.append(BYTE_TO_CHAR[b & 0xFF]);
return sb.toString();
}
static byte[] decode(String token) { // vocabulary form -> bytes
byte[] out = new byte[token.length()];
for (int i = 0; i < token.length(); i++) out[i] = (byte) CHAR_TO_BYTE[token.charAt(i)];
return out;
}
public static void main(String[] args) {
String[][] vocab = {{"1879", "Ġworld"}, {"198", "Ċ"}, {"90316", "ĠðŁĺĢ"}, {"99489", "ä¸ĸçķĮ"}, {"9707", "Hello"}};
HexFormat hex = HexFormat.ofDelimiter(" ");
for (String[] e : vocab) {
byte[] bytes = decode(e[1]);
String text = new String(bytes, StandardCharsets.UTF_8).replace("\n", "\\n");
System.out.printf("id %5s %-8s -> bytes %-14s -> \"%s\"%n", e[0], e[1], hex.formatHex(bytes), text);
}
System.out.println("encode(\" world\") = " + encode(" world") + ", encode(\"\\t\") = " + encode("\t"));
byte[] half = decode("ðŁ"); // the first 2 of the emoji's 4 bytes
System.out.println("\"ðŁ\" -> bytes " + hex.formatHex(half) + " -> \"" + new String(half, StandardCharsets.UTF_8) + "\"");
}
}id 1879 Ġworld -> bytes 20 77 6f 72 6c 64 -> " world"
id 198 Ċ -> bytes 0a -> "\n"
id 90316 ĠðŁĺĢ -> bytes 20 f0 9f 98 80 -> " 😀"
id 99489 ä¸ĸçķĮ -> bytes e4 b8 96 e7 95 8c -> "世界"
id 9707 Hello -> bytes 48 65 6c 6c 6f -> "Hello"
encode(" world") = Ġworld, encode("\t") = ĉ
"ðŁ" -> bytes f0 9f -> "�"Each vocabulary string decodes to the bytes on its line:
Ġworld(id 1879) is20 77 6f 72 6c 64: the space (byte 32, writtenĠ) and the five ASCII letters, which map to themselves.Ċ(id 198) is the single byte0a, the newline.ĠðŁĺĢ(id 90316) is five bytes: a space and the four UTF-8 bytes of 😀. The Qwen2 vocabulary has a token for "space plus this emoji", so the common case costs one token.ä¸ĸçķĮ(id 99489) is six bytes, the UTF-8 encoding of世界. The vocabulary string looks like Latin-1 noise because each byte became one character.Hello(id 9707) is plain ASCII.
encode(" world") gives Ġworld, which is the string a tokenizer looks up in the vocabulary. The tab becomes ĉ (byte 9 maps to U+0109).
The last line shows why decoding must happen on bytes, not on tokens. ðŁ is the first two bytes of the emoji, f0 9f. As a Java String they are not valid UTF-8, so the decoder produces the replacement character �. A byte-level vocabulary contains many such partial tokens, and generation can produce them one at a time. Example 8 handles this.
Example 3: merge ranks
BPE builds tokens by merging pairs of neighbors, and the order of merges matters. A merge rank is the position of a merge in tokenizer.ggml.merges: rank 0 is the first entry and has the highest priority. The merge list was produced by training, which records merges in the order it discovers them, most frequent pair first. Encoding must replay them in that same order.
This program parses the first eight merges of the real Qwen2 vocabulary into a map from pair to rank. llama.cpp splits each entry at the first space found from position 1 (word.find(' ', 1) in llama_vocab::impl::load), and the program does the same. The program copies this rule exactly so that it splits every entry where llama.cpp does.
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MergeRanks {
public static void main(String[] args) {
// The first 8 entries of tokenizer.ggml.merges in the Qwen2 vocabulary, in file order.
List<String> merges = List.of("Ġ Ġ", "ĠĠ ĠĠ", "i n", "Ġ t", "ĠĠĠĠ ĠĠĠĠ", "e r", "ĠĠ Ġ", "o n");
Map<String, Integer> rank = new HashMap<>();
for (int i = 0; i < merges.size(); i++) {
String m = merges.get(i);
int sp = m.indexOf(' ', 1); // llama.cpp: word.find(' ', 1)
String left = m.substring(0, sp), right = m.substring(sp + 1);
rank.put(left + " " + right, i);
System.out.printf("rank %d: \"%s\" + \"%s\" -> \"%s\"%n", i, left, right, left + right);
}
for (String pair : List.of("i n", "o n", "Ġ t", "t h", "ĠĠ Ġ")) {
Integer r = rank.get(pair);
System.out.println("pair " + pair + ": " + (r == null ? "no merge" : "rank " + r));
}
String a = "Ġ", b = "ĠĠĠ"; // two ways to build four spaces
System.out.println("\"ĠĠ\" + \"ĠĠ\" rank " + rank.get("ĠĠ ĠĠ") + ", \"" + a + "\" + \"" + b + "\" rank " + rank.get(a + " " + b));
}
}rank 0: "Ġ" + "Ġ" -> "ĠĠ"
rank 1: "ĠĠ" + "ĠĠ" -> "ĠĠĠĠ"
rank 2: "i" + "n" -> "in"
rank 3: "Ġ" + "t" -> "Ġt"
rank 4: "ĠĠĠĠ" + "ĠĠĠĠ" -> "ĠĠĠĠĠĠĠĠ"
rank 5: "e" + "r" -> "er"
rank 6: "ĠĠ" + "Ġ" -> "ĠĠĠ"
rank 7: "o" + "n" -> "on"
pair i n: rank 2
pair o n: rank 7
pair Ġ t: rank 3
pair t h: no merge
pair ĠĠ Ġ: rank 6
"ĠĠ" + "ĠĠ" rank 1, "Ġ" + "ĠĠĠ" rank nullThe first eight lines show the parsed merges. Four of the first eight Qwen2 merges build runs of spaces (ĠĠ, ĠĠĠĠ, ĠĠĠĠĠĠĠĠ, ĠĠĠ). Training records merges in the order it creates them, most frequent pair first. These runs, which indented source code is full of, were therefore among the most frequent pairs of Qwen2's training text. Rank 2 is i + n and rank 3 is Ġ + t, the start of very common English words.
The lookup lines show how a tokenizer uses the map. A pair either has a rank (i n is 2, o n is 7) or is not in this short list (t h is not among the first eight; in the full Qwen2 list it has rank 83). Lower ranks are applied first, which is the order in which training discovered them.
The last line shows that a merge is a specific pair of tokens, not a resulting string. Four spaces can be the result of ĠĠ + ĠĠ (rank 1), but Ġ + ĠĠĠ has no rank in the Qwen2 list, so that pair never merges directly.
The real vocabularies show two kinds of merge lists:
- Qwen2 has 151,387 merges, and every merge produces a different token. 151,387 merges plus 256 single-byte tokens are exactly the 151,643 normal tokens.
- The Llama 3 vocabulary (
ggml-vocab-llama-bpe.gguf) has 280,147 merges that produce only 127,744 distinct tokens, and up to 80 different merges produce the same token. Its merge list therefore describes several paths to a token. llama.cpp handles this family with an extra rule shown in Project 17 (ignore_merges).
Example 4: pre-tokenizer regexes by tokenizer.ggml.pre
If BPE ran on a whole document, merges could join the end of one word to the start of the next, and the resulting tokens would be strange. A pre-tokenizer prevents this. Before BPE runs, it splits text into pieces with a regular expression (a pattern language for matching text), and merges never cross a piece boundary. Each model family trained with its own regex, so the engine must use the same one.
llama.cpp selects the regex from tokenizer.ggml.pre in the constructor of llm_tokenizer_bpe in src/llama-vocab.cpp. This program applies three of those regexes to one line. The line has a contraction (We'LL), a number, two newlines, indentation, and code. Compare how the three outputs cut the same text.
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class PreTokenizers {
// From src/llama-vocab.cpp at the pinned commit (the "adapted" forms without (?i:...)).
static final String QWEN2 = "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";
static final String LLAMA3 = "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";
static final String GPT2 = "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)";
static List<String> split(String regex, String text) {
Matcher m = Pattern.compile(regex, Pattern.UNICODE_CHARACTER_CLASS).matcher(text);
List<String> out = new ArrayList<>();
int last = 0;
while (m.find()) {
if (m.start() > last) out.add(text.substring(last, m.start())); // text no alternative matched
out.add(m.group());
last = m.end();
}
if (last < text.length()) out.add(text.substring(last));
return out;
}
static String show(List<String> pieces) {
StringBuilder sb = new StringBuilder();
for (String p : pieces) sb.append('[').append(p.replace(" ", "␣").replace("\n", "\\n")).append(']');
return sb.toString();
}
public static void main(String[] args) {
String text = "We'LL pay 12345 for\n\n int x=42;";
System.out.println("qwen2 : " + show(split(QWEN2, text)));
System.out.println("llama3: " + show(split(LLAMA3, text)));
System.out.println("gpt-2 : " + show(split(GPT2, text)));
System.out.println("qwen2 pieces " + split(QWEN2, text).size() + ", llama3 " + split(LLAMA3, text).size() + ", gpt-2 " + split(GPT2, text).size());
}
}qwen2 : [We]['LL][␣pay][␣][1][2][3][4][5][␣for][\n\n][␣][␣int][␣x][=][4][2][;]
llama3: [We]['LL][␣pay][␣][123][45][␣for][\n\n][␣][␣int][␣x][=][42][;]
gpt-2 : [We]['][LL][␣pay][␣12345][␣for][\n\n␣][␣int][␣x][=][42][;]
qwen2 pieces 18, llama3 14, gpt-2 12The three regexes split the same text differently:
- Numbers. Qwen2 uses
\p{N}, one digit per piece, so12345becomes five pieces[1][2][3][4][5], and42becomes[4][2]. Llama 3 uses\p{N}{1,3}, so12345becomes[123][45]. GPT-2 uses?\p{N}+, so the whole number and its leading space are one piece,[␣12345]. - Contractions. The Qwen2 and Llama 3 regexes match
'LLas one piece through'[lL][lL]. The source keeps the original regex fromtokenizer.json, with the case-insensitive group(?i:'s|'t|...), as a comment, and uses an "adapted" form that spells out both cases as character classes. The GPT-2 regex is case-sensitive, so'LLfalls apart into[']and[LL]. - Whitespace. For two spaces before
int, Qwen2 and Llama 3 produce[␣]and[␣int]. The alternative\s+(?!\S)takes whitespace only up to the last space before a non-space, so the final space stays attached to the word. GPT-2 has no[\r\n]alternatives, so its\s+(?!\S)combines the two newlines and the first space into one piece,[\n\n␣].
The piece counts are 18, 14, and 12. More pieces mean more tokens for the same text. Single-digit splitting costs Qwen2 one token per digit of every number. This makes arithmetic on digits more regular for the model, at the cost of longer prompts.
Two Java details matter for matching llama.cpp:
- The pattern is compiled with
Pattern.UNICODE_CHARACTER_CLASS. By default Java's\smatches only ASCII whitespace, while llama.cpp's whitespace set insrc/unicode-data.cpp(unicode_set_whitespace) contains the Unicode white space characters such as U+00A0 and U+3000. - The
splitmethod keeps text that no alternative matches as its own piece. This is how llama.cpp treats gaps between matches (the GPT-2 regex has such gaps).
Example 5: encoding a word by merge rank with a priority queue
Now the tokenizer needs to apply merges to one piece. The procedure has three steps. Start with the piece's characters (one per byte after the byte-to-unicode map). Find the adjacent pair with the lowest rank. Merge it, and repeat until no pair has a rank.
A naive version rescans the whole word after each merge. llama.cpp is faster. It keeps candidate pairs in a priority queue, a collection that always gives out its smallest element first. The queue is ordered by rank, with ties broken by the leftmost position (llm_bigram_bpe::comparator). It also keeps the symbols in a linked list, so each merge changes only its two neighbors.
This program traces that loop on three words with a small merge table. Read each trace as a story: which pair merged, and what the word looks like afterwards.
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
public class MergeQueue {
record Pair(int rank, int left, int right, String text) {}
public static void main(String[] args) {
Map<String, Integer> rank = Map.of("e r", 0, "l o", 1, "lo w", 2, "low er", 3, "e s", 4, "es t", 5, "low est", 6, "n e", 7, "w er", 8);
for (String word : List.of("lower", "lowest", "newer")) {
String[] sym = new String[word.length()];
int[] prev = new int[sym.length], next = new int[sym.length];
for (int i = 0; i < sym.length; i++) { sym[i] = String.valueOf(word.charAt(i)); prev[i] = i - 1; next[i] = i + 1 < sym.length ? i + 1 : -1; }
PriorityQueue<Pair> queue = new PriorityQueue<>(Comparator.comparingInt(Pair::rank).thenComparingInt(Pair::left));
for (int i = 0; i + 1 < sym.length; i++) {
Integer r = rank.get(sym[i] + " " + sym[i + 1]);
if (r != null) queue.add(new Pair(r, i, i + 1, sym[i] + sym[i + 1]));
}
System.out.println(word + ": queue starts with " + queue.size() + " candidate pairs");
while (!queue.isEmpty()) {
Pair p = queue.poll();
if (sym[p.left()].isEmpty() || sym[p.right()].isEmpty() || !(sym[p.left()] + sym[p.right()]).equals(p.text())) {
System.out.println(" skip stale rank " + p.rank() + " \"" + p.text() + "\"");
continue;
}
sym[p.left()] = p.text(); // merge right into left
sym[p.right()] = "";
next[p.left()] = next[p.right()];
if (next[p.right()] >= 0) prev[next[p.right()]] = p.left();
StringBuilder now = new StringBuilder();
for (int i = 0; i != -1; i = next[i]) now.append('[').append(sym[i]).append(']');
System.out.println(" merge rank " + p.rank() + " -> " + now);
for (int[] lr : new int[][] {{prev[p.left()], p.left()}, {p.left(), next[p.left()]}}) {
if (lr[0] < 0 || lr[1] < 0) continue;
Integer r = rank.get(sym[lr[0]] + " " + sym[lr[1]]);
if (r != null) queue.add(new Pair(r, lr[0], lr[1], sym[lr[0]] + sym[lr[1]]));
}
}
}
}
}lower: queue starts with 2 candidate pairs
merge rank 0 -> [l][o][w][er]
merge rank 1 -> [lo][w][er]
merge rank 2 -> [low][er]
merge rank 3 -> [lower]
skip stale rank 8 "wer"
lowest: queue starts with 2 candidate pairs
merge rank 1 -> [lo][w][e][s][t]
merge rank 2 -> [low][e][s][t]
merge rank 4 -> [low][es][t]
merge rank 5 -> [low][est]
merge rank 6 -> [lowest]
newer: queue starts with 2 candidate pairs
merge rank 0 -> [n][e][w][er]
merge rank 7 -> [ne][w][er]
merge rank 8 -> [ne][wer]For lower, the queue starts with two candidates: e r (rank 0) and l o (rank 1). The trace shows four merges in rank order: er, then lo, then low, then low + er = lower. After each merge, the program adds the new pairs on both sides of the merged symbol. Merging e r created the candidate w er (rank 8).
The line skip stale rank 8 "wer" shows why a queue entry is checked before use. By the time w er comes out of the queue, w has already been merged into low, so the left symbol no longer is w. The entry is stale: it describes a pair that no longer exists. The loop compares the current text of both symbols with the text stored in the entry, and skips the entry when they differ, as llama.cpp does with if (left_token + right_token != bigram.text) continue;. Removing stale entries from the queue would cost more than skipping them.
For lowest, the merges lo, low, es, est lead to low + est = lowest at rank 6. For newer, er comes first (rank 0), then ne (rank 7), then w er (rank 8). No merge joins ne with wer, so the result is two symbols, [ne][wer]. Each final symbol is then looked up in the vocabulary to get its id.
Why the queue is worth it: each merge does a constant amount of list work plus at most two queue insertions, each costing log n for n queue entries. A piece of n characters therefore takes about n log n steps, instead of the n * n of rescanning the whole word after every merge.
Example 6: special and control tokens, and splitting text on them
Chat models use special tokens such as <|im_start|> to mark where a message begins or ends. These tokens must have exactly one id each. If BPE ran on the text <|im_start|>, it would produce many small tokens instead. The tokenizer therefore cuts special tokens out of the text first, before the pre-tokenizer sees it.
llama.cpp collects every token whose type is control (3), user-defined (4), or unknown (2). It sorts them by text length, longest first, and splits the text on each in turn (tokenizer_st_partition). The parse_special flag decides whether control tokens are recognized in the text. User-defined tokens are always recognized. This program uses four real ids from the Qwen2 vocabulary. It runs the same chat string with parse_special true and false. Compare the two outputs, and read the last line to see the order in which special tokens are tried.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class SpecialSplit {
static final int CONTROL = 3, USER_DEFINED = 4;
record Special(int id, String text, int type) {}
static final List<Special> SPECIALS = new ArrayList<>(List.of(
new Special(151643, "<|endoftext|>", CONTROL), new Special(151644, "<|im_start|>", CONTROL),
new Special(151645, "<|im_end|>", CONTROL), new Special(151646, "[PAD151646]", USER_DEFINED)));
static {
SPECIALS.sort(Comparator.comparingInt((Special s) -> s.text().length()).reversed()); // longest first
}
// Fragments are either String (text still to tokenize) or Integer (a finished token id).
static List<Object> partition(String text, boolean parseSpecial) {
List<Object> fragments = new ArrayList<>(List.of(text));
for (Special s : SPECIALS) {
if (!parseSpecial && s.type() != USER_DEFINED) continue; // user-defined tokens always split
List<Object> next = new ArrayList<>();
for (Object f : fragments) {
if (!(f instanceof String raw)) { next.add(f); continue; }
int from = 0, at;
while ((at = raw.indexOf(s.text(), from)) >= 0) {
if (at > from) next.add(raw.substring(from, at));
next.add(s.id());
from = at + s.text().length();
}
if (from < raw.length()) next.add(raw.substring(from));
}
fragments = next;
}
return fragments;
}
static String show(List<Object> fragments) {
StringBuilder sb = new StringBuilder();
for (Object f : fragments) sb.append(f instanceof String s ? "\"" + s.replace("\n", "\\n") + "\" " : "<" + f + "> ");
return sb.toString().trim();
}
public static void main(String[] args) {
String chat = "<|im_start|>user\nHi[PAD151646]<|im_end|>\n<|im_start|>assistant\n";
System.out.println("parse_special=true : " + show(partition(chat, true)));
System.out.println("parse_special=false: " + show(partition(chat, false)));
System.out.println("order tried: " + SPECIALS.stream().map(Special::text).toList());
}
}parse_special=true : <151644> "user\nHi" <151646> <151645> "\n" <151644> "assistant\n"
parse_special=false: "<|im_start|>user\nHi" <151646> "<|im_end|>\n<|im_start|>assistant\n"
order tried: [<|endoftext|>, <|im_start|>, [PAD151646], <|im_end|>]With parse_special=true, the chat string becomes seven fragments. The control tokens 151644 (<|im_start|>) and 151645 (<|im_end|>) are finished ids. The user-defined token 151646 ([PAD151646]) is a finished id as well. The text between them ("user\nHi", "\n", "assistant\n") goes on through the pre-tokenizer and BPE.
With parse_special=false, the control token texts stay as plain text, so <|im_start|> would be encoded as the characters <, |, im, and so on. The user-defined token [PAD151646] is still cut out. A comment in llama.cpp's source gives the reason: user-defined tokens are "still pre-tokenized before everything else", as in the Hugging Face tokenizers library.
The choice of parse_special is a security decision for an agent. A chat template is rendered with parse_special=true, because its control tokens must become control ids. Text from a user, a file, or a web page should be encoded with parse_special=false. Otherwise a file that contains the characters <|im_end|> could end the current message and start a forged one.
The last line shows the order in which the specials are tried: by length, <|endoftext|> (13 characters) before <|im_start|> (12), [PAD151646] (11), and <|im_end|> (10). Trying longer texts first matters when one special token's text contains another's.
Example 7: BOS and EOS rules from metadata
Two special tokens deserve a closer look. BOS (beginning of sequence) is a token that some models expect at the very start of every prompt. EOS (end of sequence) is a token the model produces when it has finished its answer. The tokenizer must know whether to add BOS, and the generation loop must know which ids mean "stop".
Both depend on metadata keys and on defaults that llama.cpp derives from the tokenizer model and pre-tokenizer. The rules from src/llama-vocab.cpp, in order:
- Byte-level BPE starts with
add_bos = false. - The Llama 3 family of pre-tokenizers (
llama3,llama-v3,llama-bpe,falcon3, and a few others) sets it to true. - SentencePiece (
llama) defaults to true. tokenizer.ggml.add_bos_token, when present, overrides everything.
This program applies those rules to five metadata maps and computes an end-of-generation set. Check each output line against the rules above.
import java.util.List;
import java.util.Map;
import java.util.TreeSet;
public class BosEosRules {
static final List<String> EOG_TEXTS = List.of("<|eot_id|>", "<|im_end|>", "<|end|>", "<end_of_turn>", "<|endoftext|>",
"</s>", "<|eom_id|>", "<EOT>", "<|end_of_text|>", "<eos>", "<|fim_pad|>", "<|repo_name|>", "<|file_sep|>");
// llama.cpp: BPE defaults to add_bos = false, the llama3 family of pre-tokenizers sets it to true,
// SentencePiece (model "llama") defaults to true, and tokenizer.ggml.add_bos_token overrides all of them.
static boolean addBos(Map<String, Object> md) {
if (md.get("tokenizer.ggml.add_bos_token") instanceof Boolean b) return b;
if ("llama".equals(md.get("tokenizer.ggml.model"))) return true;
return List.of("llama3", "llama-v3", "llama-bpe", "falcon3").contains(md.get("tokenizer.ggml.pre"));
}
static TreeSet<Integer> eog(List<String> tokens, int eos) {
TreeSet<Integer> ids = new TreeSet<>();
for (int id = 0; id < tokens.size(); id++) if (EOG_TEXTS.contains(tokens.get(id))) ids.add(id);
if (eos >= 0) ids.add(eos);
return ids;
}
public static void main(String[] args) {
Map<String, Map<String, Object>> files = new java.util.LinkedHashMap<>();
files.put("qwen2 vocab", Map.of("tokenizer.ggml.model", "gpt2", "tokenizer.ggml.pre", "qwen2"));
files.put("llama-bpe vocab", Map.of("tokenizer.ggml.model", "gpt2", "tokenizer.ggml.pre", "llama-bpe"));
files.put("llama-spm vocab", Map.of("tokenizer.ggml.model", "llama", "tokenizer.ggml.add_bos_token", true));
files.put("qwen2 + key true", Map.of("tokenizer.ggml.model", "gpt2", "tokenizer.ggml.pre", "qwen2", "tokenizer.ggml.add_bos_token", true));
files.put("llama-bpe + key false", Map.of("tokenizer.ggml.model", "gpt2", "tokenizer.ggml.pre", "llama-bpe", "tokenizer.ggml.add_bos_token", false));
files.forEach((name, md) -> System.out.printf("%-22s add_bos %s%n", name, addBos(md)));
List<String> vocab = List.of("<|endoftext|>", "<|im_start|>", "<|im_end|>", "</s>", "hello");
System.out.println("end-of-generation ids, eos = 0: " + eog(vocab, 0));
}
}qwen2 vocab add_bos false
llama-bpe vocab add_bos true
llama-spm vocab add_bos true
qwen2 + key true add_bos true
llama-bpe + key false add_bos false
end-of-generation ids, eos = 0: [0, 2, 3]The five lines follow the rules in order:
qwen2 vocab add_bos false: byte-level BPE with the Qwen2 pre-tokenizer and no key. TheHello worldprompt of The Forward Pass in Java tokenizes to[9707, 1879]with no BOS for this reason, andllama-eval-callbackprinted the same two ids.llama-bpe vocab add_bos true: the Llama 3 pre-tokenizer sets it, which is whyllama-tokenizeputs 128000 (<|begin_of_text|>) first in Example 9.llama-spm vocab add_bos true: SentencePiece vocabularies add<s>.qwen2 + key trueandllama-bpe + key false: the key wins in both directions.
A wrong BOS rule produces a prompt that differs from training by one token, and the model's output changes noticeably, so this rule is worth matching exactly.
The last line is the end-of-generation (EOG) set: the ids that stop generation. The EOS id is always in it. llama.cpp also adds tokens found by their text: <|eot_id|>, <|im_end|>, <|endoftext|>, </s>, <end_of_turn>, and others in a fixed list in llama_vocab::impl::load. In the example vocabulary, ids 0 (<|endoftext|>), 2 (<|im_end|>), and 3 (</s>) qualify.
When such a token is not marked as control in the file, llama.cpp marks it as control and logs a warning. The tiny random model's log contains one: control-looking token: 128247 '</s>' was not control-type; this is probably a bug in the model. its type will be overridden. The Java tokenizer applies the same override, because control status also changes decoding: tokenBytes in Project 17 returns no text for a control token unless special output is requested.
Example 8: decoding with a streaming UTF-8 decoder
Decoding maps each id to its bytes and the bytes to text. This looks simple, but there is a catch. UTF-8 writes one character as 1 to 4 bytes, and a byte-level token can end in the middle of a character. The emoji 😀 is four bytes, and BPE may put its first two bytes in one token and its last two in the next. Decoding each token on its own then breaks the character.
A streaming decoder solves this. It keeps the incomplete bytes of one token and completes them with the next. This program feeds four tokens, the first two of which split an emoji, through new String(bytes, UTF_8) per token and through a CharsetDecoder (Java's incremental text decoder) that keeps leftover bytes. Compare the per-token column with the streamed column on each line.
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.CoderResult;
import java.nio.charset.StandardCharsets;
import java.util.List;
public class StreamingDecode {
static final class Utf8Stream {
private final CharsetDecoder decoder = StandardCharsets.UTF_8.newDecoder();
private ByteBuffer pending = ByteBuffer.allocate(0);
String push(byte[] bytes) {
ByteBuffer in = ByteBuffer.allocate(pending.remaining() + bytes.length).put(pending).put(bytes).flip();
CharBuffer out = CharBuffer.allocate(in.remaining() + 1);
CoderResult r;
while ((r = decoder.decode(in, out, false)).isError()) { // invalid bytes become U+FFFD
in.position(in.position() + r.length());
out.put('\uFFFD');
}
pending = in.slice(); // an incomplete sequence waits
return out.flip().toString();
}
}
public static void main(String[] args) {
// " 😀 ok" split the way byte-level BPE can split it: the emoji's 4 bytes across two tokens.
List<byte[]> tokens = List.of(new byte[] {' ', (byte) 0xF0, (byte) 0x9F}, new byte[] {(byte) 0x98, (byte) 0x80},
" ok".getBytes(StandardCharsets.UTF_8), new byte[] {(byte) 0xFF, 'x'});
Utf8Stream stream = new Utf8Stream();
StringBuilder naive = new StringBuilder(), streamed = new StringBuilder();
for (byte[] t : tokens) {
String a = new String(t, StandardCharsets.UTF_8), b = stream.push(t);
naive.append(a);
streamed.append(b);
System.out.printf("token of %d bytes: per-token \"%s\" (%d chars), streamed \"%s\" (%d chars)%n", t.length, a, a.length(), b, b.length());
}
System.out.println("per-token result: \"" + naive + "\"");
System.out.println("streamed result : \"" + streamed + "\"");
}
}token of 3 bytes: per-token " �" (2 chars), streamed " " (1 chars)
token of 2 bytes: per-token "��" (2 chars), streamed "😀" (2 chars)
token of 3 bytes: per-token " ok" (3 chars), streamed " ok" (3 chars)
token of 2 bytes: per-token "�x" (2 chars), streamed "�x" (2 chars)
per-token result: " ��� ok�x"
streamed result : " 😀 ok�x"The first token holds a space and the first two bytes of 😀. Decoded on its own, it becomes " �": the space and one replacement character for the two orphan bytes. The streaming decoder returns only " " and keeps f0 9f for later.
The second token holds the last two bytes, 98 80. On its own, it decodes to ��, two replacement characters. The streaming decoder prepends the two kept bytes, gets the complete sequence f0 9f 98 80, and returns 😀. That is 2 Java chars (a surrogate pair), as the line shows.
The third token, " ok", is complete ASCII, so both methods agree.
The fourth token holds ff and x. The byte ff never appears in valid UTF-8, so both methods produce � followed by x. The streaming decoder reports such bytes as malformed (CoderResult.isError()), skips them, and writes U+FFFD, so a bad byte cannot block the output forever.
The final lines compare the full results. The per-token text contains three replacement characters in place of the emoji, while the streamed text is exactly 😀 ok�x. A chat client that prints tokens as they arrive needs the streaming form. llama-server solves the same problem on its side: while the generated text ends in an incomplete UTF-8 sequence (validate_utf8 in tools/server/server-common.cpp), it holds the bytes back instead of streaming them. This is why the chunks of The OpenAI API and Streaming always contain whole characters.
Example 9: matching llama-tokenize on the vocabulary GGUFs
A tokenizer port is only correct if it gives the same ids as the reference. The tests that matter compare the Java tokenizer with llama.cpp on real vocabularies. The program below uses GgufModel from lesson 49 and GgufTokenizer from Project 17 (Example 12), saved in the same directory. It encodes three texts (English with a number, Java code, and mixed scripts) with the Qwen2 and Llama 3 vocabulary files that ship in llama.cpp's models directory.
It then runs llama.cpp's own tokenizer test cases. Each vocabulary has an .inp file with 46 texts separated by __ggml_vocab_test__ lines and an .out file with the expected ids. tests/test-tokenizer-0.cpp checks them without BOS and without special parsing, and the Java program does the same. The program needs those files, so it is java,ignore. It was run with java MatchLlamaTokenize.java llama.cpp/models.
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.List;
public class MatchLlamaTokenize {
public static void main(String[] args) throws Exception {
Path models = Path.of(args[0]); // llama.cpp/models
List<String> texts = List.of("Hello world, it's 2026!", "for (int i = 0; i < n; i++) {\n sum += a[i];\n}",
"Ünïcödé: 世界 😀 привет");
for (String vocab : List.of("qwen2", "llama-bpe")) {
try (GgufModel m = GgufModel.open(models.resolve("ggml-vocab-" + vocab + ".gguf"))) {
GgufTokenizer tok = new GgufTokenizer(m.metadata());
for (String text : texts) System.out.println(vocab + " " + tok.encode(text, true, true));
// llama.cpp's own test cases: input texts and expected ids, encoded without BOS and without special parsing
Path base = models.resolve("ggml-vocab-" + vocab + ".gguf");
String[] inputs = Files.readString(Path.of(base + ".inp")).split("\n__ggml_vocab_test__\n", -1);
List<String> expected = Files.readAllLines(Path.of(base + ".out"));
int pass = 0;
for (int i = 0; i < expected.size(); i++) {
StringBuilder got = new StringBuilder();
for (int id : tok.encode(inputs[i], false, false)) got.append(' ').append(id);
if (got.toString().equals(expected.get(i))) pass++;
}
System.out.println(vocab + " test cases: " + pass + "/" + expected.size());
}
}
}
}Output of the Java program (the vocabulary files fix the ids, so nothing depends on the machine):
qwen2 [9707, 1879, 11, 432, 594, 220, 17, 15, 17, 21, 0]
qwen2 [1958, 320, 396, 600, 284, 220, 15, 26, 600, 366, 308, 26, 600, 2457, 341, 262, 2629, 1421, 264, 989, 935, 92]
qwen2 [52491, 77, 37572, 66, 2956, 128505, 25, 220, 99489, 90316, 12281, 26991, 8178]
qwen2 test cases: 46/46
llama-bpe [128000, 9906, 1917, 11, 433, 596, 220, 2366, 21, 0]
llama-bpe [128000, 2000, 320, 396, 602, 284, 220, 15, 26, 602, 366, 308, 26, 602, 2516, 341, 262, 2694, 1447, 264, 1004, 947, 92]
llama-bpe [128000, 53591, 77, 38672, 66, 3029, 67, 978, 25, 127365, 91416, 108349, 8341]
llama-bpe test cases: 46/46The same texts through the pinned llama.cpp build:
for v in qwen2 llama-bpe; do
llama-tokenize -m models/ggml-vocab-$v.gguf -p "Hello world, it's 2026!" --ids --log-disable
llama-tokenize -m models/ggml-vocab-$v.gguf -p $'for (int i = 0; i < n; i++) {\n sum += a[i];\n}' --ids --log-disable
llama-tokenize -m models/ggml-vocab-$v.gguf -p "Ünïcödé: 世界 😀 привет" --ids --log-disable
doneOutput of llama-tokenize (pinned build, llama-tokenize parses special tokens and adds BOS when the vocabulary asks for it):
[9707, 1879, 11, 432, 594, 220, 17, 15, 17, 21, 0]
[1958, 320, 396, 600, 284, 220, 15, 26, 600, 366, 308, 26, 600, 2457, 341, 262, 2629, 1421, 264, 989, 935, 92]
[52491, 77, 37572, 66, 2956, 128505, 25, 220, 99489, 90316, 12281, 26991, 8178]
[128000, 9906, 1917, 11, 433, 596, 220, 2366, 21, 0]
[128000, 2000, 320, 396, 602, 284, 220, 15, 26, 602, 366, 308, 26, 602, 2516, 341, 262, 2694, 1447, 264, 1004, 947, 92]
[128000, 53591, 77, 38672, 66, 3029, 67, 978, 25, 127365, 91416, 108349, 8341]All six id lists are identical to the Java lines above, and both vocabularies pass all 46 of llama.cpp's test cases. The same test passes for the gpt-2, starcoder, and refact vocabularies, which use the GPT-2 regex and the two-regex digit splitting of StarCoder.
The ids show the rules of the earlier examples at work:
- BOS. The Llama 3 lines start with 128000 (
<|begin_of_text|>). The Qwen2 lines have no BOS (Example 7). - Digits. In Qwen2,
2026is17, 15, 17, 21, one token per digit (the digits 0 to 9 are ids 15 to 24). In Llama 3 it is2366, 21, the pieces202and6from\p{N}{1,3}. - Code.
llama-tokenizewithout--idsprints the Qwen2 pieces of the code line asfor,(,int,i,=,0,;, and so on.++)(id 2457) is a single token. The newline joins the piece{through the[\r\n]*at the end of the punctuation alternative, giving token 341. The four spaces of indentation become a three-space token (262) and the space in front ofsum(2629), which is the whitespace rule from Example 4. - Unicode.
世界is the single token 99489 and😀is 90316, the entries decoded in Example 2. Accented letters cost more:Ünïcödétakes six Qwen2 tokens.
When a Java tokenizer disagrees with llama.cpp, the cause is usually one of three things: a different regex (or a regex without UNICODE_CHARACTER_CLASS), a missing BOS rule, or special-token parsing applied to the wrong text.
Example 10: caching word encodings
A prompt contains the same words many times (int, i, ;, return). The BPE result of a piece depends only on the piece. A cache, a table that remembers earlier results, can therefore map each piece to its ids and skip the merge loop for repeated pieces.
This program counts merge steps for a repetitive code text with and without a cache. It counts steps instead of measuring time, so the output is the same on every machine.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class WordCache {
record Pair(int rank, int left, int right, String text) {}
static final Map<String, Integer> RANK = new HashMap<>();
static int pops;
// Merges that build each listed word left to right: "r e", "re t", "ret u", ...
static void addWord(String w) {
String acc = w.substring(0, 1);
for (int i = 1; i < w.length(); i++) {
RANK.putIfAbsent(acc + " " + w.charAt(i), RANK.size());
acc += w.charAt(i);
}
}
static List<String> bpe(String word) {
List<String> sym = new ArrayList<>();
for (char c : word.toCharArray()) sym.add(String.valueOf(c));
PriorityQueue<Pair> q = new PriorityQueue<>(Comparator.comparingInt(Pair::rank).thenComparingInt(Pair::left));
while (true) { // a simple version: rebuild the queue after each merge
q.clear();
for (int i = 0; i + 1 < sym.size(); i++) {
Integer r = RANK.get(sym.get(i) + " " + sym.get(i + 1));
if (r != null) q.add(new Pair(r, i, i + 1, sym.get(i) + sym.get(i + 1)));
}
if (q.isEmpty()) return sym;
Pair p = q.poll();
pops++;
sym.set(p.left(), p.text());
sym.remove(p.right());
}
}
public static void main(String[] args) {
for (String w : List.of("Ġreturn", "Ġvalue", "Ġint", "Ġi", ";", "Ġ+=", "Ġ=", "Ġ0")) addWord(w);
String code = "int i = 0; int value = 0; value += i; return value; ".repeat(50);
Matcher m = Pattern.compile(" ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)").matcher(code);
List<String> words = new ArrayList<>();
while (m.find()) words.add(m.group().replace(' ', 'Ġ'));
int tokens = 0;
for (String w : words) tokens += bpe(w).size();
System.out.println(words.size() + " words, " + tokens + " tokens, no cache: " + pops + " merges");
pops = 0;
Map<String, List<String>> cache = new HashMap<>();
int hits = 0;
for (String w : words) {
if (cache.containsKey(w)) hits++;
else cache.put(w, bpe(w));
}
System.out.println("with cache: " + pops + " merges, " + cache.size() + " distinct words, " + hits + " hits");
}
}851 words, 853 tokens, no cache: 1747 merges
with cache: 19 merges, 10 distinct words, 841 hitsThe text is one line of code repeated 50 times. The pre-tokenizer cuts it into 851 pieces, which BPE turns into 853 tokens. Every piece becomes one token except the very first int, which has no leading space. The merge table only builds Ġint, so int stays three single-character tokens.
Without a cache, encoding performs 1,747 merges, about two per piece. With a cache, only the first occurrence of each of the 10 distinct pieces runs BPE (19 merges in total), and the other 841 pieces are cache hits. The work drops by a factor of about 92 for this text.
Real text repeats less than this, but code and chat prompts still repeat their common pieces heavily. The Project 17 tokenizer keeps a cache of up to 10,000 pieces in an access-ordered LinkedHashMap that drops the least recently used entry when full, so memory stays bounded when the tokenizer encodes long documents.
Example 11: SentencePiece-style vocabularies in short
Some models do not use byte-level BPE. Older Llama, Mistral, and Gemma models use SentencePiece vocabularies (tokenizer.ggml.model = "llama", called SPM in llama.cpp). They differ from byte-level BPE in four ways:
- Spaces are written as
▁(U+2581). - A
▁is added before the text. - Merges are chosen by a per-token score from
tokenizer.ggml.scoresinstead of a merge list. - Characters missing from the vocabulary fall back to byte tokens named
<0x00>to<0xFF>(token type 6).
This toy program follows the rule of llama.cpp's llm_tokenizer_spm_session: repeatedly merge the adjacent pair whose concatenation is a token with the highest score. Run it on one text with a known word and one with an unknown character.
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
public class SentencePieceStyle {
// A toy SPM vocabulary: text, score. Byte tokens <0x00>..<0xFF> would follow in a real one.
static final Map<String, Float> VOCAB = Map.ofEntries(Map.entry("▁", -1f), Map.entry("▁H", -9f), Map.entry("▁He", -7f),
Map.entry("▁Hel", -6.8f), Map.entry("▁Hello", -3f), Map.entry("lo", -5f), Map.entry("▁w", -6f), Map.entry("or", -5.5f), Map.entry("▁wor", -4f),
Map.entry("ld", -4.5f), Map.entry("▁world", -2f), Map.entry("H", -10f), Map.entry("e", -10f), Map.entry("l", -10f),
Map.entry("o", -10f), Map.entry("w", -10f), Map.entry("r", -10f), Map.entry("d", -10f));
static List<String> tokenize(String text) {
String s = "▁" + text.replace(" ", "▁"); // add_space_prefix, then escape spaces
List<String> sym = new ArrayList<>();
s.codePoints().forEach(cp -> sym.add(new String(Character.toChars(cp))));
while (true) { // merge the pair whose result has the highest score
int best = -1;
float bestScore = Float.NEGATIVE_INFINITY;
for (int i = 0; i + 1 < sym.size(); i++) {
Float score = VOCAB.get(sym.get(i) + sym.get(i + 1));
if (score != null && score > bestScore) { best = i; bestScore = score; }
}
if (best < 0) break;
sym.set(best, sym.get(best) + sym.get(best + 1));
sym.remove(best + 1);
}
List<String> out = new ArrayList<>();
for (String piece : sym) {
if (VOCAB.containsKey(piece)) out.add(piece);
else for (byte b : piece.getBytes(StandardCharsets.UTF_8)) out.add(String.format("<0x%02X>", b & 0xFF)); // byte fallback
}
return out;
}
public static void main(String[] args) {
System.out.println(tokenize("Hello world"));
System.out.println(tokenize("Hello wörld"));
}
}[▁Hello, ▁world]
[▁Hello, ▁w, <0xC3>, <0xB6>, r, ld]For Hello world, the text becomes ▁Hello▁world. The highest-scoring pairs merge first: ld, lo, or, ▁w, then ▁wor, then ▁world (score -2). The remaining ▁ H e l lo merge through ▁H, ▁He, ▁Hel to ▁Hello. The result is two pieces, [▁Hello, ▁world].
For Hello wörld, the ö is not in the toy vocabulary and no pair containing it is a token, so it stays alone and falls back to its two UTF-8 bytes <0xC3> and <0xB6>. The r remains a single-character piece, and ld merges as before.
The real Llama 2 vocabulary in models/ggml-vocab-llama-spm.gguf behaves the same way. llama-tokenize -m models/ggml-vocab-llama-spm.gguf -p "Hello wörld 😀" --log-disable on the pinned build prints:
1 -> '<s>'
15043 -> ' Hello'
281 -> ' w'
1340 -> 'ör'
430 -> 'ld'
29871 -> ' '
243 -> '�'
162 -> '�'
155 -> '�'
131 -> '�'<s> (id 1) is the BOS that SentencePiece vocabularies add. ▁Hello and ▁w are printed with a space, because decoding turns ▁ back into a space. The real vocabulary has ör as a token, so it needs no fallback there. The emoji is not in the 32,000-token vocabulary, so it becomes four byte tokens, 243, 162, 155, and 131. These are <0xF0>, <0x9F>, <0x98>, and <0x80> (the byte tokens start at id 3, so byte b is id b + 3). llama-tokenize prints each of them as �, because a single byte of a 4-byte character is not printable text.
The engine in this section supports byte-level BPE only, which covers Llama 3, Qwen2 and Qwen3, and most current models. The GgufTokenizer constructor rejects other tokenizer.ggml.model values with a clear message instead of tokenizing wrongly.
Example 12: Project 17, the GgufTokenizer class
Project 17 combines Examples 2 to 10 into one class, GgufTokenizer. Its parts are:
- The constructor takes the metadata map that
GgufModel.metadata()returns. It builds the token and merge maps, selects the pre-tokenizer regexes fromtokenizer.ggml.pre, applies llama.cpp's BOS default andignore_mergesrule, marks end-of-generation tokens, and collects special tokens. encode(text, addSpecial, parseSpecial)mirrorsllama_tokenize.tokenBytesanddecodeturn ids back into bytes and text.Utf8Streamis the streaming decoder of Example 8.
The main method is a self-contained test. It writes a synthetic vocabulary to a GGUF file: 256 single-byte tokens with ids equal to their byte values, merges that build a few words, three control tokens, and one user-defined token. It reads the file back with a small reader (MiniGguf, which returns the same value types as GgufModel). Then it checks encoding, decoding, special tokens, streaming, and a round trip on random strings.
import java.io.ByteArrayOutputStream;
import java.lang.foreign.Arena;
import java.lang.foreign.MemorySegment;
import java.lang.foreign.ValueLayout;
import java.nio.ByteOrder;
import java.nio.channels.FileChannel;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.ByteBuffer;
import java.nio.CharBuffer;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.CoderResult;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public final class GgufTokenizer {
static final int NORMAL = 1, UNKNOWN = 2, CONTROL = 3, USER_DEFINED = 4, UNUSED = 5, BYTE = 6;
// Pre-tokenizer regexes from src/llama-vocab.cpp, by tokenizer.ggml.pre.
static final String QWEN2 = "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";
static final String LLAMA3 = "(?:'[sS]|'[tT]|'[rR][eE]|'[vV][eE]|'[mM]|'[lL][lL]|'[dD])|[^\\r\\n\\p{L}\\p{N}]?\\p{L}+|\\p{N}{1,3}| ?[^\\s\\p{L}\\p{N}]+[\\r\\n]*|\\s*[\\r\\n]+|\\s+(?!\\S)|\\s+";
static final String GPT2 = "'s|'t|'re|'ve|'m|'ll|'d| ?\\p{L}+| ?\\p{N}+| ?[^\\s\\p{L}\\p{N}]+|\\s+(?!\\S)";
static List<String> regexesFor(String pre) {
return switch (pre) {
case "qwen2", "deepseek-r1-qwen", "stablelm2", "megrez" -> List.of(QWEN2);
case "llama3", "llama-v3", "llama-bpe", "falcon3", "dbrx", "smaug-bpe" -> List.of(LLAMA3);
case "gpt-2", "phi-2", "mpt", "olmo" -> List.of(GPT2);
case "starcoder", "refact", "smollm", "codeshell" -> List.of("\\p{N}", GPT2);
default -> throw new IllegalArgumentException("pre-tokenizer not supported here: " + pre);
};
}
static final List<String> EOG_TEXTS = List.of("<|eot_id|>", "<|im_end|>", "<|end|>", "<end_of_turn>", "<|endoftext|>",
"</s>", "<|eom_id|>", "<EOT>", "<|end_of_text|>", "<eos>", "<|fim_pad|>", "<|repo_name|>", "<|file_sep|>");
final String[] tokens;
final int[] types;
final Map<String, Integer> tokenToId = new HashMap<>();
final Map<String, Integer> mergeRank = new HashMap<>();
final List<Pattern> preTokenizer = new ArrayList<>();
final List<Integer> specials = new ArrayList<>(); // control, user-defined, unknown; longest text first
final Set<Integer> eog = new HashSet<>();
final boolean ignoreMerges, addBos;
final int bos, eos;
final char[] byteToChar = new char[256];
final int[] charToByte = new int[512];
final Map<String, int[]> cache = new LinkedHashMap<>(1024, 0.75f, true) {
@Override protected boolean removeEldestEntry(Map.Entry<String, int[]> e) { return size() > 10_000; }
};
@SuppressWarnings("unchecked")
public GgufTokenizer(Map<String, Object> md) {
if (!"gpt2".equals(md.get("tokenizer.ggml.model"))) throw new IllegalArgumentException("only byte-level BPE (gpt2) here");
tokens = ((List<Object>) md.get("tokenizer.ggml.tokens")).toArray(String[]::new);
types = md.get("tokenizer.ggml.token_type") instanceof int[] t ? t : new int[tokens.length];
if (!(md.get("tokenizer.ggml.token_type") instanceof int[])) java.util.Arrays.fill(types, NORMAL);
for (int i = 0; i < tokens.length; i++) tokenToId.put(tokens[i], i);
List<Object> merges = (List<Object>) md.get("tokenizer.ggml.merges");
for (int i = 0; i < merges.size(); i++) {
String m = (String) merges.get(i);
int sp = m.indexOf(' ', 1); // llama.cpp: word.find(' ', 1)
mergeRank.put(m.substring(0, sp) + " " + m.substring(sp + 1), i);
}
String pre = (String) md.getOrDefault("tokenizer.ggml.pre", "default");
for (String r : regexesFor(pre)) preTokenizer.add(Pattern.compile(r, Pattern.UNICODE_CHARACTER_CLASS));
boolean llama3 = List.of("llama3", "llama-v3", "llama-bpe", "falcon3").contains(pre);
ignoreMerges = llama3;
addBos = md.get("tokenizer.ggml.add_bos_token") instanceof Boolean b ? b : llama3;
bos = md.get("tokenizer.ggml.bos_token_id") instanceof Number n ? n.intValue() : -1;
eos = md.get("tokenizer.ggml.eos_token_id") instanceof Number n ? n.intValue() : -1;
for (String text : EOG_TEXTS) {
Integer id = tokenToId.get(text);
if (id != null) { eog.add(id); if (types[id] != CONTROL) types[id] = CONTROL; }
}
if (eos >= 0) eog.add(eos);
for (int i = 0; i < tokens.length; i++)
if (types[i] == CONTROL || types[i] == USER_DEFINED || types[i] == UNKNOWN) specials.add(i);
specials.sort(Comparator.comparingInt((Integer i) -> tokens[i].getBytes(StandardCharsets.UTF_8).length).reversed());
// GPT-2 byte-to-unicode map
int n = 0;
for (int b = 0; b < 256; b++) {
boolean printable = (b >= '!' && b <= '~') || (b >= 0xA1 && b <= 0xAC) || (b >= 0xAE && b <= 0xFF);
byteToChar[b] = printable ? (char) b : (char) (256 + n++);
charToByte[byteToChar[b]] = b;
}
}
public int vocabSize() { return tokens.length; }
public boolean isEog(int id) { return eog.contains(id); }
public String token(int id) { return tokens[id]; }
// Splits text with each regex in turn; matches and the gaps between them both become pieces.
List<String> preTokenize(String text) {
List<String> pieces = List.of(text);
for (Pattern p : preTokenizer) {
List<String> next = new ArrayList<>();
for (String piece : pieces) {
Matcher m = p.matcher(piece);
int last = 0;
while (m.find()) {
if (m.start() > last) next.add(piece.substring(last, m.start()));
next.add(m.group());
last = m.end();
}
if (last < piece.length()) next.add(piece.substring(last));
}
pieces = next;
}
return pieces;
}
String byteEncode(String s) {
StringBuilder sb = new StringBuilder();
for (byte b : s.getBytes(StandardCharsets.UTF_8)) sb.append(byteToChar[b & 0xFF]);
return sb.toString();
}
record Pair(int rank, int left, int right, String text) {}
// BPE on one pre-tokenized word, merging the lowest rank first (ties: leftmost), as llm_tokenizer_bpe_session does.
int[] encodeWord(String word) {
int[] cached = cache.get(word);
if (cached != null) return cached;
String w = byteEncode(word);
if (ignoreMerges && tokenToId.containsKey(w)) return new int[] {tokenToId.get(w)};
int n = w.length();
String[] sym = new String[n];
int[] prev = new int[n], next = new int[n];
for (int i = 0; i < n; i++) { sym[i] = String.valueOf(w.charAt(i)); prev[i] = i - 1; next[i] = i + 1 < n ? i + 1 : -1; }
PriorityQueue<Pair> queue = new PriorityQueue<>(Comparator.comparingInt(Pair::rank).thenComparingInt(Pair::left));
for (int i = 0; i + 1 < n; i++) addPair(queue, sym, i, i + 1);
while (!queue.isEmpty()) {
Pair p = queue.poll();
if (sym[p.left()].isEmpty() || sym[p.right()].isEmpty() || !(sym[p.left()] + sym[p.right()]).equals(p.text())) continue;
sym[p.left()] = p.text();
sym[p.right()] = "";
next[p.left()] = next[p.right()];
if (next[p.right()] >= 0) prev[next[p.right()]] = p.left();
if (prev[p.left()] >= 0) addPair(queue, sym, prev[p.left()], p.left());
if (next[p.left()] >= 0) addPair(queue, sym, p.left(), next[p.left()]);
}
List<Integer> ids = new ArrayList<>();
for (int i = 0; i != -1; i = next[i]) {
Integer id = tokenToId.get(sym[i]);
if (id != null) ids.add(id);
else for (char c : sym[i].toCharArray()) { Integer b = tokenToId.get(String.valueOf(c)); if (b != null) ids.add(b); }
}
int[] out = ids.stream().mapToInt(Integer::intValue).toArray();
cache.put(word, out);
return out;
}
void addPair(PriorityQueue<Pair> queue, String[] sym, int left, int right) {
Integer rank = mergeRank.get(sym[left] + " " + sym[right]);
if (rank != null) queue.add(new Pair(rank, left, right, sym[left] + sym[right]));
}
// Splits on special-token texts first (longest first), then runs the pre-tokenizer and BPE on the text between them.
public List<Integer> encode(String text, boolean addSpecial, boolean parseSpecial) {
List<Object> fragments = new ArrayList<>(List.of(text)); // String = raw text, Integer = token id
for (int id : specials) {
if (!parseSpecial && types[id] != USER_DEFINED) continue;
String s = tokens[id];
List<Object> next = new ArrayList<>();
for (Object f : fragments) {
if (!(f instanceof String raw)) { next.add(f); continue; }
int from = 0, at;
while ((at = raw.indexOf(s, from)) >= 0) {
if (at > from) next.add(raw.substring(from, at));
next.add(id);
from = at + s.length();
}
if (from < raw.length()) next.add(raw.substring(from));
}
fragments = next;
}
List<Integer> out = new ArrayList<>();
if (addSpecial && addBos && bos >= 0) out.add(bos);
for (Object f : fragments) {
if (f instanceof Integer id) out.add(id);
else for (String word : preTokenize((String) f)) for (int id : encodeWord(word)) out.add(id);
}
return out;
}
// The bytes of one token: reverse byte map for normal tokens, raw text for user-defined, nothing for control.
public byte[] tokenBytes(int id, boolean special) {
int t = types[id];
if (t == CONTROL || t == UNKNOWN) return special ? tokens[id].getBytes(StandardCharsets.UTF_8) : new byte[0];
if (t == USER_DEFINED) return tokens[id].getBytes(StandardCharsets.UTF_8);
ByteArrayOutputStream out = new ByteArrayOutputStream();
for (char c : tokens[id].toCharArray()) out.write(c < charToByte.length ? charToByte[c] : '?');
return out.toByteArray();
}
public String decode(List<Integer> ids) {
ByteArrayOutputStream out = new ByteArrayOutputStream();
for (int id : ids) out.writeBytes(tokenBytes(id, false));
return out.toString(StandardCharsets.UTF_8);
}
// Turns token bytes into text as they arrive; an incomplete UTF-8 sequence waits for the next token.
public static final class Utf8Stream {
private final CharsetDecoder decoder = StandardCharsets.UTF_8.newDecoder();
private ByteBuffer pending = ByteBuffer.allocate(0);
public String push(byte[] bytes) {
ByteBuffer in = ByteBuffer.allocate(pending.remaining() + bytes.length).put(pending).put(bytes).flip();
CharBuffer out = CharBuffer.allocate(in.remaining() + 1);
CoderResult r;
while ((r = decoder.decode(in, out, false)).isError()) { // invalid bytes become U+FFFD
in.position(in.position() + r.length());
out.put('\uFFFD');
}
pending = in.slice(); // an incomplete sequence waits
return out.flip().toString();
}
}
// Test: a synthetic byte-level vocabulary written to a GGUF file, read back, and exercised.
public static void main(String[] args) throws Exception {
List<String> tokens = new ArrayList<>(), merges = new ArrayList<>();
List<Integer> types = new ArrayList<>();
char[] byteChar = new char[256];
for (int b = 0, n = 0; b < 256; b++) { // ids 0..255: one token per byte
boolean printable = (b >= '!' && b <= '~') || (b >= 0xA1 && b <= 0xAC) || (b >= 0xAE && b <= 0xFF);
byteChar[b] = printable ? (char) b : (char) (256 + n++);
tokens.add(String.valueOf(byteChar[b]));
types.add(NORMAL);
}
for (String w : List.of("Hello", "Ġworld", "Ġcat", "Ġthe", "user", "assistant")) { // merges that build each word
String acc = w.substring(0, 1);
for (int i = 1; i < w.length(); i++) {
if (!tokens.contains(acc + w.charAt(i))) { merges.add(acc + " " + w.charAt(i)); tokens.add(acc + w.charAt(i)); types.add(NORMAL); }
acc += w.charAt(i);
}
}
for (String sp : List.of("<|endoftext|>", "<|im_start|>", "<|im_end|>")) { tokens.add(sp); types.add(CONTROL); }
tokens.add("[PAD0]");
types.add(USER_DEFINED);
int eosId = tokens.indexOf("<|endoftext|>");
byte[] file = new MiniGguf.Writer().string("tokenizer.ggml.model", "gpt2").string("tokenizer.ggml.pre", "qwen2")
.strings("tokenizer.ggml.tokens", tokens).ints("tokenizer.ggml.token_type", types.stream().mapToInt(i -> i).toArray())
.strings("tokenizer.ggml.merges", merges).u32("tokenizer.ggml.eos_token_id", eosId).u32("tokenizer.ggml.bos_token_id", eosId).bytes();
Path path = Files.createTempFile("vocab", ".gguf");
Files.write(path, file);
GgufTokenizer tok;
try (Arena arena = Arena.ofConfined(); FileChannel ch = FileChannel.open(path)) {
tok = new GgufTokenizer(MiniGguf.read(ch.map(FileChannel.MapMode.READ_ONLY, 0, ch.size(), arena)));
} finally {
Files.delete(path);
}
System.out.println("vocab " + tok.vocabSize() + " tokens, " + tok.mergeRank.size() + " merges, " + tok.specials.size() + " special, file " + file.length + " bytes");
for (String text : List.of("Hello world", "Hello the cat", "2026", "héllo 😀")) {
List<Integer> ids = tok.encode(text, true, false);
StringBuilder pieces = new StringBuilder();
for (int id : ids) pieces.append('[').append(tok.token(id)).append(']');
System.out.println("\"" + text + "\" -> " + ids + " " + pieces + " -> \"" + tok.decode(ids) + "\"");
}
String chat = "<|im_start|>user\nHello<|im_end|>\n<|im_start|>assistant\n";
System.out.println("chat, parse_special=true : " + tok.encode(chat, false, true));
System.out.println("chat, parse_special=false: " + tok.encode(chat, false, false).size() + " tokens");
Utf8Stream stream = new Utf8Stream();
StringBuilder streamed = new StringBuilder();
for (int id : tok.encode(" 😀!", false, false)) streamed.append('[').append(stream.push(tok.tokenBytes(id, false))).append(']');
System.out.println("streamed pieces of \" 😀!\": " + streamed);
Random random = new Random(17);
String alphabet = "abc XYZ 012 éü 世界 😀\n\t<|>";
int ok = 0;
for (int i = 0; i < 300; i++) {
StringBuilder sb = new StringBuilder();
int[] cps = alphabet.codePoints().toArray();
for (int j = 0, n = random.nextInt(30); j < n; j++) sb.appendCodePoint(cps[random.nextInt(cps.length)]);
if (tok.decode(tok.encode(sb.toString(), false, false)).equals(sb.toString())) ok++;
}
System.out.println("round trip on random strings: " + ok + "/300");
System.out.println("add BOS " + tok.addBos + ", end of generation: " + tok.isEog(eosId) + " for <|endoftext|>, " + tok.isEog(tokens.indexOf("<|im_end|>")) + " for <|im_end|>");
}
}
// A minimal GGUF metadata writer and reader for the test (lesson 46 has the full loader).
final class MiniGguf {
static final ValueLayout.OfInt U32 = ValueLayout.JAVA_INT_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN);
static final ValueLayout.OfLong U64 = ValueLayout.JAVA_LONG_UNALIGNED.withOrder(ByteOrder.LITTLE_ENDIAN);
static final class Writer {
final ByteArrayOutputStream kv = new ByteArrayOutputStream();
int count;
static byte[] le(long v, int n) { byte[] b = new byte[n]; for (int i = 0; i < n; i++) b[i] = (byte) (v >>> (8 * i)); return b; }
void str(String s) { byte[] b = s.getBytes(StandardCharsets.UTF_8); kv.writeBytes(le(b.length, 8)); kv.writeBytes(b); }
Writer string(String k, String v) { str(k); kv.writeBytes(le(8, 4)); str(v); count++; return this; }
Writer u32(String k, long v) { str(k); kv.writeBytes(le(4, 4)); kv.writeBytes(le(v, 4)); count++; return this; }
Writer strings(String k, List<String> v) { str(k); kv.writeBytes(le(9, 4)); kv.writeBytes(le(8, 4)); kv.writeBytes(le(v.size(), 8)); v.forEach(this::str); count++; return this; }
Writer ints(String k, int[] v) { str(k); kv.writeBytes(le(9, 4)); kv.writeBytes(le(5, 4)); kv.writeBytes(le(v.length, 8)); for (int x : v) kv.writeBytes(le(x, 4)); count++; return this; }
byte[] bytes() {
ByteArrayOutputStream f = new ByteArrayOutputStream();
f.writeBytes("GGUF".getBytes(StandardCharsets.US_ASCII)); f.writeBytes(le(3, 4)); f.writeBytes(le(0, 8)); f.writeBytes(le(count, 8));
f.writeBytes(kv.toByteArray());
return f.toByteArray();
}
}
// Same value representation as GgufModel: UINT32 -> Long, INT32 arrays -> int[], other arrays -> List.
static Map<String, Object> read(MemorySegment s) {
if (s.get(U32, 0) != 0x46554747) throw new IllegalArgumentException("not GGUF");
long[] pos = {24};
Map<String, Object> md = new LinkedHashMap<>();
for (long i = 0, n = s.get(U64, 16); i < n; i++) { String key = str(s, pos); md.put(key, value(s, pos, u32(s, pos))); }
return md;
}
static int u32(MemorySegment s, long[] pos) { int v = s.get(U32, pos[0]); pos[0] += 4; return v; }
static String str(MemorySegment s, long[] pos) {
long n = s.get(U64, pos[0]);
String v = new String(s.asSlice(pos[0] + 8, n).toArray(ValueLayout.JAVA_BYTE), StandardCharsets.UTF_8);
pos[0] += 8 + n;
return v;
}
static Object value(MemorySegment s, long[] pos, int type) {
return switch (type) {
case 4 -> u32(s, pos) & 0xFFFFFFFFL;
case 5 -> u32(s, pos);
case 8 -> str(s, pos);
case 9 -> {
int et = u32(s, pos);
int n = (int) s.get(U64, pos[0]);
pos[0] += 8;
if (et == 5) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = u32(s, pos); yield a; }
List<Object> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) list.add(value(s, pos, et));
yield list;
}
default -> throw new IllegalStateException("type " + type);
};
}
}vocab 286 tokens, 26 merges, 4 special, file 4693 bytes
"Hello world" -> [259, 264] [Hello][Ġworld] -> "Hello world"
"Hello the cat" -> [259, 270, 267] [Hello][Ġthe][Ġcat] -> "Hello the cat"
"2026" -> [50, 48, 50, 54] [2][0][2][6] -> "2026"
"héllo 😀" -> [104, 195, 169, 108, 108, 111, 32, 240, 159, 152, 128] [h][Ã][©][l][l][o][Ġ][ð][Ł][ĺ][Ģ] -> "héllo 😀"
chat, parse_special=true : [283, 273, 10, 259, 284, 10, 283, 281, 10]
chat, parse_special=false: 40 tokens
streamed pieces of " 😀!": [ ][][][][😀][!]
round trip on random strings: 300/300
add BOS false, end of generation: true for <|endoftext|>, true for <|im_end|>The first line describes the synthetic vocabulary: 286 tokens (256 bytes, 26 merged tokens, 4 special), 26 merges, 4 special tokens, and a 4,693-byte file.
The four encoding lines show the main paths:
Hello worldencodes to[259, 264], the merged tokensHelloandĠworld, and decodes back to the same text. The ids of merged tokens follow the 256 byte tokens:Heis 256,Hel257,Hell258,Hello259.Hello the catencodes to three merged tokens.2026becomes four single-digit tokens, 50, 48, 50, 54, which are the ASCII codes of the digits, because the vocabulary is theqwen2type and its regex splits digits.héllo 😀has no merges for its pieces, so every byte becomes its own token.éis the two bytes 195 and 169 (writtenÃand©in vocabulary form), and the emoji is four bytes. Byte-level BPE can therefore encode any input, and the decoded text equals the input.
The chat lines show special-token handling. With parse_special=true, <|im_start|> becomes 283 and <|im_end|> 284. user (273), Hello (259), and assistant (281) are merged tokens, and 10 is the newline byte. With parse_special=false, the same string costs 40 tokens, because every character of the control texts is encoded as text.
The streamed line decodes 😀! token by token. The space comes out at once. The four emoji bytes produce nothing until the fourth one arrives, then the full emoji appears, then !. The empty pieces [] between the space and the emoji are those waiting steps.
The round-trip line encodes 300 random strings built from ASCII letters, digits, accents, CJK, emoji, tabs, newlines, and the characters <, |, >, and decodes them back. All 300 come back unchanged. The last line confirms the metadata rules: no BOS for a qwen2 pre-tokenizer without the key, and both <|endoftext|> (the EOS id) and <|im_end|> (found by its text) end generation.
Saved as GgufTokenizer.java next to GgufModel.java, the class tokenizes real models with new GgufTokenizer(model.metadata()). Example 9 ran it on the Qwen2 and Llama 3 vocabularies, and the next lesson uses it to tokenize the prompt of the tiny random model.
The class leaves out some parts of llama.cpp:
- the other pre-tokenizer types in the
switchofllm_tokenizer_bpe - SentencePiece, WordPiece, and Unigram vocabularies
- the
lstripandrstripattributes of a few special tokens - the
clean_spacesoption, which only affects decoding withllama_detokenize
Interview points
- A GGUF tokenizer is stored in the keys
tokenizer.ggml.model,.pre,.tokens,.token_type,.merges, and the special token id keys. Token ids are indices into the token array. - Byte-level BPE stores each byte as a visible character through the GPT-2 map. Decoding maps characters back to bytes before any UTF-8 decoding.
- A merge's rank is its index in the merge list. Encoding applies the lowest rank first and breaks ties by position. A priority queue with stale-entry checks makes it
n log n. - The pre-tokenizer regex is chosen by
tokenizer.ggml.pre. Qwen2 splits single digits, Llama 3 groups up to three, and GPT-2 keeps whole numbers. - Java needs
Pattern.UNICODE_CHARACTER_CLASSso that\smatches Unicode whitespace as llama.cpp does. - Special tokens are cut out before BPE, longest first. Control tokens are cut out only with
parse_special, and user-defined tokens always. - Encoding untrusted text with
parse_special=truelets the text inject control tokens such as<|im_end|>. - BOS is false for byte-level BPE by default, true for the Llama 3 pre-tokenizers and SentencePiece, and
tokenizer.ggml.add_bos_tokenoverrides both. - Generation stops on EOS and on EOG tokens that llama.cpp finds by text, such as
<|im_end|>and<|eot_id|>. - Streaming output needs a UTF-8 decoder that keeps incomplete bytes between tokens.
- SentencePiece vocabularies use
▁, score-based merging, and<0xNN>byte fallback tokens. - A tokenizer port is verified against llama.cpp's own
models/ggml-vocab-*.gguf.inpand.outtest files.
Summary
- Token types: 1 normal, 2 unknown, 3 control, 4 user-defined, 5 unused, 6 byte.
- Qwen2 id 1879 is
Ġworld(bytes20 77 6f 72 6c 64), id 198 isĊ(newline), id 90316 is😀, and id 99489 is世界. - Qwen2 has 151,387 merges, one per non-byte normal token. Llama 3 has 280,147 merges for 127,744 distinct results.
- llama.cpp splits a merge line at
find(' ', 1). - The same line splits into 18 pieces with the Qwen2 regex, 14 with Llama 3's, and 12 with GPT-2's.
- A stale queue entry is detected by comparing the current symbol texts with the entry's text.
- Special tokens are tried longest first:
<|endoftext|>(13 characters) before<|im_end|>(10). Hello worldwith the Qwen2 vocabulary is[9707, 1879], with no BOS.- Llama 3 prompts start with 128000.
2026is[2366, 21]in Llama 3 and[17, 15, 17, 21]in Qwen2. - The Java tokenizer matches
llama-tokenizeon English, code, and mixed-script text, and passes all 46 llama.cpp test cases for the qwen2, llama-bpe, gpt-2, starcoder, and refact vocabularies. - A word cache cut merge work from 1,747 to 19 steps on a repetitive code text.
- The Llama 2 SentencePiece vocabulary encodes 😀 as four byte tokens, 243, 162, 155, and 131.
GgufTokenizerround-trips 300 random mixed-script strings exactly.