cs.DSNov 12, 2026

Sketching Language Models for Context Attribution

Authors: Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou

Organizations: Google Research · Yale University*

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.

Figures & tables

Explore similar work

CardsList
  1. DeltaTrace: Efficient Signed Attribution for Reasoning Language Models

    Oct 19, 2026Chen Liang, Daoping Wu, Donghua Yang +4Feature AttributionLLM Interpretability

  2. Probabilistic Attribution For Large Language Models

    May 20, 2026Shilpika Shilpika, Carlo Graziani, Bethany Lusch +2LLM InterpretabilityLLM Uncertainty Estimation