acceptodds
Under review as a conference paper at ICLR 2027

Logical Neural Unit: Order-Statistic Neuron

Abstract

The core primitives of modern networks (inner products, attention, and gating) all aggregate by weighted sums, and a weighted sum responds to every input at once. So they are a poor fit for sparse logical structure: a target whose label is set by a few of many features through AND/OR/threshold logic. On such targets the relevant signal is diluted by the irrelevant ones, and the samples needed to recover it grow with the feature count, the regime where decision trees and rule learners still outperform deep networks on scientific data. But logic is not built from sums: AND and OR are extrema (min and max), each decided by a single coordinate, and with negation they form the complete basis for such targets. No dominant neural primitive computes an extremum; the networks that do implement logic directly (logic-gate and lookup-table nets) require binarized inputs and target hardware cost, and tree and rule learners are not differentiable. We introduce Logical Neural Units (LNUs)}: differentiable order-statistic neurons that compute soft AND (softmin) and OR (softmax) over , with a sharpness knob from averaging to exact logic. Their gradient concentrates on a single coordinate with sensitivity independent of ; we prove a PAC sample-complexity separation: LNU's sample requirement grows only logarithmically with the feature count, versus linearly for MLPs, Transformers, and prior differentiable-logic neurons ( versus ). Empirically, under one matched protocol, LNU reaches 92–100% on non-parity canonical Boolean formulas (neural baselines below 79% at ), loses 0.6pp under distractors (versus 21.8pp for an MLP), beats DWN by –pp on continuous logical tasks, and outperforms tree ensembles and MLPs on real-world few-shot scientific data (DNA splice sites: pp over XGBoost, pp over MLP). LNU is a drop-in structural inductive bias, useful when the target is Boolean-structured; we report where it is not.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
structural inductive bias, Boolean function learning, interpretability, sample-efficient learning

Reviews

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

This paper claims that previous ML literature lacks sample-efficient optimization methods that learn sparse logical rules that act on high-dimensional continuous data. As a motivation of this problem's relevance, it raises scientific and tabular regression and classification problems as an important instance where sparse functional structure that act on high-dimensional ambient input exist.

The paper assumes that these sparse functions often take a Boolean form as a low-degree disjunctive normal form (DNF), i.e. an OR aggregation of a few sparse AND-terms. The paper then claims that the low sample efficiency of previous optimizing sparse neural operators is because existing differentiable relaxations of sparse AND and OR operations have vanishing partial derivative norms as the input dimension grows. To substantiate this, it theoretically shows how the partial derivative of two previous AND relaxations vanishes with the input dimension DD.

To overcome this issue, it proposes to learn sparse logical AND through softmax and sparse logical OR through "softmin" (which is just softmax with sign-inverted weights), and aggregate these real-valued terms using a linear layer. It puts forward a theoretical result that the sample complexity to learn the correct sparse function with this optimization formulation would only grow logarithmically in the dimension of the input, while any inner-product based architecture (such as an MLP) would have a complexity that grows linearly with the input dimension.

Finally, it conduct a some experiments to substantiate this claim about superior sample complexity. It considers regression of several sparse boolean target functions, and compares the proposed architecture to two types of MLPs, a Transformer and XGBoost. On all of these benchmarks, XGBoost achieves the highest accuracy, closely followed by the author's tailored architecture and then followed by the MLPs and the transformer architecture with a wide margin. On other datasets that are not referenced, the latter architectures catch up and mostly close the margin.

All in all, I feel this paper is quite problematic, and I am sceptical about its value and faithfulness. I'll point out my concerns below.

Critical strengths

None

Critical weaknesses

1. The paper initially makes several claims that contradict my understanding of previous literature.

For example, it claims that only "two differentiable approximations of AND exist in the literature". This is outright wrong, there are several differentiable relaxations, and this paper even cites Petersen et al. (2022), who provides a comprehensive overview of them. What's worse, these two relaxations are hardly representative for the parametrizations that are used in current differentiable logic literature, which this paper again cites (e.g. Andronic et al. 2023, Andronic et al. 2024, Petersen et al. 2022).

Also, it does not mention recent advances in few-sample regression of tabular data. For example, TabPFN (Hollmann et al., 2023) advanced the state-of-the-art of sample efficiency in tabular datasets significantly.

1.1. The paper's claims about the benefits of their softmax AND-parametrization is questionable

Choosing softmax as a parametrization for sparse functions does not seem to benefit the magnitude of backpropagated gradients. While gradients in a linear layer WxWx are independently scaled by the corresponding weight wijw_{ij}, the gradient distribution of softmax will lead to imbalanced gradients where most inputs receive tiny fractions of the gradient norm. This is precisely the inverse of what the authors claim. softmax rescales and will shrink the gradient norm for most components, while a linear layer retains a dimension-independent partial derivative (i.e. the weight wijw_{ij}).

