Our Token Counter Took 26 Seconds on a Single Prompt

This is a submission for DEV's Summer Bug Smash: Smash Stories powered by Sentry.

Project Overview

I work on AcruxCore, an LLM ops platform with an Express API gateway. Every completion passes a budget pre-check: estimate the token cost, compare against the team's remaining spend, reject if it doesn't fit.

For OpenAI-family models, that estimate used js-tiktoken:

if (isOpenAiFamily) {
  try {
    return encoder().encode(text).length;
  } catch {
    // Fall through to the heuristic if the encoder rejects the input.
  }
}
return Math.ceil(text.length / 4);

Three lines. They do the right thing. They just don't always do it quickly.

Bug Fix or Performance Improvement

Performance bug — a quadratic BPE tokenizer on the synchronous request path.

I didn't find this through a user complaint. Two datasets tests started timing out at Jest's 5-second limit. I assumed I'd broken something, stashed my changes, checked out clean staging, and ran them again. Still failed.

The tests were fine. The code under them was just brutally slow.

The BPE encoder is quadratic on whitespace-free input. BPE works by repeatedly merging the most common adjacent pair of characters. Each pass scans the entire string to find the best pair. One merge per pass, full scan each time. A string of N characters with no whitespace means roughly N passes over N characters — N² work.

Normal text never hits this because the pre-tokenizer splits on whitespace first. Every piece is one short word (~5 chars), so N² is nothing. A long unbroken string has no whitespace to split on, so the whole thing becomes one piece and N becomes the full length.

