1 Introduction↩︎

In high-stakes deployments including healthcare, finance, public policy, and safety-critical engineering, interpretability is often a functional requirement, enabling accountability and auditability [1]–[3]. In these regimes, post-hoc explainability methods that attempt to rationalize a black-box predictor can be brittle: the explanation may be misaligned with the true decision process [4], [5]. Rudin [6] argues that, when possible, one should prefer inherently interpretable models over explanations of opaque ones, where transparency is a property of the model itself.

Rule-based predictors are a natural target for such fundamental interpretability. However, interpretability is multifaceted. First, global interpretability means that a single set of rules governs the model’s behavior for all inputs; this contrasts with local explanations that provide input-dependent rationales. Second, exact interpretability means that the extracted rules reproduce the model’s inference exactly, rather than approximately (e.g., via feature-attribution scores). In this work, we focus on the demanding but practically valuable regime of global and exact interpretability, where the entire model’s inference can be reduced to symbolic logic without approximation.

Crucially, interpretability does not guarantee human understandability. Human-subject evaluations demonstrate that cognitive load scales non-linearly; specifically, studies suggest that rule sets exceeding a complexity of 50 become functionally unintelligible [7]. Hence, our work focuses on producing rule sets that minimize rule complexity while maintaining competitive predictive performance. Figure 1 showcases this: our model TT-Sparse achieves superior predictive performance while maintaining low rule complexity (well within the complexity threshold for human intelligibility of 50 indicated by the green region), outperforming other rule models and remaining competitive with the state-of-the-art deep tabular model, TabM [8].

Despite their appeal, learning high-performing rule sets while minimizing complexity remains challenging. Classical approaches often rely on discrete, heuristic search (e.g., greedy rule induction or tree growth/pruning), which can become trapped in suboptimal solutions and may struggle to exploit modern hardware efficiently [9], [10]. More recent lines of work pursue global optimization objectives or neural-symbolic relaxations that enable gradient-based training, but they impose restrictive logical forms that limit expressivity [11], [12].

Truth table-based nodes offer a direct route to exact symbolic conversion via standard minimization procedures such as Quine-McCluskey [13], [14]. Crucially, truth table-based nodes provide high expressivity because they are capable of representing any Boolean function over their inputs, effectively acting as the discrete counterpart to standard neural network (NN) nodes. Unlike neural-symbolic relaxations that approximate discrete logic through continuous functions, truth table nodes function as fundamental building blocks that directly map input patterns to outputs. However, making such nodes trainable at scale requires solving a key bottleneck: selecting a sparse, meaningful subset of inputs for each node in a way that remains compatible with backpropagation.

We introduce TT-Sparse, a differentiable rule-learning architecture built around Learnable Truth Table (LTT) nodes that can be transformed exactly into Boolean formulas (DNF/CNF) after training. Each LTT node learns a Boolean function over a small set of selected input features; the entire model is then a composition of these rule activations with a lightweight prediction head. The central technical challenge is that choosing which \(k\) inputs feed each node is a discrete TopK operation, which is non-differentiable. TT-Sparse resolves this with a novel soft TopK operator that provides a continuous relaxation while enforcing an exact cardinality constraint in expectation, enabling stable gradient flow through the connection-selection mechanism. Concretely, we use a straight-through strategy where the forward pass uses hard TopK selections to preserve sparsity, while the backward pass uses the differentiable relaxation to update connection scores. After training, we enumerate each node’s induced truth table and apply Quine-McCluskey [15], [16] minimization to obtain compact symbolic rules, yielding global and exact interpretability.

Empirically, TT-Sparse consistently achieves favorable performance-complexity trade-offs across 28 tabular benchmarks spanning binary, multiclass, and regression tasks, the only interpretable rule-learning model that natively supports all three within a single architecture while remaining competitive with the SOTA non-pretrained tabular model.

1.0.0.1 Conflict of Interest Disclosure.

