The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary
cs.FL, cs.CL, cs.DS, cs.PL
Submitted: 2026-11-09
Updated: 2026-11-09
Code: https://github.com/google/sentencepiece
Terminology
Sources
- Unambiguously coded shifts
- Constructing a BPE Tokenization DFA
- Online Tokenization with Optimal Delay in Linear Time
- Sampling from Your Language Model One Byte at a Time
- Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier
- Certified Panic Mode: Repair-Invariant Error Recovery for Maximal-Munch Lexing
- Certified Split Points for Parallel Lexing: Exact and Modulo Discarded Tokens
- Certified Splitting: Decidability and Anchor Supply for Maximal-Munch Tokenization
- Certified Split Windows for Parallel Lexing: Recovering Boundaries Where No Byte Certifies
- Language Models over Canonical Byte-Pair Encodings
Related papers
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- On Word Representations and Embeddings in Complex Matrices