Abstract
Learning-based systems are increasingly deployed across various domains, yet the complexity of traditional neural networks poses significant challenges for formal verification. Unlike conventional neural networks, learned Logic Gate Networks (LGNs) replace multiplications with Boolean logic gates, yielding a sparse, netlist-like architecture that is inherently more amenable to symbolic verification, while still delivering promising performance. In this paper, we introduce a SAT encoding for verifying global robustness and fairness in LGNs. We evaluate our method on five benchmark datasets, including a newly constructed 5-class variant, and find that LGNs are both verification-friendly and maintain strong predictive performance.
Introduction
As neural networks move into safety-critical areas like healthcare and autonomous systems, empirical performance is no longer a sufficient guarantee of reliability. We require formal verification—mathematical proof that a model behaves correctly under all possible conditions. This paper focuses on verifying 2-safety hyperproperties, specifically global robustness and global fairness.
Unlike local properties, which check stability around a single point, global properties examine the entire input space. For example, global fairness asks: "Is it true that for any two individuals who are identical except for a protected attribute like ethnicity, the model will always yield the same prediction?" For standard deep neural networks (DNNs), this is a computational nightmare due to continuous multiplications and non-linear activations, which force verifiers to use complex and often slow SMT or MILP solvers.
Methodology: Logic Gate Networks
We propose a shift from standard DNNs to Logic Gate Networks (LGNs). LGNs consist of a sparse "netlist" of two-input Boolean gates (e.g., NAND, XOR).
- Discrete Architecture: During training, gates are modeled using a differentiable relaxation, but at inference, the model is purely discrete. This allows the network to be translated directly into Conjunctive Normal Form (CNF), the native language of SAT solvers.
- Confidence-Based Verification: We define a confidence metric based on the number of activated output bits. By employing efficient sorting networks within the SAT framework, we can reason about the sum of bits without the overhead of traditional arithmetic encoding.
- SAT-Based Search: We use the Kissat SAT solver to perform a binary search over the confidence threshold $\kappa$, identifying the exact boundary where a model's predictions are guaranteed to be fair or robust.
Results and Discussion
Predictive Performance
We evaluated LGNs on five tabular benchmark datasets: German Credit, Adult, Law School, COMPAS, and a new 5-class variant of the Adult dataset. As shown in Figure 1, LGNs achieve test accuracies comparable to baselines in prior verification literature. Notably, accuracy remains stable or improves as the number of gates per layer increases, demonstrating that discretization does not significantly compromise model utility.
Verification Scalability
The primary advantage of the LGN approach is verification efficiency. Most individual verification queries are solved in under 10 seconds. Figure 5 (left) shows the total time required to find the optimal confidence threshold $\kappa$ via binary search. While the total time increases with layer size, it remains manageable, often completing in minutes where SMT-based methods for standard DNNs might take hours or time out.
Figure 5 (right) illustrates the stability of the determined $\kappa$ values across different network sizes. This suggests that the learned properties of the network are consistent even as the model's capacity grows. The ability to scale to the 5-class Adult dataset (Adult-5) further highlights the robustness of the SAT-based approach compared to mathematical approximations used for standard NNs, which often struggle beyond binary classification.
Conclusion
Logic Gate Networks transform the challenge of formal verification from a heavy optimization task into a logic puzzle that modern SAT solvers are exceptionally well-equipped to solve. By embracing discrete logic, we can provide rigorous global guarantees for fairness and robustness in seconds or minutes. Future work will focus on scaling these techniques to high-dimensional data like images and optimizing the search process through incremental SAT solving.
Summary updated