增量 BPE 词元切分

我们提出了一种用于增量字节对编码（BPE）标记化的新颖算法。该算法在最坏情况的 $\mathcal{O}(\log^2 t)$ 时间内处理每个输入字节，导致总体复杂度为 $\mathcal{O}(n \log^2 t)$，其中 $n$ 是输入长度，$t$ 是最大标记长度。该算法增量地维护输入文本的每个前缀的 BPE 标记化结果，实现由一组固定合并规则定义的标准 BPE 合并过程。这可以在流设置中实现高效的部分标记化。作为标准 BPE 的直接替代品，我们的方法比 Hugging Face 的 tokenizer 实现了高达 ${\sim}3\times$ 的加速，并且在病理输入上比 OpenAI 的 tiktoken 显着减少了延迟。我们进一步引入了一种急切的输出算法，该算法支持流式输出，在增量标记化过程中一旦确定了标记边界就发出标记。总的来说，我们的结果表明，BPE 标记化可以在最坏情况下以强有力的保证逐步执行，同时在现代 大语言模型 管道中提供实际的延迟优势。代码：https://github.com/ModelTC/mtc-inc-bpe