跳转至

A note on the impossibility of conditional PAC-efficient reasoning in large language models

讲者: Hao Zeng
会场: Advances in Machine Learning for Large Language Models and Matrix Methods
报告题目: PAC-Efficient Reasoning for Large Language Models: Marginal Guarantees, Conditional Extensions, and Anytime Validity
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

本文所涉子方向是 LLM 部署中的效率-性能权衡，具体聚焦于 路由（routing） 策略：在推理时动态选择使用一个昂贵但准确的“专家”模型（如带长链式推理的模型）或一个廉价但可能较差的“快速”模型（如直接回答的模型）。核心统计问题是：能否在 分布自由（distribution-free） 设定下，对路由决策导致的性能损失提供 有限样本保证，同时实现有意义的计算节省。该方向当前处于 从工程实践向统计理论化过渡 的阶段：已有大量工程方法（模型路由、推测解码、自适应推理），但统计保证（尤其是条件性保证）的理论基础尚不完整。

发展脉络（history）

  1. 奠基工作：LLM 推理效率的工程挑战

  2. Kwon et al. (2023)（PagedAttention）指出 LLM 部署中 KV 缓存内存管理是瓶颈，提出类虚拟内存的注意力算法，将吞吐量提升 2–4×。该工作奠定了“计算成本高”这一问题的工程认知，但未涉及统计保证。

  3. 主要进展：多种效率提升策略涌现

  4. Leviathan et al. (2023)（推测解码）提出用轻量模型并行生成候选 token，再由大模型验证，实现 2–3× 加速且输出分布不变。这是“无损失加速”的代表，但要求近似模型质量足够好，且不提供性能损失的统计控制。
  5. Ong et al. (2025)（RouteLLM）和 Dekoninck et al. (2025)（路由与级联统一框架）分别提出基于偏好数据训练的路由器或理论最优的级联策略。前者强调成本-性能权衡的优化，后者证明了路由和级联策略的最优性条件。这些工作将路由问题形式化为决策问题，但均未给出有限样本下的性能损失保证。

  6. Snell et al. (2024) 研究测试时计算缩放，发现对某些提示，增加推理计算比扩大模型参数更有效。这为“何时使用专家模型”提供了经验依据，但同样缺乏统计保证。

  7. 当前 frontier：PAC 推理框架的提出

  8. Zeng et al. (2025)（PAC reasoning）首次将 Probably Approximately Correct (PAC) 保证引入 LLM 路由：构造一个复合模型，通过校准数据集选择阈值，使得 边际风险（期望性能损失）以高概率被控制在用户指定容忍度内。该工作提供了分布自由的有限样本保证，但仅控制 边际（平均）风险。

  9. 本文的位置

  10. 本文是 Zeng et al. (2025) 的直接后续，追问：能否将边际保证升级为 条件保证（对每个输入点分别控制风险）？答案是否定的——条件 PAC 效率必然导致平凡解（几乎总是使用专家模型）。这借鉴了分布自由预测推断中条件覆盖不可能性的经典结果（Barber et al., 2021），并将其移植到 PAC 推理框架。

子线索聚类

  • 线索 A：LLM 推理效率的工程方法（Kwon et al., 2023; Leviathan et al., 2023; Ong et al., 2025; Dekoninck et al., 2025; Snell et al., 2024）
    关注如何通过系统设计、模型选择或推理策略降低计算成本，通常缺乏统计保证或仅提供经验验证。

  • 线索 B：分布自由预测推断与风险控制（Vovk, 2012; Lei & Wasserman, 2014; Lei et al., 2018; Barber et al., 2021; Angelopoulos et al., 2025a,b; Gibbs et al., 2025）
    关注在无分布假设下构造预测集或控制风险，核心结果包括边际覆盖的可行性、条件覆盖的不可能性、以及风险控制的扩展。本文直接借用该线索的技术（有限样本不可区分性构造）和结论（条件保证的不可能性）。

  • 线索 C：PAC 推理框架（Zeng et al., 2025）
    将 PAC 学习思想应用于路由问题，提供边际性能损失保证。本文是该线索的延伸，证明条件版本的不可行性。

这个方向在追问的核心问题

  1. 边际 vs. 条件保证：能否在分布自由设定下，对每个输入点提供性能损失的概率控制？
  2. 非平凡路由的存在性：是否存在一个路由器，既能以高概率控制性能损失，又能以显著概率使用快速模型（即实现计算节省）？
  3. 分布假设下的可能性：如果对输入分布或损失函数施加额外假设（如光滑性、低噪声、离散输入空间），条件保证是否可能？
  4. 与 conformal prediction 的统一：PAC 推理中的风险控制与 conformal risk control 之间是否存在更深的联系？能否将后者的条件保证结果（如 Gibbs et al., 2023 的有限群组条件覆盖）移植过来？