2. The experimental evaluation does not match the paper's initial motivation The paper initially address tabular and scientific problems, where sparse logical rules would frequently appear. Their evaluation in the main paper however restricts on synthetic boolean functions and unreferenced(!) datasets. What's more, it does not outperform the XGBoost baseline even on these synthetic examples that are tailored to meet the design of their own architecture.

Questions for authors
  • Where are the four "real-world datasets" in Table 1 from? Why have the authors chosen them and not some scientific or tabular datasets that they had initially put emphasis on?
  • Why do the authors regard their method as a valuable contribution if XGBoost outperforms it even on the synthetic boolean functions that this paper adresses? In particular, the weaker performance of the architecture on low-dimensional parity functions might highlight a concerning potential shortcoming of the softmax relaxation of a sparse AND.
  • In the light of XGBoost's superiority, why do the authors present their method as a particularly interpretable one? XGBoost remains more accurate and also more interpretable than any neural relaxation evaluated in this paper.
  • Parametrizing a sparse AND through softmax does not seem quite stable to converge to a sparse AND of multiple(!) inputs. softmax was rather introduced to relax the maximum, i.e. the selection of a single value from many. This is however insufficient to approximate k-DNF with some learnability guarantees. Why have the authors made that choice?
  • Why do the authors even keep the softmin parametrization for a soft OR when they eventually augment each input with its negation 1−x1-x and thus achieve the functional completeness with the softmax AND already?
3 comments
AuthorsOpenReview ↗

Part 1/2 (continued in the next comment)

We thank the reviewer for the detailed review and for the summary that the paper "theoretically shows" how the "partial derivative of two previous AND relaxations vanishes with the input dimension D". The reviewer's summary concern is being "sceptical about its value and faithfulness". The substantive points come first: the gradient and convergence questions in [W1.1, Q4], the datasets, the value of LNU next to XGBoost and interpretability in [W2, Q1, Q2, Q3], and the parity result in [Q2, parity]. The AND relaxations and TabPFN and the soft-OR unit are clarified together in [W1, Q5, clarification]. Results marked held-out use a protocol added in the revision: configuration and epoch are selected on a validation split, accuracy is reported on an untouched test split, and methods are compared over 10 seeds with paired Wilcoxon tests. In the revised PDF, revised and added text is shown in color.

[W1.1, Q4] Does the softmax AND help the gradients, and why use it for a multi-input AND? The paper's AND is the softmin, the minimum of the products of weight and input, and its imbalance is intended: it concentrates the gradient on the coordinate whose product is smallest. The per-coordinate derivative of a linear layer is its weight, as the reviewer notes, and does not shrink with DD; what shrinks is that coordinate's share of the output gradient, which dilutes as O(1/D)O(1/\sqrt{D}) because the layer sums over DD coordinates (Proposition 2). Under the softmin the share of the coordinate that sets the minimum stays order 1 (revised Proposition 3). Table R1 measures this share directly.

Table R1. Share of the output gradient carried by the most relevant input coordinate at initialization (β=10\beta=10, 400 random draws; revised Appendix J.25).

D201005005,000
inner-product layer0.140.0340.0080.001
LNU0.870.860.830.78

This concentration does not make the unit a single-input selector. The minimum is low whenever any one of its selected literals is low, so the unit computes a k-way AND over all of them, not the choice of a single value. On convergence, Theorem 4 is a sample-complexity result, not an SGD proof, and the submission shows convergence empirically: across 120 runs, recovery of the true multi-input support and accuracy correlate at 0.91 (Appendix J.1).

[W2, Q1, Q2, Q3] Do the datasets match the motivation, and why LNU if XGBoost is more accurate and interpretable? The real-world evaluation is on the tabular and scientific data the motivation names: the four datasets are referenced UCI benchmarks chosen for their logical target structure and cited in the Table 1 caption (Splice: Noordewier 1991, Section 5.2); all four are tabular, and Splice (DNA splice-junction recognition) is a scientific task. On these sets LNU's value does not rest on beating XGBoost, because it is a layer evaluated against the inner-product or FFN unit it replaces. XGBoost is a standalone learner: it wins the clean synthetic formulas (Table 1), and on the real-world sets held-out results put it ahead or tied on three of four (see the uKRJ reply, [W6, W8]). Against the unit it replaces, the MLP, LNU leads significantly on three of the same four sets (p≤.014p \le .014). For the same reason, its interpretability is of a different kind: LNU extracts an exact Boolean formula at β→∞\beta \to \infty from a layer inside a trained network, when its learned weights satisfy the dominance condition of Observation 4, which is a different capability from a post-hoc explanation of a standalone tree, not a claim to be more interpretable than one.

