You can estimate token-level attribution in LLMs much faster than brute force by applying sketching to the backpropagation circuit, reducing evaluations from linear in prompt length to a small constant factor.
This paper develops an efficient algorithm to compute how removing individual tokens from a prompt affects a language model's output. Instead of evaluating the model n times (once for each token removal), the algorithm uses sketching techniques to estimate all attribution values with only O(√log(1/ε)/ε) evaluations, matching a proven lower bound.