CRAYON: Hardware-Accelerated BPE Tokenization via Zero-Copy Double-Array Tries and SIMD Vectorization

Subword tokenization is a critical preprocessing gate in Large Language Model (LLM) inference and training pipelines.Traditional tokenizers rely on pointer-heavy trie structures or dynamic hash tables, introducing severe memory fragmentation, highpointer-chasing latencies, and significant cold-start loading overheads. This paper presents CRAYON, a systems-first BPE tokenizationframework that represents vocabulary matching using memory-aligned Double-Array Tries (DAT). CRAYON achieves zero-copy,sub-millisecond vocabulary swaps via operating system memory mapping. To optimize inference, CRAYON integrates an optimistic AVX2SIMD scanning pathway that processes 32-byte ASCII blocks in a single instruction cycle, bypassing UTF-8 validation overhead whensafe. For massive parallel batch processing, CRAYON introduces a GPU-accelerated parallel lookup engine in CUDA and ROCm/HIP,bypassing thread-wide lock contention through dynamic batch capacity planning. Furthermore, CRAYON implements a mathematicallyexact greedy BPE training algorithm optimized via a parallel-array linked list, an inverted occurrence index, and a lazy max-heap priorityqueue. Empirical evaluation demonstrates that CRAYON achieves CPU throughput exceeding 18.4 million tokens/sec on standardbenchmarks, outperforming Rust-based implementations by up to 35×, while maintaining a cold-start initialization latency of only 0.54 ms.