Sketching 算法将上下文归因的模型调用次数从 n 降到 O(√log(1/ε)/ε)
Sketching Language Models for Context Attribution
做可解释性或提示词调试的人可以看看这篇。算一段提示词里每个 token 对输出的影响，以前要跑 n 次模型，现在用 sketching 方法只要近平方根次，还配了理论下界证明这基本是最优的。
arXiv 论文（编号 2611.17313）研究上下文归因问题：删除提示词中的某部分后，语言模型的输出会怎么变。对 n 个 token 的提示做 leave-one-out（LOO）归因，直接计算需要 n 次模型评估。论文提出的 sketching 算法在稳定性假设下，用 O(√log(1/ε)/ε) 次评估调用即可把所有 LOO 值估计到误差正比于 ε，同时证明了匹配的 Ω(√log(1/ε)/ε) 下界，说明该复杂度在 oracle 模型中不可再降。
技术核心是对反向传播电路施加前向微分：此前直接改编 Gunn 提出的前向微分 sketch 需要 Õ(log(n)/ε²) 次调用，而作者发现在反传电路上做前向微分只需常数级额外开销，就能显著降低 sketch 方差，从而把评估次数压到近平方根级别。下界证明沿用了 Amsel、Musco 等人在随机矩阵对角元估计上的矩阵-向量查询技术。
实验部分验证了 Taylor 系数衰减与稳定性假设一致，并在一个小型语言模型检索任务上测试了算法表现。对做可解释性分析或提示词调试的开发者来说，这意味着大规模 token 级归因的成本可能从线性降为近平方根级。
Sketching Language Models for Context Attribution
Context attribution asks how removing parts of a prompt changes a language model's output. We study leave-one-out (LOO) attribution for a prompt of $n$ tokens and a fixed measurement function. Computing all LOO values directly requires $n$ model evaluations. Under a stability assumption, our algorithm estimates all LOO values to error proportional to $\varepsilon$ with constant probability using $O(\sqrt{\log(1/\varepsilon)}/\varepsilon)$ evaluation calls. To complement our upper bound, we prove a matching $Ω(\sqrt{\log(1/\varepsilon)}/\varepsilon)$ lower bound on the number of evaluation calls in an oracle model. Empirically, we verify coefficient decay consistent with stability and evaluate the performance of our sketching algorithm on a small language-model retrieval task. Technically, our result is based on a sketching algorithm for arithmetic circuits whose Taylor coefficients satisfy the stability condition recently introduced by Gunn [Gun26]. A direct adaptation of their forward differentiation sketches would require $\widetilde{O}(\log(n)/\varepsilon^2)$ evaluation calls. Our key observation is that we can apply forward differentiation to the backpropagation circuit, with only constant overhead over a forward sketch of the same Taylor degree. This reduces the variance of the sketches and is key to our improved evaluation bound. Our lower bound builds on the techniques of Amsel, Chen, Duman Keles, Halikias, Musco, and Musco [ACDH+26, SIAM Journal on Matrix Analysis and Applications] for lower bounding the number of matrix-vector queries to estimate the diagonal elements of random matrices.
本条情报归属 AITOP「论文」核心栏目，重点聚焦北美前沿实验室与硅谷科技巨头。在跨区域产业观察坐标中，该动态直接关联「AI 开发者工具链、Coding Agent 与工程化实践」研究主线，反映出当前技术演进与商业落地的最新风向。涉及核心实体与技术议题包括：上下文归因、sketching、可解释性、语言模型，读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明：本文原始线索采编自「arXiv cs.LG」（@Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou），经 AITOP 多维评分管线结构化提炼。