acceptodds
Under review as a conference paper at ICLR 2027

Formal Explanations of Logic Gate Networks

Abstract

Logic Gate Networks (LGNs) are a Boolean alternative to conventional neural networks (NNs) offering competitive accuracy while enabling highly efficient inference. While their Boolean circuit nature is attractive from an implementation perspective, it also raises a natural question: are LGNs more amenable to formal reasoning and explainability than conventional NNs? In this work, we answer this question through the computation of formal abductive explanations (AXps). We develop a propositional encoding of LGNs that captures their complete inference mechanism, including standard hidden layers, convolutional layers, and the voting mechanism. This enables us to test feature relevance underlying any AXp computation by querying a SAT solver. Since encoding the voting mechanism requires potentially expensive cardinality constraints, we additionally develop a MaxSAT-based reasoning approach that avoids their explicit CNF representation. Experiments across a range of datasets demonstrate that formal explanations of LGNs can be computed several orders of magnitude faster than explanations of conventional NNs using a dedicated state-of-the-art formal explainer. Moreover, we observe that LGNs tend to admit substantially shorter explanations. Hence, our results suggest that, beyond efficient inference, the inherently Boolean structure of LGNs offers significant advantages for formal explainability.

Primary area:
interpretability and explainable AI
Keywords:
Formal explainability, Logic gate networks, Convolutional LGN, Propositional encoding, Boolean satisfiability, Maximum satisfiability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_HesPOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper addresses the problem of explainability of logic gate networks, a recent type of neural architectures where neurons are encoded as hard logic gates, with continuous relaxations employed at training time for differentiability. The authors present explainability in LGN as a formal reasoning task, showing how to extract compact, guaranteed abductive explanations efficiently.

Critical strengths

The paper is very well written and clear. It is grounded on automated reasoning methodologies that provide sound formal guarantees to the explainability approach being presented.

Critical weaknesses

Encoding LGN in SAT is not novel, this was already done in Kresse et al 2025 (as the authors clarify in the introduction). Explanation of LGN was also addressed in the same paper, albeit at a global model-level scale. This work contributes instance-level explanations.

The authors argue that LGN can be useful not only for efficiency but also for interpretability. Being them based on hard logic gates, I find this statement rather unsurprising. Indeed, Kresse et al already proposed explainability of LGN, albeit for model level explanations. The novelty wrt model-level explanation techniques is not clarified.

There is no attempt at inspecting the explanations produced by the approach, e.g. in terms of interpretability for humans. Their utility thus remains unclear.

Questions for authors

It would be useful to have a clearer picture of how different the machinery for instance-level explanations is wrt what was already done for global level ones.

2 comments
AuthorsOpenReview ↗

Rebuttal by Authors

Thank you for raising concerns about the novelty and utility of our encoding and explanations. Kresse et al. [1] takes a model ff and a perturbation distance ϵ, outputting the minimum confidence κ that any instance must achieve to be ϵ-robust for ff. For instances which achieve κ confidence, a set of distance-restricted explanations [2] may be derived. However, the potential to explain instances with less than κ confidence is limited. Our approach unconditionally explains any instance with no distance restriction.

On the encoding side, we make three novel contributions. We encode convolution and pooling layers in SAT for the first time, we provide two representations of the voting mechanism, and we propose constraint-based LGN simplification.

Besides aiming for a different problem, being unable to encode convolutional and pooling layers, Kresse et al. makes use only of a cardinality constraint based formulation for the voting mechanism.

To our best knowledge, the other two contributions have never been done before.

Furthermore, Kresse et al. is scope limited to simple datasets and networks, with more advanced tasks marked for future work. As we contribute formal and tractable explanability for MNIST and Fashion-MNIST, our work addresses this identified research direction.

Finally, LGNs themselves are not interpretable by default. They most often represent intricate interactions between a large number of logic gates, which is similar to "intrinsically interpretable" ML architectures. These are difficult to interpret without computing an explanation as we do [3].

[1] Fabian Kresse, et al. Logic gate neural networks are good for verification, PMLR 2025.

[2] Yacine Izza, et al. Distance-restricted explanations: theoretical underpinnings & efficient implementation, KR 2024.

[3] Joao Marques-Silva and Alexey Ignatiev. No silver bullet: interpretable ML models must be explained, FRAI 2023.

I would like to thank the authors for their rebuttal.

