Abstract
We introduce "Truth Table net" (TTnet), a novel Deep Neural Network (DNN) architecture designed to provide excellent scalability/compactness trade-offs among DNNs, allowing in turn to tackle the DNN challenge of fast formal verification. TTnet is constructed using Learning Truth Table (LTT) filters, analogous to how a Deep Convolutional Neural Network (DCNN) is built upon convolutional filters. The differentiable LTT filters are unique by their dual form: they are both a neural network-based function and a small-sized truth table that can be computed within a practical time frame. This characteristic guarantees, by design and independently of the overall architecture, the ability to practically extract an efficient (in terms of the number of logical gates) and functionally equivalent Conjunctive Normal Form (CNF) Boolean logic gate implementation. This CNF circuit is even optimal when the LTT truth table's input bit size $n < 12$. In particular, TTnet architecture is the first differentiable DNN with a dual form compact logic gate representation that can scale to datasets larger than CIFAR-10: we achieve an accuracy of 41% on the ImageNet dataset while ensuring that each LTT filter truth table is fully computable within $2^{16}$ operations. We emphasize that TTnet is the first solution to the open problem of designing differentiable convolutional neural networks with an exact dual logic gate circuit representation, bridging the gap between symbolic AI and trainable DCNNs. Finally, we demonstrate TTnet's effectiveness in exact sound and complete formal verification, achieving robustness verification in 10ms vs 100s for traditional state-of-the-art DNN solvers.
Introduction
Deep Neural Networks (DNNs) are notoriously "black boxes." Their reliance on millions of floating-point parameters makes them difficult to trust in safety-critical applications. Formal verification—the mathematical proof that a network will behave correctly under specific constraints—is the solution, but it is currently an NP-hard nightmare for traditional DNNs. Existing attempts to solve this usually involve logic-based or binary neural networks, but these models face a "scalability-verifiability-compactness" trilemma: they often fail to scale beyond small datasets, proving properties about them remains computationally expensive, and converting them into hardware-efficient logic gates often results in massive, inefficient circuits.
Truth Table Net (TTnet) addresses this by drawing inspiration from cryptography to create a model that is differentiable during training but purely symbolic during inference.
Methods: The Learning Truth Table (LTT) Filter
The core innovation of TTnet is the Learning Truth Table (LTT) filter. Functioning similarly to a standard convolutional filter, the LTT filter is defined by three strict design constraints:
- Input Constraint: Each filter has a small input size ($n \le 16$ bits).
- Binarization: It uses binary inputs and outputs, maintaining real-valued weights only during training to allow for gradient descent.
- Non-linearity: It incorporates non-linear functions, such as ReLU, between binarization steps.
Because the input size is capped at 16 bits, the entire behavior of a filter can be pre-computed into a truth table ($2^{16} = 65,536$ entries) in less than a millisecond. This enables a Dual Form:
- During Training: It acts like a standard DCNN, using the Straight-Through Estimator (STE) to pass gradients through non-differentiable binary steps.
- After Training: Each filter is converted into its truth table, which is then optimized into a Conjunctive Normal Form (CNF)—a standard Boolean logic representation—using the Quine-McCluskey algorithm.
Experimental Evaluation
TTnet was evaluated across a diverse range of benchmarks, including tabular data (Adult, Breast Cancer), MNIST, CIFAR-10, and ImageNet. Scaling to ImageNet is a significant milestone, as previous differentiable logic gate networks typically failed to move beyond CIFAR-10.
Key Results
- ImageNet Scalability: TTnet achieved 41.6% top-1 accuracy on ImageNet. While lower than massive floating-point models, it is comparable to other binary networks like XnorNet and represents a first for logic-gate-equivalent models.
- Blazing Fast Verification: On MNIST and CIFAR-10, TTnet's robustness was verified in approximately 10 milliseconds. In contrast, $\alpha-\beta$-Crown, a leading DNN verifier, takes roughly 100 seconds. This $10,000\times$ speedup is possible because TTnet's equivalence to a Boolean circuit allows the use of generic, highly-optimized SAT solvers (like MiniSat).
- Compactness: On tabular data, TTnet achieved higher accuracy than competitors while using significantly fewer logical gates (e.g., 71 gates vs 640 for the Breast Cancer dataset).
Conclusion
TTnet bridges the gap between symbolic AI and trainable DCNNs. While an accuracy gap remains compared to modern ResNets, its scalability to ImageNet and unprecedented verification speeds make it a promising architecture for safety-critical applications. Future work will focus on closing the performance gap and developing complexity-aware loss functions to further shrink the resulting circuits.
Summary updated