每日论文：语言生成的密度度量

论文: Density Measures for Language Generation

作者: Jon Kleinberg, Fan Wei (Cornell University)

发表日期: 2025年4月19日

问题背景

大型语言模型在生成内容的广度（多样性）与有效性（幻觉低）之间的权衡难以量化。曾有人提出了提出了一种理论层的任务构想，语言极限生成来尝试提出一个高层次的解决方案现有方法（如Kleinberg-Mullainathan的KM算法）虽能实现极限生成，但导致生成内容局限于狭窄子集，缺乏多样性。这类似于LLMs的"模式崩塌"问题（生成单一内容）。本文提出一种密度度量，量化生成内容的广度，并设计新算法优化广度与有效性的权衡。

提出方法：密度度量与优化算法

密度度量

定义：给定目标语言 $K$ 和算法输出集合 $O$，假设 $K$ 的字符串按序排列为 ${ \ell_1, \ell_2, \ldots }$，密度度量如下：
- 上密度：$$\mu_{\text{up}}(O, K) = \limsup_{N \to \infty} \frac{|O \cap \{\ell_1, \ldots, \ell_N\}|}{N}$$
- 下密度：$$\mu_{\text{low}}(O, K) = \liminf_{N \to \infty} \frac{|O \cap \{\ell_1, \ldots, \ell_N\}|}{N}$$
- 密度表示 $O$ 在 $K$ 中的占比，高密度意味着生成内容覆盖 $K$ 的大部分，体现高广度。
意义：下密度是更严格的指标，确保最差情况下仍有一定广度。目标是设计算法使 $\mu_{\text{low}}(O, K) \geq c > 0$（如 $c = 1/8$）。

理论框架

KM模型：基于对抗性游戏：
- 对手从候选语言集合 $\mathcal{X} = {L_1, L_2, \ldots}$ 中选择未知目标语言 $K$，逐一枚举 $K$ 的字符串 $S_t = {w_1, \ldots, w_t}$。
- 算法观察 $S_t$，生成新字符串 $o_t \in K - S_t$，目标是极限生成（存在 $t^$，使 $t > t^$ 时 $o_t \in K$）。
KM算法局限：通过维护嵌套语言链 $L_{c_1} \supseteq L_{c_2} \supseteq \cdots \subseteq K$，KM算法实现极限生成，但输出集合 $O$ 的密度可能为0，生成内容单一。

新算法

核心思想：通过以下机制改进KM算法，确保输出集合 $O$ 的下密度至少为 $1/8$，兼顾有效性和广度：
- 动态调整：根据 $S_t$，灵活选择语言 $L_{c_t}$，不固定缩小路径。
- 回退机制：当 $L_{c_t}$ 太小（剩余字符串少），回退到更大的语言 $L_j \supseteq L_{c_t}$，增加多样性。
- 令牌系统：为每个语言分配令牌 $\text{tokens}(L_i)$，控制生成数量；回退时给大语言更多令牌，鼓励多生成。
- 树结构（动态森林）：节点为语言，边为包含关系；算法在树上导航，选择或回退。
实现：
- 动态森林：在时间步 $t$，构建森林 $\mathcal{D}_t$，节点为包含 $S_t$ 的语言，边为 $L_i \subseteq L_j$。随 $S_t$ 更新森林，删除不一致节点。
- 选择策略：选 $L_{c_t}$ 满足 $S_t \subseteq L_{c_t}$，优先大语言（多令牌），生成 $o_t \in L_{c_t} - S_t$。
- 回退触发：若 $|L_{c_t} - S_t|$ 小于阈值，跳到父节点 $L_j$，分配 $\text{tokens}(L_j) \gets \text{tokens}(L_j) + k$。
- 令牌充电：小语言节省令牌，积累到大语言，确保回退时输出足够多。

关键问题与结果

问题 (*)：是否存在算法 $\mathcal{A}$，对任意实例，实现极限生成且 $\mu_{\text{low}}(O, K) \geq c > 0$？
- 回答：提出算法保证 $\mu_{\text{low}}(O, K) \geq 1/8$，证明零密度非必然。
问题 ()：极限生成算法是否总在某些实例中产生零密度输出**？
- 回答：新算法打破零密度假设，部分实例可保持正密度。
问题 ()：索引生成（输出语言索引 $i_t$，使 $L_{i_t} \subseteq K$）是否能避免密度趋零*？
- 回答：存在实例使上密度趋零，但可设计算法使 $L_{i_t} = K$ 无限次（下密度为1）。

实验结果（理论）

有效性：新算法在元素生成中实现 $\mu_{\text{low}}(O, K) \geq 1/8$，显著优于KM算法的零密度。
索引生成：密度可能振荡（高低交替），但可避免持续趋零，引入"无限完美塔"表征低密度实例。

总结

本文通过密度度量和优化算法，解决了极限语言生成中广度与有效性的权衡问题。新算法通过动态调整、回退机制、令牌系统和树结构，确保输出下密度至少 $1/8$，为LLM的模式崩塌和多样性优化提供了理论指导和实用启发。