論文 / arXiv:2611.17313
Sketching Language Models for Context Attribution
PLAIN SUMMARY / やさしい要約
長い文章を読んだときに「どの一文が結論に効いたか」を確かめたいことがあります。通常は、一文ずつ抜いて何度も試す必要があります。この研究は、ある条件の下で、少ない試行回数でもその影響度をまとめて推定できる方法を提案します。たとえるなら、全ページを1枚ずつめくって確認する代わりに、要点だけを拾う“速いチェック”を設計する話です。
AIが専門用語を使わずに書いた解説です。内容の正確さは、下の原文の要旨で確認してください。
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 $Ω(\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.
ここに表示しているのは原論文の要旨です。AIによる要約や解釈は含みません。
