Abstract
We propose a novel framework of program and invariant synthesis called neural network-guided synthesis. We first show that, by suitably designing and training neural networks, we can extract logical formulas over integers from the weights and biases of the trained neural networks. Based on the idea, we have implemented a tool to synthesize formulas from positive/negative examples and implication constraints, and obtained promising experimental results. We also discuss two applications of our synthesis method. One is the use of our tool for qualifier discovery in the framework of ICE-learning-based CHC solving, which can in turn be applied to program verification and inductive invariant synthesis. Another application is to a new program development framework called oracle-based programming, which is a neural-network-guided variation of Solar-Lezama's program synthesis by sketching.
Introduction
In formal methods, program synthesis and verification are often hindered by the difficulty of discovering "qualifiers"—the fundamental logical building blocks, such as linear inequalities (e.g., $x + y > 5$), that constitute loop invariants or program specifications. Traditional symbolic methods often rely on predefined templates or exhaustive enumeration, which struggle to scale as the complexity of the required logic increases. While machine learning offers a powerful alternative for pattern recognition, standard neural networks are typically "black boxes" that lack the interpretability required for formal verification. This paper introduces a "gray-box" approach that leverages the search capabilities of neural networks while maintaining the rigor of symbolic logic.
Methodology
The proposed framework, NeuGuS (Neural-Network-Guided Synthesis), treats the neural network as an intermediate representation that can be interrogated to reveal underlying logical structures. The process follows a multi-stage pipeline designed to bridge the gap between continuous optimization and discrete logic.
1. Neural Network Training
The system utilizes a four-layer neural network architecture. Unlike modern deep learning models that favor ReLU activations, NeuGuS employs the sigmoid activation function. The sigmoid's characteristic S-curve naturally mimics logical step functions, forcing hidden nodes to learn sharp boundaries that correspond to Boolean states (true/false). The network is trained on sets of positive and negative examples representing safe and unsafe program states.
2. Qualifier Extraction
After training, the network's weights and biases are analyzed. The first hidden layer effectively learns a set of linear inequalities. To convert these floating-point weights into interpretable integer coefficients, the authors apply mathematical techniques inspired by Diophantine approximation. For instance, a weight of $0.333$ might be mapped to the fraction $1/3$, allowing the extraction of clean, symbolic qualifiers.
3. Formula Synthesis
Once a pool of candidate qualifiers is extracted, a classical logic algorithm (such as Quine-McCluskey) is used to find the optimal Boolean combination (ANDs and ORs) that satisfies the training data. This hybrid approach ensures that the neural network performs the heavy lifting of boundary discovery, while the symbolic solver ensures the final output is a valid, interpretable formula.
Experimental Evaluation
The NeuGuS tool was evaluated across several challenging domains:
- Synthetic Arithmetic: The tool achieved a 100% success rate in recovering simple conjunctive formulas and over 90% for complex formulas involving nested AND/OR logic.
- CHC Benchmarks: In tests against 123 problems from the
code2invset and SyGuS 2018 benchmarks, NeuGuS successfully solved several Constrained Horn Clause (CHC) problems that state-of-the-art symbolic solvers like HoIce could not resolve. It was particularly effective at finding invariants involving three or more variables. - Non-Linear Synthesis: By introducing auxiliary inputs (e.g., $x^2$), the framework successfully synthesized quadratic inequalities, a task notoriously difficult for traditional synthesis engines.
Conclusion and Future Work
NeuGuS demonstrates that neural networks can serve as effective guides for formal synthesis by acting as "gray boxes." By combining the search power of gradient descent with the precision of symbolic logic, the framework overcomes significant bottlenecks in invariant discovery. While training costs are higher than simple enumeration for trivial problems, the method excels as a robust solution for complex, high-dimensional verification tasks. Future work will focus on extending these techniques to recursive data structures and program loops using Recurrent Neural Networks (RNNs).
Summary updated