exatok 0.1.1

Exact GPU-resident BPE tokenizer whose token ids match tiktoken byte for byte
Documentation
//! Incremental merge with maintained pair ranks. OWNER: IncrementalMerge.
//!
//! Rescanning every adjacent pair each pass costs about 3.02 random
//! pair-table lookups per input byte, measured on real corpora, and that is
//! the dominant cost of the whole tokenizer. Recomputing only the two pairs
//! adjacent to the merge site cuts it to about 1.53 per byte with no change
//! to which merge is selected, so unlike single-rank multi-merge this is
//! exact without any reachability assumption.
//!
//! Acceptance: byte-exact agreement with [`crate::reference::encode_pretoken`]
//! on boundary, randomized, and real-vocabulary inputs, plus a pinned lookup
//! count proving the reduction is real rather than assumed.
//!
//! # Why this is exact
//!
//! [`crate::reference::encode_pretoken`] recomputes the rank of every adjacent
//! pair on every pass, then takes the leftmost minimum. A merge at index `i`
//! changes the token sequence in exactly one place: `seq[i]` becomes the merged
//! id and `seq[i + 1]` is removed. Every pair strictly left of `i - 1` and
//! strictly right of `i` therefore keeps both of its elements and keeps its
//! rank. Only two pairs can differ, so recomputing those two reproduces the
//! full rescan's rank array exactly. This optimization removes redundant
//! lookups; it never changes which merge is selected.
//!
//! The one precondition is the crate-wide sentinel contract: no real rank
//! equals [`Rank::ABSENT`], which [`crate::reference::HostMergeTable::insert`]
//! rejects at load time. Selection here is a plain unsigned minimum with no
//! presence mask, exactly as the device reduction is, so a table that reported
//! a mergeable pair at rank `u32::MAX` would be invisible to it while
//! [`crate::reference::encode_pretoken`] still merged it.
//!
//! # State layout
//!
//! Three parallel arrays, deliberately structure-of-arrays so a device port
//! min-reduces one contiguous `u32` column and reads the merged id only at the
//! winning index:
//!
//! ```text
//! seq         [ t0   t1   t2   t3 ]      len n
//! pair_rank   [ r01  r12  r23 ]          len n - 1
//! pair_merged [ m01  m12  m23 ]          len n - 1
//! ```
//!
//! The invariant is `pair_rank.len() == pair_merged.len() == n - 1` for
//! `n >= 1` and `0` for `n == 0`, with slot `k` describing the pair
//! `(seq[k], seq[k + 1])`. [`MergeState::pair_ranks`] and
//! [`MergeState::pair_merges`] expose both columns so a GPU differential can
//! diff device buffers against host state slot by slot rather than only
//! comparing final ids.
//!
//! # The off-by-one
//!
//! After the merge at `i` is applied and slot `i` is deleted, `seq[i]` holds
//! the NEWLY merged token. The two slots to refresh are:
//!
//! - `i - 1`, which covers `(seq[i - 1], seq[i])`, absent when `i == 0`.
//! - `i`, which covers `(seq[i], seq[i + 1])`, absent when the merge consumed
//!   the final pair, because slot `i` no longer exists after the deletion.
//!
//! Refreshing `i + 1` instead of `i`, or refreshing before the deletion,
//! leaves a stale rank in the array that the minimum reduction then trusts.

use std::cell::Cell;

use crate::reference::{MergeEntry, MergeTable};
use crate::{PairKey, Rank, TokenId};

/// Filler stored in `pair_merged` for an unmergeable slot.
///
/// Never read: selection requires [`Rank::is_present`], and the only rank a
/// miss can carry is [`Rank::ABSENT`]. It exists so the two columns stay the
/// same length without an out-of-band presence mask, exactly as the device
/// rank table does.
const ABSENT_MERGED_ID: TokenId = TokenId(0);

/// Merge state for one pretoken: the token sequence plus its maintained ranks.
///
/// Reusable across pretokens via [`MergeState::load`], which keeps the
/// allocation and keeps the lookup counters accumulating.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct MergeState {
    seq: Vec<TokenId>,
    pair_rank: Vec<Rank>,
    pair_merged: Vec<TokenId>,
    lookups: u64,
    merges: u64,
}

