ADR-0004: Regular expressions for pre-tokenization
Records how OKLM evaluates the regular expressions that byte-level BPE tokenizers use to split text before merging.
Status: accepted (2026-10-29).
Context
Every byte-level tokenizer splits text with a regex (GPT-2, Llama 3,
Qwen, DeepSeek, o200k... each has its own), stored in
tokenizer.json or named by GGUF's
tokenizer.ggml.pre. The first option considered was
hand-written matchers for the known patterns, because nilorea's PCRE2
would be an external dependency on the model path.
Decision
- A small backtracking regex engine written for OKLM
(
src/tok/regex.c), with Perl/Oniguruma leftmost-first semantics, supporting exactly the syntax tokenizer patterns use: alternation, non-capturing and case-insensitive groups, lookaheads, classes with Unicode general categories (\p{L}and its subcategories,\p{N},\p{M},\p{P},\p{S},\p{Z}),\s \d \w, greedy and lazy quantifiers including{m,n}. - Unicode data (categories, White_Space, NFC tables) is generated from
the Unicode Character Database into
src/tok/unicode_data.cbytools/gen_unicode_tables.py. - Safety for untrusted patterns: unbounded repetitions of expressions
that can match nothing are rejected at compile time, programs are capped
at 100 000 instructions after expansion, groups at 256 levels, the
backtracking stack at 2^20 entries, and each match attempt at 20 million
steps (reported as
OKLM_ERR_BACKENDby the tokenizer). The engine is fuzzed (fuzz/fuzz_regex.c).
Why not hand-written matchers
A generic engine reads the patterns of any
tokenizer.json as written, instead of one C function per
known pattern, and a new pre-tokenizer is a table entry. Correctness is
checked where it matters: tokenizer output is identical to Hugging
Face's on a 10 000-entry corpus for five tokenizers.
Consequences
Matching is slower than a hand-written matcher (still several MB/s, see benchmarks.md). Case-insensitive matching folds ASCII only, which covers the contraction groups the patterns use.