⚠️ 作者的 framing（必须明确标注为作者说法）

  • 作者把缺口 frame 成：“The original PAC reasoning provides marginal guarantees… A natural extension is whether we can achieve a stronger, conditional guarantee.”（第 1 页）——即本文是边际到条件的“自然”延伸，而证明其不可能性则构成一个“fundamental impossibility result”。
  • 被淡化或回避的竞争路线：作者在引言中列举了模型路由、推测解码、自适应推理等工程方法，但未讨论这些方法在 实际中是否真的需要条件保证。例如，推测解码保证输出分布不变（即零性能损失），但要求近似模型质量足够高；而 PAC 推理允许有界损失但控制概率。作者未比较这两种范式在实践中的适用场景。
  • 什么明显该被引 / 该存在、却没出现在 intro 里：
  • 关于“条件风险控制”的类似不可能性：Angelopoulos et al. (2025b) 的 conformal risk control 是否已有条件版本的不可能性？作者引用了该文，但未明确说明其与本文结果的关系。
  • 更早的“条件覆盖不可能性”在非预测推断场景的应用：例如，在假设检验中条件错误控制的不可能性（如 Berger 1985 的“条件频率学派”争论）。这些可能为本文提供更广的上下文，但未被引用。
  • 离散输入空间下的可能性：Barber et al. (2021) 指出，当输入空间为有限集时，条件覆盖是可能的（通过在每个点上分别校准）。本文假设非原子空间，但未讨论离散情况，而离散情况在 LLM 路由中可能相关（如提示类别有限）。这可能是作者有意回避的“明显缺口”。

张力

未见明显对立引用。所有被引工作基本一致地认为：边际保证可行，条件保证在分布自由设定下不可能（Barber et al., 2021; Angelopoulos et al., 2025b; Gibbs et al., 2025）。本文只是将该结论从预测覆盖迁移到风险控制。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • 符号
  • \( \mathcal{X} \)：输入空间（如自然语言提示的集合）。
  • \( \mathcal{Y} \)：输出空间（如回答的集合）。
  • \( P \)：\( \mathcal{X} \times \mathcal{Y} \) 上的联合分布，未知。
  • \( P_{\mathcal{X}} \)：\( \mathcal{X} \) 上的边际分布。
  • \( f: \mathcal{X} \to \mathcal{Y} \)：专家模型（昂贵，如带链式推理的 LLM）。
  • \( \tilde{f}: \mathcal{X} \to \mathcal{Y} \)：快速模型（廉价，如直接回答的 LLM）。
  • \( g: \mathcal{X} \to \{0,1\} \)：路由函数，\( g(x)=1 \) 表示使用专家，\( g(x)=0 \) 表示使用快速模型。
  • \( \hat{f}(x) = \begin{cases} f(x) & \text{if } g(x)=1 \\ \tilde{f}(x) & \text{if } g(x)=0 \end{cases} \)：复合模型。
  • \( \ell: \mathcal{Y} \times \mathcal{Y} \to [0,\infty) \)：损失函数，如 0-1 损失 \( \ell(\tilde{y}, y) = \mathbf{1}\{\tilde{y} \neq y\} \)。
  • \( R(\hat{f}; x) = \mathbf{1}\{g(x)=0\} \cdot \ell(\tilde{f}(x), f(x)) \)：在输入 \( x \) 处的点风险（仅当使用快速模型且出错时非零）。
  • \( \epsilon > 0 \)：用户容忍的性能损失阈值。
  • \( \alpha \in (0,1) \)：允许的失败概率。
  • \( D_{\text{cal}} = \{(x_i, y_i)\}_{i=1}^n \sim P^n \)：校准数据集，其中 \( y_i = f(x_i) \)（专家输出）。

  • \( n \)：校准样本量。

  • 模型
    数据生成机制：\( (X,Y) \sim P \)，其中 \( Y = f(X) \) 是专家模型的输出（视为“真实”或“目标”输出）。快速模型 \( \tilde{f} \) 是固定的已知函数。路由函数 \( g \) 基于校准数据 \( D_{\text{cal}} \) 构造（可能依赖于一个得分函数 \( s(x) \) 和阈值 \( \tau \)）。复合模型 \( \hat{f} \) 的风险由损失函数 \( \ell \) 度量。

  • 可观测数据

  • 可观测：校准集 \( D_{\text{cal}} \) 中的 \( (x_i, y_i) \)，其中 \( y_i = f(x_i) \) 是专家输出（假设可计算或已标注）。
  • 不可观测：真实分布 \( P \)；对于新输入 \( x \)，我们不知道专家输出 \( f(x) \) 与快速输出 \( \tilde{f}(x) \) 是否匹配（除非实际运行专家模型，但成本高）。
  • 关键区分：条件 PAC 效率要求对 每个 \( x \) 控制风险，但校准集只提供有限样本，且 \( x \) 的分布未知。这导致不可能性。

