Repository navigation
How to Design High-Performance On-Device Tokenizers? MNN Refactoring Practice and Reflections #4353
wangzhaode
announced in
Technical Blog
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
1. Introduction
In on-device LLM inference, the Tokenizer serves as the bridge between user-input text and the token IDs that the model can understand. It may seem simple, but it actually involves multiple stages: Unicode normalization, regex-based tokenization, and subword encoding.
Server-side Tokenizer implementations (such as HuggingFace Tokenizers) are typically built in Rust and depend on a complete Unicode library (ICU) and a complex regex engine, producing binaries on the order of several MB. This is not a problem on the server side, but on-device scenarios have entirely different constraints:
MNN has supported tokenization for LLM inference for quite some time, but since tokenizer implementations varied across models at the time, the original approach was to adapt to each model separately (Sentencepiece / Tiktoken / BertTokenizer / HuggingfaceTokenizer). This was incomplete and increasingly costly to maintain.
This upgrade introduces PipelineTokenizer — a unified pipeline architecture designed specifically for on-device use, with behavior fully aligned to HuggingFace Transformers. The design follows three core principles: zero third-party dependencies, high performance, and low code volume (small binary). The central idea is "pre-compute during Python export, zero-copy during C++ loading" — push all offline-computable work ahead of time, keeping the on-device C++ code as simple and fast as possible.
2. The Unified Tokenizer Pipeline: Principles and Flow
2.1 Four-Stage Pipeline
Modern HuggingFace Tokenizers adopt a unified four-stage pipeline architecture:
Each stage consists of pluggable components; different models simply combine these components differently. This single architecture covers the tokenizers of virtually all mainstream LLMs.
2.2 Example: Full Encoding Process for a Single Sentence with Qwen3.5
Take Qwen3.5 (a BPE model with ByteLevel pre-tokenization) processing the sentence
"Hello, MNN!"to illustrate the transformation at each step:Step 0: Raw Input
Step 1: Normalizer (No-op)
Qwen3's tokenizer has no Normalizer configured, so the text remains unchanged:
Step 2: PreTokenizer (ByteLevel + Digits)
The ByteLevel PreTokenizer uses a GPT-2-style regex pattern to split text into substrings. The core idea of this regex is: split English words (with leading spaces), numbers, and punctuation into separate pieces.
Meanwhile, ByteLevel maps each byte to a visible Unicode character (the GPT-2 byte-to-unicode mapping). For example, space
0x20is mapped toĠ(U+0120):Step 3: Model (BPE Encoding)
BPE (Byte Pair Encoding) is applied independently to each substring. The BPE process:
Taking the substring
"Hello"as an example:After applying BPE to all substrings:
Step 4: Final Result
Concatenate token IDs from all substrings:
This is the actual input the model receives.
2.3 Decoding Process (Reverse)
During decoding, the Decoder restores token IDs back to text:
The
Ġis restored to a space, recovering the original text.3. Problems with MNN's Legacy Tokenizer
MNN has supported tokenization for LLM inference since 2023, but at that time tokenizer implementations varied significantly across models, so MNN adopted a per-model adaptation strategy:
SentencepieceTiktokenBertTokenizerHuggingfaceTokenizerExisting problems:
std::regexperforms extremely poorly on mobile, especially for patterns with Unicode properties (e.g.,\p{L}).4. The New PipelineTokenizer: One Architecture for All Models
4.1 Architecture Design
The new PipelineTokenizer implements the complete four-stage pipeline, with each stage accommodating different models by composing different components:
This composable design covers virtually all mainstream LLM tokenizers:
4.2 Full Alignment with HuggingFace
The new implementation strictly aligns with HuggingFace Transformers' tokenizer behavior, including:
Testing covers 47 models and 1,901 test cases, with output fully consistent with the HuggingFace Python implementation.
5. On-Device Optimization: Deep Customization for Mobile
On-device deployment imposes strict requirements on loading speed, runtime memory, and installation package size. This upgrade includes targeted optimizations across all three dimensions.
5.1 Loading Speed: Core Optimization — Sort at Export Time, Not at Load Time
Problem: The legacy text format reads a 150K-line vocabulary line by line, with each line requiring base64 decoding +
std::stringallocation, taking hundreds of milliseconds to load. More critically, the legacy version builds anunordered_map<string, int>as the vocabulary lookup structure during C++ loading — the overhead of 150K string hash computations and insertions is enormous.Core idea: Move sorting from load time to export time.
The traditional approach stores the vocabulary in token ID order (ID 0, 1, 2, ...), then builds a hash table at load time for token-to-ID lookup during encoding. The key insight of this optimization is: sort the vocabulary by token string in lexicographic order during Python export and store it that way. This way, after C++ loads it, no additional processing is needed — it is already a sorted array, enabling binary search.
What is the cost? Since the vocabulary is no longer stored in ID order, each token requires an additional 4-byte token ID field. For a 150K vocabulary, this adds only about 600KB, but in return:
unordered_map.Implementation details:
read()call intobinary_buf_.std::string;StringRefpoints directly into positions within the buffer.std::lower_boundfor binary search.(id1<<32|id2)and sorted.Vocabulary lookup during encoding changes from hashmap to binary search. Although a single lookup goes from O(1) to O(log n), the sorted array is stored contiguously in memory, which is extremely CPU cache-friendly. In practice, performance is equivalent or even better, and the entire load-time construction overhead is eliminated.
5.2 File Size: Compact Binary Storage
"Ġ t")Overall, the
.mtokfile is smaller than the legacy.txt+tokenizer_config.json, while also containing more information (Normalizer configuration, Decoder configuration, etc.).5.3 Encoding Performance: Unicode Folding + Lightweight Regex as a Replacement for std::regex
std::regexis a major performance bottleneck for on-device tokenizers. Many tokenizer pre-tokenization patterns include Unicode properties (such as\p{L}+,\p{N}{1,3}), and mainstream C++ standard library regex implementations have poor or no support for Unicode properties.The new implementation provides a general-purpose
regex_scanner, with the core idea of Unicode folding: first map each character in the Unicode text to a single-byte category code by its General Category, then match using a lightweight regex engine on the folded single-byte sequence.Matching after folding operates entirely in the single-byte domain, avoiding the complexity of traditional regex engines handling multi-byte Unicode. For the rare patterns that cannot be folded, a fallback to
std::wregexis used.5.4 NFKC/NFD Normalization: From Code-Embedded to File-Embedded
Unicode normalization (NFKC / NFD) is a feature that may be used during the Normalizer stage. Briefly:
A→A, Roman numeralⅢ→III, ligaturefi→fi, etc.éis decomposed intoe+´, which works with BertNormalizer'sstrip_accentsfeature to remove diacritical marks.The data for these tables is substantial (NFKC has about 5,000+ entries, NFD is similar), and typically requires a Unicode library like ICU (several MB) for support. However, in actual on-device scenarios, only a few models need normalization — mainly BERT-family models that use BertNormalizer (with NFKC and NFD). Mainstream LLMs (Qwen, LLaMA, ChatGLM, etc.) do not require a Normalizer in their tokenizers.
Therefore, the design choice here is: do not compile NFKC/NFD data into the C++ code; instead, write it into the .mtok file on demand during Python export.
Benefits of this approach:
5.5 Code Dependencies and Package Size
On-device deployment is highly sensitive to installation package size. The following dependency control measures were taken:
tokenizer.hpp/cpp, eliminating conditional compilation and duplicated code.The entire tokenizer module has no external dependencies and relies only on the C++11 standard library, yet supports tokenizers for all mainstream LLMs.
6. Performance Benchmarks
Using the Qwen3.5-0.8B model's tokenizer as the baseline, three implementations were compared on a MacBook Pro (M3 Pro): the new MNN PipelineTokenizer (.mtok), the legacy MNN version (.txt), and HuggingFace Transformers (Python, backed by the Rust-implemented tokenizers library).
Test item descriptions:
Test Results
Performance Improvement Multipliers
Key observations:
tokenizer.jsonis a multi-megabyte JSON file containing the full vocabulary, merge rules, and configuration — parsing this JSON alone consumes significant time. This is the core reason we abandoned HuggingFace's original JSON format in favor of a custom binary format: JSON parsing is an unacceptable performance bottleneck on-device.7. Summary
The design philosophy for on-device tokenizers can be summarized in one sentence: leave the complexity to offline tools, and keep simplicity for runtime.
The Python export stage handles all the "heavy lifting": vocabulary sorting, merge rule pre-computation, Unicode normalization table generation, and binary format serialization. The C++ runtime only needs to do the simplest things: read a block of memory, set a few pointers, and encode with binary search. The entire Tokenizer C++ implementation is about 2,400 lines with zero third-party dependencies (no ICU, no Rust tokenizers, no sentencepiece library), requiring only the C++11 standard library to compile. Unicode category data is built-in in compressed range form at about 30KB, and normalization data like NFKC/NFD is embedded on demand into model files rather than into the code, achieving "pay only when you use it."
This approach demonstrates a straightforward truth: on-device inference does not need to port all the complexity of the server side. Through a reasonable division of labor between offline and online stages, it is entirely possible to achieve 100% alignment with HuggingFace Transformers tokenizer functionality with minimal code and zero external dependencies, while simultaneously achieving loading and encoding performance far exceeding server-side implementations.
8. Development Approach: Collaboration Between VibeCoding and Manual Optimization
This tokenizer refactoring made extensive use of VibeCoding as a development methodology, with Gemini 3.1 Pro and Claude Opus 4.6 completing most of the implementation work. Specifically:
What AI excels at:
What AI cannot do — core optimization strategies require human guidance:
However, for several key optimization strategies that determine the performance ceiling, AI was unable to arrive at the right direction on its own:
Reflections:
At present, AI's ability to "implement known solutions" is already very strong — given a clear optimization direction, it can complete coding, testing, and debugging with high quality. But when it comes to "proposing optimization directions," especially for on-device scenarios with special constraints (package-size sensitivity, inability to depend on heavy libraries, needing to make trade-off judgments), AI tends to provide server-side "standard answers" rather than on-device "optimal answers."
This human-AI collaboration model may be the most efficient development approach at the current stage: humans are responsible for direction judgment and key trade-off decisions, while AI is responsible for efficient implementation and extensive test verification. The entire tokenizer refactoring (covering 47 models, 1,901 test cases, ~2,400 lines of C++ plus ~500 lines of Python export) was completed efficiently under this collaborative model.
All reactions