🤖 machine learning

Synthesis and Verification of Transformer Programs (Technical Report)

This paper presents new algorithmic techniques for automatically verifying and learning C-RASP programs—language constructs that capture transformer expressiveness—by leveraging connections to Lustre model checking and local search, thereby enabling applications in transformer program optimization and constrained learning.

Original authors: Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hongjian Jiang, Matthew Hague, Philipp Rümmer, Anthony Widjaja Lin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, powerful robot (a "Transformer") that can read stories, write emails, and solve puzzles. This robot is incredibly good at its job, but it's also a bit of a "black box." You can see what it does, but you can't easily see how it thinks or prove that it will never make a specific mistake.

This paper introduces a new way to build a blueprint for these robots. Instead of trying to understand the messy, complex brain of the robot directly, the authors created a simpler, cleaner language called C-RASP. Think of C-RASP as a "simplified instruction manual" that the robot follows. It's simple enough that we can read it, understand it, and check it for errors, but it's powerful enough to describe exactly what the robot does.

Here is the breakdown of their two main achievements, explained with everyday analogies:

1. The "Safety Inspector" (Verification)

The Problem: You have a C-RASP instruction manual (a program), and you want to know: "Does this program always do the right thing? Does it ever accept a bad word or reject a good one?" Checking this manually is like trying to read a million-page book to find a single typo—it's nearly impossible and sometimes mathematically impossible to be 100% sure.

The Solution: The authors built a "Safety Inspector." They figured out how to translate these C-RASP instruction manuals into a different, very strict language called Lustre.

The Analogy: Imagine you have a complex recipe written in a messy, handwritten notebook (C-RASP). You can't easily check if the math is right. So, you translate that messy recipe into a rigid, computer-readable format (Lustre) that a super-fast robot (a "Model Checker") can read instantly.
The Result: This robot can instantly scan the recipe and say, "Yes, this is safe," or "No, here is the exact step where it goes wrong." The paper shows this works incredibly fast (in seconds) compared to training a new AI robot, which can take hours.

2. The "Auto-Editor" (Synthesis)

The Problem: Suppose you have a list of examples (e.g., "These are good sentences, these are bad ones") and you want to write a C-RASP instruction manual that fits them. You don't have the manual yet; you have to invent it from scratch.

The Solution: The authors created an "Auto-Editor" that uses a technique called Simulated Annealing.

The Analogy: Imagine you are trying to find the perfect combination of ingredients for a cake, but you can't taste it until you bake it.
1. You start with a random, messy recipe.
2. You bake it and see if it matches your examples.
3. If it's close, you make a tiny change (swap sugar for honey, add a pinch of salt).
4. If the new cake is better, you keep it. If it's worse, you might still keep it (just in case it leads to a better cake later), but you slowly stop taking risks as you get closer to the perfect recipe.
The Result: This process automatically writes a C-RASP program that fits your examples perfectly. It's like having a chef who can reverse-engineer a recipe just by tasting the final dish.

Why This Matters (According to the Paper)

The authors tested their tools on a variety of "puzzles" (like checking if parentheses are balanced or counting letters).

Speed: Their tools solved these puzzles in seconds.
Comparison: They noted that if you tried to train a standard AI (like GPT-2) to learn these same puzzles from scratch, it could take hours and still might not get it right.
Two Cool Uses:
1. Minimization: If you have a huge, bloated instruction manual, their tool can shrink it down to the smallest, simplest version that still works.
2. Constrained Learning: If you have a partial idea of what the program should do (a "specification"), their tool can fill in the blanks to make sure the final program fits both your examples and your rules.

In a nutshell: The paper gives us a way to turn the mysterious "black box" of AI into a clear, checkable, and editable instruction manual, allowing us to verify its safety and build new ones much faster than before.

Technical Summary: Synthesis and Verification of Transformer Programs

Problem Statement

Transformers, the foundational architecture of Large Language Models (LLMs), are notoriously difficult to analyze formally. While they are expressive and parallelizable, verifying their properties is undecidable, and their extension with Chain of Thoughts renders them Turing-complete. To address this, researchers have developed declarative languages like RASP (Restricted Access Sequence Processing Language) and its variant C-RASP (Counting RASP) to capture the behavior of transformers with precise semantics.

However, despite the theoretical connection between C-RASP and transformers, two critical gaps remain:

Verification: There is no automatic method to verify C-RASP programs. Checking if a C-RASP recognizes a trivial language is undecidable in the general case, and no practical tool exists to analyze properties like language equivalence or inclusion.
Synthesis: There is no known method to automatically learn or synthesize a C-RASP program from examples. Existing approaches rely on training neural networks and extracting rules, which often fail to produce implementable translations or require idealized assumptions.

This paper addresses these challenges by developing the first automatic techniques for both the verification and synthesis of C-RASP programs.

Methodology

1. Verification via Reduction to Lustre