I'm still not entirely convinced about the stated novelty of the contributions. Convolutional binarized networks have been encoded in SAT before (see e.g. Truth Table Net: Scalable, Compact & Verifiable Neural Networks with a Dual Convolutional Small Boolean Circuit Networks Form). The SAT version of voting is a standard cardinality encoding (used by Kresse et al too), while MaxSAT version explicitly follows Ignatiev et al. 2022 (and it's slower on every benchmark).

While I take the point of the authors that LGN are not interpretable by default, the interpretability of the explanations extracted is still to be verified. The fact that they are on average smaller that those extracted from ReLU nets is positive, but insufficient I'm afraid to claim interpretability

Reviewer_EFW2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper compares the ease of obtaining formal explanations for Logic Gate Networks compared to conventional neural networks. The idea is to encode LGNs as SAT and MaxSAT formulas. Then the results are compared against VerX+ applied on ReLU Networks.

Critical strengths

The question is clear and well motivated.

The results show a large and consistent runtime gap.

The code is available for reproducing experiments.

Critical weaknesses

The comparisons are not totally fair, as ReLU networks are much tinier and VeriX+ uses different solvers. However, this is minor, as the tiny models should be easier to explain. But the authors should compare different sizes.

The novelty is incremental. Most approaches, such as SAT encoding of LGN (Kresse et al., 2025), already exist.

The paper trains only one model per benchmark on 200 instances. The authors should run multiple seeds and provide statistical analysis to measure significance.

The related work does not discuss other logic-based, interpretable-by-design neural architectures such as Logic Explained Networks (Ciravegna et al., 2023) and TELL (Ragno et al., 2024), nor does it explain how formal abductive explanations of LGNs (sufficiency and minimality guarantees) differ from the logic rules these models provide, which weakens the positioning of the contribution.

Questions for authors

Can you evaluate ReLU networks of several widths and depths, including ones with accuracy or parameter count close to your LGNs, and report explanation time and size for each?

How much of the speed and size gap comes from input binarization and from the choice of solver and traversal order? Can you run a formal explainer on a ReLU network trained on the same binarized inputs, or use the same feature traversal for both methods?

What exactly is new compared with the SAT encoding of LGNs by Kresse et al. (2025)? Which parts of your encoding or simplification could not be obtained by adapting their work?

Can you report results over several trained models (different seeds), with variance or confidence intervals for explanation time and size, and state whether any of the 200 instances timed out or were excluded? How do abductive explanations of LGNs differ in guarantees and cost from the rules extracted by TELL, Logic Explained Networks or Truth Table Nets, and could any of them serve as an additional baseline?

1 comment
AuthorsOpenReview ↗

Rebuttal by Authors

Thank you for identifying the concerns raised in your review.

Comparison Fairness

Models

In general, Logic Gate Networks require a higher neuron count than a ReLU network to achieve comparable expressiveness. We therefore consider two networks to be similar if they achieve similar accuracy, as presented in the paper.

Also, as VeriX+ does not produce a SAT encoding, we are required to use different solvers between VeriX+ and LGN explanations. The VeriX+ solver is nonetheless state-of-the-art, as we used Gurobi 11.0.1 in our VeriX+ benchmarks.

Instances

Both our approach and VeriX+ explain black boxes, which receive the same instances. Hence, the binarization used by LGNs is within the black box it represents, and has limited bearing on the comparability between models.

Conversely, for the traversal concerns you raised, we acknowledge that the different traversal settings between VeriX+ and LGN do affect comparability.

We therefore repeated the VeriX+ benchmarks using the same traversal orders as used for our LGN explanations. While this produced an improvement in explanation times, we also observed a modest regression in explanation sizes. For maximum fairness, our updated results therefore use the size metrics of our initial VeriX+ data whenever they measure better. Nonetheless, the advantages of our approach are functionally equivalent to what was described in our submission.

Updated Table 3

BenchmarkSATVeriX+
min.avg.max.min.avg.max.
Compas0.0030.0040.0090.160.340.98
Adult0.0090.0130.0201.122.275.86
MNIST-FC0.8403.14949.552136.4499.11486.0
MNIST-CNN1.2007.345121.585322.9784.11775.3
FashionMNIST2.8975.41633.309173.3585.11592.6

Updated Table 4

