Tracing Computation Density in LLMs¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/CorentinKervadec/llm-strace
Area: LLM Reasoning
Keywords: computation density, mechanistic interpretability, s-Trace, computational graph pruning, prediction uncertainty
TL;DR¶
This paper introduces s-Trace, a training-free single-pass causal graph traversal framework to quantify computation density in LLMs, revealing a modular two-phase computational organization where an early-layer minimal core (0.01%–1% of edges) constructs rough predictions and dense later-layer attention heads (1%–100%) refine the full distribution.
Background & Motivation¶
Modern autoregressive Transformer-based Large Language Models (LLMs) are structured as deep and broad computational graphs comprising billions of parameters. During standard forward execution, these models execute the entire computational graph indiscriminately across all tokens and contexts, consuming vast floating-point budgets regardless of sequence complexity. While empirical insights from pruning and cognitive science have long suggested structural sparsity in artificial neural networks, it has remained an open theoretical question whether LLMs actually deploy their full capacity during generic language generation, or instead rely on compact, unraveled subgraphs. Understanding the nature and distribution of this effective computation bears critical importance for both model efficiency and cognitive science, potentially bridging symbolic linguistic competence with distributed neural processing.
Existing methodologies in mechanistic interpretability and dynamic inference face severe paradigm bottlenecks when probing this global sparsity. Conventional static pruning primarily identifies globally redundant parameters or entire layers, failing to capture dynamic, token-dependent computational routing. Conversely, mechanistic circuit discovery methods depend heavily on activation patching over handcrafted counterfactual input pairs; this approach incurs prohibitive computational costs on 7B–14B models and targets only narrow, synthetic toy tasks (such as indirect object identification). Critically, measuring circuit faithfulness via discrete top-1 accuracy ignores the model's full output probability distribution, which frequently results in degenerate or overly simplistic circuits that fail to capture subtle linguistic nuances.
To overcome the combinatorial barrier of causal patching and assess computation allocation during generic text generation, this work shifts from isolated task circuits to comprehensive graph-wide topological tracing. Drawing inspiration from the unraveled view of residual networks as ensembles of shallower sub-networks, the authors formalize the LLM forward pass as a fine-grained causal directed acyclic graph and develop s-Trace—a scalable greedy best-first traversal powered by node-normalized activation magnitudes. Across 10 open-weight models from 7 model families, this approach maps the entire trade-off between subgraph size and full distribution fidelity across five orders of magnitude. Core idea: model the LLM forward pass as a token-level causal computational graph and extract size-budgeted subgraphs via single-pass greedy traversal (s-Trace) to uncover and quantify a universal two-phase computational organization governed by an early-layer minimal core followed by late-layer attention refinement.
Method¶
Overall Architecture¶
The objective of the s-Trace framework is to identify, for any input sequence \(t = (t_1, \dots, t_n)\) and budget parameter \(s \in [0, 1]\), a subset of directed edges \(\mathcal{E}_s \subset \mathcal{E}\) (with \(|\mathcal{E}_s|/|\mathcal{E}| = s\)) in the computational graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) such that the next-token probability distribution \(\hat{P}_{\mathcal{T}_s}(t_{n+1} \mid t)\) generated by the masked subgraph \(\mathcal{T}_s\) minimizes the Total Variation (TV) distance to the full model's output distribution \(P(t_{n+1} \mid t)\). The pipeline operates in three streamlined stages: first, it extracts token-level activation vectors during a single forward pass and computes node-normalized \(L_1\) importance scores for all attention and MLP edges; second, it initializes a max-priority queue at the final token output node and traverses backward using Greedy Best-First Search (BeFS) to expand a connected sub-network until the budget \(s\) is reached; third, it applies binary masking during inference to compute the Total Variation error and integrates the error curve to derive a unified scalar computational density metric \(C\).
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Tokens & Target Output Node<br/>t = (t_1, ..., t_n), h_n^L"] --> B["1. Fine-Grained Causal Computational Graph Formulation<br/>Unraveling Residuals, MLPs & Pairwise Token Attention Edges"]
B --> C["2. Node-Normalized L1-Norm Edge Importance Scoring<br/>Single-Pass Activation Magnitude Proxy"]
C --> D["3. Greedy Best-First Subgraph Traversal<br/>Backward Expansion from Prediction Output via Max-Priority Queue"]
D --> E["4. Total Variation Faithfulness & Computational Density<br/>Distributional Reconstruction Error & Area-Under-Curve Integration"]
E --> F["Output: Two-Phase Computational Topology<br/>Construction Phase (Minimal Core) & Refinement Phase"]
Key Designs¶
1. Fine-Grained Causal Computational Graph Formulation: Target the limitation that standard circuit analyses aggregate entire multi-head attention outputs into monolithic layer-to-layer connections, obscuring token-to-token information routing -> Mechanism formalizes the forward pass as a directed acyclic graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) where nodes \(\mathcal{V}\) correspond to intermediate token representations and edges \(\mathcal{E}\) explicitly represent pairwise information transport; each Multi-Head Attention (MHA) sub-layer expands into \(N_H \times n\) token-to-token attention edges and 1 residual edge per target token, while each MLP sub-layer contributes 1 non-linear transformation edge and 1 residual edge -> Effect yields a fully unraveled, token-level topological representation (comprising over 5 million edges for a 32-layer, 14B model on 100 tokens) that permits arbitrary, non-sequential skip-paths and surgical binary edge masking.
The masked state transformations at layer \(l\) for target token position \(i\) are explicitly unrolled as: $\(z_i^l = m_{i,\text{res}}^l \cdot h_i^l + \sum_{k=1}^{N_H} \sum_{j=1}^n m_{i,j}^{l,k} \cdot \phi_{l,k}(h_i^l, h_j^l)\)$ $\(h_i^{l+1} = z_i^l + m_{i,\text{mlp}}^l \cdot \text{mlp}_l(z_i^l)\)$ where \(m \in \{0, 1\}\) are binary decisions indicating edge inclusion in the subgraph \(\mathcal{E}_s\), and \(\phi_{l,k}(h_i^l, h_j^l)\) denotes the exact vector relocated from source token \(j\) to target token \(i\) by attention head \(k\).
2. Node-Normalized L1-Norm Edge Importance Scoring: Target the intractability of exhaustive combinatorial search and the numerical scale imbalance across distinct architectural components -> Mechanism evaluates edge necessity by computing the \(L_1\)-norm of each operation's update vector \(v_e\) and normalizing it locally against all competing incoming edges feeding into the same target node \(v\) -> Effect establishes an efficient, training-free, single-pass attribution proxy that reliably ranks edge utility without backward gradient passes, outperforming directional alignment and cosine similarity metrics across multiple model families.
For any directed edge \(e\) carrying vector \(v_e\) into target node \(v\), the node-normalized importance score is defined as: $\(I(e) = \frac{\|v_e\|_1}{\sum_{e' \in \text{in}(v)} \|v_{e'}\|_1}\)$ This local normalization ensures that edges converging on early-layer nodes are not systematically eclipsed by high-norm residual vectors in deeper layers, enabling balanced competition across diverse functional units.
3. Greedy Best-First Subgraph Traversal: Target the computational challenge of finding an optimal subgraph within massive graphs containing millions of interconnected edges -> Mechanism executes a reverse Best-First Search seeded at the final prediction node \(h_n^L\), maintaining a global max-priority queue ordered by importance scores \(I(e)\); at each iteration, it extracts the most salient candidate edge, adds it to the active trace \(\mathcal{E}_s\), and expands the search frontier by inserting all unvisited incoming edges connected to the source node of \(e\) until budget \(s\) is saturated -> Effect extracts topologically connected subgraphs spanning five orders of magnitude (\(s \in [10^{-5}, 0.8]\) across 26 log-spaced grid points) with minimal CPU overhead, guaranteeing structural paths directly linked to the final output token.
The priority queue guarantees that all included operations causally connect back to the target prediction node, preventing disjoint or dangling operations from wasting the budget.
4. Total Variation Faithfulness & Computational Density: Target the flaw of KL divergence being disproportionately dominated by noisy tail tokens and binary top-1 metrics failing to reflect distributional shifts -> Mechanism measures output preservation via the Total Variation (TV) distance \(\delta_{\text{TV}}(s) = \frac{1}{2} \sum_{v \in \mathcal{V}} |P(v) - \hat{P}_{\mathcal{T}_s}(v)|\), which reflects true absolute probability mass alignment, and computes a holistic scalar metric \(C\) by numerically integrating the Area Under the Curve (AUC) across the log-scale budget grid using the trapezoidal rule -> Effect establishes a standardized, instance-level quantitative metric of model computation density that reflects resilience to pruning and enables direct comparisons across architectures, entropy levels, and token frequencies.
The scalar computational density \(C\) is computed as: $\(C = \sum_{k=1}^K \frac{1}{2} (s_k - s_{k-1}) \cdot [\delta_{\text{TV}}(s_k) + \delta_{\text{TV}}(s_{k-1})]\)$ Low \(C\) values indicate highly sparse processing where minimal subgraphs replicate output distributions, whereas high \(C\) indicates dense, distributed processing requiring broad structural participation.
Benchmark & Evaluation Protocol¶
The empirical evaluation investigates 10 decoder-only LLMs spanning 7 major open-source families: OLMo-2 (7B, 13B), Qwen3-Base (8B, 14B), Qwen2.5 (7B, 14B), Llama-3.1 (8B), Mistral-v0.1 (7B), DeepSeek-LLM (7B), and Phi-4 (14B). The dataset consists of 5,000 carefully curated sequences from WikiText (averaging ~40 words, bounded by natural sentence boundaries and complete tokens). After excluding rare numerical or OOM anomalies, each model maintains between 4,250 and 5,000 valid evaluation instances. The analysis spans 26 relative trace size budgets from \(s = 10^{-5}\) to \(s = 0.8\), totaling over 1.3 million evaluated computational traces. Comparative baselines include a strong heuristic random traversal that explicitly prioritizes residual and MLP edges over attention edges, an \(L_2\)-norm scoring variant, target-normalized norms (\(normf\)), information flow routing proximity (\(ifr\)), and cosine similarity (\(cosim\)).
Key Experimental Results¶
Main Results: Output Reconstruction & Phase Transitions Across Architectures¶
Across all 10 evaluated language models, the relationship between trace budget \(s\) and reconstruction error \(\delta_{\text{TV}}\) exhibits a universal two-phase transition: an initial Construction Phase (\(s \in [10^{-4}, 10^{-2}]\)) characterized by steep error reduction, and an extended Refinement Phase (\(s > 10^{-2}\)) characterized by gradual, log-linear precision tuning. Within the construction phase, a highly stable Minimal Core emerges at \(s \approx 10^{-3}\) (0.1% of edges), which is causally sufficient to accurately reconstruct the top-1 prediction and top-1% of the probability mass.
The table below summarizes the core architectural parameters, training token volume, processed sample count, and empirical Total Variation reconstruction error at the minimal core (\(s = 10^{-3}\)), end of construction phase (\(s = 10^{-2}\)), and full model (\(s = 1.0\)) across all 10 LLMs:
| Model Name | Parameters | Training Tokens | Valid Instances | Minimal Core \(\delta_{\text{TV}}(10^{-3})\) | Construction End \(\delta_{\text{TV}}(10^{-2})\) | Full Model \(\delta_{\text{TV}}(1.0)\) |
|---|---|---|---|---|---|---|
| OLMo-2-1124-7B | 7.3B | 4.0T | 4921 | ~0.35 | ~0.16 | 0.00 |
| OLMo-2-1124-13B | 13.7B | 5.0T | 4975 | ~0.34 | ~0.15 | 0.00 |
| Qwen3-8B-Base | 8.2B | 36.0T | 4944 | ~0.32 | ~0.14 | 0.00 |
| Qwen3-14B-Base | 14.8B | 36.0T | 4959 | ~0.31 | ~0.13 | 0.00 |
| Qwen2.5-7B | 7.6B | 18.0T | 4954 | ~0.33 | ~0.15 | 0.00 |
| Qwen2.5-14B | 14.7B | 18.0T | 4275 | ~0.32 | ~0.14 | 0.00 |
| Llama-3.1-8B | 8.0B | 15.0T | 4953 | ~0.33 | ~0.15 | 0.00 |
| Mistral-7B-v0.1 | 7.3B | Undisclosed | 5000 | ~0.36 | ~0.17 | 0.00 |
| DeepSeek-LLM-7B | 7.0B | 2.0T | 4893 | ~0.35 | ~0.16 | 0.00 |
| Phi-4 | 14.0B | 9.8T | 4964 | ~0.30 | ~0.12 | 0.00 |
Ablation Study: Scoring Functions, Topological Alignment, and Input Correlates¶
To benchmark the efficacy of the node-normalized \(L_1\) heuristic, the authors compared it against alternative attribution functions. Furthermore, the correlation between computational density \(C\) and contextual properties (output entropy, token frequency, and language modeling loss) was systematically analyzed.
The table below reports relative performance across scoring strategies alongside Spearman rank correlation coefficients between density \(C\) and linguistic/model metrics (all reported correlations are statistically significant with \(p < 0.01\)):
| Evaluation Dimension / Setup | Metric / Target Quantity | Numerical Range | Summary Finding / Mean (\(\mu\)) |
|---|---|---|---|
| Scoring Ablation: \(L_1\)-norm (s-Trace) | Total Variation Error Curve | Best | Consistently achieves lowest error across all budgets |
| Scoring Ablation: \(L_2\)-norm | Total Variation Error Curve | Near-optimal | Performs closely to \(L_1\); slightly less resilient at ultra-low budgets |
| Scoring Ablation: Target-norm (\(normf\)) | Total Variation Error Curve | Moderate | Suffers from layer-scale imbalance without node-level normalization |
| Scoring Ablation: IFR Proximity (\(ifr\)) | Total Variation Error Curve | Sub-optimal | Less effective on generic generation compared to restricted tasks |
| Scoring Ablation: Cosine Similarity (\(cosim\)) | Total Variation Error Curve | Poor | Directional alignment neglects magnitude, selecting weak noisy edges |
| Scoring Ablation: Random Baseline | Total Variation Error Curve | Worst | Exhibits \(\delta_{\text{TV}} > 0.8\) when \(s < 10^{-2}\); sharp discontinuity |
| Cross-Model Density Agreement | Pairwise Spearman \(\rho\) of \(C\) | [0.26, 0.71] | \(\mu = 0.52 \pm 0.11\); highly consistent computational allocation across LLMs |
| Density vs. Output Entropy | Spearman \(\rho\) with Shannon Entropy | [0.04, 0.37] | \(\mu = 0.22\); uncertain predictions recruit broader sub-networks |
| Density vs. Token Frequency | Spearman \(\rho\) with Top-1 Word Frequency | [-0.45, -0.22] | Robust negative correlation; frequent tokens require less computation |
| Minimal Core Stability (Jaccard) | Pairwise component overlap at \(s=10^{-3}\) | Jaccard \(\approx 0.5\) | \(Z\)-score \(\approx 20\); minimal core components shared across instances |
Key Findings¶
- Two Distinct Computational Regimes: Every evaluated LLM exhibits an identical bifurcated trajectory. The Construction Phase (\(s \in [10^{-4}, 10^{-2}]\)) assembles an early-layer functional backbone with high marginal edge utility, reducing error dramatically. Beyond \(s = 10^{-2}\), after capturing 40%–60% of total probability mass, the trace enters the Refinement Phase where log-budget scales linearly with nucleus target \(k\), indicative of independent additive calibration paths.
- Architectural Composition Inversion: At the minimal core (\(s \approx 10^{-3}\)), edge allocation is remarkably balanced across structural primitives (~30% residual, ~20% MLP, ~50% attention), even though attention heads constitute >99% of edges in the full model. This demonstrates extreme structural sparsity in attention during core construction. Early and early-middle layers comprise over 80% of minimal core edges, whereas the subsequent refinement phase is driven predominantly by late-layer attention heads.
- Input Complexity Modulates Density: Computational density \(C\) is intrinsically tied to input difficulty rather than parameter scale. Traces correlate positively with output entropy (\(\mu = 0.22\)) and negatively with unigram token frequency (\(\rho \in [-0.45, -0.22]\)). Low-entropy and high-frequency tokens require only sparse shallow subgraphs, whereas rare words and uncertain predictions mandate extensive late-layer refinement.
Highlights & Insights¶
- Scalable Graph Attribution Bypasses Patching Bottlenecks: By replacing expensive contrastive activation patching with a single-pass, node-normalized magnitude heuristic, s-Trace scales mechanistic interpretability across 10 LLMs up to 14.8B parameters, mapping continuous density curves rather than discrete toy circuits.
- Debunking Hyper-Sparse Circuit Illusions: Relying on binary top-1 success metrics produces an illusion of extreme sparsity; recovering faithful full-distribution nuances requires engaging an extensive refinement network of late-layer attention heads, setting a concrete empirical lower bound (0.1% minimal core) for faithful circuit analysis.
- Representation Geometry Validates Magnitude Primacy: Centered Kernel Alignment (CKA) demonstrates that \(L_1\)-extracted subgraphs smoothly converge in hidden state geometry toward the full model across budgets, while baseline subgraphs exhibit fractured, abrupt transitions.
Limitations & Future Work¶
- Zero-Ablation Off-Manifold Risks: The evaluation relies on zero-ablating excluded edges, which can push intermediate activations off the natural data manifold. Although pre-softmax zeroing of attention edges confirmed primary findings, implementing scalable mean-ablation across millions of fine-grained edges remains an open technical challenge.
- Linguistic and Architectural Scope: The empirical investigation is currently confined to English WikiText and standard dense autoregressive Transformers, leaving Mixture-of-Experts (MoE) routing, multi-modal architectures, and non-Transformer architectures (such as state-space models) for future exploration.
- Translation to Dynamic Runtime Acceleration: While s-Trace provides profound offline analytical insights into computation density, operationalizing these findings into dynamic, input-adaptive early-exit or head-pruning kernels on modern hardware warrants dedicated systems research.
Related Work & Insights¶
- vs. Automated Circuit Discovery (e.g., ACDC / Edge Pruning): ACDC requires bespoke contrastive prompts and heavy iterative pruning per task; s-Trace operates bottom-up on natural text via single-pass activation scoring, capturing general language modeling distributions across 1.3 million traces.
- vs. Hierarchical Stages of Inference: Prior work inferred depth-wise functional stages from sequential layer cuts; s-Trace applies an unraveled graph perspective that confirms early-layer feature construction alongside non-sequential skip-connections, providing rigorous topological evidence for progressive prediction ensembling.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ Pioneering continuous tracing framework quantifying LLM computation density across full probability distributions.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluation across 10 diverse LLMs, 1.3M traces, multi-metric ablations, and geometric CKA validation.
- Writing Quality: ⭐⭐⭐⭐⭐ Highly rigorous formalization, coherent structural narrative, and precise empirical documentation.
- Value: ⭐⭐⭐⭐⭐ Bridges mechanistic interpretability and cognitive linguistic efficiency, offering valuable foundations for adaptive inference design.