Architecture and Implementation of No-Crate Tokenizers for Embedded Rust Language Models

Full report

On this page

Introduction to Standalone Tokenization Systems

The proliferation of Large Language Models (LLMs) has necessitated the development of highly optimized, low-latency inference pipelines capable of operating in diverse computational environments. While the neural network weights, attention mechanisms, and matrix multiplications constitute the bulk of computational expenditure within the transformer architecture, tokenization—the process of mapping raw text to integer identifiers and decoding them back to text—remains a critical, frequently under-optimized, and surprisingly complex component of the inference pipeline.1 Modern tokenization ecosystems are heavily dominated by robust, generalized toolkits, most notably the HuggingFace tokenizers library and Google's sentencepiece toolkit.3 These libraries offer multi-threaded Rust and C++ implementations that are typically exposed to practitioners via high-level Python bindings.3 However, introducing these massive, generalized libraries into embedded, edge, or highly constrained environments presents significant architectural drawbacks. These frameworks introduce heavy dependency trees, drastically increase compiled binary sizes, complicate cross-compilation build processes, and often rely on dynamic heap memory allocation strategies that can be highly detrimental in real-time or memory-constrained systems.1 The computational penalty of tokenization is especially pronounced when operating smaller models, such as rerankers, classifiers, and embedding models, where the GPU compute typically finishes in single-digit milliseconds.1 In such scenarios, CPU-side tokenization processing can account for a meaningful fraction of total request latency, particularly when dealing with large batch sizes or extensive context windows.1 The paradigm of self-contained, dependency-free inference was popularized by implementations such as Andrej Karpathy's llama2.c, which famously demonstrated that a complete LLM inference engine—encompassing the tokenizer, transformer weights, and probability sampler—could be written in a few hundred lines of pure, dependency-free C code.7 Extending this minimalist philosophy to the Rust programming language yields the conceptual architecture of "TinyRustLM": a system where the tokenizer inference engine is implemented entirely in standard or core Rust without reliance on third-party crates such as serde, tokenizers, regex, or bincode.10 By stripping away generalized abstraction layers, developers can achieve zero-allocation architectures, significantly lower latency, and highly deterministic memory utilization profiles.1 Transitioning from standard HuggingFace or SentencePiece artifacts to a standalone embedded Rust tokenizer requires a comprehensive, two-stage operational pipeline. The first stage consists of an offline preprocessing phase, typically executed in Python, which parses the complex hierarchical tokenizer.json or SentencePiece protobuf files and serializes the necessary vocabulary, scores, and merge rules into a highly compact, structurally deterministic custom binary format.10 The second stage occurs natively at runtime in Rust, where this binary artifact is embedded directly into the executable memory space and parsed using zero-cost abstraction techniques.14 This approach facilitates instantaneous load times, completely bypasses file I/O overhead during execution, and allows the tokenizer inference engine to operate strictly via memory references and stack-allocated data structures.16 This report provides an exhaustive, nuanced blueprint for building this two-stage pipeline. It dissects the structural mechanics of HuggingFace's JSON formats and SentencePiece models, designs an optimal binary layout, establishes zero-allocation Rust parsing techniques, and exhaustively details the algorithmic implementation of the three predominant subword tokenization models: Byte-Pair Encoding (BPE), Unigram, and WordPiece.18

The Source Material: Dissecting Standard Tokenizer Configurations

The foundation of any tokenizer conversion plan requires a granular understanding of the source data structures. The HuggingFace ecosystem typically defines all tokenization parameters within a comprehensive configuration file known as tokenizer.json.21 This file represents the complete state of the tokenizer pipeline and dictates how raw text strings are ultimately transformed into integer sequences suitable for neural network consumption.13 The tokenizer.json file is fundamentally structured as a sequential pipeline consisting of several distinct stages, each serving a specific preprocessing or encoding purpose before the core algorithm is applied.3 Understanding these components is critical, as the offline serialization script must replicate or bypass these steps based on the target architecture's constraints.

The model object within the JSON structure is the most critical and complex component, as its internal schema varies fundamentally depending on the chosen algorithmic architecture.13 For a Byte-Pair Encoding (BPE) model, which powers architectures like GPT-2, LLaMA, and Qwen, the model object specifies a vocab dictionary that maps string tokens to integer IDs, alongside a merges array.13 The merges array contains a list of strings—each composed of two space-separated subwords—that dictates the strict hierarchical merging sequence of adjacent byte pairs.13 The order of this array is paramount, as it inherently defines the rank and priority of the merges during inference.30 Conversely, a Unigram model, frequently utilized by models such as T5 and ALBERT, eschews deterministic merge rules entirely in favor of a probabilistic vocabulary.19 In a Unigram configuration, the JSON does not contain a merges array; instead, the vocab array contains tuples pairing string tokens with their associated log-likelihood scores.25 These scores, typically represented as negative floating-point numbers, represent the independent probability of that specific subword occurring in the training corpus.25 Finally, a WordPiece model, standard in BERT and its variants, relies on a greedy matching algorithm and utilizes a specialized vocabulary where subwords that continue an existing word are prefixed with a specific marker, conventionally \#\# (defined in the configuration as continuing\_subword\_prefix).5 This model structure requires the extraction of a simple dictionary without secondary merge arrays, as the algorithm relies on identifying the longest matching prefix rather than executing iterative merges.5 In alternative ecosystems, such as models trained directly with Google's SentencePiece library, the tokenizer state might not be stored in a tokenizer.json file, but rather in a serialized Protocol Buffer (protobuf) file, often carrying a .model extension.5 The SentencePiece unigram model decomposes an input into a sequence of tokens that yield the highest likelihood under a unigram language model, maximizing the product of the sub-tokens' probabilities.37 Parsing these protobuf files directly in a constrained Rust environment without the prost or protobuf crates is highly impractical.36 Therefore, whether dealing with HuggingFace JSONs or SentencePiece protobufs, an intermediary translation layer is an absolute architectural necessity.