第二步：最小内核

考虑最简特例：
- 输入空间 \( \mathcal{X} = [0,1] \)（连续区间，非原子）。
- 损失为 0-1 损失：\( \ell(\tilde{y}, y) = \mathbf{1}\{\tilde{y} \neq y\} \)。
- 快速模型在某个正测度集上总是出错：存在区间 \( E \subset [0,1] \) 长度 \( >0 \)，使得对所有 \( x \in E \)，\( \tilde{f}(x) \neq f(x) \)。
- 路由函数 \( g(x) \) 基于校准数据 \( D_{\text{cal}} \) 构造，但可以是任意算法（不限于阈值法）。
- 条件 PAC 效率要求：对 \( P_{\mathcal{X}} \)-几乎每个 \( x \in [0,1] \)，

\[P_{D_{\text{cal}} \sim P^n}\big( R(\hat{f}; x) > \epsilon \big) \leq \alpha.\]

由于 0-1 损失下 \( R(\hat{f}; x) > \epsilon \) 等价于 \( g(x)=0 \) 且 \( \tilde{f}(x) \neq f(x) \)，而在 \( E \) 上 \( \tilde{f}(x) \neq f(x) \) 恒成立，因此条件 PAC 效率在 \( E \) 上退化为：
\[P_{D_{\text{cal}} \sim P^n}(g(x)=0) \leq \alpha, \quad \forall x \in E \text{ (a.e.)}.\]

