exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
//! The batching order and the span buffer behind it. OWNER: EncodeBatchingOrder.
//!
//! Two optimizations landed together on the encode path, and this suite pins
//! both by COUNT, never by duration:
//!
//! * `batches` orders runs by counting sort instead of
//!   `sort_by_key(|i| (Reverse(len), i))`. The permutation must be
//!   byte-identical to the one the comparison sort produced, or batches change
//!   membership and every downstream dispatch-count figure moves.
//! * The pretoken walk reuses one span buffer from the session scratch instead
//!   of collecting a fresh `Vec<Span>` per input, and the gapless-tiling
//!   assertion rides the pass that produces the spans instead of walking them
//!   a second time.
//!
//! # Why a reference implementation and not pinned output
//!
//! The old sort is gone from the shipping code, so the identity pin keeps it
//! here: [`reference_batches`] is the pre-change `batches`, comparison sort
//! and greedy grouping verbatim, and every adversarial length distribution is
//! run through both. A pinned expected output would say WHAT changed without
//! saying the change is wrong; an algorithmic reference says both.

#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]

use std::cmp::Reverse;
use std::panic::{AssertUnwindSafe, catch_unwind};

use exatok::device::{
    Batching, MAX_PRETOKEN_TOKENS, MAX_STRIDE_SPREAD, batches_for_lengths, counting_permutation,
    extend_tiling_spans, segments_per_dispatch,
};
use exatok::pretokenize::Span;

/// A deterministic xorshift64* stream.
///
/// The shuffled distributions below must be the same lengths on every run and
/// every machine: a failure has to reproduce, and a count asserted beside them
/// has to describe these lengths and not whichever ones a system RNG dealt.
struct XorShift(u64);

