betaFeedback

WorksComputer Science

Sketching Language Models for Context Attribution

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 nn tokens and a fixed measurement function. Computing all LOO values directly requires nn model evaluations. Under a stability assumption, our algorithm estimates all LOO values to error proportional to ε\varepsilon with constant probability using O(log⁡(1/ε)/ε)O(\sqrt{\log(1/\varepsilon)}/\varepsilon) evaluation calls. To complement our upper bound, we prove a matching Ω(log⁡(1/ε)/ε)Ω(\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 O~(log⁡(n)/ε2)\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.

Paper details

vlnc:W_qqpjmj45
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…