Discovering Interpretable Algorithms by Decompiling Transformers to RASP

Paper: 2602.08857 Authors: Xinting Huang, Aleksandra Bakalova, Satwik Bhattamishra, William Merrill, Michael Hahn Categories: cs.CL, cs.LG

Abstract

This paper presents a general method to extract interpretable RASP (Restricted Access Sequence Processing) programs from trained Transformers. The approach re-parameterizes a Transformer as a RASP program and applies causal interventions to discover a small sufficient sub-program. When applied to small Transformers trained on algorithmic and formal language tasks, the method often recovers simple, interpretable RASP programs from length-generalizing transformers. This provides the most direct evidence to date that Transformers internally implement simple RASP-like programs.

Key Contributions

• Transformer-to-RASP decompilation: A systematic method to convert trained Transformer weights into interpretable RASP programs
• Causal intervention for simplification: Uses causal analysis to identify and retain only the essential sub-program
• Empirical validation: Successfully recovers known algorithms from Transformers trained on algorithmic tasks
• Length generalization connection: Links interpretable internal programs to the ability to generalize to longer sequences
• Mechanistic interpretability advance: Provides the strongest evidence yet for the RASP hypothesis of Transformer computation

Background: RASP and Transformer Computation

What is RASP?

RASP (Restricted Access Sequence Processing) is a programming language designed to express computations that Transformers can perform. It provides primitives that map directly to Transformer components:

• select: Creates attention patterns (maps to attention heads)
• aggregate: Combines values based on selection patterns (maps to attention-weighted aggregation)
• sequence operations: Element-wise transformations (maps to MLP layers)

A RASP program is a composition of these primitives that describes an algorithm operating on sequences.

The RASP Hypothesis

The RASP hypothesis posits that trained Transformers internally implement algorithms expressible as RASP programs. If true, this means Transformer computation is fundamentally interpretable — we just need the right tools to extract the underlying program.

Method

Step 1: Re-parameterization

The trained Transformer’s weights are re-parameterized into RASP-compatible form. Each attention head is expressed as a select operation defined by its query-key interaction pattern, and each MLP layer is expressed as element-wise soperations:

For an attention head with query matrix $W_Q$, key matrix $W_K$, and value matrix $W_V$:

$\text{select}(q, k) = \text{pattern derived from } W_Q^T W_K$ $\text{aggregate}(s, v) = \text{weighted sum using } W_V$

Step 2: Causal Interventions

The full RASP program derived from re-parameterization is typically large and redundant. Causal interventions identify which components are actually necessary:

1. Ablation: Systematically remove individual RASP operations and measure task performance
2. Activation patching: Replace activations at specific program points with baseline values
3. Sufficing: Verify that the retained sub-program alone reproduces the full model’s behavior

The goal is to find the minimal sufficient sub-program — the smallest set of RASP operations that fully explains the model’s computation.

Step 3: Interpretation

The resulting minimal RASP program is typically small enough for human inspection. Researchers can then:

• Verify it implements a known algorithm
• Discover novel algorithmic strategies
• Understand failure modes and generalization boundaries

Case Studies

Sorting

For Transformers trained on sorting tasks, the decompid RASP program reveals a comparison-based algorithm using attention heads as comparators — each head implements a specific comparison operation, and the composition implements a sorting network.

Parity

For parity computation, the extracted program shows an XOR-accumulation pattern: attention heads aggregate binary values, and the MLP computes the running XOR.

Formal Language Recognition

For tasks like Dyck language (balanced parentheses) recognition, the decompiled program reveals a stack-like counter mechanism implemented through attention patterns that track nesting depth.

Connection to Length Generalization

iking finding is that Transformers with interpretable RASP programs tend to length-generalize, while those without clean RASP decompositions fail on longer sequences. This suggests that:

• Length generalization requires learning a genuine algorithm (not pattern matching)
• RASP-expressible algorithms are inherently length-invariant
• The decompilation method can predict which models will generalize

Results

• Successfully extracts interpretable RASP programs from Transformers trained on multiple algorithmic tasks
• Recovered programs match known optimal algorithms in most cases
• Progr from length-generalizing models are simpler and more interpretable
• Provides the most direct evidence that Transformers implement RASP-like computations

Significance

1. Mechanistic interpretability milestone: Moves beyond correlation-based interpretability to actual algorithm extraction
2. RASP hypothesis validation: Strongest empirical support for the theoretical framework connecting Transformers and RASP
3. Practical debugging tool: Could help identify why models fail on specific inputs by examining the extracted algorithm
4. Length generalization insight: Connects interpretability to generalization, suggesting that “undersnd “generalizing” are linked
5. Foundation for scaling: While demonstrated on small Transformers, the methodology could potentially scale to larger models with hierarchical decomposition