So many tokens, so little time: Introducing a faster, more flexible byte-pair tokenizer

Tokenization at scale: why standard BPE doesn't cut it

LLM-based products like GitHub Copilot rely on byte-pair encoding (BPE) tokenization, but the standard algorithms behind it have significant limitations that hurt scalability in real-world use cases. The fundamental issue: BPE implementations typically require complete input text upfront and only support encoding from scratch. This creates serious operational bottlenecks for systems that need more nuanced control over tokenization.

The missing operations

Modern LLM applications demand more than just encoding a full string. Critical workflows include:

• Incrementally tracking the token count of a chunk while it's being built.
• Counting tokens for slices of an original text or aborting counts when the text exceeds a given limit.
• Splitting text within a certain amount of tokens at a proper UTF-8 character boundary.

These operations matter particularly for retrieval augmented generation (RAG). RAG systems index content into an embeddings database and augment user prompts with relevant snippets from that database. Most code files exceed embedding model token limits, so files must be split accordingly. Prompt construction also requires strict token budgeting. When serving millions of repositories and billions of embeddings, tokenization efficiency becomes a top concern.

Implementing such operations using current tokenization algorithms would result in at least quadratic runtime, when we would like the runtime to be linear.

Consequences of slow tokenization extend beyond performance: they raise security concerns. Systems processing untrusted input can’t risk pathological runtimes from adversarial data that threatens availability. GitHub ultimately developed its own tokenizer, released as bpe and bpe-openai on crates.io (the latter includes convenience tokenizers with pre-tokenization for recent OpenAI models). The source code is open under the MIT license.

Type, run, verify

The tokenizer’s core design overcomes previous performance ceilings with linear scaling.

Benchmarking against the field

GitHub compared its implementation against tiktoken-rs (OpenAI's tiktoken library wrapper) and Huggingface’s tokenizers, all using OpenAI’s o200k_base token model. Tests were done with single-threaded throughput in MiB/s on an Apple M1 MacBook Pro.

With pre-tokenization enabled (which splits text into manageable pieces by step, the expected real-world outcome), bpe outperforms tiktoken by nearly 4x and Huggingface by about 10x. The results align with tiktoken’s own published performance claims, noting bpe’s single-threaded output only matches tiktoken’s when that library runs eight threads.

Without pre-tokenization (pathological input cases), the gap widens significantly. github's BPE shows the linear complexity advantage over Huggingface’s heap-based and tiktoken’s quadratic implementations.

How BPE works

BPE encodes text as a sequence of tokens from a fixed dictionary, where each token is either a single byte or a concatenation of previously defined tokens. Encoding proceeds by replacing pairs in a defined order.

Consider the dictionary:

a b c ac bb ab acbb

For the string abacbb, tokenization looks like:

1. a b a c b b
2. a b ac  b b
3. a b ac  bb
4. ab  ac  bb
5. ab  acbb

Notably, although ab appears first in the string, the token ac is merged first because the pair appears earlier in the dictionary. This ordering means BPE isn’t composable for incremental operations—changing the string length can cascade. Standard implementations either naively iterate until no merges remain (quadratic) or maintain a heap containing eligible token pairs (O(n log(n))), but neither enables incremental tokenization without restarting.

Finding a linear, usable path

GitHub's breakthrough insight defines what they call compatibility:

Given a valid encoding, we can append an additional token to produce a new valid encoding if the pair of the last token and the appended token are a valid encoding.

In this definition, "valid encoding" means the output matches what the original BPE algorithm would produce.

For example, ab ac is a valid encoding of abac. Can we extend it with b?

1. a c b
2. ac  b

Confirmed: ab ac b is valid. But trying to append bb instead fails:

1. a c b b
2. ac  b b
3. ac  bb 
4. acbb 

ab ac bb is not valid—the compatibility rule fails. Check anything beyond the previously valid pair, and you get different behavior.

Connecting chainable tokens to target lookup

The encoding scheme works left to right by finding the last token for each position. The algorithm iteratively enumerates all possible final tokens for a prefix at position i, then tests each candidate token against the final token of the remaining precedent. Storage is minimal: only the last token of each prefix’s encoding is ever retained.

Applying this to abacbb:

• a = a
• ab = ab
• aba = ab a
• abac = ab ac
• abacb = ab ac b
• abacbb = ab acbb

At step 6, the algorithm tests whether candidates b, bb, or acbb are compatible with the last token(s) of the 5-character prefixes, resolving to ab acbb as the only valid conclusion.

The implementation achieves efficiency through two levers:

• An Aho-Corasick automaton that finds all suffix tokens up to position i, preferring the longest candidates.
• Effective constant-time compatibility checking for pairs via in-line retokenization.

Both automaton construction and scans run linear in the input length; retokenization effort is bounded by the token dictionary’s dimensions. Net result: a linear-time algorithm built specifically for the partial-construction and partial-examination scenarios that real applications require.

Three ways to use the new tokenizer

The Rust crate implementing the new approach ships with three encoder variants, each optimized for a different use pattern:

Incremental encoders for dynamic content

The appending and prepending encoders support tokenizing text that grows over time. They store the last token for every position in the text and reuse that state when new content is added, so the current token count is always available in constant time. The design also supports constant-time snapshots and rollbacks, which makes it straightforward to build dynamic chunk-construction pipelines where you need to experiment with different boundaries.

A fast full-text encoder with backtracking

For one-shot tokenization of a complete input, the crate offers an encoder that skips the per-position bookkeeping. Instead, it processes the text left to right, selecting a candidate token for the remaining input and checking whether it aligns with the last token already emitted. When no candidate is compatible, the algorithm backtracks on the last token. Because it tests longer candidates first, this backtracking is rare in practice, keeping the common path fast.

Interval counting on subranges

A third variant answers token-count queries for any subrange of the original text in O(1) time, after a one-time O(n) preprocessing pass over the full text. The trick is to encode the substring only until the final token matches the token recorded at the same offset in the original full-text encoding. In typical cases, only a short prefix of the substring needs to be processed before this alignment occurs.

For readers who want to dig into the implementation, the crate's README documents the algorithm at a more detailed level and serves as a practical entry point into the codebase.