impl XorShift {
    fn next(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        self.0 = x;
        x.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    /// A pretoken length inside the device-bound domain, `1..=255`.
    fn length(&mut self) -> usize {
        (self.next() % 255 + 1) as usize
    }
}

/// The pre-counting-sort `batches`, verbatim.
///
/// This is the algorithm the optimization replaced: a stable comparison sort
/// on `(Reverse(len), index)`, then the greedy stride-aware fill. The fill is
/// unchanged shipping code and is duplicated here only so the WHOLE pipeline
/// is pinned, grouping included; the in-module unit tests in `src/device.rs`
/// guard the fill's own contracts. If the fill ever changes deliberately,
/// this reference changes with it and the pin keeps its meaning.
fn reference_batches(lengths: &[usize], mode: Batching, workgroups: u32) -> Vec<Vec<usize>> {
    let mut order: Vec<usize> = (0..lengths.len()).collect();
    if mode == Batching::ByLength {
        order.sort_by_key(|index| (Reverse(lengths[*index]), *index));
    }

    let mut out: Vec<Vec<usize>> = Vec::new();
    let mut current: Vec<usize> = Vec::new();
    let mut longest = 0_usize;
    let mut shortest = usize::MAX;
    for index in order {
        let len = lengths[index];
        let widened = longest.max(len);
        let narrowed = shortest.min(len);
        let spread_broken = widened + 1 > MAX_STRIDE_SPREAD * (narrowed + 1);
        let count_broken = current.len() + 1 > segments_per_dispatch(widened, workgroups);
        if !current.is_empty() && (spread_broken || count_broken) {
            out.push(std::mem::take(&mut current));
            longest = 0;
            shortest = usize::MAX;
        }
        longest = longest.max(len);
        shortest = shortest.min(len);
        current.push(index);
    }
    if !current.is_empty() {
        out.push(current);
    }
    out
}

/// The length distributions the identity pin walks.
///
/// Each name says which tie or boundary it is aimed at. A distribution that
/// never ties cannot see a stability regression, and one that never reaches
/// the cap cannot see a bucket-boundary regression, so both are here.
fn distributions() -> Vec<(&'static str, Vec<usize>)> {
    let mut rng = XorShift(0x9E37_79B9_7F4A_7C15);
    let mut one_maximum = vec![1_usize; 64];
    one_maximum[31] = MAX_PRETOKEN_TOKENS;
    vec![
        ("empty", vec![]),
        ("one run", vec![7]),
        ("one run at the cap", vec![MAX_PRETOKEN_TOKENS]),
        ("all equal", vec![5; 97]),
        ("all at the cap", vec![MAX_PRETOKEN_TOKENS; 33]),
        ("one maximum among minima", one_maximum),
        ("ascending", (1..=64).collect()),
        ("descending", (1..=64).rev().collect()),
        (
            "cap boundary alternating",
            (0..64).map(|i| MAX_PRETOKEN_TOKENS - (i % 2)).collect(),
        ),
        (
            "heavy ties on three lengths",
            (0..2048).map(|_| (rng.next() % 3 + 1) as usize).collect(),
        ),
        (
            "shuffled across the whole domain",
            (0..4096).map(|_| rng.length()).collect(),
        ),
    ]
}

/// Locks out: any permutation drift between the counting sort and the
/// comparison sort it replaced.
///
/// The counting sort is only a valid optimization if `batches` emits the
/// identical batches, in the identical order, for every input: the greedy fill
/// is order-sensitive, so even a tie broken differently changes batch
/// membership, which changes dispatch counts and padding. If this fails, the
/// two algorithms disagree on some length distribution and the "same
/// permutation" claim behind the swap is false.
#[test]
fn the_counting_sort_matches_the_comparison_sort_on_adversarial_lengths() {
    for (name, lengths) in distributions() {
        for mode in [Batching::InputOrder, Batching::ByLength] {
            for workgroups in [1, 8, 4096] {
                assert_eq!(
                    batches_for_lengths(&lengths, mode, workgroups),
                    reference_batches(&lengths, mode, workgroups),
                    "{name} ({} runs, {mode:?}, {workgroups} workgroups) grouped \
                     differently under the counting sort than under the comparison sort",
                    lengths.len()
                );
            }
        }
    }
}

/// Locks out: a silent return to comparison-based ordering in
/// `counting_permutation`, measured in key extractions rather than time.
///
/// A counting sort over an n-element input with a bounded key domain reads
/// each key a fixed number of times, twice here, once to size the buckets and
/// once to place. A comparison sort must read keys $\Theta(n \log n)$ times:
/// on this toolchain `sort_by_key` extracts the key twice per comparison and
/// measures about $2 n \lceil \log_2 n \rceil$ extractions on shuffled data,
/// so the bound below is $n \lceil \log_2 n \rceil$ with a factor of two of
/// room. The new path's exact figure is the point: $2n$ reads and not one
/// comparator call, which no comparison sort of 4096 elements can imitate
/// since $\log_2(n!)$ alone exceeds $2n$ at this size.
#[test]
fn the_new_order_reads_each_key_twice_where_the_old_sort_read_n_log_n_times() {
    let mut rng = XorShift(0xDEAD_BEEF_1234_5678);
    let lengths: Vec<usize> = (0..4096).map(|_| rng.length()).collect();
    let n = lengths.len();
    let ceil_log2 = (usize::BITS - (n - 1).leading_zeros()) as usize;

    let mut new_reads = 0_usize;
    let new_order = counting_permutation(n, MAX_PRETOKEN_TOKENS + 1, |index| {
        new_reads += 1;
        lengths[index]
    });
    assert_eq!(
        new_reads,
        2 * n,
        "the counting sort must read each key exactly twice, once per pass: a \
         superlinear count means a comparison crept back in"
    );

    let mut old_reads = 0_usize;
    let mut reference: Vec<usize> = (0..n).collect();
    reference.sort_by_key(|index| {
        old_reads += 1;
        (Reverse(lengths[*index]), *index)
    });
    assert!(
        old_reads >= n * ceil_log2,
        "the comparison sort must extract keys at least n*ceil(log2(n)) times \
         ({n}*{ceil_log2}) on shuffled data; it extracted {old_reads}"
    );
    assert_eq!(
        new_order, reference,
        "the counting permutation and the counted comparison sort disagree"
    );
}

/// Locks out: the gapless-tiling assertion going quiet when it was folded into
/// span production.
///
/// The check used to walk the collected spans a second time; it now rides the
/// producing pass, and a fold that dropped the check would pass every encode
/// while silently dropping bytes on a broken splitter. These cases feed
/// [`extend_tiling_spans`] broken streams directly, because no real pattern
/// can provoke the failure: the invariant is `pretokenize`'s own contract, and
/// the negative control has to violate it by hand. Each broken shape must
/// panic, and each well-formed one must append every span.
#[test]
fn the_tiling_check_still_fires_when_the_invariant_is_broken() {
    let gap = [Span { start: 0, end: 2 }, Span { start: 3, end: 5 }];
    let overlap = [Span { start: 0, end: 3 }, Span { start: 2, end: 5 }];
    let short_end = [Span { start: 0, end: 2 }];
    for (name, broken) in [("a gap", &gap[..]), ("an overlap", &overlap[..])] {
        let mut out = Vec::new();
        let payload = catch_unwind(AssertUnwindSafe(|| {
            extend_tiling_spans(5, broken.iter().copied(), &mut out);
        }))
        .expect_err(&format!("{name} must trip the tiling assertion"));
        let message = payload
            .downcast_ref::<String>()
            .map(String::as_str)
            .or_else(|| payload.downcast_ref::<&str>().copied())
            .unwrap_or("");
        assert!(
            message.contains("contiguous and gapless"),
            "{name} panicked with the wrong message: {message}"
        );
    }
    for (name, spans, input_len) in [
        ("a stream ending early", &short_end[..], 5_usize),
        ("no spans over a nonempty input", &[][..], 3),
    ] {
        let mut out = Vec::new();
        catch_unwind(AssertUnwindSafe(|| {
            extend_tiling_spans(input_len, spans.iter().copied(), &mut out);
        }))
        .expect_err(&format!("{name} must trip the tiling assertion"));
    }

    let mut out = Vec::new();
    extend_tiling_spans(5, [Span { start: 0, end: 2 }, Span { start: 2, end: 5 }], &mut out);
    assert_eq!(out, [Span { start: 0, end: 2 }, Span { start: 2, end: 5 }]);
    extend_tiling_spans(0, [], &mut out);
    assert_eq!(out.len(), 2, "an empty input must append nothing");
}

/// Locks out: a pretoken past [`MAX_PRETOKEN_TOKENS`] reaching the counting
/// sort unremarked.
///
/// The sort's bucket domain is the host-routing guarantee: `encode_batch`
/// routes a longer pretoken to the host before `batches` runs, so 255 is the
/// largest length the sort may ever see and 256 is a routing defect. The
/// comparison sort silently ordered such a run; the counting sort refuses it,
/// and that refusal is the pinned behavior. `tests/device_host_routing.rs`
/// proves the guarantee itself; this pins what happens if it is ever broken.
#[test]
fn a_length_past_the_host_routing_guarantee_is_refused() {
    assert_eq!(
        batches_for_lengths(&[MAX_PRETOKEN_TOKENS], Batching::ByLength, 8),
        vec![vec![0]],
        "a lone cap-length run must still batch"
    );
    catch_unwind(|| {
        let _ = batches_for_lengths(&[MAX_PRETOKEN_TOKENS + 1], Batching::ByLength, 8);
    })
    .expect_err("a run past MAX_PRETOKEN_TOKENS must be refused, not mis-ordered");
}

// ---------------------------------------------------------------------------
// Span-buffer reuse
// ---------------------------------------------------------------------------

/// The one concern that needs a session: the span buffer lives in the session
/// scratch, so only a warm `DeviceSession` can prove a second encode allocates
/// no span vector.
///
/// Run on the reference interpreter backend rather than CUDA. Buffer reuse is
/// not a device property: the same `encode_batch_probed` body runs either way
/// (the in-module session tests in `src/device.rs` say exactly this), and the
/// interpreter keeps the allocation counts deterministic, which a contended
/// card and a residency query cannot. The CUDA suites above the line prove
/// the ids; this one counts the host's calls.
mod span_buffer_reuse {
    use std::alloc::{GlobalAlloc, Layout, System};
    use std::cell::Cell;
    use std::sync::LazyLock;