Offline Preprocessing and Binary Serialization Strategy

To completely bypass dynamic parsing libraries like serde\_json or protobuf parsers in the embedded Rust runtime, developers must utilize an offline Python script to extract the disparate states from the source files and compile them into a unified, flat, and dense custom binary artifact.10 This methodology closely mirrors the highly successful paradigm utilized in llama2.c, where an export.py or tokenizer.py script systematically translates SentencePiece vocabularies and weights into a flat, memory-mappable .bin format.10 The custom binary format must be meticulously designed to support contiguous memory mapping and instantaneous zero-allocation loading.11 The overarching architecture of this binary file dictates a standardized metadata header, followed immediately by variable-length data pools containing the string vocabulary, and concluding with model-specific auxiliary data arrays.13 The header acts as the validation and configuration layer. It must begin with a 32-bit magic number (e.g., 0x544F4B4E for "TOKN") to ensure the Rust engine is loading a valid artifact.13 This is followed by a 32-bit integer defining the model type, which instructs the Rust runtime whether to route the data to the BPE, Unigram, or WordPiece inference engines (e.g., 1 for BPE, 2 for Unigram, 3 for WordPiece).13 Subsequent 32-bit integers define the exact size of the vocabulary (the total number of distinct tokens), the maximum theoretical length of any single token string (used for bounds checking and static buffer allocation), and the number of auxiliary merge rules or failure links present in the file.13

Following the fixed-size header, the Python serialization script must pack the actual string representations of the vocabulary into the binary file. Because strings are inherently of variable length, and because the target Rust engine requires contiguous slices to establish zero-copy references, the string pool must be encoded in a length-prefixed format.39 For every token in the vocabulary, the script writes a 32-bit little-endian integer indicating its exact byte length, immediately followed by the raw UTF-8 encoded bytes of the token string itself.39 After the string pool is completely serialized, the auxiliary data structures required by the specific tokenization model are appended. For a Unigram model, this takes the form of an array of 32-bit floating-point numbers (f32) representing the log-likelihood scores.25 This array must exactly match the sequential order of the preceding string vocabulary, allowing the Rust engine to map a token's index directly to its score using a simple array lookup.25 For a Byte-Pair Encoding (BPE) model, the serialization logic is more complex. The textual merge rules defined in the JSON configuration (e.g., "G Ġ") must be translated into their integer representations before being written to disk.13 The Python script iterates through the merges array, queries the vocabulary dictionary to find the integer ID of the left token and the right token, and serializes these ID pairs as consecutive 32-bit unsigned integers (u32).30 The rank, or priority, of the merge—which determines which pair should be merged first during inference—is inherently encoded by the index of the pair within this serialized array.30 This offline precomputation is an absolutely vital architectural optimization. By translating string-based merge rules into integer-based lookup pairs during the serialization phase, the burden of string-matching, hashing, and dictionary construction is completely lifted from the embedded Rust runtime.42 The inference engine can therefore operate entirely via rapid, cache-friendly index-based integer lookups, drastically reducing latency and completely eliminating the need for heap-allocated HashMaps.37

Zero-Allocation Static Memory Mapping in Rust

