Researchers Christopher Liaw, Aranyak Mehta, and Grigoris Velegkas from Google Research, alongside Felix Zhou from Yale University, released a preprint on November 12, 2026, titled Sketching Language Models for Context Attribution (arXiv:2611.17313v1). The study introduces a randomized sketching algorithm that estimates leave-one-out prompt attribution without evaluating each input token individually, providing research teams with provable computational bounds to verify source attribution, trace evidence grounding, and conduct rigorous model audit workflows in retrieval-augmented research systems.
What happened
In long-context language models and retrieval-augmented generation (RAG), researchers often need to determine which specific documents, paragraphs, or prompt tokens directly influenced a generated response. The standard benchmark for measuring this influence is leave-one-out (LOO) context attribution, which calculates how removing a specific token or text chunk alters a target measurement, such as the log-probability of the model’s generated completion.
Historically, computing exact leave-one-out attribution across an n-token prompt required n distinct forward passes through the model. For modern language models processing thousands of context tokens, running n full evaluations is computationally prohibitive. While practitioners frequently rely on surrogate models, embedding similarities, or first-order gradient heuristics to approximate token influence, these shortcuts lack formal theoretical guarantees and often break down when context pieces interact nonlinearly.
The research team solved this scaling bottleneck by framing context attribution as a sketching problem over arithmetic circuits. Under an assumption of model stability—where the Frobenius norms of higher-order Taylor coefficient tensors decay exponentially—their randomized sketching algorithm estimates all n leave-one-out values within an error margin proportional to epsilon using only sublinear evaluations. Crucially, the number of required model evaluation calls scales as O(min{n, sqrt(log(1/epsilon)) / epsilon}), breaking the linear dependency on context length. The authors also established a matching information-theoretic lower bound of Omega(min{n, sqrt(log(1/epsilon)) / epsilon}) in an oracle query model, proving their evaluation complexity is asymptotically optimal.
Methodology and key findings
To overcome the high variance of prior sketching methods, the authors introduced backward-forward sketching. Earlier circuit-sketching techniques based on forward automatic differentiation required tilde-O(log(n) / epsilon^2) queries. By applying forward differentiation directly to the backpropagation circuit (the value-and-gradient graph), the team reduced variance while maintaining constant overhead per evaluation call.
The authors validated their theoretical bounds through proof-of-concept experiments on an NVIDIA H100 GPU using the Llama-3.2-1B-Instruct model running at 64-bit precision in JAX via its jet higher-order differentiation module. Testing a 12-chunk document retrieval task where a single target chunk contained the factual answer, the team first applied a gradient-based ranking step to evaluate the top chunk exactly and then sketched the remaining eleven chunks across 128 independent trials with eight random complex Gaussian projections per trial. The empirical tests confirmed rapid Taylor coefficient decay consistent with stability, demonstrating that higher-order Taylor approximations track empirical leave-one-out values accurately while avoiding brute-force evaluations.
Why it matters for research practice
Scalable, provably bounded context attribution addresses several pressing challenges in scientific data stewardship, provenance tracking, and AI governance:
- Evidence grounding and citation integrity: When researchers use automated tools to synthesize literature or generate systematic reviews, attributing claims to exact source passages is essential to prevent subtle hallucinations. Provable attribution ensures that citations reflect true computational dependencies rather than plausible correlation.
- Auditing automated research pipelines: Implementing systematic oversight requires verifying that models do not rely on biased context or poisoned prompt injections. Sketching provides a mathematically grounded mechanism to inspect prompt influences without requiring supercomputing budgets for every query.
- Computational reproducibility: As highlighted in standards for a reproducible AI experiment and institutional reproducibility infrastructure, scientific findings derived from language models must be verifiable. Reliable context attribution bridges the gap between opaque black-box outputs and inspectable evidence trails.
- Dataset and model documentation: Scalable token attribution aligns with emerging best practices for persistent identifiers and citation for AI models and training datasets, allowing researchers to document precisely which contextual datasets or knowledge bases generated specific scientific conclusions.
Sources
- Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, and Felix Zhou. “Sketching Language Models for Context Attribution.” arXiv preprint arXiv:2611.17313v1, submitted November 12, 2026. https://arxiv.org/abs/2611.17313.
- Gunnar Gunn. “Sketching Arithmetic Circuits.” arXiv preprint arXiv:2602.04567, 2026.
- Noah Amsel, Tyler Chen, Sinan Duman Keles, Diana Halikias, Cameron Musco, and Christopher Musco. “Lower bounds for estimating the diagonal of random matrices via matrix-vector queries.” SIAM Journal on Matrix Analysis and Applications, 2026.