    use exatok::Encoding;
    use exatok::device::{DeviceTokenizer, MAX_PRETOKEN_TOKENS};
    use exatok::vocab::{Vocabulary, artifact_dir};

    // Doc comments sit INSIDE the braces, on the statics: above the macro they
    // attach to the invocation and are discarded, taking the reasoning with
    // them.
    thread_local! {
        /// Allocator calls made by the CALLING THREAD since it last read this.
        ///
        /// Thread-local rather than a process-wide atomic, because the harness
        /// runs tests on parallel threads sharing one global allocator, and a
        /// shared counter would charge this test for another test's
        /// allocations and fail in a full-suite run while passing alone.
        static ALLOCATIONS: Cell<usize> = const { Cell::new(0) };
    }

    /// Add one call to the calling thread's counter, tolerating a dead TLS
    /// slot during thread teardown, where no measurement is live.
    fn record_allocation() {
        let _ = ALLOCATIONS.try_with(|count| count.set(count.get().wrapping_add(1)));
    }

    /// A pass-through allocator that counts allocation calls.
    ///
    /// Calls and not bytes: the defect this pins is one `Vec<Span>` per input
    /// per encode, a few kilobytes that vanish in a byte total and stand out
    /// in a call count.
    struct Counting;

    // SAFETY: every method forwards to `System` unchanged, so the allocator
    // contract is whatever `System` guarantees. The counter is a thread-local
    // increment that allocates nothing and does not participate in the
    // contract.
    unsafe impl GlobalAlloc for Counting {
        unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
            record_allocation();
            // SAFETY: `layout` came from the caller and is forwarded unchanged.
            unsafe { System.alloc(layout) }
        }

        unsafe fn dealloc(&self, pointer: *mut u8, layout: Layout) {
            // SAFETY: both arguments came from the caller and are forwarded
            // unchanged.
            unsafe { System.dealloc(pointer, layout) }
        }

