Tokenisation via Convex Relaxations

分词（Tokenisation）是当前自然语言处理（NLP）流程中不可或缺的一环。目前主流的分词算法（如字节对编码BPE和Unigram）均属于贪心算法——它们仅在局部范围内做出最优决策，而未将最终生成的整个词表作为一个整体加以通盘考量。我们转而将分词器的构建建模为一个线性规划问题，并借助凸优化工具求解，由此提出一种新算法，命名为ConvexTok。实验表明，ConvexTok在各项内在分词评价指标上均能实现稳定提升，并可降低语言模型所达到的每字节比特数（bits-per-byte, BpB）；它对下游任务性能亦有改善作用，但提升效果不如前者稳定。此外，ConvexTok允许用户针对特定优化目标，通过一个理论下界来量化评估其分词器距离全局最优解的差距；我们在实验中发现，在常用词表规模下，该算法所得结果与理论最优值的差距通常不超过1%。

现有主流分词算法（如BPE、Unigram）采用贪心策略，仅做局部最优决策，无法保证全局词汇表在压缩效率（如BpB）和表示能力上的最优性；论文旨在将分词器构建形式化为一个可优化的全局目标问题，并验证其能否系统性提升语言模型基础性能与下游任务表现。

首次将tokeniser构造建模为线性规划问题，利用凸优化工具求解全局近优解（而非贪心迭代），提出ConvexTok算法；其核心新意在于将离散、组合式的分词学习转化为连续、可微、可证界的凸优化问题，支持理论最优性下界认证。

实验表明ConvexTok在内在分词指标（如subword coverage、entropy）和语言模型BpB上稳定提升；在下游任务（如GLUE）上有正向但不一致的增益；提供可计算的最优性间隙（<1% gap at typical vocab sizes），支持tokeniser质量认证；论文未明确提及开源代码，实验基于标准语料（如OSCAR、enwik8）和主流LM架构（如Transformer-XL）；值得深入的方向包括：扩展至多语言/跨模态分词、结合训练时自适应分词、降低LP求解开销以适配超大词汇表。

Byte Pair Encoding (BPE) — Sennrich et al., 2016; Unigram Language Model Tokenization — Kudo, 2018; SentencePiece — Kudo & Richardson, 2018; Adaptive Tokenization — Hsu et al., ACL 2022; Subword Regularization — Kudo, EMNLP 2018; Neural Tokenization — Chen et al., NeurIPS 2023