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:
- Backpropagation: They use standard backprop to get the gradient of the output with respect to the input weights.
- Forward Differentiation: They then apply forward differentiation to that gradient circuit.
- Random Projections: Instead of calculating every possible interaction, they project the Taylor tensors onto random complex Gaussian vectors.
- 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