Discovering Interpretable Algorithms by Decompiling Transformers to RASP

AI summary

Authors: Xinting Huang, Aleksandra Bakalova, Satwik Bhattamishra, William Merrill, Michael Hahn Affiliations: Saarland Informatics Campus, Saarland University; University of Oxford; Allen Institute for AI arXiv: 2602.08857v2 [cs.LG] (published 2026-02-09; v2 dated 05 Jun 2026) · License: CC BY 4.0 Code: https://github.com/lacoco-lab/decompiling_transformers · Blog: https://lacoco-lab.github.io/home/decompiling_transformers

Overview

Research area: Mechanistic interpretability of Transformers, formal language theory, and the RASP family of symbolic programming languages. Technical level: Advanced — the paper assumes familiarity with Transformer internals (attention heads, layer norm, residual streams), RASP dialects, and causal intervention methods. Scope (one sentence): The paper introduces a pipeline that re-parameterizes a trained GPT-2-style Transformer as an exact RASP program and then causally prunes it down to a small, human-readable program, and validates this on small models trained on algorithmic and formal-language tasks.

What This Paper Is About

Theory has shown that Transformers can be simulated by short programs in the RASP family, and prior work conjectured that tasks with short RASP programs are exactly the ones Transformers length-generalize on. What was missing is evidence that trained models actually implement such programs. This paper closes that gap with a general decompilation method: translate a trained Transformer faithfully into a program in a new dialect called Decompiled RASP (D-RASP), then discover a minimal sufficient sub-program through causal interventions.

Key Contributions

1. D-RASP, a new RASP dialect. The authors define Decompiled RASP, whose primitives mirror Transformer computation (softmax-based aggregation over an unbounded number of positions, non-uniform attention) while exposing intermediate variables in interpretable token and position bases. They show a fragment of D-RASP under rounded semantics and rational parameters defines exactly the same functions as C-RASP (Theorem 2.1).
2. A faithfulness theorem (Theorem 3.2). Under the Linear Layer Norm Assumption (LLNA), any GPT-2-style Transformer satisfying it exactly can be translated into a D-RASP program with identical input–output behavior, obtainable explicitly from the model's parameters.
3. A causal simplification method. Because the faithful translation is exponentially large in model depth, the authors add a second stage that prunes causally irrelevant components and replaces learned matrices with library primitives, tracing a Pareto frontier of match accuracy vs. program length.
4. Empirical demonstration. On small GPT-2-style models trained on algorithmic problems and a battery of finite-state languages, the pipeline often recovers compact, interpretable programs from length-generalizing models and fails on non-length-generalizing ones.

Main Findings

• Length generalization predicts decompilability. Eight algorithmic tasks showed length generalization at least at some hyperparameters and could be decompiled; three did not length-generalize and could not be decompiled. For formal languages, 14 showed length generalization and decompilation succeeded on 9 of them; the 3 languages without length generalization all failed to decompile.
• Large programs collapse to tiny ones. For the most-frequent-character task, models trained with 1 layer / 4 heads and 4 layers / 4 heads had D-RASP translations of 56 lines and 16,201,616 lines respectively; causal pruning produced equivalent 3-line programs in both cases. In contrast, for non-length-generalizing models, pruning usually had only very limited success even when layer norm was kept intact.
• Recovered algorithms match known theory. Decompilation recovers histogram-based majority computation (the most-frequent-character program aggregates a token histogram that directly determines output logits), induction-head-based copying (Unique Copy), anti-induction heads for copying backwards, and bracket-counting-style behavior in bounded-depth Dyck languages — matching motifs hypothesized by prior RASP and interpretability work.
• Decompilation also handles non-primitive operations. The sort program could not be reduced to library primitives, but remained interpretable: a select favors the smallest keys larger than the query, and a per-position operation "hardens" the aggregated histogram into a one-hot vector, promoting EOS when no larger number exists.
• Special cases and coverage. For strictly local languages such as a⁺b⁺c⁺d⁺e⁺, no aggregation is needed and the program is just a projection from token. Bounded-depth Dyck models for D2, D4, and D12 were decompiled; the D3 model failed during layer norm linearization. The shortest program (4 lines) was found for D4.
• Only models satisfying LLNA were decompilable at scale. LLNA tended to hold for length-generalizable models (Tables 1 and 2), which are exactly the class for which prior work predicts short RASP programs should exist.
• Architecture, seed, and checkpoint sensitivity. The choice of architecture, random seed, and training checkpoint all affect length-generalization performance and therefore decompilability. Programs from different seeds or sparsity penalties can differ, but are often similar in practice.
• Faithfulness threshold. Decompilation is declared causally faithful when match accuracy is at least 90%, measured across all token positions receiving training signal.

Methodology in Plain English

The pipeline has two stages.

Stage 1 — Reparameterize. Treat the Transformer as a function that maps an input sequence to next-token logits. Using pos and token one-hot variables as inputs, each attention head is expressed as four select operations (one for each key/query interaction between position and token bases) feeding aggregate, and each MLP becomes an element_wise_op. Every path through the residual stream becomes a variable, so a layer's residual stream is recovered as a linear combination of variables with coefficient matrices taken from the model's weights. Final logits are produced by project statements plus a softmax or sigmoid. The residual stream in layer 1 is represented using 2 + 2H + 1 variables, where H is the number of heads, and the construction repeats layer by layer. This translation is exact only if layer norm can be replaced by a linear map — the LLNA.

