900 KB of one repeated letter took almost six minutes to count
tiktoken-go is quadratic on one long piece of text: how we measured it, two fixes that did not hold, the 512-byte bounded count, and what it does to billed tokens.
The Apertis relay counts a prompt's tokens before it forwards the request. Part of that count runs the tiktoken encoder: tool definitions and tool-call text always, and all prompt text when exact counting is on. In an October load-test run, a 100 KB prompt made of one repeated character took 14 s end to end, and a 900 KB prompt of the same shape timed out at the origin. We suspected the tokenizer. Timed directly on our development host, an exact count of 900 KB of one letter took 5 min 49.6 s: tiktoken-go is quadratic on a long unbroken piece of text. This post covers the measurement, two fixes that did not hold, the one that did, and the billed count.
The short version
- The relay's exact count uses tiktoken-go v0.1.8. Its byte-pair merge is quadratic in the length of one regex piece, and it rescans the rest of the text at every special-token string it does not allow.
- The fix hands the encoder at most 512 bytes per call, cut where possible at a boundary between two regex pieces, and sums the counts.
- After the fix, 900 KB of one letter, of
"/\n", of the end-of-text token followed by a space, and of the Tamil, Myanmar and Khmer samples each count in 0.10 to 0.27 s on the same host. - The count is exactly the unsplit count on the constructed samples of repeated sentences we tested. On the other shapes tested, the total difference is at most one token per cut, or two for one white-space mix.
How we measured it
The load-test run sent the 900 KB prompt through our edge and also directly to the origin. It timed out both ways, so the edge was not the cause. That was one run, and it did not show which count was slow.
To isolate the counter, we timed the count itself on the main branch, outside any request: 8.45 s for 100 KB of one repeated letter, 5 min 49.6 s for 900 KB. Nine times the input took about 41 times as long.
Then we wrote the deadline we wanted as a test. It counts one letter repeated through every exact count path that takes request text, including a tool-call argument, a tool definition and a tool-call id. It requires 900 KB to finish under 2 s and 100 KB under 300 ms. On the main branch it failed 12 of 12 subtests.
Why one letter is expensive
tiktoken splits text into pieces with a regular expression, then runs byte-pair merging inside each piece. The merge is quadratic in the length of the piece. Ordinary text has short pieces, because a word ends at a space or a punctuation mark. One letter repeated for 900 KB is a single piece 900 KB long.
There is a second cost. At every special-token string the encoder finds and does not allow, such as <|endoftext|>, it rescans the rest of the text. A prompt that repeats that string costs quadratic time without any long piece in it.
What did not work
Bounding runs of one character class
The first version cut only long runs of one character class. That is not a bound, because what makes a piece long depends on the encoding. Before that version was pushed, one case had already been fixed: the regex's \s is unicode.IsSpace, so "\u3000\n" repeated (an ideographic space and a newline) is one white-space piece, and white space had to be classified by decoded rune. Two shapes still got through. In o200k, the encoding of gpt-4o, "/\n" repeated is one piece that mixes punctuation and line breaks. And <|endoftext|> repeated stalls on the special-token rescan, which has nothing to do with pieces. The new piece-shape deadline test runs those two shapes on both encodings through two count paths, and at that version 6 of its 8 subtests failed.
Cutting only after letters and numbers
The second version bounded every call and preferred to cut where a letter is followed by a non-letter, or a number by a non-number. Review found the gap: in Tamil, Myanmar and Khmer, words end in combining marks, so a letter is rarely followed by a non-letter, and the cut fell inside a piece. The count drifted up. Tamil on o200k counted 1070 tokens against 1042 unsplit, 28 tokens over 19 cuts.
The fix: bound every encode call
Every exact count of request text now goes through one helper, boundedTokenCount. It splits the text into consecutive parts of at most 512 bytes; text of 512 bytes or less stays one call, as before. Each cut is on a UTF-8 rune boundary. In the second half of the window, the cut takes the last point that is a boundary between two regex pieces in both cl100k and o200k:
switch {
case unicode.IsLetter(prev) && !unicode.IsLetter(next) && !unicode.IsMark(next) && next != '\'':
return p
case unicode.IsNumber(prev) && !unicode.IsNumber(next):
return p
case !prevSpace && nextSpace && next != '\r' && next != '\n':
return p
case (prev == '\r' || prev == '\n') && !nextSpace && next != '/':
return p
}
The last two cases, a non-white-space character before white space and a line break before a character that is neither white space nor /, are the fix for Tamil, Myanmar and Khmer. The slash is excluded because the o200k punctuation piece can take one after a newline. The comment on boundedTokenCut checks each point against both patterns as vendored, including at the ends of a part. With no such point in the window, as in one repeated letter, the cut falls at the last rune boundary.
With every call at most 512 bytes, a piece costs at most O(512²) merge steps and a special-token rescan O(512), so a prompt of n bytes costs O(n × 512) whatever its pieces look like.
We picked 512 from a benchmark on 900 KB of one letter on gpt-4o, run on the first version of the pull request on a host at load 16:
| Part size | Time for 900 KB of one letter |
|---|---|
| 512 bytes | 0.24 s |
| 1024 bytes | 0.41 s |
| 2048 bytes | 0.70 s |
| 4096 bytes | 1.27 s |
512 was the smallest candidate and kept this prompt well under the 2 s deadline.
The result
Counted on the development host:
| Input | Before | After |
|---|---|---|
| 100 KB of one letter | 8.45 s | under the 300 ms deadline (deadline test, gpt-4o) |
| 900 KB of one letter | 5 min 49.6 s | 0.16 to 0.27 s |
900 KB of "/\n" repeated, o200k |
about 220 s, extrapolated | 0.16 to 0.27 s |
900 KB of <|endoftext|> repeated, cl100k |
about 2 min | 0.16 to 0.27 s |
| 900 KB of the Tamil, Myanmar and Khmer samples | — | 0.10 to 0.13 s |
| 900 KB of English prose or Chinese | unsplit time | 0.93 to 1.08 times the unsplit time |
The 900 KB "after" times come from BenchmarkBoundedTokenCountShapes on gpt-4 (cl100k) and gpt-4o (o200k), run on the pull request's branch. The 100 KB row is the deadline test's pass, not a timing. The one-letter "before" figures are direct timings on the same host and name no model. The last row is text that never needed the bound: within 8 percent of the old time either way.
After the merge, a staging run sent two 900,000-character chat requests through our staging gateway to a stub upstream: one letter repeated, and prose. Both returned 200, in 5.2 s and 2.1 s end to end, and the stub recorded the full prompt each time. That was one run. The change shipped in release 49f1a72a16b4.
What happens to the billed count
This count is not only a display number. When the upstream reports no usage, the relay's prompt estimate is the settled price. The split can move a billed count only where the relay counts exactly: tool definitions and tool-call text in every mode, and all prompt text when exact counting is on.
A cut between two regex pieces changes nothing. A cut inside a piece can, because each side may lose a merge. What the tests assert, on both encodings:
- Exact on the tested samples. Constructed samples of repeated sentences: English, Chinese with punctuation, Go source, a JSON tool schema, a JSON array of numbers, Tamil, Myanmar with spaces, Myanmar with line breaks only, and Khmer count exactly as the unsplit encoder does at 1, 8 and 64 KB, split at 512, 1024 and 4096 bytes. That is all the exactness we claim, not exactness for arbitrary text.
- Bounded per cut elsewhere. A second test measures shapes with no boundary point in reach at six sizes from 2 to 16 KB, and holds the total difference, in either direction, to at most one token per cut. A run alternating U+00A0 and an ASCII space is held to two per cut, because both sides of a cut can lose a merge there. This holds for every shape the test measures; it is not a proof for every input.
The worst measured difference divided by the number of cuts, at 512 bytes:
| Shape | Worst tokens per cut, averaged over the cuts |
|---|---|
| Alternating U+00A0 and space | 1.50 (cl100k), 1.38 (o200k) |
| Khmer with every space removed | 1.00 (cl100k) |
| Myanmar with every space removed | 0.77 (o200k) |
| Digits only | 0.40 |
| Tamil with every space removed | 0.25 (o200k), 0 (cl100k) |
One letter, base64, unpunctuated Han, spaces, newlines, "/\n" |
0 |
To check that the tests can fail, we broke the code one way at a time and restored it each time. Encoding the whole text failed 64 subtests. Dropping the boundary preference gave 2136 tokens against 2127. Dropping the number point gave 33275 against 33207 on a list of numbers. Dropping the white-space point gave 32306 against 32242 on 64 KB of Tamil on cl100k. Dropping the line-break point gave 10981 against 10853 on 64 KB of Myanmar with line breaks on o200k. Holding the U+00A0 mix to a total of one token per cut made the bound test fail, so that exception is needed.
What we would do differently
- Write the deadline test before the fix. The 12 of 12 failures on main defined "fixed" before any code changed. Under the race detector the deadline is scaled by 10 instead of skipped, and a quadratic count, which takes minutes, still fails it.
- Bound the cost, not a kind of input. The first version bounded the input we had imagined. The encoder's cost depends on pieces and special tokens, which depend on the encoding. A cap on each call's length holds for any text.
- Put scripts with combining marks in the equality table from the start. Tamil, Myanmar and Khmer joined the table in the same commit as their fix, after review found the drift.
- Write the billing claim exactly as the tests state it. "Counts do not change" would have been wrong. "Exact on these samples, a total difference of at most one token per cut on these shapes" is what we can show.
Still open
- We have not measured large-prompt latency in production. The numbers here come from the development host and one staging run.
- The large-body evidence after the fix went through staging. We did not repeat the 900 KB run through the load-test environment's edge and load balancer.
- Khmer with every space removed measures exactly 1.00 token per cut on cl100k, on average over its cuts, which is the bound itself. A tokenizer or sample change that moves it up slightly will turn the bound test red without a real regression.