[Q2, parity] Does the weaker parity result show a flaw in the softmax relaxation? The weaker result on low-dimensional parity reflects training a single layer, not the soft-AND relaxation. One layer represents XOR, but parity gives no single literal a correlation with the label, so it is learned only partly, and only at small DD, and a second layer makes it learnable at low DD (see the TZ2v reply, [upper bound, XOR]).

[W1, Q5, clarification] Do only two AND relaxations exist, and what about TabPFN and soft-OR? There are many differentiable relaxations of AND; the two the submission names are the D-dimensional soft-AND aggregators it compares against, NLN and LNN, while the logic-gate and LUT family (Petersen 2022; Andronic 2023) uses small-fan-in gates, a different primitive, as Section 2 states. The revised PDF rewrites that sentence to say that many relaxations exist, including those gates, and cites TabPFN (Hollmann 2023) with tree ensembles as strong learners on tabular data (revised Section 1); LNU is a layer, compared against the unit it replaces. Soft-OR is not needed for completeness, since with complement augmentation soft-AND alone is functionally complete by De Morgan (Section 3.2); the ablation in Appendix E keeps it because AND+OR scores highest on the mixed MAJ target, though all three variants are within seed noise.

I thank the authors for some clarifications on the intent and meaning behind their statements.

Still, my assessment is unchanged. I do not recommend this paper for publication. The paper is still hardly readable for a human and its value is questionable.

I encourage the authors to present and evaluate their work more consistently, clearly and rigorously.

Reviewer_uKRJOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces Logical Neural Units (LNUs). This neuron computes the softmin (AND) and the softmax(OR) over the input (x) augumented with its negations (1-x). Traditional neural nets use weighted sums over the input(x), and struggle with learning sparse logical targets. Whereas, LNUs is able to learn from far fewer samples.

The paper makes the following contributions: - It presents LNU, as a differentiable unit, which also works with continuous inputs, and usable as a drop-in layer. This contrasts with other methods from the literature, which need binary inputs or are non-differentiable. - It argues that the LNU gradient concentrates on the single input that determines the min or max, with a strength that does not shrink as the number of features grows. - A sparse LNU can learn a k-term logical formula from a number of examples that grows in log(feature count), which is an improvement over litrature that grows linearly.

Critical strengths
  • The idea is well motivated. The intuition that logical AND/OR are extrema, not sums, is clear and compelling.
    • With many irrelevant features and few samples, the LNU learns sparse logical rules almost perfectly while standard networks fail.
    • Accuracy barely changes when thousands of irrelevant features are added, indicating robustness to wards irrelevant features.
    • Unlike logic-gate and lookup-table networks, it does not require binarization.
Critical weaknesses
  • The text is difficult to follow, and can be written better.
    • Several acronyms are never defined, including paper-specific ones such as DWN, MAJ, UAT, JSC, NLI, GBT and OWA. Other common acronyms like MLP, should also be defined.
    • Inconsistancy in several places across the text. The same configuration is reported with different results in different tables (e.g., LNU on DNF at D=200, N=100: 92.8% in Table 1, 96.0% in Table 17).
    • Several statements contradict each other, like Holm-significant formulas (19/30 in Sec. 5.1 vs 13/30 in J.8)
    • The MLP baseline changes between experiments (1 hidden layer in Sec. 5, 3 layers in Table 14) without explanation.
    • Some results are not explained. Transformers scores 37.3% on Splice (Table 1), 10.9% on Splice padded to D=5,000 (Table 2). These are extremely low compared to other methods, and should have been addressed.
    • Statistical significance is not tested for most claims. On the real-world datasets, the paper states that "LNU wins on all four", but the margins over XGBoost on Mushroom (+0.6pp), Phishing (+0.8pp) and Chess (+1.5pp) are within about one standard deviation (Table 1), and no test is reported. Several tables report no standard deviation at all for some methods (Tables 20 and 22).
    • The abstract claims a stronger result than the paper proves, stating the paper proves that MLPs, Transformers and earlier logic neurons need far more training examples than LNU. But in Sec. 4.2 states otherwise ("We do not prove it for multi-layer ReLU networks").
    • The reported results are chosen on the same data used for evaluation. For each run, the paper reports the best accuracy over all training epochs (Sec. 5 Setup), measured on the 500 held-out samples for synthetic tasks and on the "standard test splits" for real-world datasets. A separate validation set should be used to pick the epoch, with the final number reported on an untouched test set.
Questions for authors
2 comments
AuthorsOpenReview ↗

Part 1/2 (continued in the next comment)