The authors establish a formal connection between C-RASP and Lustre, a synchronous dataflow language used for embedded systems.

Translation: A C-RASP program is translated into a Lustre node. The translation maps C-RASP rules to Lustre variables (Boolean and integer streams).
- Counting Operators: The C-RASP counting operator #φ (counting positions where φ holds) is simulated in Lustre using auxiliary integer variables that accumulate values over an infinite stream.
- Finite vs. Infinite: Since C-RASP operates on finite words and Lustre on infinite streams, the input is encoded as an infinite stream with a specific end-of-stream marker (#) and an eternity marker (Ω).
Model Checking: Once translated, properties such as language equivalence, inclusion, and emptiness are verified using state-of-the-art model checkers (specifically Kind2) coupled with optimized SMT solvers (CVC5, Z3).
Complexity: The translation is polynomial in size, provided that the range parameters in the #rs,re operator are encoded in unary.

2. Synthesis via Simulated Annealing

The paper proposes a local search algorithm based on simulated annealing to synthesize C-RASP programs from positive and negative examples.

State Space: The search is constrained to a fixed "program shape" defined by the number of Boolean rules ( $N_b$ ), counting rules ( $N_c$ ), and a bound on numeric constants ( $K$ ).
Mutation Operators: The algorithm explores the state space by applying syntactic mutations to the current program. These include:
- Resampling: Replacing the right-hand side of a rule entirely.
- Micro-mutations: Local changes such as swapping logical connectives, toggling negation, or flipping comparison strictness.
- Constraints: Mutations are restricted to shallow syntax fragments (e.g., depth-2 for counting expressions) to bias the search toward simple, interpretable models.
Objective Function: The scoring function $E(P)$ prioritizes minimizing misclassifications ( $\lambda_{mis}$ ), followed by penalizing unreachable rules ( $\lambda_U$ ) and the total size of the abstract syntax tree ( $\lambda_S$ ).
Annealing Dynamics: The algorithm accepts worse solutions with a probability dependent on a cooling temperature schedule, allowing it to escape local optima.

3. Integrated Applications

The authors integrate these two components into a unified framework supporting two applications:

Transformer Program Minimization: Given a C-RASP program, the system synthesizes a structurally smaller, equivalent program. It alternates between local search and equivalence checking; counterexamples from the verifier guide the search.
Constrained Learning: Given a partial specification (a C-RASP program $P_{spec}$ ) and labeled examples, the system synthesizes a program that fits the examples and is included in the language of $P_{spec}$ ( $L(P) \subseteq L(P_{spec})$ ).

Key Contributions

First Automatic Verification Method: The paper presents the first technique to automatically verify C-RASP programs by reducing them to Lustre and utilizing model checking. This enables the verification of language equivalence, inclusion, and emptiness.
First Automatic Synthesis Method: The authors introduce a local search algorithm (simulated annealing) capable of synthesizing C-RASP programs directly from examples, bypassing the need for intermediate neural network training.
Implementation and Benchmarking: A unified Scala toolchain was implemented and evaluated against a suite of benchmarks from the literature, including regular, counting-based, and context-free-style languages.

Experimental Results

The authors evaluated their tool on a benchmark suite including languages like Dyck-1, Majority, and various Tomita automata.

Efficiency: The tool successfully synthesized correct C-RASP programs for most benchmarks within a 300-second timeout. For instance, synthesizing a program for Dyck-1 took approximately 3.92 seconds, while AnBnCn took 80.05 seconds.
Accuracy: The synthesis achieved high training and evaluation accuracy (often 100%) on languages within C-RASP's expressive power.
Comparison to Transformers: The paper notes that for certain benchmarks, training a transformer (e.g., GPT-2 via HuggingFace) to achieve the correct language could take several hours, whereas the C-RASP synthesis tool completed the task in seconds.
Limitations: As expected from expressivity theory, languages beyond C-RASP's power (e.g., Parity, Tomita 3, Tomita 5) could not be learned with high accuracy, with best training accuracies remaining below 80%.

Significance and Claims

The paper positions C-RASP not merely as a theoretical tool for understanding transformer expressivity, but as an interpretable surrogate model. By providing automatic methods for verification and synthesis, the authors argue that C-RASP can be analyzed using formal methods (FXAI), bridging the gap between the "black box" nature of neural networks and the need for explainability.

The significance lies in:

Decidability in Practice: While general verification is undecidable, the reduction to Lustre provides a practical, automated pathway for verifying specific, real-world transformer behaviors.
Direct Synthesis: The synthesis method offers a direct route to generating interpretable programs without the instability or opacity of training deep neural networks.
Optimization: The ability to minimize existing transformer programs and learn them under constraints demonstrates the utility of C-RASP for program refinement and safety-critical applications.

The authors conclude that their work lays the groundwork for formal analysis of transformers, with future directions including robustness verification and the incorporation of Chain of Thoughts (CoT) mechanisms.