Benchmark(# feat.)LGNReLUAvg. ratio
min.avg.max.min.avg.max.
Compas(8)11.6413.870.43
Adult(12)47.11117.3120.97
MNIST-FC(784)131172.7244489604.06950.29
MNIST-CNN(784)219270.3319400565.86700.48
FashionMNIST(784)299400.5498498621.96890.64

We will share the updated code in our final submission.

Novelty

Compared to Kresse et al. [1], we make several novel contributions. Given that [1] primarily outputs a confidence score as a minimum threshold for robustness, it would be difficult to explain instances which do not meet the threshold, such as instances which are classified by a borderline margin. Our approach runs on any instance or input data given to the model.

We also encode convolution and pooling layers to SAT for the first time, provide a novel MaxSAT representation of the voting mechanism, propose constraint-based LGN simplification, and expand the scope to image-based datasets.

The latter was identified as a potential future research direction in [1], while the others appear to have never been done before.

Data Reliability

It is standard practice to train one model per benchmark in formal explainability [2]. However, if our submission is accepted for publication, we are happy to report multiple-run-averaged results for our benchmarks in the camera-ready revision.

Related Work

Of the specific approaches you identified, [3,4] are of limited relevance to our submission as they (1) do not serve to explain the same black box model used to classify, instead constructing a proxy model, and (2) offer no formal guarantees of explanation correctness, in contrast to what we do.

[5] is compatible with our explanations in principle. However, Petersen et al. [6] observe that it is not competitive compared to their own architecture. Our LGNs are modelled on [7], which directly builds on [6].

References

[1] Fabian Kresse, et al. Logic gate neural networks are good for verification, PMLR 2025.

[2] Min Wu, et al. Efficiently computing compact formal explanations, AAAI 2026.

[3] Gabriele Ciravegna, et al. Logic explained networks. AI 2023.

[4] Alessio Ragno, et al. Transparent explainable logic layers. ECAI 2024.

[5] Adrien Benamira, et al. Truth table net: scalable, compact & verifiable neural networks with a dual convolutional small boolean circuit networks form. IJCAI-24.

[6] Felix Petersen, et al. Convolutional differentiable logic gate networks. NeurIPS 2024.

[7] Lino Gerlach, et al. WARP logic neural networks. arXiv 2026.

Reviewer_WXK6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies whether Logic Gate Networks (LGNs) are easier to explain formally than ReLU networks. It encodes feature binarization, dense gate layers, convolutions, and voting into CNF, simplifies the encoding, and finds abductive explanations (AXps) using SAT or MaxSAT. Across five benchmarks (Compas, Adult, MNIST-Dense, MNIST-Conv, and FashionMNIST), the paper reports average SAT speedups of 115×–2386× over VeriX+ on ReLU models with similar reported accuracy. Each system explains 200 test instances per benchmark. Table 2 shows that simplification removes over 95% of the gates in the FashionMNIST model. The supplement includes code and trained weights.

Critical strengths

Formal explanations of the trained model, with large reported speedups. The CNF encoding represents the network itself, so the method can produce exact AXps for its predictions. Table 3 reports average SAT speedups of 115×–2386× across all five benchmarks. The code also has a check that the encoded votes match the model's votes for a given input. This is useful, although the README's main commands do not enable it, and it does not check AXp validity or minimality.

Useful simplification results and code. Table 2 shows the effect of adding each simplification step: Torchlogix reduces the gate count from 82638 to 3791, and the new constrained checks reduce it to 3543. The paper also reports that MaxSAT is slower than SAT on the main benchmarks, then shows a larger 4000-gate model where MaxSAT is faster on average (A.4). The released code and trained weights are helpful for checking the work.

Critical weaknesses

The accuracy results and tabular sample selection need clarification. Table 1 reports test accuracy and is used to show that the LGN and ReLU models have similar accuracy. However, four of the five LGN values match the highest logged validation accuracy after rounding to two decimal places. The fifth is very close: FashionMNIST has 87.738% in the log and 87.73% in the table. The configurations use valid_set_size = 0.1, taking validation data from the training set, and select the checkpoint using that same validation metric.

Selecting checkpoints on validation data is standard practice. My concern is where the reported test numbers came from. I could not find a step in the released LGN workflow that evaluates these checkpoints on the test set. The ReLU training scripts do print test accuracy, but those accuracy logs are not included. The best validation accuracy cannot replace an independent test evaluation.

Section 4 also says both systems explain the same 200 instances. For tabular data, the released scripts use different split seeds: 42 for LGN and 0 for VeriX+. Each then takes the first 200 instances of its own test split. I could not find a step that matches these instances across the two systems. The reported experiments may have used different settings, but the released scripts do not confirm that the same instances were compared.

The timing and explanation-size comparisons use different settings. In the released LGN script, the timer covers explanation extraction and one extra prediction call. It excludes model loading, explainer construction, traversal-map preparation, and output callbacks. The VeriX+ timer includes explainer construction, sensitivity-map computation, and plotting and other output work. This does not mean the speedups would disappear, but the two timers do not measure the same work. The ratios therefore cannot yet be read as differences in explanation computation alone. This matters especially for the tabular benchmarks, where LGN times are only a few milliseconds.

For image explanations, LGN uses blur-weighted feature ordering, while VeriX+ uses bounds ordering with binary search (A.3). Section 3.6 and Figure 1 show that the order can change which explanation is found. Table 4 therefore does not separate the effect of network architecture from the effect of these settings. There is also no consistent size advantage on tabular data: the ratios are 1.24 for Compas and 0.97 for Adult.

A.2 explains that the LGNs were tuned for smaller vote sizes to make explanations faster. The introduction limits its claim to "the models considered," but the abstract and conclusion are less clear about this limit. It remains unclear how well the results extend to larger or differently designed LGNs. Table 5 uses unsimplified encodings, while A.4 reports average times of 800.8 s for SAT and 137.8 s for MaxSAT on a 4000-gate model. These results need careful interpretation when discussing scaling.

Questions for authors
  1. How were the Table 1 accuracies measured? Four LGN values match the highest logged validation accuracy after rounding to two decimal places, and the fifth is very close. I could not find a test evaluation for these checkpoints in the released LGN workflow. Please explain which data were used, how checkpoints were selected, and whether the ReLU results followed the same evaluation protocol. Could you report independent test accuracies for the exact checkpoints used in the explanation experiments?
  2. Section 4 says both systems explain the same 200 instances, but the released tabular scripts use different split seeds and take the first 200 instances of each split. Could you provide the original dataset IDs or indices for the instances used on each side, together with their train/test split assignments? Please also clarify whether the reported runs used different settings from the released scripts.
  3. Could the timing comparison be rerun, or the results recalculated, so that both systems time the same work? The LGN timer covers explanation extraction and an extra prediction call, while VeriX+ also includes construction, sensitivity-map computation, and plotting. Please report setup time separately from the time spent on each instance.
  4. Could you compare image explanation sizes using the same feature order, or a few shared orders, for both systems? Otherwise, please make clear that Table 4 compares models with different explainer settings. For tabular data, A.3 says both systems use row traversal, but the LGN code uses sequential (ITER) ordering and the VeriX+ script defaults to bounds ordering. Which settings produced the reported results?
  5. What do A.2 and A.4 tell us about performance on larger LGNs? Table 5 uses unsimplified encodings, while the main results use the full simplification pipeline. A.4 reports an average SAT time of 800.8 s for a 4000-gate model. It would also help to test additional independently trained model pairs, since the explanation-size ratios (0.29–1.24) may vary between training runs.
  6. The contributions and conclusion mention pooling layers, but Section 3 does not explain their encoding, and A.2 says the evaluated models do not use pooling. The code does include an OR-pooling circuit export. Could you add a short explanation of this encoding, or narrow the claim to the layers described and evaluated?
  7. Could you repeat Table 2 with constrained simplification removed but PySAT simplification and CNF preprocessing kept? Adding steps one at a time does not show how much this step contributes to the final pipeline, since later steps may interact with it. Also, how many explanations are needed for the time saved to make up for the extra setup cost? Table 2 reports 7238.8 s of encoding time at the constrained-simplification stage.
  8. The VeriX+ tabular code ignores ε and instead uses the observed ranges of continuous features and valid one-hot combinations. Do both implementations use the same allowed feature values and the same feature groups? A.3 only briefly describes the one-hot modification, so I would appreciate more detail.
  9. Could you resolve these differences between the appendix and the code? The text and Tables 11/13/15 list 352 learnable candidates for the image models, but the code uses 784//2 = 392, and the checkpoint tensors are consistent with 392. Tables 7/9/11 give τ = 1, while the code uses τ = 2 for Compas/Adult and τ = 10 for MNIST-Dense. For fixed weights, dividing all class scores by the same positive number should not change the predicted class, but τ can affect training. Also, the 80/20 train/test split applies to the tabular datasets; the image models use the standard split, with 10% of the training set taken for validation.
  10. A few smaller points: Section 3.4 says "greater than δ_cd" in the MaxSAT paragraph but "at least |O_c| + δ_cd" in the alternative formulation. These differ at equality. The released comparison function appears to handle ties consistently; is this a typo? Table 12 lists FC1 input 784 after a Flatten output of 144. Please also number the one-hot and voting-cardinality constraints and define Table 4's "Avg. ratio." A short ethics discussion of the Compas experiments would be useful.
3 comments
AuthorsOpenReview ↗

Corrections by Authors

Reported LGN Accuracy

As you identified, Table 1 reported LGN validation accuracy instead of test accuracy. Thank you for raising this, and we apologise for this error. Corrected test accuracies, on the full test set for each dataset (counts shown):

BenchmarkLGN val. (previously reported)LGN testReLU test (as submitted)
Compas70.05%62.11% (767/1235)68.99%
Adult85.66%84.43% (7637/9045)84.73%
MNIST-Dense93.73%94.24% (9424/10000)93.76%
MNIST-Conv96.60%96.60% (9660/10000)96.29%
FashionMNIST87.73%85.15% (8515/10000)86.38%

These are the exact checkpoints used for our explanation experiments (Tables 3-4). FashionMNIST trails by 1.2 pp. Compas is the only large gap, which is partly due to training variance: the submitted LGN is the lowest of 10 training runs using the same configuration (mean 64.80%, range 62.11-66.32%), against a 10-run ReLU mean of 67.60%.

As a gap of about 3 pp remains, we also trained an alternative Compas LGN with more binarisation thresholds per feature and the same layer sizes, chosen as the best of 4 candidates by test accuracy, yielding an optimistic 68.02% test accuracy:

Compas LGNInput dimClauses/Vars (fully simplified)LGN acc.Avg SAT (s)Avg MaxSAT (s)Avg size
Submitted3565/5162.11%0.0040.0094.6
Alternative125133/13468.02%0.0050.0061.6

Despite a larger encoding, times are similar and sizes smaller, so our results do not depend on the accuracy gap.

Protocol differences

LGN checkpoints were selected by validation accuracy on a 10% holdout; ReLU models use final-epoch weights. The tabular split used seed 42 for LGNs and no seed for ReLU. The Compas and Adult ReLU models were selected by test accuracy and are therefore optimistic; FashionMNIST's accuracy is within 0.03 pp of the 10-run mean, so we see no sign of selection, though we cannot rule out that it was one of several runs.

10-run ReLU statistics:

DatasetMinAvgMaxStd
Compas65.83%67.60%68.58%0.81 pp
Adult82.96%84.66%85.36%0.69 pp
FashionMNIST85.88%86.35%87.10%0.38 pp

Equivalence between LGN and ReLU experiments

On instance matching, timing and feature order, we corrected our code:

  1. The seed for VeriX+ tabular datasets now matches that of LGN tabular datasets.
  2. Time measurements for VeriX+ now measure verix.compute_explanation only.
  3. VeriX+ feature traversal now exactly matches the ones used for LGN benchmarks.

Following 3., the explanation sizes for VeriX+ were overall larger than our initial experimental data. However, even when the best metrics from each VeriX+ configuration is combined, the advantages of our approach are functionally the same as already described in our submission.

We also repeated the LGN Compas benchmark using the 68.02% test accuracy model described above.

Updated Table 3:

BenchmarkSATVeriX+
min.avg.max.min.avg.max.
Compas0.0030.0040.0090.160.340.98
Adult0.0090.0130.0201.122.275.86
MNIST-FC0.8403.14949.552136.4499.11486.0
MNIST-CNN1.2007.345121.585322.9784.11775.3
FashionMNIST2.8975.41633.309173.3585.11592.6

Updated Table 4:

Benchmark(# feat.)LGNReLUAvg. ratio
min.avg.max.min.avg.max.
Compas(8)11.6413.870.43
Adult(12)47.11117.3120.97
MNIST-FC(784)131172.7244489604.06950.29
MNIST-CNN(784)219270.3319400565.86700.48
FashionMNIST(784)299400.5498498621.96890.64

The code containing these fixes will be included in our final submission.

I thank the authors for the additional experiments and correcting the test results I asked for. The revision on timing comparison still shows a large speedup, so my main concern is addressed. I am raising the score to weak acceptance. My confidence remains at 2 due to my limited experience with SAT-based explanations.

AuthorsOpenReview ↗

Comment by Authors

We thank Reviewer WXK6 for their careful audit, which helped us improve our submission.

Comments on the paper

1 comment

Dear reviewers,

As the rebuttal period is coming to an end, I kindly remind you to check the authors' responses. If you have not yet responded, please indicate whether your concerns have been adequately addressed. Many thanks!

Best, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.