We thank the reviewer for the constructive feedback and for acknowledging the strengths: the intuition that "logical AND/OR are extrema, not sums" (Strength 1), learning sparse rules "while standard networks fail" (Strength 2), and that "it does not require binarization" (Strength 4), along with its use as a "drop-in layer" (summary). The substantive points come first: the held-out protocol the reviewer describes is added, with paired tests and mean ±\pm std, in [W6, W8], and the abstract is rephrased to the proven claim in [W7]. The differing values, Holm counts and MLP depth are explained in [W2, W3, W4], the Transformer scores in [W5], and the acronyms in [W1, clarification]. In the revised PDF, revised and added text is shown in color.

[W6, W8] Are the results selected on evaluation data, and are they significant? In the added held-out protocol, configuration and epoch are selected on a validation split, accuracy is reported on an untouched test split, and each of 10 seeds draws its own random split. The main-text tables keep their submitted-protocol values, labeled as such in their captions, and the held-out results are collected in revised Appendix J.25. Of the XGBoost margins the reviewer flags as within one standard deviation, Mushroom and Chess now test within noise and LNU is ahead on Phishing (+1.2, p=.004p=.004), while XGBoost is ahead on Splice (-2.7, p=.04p=.04), and revised Section 5.2 states this held-out comparison in place of "LNU wins on all four" (see also the QjvL reply, [W2, Q1, Q2, Q3]). Against the MLP, whose unit LNU replaces, paired Wilcoxon tests show LNU's lead (Table R1) significant on Splice, Chess and Phishing (p≤.014p \le .014) and within noise on Mushroom (+0.4).

Table R1. Real-world held-out results, N=100N=100, 10 seeds, accuracy % (mean ±\pm std); p: paired Wilcoxon, LNU vs the baseline; ns: p > .05 (revised Table 28).

DatasetLNUMLPpXGBoostp
Splice88.0 ±\pm 2.978.5 ±\pm 1.7.00290.7 ±\pm 1.4.04
Chess91.7 ±\pm 1.483.5 ±\pm 2.5.00292.3 ±\pm 1.4ns
Mushroom95.6 ±\pm 1.695.2 ±\pm 1.4ns96.4 ±\pm 1.4ns
Phishing91.3 ±\pm 0.989.7 ±\pm 1.4.01490.1 ±\pm 0.7.004

The tables the reviewer names without standard deviations are now covered with mean ±\pm std: the Table 22 configurations, re-run under the held-out setting, show LNU's lead over the MLP persisting as NN grows (Splice +4.2, +9.5 and +11.2pp at N=50N=50, 100 and 200; revised Table 23), and Table 20's comparison is covered by revised Tables 23 and 28. Two further held-out checks show the lead is not an artifact of one setting (revised Appendix J.25): under a random search of 60 configurations for LNU and 64 for the MLP (5 seeds), LNU still leads (Splice 89.3 vs 80.6, Chess 92.8 vs 88.9), and over 20 repeated random splits it beats the MLP on Splice in 20/20 splits (87.7 vs 78.5) and on Chess in 18/20 (91.4 vs 86.3).

[W7] Does the abstract claim more than the paper proves? The paper proves a separation only against worst-case empirical risk minimization over the unconstrained linear-threshold class (revised Section 4.2), and the revised abstract states it: a PAC sample complexity separation for a sparse hypothesis class, learning a kk-term DNF from a number of samples logarithmic in DD versus Ω(D)\Omega(D) for worst-case ERM over unconstrained linear thresholds. Section 4.2 already states "We do not prove it for multi-layer ReLU networks", and the extension to MLPs and Transformers is shown empirically, not proven (see also the YLPM reply, [W3]).

[W2, W3, W4] Why do values, Holm counts and the MLP baseline differ across the paper? The values differ because the tables come from separate runs. Table 17 is a separate run from Table 1, with per-run learning-rate selection, as its revised caption states, and revised Appendix J.25 states that every appendix table re-running a Table 1 configuration is a separate run with its own seeds and learning-rate selection; for DNF(2-term) at D=200D=200 the revised PDF gives the held-out value, 83.1 with β\beta fixed at 10, which replaces both 92.8 and 96.0 in the final version. The two Holm counts measure different things: 19/30 formulas are significant at α=0.05\alpha=0.05 per formula, and 13/30 remain significant after Holm correction across the 30 formulas, and revised Section 5.1 and Appendix J.8 state both with these labels. The MLP depth changes because the continuous-input Table 14 uses a wide three-hidden-layer MLP as a capacity control, as its revised caption states, while the main Boolean tables use a one-hidden-layer MLP.

[W5] Can the Transformer perform better on Splice? It can: reading one token per input feature, in the held-out setting all methods share (revised Appendix J.25), it reaches 83.4% on Splice, replacing the 37.3%, and the 10.9% cell at D=5,000D=5{,}000 is not re-measured, as the held-out runs stop at D=1,000D=1{,}000 (revised Appendix N).

