TL;DR
Verifying global robustness and fairness in traditional deep neural networks is notoriously difficult due to floating-point operations and non-linear activations. This paper proposes a pure Boolean SAT encoding to verify global 2-safety properties with confidence guarantees on Logic Gate Networks (LGNs)—models constructed entirely from discrete logic gates. The resulting system scales to multi-class classification and verifies models in seconds to minutes while matching the predictive accuracy of conventional networks.
What Problem Does This Paper Address?
Ensuring that machine learning models satisfy safety properties—such as fairness (identical treatment across demographic groups) and robustness (consistent predictions under bounded input perturbations)—is vital in high-stakes domains.
Most verification research focuses on local properties around specific test points. Verifying global properties (2-safety hyperproperties) requires proving that all possible pairs of inputs $(x, x')$ satisfy the safety condition across the entire input domain. For standard floating-point deep neural networks (DNNs), this requires SMT or MILP solvers, which suffer from extreme computational overhead. Furthermore, verifying confidence-calibrated decisions in multi-class settings usually requires approximating the softmax function, often introducing spurious counterexamples.
Methods
Instead of forcing continuous neural networks into constraint solvers, the authors verify differentiable Logic Gate Networks (LGNs). LGNs are trained using continuous relaxations over 16 primitive two-input Boolean logic gates and then "hardened" into discrete logic circuits.
The authors introduce an exact, end-to-end SAT formulation:
- Input Encoding: Categorical attributes are one-hot encoded; numerical features use thermometer encoding. Proximity constraints enforce that two inputs differ by at most $\epsilon$ bit-flips on non-sensitive features.
- Model Representation: Every gate in the network maps directly to standard Boolean clauses, completely bypassing floating-point arithmetic.
- Confidence and Multi-Class Logic: Class scores equal the sum of activated output bits. Instead of floating-point softmax, the authors use sorting networks to order output bits symbolically. This enables exact Boolean comparison of winning margins and confidence thresholds ($\text{score}(f(x)) / \sum \text{score} > \kappa$).
- Verification via SAT: To prove a property holds, the solver searches for a counterexample pair $(x, x')$ that satisfies input similarity and high confidence on $x$ but yields conflicting predictions ($f(x) \neq f(x')$). If the query is unsatisfiable (UNSAT), the network is proven globally safe.
- Verification Engine: Solved using the SAT solver Kissat, running a binary search over the confidence threshold $\kappa$ to identify the tightest safe confidence boundary.
Input Pair (x, x')
[Thermometer & One-Hot Encoded]
│
▼
┌───────────────────────────────┐
│ LGN Forward Passes │ (Directly encoded as CNF clauses)
│ net(x) and net(x') │
└──────────────┬────────────────┘
│
▼
┌───────────────────────────────┐
│ Sorting Networks │ (Counts active bits symbolically)
│ Rank classes & confidence │
└──────────────┬────────────────┘
│
▼
Property Negation Check:
Similarity(x, x') ∧ Conf(x) > κ ∧ f(x) ≠ f(x')
│
[ SAT Solver ]
/ \
UNSAT SAT
(Certified) (Counterexample)
Datasets
The approach was evaluated on five tabular datasets:
- German Credit: 1,000 samples, 16 features (12 categorical, 4 numeric), 2 classes.
- Adult (Census): 46,033 samples, 7 features (4 categorical, 3 numeric), 2 classes.
- Law School: 21,982 samples, 9 features (5 categorical, 4 numeric), 2 classes.
- COMPAS: 60,798 samples, 8 features (7 categorical, 1 numeric), 3 classes.
- Adult-5 Class (New Benchmark): 195,665 samples, 7 features, 5 classes. Constructed using the Folktables 2018 California census data by binning annual income into five brackets to test multi-class verification scalability.
Key Insights and Ideas
- Symbolic by Nature, Not by Approximation: Because LGNs are discrete netlists, verification requires no quantization relaxations, interval over-approximations, or floating-point abstractions.
- Exact Softmax-Free Confidence: Sorting networks allow the SAT solver to perform exact ratio comparisons without non-linear arithmetic, avoiding the spurious counterexamples common in prior SMT-based DNN verification.
- Output Layer is the Verification Bottleneck: Scaling the width of hidden layers adds very little solving time. In contrast, expanding the output layer drastically increases solving time because larger output blocks significantly increase the complexity of the sorting network.
- Non-Triviality Verification: Unlike previous work that only verified whether a threshold was technically safe, this framework verifies that there actually exists at least one valid input attaining that confidence level, ensuring properties are not vacuously satisfied.
Key Results
- Predictive Performance: LGNs achieve accuracies comparable to standard DNN baselines across all tasks (e.g., ~82.6%–83.4% on Adult).
- Verification Speed: Fixed-threshold queries on models with up to 300 gates per layer frequently solved in under 10 seconds.
- Global Fairness: Complete binary searches across confidence thresholds $\kappa$ converged within seconds to minutes for Adult, Adult-5, COMPAS, and Law School. Only German Credit timed out (at an 8-hour limit) for layer sizes exceeding 100 gates.
- Multi-Class Scalability: Successfully certified global robustness and fairness on the new 5-class Adult benchmark, a setting where previous SMT methods struggled due to compounding approximation errors.
Limitations and Future Work
- Feature Dimensionality Sensitivity: On datasets with numerous features (such as German Credit), verification scales poorly to larger layer sizes, triggering timeouts.
- Tabular Scope: Experiments are limited to small-to-medium tabular models; scaling to high-dimensional image classification networks remains open.
- Solver Optimization: Current experiments invoke independent SAT solver calls for each binary search step. Integrating incremental SAT solving could dramatically reduce total verification runtimes.
Summary updated