impl MergeState {
    /// Empty state with no counted lookups.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            seq: Vec::new(),
            pair_rank: Vec::new(),
            pair_merged: Vec::new(),
            lookups: 0,
            merges: 0,
        }
    }

    /// Replace the sequence with `tokens` and build every pair rank.
    ///
    /// Costs exactly `tokens.len().saturating_sub(1)` lookups, the one full
    /// scan the incremental path still pays. Counters are NOT reset, so
    /// encoding a whole corpus accumulates a single total; use
    /// [`MergeState::clear_counters`] to start a fresh measurement.
    pub fn load(&mut self, tokens: &[TokenId], table: &impl MergeTable) {
        self.seq.clear();
        self.seq.extend_from_slice(tokens);
        let slots = self.seq.len().saturating_sub(1);
        self.pair_rank.clear();
        self.pair_rank.resize(slots, Rank::ABSENT);
        self.pair_merged.clear();
        self.pair_merged.resize(slots, ABSENT_MERGED_ID);
        for slot in 0..slots {
            self.refresh(slot, table);
        }
    }

    /// Leftmost slot holding the minimum present rank, or `None` when no pair
    /// is mergeable.
    ///
    /// The comparison is strict `<`, so an equal rank further right never
    /// displaces the leftmost occurrence. [`Rank::ABSENT`] is `u32::MAX` and
    /// the running best starts there, which is why a miss can never win and no
    /// separate presence mask is needed.
    #[must_use]
    pub fn select(&self) -> Option<usize> {
        let mut best_slot = 0usize;
        let mut best_rank = Rank::ABSENT;
        for slot in 0..self.pair_rank.len() {
            let rank = self.pair_rank[slot];
            if rank < best_rank {
                best_rank = rank;
                best_slot = slot;
            }
        }
        if best_rank.is_present() {
            Some(best_slot)
        } else {
            None
        }
    }

    /// Apply the merge recorded at `slot`, then refresh only its two
    /// neighbours.
    ///
    /// The guards keep this total rather than trusting the caller: every slot
    /// [`MergeState::select`] reports is in range, has a right neighbour, and
    /// carries a present rank. Refusing an absent slot is what makes
    /// [`ABSENT_MERGED_ID`] genuinely unreadable: without it a caller driving
    /// slots directly, as a device differential does, would splice
    /// `TokenId(0)` into the sequence and get a plausible-looking wrong answer
    /// instead of a no-op.
    pub fn apply(&mut self, slot: usize, table: &impl MergeTable) {
        if slot >= self.pair_rank.len() || slot + 1 >= self.seq.len() {
            return;
        }
        if !self.pair_rank[slot].is_present() {
            return;
        }
        let merged = self.pair_merged[slot];
        self.seq[slot] = merged;
        self.seq.remove(slot + 1);
        // The merged pair's own slot does not get recomputed, it disappears:
        // its right element is gone and the arrays must shrink with `seq`.
        self.pair_rank.remove(slot);
        self.pair_merged.remove(slot);
        self.merges += 1;
        // `seq[slot]` is now the merged token. Slot `slot - 1` covers
        // `(seq[slot - 1], seq[slot])`.
        if slot > 0 {
            self.refresh(slot - 1, table);
        }
        // Slot `slot` covers `(seq[slot], seq[slot + 1])`. It is gone when the
        // merge consumed the final pair.
        if slot < self.pair_rank.len() {
            self.refresh(slot, table);
        }
    }

    /// Merge until no pair is mergeable.
    ///
    /// Termination is structural: [`MergeState::apply`] removes exactly one
    /// element per call, so at most `len - 1` merges run.
    pub fn run(&mut self, table: &impl MergeTable) {
        while let Some(slot) = self.select() {
            self.apply(slot, table);
        }
    }

    /// One pair-table lookup for `slot`, writing both columns.
    ///
    /// This is the only place either column is written after [`MergeState::load`],
    /// and the only place `lookups` advances, so the counter cannot drift from
    /// the real probe count.
    fn refresh(&mut self, slot: usize, table: &impl MergeTable) {
        let (Some(&left), Some(&right)) = (self.seq.get(slot), self.seq.get(slot + 1)) else {
            return;
        };
        self.lookups += 1;
        match table.lookup(PairKey::new(left, right)) {
            Some(entry) => {
                self.pair_rank[slot] = entry.rank;
                self.pair_merged[slot] = entry.id;
            }
            None => {
                self.pair_rank[slot] = Rank::ABSENT;
                self.pair_merged[slot] = ABSENT_MERGED_ID;
            }
        }
    }

    /// Current token sequence.
    #[must_use]
    pub fn tokens(&self) -> &[TokenId] {
        &self.seq
    }

    /// Maintained rank column, slot `k` covering `(seq[k], seq[k + 1])`.
    #[must_use]
    pub fn pair_ranks(&self) -> &[Rank] {
        &self.pair_rank
    }

    /// Maintained merged-id column, parallel to [`MergeState::pair_ranks`].
    #[must_use]
    pub fn pair_merges(&self) -> &[TokenId] {
        &self.pair_merged
    }

    /// Pair-table lookups issued since the last [`MergeState::clear_counters`].
    #[must_use]
    pub const fn lookups(&self) -> u64 {
        self.lookups
    }

    /// Merges applied since the last [`MergeState::clear_counters`].
    #[must_use]
    pub const fn merges(&self) -> u64 {
        self.merges
    }

    /// Zero both counters, leaving the sequence untouched.
    pub const fn clear_counters(&mut self) {
        self.lookups = 0;
        self.merges = 0;
    }
}