[W1, clarification] Are the acronyms defined, and is the text easier to follow? The revised PDF defines each acronym the reviewer lists at first use (MLP multilayer perceptron, DWN differentiable weightless network, MAJ majority, UAT universal approximation theorem, JSC jet substructure classification, NLI natural language inference, GBT gradient-boosted trees, OWA ordered weighted averaging), and it opens the appendix with an index of each section, its content and the main-text part it supports.

Reviewer_YLPMOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes Logical Neural Units (LNUs), a differentiable primitive for learning logic operators. The main contribution is that the authors reveal the better sample efficiency of LNUs than inner-product-based primitives (e.g., attention) for learning sparse logic structures, partly theoretically, partly experimentally. Theoretically, the authors prove that LNUs have better sample efficiency than linear threshold models. Empirically, the authors justify that LNUs have better sample efficiency than MLPs, Transformers, etc.

Critical strengths

None

Critical weaknesses

This manuscript overclaims in the following aspects.

  • The first sentence of the Introduction "Modern networks aggregate by weighted sums; logic does not." is contradictory to the core design of LNU (Eq. 1), which is also a weighted sum.
  • Line 21: "Rule learners are not differentiable" is wrong. Many works target differentiable rule learning. See below for non-exhaustive example references.
  • Line 25-28: "We prove a PAC sample-complexity separation: LNU's sample requirement grows only logarithmically with the feature count, versus linearly for MLPs Transformers, and prior differentiable-logic neurons" However, Theorem 4 only shows the complexity for linear threshold models, and the complexity for deep MLPs and Transformers is missing. This work analyzes the complexity for MLPs and Transformers only by empirical results, not theoretical results.
  • Line 24-25: "Their gradient concentrates on a single coordinate with sensitivity independent of DD" However, in Proposition 3, the sensitivity depends on β\beta and, on Line 251, β\beta seems dependent on DD.

[1] Scalable Rule-Based Representation Learning for Interpretable Classification. NeurIPS 2021.

[2] Learning Explanatory Rules from Noisy Data. Journal of Artificial Intelligence Research 61 (2018).

[3] Neuro-Symbolic Hierarchical Rule Induction. ICML 2022.

[4] DIFFERENTIABLE RULE INDUCTION FROM RAW SEQUENCE INPUTS. ICLR 2025.

Questions for authors

I would be open-minded if I made mistakes in Critical Weaknesses.

1 comment

We thank the reviewer for the constructive feedback and for the summary that LNUs show "better sample efficiency" than "inner product-based primitives", shown "partly theoretically, partly experimentally". The reviewer's main concern is that "This manuscript overclaims". The substantive points come first: what Theorem 4 covers in [W3] and the sensitivity in [W4]. The first sentence of the Introduction and the rule-learner sentence are clarified together in [W1, W2, clarification]. In the revised PDF, revised and added text is shown in color.

[W3] Does the abstract claim a proof for MLPs and Transformers? The revised abstract claims the proof only for a sparse hypothesis class, a kk-term DNF learned from a number of samples logarithmic in DD versus Ω(D)\Omega(D) for worst-case ERM over unconstrained linear thresholds, and states: "For multilayer perceptrons (MLPs) and Transformers we show the gap empirically". This matches Theorem 4's scope: its lower bound is for worst-case empirical risk minimization over the unconstrained linear-threshold class (revised Section 4.2), and as Section 4.2 states, "We do not prove it for multi-layer ReLU networks". Under a held-out protocol added in the revision (configuration and epoch selected on a validation split, accuracy on an untouched test split, 10 seeds), LNU's lead over the MLP on the four non-parity canonical formulas is +4.1 to +15.8pp at D=20D=20 and widens to +17.0 to +34.6pp from D=50D=50 to D=200D=200, every cell p≤.008p \le .008 by paired Wilcoxon test (revised Appendix J.25).

[W4] Does the sensitivity depend on β\beta, and β\beta on DD (submitted line 251)? The leading term depends on neither: at the coordinate that sets the minimum it is w/rw/r, where rr is the number of tied minima (r=1r=1 when a failed literal sets it), independent of β\beta and DD (revised Proposition 3), and β\beta is a hyperparameter set per experiment, not a function of DD (default 10). The dependence the reviewer points to is in the correction term, which carries n=2Dn=2D, so the Θ(∣w∣)\Theta(|w|) bound needs β≥log⁡(n)/g\beta \ge \log(n)/g: at β=10\beta=10, for a unit with one failed literal, the derivative is (1+ε)w(1+\varepsilon)w with ε\varepsilon rising from 0.02 at D=20D=20 to 0.68 at D=1,000D=1{,}000 and 1.8 at D=5,000D=5{,}000, so it stays of order ∣w∣|w|, within a factor of 3 up to DD of about 11,000. Measured directly at the default β=10\beta=10, LNU's top-coordinate gradient share stays between 0.87 and 0.78 from D=20D=20 to D=5,000D=5{,}000, while an inner-product layer's falls from 0.14 to 0.001 (revised Appendix J.25).

