Paper Detail

Sketching Language Models for Context Attribution

Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou

arxiv Score 8.8

Published 2026-11-12 · First seen 2026-11-13

General 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.

Workflow Status

Review status
pending
Role
unreviewed
Read priority
soon
Vote
Not set.
Saved
no
Collections
Not filed yet.
Next action
Not filled yet.

Reading Brief

No structured notes yet. Add `summary_sections`, `why_relevant`, `claim_impact`, or `next_action` in `papers.jsonl` to enrich this view.

Why It Surfaced

No ranking explanation is available yet.

Tags

No tags.

BibTeX

@article{liaw2026sketching,
  title = {Sketching Language Models for Context Attribution},
  author = {Christopher Liaw and Aranyak Mehta and Grigoris Velegkas and Felix Zhou},
  year = {2026},
  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 \$\textbackslash{}varepsilon\$ with constant probability using \$O(\textbackslash{}sqrt\{\textbackslash{}log(1/\textbackslash{}varepsilon)\}/\textbackslash{}varepsilon)\$ evaluation calls. To complement our upper bound, we prove},
  url = {https://arxiv.org/abs/2611.17313},
  keywords = {cs.DS, cs.AI, cs.LG, stat.ML},
  eprint = {2611.17313},
  archiveprefix = {arXiv},
}

Metadata

{}