All authors are affiliated with Implicant (https://implicant.ai), a company that deploys TT-Sparse for commercial applications. The model evaluated in this paper forms the core technology of that product.

Contributions. The main contributions of this work include: (1) We propose a novel, efficient, and fully differentiable relaxation of the discrete TopK operator, enabling end-to-end gradient-based optimization of discrete feature routing via backpropagation with zero gradient variance. (2) We introduce the TT-Sparse layer, a flexible neural building block that leverages our Soft TopK operator to dynamically learn sparse connections and extract multi-feature Boolean interactions. Each LTT node’s learned Boolean function is converted exactly to DNF/CNF via truth table enumeration and Quine-McCluskey minimization, yielding global and exact interpretability with no post-hoc approximation (Figure 3). (3) Through extensive empirical validation on 28 datasets, we demonstrate that TT-Sparse establishes a new Pareto frontier in the performance-complexity landscape while achieving predictive accuracy competitive with SOTA non-pretrained tabular model, TabM. Notably, TT-Sparse is the only interpretable rule-learning model that natively supports all three task types (binary, multiclass classification, and regression) within a single architecture.

2 Related Work↩︎

In this section, we provide an overview of the literature on methods that achieve global and exact interpretability, as well as relaxations of the discrete TopK function. We evaluate these approaches with TT-Sparse in Section 4.

Tree-Based Approaches. While classical decision trees [10] offer an intuitive approach, their greedy induction strategy often leads to suboptimal rule sets. To address this, GOSDT [17] employs dynamic programming to find provably optimal sparse trees, though at a high computational cost for large datasets. Conversely, ensemble methods like LightGBM [18] achieve state-of-the-art predictive performance but sacrifice interpretability by distributing the decision logic across hundreds of weaker trees. However, the tree topology inherently restricts each root-to-leaf path to a logical conjunction (AND) of splitting predicates.

Heuristic-Guided Bottom-Up Rule Induction. RIPPER [9] is a classic technique that employs a greedy strategy to grow and prune rule sets, incrementally refining them to optimize predictive accuracy. Classy [19] advances this approach by utilizing the Minimum Description Length (MDL) principle to search for compact probabilistic rule lists without the need for hyperparameter tuning. Other approaches, such as GLRM [20] and RuleFit [21] improve scalability by leveraging column generation or tree ensembles to identify candidate rules. However, similar to the limitation with trees, these methods remain constrained by discrete heuristic generation: they build rules by iteratively adding conjunctions (ANDs), lacking the native flexibility to learn complex, nested Boolean structures (e.g., ORs) directly within a single rule unit.

Neuro-Symbolic Approaches. Neuro-symbolic models aim to combine the generalization power of neural networks with symbolic interpretability. DILP [22] and RRL [23] learn a set of discrete rules by projecting logical structures into a differentiable space and applying gradient-based optimization. RL-Net [24] uses a neural architecture that mimics rule lists by enforcing a hierarchical activation structure. Most recently, NeuRules [25] integrate feature discretization, rule construction, and rule ordering into a single end-to-end differentiable pipeline.

Differentiable TopK. Prior differentiable TopK approaches rely on iterative Optimal Transport solvers with the Sinkhorn algorithm [26], [27] or stochastic noise injection [28], [29], which introduces significant computational overhead or gradient variance. Most recently, Petersen et al. [30] used these novel differentiable TopK operators to define a top-\(k\) cross-entropy loss, enabling the direct end-to-end optimization of top-\(k\) classification accuracy, achieving state-of-the-art fine-tuning results on ImageNet.

3 TT-Sparse↩︎

In this section, we introduce TT-Sparse, a Truth Table-based Sparse neural block. Each node in the TT-Sparse layer can be understood as a learnable truth table logic over its inputs; we call them Learnable Truth Table (LTT) nodes interchangeably. This block is the core interpretable unit that transforms input features into Boolean rules. Let \(\vec{x}\) be the \(n\)-dimensional input vector to the layer, and there are \(M\) LTT nodes in the layer.

The TT-Sparse layer comprises of 3 components: the connection selection, the linear operation of the selected inputs, and the binarization. The connection selection mechanism leverages the soft TopK operator we introduce to enable learning by backpropagation of the loss by relaxing the discrete, non-differentiable selection of the traditional TopK.

3.1 Components↩︎

3.1.1 Soft TopK↩︎

We define the operator \[S_k: \mathbb{R}^n \to \mathcal{P}_k \subset[0,1]^n\] where \(\vec{s} \in \mathbb{R}^n\) denotes an input score vector (in practice, a column of the connection matrix \(W_{\text{map}}\); see Section 3.1.2) and \(\mathcal{P}_k = \{\vec{\pi}\in[0,1]^n : \sum_{i=1}^n \pi_i = k\}\).

The hard TopK operator can be viewed as finding the vector \(\vec{\pi}\) within the feasible set that maximizes \(\vec{s}^\top \vec{\pi}\), achieved by assigning the components of \(\vec{\pi}\) corresponding to the \(k\) largest values of \(\vec{s}\) to 1, while setting the rest to 0. Since this discrete selection is not differentiable, we introduce an entropic regularizer to find a selection probability vector \(\vec{\pi} \in [0, 1]^n\) that is closest to the scores \(\vec{s}\) (maximizing the dot product) while maintaining smoothness and summing exactly to \(k\). The entropic regularizer is weighted by a predetermined parameter temperature \(\tau > 0\). This leads us to the optimization objective

\[\vec{\pi}^* = \underset{\vec{\pi} \in [0, 1]^n}{\mathrm{argmax}} \left[ \sum_{i=1}^n \pi_i s_i + \tau\!\sum_{i=1}^n H(\pi_i) \right] \;\;\text{s.t.}\;\; \sum_{i=1}^n \pi_i = k \label{eq:topk-objective}\tag{1}\]

where \(H(\pi_i) = -\pi_i \log \pi_i - (1-\pi_i) \log(1-\pi_i)\) is the binary entropy. Solving via Lagrange multipliers (Appendix 8), the solution \(S_k(\vec{s}):=\vec{\pi}^*\) has components \[\pi^*_i = \sigma\!\left(\frac{s_i}{\tau} + c\right) \label{eq:topk-solution}\tag{2}\] where \(\sigma(\cdot)\) is the sigmoid and \(c\in\mathbb{R}\) is the unique root of \(f(c) = \sum_{j=1}^n\sigma(\frac{s_j}{\tau}+c) - k = 0\), found by bisection.

This allows exact gradients to be derived by implicit differentiation. Let \(d_i=\sigma'(\frac{s_i}{\tau}+c) = \pi^*_i(1-\pi^*_i)\) and \(\vec{d} = [d_1, \dots,d_n]^\top\). Then the element-wise partials are: \[\begin{align} \frac{\partial \pi_i}{\partial s_j} &= \frac{1}{\tau}\, d_i \left( \delta_{ij} - \frac{d_j}{\|\vec{d}\|_1} \right) \tag{3}\\[4pt] \frac{\partial \pi_i}{\partial k} &= \frac{d_i}{\|\vec{d}\|_1} \tag{4} \end{align}\] which yield the full Jacobian and gradient in matrix form: \[\begin{align} \nabla_{\!\vec{s}}\, S_k(\vec{s}) &= \frac{1}{\tau} \left[ \mathrm{diag}(\vec{d}) - \frac{\vec{d}\, \vec{d}^{\!\top}}{\|\vec{d}\|_1} \right] \tag{5}\\[4pt] \nabla_{\!k}\, S_k(\vec{s}) &= \frac{\vec{d}}{\| \vec{d} \|_1} \tag{6} \end{align}\]

The complete derivation of the partials can be found in Section 8.2. The gradient is scaled by \(\frac{1}{\tau}\), similar to the role of temperature in softmax. As \(\tau \to0\), the relaxation approaches the hard TopK; the effect of \(\tau\) on the selection weights is illustrated in Figure 6. Implementation details are in Section 8.4.

The closed-form sigmoid solution is critical for TT-Sparse: since the operator is applied independently to each of the \(M\) LTT nodes at every training step, both memory footprint and gradient stability compound across the layer. Table 1 compares against the Sinkhorn-based optimal transport relaxation [26] and the perturbed maximizer [28]. While Sinkhorn is also deterministic (zero gradient variance), its iterative solver incurs \(10\times\) higher latency and \(316\times\) more memory, which is prohibitive when applied \(M\) times per forward pass. The Perturbed operator matches our throughput but requires stochastic noise injection, introducing substantial gradient variance that destabilizes connection routing over long training runs, and consuming \(73\times\) more memory to store the Monte Carlo samples.

3.1.2 LTT Nodes↩︎

Let \(\vec{x}\in\mathbb{R}^n\) denote the input to the TT-Sparse layer with \(M\) LTT nodes. The block has 2 learnable modules: the connection mapping represented by a matrix \(W_{\text{map}} \in \mathbb{R}^{n \times M}\) and the truth table logic represented by matrix \(W_{\text{LTT}} \in \mathbb{R}^{n \times M}\) (augmented by a bias vector \(b \in \mathbb{R}^M\)).

For each LTT node \(j \in \{1, \dots, M\}\), the objective is to select a sparse subset of \(k\) input features to form a truth table of size \(2^k\) and learn effective truth table logic over the features. To determine the active inputs for node \(j\), we define a selection mask vector \(m^{(j)}\in\{0,1\}^n\).

In the forward pass, this mask is discrete. It selects the indices corresponding to the top-\(k\) values in the \(j\)-th column of the mapping matrix: \[m^{(j)}_{\text{forward}, i} = \begin{cases} 1 & \text{if } W_{\text{map}}[i, j] \in \text{TopK}(W_{\text{map}}[:, j]) \\ 0 & \text{otherwise} \end{cases}\] for \(i \in [1,\dots,n]\).

The intermediary output of each LTT node is the linear combination of the active features. Let \(\mathcal{I}_j = \{i : m_i^{(j)} = 1\}\) with \(|\mathcal{I}_j| = k\) denote the selected index set for node \(j\). Then: \[z_j(\vec{x}) = \sum_{i \in \mathcal{I}_j} W_{\text{LTT}}[i, j]\cdot x_i +b_j\]

However, the traditional TopK operation is discrete and not differentiable, so without relaxation, the connection matrix will not update to find better connections for the LTT logic. Thus, we leverage the soft TopK operator \(S_k\) we propose in 3.1.1 to replace \(m^{(j)}\) in the backward pass with \(m^{(j)}_{\text{backward}} = S_k(W_{\text{map}}[\cdot, j])\), where the score vector \(\vec{s} = W_{\text{map}}[\cdot, j]\).

Consequently, the partial derivatives w.r.t. the connection weights are computed via the chain rule. The gradient flow to the connection matrix is given by \[\frac{\partial \mathcal{L}}{\partial W_{\text{map}}[\cdot, j]} = \frac{\partial \mathcal{L}}{\partial z_j} \cdot \frac{\partial z_j}{\partial m^{(j)}_{\text{backward}}} \cdot \frac{\partial S_k(W_{\text{map}}[\cdot, j])}{\partial W_{\text{map}}[\cdot, j]}\]

The first term \(\frac{\partial \mathcal{L}}{\partial z_j}\) is the upstream loss gradient, representing how much the overall loss changes w.r.t. the node’s pre-binarization output. The second term \(\frac{\partial z_j}{\partial m^{(j)}_{\text{backward}}} = \vec{x} \odot W_{\text{LTT}}[\cdot, j]\) is an \(n\)-dimensional vector representing the potential contribution of each feature if selected. The third term \(\frac{\partial S_k(W_{\text{map}}[\cdot, j])}{\partial W_{\text{map}}[\cdot, j]}\) is the Jacobian of the Soft TopK operator, \(J_{S_k} \in \mathbb{R}^{n \times n}\) given by Equation 5 (with \(\vec{s} = W_{\text{map}}[\cdot, j]\)). Similar to the connection weights, the gradient for the truth table weights \(W_{\text{LTT}}[i,j]\) is scaled by the selection probability \(\pi_i^{(j)} = [S_k(W_{\text{map}}[\cdot, j])]_i\), so features with higher selection mass receive stronger weight updates. Thus, both \(W_{\text{map}}\) and \(W_{\text{LTT}}\) are jointly optimized through the soft TopK relaxation: the former learns which features to route, while the latter learns how to combine them. The full derivation is provided in Appendix 9. This mechanism allows the TT-Sparse layer to dynamically re-route connections into the LTT node while learning the LTT logic during training.

Finally, to function as a Boolean logic gate, the continuous output \(z_j\) is binarized to \(y_j = \mathbf{1}_{(z_j > 0)}\). Differentiability is maintained with a straight-through estimator [31].

3.2 TT-Sparse Design↩︎

The architecture of the overall model is designed as a hybrid neural block that integrates multi-feature interaction logic through the TT-Sparse layer with linear single-feature.

The layer processes an \(n\)-dimensional input vector \(\vec{x}\) to produce \(M\) binary rule activations \(\vec{y} \in \{0, 1\}^M\) via the LTT nodes. Then, we implement a skip-concatenation, so the final representation \(\vec{h}\) is formed by concatenating the raw input features with the LTT rule outputs: \(\vec{h} = [\vec{x} \parallel \vec{y}] \in \mathbb{R}^{n+M}\). This combined vector is then fed into a final classifier or regressor layer \(f_{\text{cls}}(\vec{h}) = \sigma(W_{\text{cls}}\vec{h} + b_{\text{cls}})\), depending on the task (binary/multiclass/regression). Because \(f_{\text{cls}}\) is linear over the concatenation, each weight corresponds to either a multi-feature Boolean rule (from \(\vec{y}\), extracted via truth table enumeration) or a single-feature (unary) rule (from \(\vec{x}\), readable directly as a weighted threshold). The extracted rule set includes both terms with exact weights, preserving full interpretability.

While the TT-Sparse layer selects several inputs per node, not all connections or all nodes may be essential for a given task. To identify the most compact and effective rule set, we implement a post-hoc iterative magnitude pruning after the initial training phase. Connections in the TT-Sparse layer are removed based on the weights’ \(L_1\) norm, followed by an iterative fine-tuning of the non-zeroed weights. Throughout this refinement process, the selected connections of the LTT nodes remain fixed to the selected indices by \(W_{\text{map}}\) during training. This refinement phase focuses on optimizing the weights of the established logical structure, finding the lightest and most effective rule logic for the given task.

3.3 Rule Extraction↩︎

Each node \(j\) computes a learnable Boolean function over its \(k\) selected inputs. Let \(\mathcal{I}_j = \{i_1, \ldots, i_k\} \subset \{1, \ldots, n\}\) denote the indices selected by the top-\(k\) operator on \(W_{\text{map}}\). To extract the explicit Boolean formula, we enumerate all \(2^k\) binary assignments to these \(k\) inputs. For a binary vector \(v \in \{0,1\}^k\), component \(v_\ell\) corresponds to the input feature \(\vec{x}\) at index \(i_\ell \in \mathcal{I}_j\). Let \(w^{(j)} \in \mathbb{R}^k\) be the subvector of \(W_{\text{LTT}}[:,j]\) restricted to \(\mathcal{I}_j\). The localized evaluation is: \[y_j(v) = \mathbf{1}\!\left(v^\top w^{(j)} + b_j > 0\right) = \mathbf{1}\left(z_j > 0 \right)\]

The truth table \(\mathcal{T}_j = \{ (v^{(i)},\, y_j(v^{(i)})) \}_{i=1}^{2^k}\) records the output for every assignment, where \(v^{(1)}, \dots, v^{(2^k)}\) enumerates all \(2^k\) binary vectors in \(\{0,1\}^k\) (e.g., \(000, 001, 010, \dots\)). The subset \(\mathcal{M}_j = \{ v^{(i)} \mid y_j(v^{(i)}) = 1 \}\) are the minterms of the Boolean function.

To minimize rule complexity, we identify Don’t-Care Terms (DCTs): input combinations (\(v^{(i)}\)) that do not appear in the training data. Following the identification of minterms and DCTs, the truth table is synthesized into a minimal DNF expression via the Quine-McCluskey (QMC) algorithm [15], [16] (Algorithm 13). By optimally assigning binary values to these DCTs, the algorithm minimizes the number of implicants and literals in the resulting rule while maintaining exact fidelity on the observed training distribution.

After QMC minimization, each node’s Boolean function is expressed in Disjunctive Normal Form (DNF): a disjunction (OR) of implicants, where each implicant is a conjunction (AND) of literals (Boolean conditions on individual features). We define the complexity of a rule set as the total number of literals across all rules in the model, including unary rules and the bias term. For multiclass tasks, a rule contributes to the count exactly once if it holds a non-zero weight for any class.

3.3.0.1 Per-node complexity.

Each node with fan-in \(k\) computes a linearly separable (threshold) Boolean function of its \(k\) inputs. By Sperner’s theorem, the maximum number of prime implicants of any such function is \(\binom{k}{\lfloor k/2 \rfloor}\) [32]. Since a node’s total literal count in its minimized DNF directly equals its contribution to overall model complexity, Table 2 characterizes learned per-node complexity by extracting and minimizing every non-trivial node’s Boolean function via QMC across all 28 datasets and 5 seeds. The "with DCT" column marks input patterns unobserved in training data as don’t-cares, as the full extraction pipeline.

Table 2 shows that mean per-node literal count remains well below the tight worst-case bound at every fan-in. At \(k{=}6\), nodes average 5.7 implicants (19.2 literals) versus a bound of 20 implicants, and don’t-care optimization further reduces this to 2.8 implicants (7.1 literals). This confirms that individual nodes converge to functions that use only a fraction of their representational capacity, and that the training-data-aware DCT simplification yields rules roughly half as complex while providing regularization. The total model complexity (reported in Tables ¿tbl:tab:results-binary?–¿tbl:tab:results-regression?) is then the sum of per-node literals for all rules.

By modeling the node truth table logic as a thresholded linear combination of the selected inputs, TT-Sparse requires only \(n+1\) learnable parameters (one weight per selected input plus a bias term) to represent the logic, a linear complexity compared to DiffLogicNet [11] double-exponential and DWN [33] exponential complexities.

DiffLogicNet introduces a differentiable relaxation of the Boolean logic to implement binary gates as nodes, by learning a probability distribution over the set of all possible binary operators for a given number of inputs. While effective for 2-input gates, this approach scales poorly as the number of possible Boolean functions grows double exponentially with the number of inputs, \((2^{2^n})\).

The DWN model [33] addresses this scalability bottleneck by parameterizing nodes as Lookup Tables (LUTs) with \(2^n\) parameters and Extended Finite Differences for gradient estimation. However, LUTs are position-dependent: permuting selected features invalidates the learned weights, causing inefficiency during connection search. In contrast, the TT-Sparse linear combination is commutative, making nodes robust to input reordering. Additionally, pruning a LUT input requires constraining half the table via Shannon expansion, whereas TT-Sparse simply pushes a weight to zero via \(L_1\). We validate these advantages empirically in Tables ¿tbl:tab:results-binary?–¿tbl:tab:results-regression?.

4 Experiments↩︎

We validate TT-Sparse on 28 tabular datasets (14 binary, 7 multiclass, 7 regression), evaluating whether it achieves Pareto-competitive performance-complexity trade-offs against interpretable baselines and how it compares to TabM [8], the SOTA non-pretrained tabular model.

Datasets and Metrics. We evaluate ROC-AUC for classification (One-vs-Rest for multiclass) to judge predictive performance while handling class imbalance and \(R^2\) for regression. All models are trained with cross-entropy loss for classification and MSE for regression.

Baselines. We compare against GOSDT [17], GLRM [20], RuleFit [21], Classy [19], NeuRules [25], RL-Net [24], RRL [23], and DWN [33].

We use the rule-set complexity metric defined in Section 3.3. We visualize full performance-complexity Pareto frontiers in Appendix 10; Tables ¿tbl:tab:results-binary?–¿tbl:tab:results-regression? report the best Pareto-optimal configuration per model. Due to architectural limitations, GLRM and RuleFit cannot handle multiclass, and the remaining models are limited to classification.

For all binary classification datasets except covertype, jungle, and road_safety (Table ¿tbl:tab:results-binary?), TT-Sparse consistently pushes the Pareto limit, achieving comparable or better performance with lower complexity. While GOSDT often yields the lowest complexity rules with sparse decision trees, it frequently suffers from performance issues. For some datasets (blood, compas, cc_default, creditg, diabetes, heart, income), TT-Sparse remains competitive with the SOTA DL baseline TabM, notably surpassing it on the Heart dataset with low complexity.

Multiclass classification (Table ¿tbl:tab:results-multiclass?) highlights the strongest advantage of our approach. With GLRM and RuleFit unable to operate in this setting, TT-Sparse comfortably outperforms the other models in all datasets as the Pareto frontier, and is very close to achieving TabM performance while maintaining full transparency. TT-Sparse also shows strong competitiveness for the regression tasks (Table ¿tbl:tab:results-regression?), effectively outperforming GLRM and underperforming RuleFit in rank by a thin margin.

4.1 Ablation Study↩︎

TopK fan-in constraint. The TT-Sparse design makes three deliberate choices regarding per-node connectivity. First, it imposes a hard top-\(k\) fan-in constraint on each node before training begins, rather than relying on post-hoc sparsification of a fully connected layer. Second, it introduces a dedicated learnable mapping module \(W_{\text{map}}\) to determine which \(k\) inputs each node receives, rather than selecting connections by weight magnitude alone. Third, within that mapping, it employs a differentiable Soft TopK operator to select the \(k\) most important distinct inputs, rather than a slot-based Softmax as in DWN [33]. The first two choices are validated here; the third is evaluated separately below.

We compare against three baselines that share the same LTT architecture and QMC extraction pipeline, differing only in how connectivity is determined. FC + \(L_0\) gates [34] learns stochastic binary gates with an \(L_0\) penalty on gate openness, applying sparsification during training but without a fixed fan-in guarantee. FC + \(L_1\) + prune applies \(L_1\) regularization during training and then iteratively prunes by magnitude until per-node fan-in permits extraction. Both approaches attempt to reach the required fan-in through generic sparsification rather than enforcing it structurally. Magnitude TopK enforces the same fan-in \(k\) as TT-Sparse, but selects the \(k\) highest-magnitude LTT weights per node after \(L_1\)-regularized training, without a separate learned mapping. We sweep \(\lambda \in \{0, \ldots, 10\}\) across 5 seeds on 4 datasets spanning all three task types (Table 3).

TT-Sparse dominates the performance-complexity tradeoff on all four datasets. The \(L_0\) and \(L_1\) approaches, which lack a structural fan-in guarantee, can leave nodes with large or uneven fan-in that inflates extracted rule complexity even after pruning. More fundamentally, networks trained without a fan-in constraint distribute information across all available connections, learning high-order node functions. Pruning these connections post-hoc destroys the learned representations, resulting in large performance drops. In contrast, TT-Sparse forces the network to learn compact per-node functions from the start by constraining each node to \(k\) inputs throughout training. The comparison with Magnitude TopK validates the second design choice: it is not sufficient to simply select the \(k\) largest LTT weights after training. Learning connectivity through a separate mapping module \(W_{\text{map}}\) yields better performance-complexity tradeoffs because the mapping can specialize in selecting informative inputs independently of the logic weights that determine the Boolean function.

Soft TopK vs.slot-based Softmax. Given that a learned mapping is beneficial, we further validate the choice of selection mechanism. We compare against the slot-based Softmax connection selection from DWN [33], where instead of selecting \(k\) features from a single importance vector, the \(k\) inputs to each LTT node are treated as distinct, ordered “slots”. The connection matrix becomes \(W_{\text{map}} \in \mathbb{R}^{n \times kM}\) instead of \(W_{\text{map}} \in \mathbb{R}^{n \times M}\), and each slot selects its input independently via argmax (relaxed with softmax during backpropagation). This design has two disadvantages: (1) parameter inefficiency, where mapping complexity scales as \(\mathcal{O}(M \cdot n \cdot k)\) rather than \(\mathcal{O}(M \cdot n)\); and (2) input redundancy, where independent slots may converge on the same feature index, effectively collapsing the dimension of the truth table. Our Soft TopK operator prevents both issues by selecting the \(k\) most relevant distinct indices from a single importance vector per node. Experimental results (Figure 5) across all 28 datasets confirm that Soft TopK consistently yields superior predictive performance.

5 Conclusion↩︎

In this work, we introduced TT-Sparse, a new neural building block designed to achieve highly performant rule sets while minimizing complexity. By reformulating truth tables as differentiable modules with sparse connectivity learned through the new soft TopK operator, we enable the end-to-end learning of Boolean logic via standard gradient descent. Furthermore, as a fully differentiable layer, TT-Sparse offers significant architectural flexibility; it can be seamlessly integrated into standard neural pipelines to learn interpretable rules across diverse problem settings, including binary, multiclass, and regression tasks.

5.1 Limitations↩︎

Continuous features must be encoded before training, fixing the representation of the literals. Second, the utilization of the soft TopK operator makes training reliant on the initialization of the temperature parameter \(\tau\). While these parameters must be well-initialized, our ablations in Appendix 13 show that TT-Sparse is robust to this constraint, maintaining high performance after as few as 5 encoding bits. Third, each LTT node is restricted to linearly separable Boolean functions of its \(k\) inputs. Though it’s a theoretical limitation, we validate empirically in Appendix 14 that this is not a practical limitation on tabular data.

5.2 Future Work↩︎

Future work includes extending TT-Sparse to other data domains such as time-series via recurrent latent dimensions and supporting literals formed by learnable linear combinations of inputs (e.g.\(w_1x_1+w_2x_2 \le z\)) to reduce the Boolean complexity required for non-linear boundaries.

Impact Statement↩︎

This work advances the field of interpretable machine learning by introducing a scalable framework for achieving global and exact interpretability without sacrificing predictive performance. This directly addresses the transparency requirements of high-stakes sectors such as healthcare, finance, and criminal justice, where auditability and accountability are essential. By enabling domain experts to inspect, verify, and reason about model behavior, TT-Sparse facilitates algorithmic oversight, strengthens institutional trust, and supports informed, responsible use of machine-learning systems under emerging regulatory frameworks.

6 Datasets↩︎

We benchmark with 28 publicly available datasets (14 binary, 7 multiclass, 7 regression) used in prior works [20], [25], [35]–[37].

7 Implementation Details↩︎

7.1 Hardware↩︎

For all experiments, we use 4 Nvidia GeForce RTX 3090 GPUs and 2\(\times\) Intel Xeon Silver 4310 CPUs (24 cores / 48 threads) clocked at 2.10 GHz, 128 GB RAM. Neural networks under PyTorch (TT-Sparse, NeuRules, RL-Net, RRL, DWN, TabM) were run on GPU, while tree-based model GOSDT and rule induction based models (Classy, GLRM, RuleFit) were run on CPU.

7.2 Hyperparameters and Training Protocol↩︎

For each dataset, we reserve 20% of the data as a hold-out test set using a fixed seed. The remaining 80% is used for hyperparameter tuning. We perform a grid search by further splitting this development set into 80% training and 20% validation. Once the optimal hyperparameters are identified based on the validation metric (AUC for classification, \(R^2\) for regression), we retrain the model on the full development set. This process is repeated across 5 different random seeds and we report the model’s performance on the hold-out test set.

All neural models (TT-Sparse, NeuRules, RL-Net, RRL, DWN) use Adam with learning rate 0.01–0.02, batch size 2048, and early stopping on validation loss. For TT-Sparse, each continuous feature is binarized via thermometer encoding: we place \(b\) thresholds at evenly-spaced quantiles of the training distribution and produce \(b\) binary literals \(\mathbf{1}(x > t_i)\) per feature. Categorical features are one-hot encoded. We tune the key architectural hyperparameters for all models by performing GridSearch:

• TT-Sparse: Number of thermometer bits \(b \in \{4,5,6\}\), Number of LTT nodes \(\in \{1,20,30,40,50\}\), Soft TopK temperature \(\tau \in \{0.001, 0.01, 0.05\}\).

• RuleFit: max_rules \(\in \{5, 20, 40, 60, 80\}\) and regularization strength \(Cs \in \{1, 5, 10, 50\}\).

• GLRM: Regularization penalty \(\lambda_0 \in \{0.05, 0.01, 0.005\}\). We fix \(\lambda_1 = 0.2 \cdot \lambda_0\) as per [20].

• Classy (MDL-Rule-List): min_support \(\in \{5, 10, 15, 20, 30\}\), maximum depth \(\in \{3, 5, 7\}\), and number of cutpoints \(\in \{5, 7\}\).

• GOSDT: Regularization parameter \(\in \{0.005, 0.01, 0.05\}\) and depth budget \(\in \{3, 5, 7\}\).

• NeuRules: n_rules \(\in \{5, 10, 20, 40, 60, 80\}\), predicate temperature \(\in \{0.1, 0.2\}\), and selector temperature \(\in \{0.5, 1.0\}\).

• RL-Net: n_rules \(\in \{5, 10, 20, 40, 60, 80\}\), conjunction penalty \(\lambda_{and} \in \{0.01, 0.005, 0.001\}\), and \(L_2\) regularization \(\in \{0, 0.001, 0.01\}\).

• DWN (Linear): Hidden layer sizes \(\in \{20, 30, 40, 50\}\) and Look-Up Table (LUT) size \(\in \{4, 5, 6\}\). To ensure a fair comparison with TT-Sparse, we implemented the classifier layer immediately following the LUT layer. This architecture introduces a linear operation by assigning a weight to each LUT and adding a bias term before the activation function. The logic rules are derived similarly as TT-Sparse, utilizing Quine-McCluskey conversion to transform LUT minterms into DNF equations.

• TabM: We use the AdamW optimizer and a batch size of 512. Number of layers \(\in \{1, 2, 3\}\), hidden size \(\in \{64, 128, 256, 512\}\), dropout rate \(\in \{0, 0.1, 0.2\}\), learning rate \(\in \{0.01, 0.005, 0.001\}\), bin count for embeddings \(\in \{8, 16, 32, 64\}\), and embedding dimension \(\in \{8, 16, 32, 64\}\).

8 Soft TopK↩︎

\(S_k(\vec{s}) = [\pi_1, \dots, \pi_n]\) where \(\pi_i = \sigma(\frac{s_i}{\tau} + c)\), constrained by \(\sum_{j=1}^n\sigma(\frac{s_j}{\tau}+c)=k\). \(\sigma(x)=\frac{1}{1+e^{-x}}\) is the sigmoid function and \(\sigma'(x) = \sigma(x)(1-\sigma(x))\). Let \(d_i=\sigma'(\frac{s_i}{\tau}+c)=\frac{d}{d(\frac{s_i}{\tau}+c)}\sigma(\frac{s_i}{\tau}+c) = \pi_i(1-\pi_i) \text{ and }\vec{d} = [d_1, \dots,d_n]^\top\).

8.1 Solving the optimization objective via Lagrange multipliers↩︎

Recall the optimization objective

\[\vec{\pi}^* = \underset{\vec{\pi} \in [0, 1]^n}{\mathrm{argmax}} \left[ \sum_{i=1}^n \pi_i s_i + \tau\!\sum_{i=1}^n H(\pi_i) \right] \;\text{s.t.}\; \textstyle\sum_{i=1}^n \pi_i = k\]

where \(H(\pi_i)\) is the binary entropy \(H(\pi_i) = -\pi_i \log \pi_i - (1-\pi_i) \log(1-\pi_i)\). We then derive the optimum by introducing a Lagrange multiplier \(\lambda\) for the \(\sum_{i=1}^n \pi_i = k\) constraint such that the problem becomes

\[\begin{align} \mathcal{L}(\vec{\pi}, \lambda) &= \sum_{i=1}^n \pi_i s_i + \tau \sum_{i=1}^n \Big( {-}\pi_i \log \pi_i - (1{-}\pi_i) \log(1{-}\pi_i) \Big) - \lambda \left( \sum_{i=1}^n \pi_i - k \right) \\ \frac{\partial \mathcal{L}}{\partial \pi_i} &= s_i + \tau\left( \log \tfrac{1-\pi_i}{\pi_i} \right) - \lambda = 0 \end{align}\]

Setting the derivative 0, we obtain the solution \(\pi_i = \frac{1}{1 + e^{-\frac{(s_i - \lambda)}{\tau}}}=\sigma(\frac{s_i - \lambda}{\tau})\), where \(\sigma(\cdot)\) is the sigmoid function. Thus, setting \(c = -\frac{\lambda}{\tau}\), we define \(S_k(\vec{s}):=\vec{\pi}\) where \(\pi_i := \sigma(\frac{s_i}{\tau} + c)\) for \(i \in \{1,\dots,n\}\) and \(c\in\mathbb{R}\) is the unique root of \(f(c) = \sum_{j=1}^n\sigma(\frac{s_j}{\tau}+c) -k= 0\). Since \(f(c)\) is strictly increasing, \(c\) is uniquely determined and solved by the bisection method.

8.2 Obtaining \(\nabla_{\vec{s}}S_k(\vec{s})\)↩︎

We want the Jacobian \(J \in R^{n \times n}\) where \(J_{ij} = \frac{\partial \pi_i}{\partial s_j}\).

First, we apply the chain rule to \(\pi_i = \sigma(\frac{s_i}{\tau} + c)\): \[\frac{\partial \pi_i}{\partial s_j} = \sigma'\left(\frac{s_i}{\tau} + c\right) \cdot \frac{\partial}{\partial s_j}\left(\frac{s_i}{\tau} + c\right)\] Since \(\frac{\partial s_i}{\partial s_j} = \delta_{ij}\): \[\begin{align} \frac{\partial \pi_i}{\partial s_j} = d_i \left( \frac{1}{\tau}\delta_{ij} + \frac{\partial c}{\partial s_j} \right) \label{eq:chain-rule-yi} \end{align}\tag{7}\] where \(\delta_{ij} = \mathbf{1}_{\{i=j\}}\) is the Kronecker delta. Next, we differentiate the constraint function w.r.t. \(s_j\) to obtain: \[\begin{align} \frac{\partial}{\partial s_j} \sum_{m=1}^n \sigma\left(\frac{s_m}{\tau} + c\right) &= 0.\\ \sum_{m=1}^n d_m \left( \frac{1}{\tau}\delta_{mj} + \frac{\partial c}{\partial s_j} \right) &= 0.\\ \frac{1}{\tau}d_j + \left( \sum_{m=1}^n d_m \right) \frac{\partial c}{\partial s_j} &= 0. \\ \frac{\partial c}{\partial s_j} &= - \frac{1}{\tau} \frac{d_j}{\|\vec{d}\|_1} \end{align}\] Substituting this back to Equation 7 : \[\begin{align} \frac{\partial \pi_i}{\partial s_j} &= \frac{1}{\tau} d_i \left( \delta_{ij} - \frac{d_j}{\|\vec{d}\|_1} \right) \\ \nabla_{\vec{s}} S_k(\vec{s}) &= \frac{1}{\tau} \left[ \text{diag}(\vec{d}) - \frac{\vec{d}\, \vec{d}^\top}{\|\vec{d}\|_1} \right] \end{align}\]

8.3 Obtaining \(\nabla_{k}S_k(\vec{s})\)↩︎

\[\begin{align} \frac{\partial \pi_i}{\partial k} &= d_i \cdot \frac{\partial}{\partial k}\left(\frac{s_i}{\tau} + c\right) \\ \frac{\partial \pi_i}{\partial k} &= d_i \cdot \frac{\partial c}{\partial k} \end{align}\] Then, similarly, we differentiate both sides of the constraint function w.r.t. \(k\) to obtain: \[\begin{align} \frac{\partial}{\partial k} \sum_{m=1}^n \sigma\left(\frac{s_m}{\tau} + c\right) &= 1 \\ \sum_{m=1}^n d_m \cdot \frac{\partial c}{\partial k} &= 1\\ \frac{\partial c}{\partial k} &= \frac{1}{\|\vec{d}\|_1} \end{align}\] Substituting this back to Equation (17): \[\begin{align} \frac{\partial \pi_i}{\partial k} &= \frac{d_i}{\|\vec{d}\|_1} \\ \nabla_{k} S_k(\vec{s}) &= \frac{\vec{d}}{\| \vec{d} \|_1} \end{align}\]

8.4 Convergence of bisection method↩︎

To compute the constant \(c\), we implement vectorized bisection search that solves for \(c\) across an entire batch simultaneously on GPU. The bisection method halves the search space in every iteration, so the absolute error \(|\sum S_k(\vec{s})_i-k|\) decays with \(\epsilon_{t} \propto 2^{-t}\).

Figure 7 illustrates the convergence of this method. The soft TopK is applied to a batch of 16 score vectors \(\vec{s} \in \mathbb{R}^{100}\) with target \(k=10\). The theoretical linear convergence (linear slope on the semi-log plot) is observed empirically. The error magnitude drops below \(10^{-3}\) within 15 iterations and reaches the limit of Float32 machine precision in around 30 iterations. Our experiments also show negligible overhead with around 1 ms for a batch of size 16, giving a throughput of more than 10000 samples per second.

9 TT-Sparse Parameter Gradients↩︎

Let \(\vec{x}\in\mathbb{R}^n\) denote the input to the TT-Sparse layer with \(M\) LTT nodes. The layer is parameterized by \(W_{\text{map}} \in \mathbb{R}^{n \times M}\), \(W_{\text{LTT}} \in \mathbb{R}^{n \times M}\), and \(b \in \mathbb{R}^M\). For each node \(j \in \{1, \dots, M\}\), the output is \[z_j = \sum_{i=1}^n m_i^{(j)} \cdot W_{\text{LTT}}[i, j]\cdot x_i +b_j.\]

Leveraging the soft TopK operator \(S_k\) in the backpropagation, \(m^{(j)} = S_k(W_{\text{map}}[\cdot, j])\) is the operator applied on the \(j\)-th column of \(W_{\text{map}}\) (i.e., \(\vec{s} = W_{\text{map}}[\cdot, j]\)) which corresponds to the \(j\)-th node. Let \(\mathcal{L}\) be the upstream loss.

9.1 Gradient w.r.t. \(W_{\text{map}}\)↩︎

Applying the chain rule and denoting the Jacobian \(J_j = \frac{\partial S_k(W_{\text{map}}[\cdot, j])}{\partial W_{\text{map}}[\cdot, j]}\), we have \[\frac{\partial \mathcal{L}}{\partial W_{\text{map}}[\cdot, j]} = J_j^\top \left(\frac{\partial \mathcal{L}}{\partial z_j} \cdot \frac{\partial z_j}{\partial S_k(W_{\text{map}}[\cdot,j])}\right)\]

As \(m^{(j)}=S_k(W_{\text{map}}[\cdot, j])\), we have \[\frac{\partial z_j}{\partial S_k(W_{\text{map}}[\cdot,j])} = \vec{x} \odot W_{\text{LTT}}[\cdot,j].\] The Jacobian \(J_j\) is that of the soft TopK operator applied on the \(j\)-th column of \(W_{\text{map}}\). Using the Jacobian formula obtained in Equation 5 , where \(\vec{d} = m^{(j)}\odot(1-m^{(j)})\) is the elementwise sigmoid derivative evaluated at the soft TopK output: \[\frac{\partial S_k(W_{\text{map}}[\cdot, j])}{\partial W_{\text{map}}[\cdot, j]} = \frac{1}{\tau} \left[ \text{diag}(\vec{d}) - \frac{\vec{d}\, \vec{d}^\top}{\|\vec{d}\|_1} \right]\]

Let \(g_j = \frac{\partial \mathcal{L}}{\partial z_j} \cdot (\vec{x} \odot W_{\text{LTT}}[\cdot, j])\) be the local gradient from the first and second terms of the derivative. Since \(J_j\) is symmetric, we obtain the vector-Jacobian product: \[\frac{\partial \mathcal{L}}{\partial W_{\text{map}}[\cdot, j]} = \frac{1}{\tau} \left[ \text{diag}(\vec{d})g_j - \frac{\vec{d}\, \vec{d}^\top}{\|\vec{d}\|_1}g_j \right] = \frac{1}{\tau}\left[\vec{d} \odot g_j - \frac{\vec{d}(\vec{d}\cdot g_j)}{\|\vec{d}\|_1}\right]\]

9.2 Gradient w.r.t. \(W_{\text{LTT}}\) and \(b\)↩︎

\[\begin{align} \frac{\partial \mathcal{L}}{\partial W_{\text{LTT}}[i, j]} = \frac{\partial \mathcal{L}}{\partial z_j}\cdot \frac{\partial z_j}{\partial W_{\text{LTT}}[i, j]} &=\frac{\partial \mathcal{L}}{\partial z_j} \cdot m_i^{(j)} \cdot \vec{x}_i \\ \frac{\partial \mathcal{L}}{\partial b_j} = \frac{\partial \mathcal{L}}{\partial z_j} \cdot \frac{\partial z_j}{\partial b_j} &= \frac{\partial \mathcal{L}}{\partial z_j} \end{align}\]

10 Performance-Complexity Pareto Grids↩︎

11 Example rules↩︎

GLRM example rule for eye_movements dataset with complexity 15:
0.84 – \(\text{titleNo} \le 2\); 0.34 – \(\text{wordNo} \le 2\); -0.33 – \(\text{nextWordRegress} = 1\); 0.31 – \(\text{regressDur} \le 139\); 0.13 – \(\text{nextWordRegress} = 0\); -0.13 – \(\text{wordNo} \le 1\); 0.15 – \(\text{regressDur} \le 0\); -0.18 – \(\text{prevFixPos} \le 149.5\); -0.16 – \(\text{landingPos} \le 71.6\); -0.10 – \(\text{firstSaccLen} \le 250.1\); -0.04 – \(\text{firstSaccLen} \le 204.0\); -0.53 – \((\text{lastSaccLen} \le 503.2 \land \text{landingPos} \le 117.3 \land 1 < \text{wordNo} \le 8)\); (Bias: -0.23)

GOSDT example rule in the form of a tree for blood dataset with complexity 14:
Class 0 – \(\text{Feature}_0 > -0.62\); Class 0 – \(\text{Feature}_0 \le -0.62 \land \text{Feature}_3 > 0.34\); Class 1 – \(\text{Feature}_0 \le -0.62 \land \text{Feature}_3 \le 0.34 \land \text{Feature}_6 > 2.14\); Class 0 – \(\text{Feature}_0 \le -0.62 \land \text{Feature}_3 \le 0.34 \land \text{Feature}_6 \le 2.14 \land \text{Feature}_8 > 0.34\); Class 1 – \(\text{Feature}_0 \le -0.62 \land \text{Feature}_3 \le 0.34 \land \text{Feature}_6 \le 2.14 \land \text{Feature}_8 \le 0.34\);

Classy (MDL Rule List) example decision list for blood dataset with complexity 8:
Class 1 (\(P=0.57\)) – \((\text{monetary} \ge 1500 \land \text{time} < 59 \land \text{recency} < 7)\); Class 0 (\(P=0.71\)) – \(\text{recency} < 7\); Default Class 0 (\(P=0.89\)) – \(\text{else}\).

NeuRules example rule for diabetes dataset with complexity 17:
3.19 – (\(0.82 < \text{Feature}\_0 < 1.69) \rightarrow \text{Class 1} (71.5\%\)); 8.41 – (\(0.46 < \text{Feature}\_4 \land -0.40 < \text{Feature}\_7 < 3.50) \rightarrow \text{Class 1} (74.2\%\)); 4.56 – (\(0.62 < \text{Feature}\_4 \land -0.15 < \text{Feature}\_7 < 3.31) \rightarrow \text{Class 1} (62.8\%\)); 5.97 – (\(\text{Feature}\_0 < 2.49 \land \text{Feature}\_1 < 0.58 \land \text{Feature}\_6 < 4.55) \rightarrow \text{Class 0} (80.9\%\)); 1.00 – (\(-3.49 < \text{Feature}\_1 < 1.67 \land 0.18 < \text{Feature}\_4 < 4.98 \land -1.14 < \text{Feature}\_6 < 5.58 \land -0.35 < \text{Feature}\_7 < 3.50) \rightarrow \text{Class 1} (64.4\));

RL-Net example rule for calhousing dataset with complexity 87:
Class 1 – (\(\text{Feature}_0 \land \neg \text{Feature}_4 \land \neg \text{Feature}_6 \land \neg \text{Feature}_7\)); Class 1 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \neg \text{Feature}_2 \land \text{Feature}_3 \land \neg \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \neg \text{Feature}_7\)); Class 1 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \text{Feature}_2 \land \text{Feature}_3 \land \neg \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \neg \text{Feature}_7\)); Class 1 – (\(\text{Feature}_0 \land \neg \text{Feature}_1 \land \text{Feature}_2 \land \text{Feature}_3 \land \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \neg \text{Feature}_7\)); Class 0 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \neg \text{Feature}_2 \land \text{Feature}_3 \land \text{Feature}_4 \land \text{Feature}_5 \land \text{Feature}_6 \land \text{Feature}_7\)); Class 0 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \neg \text{Feature}_2 \land \neg \text{Feature}_3 \land \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \text{Feature}_7\)); Class 0 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \neg \text{Feature}_2 \land \text{Feature}_3 \land \neg \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \text{Feature}_7\)); Class 0 – (\(\neg \text{Feature}_0 \land \text{Feature}_1 \land \neg \text{Feature}_2 \land \text{Feature}_3 \land \text{Feature}_4 \land \text{Feature}_5 \land \neg \text{Feature}_6 \land \neg \text{Feature}_7\)); Default: Class 0