/// Encode one pretoken with the incremental path.
///
/// Byte-identical to [`crate::reference::encode_pretoken`] on every input.
#[must_use]
pub fn encode_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> Vec<TokenId> {
    let mut state = MergeState::new();
    state.load(tokens, table);
    state.run(table);
    state.seq
}

/// Encode a pretoken sequence into one flat id stream.
///
/// Reuses one [`MergeState`] across pretokens: merges never cross a pretoken
/// boundary, so the state is fully replaced per pretoken and nothing carries
/// over except the buffers.
#[must_use]
pub fn encode<S: AsRef<[TokenId]>>(pretokens: &[S], table: &impl MergeTable) -> Vec<TokenId> {
    let mut ids = Vec::new();
    let mut state = MergeState::new();
    for pretoken in pretokens {
        state.load(pretoken.as_ref(), table);
        state.run(table);
        ids.extend_from_slice(&state.seq);
    }
    ids
}

/// Result of an instrumented encode.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Measurement {
    /// Final token ids.
    pub ids: Vec<TokenId>,
    /// Pair-table lookups issued.
    pub lookups: u64,
    /// Merges applied.
    pub merges: u64,
}

/// Encode one pretoken and report the lookups it cost.
///
/// The counter is the point: the claimed reduction has to be measured on the
/// same input as the path it is compared against, not inferred from the
/// algorithm's shape.
#[must_use]
pub fn measure_pretoken(tokens: &[TokenId], table: &impl MergeTable) -> Measurement {
    let mut state = MergeState::new();
    state.load(tokens, table);
    state.run(table);
    Measurement {
        lookups: state.lookups,
        merges: state.merges,
        ids: state.seq,
    }
}

/// Encode a pretoken sequence and report the total lookups.
#[must_use]
pub fn measure<S: AsRef<[TokenId]>>(pretokens: &[S], table: &impl MergeTable) -> Measurement {
    let mut ids = Vec::new();
    let mut state = MergeState::new();
    for pretoken in pretokens {
        state.load(pretoken.as_ref(), table);
        state.run(table);
        ids.extend_from_slice(&state.seq);
    }
    Measurement {
        ids,
        lookups: state.lookups,
        merges: state.merges,
    }
}

/// Merge table that counts the lookups passed through it.
///
/// Wrapping the table rather than instrumenting each encoder is what makes the
/// comparison honest: the naive path in [`crate::reference`] and the
/// incremental path here are measured by the identical mechanism, so a
/// difference in counts cannot be an artifact of two counting conventions.
#[derive(Debug, Default)]
pub struct CountingTable<T> {
    inner: T,
    lookups: Cell<u64>,
}

impl<T: MergeTable> CountingTable<T> {
    /// Wrap `inner` with a zeroed counter.
    #[must_use]
    pub const fn new(inner: T) -> Self {
        Self {
            inner,
            lookups: Cell::new(0),
        }
    }

    /// Lookups seen so far.
    #[must_use]
    pub fn lookups(&self) -> u64 {
        self.lookups.get()
    }

    /// Zero the counter.
    pub fn clear(&self) {
        self.lookups.set(0);
    }
}

impl<T: MergeTable> MergeTable for CountingTable<T> {
    fn lookup(&self, pair: PairKey) -> Option<MergeEntry> {
        self.lookups.set(self.lookups.get().saturating_add(1));
        self.inner.lookup(pair)
    }
}

/// Lookups the full-rescan reference path issues on `tokens`.
///
/// Drives the real [`crate::reference::encode_pretoken`] rather than a local
/// re-implementation, so the baseline cannot drift from the shipping oracle.
#[must_use]
pub fn naive_lookups(tokens: &[TokenId], table: &impl MergeTable) -> u64 {
    let counting = CountingTable::new(table);
    let _ = crate::reference::encode_pretoken(tokens, &counting);
    counting.lookups()
}

/// Lookups the incremental path issues on `tokens`, measured through
/// [`CountingTable`] for a like-for-like comparison with [`naive_lookups`].
#[must_use]
pub fn incremental_lookups(tokens: &[TokenId], table: &impl MergeTable) -> u64 {
    let counting = CountingTable::new(table);
    let _ = encode_pretoken(tokens, &counting);
    counting.lookups()
}