A Sketching Trick That Estimates Every Token's Importance in Sublinear Time — With Matching Lower Bounds

Provably optimal algorithm estimates all leave-one-out attribution values for n-token prompts using O(√log(1/ε)/ε) model calls instead of n. Tight lower bound proves you can't do better.

Imagine you're a chef tasting a stew with 30 ingredients, and you want to know how much each one matters. The brute-force approach: make 30 separate pots, each missing one ingredient, and taste them all. That's expensive. Now imagine you could instead take a handful of cleverly chosen random spoonfuls from perturbed versions of the stew — far fewer than 30 — and mathematically reconstruct each ingredient's contribution with controlled error. That's what this paper does for language model prompts. The committed claim: given a prompt of n tokens and a fixed measurement function, you can estimate every leave-one-out (LOO) attribution value to ε error using O(√log(1/ε)/ε) model evaluations — and this is provably optimal. The brute-force cost is n evaluations. This paper's cost depends only on the desired accuracy ε, not on prompt length n. For long prompts, this is a dramatic win. The matching Ω(√log(1/ε)/ε) lower bound means no algorithm in this oracle model can do better, period. The mechanism lives in the intersection of two ideas: sketching algorithms for arithmetic circuits and a stability condition on Taylor coefficients recently introduced by Gunn (2026). The authors' key insight is applying forward differentiation not to the original computation graph but to the backpropagation circuit. This is the load-bearing technical move — it reduces variance of the sketches and drops the evaluation complexity from Õ(log(n)/ε²) (what a direct adaptation of Gunn's approach would give) down to O(√log(1/ε)/ε). The backprop-sketch composition is genuinely clever: you get constant overhead over a forward sketch of the same Taylor degree while harvesting the variance reduction that backpropagation naturally provides. On the ladder: the naive baseline is n full model evaluations. Prior sketching work (Gunn's forward differentiation) would need Õ(log(n)/ε²) calls — still sublinear in n but quadratic in 1/ε and logarithmic in n. This paper removes both the n-dependence and the ε² penalty. The lower bound, building on Amsel, Chen, Duman Keleş, Halikias, Musco, and Musco's matrix-diagonal estimation techniques, locks the result tight. This is not an incremental improvement — it's a complexity-theoretic resolution of the question. Integrity is mixed in a characteristic theory-paper way. The upper bound is a mathematical proof — airtight within its model. The lower bound is an information-theoretic argument in an oracle model, which is the right framework but does leave room for real-world shortcuts if the stability assumption is unusually favorable in practice. Empirically, the authors verify coefficient decay consistent with their stability assumption and test on a small LM retrieval task — this is a sanity check, not a large-scale empirical validation. No community benchmark exists for this exact problem, so they're necessarily grading their own homework on the experimental side. The stability assumption is the elephant: the paper assumes Taylor coefficients of the model's output (viewed as a multilinear polynomial in token inclusion/exclusion variables) decay in a specific way. The authors provide empirical evidence this holds for a small model, but whether it holds for frontier-scale transformers under diverse prompts is an open and important question. If the assumption breaks, the guarantees evaporate. The practical unlock is interpretability at scale. Context attribution — understanding which parts of a prompt drive model behavior — is a bottleneck for retrieval-augmented generation, prompt debugging, and mechanistic interpretability. If you can get reliable LOO scores in sublinear time, you can run attribution as a routine diagnostic rather than an expensive offline analysis. The gap between here and deployment is empirical validation on large models with long contexts — the theory is done, but the engineering story is just beginning.