sml-bytebpe

The GPT-2 byte-level BPE tokenizer in pure Standard ML.

GPT-2 tokenizes by byte-level BPE: text is UTF-8 encoded, every byte is mapped to a printable "unicode" character (bytes_to_unicode), the text is pre-tokenized by GPT-2's fixed regex, and each piece is merged by the ranked BPE merges into vocabulary tokens. Because it works on bytes, it never emits an unknown token, and decode ∘ encode = id for any input.

encode/decode are pure and deterministic — token ids are integers, so the output is byte-identical under MLton and Poly/ML. Lookups use a sorted-vector binary search, so loading the full 50k-merge GPT-2 tables is practical.

smlpkg add github.com/sjqtentacles/sml-bytebpe
smlpkg sync

Depends on sml-json and sml-unicode (fetched by smlpkg sync).

(* from GPT-2 file *contents* (caller does the IO) *)
val tok = Bytebpe.fromGpt2 { vocab = vocabJsonText, merges = mergesTxtText }
val ids  = Bytebpe.encode tok "hello world"     (* [31373, 995] *)
val text = Bytebpe.decode tok ids               (* "hello world" *)

(* or from an explicit vocabulary + merge list (rank = list order) *)
val t = Bytebpe.make { vocab = [("a",0),("b",1),("ab",2)], merges = [("a","b")] }

type tokenizer
exception Bytebpe of string
val make      : {vocab:(string*int) list, merges:(string*string) list} -> tokenizer
val fromGpt2  : {vocab:string, merges:string} -> tokenizer   (* vocab.json + merges.txt text *)
val encode    : tokenizer -> string -> int list
val decode    : tokenizer -> int list -> string
val byteToUnicode : int -> int      (* GPT-2 byte<->unicode bijection on 0..255 *)
val unicodeToByte : int -> int
val pretokenize   : string -> string list
val vocabSize     : tokenizer -> int

The pre-tokenizer implements GPT-2's fixed pattern

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

by hand. \p{L}/\p{N} are classified for ASCII letters/digits; any non-ASCII codepoint is treated as "other" (the [^\s\p{L}\p{N}] class). This reproduces GPT-2 exactly for ASCII text and for symbols / emoji / punctuation (which are not letters or numbers — so multibyte input like "cat 🐱" tokenizes identically), but not for non-ASCII letters or digits (e.g. accented Latin, CJK, Arabic-Indic digits). sml-unicode provides the UTF-8 codec but no character classes, so full Unicode \p{L}/\p{N} is out of scope.

make example builds and runs examples/demo.sml, which round-trips a couple of bytes through the GPT-2 byte<->unicode map, pre-tokenizes "banana time", and builds a tiny hand-derived vocab/merge table to BPE-encode and decode "banana" (output is byte-identical under MLton and Poly/ML):

GPT-2 byte<->unicode map:
  byteToUnicode 65 = 65  (unicodeToByte back = 65)
  byteToUnicode 255 = 255  (unicodeToByte back = 255)

Pre-tokenize "banana time":
  ["banana"," time"]

Tiny hand-built tokenizer (vocab a/b/n/an, merge a+n):
  vocabSize = 4
  encode "banana" = [1,3,3,0]
  decode [1,3,3,0] = "banana"
  decode o encode = id: true

make test       # MLton
make test-poly  # Poly/ML

31 assertions, green on MLton and Poly/ML with byte-identical output. Two tiers:

1. Core algorithm on a tiny custom vocab/merges whose tokenization is hand-derivable — proving the merge algorithm + byte mapping without any GPT-2 file.
2. GPT-2 conformance against Golden — a curated slice of the official vocab.json/merges.txt (only the ~80 vocab entries / ~46 merges the test prompts exercise) with token-id goldens straight from tiktoken. Keeping every applied merge at its original rank is enough to reproduce exact real GPT-2 ids, so the repo vendors a few KB instead of the ~1.5 MB full files, and CI needs no Python. The generator is tools/gen_reference.py (dev-time only).

MIT