With the custom binary artifact prepared, the next phase involves importing and interpreting this dense data structure within a pure Rust environment. To achieve true zero-dependency and zero-allocation execution, the tokenizer architecture must rigorously avoid dynamic file operations via std::fs, heap-allocated collections like Vec or String, and dynamic deserialization crates.11 The optimal system-level solution is to embed the binary file directly into the compiled executable's read-only data section (.rodata) utilizing Rust's built-in include\_bytes\! macro.14 However, leveraging include\_bytes\! introduces a critical and often misunderstood systems programming challenge regarding memory alignment. The Rust compiler treats the output of the include\_bytes\! macro simply as a generic, statically sized byte array (&'static \[u8\]).15 The compiler provides no inherent guarantees regarding the memory alignment of this array; it defaults to an alignment of 1 byte, meaning the array could begin at any arbitrary memory address.15 This lack of alignment becomes catastrophic when the embedded software attempts to parse the binary data. If the software attempts to safely cast, transmute, or read segments of this unaligned byte slice into primitive types that possess higher alignment requirements—such as a 32-bit integer (u32) or a 32-bit float (f32), both of which require 4-byte memory alignment—the processor will likely raise a hardware-level alignment exception, resulting in undefined behavior, corrupted data reads, or immediate segmentation faults on strict architectures like ARM.16 To circumvent this hardware constraint without utilizing third-party alignment crates, developers must exploit Rust's representation attributes to manually force the compiler's hand. By wrapping the include\_bytes\! macro invocation within a custom struct annotated with \#\[repr(C, align(4))\], the compiler is explicitly instructed to align the entire static byte array to 4-byte boundaries.17

Rust \#\[repr(C, align(4))\] struct AlignedTokenizerBinary(\[u8; include\_bytes\!("tokenizer.bin").len()\]);

static TOKENIZER\_DATA: \&AlignedTokenizerBinary \= \&AlignedTokenizerBinary(\*include\_bytes\!("tokenizer.bin"));

This technique, formally documented in Rust systems programming circles, is the primary method for achieving zero-cost, perfectly aligned static binary inclusion without relying on external dependencies.16 The underlying bytes can then be accessed safely and efficiently. Furthermore, the implementation of massive static arrays in Rust requires careful consideration regarding the distinction between the const and static keywords. While large data structures can technically be defined using const, doing so is an architectural anti-pattern for embedded data.45 The Rust compiler treats const values as inlineable definitions; it may attempt to inject the entire massive binary array directly onto the execution stack at the site of use, instantly triggering a stack overflow exception.45 Therefore, the binary wrapper must strictly be declared as a static item.45 This ensures the multi-megabyte data blob remains securely anchored in the .rodata section of the executable, and any subsequent references to it simply pass lightweight memory pointers rather than physically duplicating the data.45 Parsing the binary format into functional tokenization structures requires precise slice manipulation and byte decoding. The engine iterates over the static byte array using a moving cursor. When extracting the 32-bit integers for the header values, string lengths, or BPE merge pairs, the engine slices a four-byte chunk from the array and decodes it utilizing the standard library's u32::from\_le\_bytes method.39 This function operates at absolute zero-cost, executing a direct read in little-endian format and gracefully handling endianness conversions if the host hardware operates on a big-endian architecture.39 When interpreting the string pool, the engine extracts the specified number of bytes based on the decoded length prefix and applies the core::str::from\_utf8\_unchecked function.40 Because the offline Python script implicitly guarantees the validity of the UTF-8 encoding during the serialization process, bypassing runtime UTF-8 validation checks in Rust represents a safe, zero-cost optimization.40 The result is an array of &'static str references that perfectly represent the vocabulary, pointing directly into the executable's .rodata segment without a single byte of heap allocation or data duplication. For the auxiliary data, Unigram log-likelihood scores can be decoded by transmuting 4-byte little-endian chunks into f32 values, leveraging the guaranteed 4-byte alignment of the overarching static wrapper.37 This continuous, sequential extraction populates lightweight array structures on the stack or within a pre-allocated static arena, finalizing the initialization of the tokenizer in a fraction of a millisecond and paving the way for instantaneous inference.

Byte-Pair Encoding (BPE) Inference and Arena Linked Lists

Byte-Pair Encoding (BPE) represents the overwhelmingly dominant tokenization strategy in the contemporary AI landscape, serving as the foundational text-processing layer for frontier models such as GPT-2, GPT-4, LLaMA, and Qwen.2 The theoretical underpinning of BPE is derived from an iterative data compression algorithm originally introduced in 1994, which initializes with a base vocabulary of individual characters and progressively merges the most frequent adjacent pairs until a predefined target vocabulary size is achieved.19 In the context of LLM inference, the tokenizer must execute this logic in reverse: it takes a raw string, converts it to its base token representation, and iteratively applies the known merge rules sequentially until no further merges are possible.30 Modern LLM tokenizers utilize a highly specific variant known as byte-level BPE. Rather than initializing the base vocabulary with Unicode characters, which can result in an intractable number of rare characters being mapped to unknown (\<UNK\>) tokens, byte-level BPE initializes with a base vocabulary of exactly 256 tokens, corresponding to all possible raw byte values (0x00 to 0xFF).2 This guarantees that absolutely any text, in any language or encoding, can be represented by the model without resorting to \<UNK\> degradation.2 During the initial decoding step, if the tokenizer encounters invalid byte sequences that Python cannot decode natively into text, standard implementations avoid throwing exceptions by replacing them with a default Unicode replacement character ().2 Before the core BPE merge algorithm can execute, the inference engine must perform a pre-tokenization regex split.2 To prevent the BPE algorithm from merging characters across conceptual boundaries—such as merging the end of a word with the punctuation mark that follows it—a regular expression is utilized to shatter the input text into distinct chunks based on predefined character categories.26 For instance, GPT-2 utilizes a relatively simple pre-tokenization rule that splits on spaces, while prepending a specialized metaspace character, conventionally Ġ, to tokens that follow a space.28 GPT-4's cl100k\_base tokenizer employs a vastly more complex regex pattern to force splits across specific punctuation, numeric sequences, and whitespace categories, which requires careful replication in a custom Rust state machine.2 Implementing the core BPE iterative merge algorithm in pure Rust without standard library constraints requires highly sophisticated data structure management to avoid catastrophic algorithmic time complexities.43 A naive, standard implementation of BPE inference scans the input sequence of base bytes to find the single most highly ranked adjacent pair, merges them into a new token, physically shifts all remaining tokens in the array to close the newly created gap, and then scans the entire string again from the beginning.43 This naive approach requires an [Figure omitted from source export] scan to locate the best pair, and an [Figure omitted from source export] memory shift operation to execute the merge. Executed over a potential [Figure omitted from source export] sequence of merges, this results in a devastating [Figure omitted from source export] algorithmic time complexity.43 While this quadratic scaling may be unnoticeable on short sentences, it severely degrades performance and spikes latency when processing large context windows, extensive un-split documents, or pathological string sequences.43 The memory scaling issues of BPE are so severe that during the offline training phase, applying supermerges to a 160GB text corpus can cause RAM usage to explode to 7.6TB if naive doubly linked lists are utilized, necessitating complex external-memory paging strategies.56 To solve this at inference time within a minimal Rust environment, the algorithm must be redesigned using an emulated doubly linked list paired with a priority queue structure, successfully driving the complexity down to a manageable [Figure omitted from source export].43 Traditional pointer-based linked lists in Rust are notoriously difficult to implement and computationally inefficient due to poor CPU cache locality and the strict ownership rules enforced by the borrow checker.43 The optimal system architecture emulates a doubly linked list by utilizing a flat, pre-allocated static array acting as a memory arena.43 The Rust data structure for a sub-token symbol must track its physical location in the byte stream, as well as virtual pointers to its neighbors. A Symbol struct is defined with start\_byte and end\_byte parameters to reference the bounds of the original text slice, alongside prev and next parameters typed as isize.43 These prev and next indices point to positions within the flat arena array, utilizing a sentinel value (such as \-1) to mathematically indicate the absence of a neighbor at the boundaries of the text chunk.43 A companion SymbolPair struct is designed to represent a potential merge candidate, storing the left index, the right index, and the merge priority score extracted from the binary artifact.43 The execution begins by mapping a chunk of text into an initial sequence of individual byte symbols in the arena array. The engine scans adjacent pairs; each pair is queried against the serialized integer merge rules to determine its priority rank. Valid pairs found within the vocabulary are pushed into a Binary Heap (alloc::collections::BinaryHeap), which inherently acts as an agenda prioritizing the lowest rank (highest priority) pairs.43 The main algorithmic loop repeatedly pops the highest-priority pair from the heap. The engine first verifies that neither the left nor the right symbol has been invalidated by a prior merge.43 If valid, the merge is executed entirely via metadata manipulation. Rather than deleting elements and physically shifting the array, the right symbol is simply flagged as deleted by updating a state boolean. The left symbol is mutated in place: its end\_byte is extended to encompass the deleted right symbol's bytes, and its next pointer is updated to point directly to the right symbol's subsequent next neighbor.43 Finally, the engine queries the newly formed symbol against its new immediate left and right neighbors; if these form valid merge pairs found in the binary vocabulary, they are dynamically pushed onto the agenda heap.43 This sequence repeats until the priority heap is entirely exhausted. The final output sequence is generated by traversing the arena array via the next pointers, starting from the first symbol, skipping any nodes marked as deleted, and yielding the remaining merged tokens.43 This linked-list arena technique ensures that neighbor updates and node invalidations are executed in strict [Figure omitted from source export] time, maintaining dense memory locality and vastly outperforming standard iterative string replacements while strictly avoiding heap allocation overhead.43

Unigram Tokenization and Viterbi Decoding Optimization

While BPE relies on deterministic, frequency-based mechanical merge rules, the Unigram tokenization model approaches the segmentation problem probabilistically.1 Utilized extensively in models like Google's T5 and ALBERT, Unigram operates under the fundamental assumption that every token in the vocabulary has an independent probability of occurring.19 Consequently, the goal of the inference engine is not to iteratively merge characters, but rather to evaluate all possible segmentations of the input string and identify the specific sequence that maximizes the overall product of the individual token probabilities.37 Mathematically, for a given text sequence mapped to tokens [Figure omitted from source export], the objective is to maximize the likelihood function [Figure omitted from source export].33 To avoid severe floating-point underflow errors when multiplying many infinitesimally small probabilities in software, the algorithm operates entirely in logarithmic space.37 Thus, the objective transforms into maximizing the sum of log-likelihoods: [Figure omitted from source export]. These log-likelihood scores are the exact negative f32 floating-point numbers embedded during the offline Python serialization phase.37 The computational problem of finding the optimal segmentation sequence is a classic decoding challenge, universally solved utilizing the Viterbi algorithm.33 Originally designed in 1967 by Andrew Viterbi to decode convolutional codes over noisy transmission channels, the algorithm is a dynamic programming approach that identifies the most likely path through a hidden Markov model.60 In telecommunications, soft-decision Viterbi decoders utilize branch metrics representing the Euclidean distance between received voltages and expected voltages.61 In the realm of NLP tokenization, the "states" represent character positions within the input text, the "branch metrics" represent the log-likelihood scores of the subword tokens bridging those positions, and the "path metric" represents the accumulated score of the optimal token sequence up to that point.60 The implementation of the Viterbi algorithm in Rust requires a rigorous two-step process: a forward pass to calculate the maximum path metric up to each character boundary, and a backward pass through a traceback memory to reconstruct the chronological sequence.37 The primary data structure required for tracking these paths is a Node struct. To maintain the overarching zero-allocation constraints of TinyRustLM, the node utilizes a Rust lifetime 'a to borrow string slices directly from the input text, completely avoiding String clones.37 The struct encapsulates the &'a str text, the floating-point score, the integer index of the token, and the start and end byte offsets relative to the input sequence.37 A naive implementation of the forward pass iterates through every possible sub-slice of the input text, checking if the sub-slice exists within the vocabulary.37 If it does, the local score is calculated as the sum of the best path metric up to the start of the sub-slice and the branch metric of the token itself. If this local score exceeds the previously recorded best score for the end position of the sub-slice, the path array is updated.37 However, this nested loop generates an [Figure omitted from source export] substring scanning complexity, creating severe computational bottlenecks for long inputs, mirroring the performance degradation seen in unoptimized BPE.37 To achieve the performance required for production rerankers and classifiers, the Unigram inference engine must utilize a character-based Directed Acyclic Graph (DAG) or a Trie structure.1 This Trie can either be built dynamically in Rust at load time, or optimally, serialized directly into the binary artifact offline. In the Trie, nodes representing complete, valid tokens are marked as leaves and store their associated log-likelihood score.37 Instead of generating all possible substrings manually, the algorithm employs a common\_prefix\_search function.37 Starting at a specific character position, it traverses the Trie byte by byte.37 If it encounters a leaf node, it evaluates the score. Crucially, if it encounters a character that does not exist in the current node's children, it immediately terminates the search for that starting position, pruning the search tree.37 This prefix search restricts the evaluation exclusively to sequences that actually exist in the vocabulary, dramatically reducing the computational search space.37 The forward pass populates an array of state scores initialized to negative infinity, progressively updating them to the maximum possible log-likelihoods.37 Special handling must be implemented for unknown characters. If the prefix search yields absolutely no matches, the algorithm forces a generic unknown token (\<UNK\>) with a score of zero for that single character, allowing the dynamic programming sequence to recover and continue without permanently stalling.37 Once the forward pass completes and the maximum scores at each character boundary are established, the backward pass initiates. The algorithm starts at the final character position and traces backwards by referencing the start index stored in the optimal Node for that position, effectively utilizing it as a traceback memory pointer.37 This tracing collects the sequence of nodes in reverse chronological order.37 A final reversal of this collected array yields the correct sequence of optimally segmented tokens.37 The performance gains achieved by implementing a custom Trie-based Viterbi decoder in pure Rust are substantial. Benchmarks indicate that replacing generic HuggingFace tokenizers with focused, zero-allocation Unigram implementations cuts p50 latency by roughly 5x, and outperforms standard C++ SentencePiece implementations by 2x.1 By operating without multi-threading overhead or Python Global Interpreter Lock (GIL) serialization constraints, this approach reduces CPU utilization in the inference stack by 5-6x, shaving double-digit milliseconds off reranker latency and demonstrating the immense value of custom embedded tokenizers.1

WordPiece Tokenization and Linear MaxMatch Architecture

WordPiece tokenization, introduced prominently with Google's BERT architecture, serves as an operational middle ground between the deterministic mechanical nature of BPE and the probabilistic complexity of Unigram.5 Unlike BPE, which relies on a strict sequence of hierarchical merges across the entire text string, WordPiece tokenization processes words individually and utilizes a greedy longest-match-first strategy known as MaxMatch.63 Furthermore, WordPiece introduces a unique vocabulary structure that must be handled delicately in software: subwords that form the beginning of a word are represented normally, while subwords that continue a word are prefixed with a designated marker, most commonly \#\#.5 For example, the word "unbelievable" might be tokenized into \["un", "\#\#believ", "\#\#able"\]. The \#\# prefix explicitly designates that the token is attached to the preceding subword without an intervening space.13 Consequently, when building a custom WordPiece engine, the pre-tokenization phase must aggressively split the input text on whitespace and punctuation, processing the resulting words entirely independently, in stark contrast to byte-level BPE.19 The standard MaxMatch algorithm iterates over an input word, searching for the absolute longest substring starting from the current position that exists within the loaded vocabulary.65 Once the longest match is successfully found, the token is recorded, the starting position is advanced to the end of the match, and the algorithm repeats from the new position.34 From the second iteration onward, the algorithm must ensure that subsequent searches exclusively look for tokens bearing the \#\# prefix to signify continuation.34 If no match whatsoever can be found at any point in the word, the entire tokenization for that specific word fails, and the entire sequence of characters is typically replaced by a single unknown token marker (\[UNK\]).20 Similar to Unigram and BPE, relying on a naive nested loop for the MaxMatch algorithm results in inefficient computational scaling. The algorithm can be significantly accelerated using a standard Trie data structure to match prefixes rapidly.34 However, even a standard Trie approach can suffer from severe backtracking inefficiencies. When a long sequence of characters appears to form a valid prefix but ultimately fails to match completely at the end, the algorithm must step back, reset its pointers, and re-evaluate shorter prefixes, leading to wasted CPU cycles.34 To implement a highly optimized, no-crate WordPiece tokenizer in Rust that outperforms implementations in C\# and C++, the architecture should leverage the advanced LinMaxMatch algorithm.64 Inspired by the Aho-Corasick string matching automaton, LinMaxMatch dramatically augments the standard vocabulary Trie by introducing auxiliary "failure links".63 During the offline Python serialization phase, the script constructs the Trie from the WordPiece vocabulary. For every single node in the Trie, it calculates a failure link. If the runtime algorithm is traversing the Trie and fails to find a matching child node for the next character in the input string, the failure link immediately directs the state machine to a fallback node representing the longest possible valid suffix of the current string, without resetting the search to the beginning.63 Additionally, the offline script computes a "failure pop" value for each node, which explicitly specifies the exact tokens that should be emitted to the output array if a failure occurs at that specific state.34 By calculating these mathematical relationships offline and embedding these failure links directly into the custom binary .bin format alongside the string pool, the Rust inference engine can execute WordPiece tokenization in strict [Figure omitted from source export] linear time.64 The algorithm simply iterates through the characters of the input word exactly once.65 It navigates down the Trie matching characters; upon encountering a mismatch, it utilizes the precomputed failure link to instantaneously jump to the appropriate fallback state, emitting the precalculated failure pop tokens along the way.34 This optimization completely eliminates all backtracking. It ensures that the time complexity remains strictly proportional to the length of the input word, devoid of any vocabulary-specific multiplicative factors or deep recursive calls.64 In a system constrained by strict performance parameters, such as a zero-allocation Rust embedded environment, this deterministic state-machine approach ensures that WordPiece tokenization scales linearly even for pathological long-tail inputs.55 Experimental results show that LinMaxMatch algorithms are 3x faster on average than production systems and up to 4.5x faster at the 95th percentile.65 Furthermore, because the state transitions and token emissions are entirely precomputed and mapped into the embedded binary, the Rust runtime simply reads memory offsets and assembles slice references, avoiding the dynamic memory allocations and class instantiations that plague less optimized C\# and Python wrappers.66

Conclusion

The pursuit of minimal, dependency-free inference engines represents a critical frontier in deploying large language models to edge devices, embedded systems, and highly optimized server environments. By strategically decoupling the tokenization process from heavy, generalized frameworks like HuggingFace's tokenizers crate or Google's sentencepiece, engineers gain granular control over memory allocation, compilation footprint, and execution latency. The comprehensive strategy delineated in this report—shifting the algorithmic complexity to an offline Python serialization script and designing a robust, dense custom binary format—forms the backbone of this methodology. Whether implementing Byte-Pair Encoding, Unigram, or WordPiece tokenization, the underlying principles of memory efficiency remain aggressively consistent. The usage of Rust's include\_bytes\! macro, combined with explicit \#repr(C, align(4)) memory alignment attributes, enables instantaneous, zero-cost access to the static .rodata segment without risking hardware-level alignment faults or stack overflows. By leveraging advanced, highly specialized data structures directly atop these memory slices—such as arena-based doubly linked lists for BPE, Trie-backed Viterbi dynamic programming decoders for Unigram, and LinMaxMatch failure link automata for WordPiece—the inference engine bypasses traditional runtime bottlenecks and combinatorial explosions. The synthesis of these techniques ensures that the "TinyRustLM" architecture operates with absolute determinism, matching or exceeding the theoretical complexity limits of industry-standard libraries while maintaining a pristine, allocation-free execution environment suitable for the most demanding deployment parameters.

Works cited

1. Improving Unigram Tokenizer CPU Performance \- Perplexity Research, accessed June 29, 2026, https://research.perplexity.ai/articles/improving-unigram-tokenizer-cpu-performance
2. Let's build the GPT Tokenizer \- YouTube, accessed June 29, 2026, https://www.youtube.com/watch?v=zduSFxRajkE
3. tokenizers \- Rust \- Docs.rs, accessed June 29, 2026, https://docs.rs/tokenizers/
4. google/sentencepiece: Unsupervised text tokenizer for Neural Network-based text generation. \- GitHub, accessed June 29, 2026, https://github.com/google/sentencepiece
5. Tokenizers in Language Models \- MachineLearningMastery.com, accessed June 29, 2026, https://machinelearningmastery.com/tokenizers-in-language-models/
6. GitHub \- swaits/bpe-tokenizer: A Rust library to do Byte Pair Encoding (BPE) tokenization., accessed June 29, 2026, https://github.com/swaits/bpe-tokenizer/
7. llama2.c/run.c at master · karpathy/llama2.c · GitHub, accessed June 29, 2026, https://github.com/karpathy/llama2.c/blob/master/run.c
8. llama2, accessed June 29, 2026, https://www.marble.onl/posts/llama2.html
9. Understanding Llama2.c And ChatGPT Inferencing – A Visual Design Walkthrough, accessed June 29, 2026, https://www.signalpop.com/2024/02/10/understanding-llama2-c-and-chatgpt-a-visual-design-walkthrough/
10. How to run Llama 2 LLM in C \- by Kevin Haritmonds \- Medium, accessed June 29, 2026, https://medium.com/@mckev/how-to-run-llama-2-llm-in-c-843b462daed9
11. Want to write a binary parser, what crates should I use? : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/18prh6o/want\_to\_write\_a\_binary\_parser\_what\_crates\_should/
12. GitHub \- karpathy/llama2.c: Inference Llama 2 in one file of pure C, accessed June 29, 2026, https://github.com/karpathy/llama2.c
13. Introduction to HuggingFace Tokenizers \- Cameron Barker, accessed June 29, 2026, https://cameronbarker.me/posts/intro-to-hf-tokenizers/
14. include\_bytes\_aligned \- Rust \- Docs.rs, accessed June 29, 2026, https://docs.rs/include\_bytes\_aligned/latest/include\_bytes\_aligned/
15. include\_bytes\_aligned \- crates.io: Rust Package Registry, accessed June 29, 2026, https://crates.io/crates/include\_bytes\_aligned
16. Can i conveniently compile bytes into a Rust program with a specific alignment?, accessed June 29, 2026, https://users.rust-lang.org/t/can-i-conveniently-compile-bytes-into-a-rust-program-with-a-specific-alignment/24049
17. Include\_bytes\! with custom alignment? \- help \- The Rust Programming Language Forum, accessed June 29, 2026, https://users.rust-lang.org/t/include-bytes-with-custom-alignment/39051
18. TokenBreak: Bypassing Text Classification Models Through Token Manipulation \- arXiv, accessed June 29, 2026, https://arxiv.org/html/2506.07948v1
19. Tokenization algorithms \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/transformers/en/tokenizer\_summary
20. Building a tokenizer, block by block \- Hugging Face, accessed June 29, 2026, https://huggingface.co/learn/llm-course/en/chapter6/8
21. Tokenizer \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/transformers/main\_classes/tokenizer
22. Input sequences — tokenizers documentation \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/tokenizers/python/latest/api/reference.html
23. Tokenizer \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/transformers/en/main\_classes/tokenizer
24. Tokenization in Transformers v5: Simpler, Clearer, and More Modular \- Hugging Face, accessed June 29, 2026, https://huggingface.co/blog/tokenizers
25. Tokenization Confusion \- SpecterOps, accessed June 29, 2026, https://specterops.io/blog/2025/06/03/tokenization-confusion/
26. hkeshhk/bpetokenizer \- Hugging Face, accessed June 29, 2026, https://huggingface.co/hkeshhk/bpetokenizer
27. BlockBPE: Parallel BPE Tokenization \- arXiv, accessed June 29, 2026, https://arxiv.org/html/2507.11941v1
28. Byte Pair Encoding (BPE): From Data Compression to GPT-2 Tokenization | by Daksh Rathi, accessed June 29, 2026, https://medium.com/@dakshrathi/byte-pair-encoding-bpe-from-data-compression-to-gpt-2-tokenization-44e35be2fd58
29. Tokenization algorithms \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/transformers/tokenizer\_summary
30. Byte Pair Encoding (BPE) Tokenizer From Scratch \-- Simple \- GitHub, accessed June 29, 2026, https://github.com/rasbt/LLMs-from-scratch/blob/main/ch02/05\_bpe-from-scratch/bpe-from-scratch-simple.ipynb
31. Tokenization in Large Language Models | by Anwar Gh \- Medium, accessed June 29, 2026, https://medium.com/@anwgh/tokenization-in-large-language-models-1f7c3c67228f
32. tokenizers \- Hugging Face, accessed June 29, 2026, https://huggingface.co/docs/transformers.js/v3.8.1/en/api/tokenizers
33. DmitryAsdre/UnigramTokenization: Unigram Tokenization realization from scratch \- GitHub, accessed June 29, 2026, https://github.com/DmitryAsdre/UnigramTokenization
34. Fast WordPiece Tokenization \- ACL Anthology, accessed June 29, 2026, https://aclanthology.org/2021.emnlp-main.160.pdf
35. sentencepiece \- Rust \- Docs.rs, accessed June 29, 2026, https://docs.rs/sentencepiece
36. sentencepiece-model \- crates.io: Rust Package Registry, accessed June 29, 2026, https://crates.io/crates/sentencepiece-model
37. A Rust SentencePiece implementation | Rust NLP tales, accessed June 29, 2026, https://guillaume-be.github.io/2020-05-30/sentence\_piece
38. Rust for working with binary protocols \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/155jhf5/rust\_for\_working\_with\_binary\_protocols/
39. A bit of rust \- Bilal Durrani, accessed June 29, 2026, https://bilaldurrani.com/post/2020/01/19/a-bit-of-rust/
40. This has got to be simple : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/1fmc67b/this\_has\_got\_to\_be\_simple/
41. Tokenizer.from\_file() HUGGINFACE : Exception: data did not match any variant of untagged enum ModelWrapper \- Stack Overflow, accessed June 29, 2026, https://stackoverflow.com/questions/74279005/tokenizer-from-file-hugginface-exception-data-did-not-match-any-variant-of
42. How can I build a vocab.bpe file for GPT and GPT2 models using my own text corpus?, accessed June 29, 2026, https://community.latenode.com/t/how-can-i-build-a-vocab-bpe-file-for-gpt-and-gpt2-models-using-my-own-text-corpus/35990
43. Byte Pair Encoding and Data Structures | Rust NLP tales, accessed June 29, 2026, https://guillaume-be.github.io/2021-09-16/byte\_pair\_encoding
44. Fixing include\_bytes\! : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/ih7ecn/fixing\_include\_bytes/
45. Large consts vs statics \- help \- The Rust Programming Language Forum, accessed June 29, 2026, https://users.rust-lang.org/t/large-consts-vs-statics/128594
46. Generating static arrays during compile time in Rust \- DEV Community, accessed June 29, 2026, https://dev.to/rustyoctopus/generating-static-arrays-during-compile-time-in-rust-10d8
47. How to handle function returning large static array : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/1sifhj9/how\_to\_handle\_function\_returning\_large\_static/
48. u32 \- Rust, accessed June 29, 2026, https://doc.rust-lang.org/std/primitive.u32.html
49. What is the most idiomatic way to convert a slice of u8 array into u32 using u32::from\_le\_bytes() in Rust? \- Stack Overflow, accessed June 29, 2026, https://stackoverflow.com/questions/76749778/what-is-the-most-idiomatic-way-to-convert-a-slice-of-u8-array-into-u32-using-u32
50. "from\_le\_bytes" Search \- Rust Documentation, accessed June 29, 2026, https://doc.rust-lang.org/stable/std/?search=from\_le\_bytes
51. Byte Pair Encoding: building the GPT tokenizer with Karpathy \- \- Francesco Pochetti, accessed June 29, 2026, https://francescopochetti.com/byte-pair-encoding-building-the-gpt-tokenizer-with-karpathy/
52. Let's Build the GPT Tokenizer: A Complete Guide to Tokenization in LLMs \- Fast.ai, accessed June 29, 2026, https://www.fast.ai/posts/2025-10-16-karpathy-tokenizers
53. Implementing A Byte Pair Encoding (BPE) Tokenizer From Scratch \- Sebastian Raschka, accessed June 29, 2026, https://sebastianraschka.com/blog/2025/bpe-from-scratch.html
54. bpe \- crates.io: Rust Package Registry, accessed June 29, 2026, https://crates.io/crates/bpe
55. Incremental BPE Tokenization \- arXiv, accessed June 29, 2026, https://arxiv.org/html/2605.30813v1
56. Cross posting from stack overflow "External-memory approach for BPE training where merges depend on text adjacency (160 GB corpus)" : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/1uezurj/cross\_posting\_from\_stack\_overflow\_externalmemory/
57. Which Pieces Does Unigram Tokenization Really Need? \- arXiv, accessed June 29, 2026, https://arxiv.org/html/2512.12641v1
58. VITERBI DECODER PROCESSING, accessed June 29, 2026, https://www.ece.ucdavis.edu/\~bbaas/281/notes/Handout.viterbi.pdf
59. Decode convolutionally encoded data using Viterbi algorithm \- Simulink \- MathWorks, accessed June 29, 2026, https://www.mathworks.com/help/comm/ref/viterbidecoder.html
60. The Viterbi Algorithm Demystified, accessed June 29, 2026, https://viterbischool.usc.edu/news/2017/03/viterbi-algorithm-demystified/
61. 6.02 Lecture 7: Viterbi decoding \- MIT OpenCourseWare, accessed June 29, 2026, https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/f398fa4a366439301b3d17e45e028952\_MIT6\_02F12\_lec07.pdf
62. An illustrated implementation of SentencePiece's unigram encoding : r/rust \- Reddit, accessed June 29, 2026, https://www.reddit.com/r/rust/comments/gvvm8l/an\_illustrated\_implementation\_of\_sentencepieces/
63. \[2012.15524\] Fast WordPiece Tokenization \- ar5iv \- arXiv, accessed June 29, 2026, https://ar5iv.labs.arxiv.org/html/2012.15524
64. arXiv:2012.15524v3 \[cs.CL\] 5 Oct 2021, accessed June 29, 2026, https://arxiv.org/pdf/2012.15524
65. Linear-Time WordPiece Tokenization \- ResearchGate, accessed June 29, 2026, https://www.researchgate.net/publication/348078675\_Linear-Time\_WordPiece\_Tokenization
66. GitHub \- NLPOptimize/flash-tokenizer: EFFICIENT AND OPTIMIZED TOKENIZER ENGINE FOR LLM INFERENCE SERVING, accessed June 29, 2026, https://github.com/NLPOptimize/flash-tokenizer