Towards Long-Horizon Interpretability: Efficient and Faithful Multi-Token Attribution for Reasoning LLMs

Token attribution methods provide intuitive explanations for language model outputs by identifying causally important input tokens. However, as modern LLMs increasingly rely on extended reasoning chains, existing schemes face two critical challenges: (1) efficiency bottleneck, where attributing a target span of $M$ tokens within a context of length $N$ requires $\mathcal{O}(M \cdot N)$ operations, making long-context attribution prohibitively slow; and (2) faithfulness drop, where intermediate reasoning tokens absorb attribution mass, preventing importance from propagating back to the original input. To address these, we introduce FlashTrace, an efficient multi-token attribution method that employs span-wise aggregation to compute attribution over multi-token targets in a single pass, while maintaining faithfulness. Moreover, we design a recursive attribution mechanism that traces importance through intermediate reasoning chains back to source inputs. Extensive experiments on long-context retrieval (RULER) and multi-step reasoning (MATH, MorehopQA) tasks demonstrate that FlashTrace achieves over $130\times$ speedup over existing baselines while maintaining superior faithfulness. We further analyze the dynamics of recursive attribution, showing that even a single recursive hop improves faithfulness by tracing importance through the reasoning chain.

Modern AI language models often "think out loud," producing long chains of intermediate reasoning before giving a final answer. When we want to understand why a model answered as it did, we would like to trace the answer back to the specific pieces of the original input that mattered. Existing tools for this "attribution" task were built for short answers and break down on long reasoning in two ways: they become extremely slow, and they tend to credit the model's own intermediate thoughts rather than the original input. This paper introduces FlashTrace, a method that makes such explanations both fast and accurate for long reasoning. Instead of analyzing the answer one word at a time, FlashTrace analyzes a whole span of words at once, cutting the computation from hours to seconds. It also follows the trail of importance step by step through the model's reasoning back to the input that truly drove the answer. Across long documents, multi-step question answering, mathematics, and code, FlashTrace is over 130 times faster than previous methods while producing more faithful explanations, making it practical to inspect and audit modern reasoning AI systems.