Quadratic time in bytePairMerge: one long run of repeated characters blocks for minutes

**Version:** 1.0.6 (latest) · **Node:** 24.16.0 (linux/docker), also reproduced on 24.13.1 (Windows) · **Encoding:** `o200k_base`

## Summary

`count()`/`encode()` take quadratic time in the length of a single "piece". Ordinary text is never affected, because the split pattern breaks it into short pieces. But the o200k pattern caps **digit** runs at three characters while leaving **letter, punctuation and whitespace** runs unbounded — so any long run without a word boundary becomes one enormous piece, and `bytePairMerge` goes quadratic.

The practical effect is that a single input can block a Node event loop for minutes.

## Reproduction

```js
import { Tokenizer } from 'ai-tokenizer';
import * as o200k from 'ai-tokenizer/encoding/o200k_base';
const tok = new Tokenizer(o200k);

console.time('50k underscores'); tok.count('_'.repeat(50000)); console.timeEnd('50k underscores');
console.time('480k of prose'); tok.count('the patient was stable. '.repeat(20000)); console.timeEnd('480k of prose');
```

```
50k underscores: 3948.9 ms
480k of prose: 9.0 ms
```

Ten times *less* input takes four hundred times *longer*.

### Scaling — doubling the input roughly quadruples the time

| chars | ms | tokens | vs previous |
|---|---|---|---|
| 6,250 | 104.9 | 100 | — |
| 12,500 | 343.2 | 197 | 3.27× |
| 25,000 | 1,253.5 | 392 | 3.65× |
| 50,000 | 3,948.9 | 782 | 3.15× |
| 100,000 | 15,468.7 | 1,563 | 3.92× |

Extrapolating, a ~1.1M-character input of this shape takes over nine minutes (measured: still running at 9.5 minutes when we killed it).

## Why

Two things combine.

**1. The split pattern bounds digit runs only.** From `o200k_base`'s `pat_str`:

```
\p{N}{1,3} <- digit runs capped at 3
?[^\s\p{L}\p{N}]+[\r\n/]* <- punctuation/symbol runs unbounded
\s+ <- whitespace runs unbounded
[\p{Ll}\p{Lm}\p{Lo}\p{M}]+ <- letter runs unbounded
```

Measured piece counts confirm it:

| input | pieces | longest piece |
|---|---|---|
| 50K underscores | 1 | 50,000 |
| 50K spaces | 1 | 50,000 |
| 50K digits | 16,667 | 3 |
| `'ab'.repeat(25000)` | 1 | 50,000 |

This is OpenAI's official o200k regex, so it isn't itself the defect — it's the input condition that exposes the next one.

**2. `bytePairMerge` is O(n²) in the piece length.** Each iteration of the merge loop does a full linear scan for the minimum rank plus two `Array.prototype.splice` calls, and the loop runs once per merge:

```js
while (starts.length > 1) {
let minRank = NO_RANK, minIdx = -1;
const ranksLen = ranks.length - 1;
for (let i = 0; i < ranksLen; i++) { // O(n) scan, every merge
const rank = ranks[i];
if (rank < minRank) { minRank = rank; minIdx = i; }
}
if (minRank === NO_RANK || minIdx === -1) break;
starts.splice(minIdx + 1, 1); // O(n)
ranks.splice(minIdx, 1); // O(n)
ranks[minIdx] = getRank(minIdx);
if (minIdx > 0) ranks[minIdx - 1] = getRank(minIdx - 1);
}
```

For normal pieces (a word, ~10 bytes) this is irrelevant. For a 50,000-byte piece it is fatal.

## Real-world occurrence

We hit this in production on a shared internal chat deployment (~750 users) that uses `ai-tokenizer` for token counting. It took the service down **four times in one day** before we identified it.

- Symptom: one CPU core pinned at 100%, HTTP requests unserved, health endpoint timing out at 10s, recovery only via restart.
- Attribution: per-thread CPU showed the Node **main thread at 101%** with all V8 worker threads and all libuv pool threads at 0%, and RSS at 24% of the container limit — so neither GC nor the threadpool.
- A V8 CPU sampling profile taken during a live incident showed **99.7% of 18,661 samples** with self time in `bytePairMerge`:

```
bytePairMerge node_modules/ai-tokenizer/dist/index.cjs:322
← bytePairEncode → encodeOrdinaryInto → encode
← (caller's token-counting wrapper)
```

- Trigger: text extracted by OCR from a scanned PDF, ~1.1M characters, containing long runs of repeated characters — the underscore field-rules and dot leaders that scanned forms are full of. Nothing exotic or adversarial; an ordinary business document.

That last point is why we're filing rather than just working around it: the triggering input isn't a crafted string, it's what OCR output normally looks like. Any service that counts tokens on user-supplied documents on a single-threaded runtime is exposed.

Happy to open a PR if you'd like a direction — we have a validated O(n log n) approach (linked list + lazy-deletion min-heap in place of the splices and the linear scan) that produces byte-identical output, but I didn't want to presume the fix before you've characterised the bug.

Start at bytePairMerge in dist/index.cjs and reproduce the slowdown with the 50,000-character underscore input through Tokenizer.count(). Compare the existing scan-and-splice loop with the proposed linked-list and lazy-deletion min-heap approach. Done means preserving byte-identical tokenization while avoiding quadratic behavior on long repeated-character pieces.

Written by the indexing model from the issue text.