        unsafe fn realloc(&self, pointer: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
            record_allocation();
            // SAFETY: all three arguments came from the caller and are forwarded
            // unchanged.
            unsafe { System.realloc(pointer, layout, new_size) }
        }
    }

    #[global_allocator]
    static ALLOCATOR: Counting = Counting;

    /// Run `body` and report how many allocations the calling thread made.
    fn allocations<T>(body: impl FnOnce() -> T) -> (T, usize) {
        let before = ALLOCATIONS.get();
        let value = body();
        (value, ALLOCATIONS.get() - before)
    }

    /// The real `cl100k_base` vocabulary, loaded once for the binary.
    static CL100K: LazyLock<Vocabulary> = LazyLock::new(|| {
        Vocabulary::load_tiktoken_path(&artifact_dir().join("cl100k_base.tiktoken"))
            .unwrap_or_else(|error| {
                panic!(
                    "Fix: place the real cl100k_base rank file at $EXATOK_VOCAB_DIR \
                     (default ~/.cache/exatok-vocab), got: {error}"
                )
            })
    });

    /// Locks out: a per-input `Vec<Span>` returning to the encode walk.
    ///
    /// The old walk collected `spans(pattern, input)` per input, one fresh
    /// vector per input per encode. The session scratch now holds one span
    /// buffer reused across inputs and encodes, so at a CONSTANT pretoken
    /// count the marginal allocation of one more INPUT must be exactly one:
    /// the per-input output `Vec<TokenId>` that id assembly builds. A revived
    /// span vector adds exactly one more and turns this red.
    ///
    /// The margin is measured between two warm-session batches with the same
    /// number of pretokens and no device work at all: eight one-pretoken
    /// inputs against four two-pretoken inputs, every pretoken over
    /// [`MAX_PRETOKEN_TOKENS`] and therefore host-routed. No dispatch means no
    /// driver in the count, and equal pretoken counts cancel every
    /// per-pretoken cost the host encoder carries, so only per-input costs
    /// survive the subtraction. Pretokenization still runs its full walk for
    /// both batches, span buffer included, which is the code under test.
    #[test]
    fn a_warm_session_allocates_no_span_vector_per_input() {
        let tokenizer = DeviceTokenizer::new(&CL100K, &Encoding::cl100k_base())
            .expect("the real cl100k_base artifact must build a device merge table");
        let backend = vyre_driver_reference::CpuRefBackend;
        let session = tokenizer
            .bind(&backend)
            .expect("session bind must succeed on the interpreter backend");

        // One host-routed pretoken per input: a single letter run past
        // MAX_PRETOKEN_TOKENS. Eight inputs, eight pretokens.
        let one = "a".repeat(MAX_PRETOKEN_TOKENS + 1);
        // Two host-routed pretokens per input: two letter runs past the cap,
        // separated so the pattern splits them. Four inputs, eight pretokens.
        let two = format!("{} {}", "a".repeat(MAX_PRETOKEN_TOKENS + 1), "b".repeat(MAX_PRETOKEN_TOKENS + 1));
        let eight_inputs: Vec<&[u8]> = vec![one.as_bytes(); 8];
        let four_inputs: Vec<&[u8]> = vec![two.as_bytes(); 4];

        // Warm both shapes twice, so the scratch buffers, the span buffer
        // included, hold steady-state capacity before a call is counted.
        for _ in 0..2 {
            let _ = session.encode_batch(&eight_inputs).expect("warmup encode failed");
            let _ = session.encode_batch(&four_inputs).expect("warmup encode failed");
        }
        let (encoded_eight, allocs_eight) =
            allocations(|| session.encode_batch(&eight_inputs).expect("eight-input encode failed"));
        let (encoded_four, allocs_four) =
            allocations(|| session.encode_batch(&four_inputs).expect("four-input encode failed"));

        assert_eq!(
            encoded_eight.routing().on_host(),
            8,
            "the one-pretoken fixture must route all eight pretokens to the host"
        );
        assert_eq!(
            encoded_four.routing().on_host(),
            8,
            "the two-pretoken fixture must route all eight pretokens to the host"
        );
        assert_eq!(encoded_eight.routing().on_device(), 0);
        assert_eq!(encoded_four.routing().on_device(), 0);
        assert_eq!(
            tokenizer.last_dispatch_count(),
            0,
            "an all-host encode must not dispatch, or driver costs enter the margin"
        );

        assert_eq!(
            allocs_eight - allocs_four,
            4,
            "four more inputs at a constant pretoken count must cost exactly \
             ONE allocation each, the output id vector: a second would be a \
             per-input buffer back in the walk ({allocs_four} for four inputs, \
             {allocs_eight} for eight)"
        );
    }
}