[W1, W2, clarification] Is the first sentence of the Introduction contradictory to Eq. 1, and are rule learners differentiable? The first sentence of the Introduction is not contradictory to Eq. 1, because it distinguishes the reduction operator, not the summation sign. Eq. 1 is written as a sum, but its coefficients α\alpha are a softmin of the products themselves: they depend on the input, concentrate on the smallest product, and as β\beta grows the sum returns exactly min⁡izi\min_i z_i (Section 3.1, "selects the smallest product"). An inner product's coefficients are fixed weights, so it "averages all DD coordinates". The revised first sentence of the Introduction now names that distinction: modern networks reduce their inputs by a weighted sum, logic by an extremum.

The submitted sentence at line 21 reads "tree and rule learners are not differentiable", in the classical sense the paper evaluates: decision trees and rule-induction systems such as RIPPER (Appendix J.3), which are not differentiable. In the broader sense of the reviewer's references, neurosymbolic rule learners are differentiable, and the revised sentence covers both: "trees are not differentiable, and differentiable rule learners learn standalone rule sets rather than a layer inside a network" (revised abstract; revised Section 1 states the same with the citations). Of the reviewer's references, [2] (Evans & Grefenstette, 2018) is already discussed in Appendix I, which states that "Evans & Grefenstette (2018) learn first-order logic programs differentiably but require a pre-defined language bias"; [1] (Wang et al., 2021), [3] (Glanois et al., 2022) and [4] (Gao et al., 2025) are added and cited in Section 1. All four learn standalone rule sets, whereas LNU is an aggregation layer over continuous inputs inside a network.

Reviewer_TZ2vOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

Disclaimer: This is an emergency review completed on short notice. I am reading as an informed outsider rather than as a domain expert, so my assessment focuses on clarity, soundness of the core argument, and the strength of the evidence as presented. I have not independently verified proofs, re-run experiments, or checked the related work in depth, and the area chair should weight this review accordingly, particularly on questions of novelty relative to prior work.

Summary: The paper proposes Logical Neural Units (LNU), neurons that aggregate complement-augmented inputs [x,1−x][x, 1-x] with a temperature-controlled softmin (soft AND) or softmax (soft OR) instead of a weighted sum. It argues that this gives a per-coordinate gradient that doesn't shrink with input dimension and a PAC sample-complexity separation from inner-product models on sparse DNF targets, supported by synthetic Boolean benchmarks, distractor-padding experiments, and UCI datasets.

Technical assessment: The central claim is clear, but the Ω(D)\Omega(D) lower bound uses the hypothesis class's VC dimension rather than the target class's, and Winnow (a proper linear learner) achieves O(klog⁡D)O(k \log D), so Theorem 4 seems to separate sparse from unconstrained learners rather than LNU from inner products. Its upper bound also covers ℓ0\ell_0-constrained ERM rather than the trained model, and the trained model fails on XOR even though it is in the covered class. The distractor-robustness results seem to be the strongest evidence (Table 2), but the somewhat implausible Transformer baseline (37.3% on Splice, below the majority-class rate, and 10.9% on padded Splice, below random guessing) and missing sparse baselines in the headline tables signals to me that the advantages of LNU are not separated convincingly enough from any feature-sparsity prior.

Critical strengths

See technical assessment above.

Critical weaknesses

See technical assessment above.

Questions for authors
2 comments
AuthorsOpenReview ↗

Part 1/2 (continued in the next comment)

We thank the reviewer for taking on this review on short notice and for noting that "The central claim is clear" (technical assessment). The reviewer's summary concern is that the advantages of LNU are "not separated convincingly enough from any feature-sparsity prior". The separation is on non-linear logical structure: sparse linear learners carry that prior but cannot represent a DNF, and they stay below LNU through D=200D=200 (see [sparse baselines]). The technical points come first, the lower bound in [lower bound] and the upper bound and XOR in [upper bound, XOR], and the baselines and Table 2 are clarified in [baselines, Table 2]. Results marked held-out use a protocol added in the revision: configuration and epoch are selected on a validation split, accuracy is reported on an untouched test split, and methods are compared over 10 seeds with paired Wilcoxon tests. In the revised PDF, revised and added text is shown in color.

