OKLMdocumentation v1.0.3
On this page

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.c by tools/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_BACKEND by 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.