Sketching Language Models for Context Attribution

Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Felix ZhouarXiv 2026 · arXiv

TL;DR

This paper introduces a highly efficient algorithm for "context attribution"—determining how much each part of a prompt contributes to a language model's output. By combining backpropagation with forward differentiation in a novel "backward-forward sketch," the authors can estimate all Leave-One-Out (LOO) values using a number of model evaluations that is independent of the prompt length, achieving a theoretically optimal query complexity.

What Problem Does This Paper Address?

When a language model (LM) generates an answer, we often want to know which parts of the input prompt were responsible for that specific output. This is crucial for assigning credit to sources, pruning unnecessary context, or detecting "poisoning" attacks.

The gold standard for this is Leave-One-Out (LOO) attribution: you remove one token (or chunk) at a time and see how the output changes. The problem is scale. If your prompt has $n$ tokens, brute-force LOO requires $n$ separate model evaluations. For long-context models, this is computationally ruinous. While researchers use heuristics like gradient saliency or surrogate models, these often lack formal accuracy guarantees and can fail when tokens interact non-linearly.

Methods

The authors treat the LM as an arithmetic circuit and leverage a property called stability—the idea that the model's Taylor coefficients (which describe how the output changes as you "downweight" tokens) decay quickly.

Their core technical contribution is the Backward-Forward Sketch:

  1. Backpropagation: They use standard backprop to get the gradient of the output with respect to the input weights.
  2. Forward Differentiation: They then apply forward differentiation to that gradient circuit.
  3. Random Projections: Instead of calculating every possible interaction, they project the Taylor tensors onto random complex Gaussian vectors.
  4. Trimmed Mean Estimation: To handle potential outliers in these random samples, they use a "trimmed mean" (discarding the highest and lowest values) to produce a robust estimate.

By sketching the gradient rather than the function itself, they significantly reduce the variance of their estimates. This allows them to achieve an upper bound of $O(\sqrt{\log(1/\epsilon)}/\epsilon)$ evaluation calls to reach an error of $\epsilon$, regardless of how many tokens $n$ are in the prompt.

Datasets

The paper focuses primarily on theoretical proofs, but includes a "proof of concept" experiment:

  • Model: Llama-3.2-1B-Instruct.
  • Task: A small retrieval task where the model is given 12 chunks of text. Only one chunk (the 7th) contains the answer to a specific question; the others are irrelevant noise.
  • Implementation: They implemented the downweights using continuous attention masking, allowing them to "partially deactivate" tokens to calculate derivatives.

Key Insights and Ideas

  • Independence from $n$: The most striking insight is that the number of model calls needed for a specific accuracy level doesn't grow with the prompt length. You can attribute a 100-token prompt or a 100,000-token prompt with the same number of sketches.
  • The Power of the Gradient: Previous sketching methods (like Gunn [Gun26]) sketched the function directly. By sketching the backpropagation circuit, the authors capture first-order information exactly, which slashes the variance of the remaining higher-order terms.
  • Optimality: The authors didn't just find a fast algorithm; they proved a matching lower bound. This means that in a "black-box" setting, no algorithm can do significantly better than theirs.
  • Stability is Real: They empirically verified that modern LLMs like Llama-3.2 actually exhibit the "Taylor coefficient decay" required for their math to work.

Key Results

  • Theoretical Efficiency: The algorithm improves the query complexity from $\widetilde{O}(\log(n)/\epsilon^2)$ in prior work to $O(\sqrt{\log(1/\epsilon)}/\epsilon)$.
  • Variance Reduction: In experiments, the backward-forward sketches showed significantly lower standard deviation compared to forward-only sketch baselines at the same computational budget.
  • Accuracy: The algorithm correctly identified that the "answer chunk" in their retrieval task had the highest attribution, and the estimated error proxies closely tracked the actual empirical error.

Limitations and Future Work

  • Scale of Experiments: The empirical tests were "minimal," involving only 12 chunks. While the theory suggests it will scale to thousands of tokens, large-scale practical testing is still needed.
  • Polynomial Approximations: The theory assumes arithmetic circuits (which use additions and multiplications). Real LMs use non-polynomial functions like Softmax and GELU. The authors used polynomial approximations for these, but the impact of these approximations on very deep models isn't fully explored.
  • Implementation Complexity: Implementing "continuous masking" and forward differentiation through a backprop circuit requires deep integration with frameworks like JAX (which they used) or PyTorch, which might be a hurdle for some practitioners.

Summary updated

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.
BibTeX
@misc{liaw2026sketching,
  author = {Christopher Liaw and Aranyak Mehta and Grigoris Velegkas and Felix Zhou},
  title = {{Sketching Language Models for Context Attribution}},
  year = {2026},
  eprint = {2611.17313},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17313},
}
Figure