An Efficient Algorithm for Streaming BPE Tokenization
summary
Claims a linear-time, low‑memory streaming algorithm for BPE tokenization that reads input in blocks sized by a rule‑set dependent delay and emits safe prefixes. Implements a finite‑state‑transducer approach, computes per‑batch delays to avoid building the full product transducer, and reports for a 200,000‑rule set a delay estimate < 3,000 so memory stays on the order of kilobytes (streaming algorithm uses kilobytes). Benchmarks show the FST tool outperforms Hugging Face and DP and scales with input length.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:42What is tokenization and BPE
- 3:15BPE rule sets
- 4:45Standard BPE procedure
- 6:52Existing BPE algorithms
- 7:59BPE transducers challenges
- 11:15Delay for streaming BPE
- 13:23Computing delay with rule batches
- 14:49Tokenizer comparison
- 16:15Proposed algorithm summary
- 17:40Q&A: Serial composition and priority
- 18:22Q&A: Delay vs token length
- 19:46Q&A: Streaming and parallelization
related talks
33mTrillion-Token Pretraining
30mLarge Scale Private Learning on Data Streams, and the BLTs
25mThe Golden Triangle of Inference Optimization: Balancing Latency, Throughput, and Quality
05mBit-Blasting Probabilistic Programs
18mLearning-Enhanced High-Throughput Pattern Matching Based on Programmable Data Plane
41mInside GPT – The Maths Behind the Magic
14mFlexPipe: Maximizing Training Efficiency for Transformer-based Models with...
01h 14mTutorial: Privacy, Part III