Design and Implement a Trie-Based Subword Tokenizer for LLM Pretraining

Context

You are tasked with designing and implementing a subword tokenizer for a large-scale LLM pretraining pipeline. The tokenizer must meet stringent production requirements: it must be deterministic, fast, memory-efficient, and Unicode-safe.

Requirements

API

The tokenizer must expose the following core API:

• build(vocab, config) -> Tokenizer: Constructs the tokenizer from a given vocabulary and configuration.
• tokenize(text) -> List[int]: Converts input text into a list of token IDs.
• detokenize(ids) -> str: Reconstructs text from a list of token IDs.
• Optional: encode(text) -> List[str] (returns subword pieces) and decode(pieces) -> str (reconstructs text from subword pieces).

Core Algorithm

• Implement greedy longest-prefix matching using a prefix trie built from a fixed vocabulary of subword strings.
• Matching must operate over Unicode code points, not bytes, to correctly handle multi-byte UTF-8 characters, emojis, and CJK scripts.

Unicode Handling

• The tokenizer must correctly process complex Unicode inputs, including multi-byte UTF-8, emojis (e.g., ZWJ sequences, variation selectors), CJK characters, Right-to-Left (RTL) scripts, and combining marks.
• The candidate must specify whether matching operates on bytes, code points, or grapheme clusters, and justify the choice.

Normalization and Casing

• Define and justify normalization choices (e.g., NFKC), discussing their impact on reversibility.
• Define a casing policy (e.g., preserve case vs. lowercasing) and explain its implications for detokenization fidelity.

Whitespace and Punctuation

• Establish clear rules for handling whitespace (e.g., SentencePiece-style "▁" for spaces or GPT-style leading-space tokens) and punctuation.
• Clarify how multiple spaces, tabs, newlines, and various punctuation marks are tokenized.

Unknown-Token Fallback

• Implement a robust fallback mechanism for situations where no subword matches at a given position.
• Discuss options such as a dedicated <unk> token versus a byte-level fallback, considering total coverage and reversibility.

Complexity Analysis

• Provide time and space complexity analysis for the build, tokenize, and detokenize operations.
• Include practical memory estimates and throughput considerations relevant for a production environment.

Incremental Vocabulary Updates

• Describe strategies for adding new tokens to the vocabulary incrementally without compromising determinism.
• Discuss versioning, hot-swap strategies, and the implications for previously tokenized data.

Testing Strategy

• Propose a comprehensive testing strategy, including specific test cases for challenging inputs: emojis (with ZWJ sequences and skin tones), CJK text without explicit spaces, combining marks, RTL scripts, invalid UTF-8 sequences, runs of whitespace, URLs, and code snippets.

Comparison to Alternatives

• Compare the proposed trie-based approach with alternative subword tokenization methods like BPE, WordPiece, or Unigram.
• Discuss the trade-offs, particularly concerning throughput and memory usage in a production setting.