RRL example rule with complexity 12:
0.12 – \(\text{frequency} > 17.85\); -0.05 – \(\text{frequency} \le 3.14\); 0.04 – \(\text{recency} > 19.73\); 0.04 – \((\text{recency} > 32.27 \lor \text{time} \le 31.02)\); 0.19 – \((\text{recency} > 12.79 \land \text{time} > 10.96 \land \text{frequency} \le 1.75)\); 0.09 – \((\text{time} > 16.72 \land \text{frequency} \le 2.10 \land \text{monetary} \le 1131.57)\); (Bias: -0.02)

RuleFit example rule on abalone dataset with complexity 15:
12.63 – \(\text{Feature\_5}\); -11.86 – \(\text{Feature\_6}\); -3.28 – \(\text{Feature\_7}\); 3.12 – \(\text{Feature\_8}\); 1.83 – \(\text{Feature\_4}\); 1.36 – \(\text{Feature\_3}\); -0.74 – \(\text{Feature\_0}\); -0.12 – \(\text{Feature\_2}\); 0.08 – \(\text{Feature\_1}\); -0.30 – (\(\text{Feature\_8} \le -0.62\)); 0.09 – (\(\text{Feature\_8} > -0.64 \land \text{Feature\_8} \le 0.83\)); -0.43 – (\(\text{Feature\_8} > -0.64 \land \text{Feature\_8} > 0.83\)); (Bias: 10.24)

