面向上下文归因的草图化语言模型算法研究
Sketching Language Models for Context Attribution
AI 导读
一项 arXiv 研究提出草图算法，加速语言模型的 leave-one-out（LOO）上下文归因计算。在稳定性假设下，该算法以 O(√log(1/ε)/ε) 次模型评估估计全部 n 个 token 的 LOO 值，误差与 ε 成正比，并证明匹配的 Ω(√log(1/ε)/ε) 下界，优于直接适配前向微分草图所需的 O(log(n)/ε²) 次调用。
正文 · 原文
Abstract: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 $\Omega(\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.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2611.17313 [cs.DS] |
| (or arXiv:2611.17313v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2611.17313 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Felix Zhou [view email]
[v1]
Thu, 12 Nov 2026 18:57:48 UTC (243 KB)
来源：arXiv cs.AI · arxiv.org