Stage 2 — Simplify. Because the exact translation is exponentially large, the authors avoid unfolding it fully and instead prune in multiple stages. Causal pruning follows Li and Janson (2024): edges are pruned using trainable gates with an objective combining KL divergence between pruned and original models with a sparsity penalty. Selector inputs get replaced with 0 or key-only selectors when this has negligible causal effect; element_wise_op inputs are removed and absorbed into the transformation; final softmax inputs are replaced with a constant absorbed into the bias. Layer norms are re-fitted as linear operations. Per-position transformations are rewritten as sums of single-input operations re-fitted as MLPs, so they can be interpreted and pruned individually. Learned matrices are replaced with primitives from a library (identity, off-by-one shifted identity, hard-max, no-op) when this preserves faithfulness, or optimized to be sparse with integer values. When no primitive fits, the function is inspected directly: if it feeds the unembedding, it is transformed to have output dimension |Σ| to see which tokens are promoted; if it feeds select as keys or queries, the authors inspect which variable pairs produce high attention logits — an adaptation of LogitLens that accounts for paths other than the residual stream.

Experimental setup. Small GPT-2-style models with absolute positional encodings were trained on algorithmic problems (based on Huang et al. 2025 and Zhou et al. 2024) and finite-state languages from Bhattamishra et al. (2020). Algorithmic problems are framed as sequence prediction; formal languages are framed as per-step binary validity labels for each symbol via sigmoid on the logits, rather than language modeling. Models were trained at input lengths up to 50 and evaluated for length generalization at lengths 51–150, with random offsets so all position embeddings are trained. Decompilation ran on inputs up to length 150, and match accuracy was measured on random i.i.d. samples at length up to 150. Hyperparameters varied over numbers of layers and heads in {1, 2, 4} and model dimensions in {16, 64, 256}. For each task the best length-generalizing model was kept; per model, sparsity coefficients were varied to trace a Pareto frontier of match accuracy vs. program length, and the shortest program with match accuracy ≥ 0.9 was selected.

Why This Matters

Impact on research. The paper provides what its authors call the most direct evidence so far that Transformers internally implement simple RASP programs, converting a theoretical conjecture about length generalization into an empirically testable and partially verified claim. It also supplies the inverse of prior work that maps RASP programs to Transformers — recovering programs from trained models — and shows that generalizable models tend to be more interpretable than non-generalizable ones of similar size. The D-RASP/C-RASP correspondence theorem ties the extracted objects back into existing formal-language characterizations of Transformer expressivity, including log-precision Transformers and FO(M).

Potential applications (these follow from the method; the paper itself does not report deployed applications):

• Automated auditing of models: extracting a readable algorithm from a trained network to check whether it uses the mechanism a designer intended.
• Debugging generalization failures: identifying when a model relies on entangled, non-program-like mechanisms instead of a clean algorithm.
• Transferring verified symbolic algorithms into model implementations, or using extracted programs as specifications for rebuilding a model.
• Producing compact symbolic artifacts for regulated settings where a human-readable explanation of model behavior is required.

Industry relevance. The approach targets the practical question of whether a model's competence rests on an algorithm that will hold up out of distribution. The pipeline's diagnostic signal — decompilation succeeds for length-generalizers and fails otherwise — is directly useful for teams deciding whether a model can be trusted on inputs longer than those seen in training.

Future Directions

• Extending beyond GPT-2-style architectures. The method currently applies only to GPT-2-style models with absolute positional encodings; the authors note this choice because length-generalization theory is best developed for it, and defer generalizing to other positional encoding strategies.
• Handling LLNA violations. Models such as the D3 Dyck model failed at the layer norm linearization step, so a decompilation path that does not require LLNA is an open problem.
• Making the exact translation tractable. The guaranteed D-RASP program is exponential in model size, which is why multi-stage pruning is needed; better search over minimal sufficient sub-programs, including optimal program selection rather than a Pareto frontier, remains open.
• Characterizing when decompilation fails. Non-length-generalizing models resist decompilation, but the paper leaves open a precise account of which alternative mechanisms they use, and why seeds, checkpoints, and architecture choices change decompilability.

Target Audience

Interpretability researchers working on circuit discovery and mechanistic explanations of Transformer behavior; theoretical computer scientists studying the expressivity and length-generalization properties of Transformers and RASP dialects; and machine learning engineers who need to determine whether a trained model has learned a robust algorithm or a length-specific shortcut. Because the paper assumes knowledge of attention, layer norm, residual streams, and RASP syntax, beginners would need substantial background reading before the methodology sections are accessible.

Authors’ abstract

Recent work has shown that the computations of Transformers can be simulated in the RASP family of programming languages. These findings have enabled improved understanding of the expressive capacity and generalization abilities of Transformers. In particular, Transformers have been suggested to length-generalize exactly on problems that have simple RASP programs. However, it remains open whether trained models actually implement simple interpretable programs. In this paper, we present a general method to extract such programs from trained Transformers. The idea is to faithfully re-parameterize a Transformer as a RASP program and then apply causal interventions to discover a small sufficient sub-program. In experiments on small Transformers trained on algorithmic and formal language tasks, we show that our method often recovers simple and interpretable RASP programs from length-generalizing transformers. Our results provide the most direct evidence so far that Transformers internally implement simple RASP programs.