TT-Sparse example rule (same as Figure 2) with complexity 15:
-0.83 – \(\text{Feature\_ChestPainType} = \text{'NAP'}\); 0.97 – \(\text{Feature\_ExerciseAngina} = \text{'Y'}\); 1.13 – \(\text{Feature\_ST\_Slope} = \text{'Flat'}\); 1.40 – \(((\text{Feature\_Cholesterol} < 167.63 \land \text{Feature\_Oldpeak} \ge 3.00) \lor (\text{Feature\_ChestPainType} \neq \text{'TA'} \land \text{Feature\_Oldpeak} \ge 3.00) \lor (\text{Feature\_ChestPainType} \neq \text{'TA'} \land \text{Feature\_ChestPainType} \neq \text{'ATA'} \land \text{Feature\_Cholesterol} < 167.63))\); -1.03 – \(((\text{Feature\_MaxHR} \ge 177.25 \land \text{Feature\_Oldpeak} < 2.25) \lor (\text{Feature\_ChestPainType} = \text{'ATA'} \land \text{Feature\_Cholesterol} < 224.88))\); (Bias: -1.04)

TT-Sparse example multiclass rule (Iris dataset) with complexity 7: Class 0: -3.66 – \(\text{sepal-length}\); Class 0: 7.10, Class 2: -2.91 – \(\text{sepal-width}\); Class 0: -9.47, Class 2: 6.42 – \(\text{petal-length}\); Class 0: -10.65, Class 1: -4.34, Class 2: 5.77 – \(\text{petal-width}\); Class 1: -10.55, Class 2: 8.85 – \((\text{petal-length} \ge 5.76 \lor \text{petal-width} \ge 1.87)\); (Bias: Class 0: 2.70, Class 1: 8.71, Class 2: -2.82)