核心思路：如果存在一个正测度集 \( E \) 使得 \( P(g(x)=0) > \alpha \)，那么可以构造一个与 \( P \) 在 \( n \) 个样本上几乎不可区分的分布 \( P' \)，使得在 \( x^* \in E \) 处快速模型总是出错。由于条件 PAC 效率必须对 \( P' \) 也成立，推出 \( P'(g(x^*)=0) \leq \alpha \)，再通过总变差距离控制得到 \( P(g(x^*)=0) \leq \alpha \)，矛盾。因此，任何满足条件 PAC 效率的算法必须满足 \( P(g(x)=0) \leq \alpha \) 对几乎所有 \( x \) 成立——即几乎总是使用专家模型，无效率提升。

这个最小内核揭示了论文的数学本质：条件保证要求对每个 \( x \) 独立控制风险，但校准集是有限的，且 \( x \) 的分布未知。通过局部修改分布（仅在一个小邻域内改变条件分布），可以“欺骗”算法：算法无法区分 \( P \) 和 \( P' \)，因此必须对两者都满足条件保证，从而迫使算法在几乎所有 \( x \) 上几乎总是使用专家模型。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在分布自由设定下，LLM 路由算法能否实现 条件 PAC 效率（即对每个输入点 \( x \)，性能损失超过 \( \epsilon \) 的概率不超过 \( \alpha \)）？
  2. 核心工具/方法：有限样本不可区分性引理（Lemma 5），通过局部修改分布构造一个与原始分布在 \( n \) 个样本上总变差距离任意小的敌对分布。
  3. 主要结论：条件 PAC 效率等价于平凡性——对几乎所有输入 \( x \)，算法使用快速模型的概率不超过 \( \alpha \)。这意味着任何非平凡的路由（以大于 \( \alpha \) 的概率使用快速模型）都不可能满足条件 PAC 效率。

关键设定与假设

  • 输入空间 \( \mathcal{X} \)：非原子完备可分度量空间（如 \( \mathbb{R}^d \) 或连续函数空间）。该假设保证可以找到任意小的正测度球，用于局部修改分布。
  • 快速模型的非平凡损失：存在正测度集 \( E \subset \mathcal{X} \) 使得对所有 \( x \in E \)，\( \ell(\tilde{f}(x), f(x)) > \epsilon \)。即快速模型在某些输入上必然导致不可接受的性能损失。这是不可能性结果的必要条件——如果快速模型在所有输入上损失都 \( \leq \epsilon \)，那么平凡使用快速模型也满足条件 PAC 效率。
  • 分布自由：结果对所有可能的 \( P \) 成立，不假设任何参数形式或光滑性。
  • 与已有文献的比较：
  • 相比 Zeng et al. (2025) 的边际 PAC 效率（仅控制期望风险），本文要求更强的条件控制。
  • 相比 Barber et al. (2021) 的条件覆盖不可能性，本文将类似结论从预测集覆盖迁移到风险控制，且证明结构几乎相同（局部修改分布 + 总变差距离控制）。
  • 相比 Angelopoulos et al. (2025b) 的 conformal risk control，本文聚焦于“条件”而非“边际”风险控制，且证明更简洁（仅需一个引理）。

主要结果

定理 3（Impossibility）：设 \( \mathcal{X} \) 为非原子完备可分度量空间，快速模型在正测度集上损失 \( > \epsilon \)。则算法 \( \mathcal{A} \) 是 \( (\epsilon, \alpha) \)-条件 PAC efficient 当且仅当对几乎所有 \( x \in \mathcal{X} \)，

\[P_{D_{\text{cal}} \sim P^n}(g(x)=0) \leq \alpha.\]

  • 直觉：条件 PAC 效率要求对每个 \( x \) 控制风险。由于在快速模型必然出错的输入上，风险仅由 \( g(x)=0 \) 导致，因此条件保证迫使算法几乎总是使用专家模型。
  • 必要条件：非原子性（否则可在每个原子点上独立校准，如 Barber et al. 2021 所述）。
  • 解决的技术难点：如何从“条件 PAC 效率”推导出“使用快速模型的概率有界”？关键是通过构造敌对分布 \( P' \) 来“暴露”算法在某个 \( x \) 上的行为。构造的难点在于 \( P' \) 必须与 \( P \) 在有限样本上几乎不可区分，同时确保在 \( x \) 处快速模型必然出错。Lemma 5 通过局部修改条件分布解决了这一点。

证明路线与技术技巧

整体路线（3 步）：

  1. 必要性（\( \Leftarrow \)）：若对几乎所有 \( x \)，\( P(g(x)=0) \leq \alpha \)，则

    \[P(R(\hat{f};x) > \epsilon) \leq P(g(x)=0) \leq \alpha,\]

    因为 \( R(\hat{f};x) > \epsilon \) 蕴含 \( g(x)=0 \)。这一步平凡成立。

  2. 充分性（\( \Rightarrow \)）：假设 \( \mathcal{A} \) 是条件 PAC efficient，但存在正测度集 \( E \) 使得对所有 \( x \in E \)，\( P(g(x)=0) > \alpha \)。

  3. 固定 \( x^* \in E \)。由 Lemma 5，对任意 \( \eta > 0 \)，存在分布 \( P' \) 满足：
    (i) 在 \( P' \) 下，\( \ell(\tilde{f}(x^*), f(x^*)) > \epsilon \) 几乎必然；
    (ii) \( \mathrm{TV}((P')^n, P^n) < \eta \)。
  4. 由于 \( \mathcal{A} \) 是条件 PAC efficient，对 \( P' \) 也成立：\( P'_{D_{\text{cal}} \sim (P')^n}(g(x^*)=0) \leq \alpha \)。
  5. 由总变差距离的性质，
    \[|P_{P^n}(g(x^*)=0) - P_{(P')^n}(g(x^*)=0)| \leq \mathrm{TV}(P^n, (P')^n) < \eta.\]

    令 \( \eta \to 0 \) 得 \( P_{P^n}(g(x^*)=0) \leq \alpha \)，与假设矛盾。

  6. 由 \( \mathcal{X} \) 的可分性，该矛盾对 \( P_{\mathcal{X}} \)-几乎所有 \( x \) 成立。

  7. 结论：因此，对几乎所有 \( x \)，\( P(g(x)=0) \leq \alpha \)，即算法几乎总是使用专家模型。

关键跳跃点：Lemma 5 的构造。
- 难点：需要构造一个与 \( P \) 在 \( n \) 个样本上几乎不可区分的分布 \( P' \)，同时确保在 \( x^* \) 处快速模型必然出错。
- 解法：选择以 \( x^* \) 为中心、半径足够小的开球 \( B \)，使得 \( P_{\mathcal{X}}(B) < \eta/(2n) \)。保持 \( P' \) 在 \( B \) 外的条件分布与 \( P \) 相同，但在 \( B \) 内将条件分布替换为某个 \( Q_\epsilon \)，使得所有 \( y \in \mathrm{supp}(Q_\epsilon) \) 满足 \( \ell(\tilde{f}(x^*), y) > \epsilon \）。由于 \( B \) 的测度很小，\( n \) 个样本全部落在 \( B \) 外的概率至少为 \( 1 - n P_{\mathcal{X}}(B) > 1 - \eta/2 \)。在此事件下，\( P' \) 和 \( P \) 的样本分布完全相同；在补事件上，总变差距离最多为 \( 2n P_{\mathcal{X}}(B) < \eta \)。因此总变差距离 \( < \eta \)。

技术技巧点名：
- 有限样本不可区分性（Lemma 5）：利用总变差距离和局部修改，这是分布自由不可能性证明的标准技巧（参见 Barber et al., 2021, Lemma 1）。
- 非原子性：保证可以找到任意小正测度的开球，用于局部修改。
- 可分性：用于将点态结论推广到几乎处处。

真实例子与应用

本文为纯理论，无实证例子。 论文未包含任何模拟或真实数据实验。作者仅在结论中提及“practical implications are clear”，但未提供任何数值验证。

🔎 结论是否比证明窄

  • 定理的“if and only if”是严格的：证明完整覆盖了充分性和必要性，没有过度 claim。
  • “trivial”的定义：作者将“使用快速模型的概率 \( \leq \alpha \)”视为平凡，因为这意味着几乎总是使用专家模型。但严格来说，当 \( \alpha \) 很小时（如 0.05），算法仍能以 5% 的概率使用快速模型，这在某些场景下可能仍有意义。作者未讨论这种“几乎平凡”是否可接受。
  • 假设的强度：定理要求快速模型在 正测度集 上损失 \( > \epsilon \)。如果快速模型仅在零测集上出错（例如，几乎处处正确），则条件 PAC 效率可能非平凡地实现（例如，总是使用快速模型）。作者在 Remark 4 中隐含了这一点，但未明确讨论。
  • 与 Barber et al. (2021) 的关系：本文的证明几乎完全复制了 Barber et al. (2021) 的构造，只是将“预测集覆盖”替换为“风险控制”。作者在引言中承认了这一点，但未强调其证明的新颖性有限。实际上，本文的主要贡献在于 将已知的不可能性结果移植到 PAC 推理框架，而非提出新的证明技术。

四、开放问题（扎根具体语句）

  1. 分布假设下的可能性：本文证明在非原子空间和分布自由设定下不可能。但若对 \( P \) 施加光滑性假设（如 Lipschitz 密度）或对损失函数施加结构（如凸性），是否可能实现非平凡的条件 PAC 效率？

  2. 扎根：结论最后一句：“explore relaxed notions of conditional efficiency under distributional assumptions.”（第 4 页）

  3. 离散输入空间：当 \( \mathcal{X} \) 为有限集（如提示类别有限）时，条件 PAC 效率是否可能？Barber et al. (2021) 指出离散情况下条件覆盖是可能的（通过在每个点上独立校准），但本文未讨论。

  4. 扎根：定理 3 明确假设“非原子”，暗示离散情况可能不同，但作者未展开。

  5. 介于边际与条件之间的保证：能否定义一种“局部”条件保证（如对某个有限子群或邻域），既比边际更强，又避免不可能性？Gibbs et al. (2023) 在 conformal prediction 中给出了有限群组条件覆盖的可行方法，类似思路是否可移植到 PAC 推理？

  6. 扎根：引言提到“This is analogous to the notion of object-conditional validity in conformal prediction”（第 1 页），但未深入讨论中间方案。

  7. 与 conformal risk control 的统一：本文证明的条件 PAC 效率不可能性，是否与 Angelopoulos et al. (2025b) 的 conformal risk control 中的条件版本不可能性等价？能否给出一个统一的框架？

  8. 扎根：作者在引言中引用 Angelopoulos et al. (2025b) 和 Gibbs et al. (2025)，但未比较两者的证明或结论。

提醒：要确认这些是否真 gap，建议阅读 Barber et al. (2021) 的讨论部分、Gibbs et al. (2023) 的引言，以及 Angelopoulos et al. (2025b) 中关于条件风险控制的段落。若多篇近期论文都指向同一方向，则为共识性 gap；若互相矛盾，则可能是机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论