Measured on cl100k_base (GPT-4's tokenizer):

single piece	encode time
256 chars	4 ms
512 chars	18 ms
1,024 chars	70 ms
2,048 chars	281 ms
9,000 chars	5.4 s
20,000 chars	26 s

Doubling the length roughly quadruples the time. Meanwhile, 20,000 characters of ordinary prose encodes in 3 ms. It's not the length — it's the lack of whitespace.

This function runs on every single request. Node runs JavaScript on one thread. A 26-second synchronous encode doesn't just slow down one request — it freezes every other user on that process.

And the input that triggers it isn't exotic: a base64 blob in a prompt, a minified JSON payload, a corrupted copy-paste. Any authenticated caller could stall the whole process.

gateway completion, 2-char rendered variable:      82 ms
gateway completion, 9000-char rendered variable:  5506 ms

Same code path. Same mocked provider. One template variable different.

Why not just remove the tokenizer?

My first thought. But estimateTokens has two jobs:

1. Budget pre-check — reject requests that would exceed the spend cap. Overestimate and you reject valid requests. Underestimate and teams blow past their budget.
2. Billing — when a provider streams without usage data, this estimate becomes the number on the user's bill.

And chars / 4 is a rough rule of thumb for English prose. It breaks on other inputs. Our test suite uses a synthetic 400 KB input (1,600 repetitions of 250 x characters plus a space — the same one that caused the timeouts):

Characters: 1,600 × 251 = 401,600
Exact BPE:  52,800 tokens  →  401,600 / 52,800 = 7.6 chars/token
chars / 4:  100,400 tokens  →  401,600 / 4 = 100,400 (nearly 2× the truth)

If your budget allows 80,000 tokens, the real prompt fits (52,800) but chars / 4 says it doesn't (100,400) and rejects it. Using chars / 4 everywhere would overestimate so aggressively that it would reject roughly half of all valid prompts.

So the tokenizer stays. It just doesn't get to run unbounded anymore.

Code

The work happened in a private repo, so the PR link won't help. The fixed file is public in our mirror, with the measurement table in the doc comment:

• apps/api/src/gateway/providers/token-estimate.ts

Before — the entire string in one encoder call:

if (isOpenAiFamily) {
  try {
    return encoder().encode(text).length;
  } catch { /* fall through to heuristic */ }
}
return heuristic(text.length);

After — two decisions: how much text to encode, and how to chop it up first:

if (isOpenAiFamily) {
  try {
    // Bound 2: past 20,000 chars, encode a sample and scale the rest.
    if (text.length <= MAX_BPE_SAMPLE_CHARS) return boundedEncode(text);
    const sampleTokens = boundedEncode(text.slice(0, MAX_BPE_SAMPLE_CHARS));
    const ratio = sampleTokens / MAX_BPE_SAMPLE_CHARS;
    return sampleTokens + Math.ceil((text.length - MAX_BPE_SAMPLE_CHARS) * ratio);
  } catch { /* fall through to heuristic */ }
}
return heuristic(text.length);

My Improvements

Two bounds. No new dependencies. No change to what it returns for normal input.

Bound 1 — cap each piece at 256 characters

Nothing over 256 characters reaches the encoder. Longer pieces get ceil(chars / 4) as a quick estimate instead.

This removes the quadratic cost entirely, because 256 chars keeps each encoder call under ~4 ms.

Important: 256 is a threshold, not a chunk size. A 1,024-character piece is not split into four 256-char chunks. It skips the encoder entirely and gets ceil(1024 / 4) = 256 directly. Zero encoder calls.

The text is only split at whitespace boundaries — to keep token counts accurate:

function boundedEncode(text: string): number {
  let tokens = 0;
  let pendingSeparator = '';
  for (const part of text.split(/(\s+)/)) {
    if (part.length === 0) continue;
    if (/^\s+$/.test(part)) {
      pendingSeparator += part;
      continue;
    }
    const piece = pendingSeparator + part;
    pendingSeparator = '';
    tokens += piece.length > MAX_BPE_PIECE_CHARS
      ? heuristic(piece.length)
      : encoder().encode(piece).length;
  }
  if (pendingSeparator.length > 0) {
    tokens += pendingSeparator.length > MAX_BPE_PIECE_CHARS
      ? heuristic(pendingSeparator.length)
      : encoder().encode(pendingSeparator).length;
  }
  return tokens;
}

The easy line to get wrong is pendingSeparator. Whitespace must be attached to the following word because tiktoken groups " word" as one token. Encode the space on its own and " the" becomes two tokens instead of one — every prose prompt gets overcounted by roughly its word count, and budget checks silently start rejecting requests they shouldn't.

A correctness bug from a performance fix is a bad trade.

Effect on the 20,000-character blob

	before	after
encoder calls	one, on 20,000 chars	none (20,000 > 256)
time	26,952 ms	0 ms
tokens returned	2,500	5,000

The count doubles — that's deliberate. ceil(chars / 4) overestimates, but 20,000 identical characters isn't a real prompt, and for a budget check, overestimating is the safe direction.

Ordinary text is untouched. "Hello world" splits into "Hello" and " world", both under 256, both encoded exactly as before.

Bound 2 — cap the total at 20,000 characters

Bound 1 only looks at one piece at a time. It never catches the case of many short pieces adding up.

1,600 repetitions of 250 xs plus a space = 400 KB. Each piece is 250 chars (under the 256 cap), so Bound 1 lets every one through. At ~4 ms each, that's 7 seconds. Bound 1 never triggers once.

Bound 2 fixes this: encode at most 20,000 characters total. For anything longer, encode the first 20K, measure the tokens-per-char ratio, and scale that ratio across the rest.

Step by step:

1. Take the first 20,000 characters
2. Run boundedEncode on them (still uses Bound 1 internally)
3. Get the token count from the sample
4. Divide by 20,000 to get a tokens-per-char ratio
5. Multiply the ratio by the remaining characters
6. Add sample tokens + tail estimate = return value

Effect on the 400 KB input

	bound 1 only	both bounds
characters encoded	401,600	20,000
time	7,018 ms	334 ms
tokens returned	52,800	52,771

The first 20K characters gave 2,628 tokens. Applied to the remaining 381,600 characters: 50,143 tokens. Total: 52,771 vs exact 52,800.

Sampled ratio:  2,628 / 20,000 = 0.13 tokens per character
chars / 4 ratio:            1 / 4 = 0.25 tokens per character

0.13 is roughly half of 0.25. Using chars / 4 would claim 95,400 tokens on the tail instead of 50,143 — nearly double the truth. The sample already measured the real ratio, so using it is almost as accurate as encoding everything, without the 7-second cost.

0.05% off, for 5% of the work.

Why 20,000 characters? At the 256-char piece cap, worst case is ~80 pieces (20,000 / 256). At ~4 ms each, that's ~320 ms — fast enough to stay on the request path. Anything bigger gets the sample treatment. The number isn't magic; it's where "encode everything" becomes "too slow."

Worst case is now roughly 350 ms for any input size.

Error direction

Bound 1 can only overestimate — ceil(chars / 4) always returns more tokens than real BPE on the inputs that trigger it. For a budget check, that's the safe direction.

Bound 2 is different: it extrapolates from a sample, so it can land slightly above or below the true count. The 400 KB case came out 0.05% low. But that only applies past 20,000 characters, and a fraction of a percent drift on a huge prompt is not a budget problem. A 7-second event-loop stall is.

Proving it didn't change the answer

A bounded estimator that returns different numbers is a new bug, not a fix. Tests pin exactness first, speed second.

Exactness — must match whole-string BPE on all normal input (under 20K chars):

it('matches whole-string BPE counts for ordinary text', () => {
  const encoder = getEncoding('cl100k_base');
  const samples = [
    'Hi Alice, what is the weather in London?',
    'The quick brown fox jumps over the lazy dog. '.repeat(114),
    'const x = foo.bar(baz, 42); // comment here\n'.repeat(100),
    JSON.stringify({ a: 'hello world', b: [1, 2, 3], c: { d: 'nested value here' } }).repeat(50),
  ];
  for (const sample of samples) {
    expect(estimateTokens(sample, 'gpt-4o-mini')).toBe(encoder.encode(sample).length);
  }
});

Prose, code, JSON: identical counts. No existing estimate moved.

Direction — pathological input must never come back low:

it('never underestimates the pathological input', () => {
  const encoder = getEncoding('cl100k_base');
  const text = 'x'.repeat(2000);
  expect(estimateTokens(text, 'gpt-4o-mini')).toBeGreaterThanOrEqual(encoder.encode(text).length);
});

Speed — one test per bound, so removing either guard fails immediately:

it('stays fast on a long unbroken run of characters', () => {
  estimateTokens('warm up the encoder', 'gpt-4o-mini');
  const started = Date.now();
  const n = estimateTokens('x'.repeat(50_000), 'gpt-4o-mini');
  expect(n).toBeGreaterThan(0);
  expect(Date.now() - started).toBeLessThan(1000);
});

it('stays fast when many pieces sit just under the per-piece cap', () => {
  estimateTokens('warm up the encoder', 'gpt-4o-mini');
  const text = `${'x'.repeat(250)} `.repeat(1600);
  const started = Date.now();
  const n = estimateTokens(text, 'gpt-4o-mini');
  expect(n).toBeGreaterThan(0);
  expect(Date.now() - started).toBeLessThan(1000);
});

The 1-second limit is deliberately generous — won't flake on loaded CI, but still fails instantly if someone removes a guard (the unfixed path takes minutes).

Results

	before	after
50,000-char unbroken run	minutes	< 1 s
400 KB of 250-char pieces	7,018 ms	334 ms
completion, 9,000-char variable (provider mocked)	5,506 ms	~82 ms
datasets test A	6,340 ms	410 ms
datasets test B	6,243 ms	323 ms

The timing-out tests were never touched. They passed because the code underneath stopped being slow.

What I'd carry to another codebase

• Test adversarial input, not your own. Every prompt I'd written was ordinary prose — the tokenizer's best case. Timing 'x'.repeat(20000) took ten minutes and found the whole bug.
• A synchronous function on a request path is a shared resource. "It's just a pure function over a string" stops being reassuring when the string is caller-controlled and the cost is superlinear.
• Pin the old answer before you optimize. An exact-match test against whole-string encoding is how I caught the pendingSeparator detail that would have silently overcounted every prompt.

---

If you're running a BPE tokenizer anywhere synchronous, it's worth timing encoder.encode('x'.repeat(20000)) on your own setup today. What did you get?