12 Quine-McCluskey↩︎

13 Ablation Studies↩︎

We conduct ablation studies to isolate the impact of specific components and hyperparameters within the TT-Sparse framework. In Figure 14, we analyze the effect of the number of thermometer bits \(b\) (i.e., the number of quantile-based thresholds per continuous feature) on both predictive performance and rule complexity. We observe a performance plateau beyond 7 bits, indicating that TT-Sparse effectively captures decision boundaries without requiring finer quantization. Figures 15 and 16 examine the model’s sensitivity to key structural parameters: the sparsity degree (number of input bits per LTT node), the model capacity (number of LTT nodes), and the temperature \(\tau\) of the Soft TopK operator. Finally, we validate the necessity of our hybrid design by ablating the global skip connections that link input features directly to the final classifier. We observe that removing this skip connection degrades performance.

13.1 TopK Necessity: Full Pareto Grids↩︎

Figure 18 shows the full performance–complexity Pareto frontiers for TT-Sparse and the three generic sparsification baselines from Section 4.1. Each point represents one \((\lambda, \text{seed})\) configuration. TT-Sparse consistently occupies the upper-left region (high performance, low complexity), while the baselines are pushed toward the right (high complexity) or bottom (low performance). Notably, FC + \(L_0\) gates on Abalone produces no extractable points at moderate \(\lambda\), and collapses to trivial predictions (\(R^2 \approx 0\)) at extreme \(\lambda\).