[lower bound] Does Theorem 4 separate LNU from inner products, or sparse from unconstrained learners? It separates learners with a sparsity bias from worst-case empirical risk minimization over the unconstrained linear-threshold class, so it does not separate LNU from Winnow, which has a sparsity bias and attains O(klog⁡D)O(k \log D). The revised lower bound is proved by a direct witness, not from the VC dimension of either class: on a point-mass distribution with the single-literal target x1x_1, some linear threshold consistent with all NN samples is wrong on the unseen unit vectors and has error above ε\varepsilon unless N=Ω(D/ε)N = \Omega(D/\varepsilon) (revised Section 4.2 and Appendix A.12). This is the cost of searching all DD coordinates without a sparsity bias, and Winnow and sparse linear ERM do not pay it on this witness. Where LNU and Winnow differ is the target class: a sparse linear learner does not represent a general kk-term DNF, while the LNU class represents every kk-term DNF (Observation 1) and learns it from the upper bound's sample size (revised Appendix A.12); the measured side of this difference is in [sparse baselines].

[upper bound, XOR] Does the upper bound cover the trained model, and why does it fail XOR? The upper bound covers the sparse class, at most kℓk\ell nonzero first-layer weights, not the SGD-trained model; as Appendix J.1 states, Theorem 4 "bounds the samples a sparse learner needs; it does not describe SGD's behavior", and trained LNUs recover the relevant support empirically (Appendix J.1). XOR lies in the class, since two conjunction units under the linear head represent it (revised Section 3.2), so the failure is one of training. Parity gives every single literal zero correlation with the label at every DD, so the gradient cannot single out the relevant pair: one layer learns it only partly, and only while DD is small (74.6% at D=20D=20, 64.4% at D=50D=50, held-out) and is at chance by D=200D=200, the one layer limit the Table 1 footnote discloses. Adding a second LNU layer makes XOR learnable at low DD: two layers reach 99.6 ±\pm 0.7 at D=20D=20 and 92.2 ±\pm 12.8 at D=50D=50, held-out (p=.002p=.002 over one layer; revised Appendix K).

[sparse baselines] Are LNU's advantages separated from a feature-sparsity prior? It is separated on non-linear logical structure, and the separation is in what the learners can fit, not in how results are selected: on a 2-term DNF, sparse and linear learners (l1, l0, ElasticNet, univariate screening) stay at 87 to 91% training accuracy even at N=2,000N=2{,}000, while LNU fits it (Section 5.5). Held-out (Table R1), l1 and l0 stay at 81 to 88% at every ratio, including 1 : 0, and LNU leads both by 4 to 18 points through 1 : 49 relevant to irrelevant features (p≤.020p \le .020); it is still ahead at 1 : 124, though not significantly (p≥.084p \ge .084), and the three are level beyond the range shown (D=1,000D=1{,}000, 1 : 249: 77.3, 79.0 and 79.7, p≥.19p \ge .19). On Splice, a near-linear real target, selection alone suffices: l0-screen matches or exceeds LNU at every padding level (lower block); and on the four real-world sets the best of them is within noise of LNU (revised Table 28). They are reported with the other held-out results in revised Appendix J.25 (Tables 28 and 29), where every method shares one setting, rather than in Tables 1 and 2, whose cells come from the submitted protocol.

Table R1. Sparse linear learners (l1-logistic, l0-screen, Winnow) under distractors, held-out, N=100N=100, 10 seeds, accuracy % (mean ±\pm std); ratio: relevant : irrelevant features for the DNF (4 relevant variables; 1 : 0 keeps only those 4), original : random features for Splice; LNU width and β\beta tuned on validation; p: paired Wilcoxon, LNU vs each sparse learner, from the same runs (accuracies in revised Table 29).

DratioLNUl1-logisticl0-screenWinnowp (LNU vs l1)p (LNU vs l0)p (LNU vs Winnow)
DNF(2-term), synthetic
41 : 0100.0 ±\pm 0.087.8 ±\pm 4.684.8 ±\pm 5.067.4 ±\pm 7.1.002.002.002
201 : 499.9 ±\pm 0.284.9 ±\pm 3.384.8 ±\pm 3.977.3 ±\pm 3.0.002.002.002
501 : 11.598.9 ±\pm 1.680.9 ±\pm 2.883.4 ±\pm 3.376.9 ±\pm 3.5.002.002.002
2001 : 4987.3 ±\pm 2.881.6 ±\pm 1.483.1 ±\pm 3.775.5 ±\pm 3.0.002.020.002
5001 : 12485.2 ±\pm 6.380.9 ±\pm 1.882.7 ±\pm 4.871.1 ±\pm 3.6.084.19.002
Splice, real data
2871 : 088.3 ±\pm 2.684.9 ±\pm 2.288.8 ±\pm 1.584.0 ±\pm 1.6.006.85.002
5001 : 0.7487.6 ±\pm 2.084.8 ±\pm 1.388.0 ±\pm 1.984.2 ±\pm 2.1.004.45.010
10001 : 2.585.7 ±\pm 2.983.9 ±\pm 2.087.1 ±\pm 2.580.0 ±\pm 7.5.037.23.002
20001 : 6.084.3 ±\pm 3.283.1 ±\pm 2.087.5 ±\pm 1.681.5 ±\pm 3.1.43.027.014
50001 : 16.477.2 ±\pm 4.382.8 ±\pm 1.886.2 ±\pm 3.279.6 ±\pm 6.4.002.002.38

