Universal coding of integers (UCI) provides prefix codes for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length under $P$ stays within $K$ times $\max\{1,H(P)\}$. For a given UCI $\mathcal{C}$, the smallest such constant $K$ is called the minimum expansion factor of $\mathcal{C}$, denoted $C_{\mathcal{C}}^{*}$. Let $C^{*}\triangleq \inf \{C_{\mathcal{C}}^{*}\}$ over all UCIs. A UCI attaining $C^{*}$, or a family of UCIs attaining $C^{*}$ in the limit, is called optimal. It is currently known that $2\le C^{*}\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every UCI, a distribution in this family attains the worst-case ratio; thus, the family is least favorable for the UCI problem. We further establish an inequality, called the \emph{UCI inequality}, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B\ge 1$, it decides whether $B$ lies below or above $C^*$. The UCI inequality gives an equivalent definition of $C^*$. By numerical computation, we determine $C^* = 2.00012475703610197861701176297579886254\cdots$, the first $38$ decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.
Ming Chen Zhejiang University, Wenyao Li, Chao Liang Hubei Academy of Aerospace Technology General Design Institute, Shi Gu Zhejiang University, Peng Lin Zhejiang University, De Ma Zhejiang University, Huajin Tang Zhejiang University, Qian Zheng 等 9 位作者
Tokenizers play a critical role in large language model studies. Despite recent advances, existing tokenizers fail to explicitly leverage historical tokenization results when making subsequent token decisions, nor do they selectively utilize such history based on contextual relevance. We propose SPEAK, a tokenizer that integrates spiking neurons to explicitly leverage historical tokenization results. Furthermore, we introduce an entropy-aware reset mechanism that selectively leverages history based on contextual relevance, which is determined by token-level entropy. High-entropy tokens are treated as contextual boundaries, whereas low-entropy tokens between consecutive such boundaries exhibit strong contextual relevance. Accordingly, we induce hard reset at high-entropy tokens to discard irrelevant historical tokenization results, and soft reset at low-entropy tokens to preserve and leverage relevant history. Experiments on 2 language models and 5 datasets spanning 16 languages demonstrate superior cross-lingual adaptability, with competitive performance and efficiency. Our code is publicly available at https://github.com/zju-bmi-lab/SPEAK.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表