Can Transformers Learn to Solve Problems Recursively?
This addresses the problem of understanding neural network failures in tasks relevant to software engineering and formal verification, but it is incremental as it focuses on analyzing existing limitations rather than proposing a new solution.
The paper investigates whether transformers can learn to emulate structurally recursive functions, which are key to tasks like program behavior emulation, and finds that by reconstructing the learned algorithms, they can predict 91% of failure cases for one function.
Neural networks have in recent years shown promise for helping software engineers write programs and even formally verify them. While semantic information plays a crucial part in these processes, it remains unclear to what degree popular neural architectures like transformers are capable of modeling that information. This paper examines the behavior of neural networks learning algorithms relevant to programs and formal verification proofs through the lens of mechanistic interpretability, focusing in particular on structural recursion. Structural recursion is at the heart of tasks on which symbolic tools currently outperform neural models, like inferring semantic relations between datatypes and emulating program behavior. We evaluate the ability of transformer models to learn to emulate the behavior of structurally recursive functions from input-output examples. Our evaluation includes empirical and conceptual analyses of the limitations and capabilities of transformer models in approximating these functions, as well as reconstructions of the ``shortcut" algorithms the model learns. By reconstructing these algorithms, we are able to correctly predict 91 percent of failure cases for one of the approximated functions. Our work provides a new foundation for understanding the behavior of neural networks that fail to solve the very tasks they are trained for.