On Splice padded with random features (lower block), l0-screen is level with LNU up to D=1,000D=1{,}000 (1 : 2.5) and ahead from D=2,000D=2{,}000 (87.5 vs 84.3 at 1 : 6.0; 86.2 vs 77.2 at 1 : 16.4, p=.002p=.002), while l1-logistic stays below LNU up to D=1,000D=1{,}000, is level at D=2,000D=2{,}000 and overtakes it at D=5,000D=5{,}000. Splice is close to linearly separable, so explicit feature selection loses little as padding grows (l0 -2.6 and l1 -2.1 points from D=287D=287 to 5,000), while LNU, which selects its literals by gradient among all coordinates, loses 11.1.

[baselines, Table 2] Can the Transformer baseline perform better? It can: reading one token per input feature, in the held-out setting all methods share (revised Appendix J.25), it reaches 83.4% on Splice, replacing the 37.3%, and the 10.9% cell at D=5,000D=5{,}000 is not re measured, as the held-out runs stop at D=1,000D=1{,}000. Under the held-out setting, padded Splice does not show the near-invariance of the submitted Table 2 (94.8, -0.6pp). Its comparison with the sparse learners under padding is in [sparse baselines].

Comments on the paper

1 comment

We thank the reviewers for their feedback and the Area Chair for handling this submission. We have uploaded a revised PDF with changes shown in color. Section, appendix, table and theorem numbers below refer to it. We answer every point in the replies to each reviewer. Below we summarize the most important ones.

Significance of the proposed primitive. A standard neural unit sums its weighted inputs, so every input shares the gradient. LNU takes a soft minimum (AND) or soft maximum (OR) over its inputs and their complements, so the input that sets the minimum gets most of the gradient. We measured this at initialization. That input keeps most of the gradient as irrelevant inputs are added, while in an inner-product layer its share falls toward zero (Appendix J.25). The practical consequence is sample efficiency. With 100 training examples, LNU learns rules that depend on a few of many features far more accurately than the MLP, the unit it replaces, under the held-out protocol (Table 28). Propositions 2 and 3 give the reason for a single unit. In a thresholded weighted sum, the influence of a relevant input relative to the total variation of the sum shrinks as 1/D1/\sqrt{D}, while in LNU the derivative of the input that sets the minimum stays of the order of its weight. Theorem 4 proves a sample complexity separation for a sparse class of LNUs. Such a class learns a kk-term DNF from a number of samples that grows only logarithmically in DD, while worst-case empirical risk minimization over unconstrained linear thresholds can need a number that grows linearly in DD. Trees and rule learners are separate models, while LNU is a layer inside a network. Logic-gate and LUT networks need binarized inputs and connect each gate to a few of them, while LNU takes continuous inputs and reads all of them.

Clarifications.

  1. Eq. 1 is written as a sum, but its weights are a softmin of the products themselves. As the sharpness β\beta grows, the sum returns the smallest product (YLPM).
  2. The gradient concentrates on one input by design. This is how the relevant input still receives gradient when DD is large (QjvL).
  3. Sparsity is not the whole difference. One LNU layer with a linear output represents any kk-term DNF, and a sparse linear learner cannot (Section 3.2; TZ2v).
  4. LNU is a layer, so we compare it with the unit it replaces, not with a standalone learner such as XGBoost (QjvL).

Added in the revision.

  1. The abstract states the claim that Theorem 4 proves. For MLPs and Transformers the gap is shown by experiments (TZ2v, YLPM, uKRJ).
  2. We added a held-out protocol. Configuration and epoch are selected on a validation split and accuracy is reported on an untouched test split, over 10 seeds with paired tests. With this protocol, LNU's lead over the MLP is significant on Splice, Chess and Phishing and within noise on Mushroom (Table 28; uKRJ).
  3. We added sparse linear baselines under the same protocol. ℓ1\ell_1-logistic, ℓ0\ell_0-screen and Winnow stay below LNU on the 2-term DNF through D=200D=200 (Table 29; TZ2v).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.