CRAYON

In large language model (LLM) pipelines, tokenization represents the initial gate between raw, unformatted sequence inputs and neural network layer embeddings. Traditional implementations represent vocabularies as dynamic pointer-heavy graph structures or complex hash tables. While flexible, these representations suffer from severe memory fragmentation, high latency CPU page table walks, and an inability to swap vocabularies dynamically without rebuilding internal pointer states.

CRAYON (frequently referred to in documentation logs by typographical alternatives such as Caryon, Cranyon, or Cryon) resolves this systemic bottleneck by shifting vocabulary representations from dynamic heap allocations to a memory-aligned, rigid binary **Double-Array Trie (DAT)** format. Rather than chasing heap-allocated node pointers, transitions are resolved in $O(1)$ constant-time via array indexing. When a tokenizer state needs to be loaded, Crayon maps the binary representation directly into memory space using the zero-copy system call `mmap`. This reduces vocabulary profile swap latency to a constant 0.54 milliseconds, allowing dynamic domain-specific adjustments on-the-fly.

Rather than loading monolithic, slow-parsing text configurations, Crayon packages its vocabulary sets into binary files known as Cartridges. Cartridges are structured to align directly with CPU/GPU L2/L3 cache blocks and are loaded via zero-copy mappings, which allow the operating system to map files directly to the address space. Crayon supports both standardized production sizes and specialized academic layouts.

Profile Resolution Hierarchy

When the Python wrapper calls `vocab.load_profile("profile_name")`, the system initiates a path traversal sequence to locate and map the profile. The resolution search paths are interrogated in the following order:

1. Package Internal Resources: Traverses `src/crayon/resources/dat/vocab_{profile_name}.dat`
2. Importlib Package Structure: Dynamically checks Python module directories.
3. Developer Directory Override: Queries directories mapped inside the `CRAYON_PROFILE_DIR` environment variable.
4. User Cache Cache: Searches `~/.cache/xerv/crayon/profiles/`
5. Unix Root Cache: Fallback to `/var/cache/crayon/`

The core data structure of Crayon is the Double-Array Trie (DAT). In classic graph-based tries, each node consists of dynamic pointer tables. Transitioning from state $s$ via a character byte $c$ requires chasing memory addresses, resulting in cache-misses. DAT compresses the entire node tree structure into three parallel, contiguous, cache-aligned integer arrays of equal length: `BASE`, `CHECK`, and `VALUES`.

Transition Mathematics

Given a parent state (or array index) $s$, and the current input character byte value $c$ ($0 \le c \le 255$):

If the ancestry validation fails ($\text{CHECK}[t] \ne s$), the state transition is marked invalid, terminating the current lookup path. Backtracking is resolved by reading the last valid `VALUES[t]` captured prior to state exhaustion.

Compiling a standard prefix trie into a Double-Array Trie is an offline packing problem. For each parent state, we must find an offset base value $b$ in the flat array such that the computed child slots $b + c_i$ (for all child characters $c_i$) are free from existing collisions. This operation is computationally heavy: $O(N \times M)$ where $N$ is vocabulary size and $M$ is alphabet length.

In Crayon, the compiler module (`compiler.cpp`) is implemented in native C++17. The packing algorithm performs a **First-Fit Linear Scan**:

1. Extract the children character bytes of a parent node: $\{c_1, c_2, ..., c_k\}$.
2. Initialize candidate base index scan: $b = 1$.
3. Interrogate array boundaries: test if $\text{CHECK}[b + c_i] == -1$ for all child elements.
4. If a collision occurs (any child slot is occupied), increment $b$ and repeat step 3.
5. Once a collision-free base offset $b$ is located, commit the value to $\text{BASE}[\text{parent}] = b$, and claim the slots by setting $\text{CHECK}[b + c_i] = \text{parent}$.

By moving this compiler layer from Python to native C++17 and releasing the Global Interpreter Lock (GIL) during compilation loops, Crayon compiles vocabularies ~500x faster than naive Python-based trie packers.

To maintain high throughput across varying environments, Crayon does not rely on a single execution path. It implements an **Omni-Backend** structure, targeting CPUs and GPUs via dedicated hardware-specific compilation layers:

1. CPU Engine: AVX2 ASCII-Optimistic Paths

Implemented in `cpu_engine.cpp`, the CPU backend features a dual-execution pathway. When tokenizing raw strings, the engine processes chunks of 32 characters in a single cycle using 256-bit SIMD registers to verify ASCII status:

inline int is_ascii_32_avx2(const char* ptr) {
    __m256i chunk = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(ptr));
    int mask = _mm256_movemask_epi8(chunk);
    return mask == 0;
}

If all 32 bytes are verified as ASCII, the engine activates the **Fast Path** loop, bypassing UTF-8 multibyte boundary validation. This allows the compiler to unroll loops, achieving over 18 million tokens/second on commodity CPU cores. When non-ASCII bytes are detected, it switches to the **Safe UTF-8 Path**.

Training subword vocabularies on large texts is often a bottleneck in NLP systems, as traditional implementations scan the entire text block to count frequencies and merge pairs in each iteration.

Crayon's BPE training engine (`trainer.cpp`) implements a single-core trainer using three coordinated system structures:

• Parallel Array Linked-List: The corpus is stored as four contiguous integer arrays: `tokens`, `prev_pos`, `next_pos`, and `active`. This keeps the training data inside the CPU cache. Merging adjacent elements is reduced to updating index pointers in constant time, rather than modifying string memory on the heap.
• Inverted Index (`pair_locations`): A hash map mapping each unique subword pair $(A, B)$ to its list of corpus index locations. The trainer updates only the affected sites, avoiding full corpus rescans.
• Lazy Max-Heap: A priority queue that stores pairs sorted by frequency. If a merge event invalidates adjacent pairs, the trainer does not adjust their counts in the heap. Instead, when a pair is popped, the trainer compares its heap count with the true count in the hash map. If they mismatch, it is discarded in $O(1)$ time, reducing heap restructure operations.

For production-grade deployments, Crayon incorporates several memory structures to handle large text data streams without allocation overheads:

Experience the live performance and dynamic vocabulary swaps on hardware-accelerated endpoints. The interface below hosts the **Official XERV Crayon Production Demo Sandbox** connected to native backends.

Below are the officially verified benchmark execution speeds capturing throughput characteristics of XERV Crayon against leading industry subword extraction tokenizers. Workloads were evaluated using a commodity AMD64 CPU platform on a standardized mixed-linguistic and syntax corpus.