Abstract
Modern safety-critical systems increasingly rely on neurosymbolic programs—architectures that embed neural networks within structured, human-written symbolic code. However, the discrete nature of symbolic logic, such as branching and loops, creates non-differentiable boundaries that prevent standard gradient-based optimization from ensuring safety. This paper presents Differentiable Symbolic Execution (DSE), a framework that transforms discrete program execution into a differentiable optimization problem. By combining probabilistic symbolic execution with a generalized REINFORCE estimator, DSE enables the training of neural components to satisfy worst-case safety constraints across entire input intervals.
1. Introduction
In domains like autonomous aviation and medical robotics, neural networks (NNs) are rarely deployed in isolation. Instead, they function as components within larger symbolic systems that handle high-level logic and safety checks. While NNs excel at pattern recognition, the surrounding symbolic code—containing if-else branches and discrete assertions—is inherently non-differentiable.
Existing safe learning frameworks, such as DIFFAI, are designed for isolated neural networks but struggle with the "discontinuity gap" of symbolic code. When a minor adjustment to NN parameters causes a program to switch execution paths, the resulting jump in behavior cannot be captured by traditional gradients. This paper addresses the challenge of training these hybrid systems to be provably safe under worst-case scenarios.
2. Differentiable Symbolic Execution (DSE)
The core contribution of this work is the Differentiable Symbolic Execution (DSE) framework, which smooths the discrete jumps of symbolic logic into a continuous landscape suitable for optimization.
2.1 Probabilistic Symbolic Execution
Rather than treating a branch condition (e.g., if x > 0) as a hard boolean choice, DSE treats the execution path probabilistically. The probability of following a specific path is defined by the "volume" of the input space that satisfies that path's constraints. This transformation ensures that the likelihood of taking a path varies continuously with respect to the neural network’s parameters, providing a meaningful gradient even across discrete branches.
2.2 Worst-Case Safety Loss
For each sampled execution path, DSE constructs a symbolic safety loss. This loss quantifies the distance between the current state and a safety violation (an assertion failure). By optimizing for this loss, the learner is forced to consider the most dangerous possible inputs within a given interval, rather than just the average case.
2.3 Generalized REINFORCE Estimator
To propagate gradients through the symbolic structure, the authors developed a generalized version of the REINFORCE algorithm. In standard Reinforcement Learning, REINFORCE uses a scalar reward; however, DSE requires backpropagating through a loss function that is itself a differentiable function of the parameters. This derivation allows the gradient to perform two simultaneous roles:
- Path Safety: Improving the safety of individual execution trajectories.
- Path Selection: Discouraging the system from entering paths that are fundamentally unsafe.
2.4 Lagrangian Optimization
The training objective is formulated as a constrained optimization problem: minimize the standard data loss subject to the constraint of zero safety violations. This is solved using a Lagrangian approach, modeled as a minimax game between a learner and a safety player.
3. Experimental Evaluation
The authors evaluated DSE against several baselines, including an extended version of DIFFAI (DIFFAI+), across a variety of benchmarks:
- Synthetic Microbenchmarks: Five tasks designed to test edge cases like parameterized branches and state merging.
- Control Tasks: Including a Thermostat regulator, Aircraft-Collision (AC) avoidance, and a Racetrack navigation task involving multi-agent coordination.
- Cartpole: A classic control problem modified with strict safety constraints on the pole's angular position.
4. Key Results
4.1 Provable Safety
In synthetic benchmarks, DSE consistently achieved a 1.0 provably safe portion, meaning 100% of the symbolic trajectories were guaranteed to be safe. In contrast, the state-of-the-art DIFFAI+ baseline often remained at 0.0 safety in the presence of complex symbolic branching.
4.2 Performance in Complex Scenarios
On high-dimensional tasks like Aircraft-Collision and Racetrack, DSE successfully identified parameters that were nearly 100% safe. Baselines failed to provide any safety guarantees in these multi-agent scenarios, as they could not navigate the discontinuous gradient landscape created by the symbolic logic.
4.3 Data Efficiency and Scalability
DSE demonstrated remarkable data efficiency, reaching high safety thresholds with as few as 200 training points. Furthermore, despite the computational overhead of symbolic execution, DSE often converged faster than baselines because it provided a clearer, more informative gradient signal, avoiding the "zero gradient" plateaus common in traditional abstract interpretation.
5. Discussion and Limitations
While DSE represents a significant step forward, several areas for improvement remain:
- State Abstraction: The current use of "box" (interval) domains is computationally efficient but can introduce over-approximation errors. Future iterations may utilize more precise geometric shapes like zonotopes.
- The Refinement Trade-off: There is a "Goldilocks" problem in symbolic execution: if the input space is partitioned too finely, the gradient signal may vanish as each state leads to only one unique path. Finding the optimal level of abstraction is a key open question.
- Gradient Variance: As a REINFORCE-based method, DSE can suffer from high gradient variance. Integrating variance reduction techniques from the RL literature could further stabilize training.
6. Conclusion
Differentiable Symbolic Execution provides a robust framework for bridging the gap between deep learning and formal verification. By smoothing symbolic logic into a differentiable form, DSE allows for the creation of neurosymbolic systems that are not only high-performing but also provably safe in the face of worst-case inputs.
Summary updated