Hongjian Jiang: Synthesis and Verification of Transformer Programs

Item: Hongjian Jiang: Synthesis and Verification of Transformer Programs
Rating: 4
Author: PostSingularity Institute

by Hongjian Jiang

Formal & Physical Sciences Computing & Cybersecurity UMZSoftware Engineering UMZTSoftware testing and verification

🎙 Hongjian Jiang 👥 3K 📅 August 31, 2026 ⏱ 30 min 👁 1 📄 original study 🧭 2026-08-31

Available in: English (current) Français

Keywords

RASPLustremodel checkingprogram synthesisformal verification

Summary

This talk presents a method for synthesizing and verifying transformer programs, specifically RASP programs, using formal methods. The approach translates RASP programs into Lustre, a synchronous dataflow language, and uses the Kind 2 model checker to verify properties such as language inclusion, equivalence, and universality. For synthesis, a local search algorithm with simulated annealing is used to generate RASP programs from labeled examples, with the verifier providing counterexamples to guide the search. The work demonstrates that learning and verification can be performed on the RASP surrogate model rather than directly on transformers, which is more resource-efficient. Experiments on a dataset of formal language tasks show that the method can synthesize programs for many tasks, but fails on some, consistent with theoretical limitations of transformers. The talk also discusses applications like program minimization and constraint learning. The approach is a significant step towards bridging formal language theory and neural network interpretability.

150 words

Critical Evaluation

Value of the Information & Strength of the Argument

The value of the information is high, as it introduces a novel framework for formally verifying and synthesizing transformer programs, which is a significant contribution to the field of interpretability and reliability of neural networks. The argumentation is solid, building on established formal methods (Lustre, model checking) and theoretical results (RASP expressiveness). The presentation includes concrete examples and experimental results, supporting the claims. The approach is well-motivated by the need for efficient verification of transformer behavior, avoiding the cost of training and analyzing full models.

Scientific Rigor, Source Quality, Title Accuracy

The scientific rigor is high, with clear definitions and a formal translation from RASP to Lustre. The use of a model checker ensures sound verification. The sources are not explicitly cited in the talk, but the work is based on prior publications (e.g., RASP paper, Lustre formalization). The title accurately reflects the content, focusing on both synthesis and verification. The talk is well-structured and presents a complete pipeline, from synthesis to verification.

172 words

Title / Content Match

The title accurately reflects the content, which focuses on both synthesis and verification of transformer programs.

Quality & Reliability

8/10

The talk presents a formal framework for synthesizing and verifying transformer programs, grounded in established theory (RASP, Lustre, model checking). The approach is rigorous, with clear definitions and experimental validation, though the presentation is dense and assumes prior knowledge.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

RASP: A Language for Neural Network Program Synthesis — Defines the RASP language used in the talk.
Lustre: A declarative language for programming synchronous systems — The synchronous language used for translation.
Kind 2 model checker — Used for verifying Lustre programs.

Concurring Sources

RASP: A Language for Neural Network Program Synthesis — Provides the theoretical foundation for RASP and its expressiveness.
Lustre: A declarative language for programming synchronous systems — Defines the Lustre language used for translation.

Contribution & Novelties

The talk presents a novel approach to formally verify and synthesize transformer programs using RASP and Lustre. This bridges the gap between neural network interpretability and formal methods, enabling rigorous verification of transformer behavior on specific tasks. The synthesis algorithm, guided by a model checker, allows for automatic generation of correct programs, which is a significant advancement.

Pour aller plus loin :

RASP: A Language for Neural Network Program Synthesis — The original RASP paper, foundational to this work.
Lustre: A declarative language for programming synchronous systems — The Lustre language reference.
Kind 2: A Multi-Engine SMT-Based Model Checker — The model checker used for verification.

106 words

Radar Profile

The radar profile shows high scores in technical level and information quality, reflecting the formal and rigorous nature of the talk. The quantity of information is also high, but the fiabilite is slightly lower due to the lack of explicit citations and the complexity of the presentation.

Reliability 8/10