14 Expressivity Validation: Deep LTT↩︎

14.1 Architecture↩︎

Each standard LTT node computes a linear threshold function \(y_j(v) = \mathbf{1}(v^\top w^{(j)} + b_j > 0)\), which can only represent linearly separable Boolean functions. To test whether this restriction limits performance, we introduce a deep LTT variant that achieves universal Boolean expressivity per node. The architecture replaces the single linear combination with a two-path computation (Figure 19):

1. Hidden path (nonlinear): The \(k\) selected inputs pass through a hidden layer with \(H\) units (\(H = 2^k\) by default) and ReLU activation, followed by a linear output projection. This path can approximate any Boolean function given sufficient hidden units.

2. Skip path (linear): A direct linear combination of the \(k\) inputs (identical to the standard LTT computation), providing a residual connection.

The node output combines both paths: \(z_j(x) = \underbrace{h(x)^\top w_{\text{out}}^{(j)}}_{\text{hidden path}} + \underbrace{x_{\mathcal{I}_j}^\top w_{\text{skip}}^{(j)}}_{\text{skip path}} + b_j\), binarized as before via \(y_j = \mathbf{1}(z_j > 0)\). The same Soft TopK connection selection operates on both paths simultaneously through a shared mask.

14.2 Results↩︎

Synthetic expressivity. We train single-node models on all \(2^{2^3} = 256\) possible 3-bit Boolean functions. Deep LTT achieves 100% exact fit rate while the standard LTT fits only 40.6% (the linearly separable subset), confirming that the theoretical gap is real.

Real-world evaluation. We compare both variants across 27 datasets (14 binary, 6 multiclass, 7 regression) with full hyperparameter search and 5 seeds. Table 5 summarizes results by task type. The standard LTT wins on 24/27 datasets by predictive metric; deep LTT wins on only 3. Mean AUC/\(R^2\) deltas are consistently negative (deep minus standard), indicating the additional expressivity does not translate to gains on tabular data.

The linear threshold inductive bias acts as beneficial regularization: it constrains each node toward simple decision boundaries, which aligns with the structure of real tabular data. The standard LTT is therefore the appropriate default for interpretable rule learning.

References↩︎