How Much Does One Wrong Answer Cost? Error Propagation in Constraint Pruning with Noisy LLM Oracles
作者: Zhengtao Gui, Weining Shen
分类: cs.LG
发布日期: 2026-10-19
备注: 33 pages, including appendices
💡 一句话要点
提出错误传播模型以优化约束修剪中的噪声LLM预言机
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 约束修剪 错误传播 大型语言模型 风险评估 实体解析 查询优化
📋 核心要点
- 现有的约束修剪方法通常假设预言机是正确的，未考虑错误传播对结果的影响。
- 论文提出了一种新的风险评估框架，考虑了预言机错误时的约束修剪效果，特别是错误答案的传播效应。
- 通过模拟实验，论文验证了不同查询顺序对错误传播的影响，提供了优化的查询策略。
📝 摘要（中文）
约束修剪通过跳过先前接受答案所隐含的每个是/否问题，来节省对大型语言模型（LLM）或其他噪声预言机的查询。然而，现有分析通常假设预言机是正确的。本文主张在预言机出错时应评估修剪的风险，因为一个错误答案会传播到它所暗示的每个问题。我们分析了两种约束类型，发现随机顺序的修剪不会增加一阶风险，而共享前提的规则则会导致更高的风险。通过模拟实验，我们验证了理论预测的准确性。
🔬 方法详解
问题定义：本文解决的是在约束修剪中如何评估预言机出错时的风险，现有方法未考虑错误传播的影响，可能导致错误累积。
核心思路：论文提出了一种新的风险评估方法，分析了错误答案如何影响后续问题的正确性，特别是通过随机顺序和共享前提的规则来评估风险。
技术框架：整体架构包括对约束类型的分类、风险评估模型的构建以及模拟实验的设计，主要模块包括错误传播分析和查询顺序优化。
关键创新：最重要的技术创新在于提出了一阶风险的概念，并通过数学模型定量分析了错误答案对多个事实的影响，突破了传统方法的局限。
关键设计：关键参数包括错误概率$ ext{ε}$和Wiener指数的计算，损失函数设计为基于错误传播的影响评估，确保模型能够准确反映风险。
🖼️ 关键图片
📊 实验亮点
实验结果表明，优化的查询顺序能够将错误传播的影响降低至2倍以内，而随机顺序的影响则高达$m^{1/3}$，这表明新方法在处理错误时的有效性显著优于传统方法。
🎯 应用场景
该研究的潜在应用领域包括实体解析系统和基于LLM的排序系统，能够有效减少错误传播带来的影响，提高系统的鲁棒性和准确性。未来，该方法可扩展至其他依赖于不确定性预言机的领域，如自动问答和信息检索。
📄 摘要（原文）
Constraint pruning saves queries to a large language model (LLM) or another noisy oracle by skipping each yes/no question implied by answers accepted earlier, for example through transitivity. Entity-resolution systems and LLM-based rankers use this idea. However, their analyses typically assume a correct oracle. We argue that pruning should be judged by its risk when the oracle errs, since an accepted wrong answer spreads to every question it implies. When each answer is wrong independently with small probability $\varepsilon$, the first-order risk is set by how many facts one wrong answer corrupts on average. We consider two kinds of constraints. For implication rules, as in taxonomies, pruning in a random order adds no first-order risk: a wrong answer that would change $k$ facts is accepted with probability $1/k$, so it costs one fact on average. Rules with $s$ premises break this balance: a wrong answer at a premise shared by $r$ rules can cost order $r^{1-1/s}$ facts. For entity resolution with $m$ records of one entity, the first-order risk equals $\varepsilon$ times the Wiener index (the total pairwise distance) of the spanning tree built by the query order. Pivot orders, which first compare one record with all others, amplify errors by less than 2 and are optimal; random orders by order $m^{1/3}$; the common most-similar-first order is the worst in one dimension and, for large $m$, worse than random in two. With several entities, the cost of wrongly merging two does not depend on how many others exist. Simulations agree with every predicted constant within sampling error.