Tracing Computation Density in LLMs

Corentin Kervadec, Iuliia Lysova, Iuri Macocco, Marco Baroni, Gemma Boleda · 2026

Read Tracing Computation Density in LLMs by Corentin Kervadec, Iuliia Lysova, Iuri Macocco, Marco Baroni, Gemma Boleda (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27033.txt.

Introduction

In their 2026 study, Kervadec and four co-authors present s-Trace, a method that estimates a small subgraph approximating a full language model's output. Computation organizes into two phases: a sparse early-layer core reconstructs the head of the output distribution, while added later-layer nodes, increasingly attention heads, refine it step by step. Needed computation per input tracks model uncertainty, and sparser subgraphs encode shallow statistics such as unigram frequency. The results suggest a consistent modular organization of effective model computation.

Catalog record

CREATORCorentin Kervadec, Iuliia Lysova, Iuri Macocco, Marco Baroni, Gemma Boleda
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41738
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27033

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tracing Computation Density in LLMs Corentin Kervadec, Iuliia Lysova, Iuri Macocco, Marco Baroni, Gemma Boleda Abstract Transformer-based large language models (LLMs) are comprised of billions of parameters arranged in deep and wide computational graphs, but it is not clear that they exploit their full capacity for all inputs. We introduce the s-Trace method to efficiently estimate the subgraph of size s that best approximates a full model output. With this method, we find the computation in a variety of LLMs to be organized in two distinct phases. A small subgraph mostly composed of early-layer nodes can reconstruct the head of the full model output distribution. Adding further nodes, mostly located in later layers and increasingly consisting of attention heads, leads to incremental refinements in approximating the full output distribution. We find moreover that the amount of necessary computation per input correlates with model uncertainty, and that sparser subgraphs encode shallow statistics, such as unigram frequency. Overall, our results suggest a consistent modular organization in effective LLM computation, with a sparse early-layer core providing a rough prediction that is further refined through denser computations in later layers. 1 Introduction Modern transformer-based large language models (LLMs) can be represented as deep and wide computational graphs whose execution entails billions of operations that collectively update internal representations to yield a prediction. While standard inference executes the full graph for every input, it remains unclear whether the effective computation required to generate a faithful prediction utilizes the model’s full capacity or relies on a considerably sparser sub-network. Furthermore, the structural nature of this effective computation is largely unknown: is it uniformly distributed across the network, or is it composed of distinct dense and sparse subgraphs? It is also an open question whether this effective amount of computation is dependent on specific input properties. Answering these questions has both practical and theoretical implications. From a practical point of view, precisely quantifying the true sparsity of LLM computation and predicting which inputs require more computation can help building more efficient models through pruning, routing, distillation or other techniques. Establishing sparsity is also a prerequisite for meaningful application of interpretability techniques such as circuit analysis, that assume that many language/knowledge processes in LLMs can be reduced to the mechanics of a sparse subgraph ( 8 ; 12 ; 2 ) . From a theoretical point of view, our pursue bears on two fundamental questions in cognitive science. On the one hand, language competence has traditionally been modeled as a sparse, symbolic, rule-based system greatly at odds with LLMs’ highly distributed nature 35 . If LLMs turned out to rely on much sparser circuits during average processing, this would pave the way for a reconciliation between the symbolic and distributed views of language 6 . On the other hand, the nature of linguistic complexity and how to measure it are fundamental topics in linguistics ( 20 , e.g.,) . If the amount of effective computation in LLMs depends on specific properties of their inputs, then LLMs could provide a practical and precise way to measure complexity. We introduce here a general method to calculate the amount of effective computation performed by an LLM in response to an input. The method, based on automated circuit discovery ( 9 ; 13 ; 36 ) , extracts the sub-network of size s (the s-Trace ) that, given an input, best reconstructs the output probability distribution generated by the full model. Varying the computation budget, measured as the size of the sub-network, allows for a systematic examination of the performance/complexity trade-off in LLMs (Fig. 3 ). We analyze 10 different LLMs, ranging from 7B to 14B parameters, and find pervasive sparsity in LLM computation. By analyzing the trace across varying granularities, we identify two distinct phases. First, for highly sparse subgraphs (beginning at 10^{-4} of full model size), LLMs undergo a construction phase , in which each operation strongly affects the output prediction, and there is a predominance of early layers being added. Within this phase (at \approx 10^{-3} ), a highly stable minimal core emerges, sufficient to accurately recover the head of the output distribution. Beyond 10^{-2} , having already reconstructed 40\% to 60\% of the prediction probability mass, the trace enters a refinement phase . Here, the marginal utility of additional operations, which are mostly located in later layers, becomes diffuse. At this stage, the network only fine-tunes the prediction, integrating the nuances required to encode the full richness of the final output distribution. We also find that different LLMs distribute computation in strikingly similar patterns across similar inputs, suggesting that resource allocation depends on intrinsic input properties, more than on the architectural details of specific models. Two results suggest that computation density, as measured by the s-Trace method, is indeed related to the complexity of the input: 1) the density distribution is positively correlated with LLM output entropy (LLMs’ own uncertainty estimate); 2) density increases for rarer words (plausibly harder to guess). 1 1 1 The code and data required to reproduce the experiments will be made publicly available on a Github repository upon acceptance. 2 Background Sparsity in LLMs Our work builds on a rich literature establishing structural sparsity in neural networks 25 ; 14 , which extends directly to LLMs 39 . While static pruning techniques identify permanently redundant parameters or layers across a model 32 ; 23 ; 28 , a growing body of evidence suggests that computation density is highly dynamic and input-dependent. Modern efficiency frameworks exploit this by dynamically bypassing modular units, attention heads, or entire layers on the fly based on token-level complexity and input difficulty 42 ; 29 ; 11 ; 26 . While these methods focus on task-specific efficiency, our goal is analytical: we seek to quantify the computational footprint required by an LLM to faithfully reconstruct its own output distribution during generic next-token prediction. Mechanistic Interpretability To quantify the amount of computation in LLMs, we leverage methods from mechanistic interpretability. This line of research generally views LLMs as computational graphs composed of discrete, human-interpretable “circuits" 33 ; 8 ; 2 . Notable examples include circuits responsible for the greater-than operation 18 , indirect object identification 40 , subject-verb agreement 12 , and knowledge retrieval 30 . Circuit discovery can be automated, for instance using greedy search 9 , sparse dictionary learning 7 , activation patching 36 , or gradient-based pruning 4 . More recently, the granularity of circuit discovery has transitioned from coarse attention heads to individual features using sparse autoencoders 7 and cross-layer transcoders 2 . We specifically build upon the Information Flow Route (IFR) framework 13 , which leverages attribution to efficiently identify circuits at scale. However, rather than applying it to the identification of task-specific circuits, we repurpose it as a general method to estimate the maximum degree of output reconstruction that can be achieved by a subgraph of a certain size. Structure of Computation in LLMs Our s-Trace approach is motivated by the “unraveled view” of residual networks 38 , which states that the transformer architecture behaves not as a monolithic pipeline, but as an implicit ensemble of shallower subnetworks. Our method exploits this by using an unconstrained graph traversal algorithm to identify and extract these

Read the complete text