betaFeedback

WorksComputer Science

Where to Approximate in Neurosymbolic Inference?

Abstract

Probabilistic neurosymbolic methods rely on weighted model counting (WMC) to combine neural predictors with symbolic constraints. Exact WMC is #P-hard and typically scales poorly, so many methods resort to approximations. By unifying existing approaches under a three-step bottom-up approximate compilation pipeline, we study where approximation budget is best allocated. Inspired by tensor networks, we instantiate two steps with tensor train decompositions and derive new pipelines that exactly multiply approximated factors and recompress their products via SVD- or interpolation-based schemes. Across six tasks in Sudoku, arithmetic reasoning, and scene understanding, and across increasing problem sizes, our pipelines produce WMC estimates orders-of-magnitude more accurate than prior methods. This translates into stronger downstream learning on tasks where reasoning relies on tight interactions between symbolic factors, where cruder approximations ignore these dependencies. Our pipelines open novel design space for effective approximate compilation of challenging probabilistic reasoning tasks.

Introduction

Probabilistic neurosymbolic (NeSy) systems combine neural perception with symbolic constraints, to enable learning from weak supervision [34, 67] or to inject symbolic knowledge into structured prediction pipelines [1]. Inference involves solving the weighted model count (WMC) problem [7]: computing the probability that a neural distribution over discrete concepts satisfies a constraint. Computing the WMC exactly is #P\#\mathrm{P}-hard in general [56]. One approach for solving practical instances tractably is circuit compilation which compiles the constraint into a logical circuit, a process also called knowledge compilation [15], while the neural distribution is turned into a probabilistic circuit [63, 9, 1]. Then, under certain structural properties, these circuits can be efficiently multiplied and summed over to yield the exact WMC [51, 64]. The same structural properties and multiplication operation are also behind popular bottom-up strategies for knowledge compilation [46, 14].

However, compilation is itself hard, and exactly multiplying several compiled circuits blows up exponentially in the number of factors [64]. This implies that compilation strategies can hit a wall on many real-world NeSy problems. Even compiling a 9×99 \times9 Sudoku board, often used in benchmarks [4, 66], as a constraint is out of reach for all exact compilers. Without surprise, many NeSy methods focused on approximate computation of the WMC [59, 53, 8, 16]. However, these approaches have carried over with different perspectives and from different communities. As such, the problem of understanding where and when to approximate in a systematic way is still open.

In this paper, we provide a unified view over many NeSy pipelines and we identify three stages at which approximations can enter Figure 1: (I) compiling each factor exactly or with a relaxed circuit, (II) multiplying factors exactly or via a recompression that controls size growth, and (III) combining remaining factors under an independence assumption. Many existing methods fit in this categorization, sometimes mixing several approximations. Independence (fuzzy) approximations are by far the most

Compilation strategies and approximation pipeline

Figure 1. Where can we approximate when compiling structured-decomposable circuits? We unify bottom-up approaches in a three-step pipeline: (Step I) compiles each factor ϕj\phi_j into an exact or relaxed circuit, (Step II) multiplies the resulting NN circuits down to KK exactly or using recompression strategies, and (Step III) combines any K>1K > 1 remaining circuits with an independence (fuzzy) approximation. Existing methods correspond to specific combinations of exact or approximate operations, but the framework also allows for new TT-based APRICOT strategies yet to be explored.

40th Conference on Neural Information Processing Systems (NeurIPS 2026). common [5, 58, 2] and are well known to support effective learning [58, 32], yet their inference fidelity is not well-studied. Stages (I) and (II) are far less explored. Drawing on the close connection between tensor networks and circuits [30], we instantiate stages (I) and (II) using tensor train (TT) decompositions. TTs have been used in NeSy to approximate and compress isolated factors [8] but not in a full compilation pipeline. We show how approximate tensor trains can be used for inference and compilation, deriving novel APRICOT pipelines.

Contributions. (i) We unify existing bottom-up compilation methods under a three-stage approximate-compilation pipeline and analyze how error and cost compose across strategies. (ii) Within this framework, we derive new approximation strategies based on TN recompressions, previously unexplored in NeSy or compilation. (iii) We map the compilation design space on Sudoku and evaluate weighted inference and learning on arithmetic and scene understanding tasks. We show that APRICOT pipelines scale beyond exact compilation, produce WMC estimates orders of magnitude more accurate than prior methods by preserving dependencies, which also translates to better learning in programs where factors are structurally tightly connected. Code and instructions for reproducing all experiments are available at github.com/sbadredd/apricot.

Probabilistic NeSy Models

A probabilistic NeSy model combines (i) a parameterized (neural) model pθ(c∣x)p_\theta(\mathbf{c} \mid\mathbf{x}) which maps the input x\mathbf{x} to a vector of discrete, symbolic concepts c=[ci]i=1,…,d\mathbf{c} = [c_i]_{i=1,\ldots,d}, ci∈Cic_i \in\mathcal{C}_i, with (ii) a symbolic constraint ϕ:C1×⋯×Cd→{0,1}\phi: \mathcal{C}_1 \times\cdots\times\mathcal{C}_d \to\{0,1\} that assesses the validity of the predicted concepts. In Sudoku, for example, x\mathbf{x} is the image of the board, c\mathbf{c} are the predicted digits in each cell, and ϕ\phi checks that the predicted digits satisfy the Sudoku rules. This involves computing pθ(ϕ∣x)p_\theta(\phi\mid\mathbf{x}) which maps the input x\mathbf{x} to the probability of satisfying the constraint ϕ\phi. This is known as a conditional weighted model count (WMC) problem, defined as1

pθ(ϕ∣x):=∑c∈Cpθ(c∣x) ϕ(c).(1)p_\theta(\phi\mid\mathbf{x}) := \sum_{\mathbf{c}\in\mathcal{C}} p_\theta(\mathbf{c} \mid\mathbf{x})\,\phi(\mathbf{c}). \tag*{(1)}

The problem can also be stated with ϕ(c,y)\phi(\mathbf{c},\mathbf{y}) being a program that maps concepts c\mathbf{c} to a supervised structured output y\mathbf{y}, in which case the WMC derives pθ(y∣x)p_\theta(\mathbf{y} \mid\mathbf{x}) (sometimes up to a normalization constant, see Section H.1 for details).

Often, ϕ\phi factorizes into a conjunction of subformulas ϕ1(c1)∧⋯∧ϕN(cN)\phi_1(\mathbf{c}_1) \land\cdots\land\phi_N(\mathbf{c}_N), where each factor ϕj\phi_j has scope cj⊆c\mathbf{c}_j \subseteq\mathbf{c}. For example, the 9×99 \times9 Sudoku rules decompose into N=810N = 810 factors that check pairwise constraints ci≠cjc_i \ne c_j for cells i,ji,j in the same row, column, or box. Programs may additionally introduce auxiliary symbolic variables, unweighted and unsupervised, to derive the factorization. For example, the arithmetic rules of addition, often explored in NeSy [11, 31], factorize using auxiliary carries between digits. This is further discussed in Section H.1.

Computing the WMC is #P-hard in general [56], and this is also due to the large combinatoric space of NeSy problems. E.g., in a 9×99 \times9 Sudoku there are 9819^{81} possible configurations, out of which only 6.67×10216.67 \times10^{21} are valid boards [19]. To solve this issue, probabilistic NeSy methods must use compilation techniques and/or relaxation strategies to make the WMC tractable.

Exact circuit compilation

A prominent approach to computing the WMC tractably is to represent both ϕ\phi and pθ(c∣x)p_\theta(\mathbf{c} \mid\mathbf{x}) as circuits and combine them [27, 34, 67, 1]. A circuit is a directed acyclic computational graph of weighted sum and product operations over tractable input functions [9, 64]. We focus on smooth and decomposable circuits, which support marginalization in time linear in their size. For tractable multiplication, circuits additionally need compatible decomposition structures: a circuit is structured-decomposable when its product units respect a common hierarchical partition of the variables (called a vtree), and two such circuits are compatible when these decompositions agree on shared variables [64]. Compatible circuits can be multiplied in polynomial time while preserving smoothness and decomposability. We defer formal definitions to Section A.

Knowledge compilation (KC) transforms a logical constraint ϕ\phi into a logical circuit, typically expressed using AND/OR gates [15]. For deterministic circuits, whose OR children have disjoint supports, AND/OR gates can be interpreted as product/sum operations without changing the represented Boolean function [25]. A deterministic compiled circuit for ϕ\phi can be multiplied tractably with a compatible probabilistic circuit pθ(c∣x)p_\theta(\mathbf{c} \mid\mathbf{x}).

Sentential decision diagrams (SDDs) [14] are a popular class of deterministic, structured-decomposable logical circuits. They can also be constructed bottom-up by multiplying circuit representations of factors ϕj\phi_j. Let KC⁡(ϕj)\operatorname{KC}(\phi_j) denote the circuit obtained by compiling factor ϕj\phi_j. We express bottom-up compilation using MUL:

∑c∈Cpθ(c∣x)MUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN))(c).(2)\sum_{\mathbf{c} \in\mathcal{C}} p_\theta(\mathbf{c} \mid\mathbf{x})\operatorname{MUL}\left(\operatorname{KC}(\phi_1), \ldots, \operatorname{KC}(\phi_N)\right)(\mathbf{c}). \tag*{(2)}

This is the classical recipe behind many approaches such as semantic loss [67] or DeepProbLog [34].

The main limitation is constructing a sufficiently compact circuit for ϕ\phi with the required structural properties. KC is at least NP-hard [15, 7], and, to the best of our knowledge, existing compilers cannot produce a polynomial-size circuit in reasonable time for a 9×99 \times9 Sudoku instance, even when relaxing structured decomposability [12, 28].2 Therefore, a common practice is to consider approximations. We focus on approximations which (i) apply to bottom-up circuit compilation, (ii) are differentiable. In Section B, we discuss other approaches to WMC in NeSy, such as amortized or sampling-based methods, and how they relate to our work.

Approximations

Independence approximations. A common approximation when multiplying two circuits is to assume they are independent, even if they are defined over the same set of variables. If we assume that, the WMC of their conjunction factorizes into the product of their WMCs. More formally,

∑c∈Cpθ(c∣x)MUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN))(c)≈∏j(∑cj∈Cjpθ(cj∣x)KC⁡(ϕj)(cj)).(3)\sum_{\mathbf{c} \in\mathcal{C}} p_\theta(\mathbf{c} \mid\mathbf{x})\operatorname{MUL}\left(\operatorname{KC}(\phi_1), \ldots, \operatorname{KC}(\phi_N)\right)(\mathbf{c}) \approx\prod_j \left(\sum_{\mathbf{c}_j \in\mathcal{C}_j} p_\theta(\mathbf{c}_j \mid\mathbf{x})\operatorname{KC}(\phi_j)(\mathbf{c}_j)\right). \tag*{(3)}

Often, ∣Cj∣≪∣C∣\lvert\mathcal{C}_j \rvert\ll\lvert\mathcal{C} \rvert, which makes the factor WMCs much easier to compute. Fuzzy NeSy approaches with product semantics [5, 17, 58] can be understood as probabilistic approaches relaxing all dependencies [57].3 The approximation is only correct when the factors ϕj\phi_j are independent, i.e., when the scopes cjc_j are pairwise disjoint. In general, this is not the case and the approximation can be arbitrarily bad, as we will show in our experiments. Still, in the context of differentiable learning, fuzzy relaxations are known to be effective in practice [58].

Fuzzy relaxations can be used in combination with exact circuit compilation. Semantic Strengthening [2] compiles SDD circuits for factor groups under a certain budget, prioritizing groups of factors with high mutual information, and applies the independence approximation between groups. SDDs are particularly suitable for this approach as they can iteratively multiply and analyze factors, making informed compilation or stopping decisions within the budget.

Factor approximations. Instead of approximating the marginalization step, one can approximate the factors themselves. This requires approximate compilation (AC) step, i.e.,

MUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN))≈FMUL⁡(AC⁡(ϕ1),…,AC⁡(ϕN))(4)\operatorname{MUL}(\operatorname{KC}(\phi_1),\ldots,\operatorname{KC}(\phi_N)) \mathrel{\overset{\mathrm{F}}{\approx}} \operatorname{MUL}(\operatorname{AC}(\phi_1),\ldots,\operatorname{AC}(\phi_N)) \tag*{(4)}

where AC compiles an approximated circuit in the real semiring for factor ϕj\phi_j, i.e., a circuit that does not encode a Boolean function but closely approximates it up to an ϵ\epsilon-error. Crucially, the circuit retains all the structural properties needed to tractably compute MUL. In Section 3, we discuss how each factor can be approximated with tensor trains (TTs) [43], a special family of tensorized circuits [30] for which there is a rich literature on function approximation [41]. Such a TT-approximated factor AC⁡(ϕj)\operatorname{AC}(\phi_j) can be a representation that is significantly smaller than the exact circuit KC⁡(ϕj)\operatorname{KC}(\phi_j), given that it can introduce negative parameters [29]. Additionally, TTs inherently handle categorical variables and do not need Boolean encoding.

CTSKETCH [8] is a recent approach that approximates factors ϕj\phi_j with low-rank TTs. However, CTSKETCH only considers programs that follow a certain tree-like independence structure, where any variable cic_i can appear in at most one factor. This applies to simple problems such as MNISTADD [34], but most programs, like Sudoku boards, have overlapping factors and violate this assumption. Therefore, CTSKETCH mixes factor approximations with fuzzy independence approximations ∏jpθ(cj∣x)AC⁡(ϕj)(cj)\prod_j p_\theta(c_j \mid x)\operatorname{AC}(\phi_j)(c_j). Section D details this. In Section 3, we show how to exactly multiply TT-approximated factors under more complex dependence structures.

Product approximations. Finally, we consider approximating the multiplication step directly, without going through intermediate approximations of the factors themselves, i.e.,

MUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN))≈PROUNDMUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN)).(5)\operatorname{MUL}(\operatorname{KC}(\phi_1),\ldots,\operatorname{KC}(\phi_N)) \mathrel{\overset{\mathrm{P}}{\approx}} \operatorname{ROUNDMUL}(\operatorname{KC}(\phi_1),\ldots,\operatorname{KC}(\phi_N)). \tag*{(5)}

Drawing on TN theory, we show that it is possible to derive algebraically-principled approximations which compress the product of circuits into smaller circuits. We denote such operations ROUNDMUL for rounded multiplications, inspired by the TT-ROUND [43] algorithm discussed in § 3.3. This direction is, to the best of our knowledge, unexplored in the NeSy or compilation literature, and can prove useful to approximate many operations on circuits.

Approximate Tensor Trains...

The tensor perspective applies to WMC by representing the constraint ϕ\phi as a Boolean-valued tensor X∈{0,1}n1×⋯×nd\mathcal{X} \in\{0,1\}^{n_1 \times\cdots\times n_d}, where ni=∣Ci∣n_i = \lvert C_i\rvert and X(c):=ϕ(c)\mathcal{X}(c) := \phi(c). This is an order-dd tensor: each mode corresponds to one variable cic_i, and its size nin_i is the number of values that variable can take. Thus, each tensor entry records whether a particular assignment satisfies the constraint. The dense representation contains ∏i=1dni\prod_{i=1}^{d} n_i entries, which quickly becomes infeasible to materialize as the number of variables grows. For example, the full 9×99 \times9 Sudoku constraint has d=81d = 81 variables, each with 9 possible values, giving an order-81 tensor with 9819^{81} entries.

Tensor trains (TTs) [43, 45] represent such tensors through a sequence of smaller tensors. They are a special case of tensor networks and can also be viewed as structured-decomposable circuits [30]. A TT represents an approximation X~\widetilde{\mathcal{X}} of an order-dd tensor X\mathcal{X} using one core per mode:

X(c1,…,cd)≈X~(c1,…,cd)=TX~1(c1)⋯TX~d(cd).\mathcal{X}(c_1,\ldots,c_d) \approx\widetilde{\mathcal{X}}(c_1,\ldots,c_d) = \mathcal{T}_{\widetilde{\mathcal{X}}_1}(c_1)\cdots\mathcal{T}_{\widetilde{\mathcal{X}}_d}(c_d).

Each core TX~k\mathcal{T}_{\widetilde{\mathcal{X}}_k} is an order-3 tensor of shape rk−1×nk×rkr_{k-1} \times n_k \times r_k. Fixing the variable value ckc_k selects a matrix slice TX~k(ck):=TX~k(:,ck,:)\mathcal{T}_{\widetilde{\mathcal{X}}_k}(c_k) := \mathcal{T}_{\widetilde{\mathcal{X}}_k}(:,c_k,:). The dimensions rkr_k are the TT ranks, with r0=rd=1r_0 = r_d = 1 so that multiplying all selected matrices returns a scalar. Writing n=max⁡knkn = \max_k n_k and r=max⁡krkr = \max_k r_k, TT storage is O(dnr2)O(dnr^2), compared with up to O(nd)O(n^d) entries in the dense tensor. The representation is therefore compact when the ranks remain small. We now use this representation to approximate individual constraint factors, multiply the resulting TTs, and recompress their products.

Closed algebra over tensor trains

Figure 2. Closed algebra over TTs. TTs (a) can approximate discrete functions under an error criterion and (b) are closed under several exact operations including multiplications. As multiplications involve Kronecker products ⊗\otimes of the cores resulting in an exponential increase in rank, algebraic recompression strategies (c) can approximate the result of the operations.

TT Factor Approximations

A factor ϕj\phi_j with scope cjc_j of size djd_j corresponds to an order-djd_j tensor Xj\mathcal{X}_j. For example, each pairwise Sudoku constraint ci≠clc_i \ne c_l is an order-2 tensor: a 9×99 \times9 matrix with zeros on the diagonal and ones elsewhere. While the full constraint tensor is generally too large to materialize, these factor tensors are often small enough to construct explicitly and approximate using TT-SVD.

We approximate each dense factor tensor using TT-SVD [43], as in CTSKETCH [8]. The algorithm constructs a TT X~j\widetilde{\mathcal{X}}_j under either a prescribed Frobenius error tolerance ∥Xj−X~j∥F≤ϵj\lVert\mathcal{X}_j-\widetilde{\mathcal{X}}_j\rVert_F \le\epsilon_j or a maximum TT rank RR. For prescribed ranks, TT-SVD is quasi-optimal: its error is within a factor dj−1\sqrt{d_j-1} of the best approximation with those ranks. Importantly, TT-SVD requires its dense input to be materialized, which motivates applying it to the small factor tensors rather than to the full constraint. The resulting TTs must then be combined (i.e., multiplied) while accounting for dependencies between their overlapping scopes.

Exact multiplication of TTs

TTs are closed under element-wise (Hadamard) multiplication, which allows us to compile TT-approximated factors without introducing new approximations. The operation requires matching scopes and mode orderings. We fix a global variable ordering and arrange each factor’s modes accordingly. Before multiplying factors with different scopes, we broadcast their TTs to the union of their scopes by inserting identity cores for missing variables. The construction and a heuristic for choosing the global ordering are detailed in Section F.2.

Consider two TTs Xj\mathcal{X}_j and Xl\mathcal{X}_l after broadcasting to a common scope of qq variables, locally indexed c1,…,cqc_1,\ldots,c_q. Their product X∗=Xj∗Xl\mathcal{X}^*=\mathcal{X}_j * \mathcal{X}_l has cores

TX∗,k(ck)=TXj,k(ck)⊗TXl,k(ck),k=1,…,q,(6)\mathcal{T}_{\mathcal{X}^*,k}(c_k)=\mathcal{T}_{\mathcal{X}_j,k}(c_k)\otimes\mathcal{T}_{\mathcal{X}_l,k}(c_k),\qquad k=1,\ldots,q, \tag*{(6)}

where ⊗\otimes denotes the matrix Kronecker product. This is a special case of the MUL operation for compatible structured-decomposable circuits which maintains a TT structure. Because of the Kronecker, the product ranks are rk∗=rkjrklr_k^*=r_k^j r_k^l. Thus, two TTs with ranks bounded by rr can produce a TT with ranks up to r2r^2 and storage O(qnr4)O(qnr^4). Repeatedly multiplying mm such TTs can require O(qnr2m)O(qnr^{2m}) storage in the uncompressed representation. This matches the worst-case exponential complexity of circuit multiplication [64]. Exact multiplication therefore preserves dependencies between factors, but its rank growth motivates recompression.

Approximate multiplications of TTs

To control rank growth, we approximate the product X∗\mathcal{X}^* by a TT with a target maximum rank RR. Unlike factor approximation with TT-SVD, this product recompression operates directly on the input TTs, without materializing the dense product. Depending on the method, the recompression can alternatively be controlled by a truncation tolerance ϵ\epsilon. We consider four strategies, distinguished by their compression mechanism (SVD or interpolation) and their use of deterministic or randomized compression directions. Algorithmic details are deferred to § 17.

TT-ROUND [43] (SVD, deterministic/site-randomized) uses successive SVD-based truncations to reduce TT ranks. For Hadamard products, we exploit the Kronecker structure to interleave products and compressions without materializing the Kronecker product cores. We consider both deterministic and randomized per-site SVDs [23].

HATT [55] (SVD, randomized) uses a random TT sketch of the product to identify compression subspaces, then applies SVDs to small sketched matrices. Its randomization acts at the TT level, rather than independently within each local SVD.

TCI [39, 42] (interpolation, deterministic) constructs a TT approximation from selected entries of the product, choosing representative rows and columns through maxvol-based cross interpolation [20].

RSI [38] (interpolation, randomized) combines random sketching with interpolative decompositions. It replaces TCI’s maxvol-based initialization with sketched environments built from the input TTs. We extend its original single left-to-right sweep to alternating left-to-right and right-to-left sweeps, using the connection to TCI (details in § 17.4).

From tensor error to WMC error

The Frobenius guarantees provided by TT-SVD and SVD-based recompression translate to a bound on the final inference error. Let X~\widetilde{\mathcal{X}} approximate the full constraint tensor X\mathcal{X}, with ∥X~−X∥F≤ϵ\lVert\widetilde{\mathcal{X}}-\mathcal{X}\rVert_F \le\epsilon, and let P(c)=pθ(c∣x)\mathcal{P}(\mathbf{c}) = p_\theta(\mathbf{c}\mid\mathbf{x}). Since the WMC pθ(ϕ∣x)p_\theta(\phi\mid\mathbf{x}) in Equation (1) is the Frobenius inner product of these tensors, Cauchy-Schwarz gives

∣WMC^−WMC∣≤ϵ∥P∥F≤ϵ.(7)\left|\widehat{\mathrm{WMC}}-\mathrm{WMC}\right| \le\epsilon\lVert\mathcal{P}\rVert_F \le\epsilon. \tag*{(7)}

The last inequality follows because P\mathcal{P} is a normalized probability tensor. More details are given in Section C, including how the factor errors ϵ\epsilon propagate under multiplications.

…for Inference and Compilation

We now combine these ingredients into the TT-based framework APRICOT: APproximate Representations for Inference and COmpilation using Tensor trains. We describe instantiations of this framework within a unified bottom-up pipeline that also accommodates exact circuit compilation and some pre-existing approximation strategies (Figure 1). Given a constraint ϕ=ϕ1∧⋯∧ϕN\phi=\phi_1\land\cdots\land\phi_N, the pipeline has three stages: compiling factors, multiplying their circuit representations, and evaluating the remaining circuits. The choices at each stage decide whether factor, product, and/or independence approximations are involved.

Step I: Factor compilation. Each factor is represented by a circuit. Exact compilation constructs KC(ϕj)\mathrm{KC}(\phi_j), for which we use SDDs [14]. Alternatively, APRICOT applies TT-SVD to the dense factor tensor Xj\mathcal{X}_j, with an initial rank budget RinitR_{\mathrm{init}} or a Frobenius error tolerance (see § 3.1). Before TT decomposition, small factors may optionally be grouped and pre-multiplied exactly in dense tensor space. This captures dependencies within each group before introducing a factor approximation, as long as the grouped tensor fits in memory. Let MM denote the number of circuits resulting from this stage. Without grouping, M=NM=N. All circuits use compatible decomposition structures (in the case of TTs, variable orderings) so that they can subsequently be multiplied.

Step II: Multiplication (M→KM\to K). The MM circuits are reduced to KK circuits through pairwise multiplications, where 1≤K≤M1\le K\le M. Exact multiplication uses SDD Apply for SDDs or the TT product of § 3.2. For APRICOT, the propagation of existing factor errors is analyzed in Section C. To control the growth of intermediate TTs, APRICOT can instead use recompressed multiplication, with any of the strategies introduced in § 3.3. Recompression introduces additional approximation error in exchange for smaller representations. The multiplication schedule, recompression strategy, and stopping criterion are all parameters of the pipeline. For example, KK may be prescribed or determined by the available resources and approximation conditions. Our experimental choices are specified in Section 5.

Step III: Final independent reduction (K→1K \to1). Let ϕ~1,…,ϕ~K\tilde{\phi}_1, \ldots, \tilde{\phi}_K be the remaining circuits, with scopes c1,…,cK\mathbf{c}_1, \ldots, \mathbf{c}_K. We compute their individual WMCs and combine them as

p^θ(ϕ∣x)=∏k=1K(∑ck∈Ckpθ(ck∣x)ϕ~k(ck)),\hat{p}_{\theta}(\phi\mid\mathbf{x}) = \prod_{k=1}^{K} \left( \sum_{\mathbf{c}_k \in\mathcal{C}_k} p_{\theta}(\mathbf{c}_k \mid\mathbf{x}) \tilde{\phi}_k(\mathbf{c}_k) \right),

where Ck\mathcal{C}_k is the assignment space of the kk-th residual scope. For K>1K > 1, this applies the independence approximation between remaining factors (Equation (3)). The introduced error is difficult to predict and depends on the specific factors remaining after Step II (Section E).

Figure 1 maps existing approaches and new APRICOT variants as different choices in each step of the pipeline. Exact compilation and multiplication to K=1K = 1 is exact inference, while stopping earlier gives the grouped independence strategy used, for example, by Semantic Strengthening. TT factor approximation followed directly by independent reduction gives the CTSKETCH-style approximation for overlapping factors, a special case of APRICOT. Variants can additionally combine them: APRICOT A combines TT factors through exact multiplications before an independence reduction, APRICOT B additionally uses product recompression up to a budget, while APRICOT C avoids the final independence approximation. Notice that each row in Figure 1 identifies a family rather than a fixed configuration: ranks, multiplication schedules, and reduction targets can vary across tasks. In particular, we detail different multiplication schedules we evaluate in Section G.2.

Experiments

We first explore the compilation design space on Sudoku, a popular NeSy benchmark [4, 66] with a complex dependence structure, and evaluate in-depth where to introduce approximation during compilation. We then compare representative pipelines on arithmetic and scene-understanding tasks of increasing difficulty. Finally, we address whether accurately compiling dependencies improves neurosymbolic learning across these settings.

Tasks. For the compilation ablation, we use Sudoku boards of size 4×44 \times4, 6×66 \times6, and 9×99 \times9, where known model counts derived analytically [19] allow us to evaluate unweighted approximation quality. For learning, we use two Visual Sudoku tasks. ViSudo-Classification predicts whether a board of MNIST images satisfies the Sudoku rules, using the dataset from Augustine et al. [4]. ViSudo-Completion predicts missing cells from the observed digit images, using the SatNet dataset [66] with the data-leak correction of Chang et al. [6]. We additionally evaluate four tasks for both weighted inference and learning. MNISTAdd [34] and MNISTMul predict the sum or product of two LL-digit numbers represented by MNIST images, with supervision only on the result. CLEVR-Diff predicts whether all objects in a CLEVR scene [24] have different attribute tuples (color, shape, …), while CLEVR-CountDiff predicts the number of distinct attribute tuples in the scene. We construct the CLEVR tasks reusing scenes from Stammer et al. [54].

These tasks differ in how their programs factorize. In particular, the arithmetic and distinct-counting programs introduce auxiliary symbolic variables such as carries and running counts to express the constraint with smaller factors (see Section H.3 for details). In comparison, our Sudoku and CLEVR-Diff factorizations directly compare perceptual concepts and do not introduce such intermediate symbols. This will prove meaningful when analyzing the NeSy learning results.

Baselines. We use the family names introduced in Figure 1. The Sudoku compilation ablation explores many configurations within these families, while the learning experiments evaluate only selected representatives. On the arithmetic and CLEVR tasks, we compare three strategies: full independence reduction (LTN/DFL-style), full exact compilation (Semantic Loss/DeepProbLog-style), and full TT compilation allowing product recompression (APRICOT C). As explained in Section 4, the names identify families; the exact configurations (ranks, multiplication schedules) depend on the specific task programs and are detailed in Section H.5.

We implement all TT algorithms in PyTorch [44], use PySDD [37] for SDD compilation, and K_Lay [33] for GPU inference on SDDs. Results are averaged over 7 runs with errors bars for standard deviation. Hardware and training protocols are given in Section H.5.

Sudoku compilation ablation

Figure 3 compares compilation time and model-count error on the larger boards. We vary the number and type of the multiplications (exact or recompressed) as well as the rank for the initial TT-SVD.

Pareto fronts of absolute log inference error versus compilation time for Sudoku 6x6 and 9x9

Figure 3. Pareto front of absolute log inference error vs. compilation time for Sudoku 6x6 (left) and 9x9 (right). SDD pipelines are in yellow ●. APRICOT pipelines are in blue ● when they do not use recompressions, in violet ● when they use SVD-based recompressions (TT-ROUND ● and HATT ◆) and in green for interpolation-based strategies (TCI ● and RSI ◆).

Each point in the plot is a candidate compilation pipeline; details on our grid search and on the tags we use to identify points are in Section H.2. Below, we highlight trends in the results.

We measure absolute errors on a logarithmic scale ∣log⁡10MC/MCref∣|\log_{10} \mathrm{MC}/\mathrm{MC}_{\mathrm{ref}}|, with zero indicating an exact count. The model count estimates are obtained by calculating the WMC under a uniform distribution, which gives the probability of an assignment being a model, multiplied by the size of the assignment space. The ground-truth counts are 288, 28,200,960, and approximately 6.67×10216.67 \times10^{21} for the three board sizes. 4×44 \times4 serves as a sanity check, with both exact SDD compilation and suitable TT configurations recovering its count to numerical precision (Section H.2.3). 6×66 \times6 is already challenging: compilation is only possible with the best non-structured-decomposable compilers like d4 [28], not with SDDs. To the best of our knowledge, 9×99 \times9 is unsolved by any existing compilers.

On independence approximations. As expected from our error analysis and discussion on fuzzy bounds (Section C), the fuzzy approximations of the WMC have unpredictable behaviors which vary with the encoding used. Even at matched KK, SDD (yellow) and APRICOT behave very differently. In practice, the MC estimate of SDD+Fuzzy is approximately zero, making it hardly usable.

On exact multiplications. Combining factors before independence reduction always significantly improves fidelity. However, both SDD size and TT ranks limit how far exact multiplication scales. Factor approximations can compress initial factors, but their products still grow exponentially.

On approximate multiplications. Recompression allows further multiplications and provides the strongest accuracies. The SVD-based strategies are more reliable than the interpolation-based alternatives, with no significant difference between randomized strategies. In both cases, however, attempting too many multiplications under a limited rank budget can also degrade the representation because of expressivity limitations. To distinguish count accuracy from constraint fidelity, we additionally evaluate how well each circuit separates satisfying assignments from nonsatisfying assignments. We measure this using average precision on 1000 model and 1000 non-model sudoku samples, evaluating the product of the current factors indexed on each sample. On 9×99 \times9, we find points (marked “low AP”) which, after much recompression, achieve good aggregate error but miss the actual models. This highlights the importance of halting compilation based on the accumulated Frobenius error bound (Section C) once it exceeds a certain tolerance.

Weighted inference

Next, we evaluate whether the compilation strategies remain effective when querying the circuits with weights. We compare circuit estimates with exact compilation or task-specific exact references under 64 shared random weightings. For each weighting, we compute the absolute base-10 log-ratio between the estimated and reference WMC, and report the median of these 64 errors alongside compilation time (Figure 4). That is, a reported error of 1 means that, for a typical sampled weighting, the estimated WMC differs from the reference by a factor of 10. Details are specified in Section H.4.

Figure 4. Median absolute log WMC error and compilation time across tasks and problem sizes. Exact SDD compilation becomes infeasible on harder problems. Full TT reduction (APRICOT C) can scale further while producing estimates orders of magnitude more accurate than fuzzy. On MNISTAdd, both SDDs with a suitable vtree and APRICOT exploit the carry-chain structure to scale efficiently with the number of digits. On the more challenging CLEVR-Diff, MNISTMul, and CLEVR-CountDiff, APRICOT C scales beyond the evaluated SDD compiler. At the same time, its WMC estimates are substantially more accurate than those obtained by independence reduction. Independence reduction is inexpensive at the cost of inference fidelity, but TT recompression provides a practical trade-off, retaining these dependencies approximately in a manageable representation.

Learning

Previous works have found that faithful inference is not always a requirement for competitive downstream learning. Indeed, despite ignoring dependencies, fuzzy systems provide good differentiability in many use cases [5] and can behave surprisingly well as gradient estimators [32]. We explore whether this holds across more complex settings.

We measure the concept accuracy as the fraction of individual concepts c\mathbf{c} predicted correctly (digits or object keys) and the output accuracy yy as a per-instance exact accuracy (e.g., all missing cells must be correct for Sudoku completion, all output digits must be correct for arithmetic). Notice that output accuracy can decline with problem size even when individual concepts and reasoning remain accurate: for two inputs with LL digits, independent digit errors at 99% accuracy gives a probability of all inputs being correct 0.992L0.99^{2L} (about 13% at L=100L = 100), which is necessary for per-instance output accuracy. For ViSudo-Classification and both CLEVR tasks, we evaluate concept accuracy up to a permutation given that the exact concepts c\mathbf{c} are not identifiable from the label signal [35, 36]. More details are provided in Section H.5.

We find a clear contrast depending on the task constraint. Independence reduction is competitive on Visual Sudoku and CLEVR-Diff (first three columns in Figure 5) with all baselines achieving close to 99% concept accuracy, leaving little room for improvement. However, preserving dependencies improves learning on the arithmetic and CLEVR-CountDiff programs (last three columns). We hypothesize that this is due to factorizations introducing auxiliary symbolic variables. For example, in MNISTAdd, the constraint (detailed in Section H.3) has factors at each position kk

Figure 5. Concept and output accuracy across tasks and problem sizes. APRICOT matches exact compilation when the latter is feasible, and outperforms fuzzy in larger regimes.

Ak+Bk+Ck−1=Yk+10CkA_k + B_k + C_{k-1} = Y_k + 10 C_k

where the perception network predicts input digits AkA_k, BkB_k, derives an output YkY_k, and introduces carries CkC_k. The carry CkC_k is an unweighted auxiliary symbol that denotes the part of the result at position kk which exceeds 10 and rolls over position k+1k + 1. Its value must agree between the factors at these two positions, and jointly marginalizing them enforces this agreement. On the other hand, independently marginalizing the factors permits inconsistent carries which weakens the propagation of the supervised signal from YkY_k to the perceived AkA_k, BkB_k. This matters for learning concepts and inferring outputs in more complicated settings (arithmetic as NN grows, or CountDiff for any mm).

In such settings, exact compilation and APRICOT C preserves agreements between factor computations and vastly outperforms the fuzzy baseline. Notice that this gap is not domain dependent as exemplified by the contrast between CLEVR-Diff and CLEVR-CountDiff, highlighting the importance of the constraint structure.

Larger error bars sometimes reflect optimization failures. For example, on CountDiff with m=8m = 8 and m=16m = 16, respectively one and three of ten APRICOT runs fail to converge, or on arithmetic nearly half of the fuzzy seeds. Task-specific tuning may reduce these failures, but the aggregate results support the trends discussed above. We also note that on MNISTMul, fuzzy uses a different factorization because the finer encoding used by SDD and APRICOT would give vanishing gradients (details in Section H.3.1). Its dense initial factors are thus larger and exceed GPU memory at L=3L = 3.

Conclusions

We unify existing bottom-up compilation methods for WMC under a modular pipeline (Figure 1) and instantiate previously unexplored configurations via tensor-train decompositions (APRICOT). APRICOT combines TT factor representations with exact and recompressed multiplication, improving inference fidelity while extending the scale of feasible compilation. Our learning experiments show that independence reduction can be effective, but that preserving dependencies matters when local computations must relate shared auxiliary variables.

Limitations. Most TT decompositions and recompressions – particularly TCI and RSI– are not specifically tailored to sparse Boolean tensors. Future work should develop methods specific to this regime. Our results also motivate an extended study on how program factorization (particularly auxiliary-variable structure) impacts gradient-based learning beyond compiled NeSy methods.

Acknowledgements

We would like to thank Lorenzo Loconte, Christoph Staudt, Andreas Grivas and Joan Serrà for fruitful discussions during the writing of this paper. Emile van Krieken was funded by the NWO AiNed project “Human-Centric AI Agents with Common Sense” (NGF.1607.22.044). Luciano Serafini was funded by the NRRP project Future AI Research (FAIR - PE00000013) under the NRRP MUR program, funded by NextGenerationEU. Antonio Vergari was supported by the “UNREAL: Unified Reasoning Layer for Trustworthy ML” project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC.

Author contributions. The core ideas were born when SB visited the University of Edinburgh under the supervision of AV. AV ideated approximating factors with non-deterministic circuits which SB implemented with tensor trains, further exploring product approximations. EvK and LS provided continuous and invaluable feedback throughout the project. SB conceived and implemented the experiments with guidance from AV and EvK. EvK also helped in running baseline experiments. All authors contributed to writing.

AI use statement. We used generative AI tools to assist in implementing the MNIST arithmetic and CLEVR experiments, for plotting, for designing the groundtruth dynamic programming solutions in weighted inference (see Section H.4), for drafting some of the appendices, and for reviewing the manuscript before submission. The main manuscript was entirely written by the authors. APRICOT was also manually implemented by the authors, only using AI for reviewing the code. All generated content was reviewed by the authors. We take responsibility for the final content of this work, including text and artifacts produced with the aid of generative AI.

References

Circuits

Background

We first define circuits abstractly over a semiring, which allows us to distinguish the logical and probabilistic representations used in NeSy AI.

Definition A.1 (Circuit [9, 64, 25]). Let (S,⊕,⊗,0,1)(\mathcal{S}, \oplus, \otimes, 0, 1) be a commutative semiring. A circuit f(z)f(\mathbf{z}) is a directed acyclic computational graph whose intermediate units compute ⊕\oplus and ⊗\otimes operations over tractable input functions of variables z\mathbf{z}.

Different choices of semiring recover the circuit representations commonly used in probabilistic inference and knowledge compilation. Probabilistic circuits (PCs) [13, 63, 9] operate over the non-negative real semiring (R≥0,+,×,0,1)(\mathbb{R}_{\ge0}, +, \times, 0, 1) and encode non-negative functions; their sum-unit weights are typically constrained to be non-negative [29, 30]. In contrast, logical circuits are conventionally defined over the Boolean semiring ({0,1},∨,∧,0,1)(\{0,1\}, \lor, \land, 0, 1) as DAGs whose internal units are logical OR/AND operations and whose inputs represent logical literals [15].

Tractable computation of multiplication and marginalization over arithmetic circuits requires certain structural properties, which we briefly discuss next. We refer the reader to Choi et al. [9] for details.

We focus on circuits that are smooth, i.e., all inputs of sum units are defined over the same variables, and decomposable, i.e., inputs of product units are defined over disjoint sets of variables. These properties enable tractable marginalization in time linear in the circuit size [9].

For tractable circuit multiplication, stronger structural constraints are required. A decomposable circuit is structured-decomposable if its product units respect a common hierarchical partition of the variables, typically represented by a vtree. Two structured-decomposable circuits are compatible [64] when their decompositions agree on their shared variables. Compatible circuits can be multiplied in time polynomial in their sizes while preserving smoothness and decomposability.

Probabilistic NeSy reasoning

To use a logical circuit together with a PC, we first cast the logical circuit into the real sum-product semiring. This conversion is sound for deterministic logical circuits, whose OR units have children with disjoint supports. For such circuits, at most one child of each OR unit evaluates to 1 for any assignment, and hence Boolean OR can be replaced by real addition and AND by multiplication without changing the encoded Boolean function. The resulting arithmetic circuit has unit weights equal to 1 at the former OR units.

Consequently, if ϕ\phi is represented by a smooth, decomposable, deterministic logical circuit, its arithmetic representation is compatible with the PC pθ(c∣x)p_{\theta}(\mathbf{c}|\mathbf{x}), and the two can be multiplied tractably, then Equation (15) can be computed exactly and efficiently. A first requirement is therefore constructing from ϕ\phi a logical circuit with the required structural properties, a task known as knowledge compilation (KC) and which is at least NP-hard [15, 7].

Most widely used KC software operates on propositional formulas and outputs circuits over Boolean variables.4 Thus, the propositionalization overhead reported here reflects our use of available Boolean KC implementations, rather than a fundamental requirement of circuit representations.

Sentential decision diagrams (SDDs) [14] are a popular class of deterministic and structured-decomposable logical circuits for KC. After interpreting their deterministic OR/AND units in the real sum-product semiring, they can be combined with compatible PCs pθ(c∣x)p_{\theta}(\mathbf{c}|\mathbf{x}). They can also be constructed bottom-up by multiplying circuit representations of factors ϕj\phi_j.

Let KC⁡(ϕj)\operatorname{KC}(\phi_j) denote the arithmetic circuit obtained by compiling factor ϕj\phi_j into a deterministic logical circuit and interpreting it in the sum-product semiring. We rewrite the WMC using the symbolic operator MUL, which takes a set of compatible circuits as input and returns a circuit representing their product:

∑c∈Cpθ(c∣x)MUL⁡(KC⁡(ϕ1),…,KC⁡(ϕN))(c).(8)\sum_{c \in\mathcal{C}} p_{\theta}(c \mid x)\operatorname{MUL}\left(\operatorname{KC}(\phi_{1}),\ldots,\operatorname{KC}(\phi_{N})\right)(c). \tag*{(8)}

This is the classical recipe underlying many NeSy approaches, including semantic loss [67] and DeepProbLog [34].

Related Work

Knowledge compilation. Compilers more permissive than SDDs handle larger formulas at the cost of compositionality with other circuits. d4 [28] is an exact compiler for d-DNNF, a broader class than SDDs that drops structured-decomposability. It scales to formulas no SDD compiler can handle (e.g., 6x6 Sudoku, though still not 9x9), but the resulting circuits can only be weighted by fully-factorized probabilities, an independence assumption known to lack expressivity in practice [1, 60, 61]. Dierckx et al. [16] propose an approximate variant of d-DNNF compilation, which enumerates a budget-limited set of models into a DNF to derive lower- and upper-bound circuits. While these provide provable intervals, the resulting circuits are again not structured-decomposable, making them orthogonal to our target. Onaka et al. [40] treat TTs themselves as a target for exact factor compilation, using them in the knowledge-compilation map alongside NNF subsets and showing they are strictly more succinct than OBDDs while supporting the same polytime operations. This corresponds to combining TT factors via exact multiplications without TT-SVD approximation or product recompression, and inherits the same exponential blow-up under multiplication that motivates the approximate strategies we study.

Scalable inference in NeSy. Other approaches avoid circuit compilation entirely. A-NeSI [59] trains a neural network to amortize WMC inference, which are more expressive than circuits. Like APRICOT (but unlike SDD pipelines), A-NeSI can also learn the logic of black-box programs using input-output examples. However, the neural approach offers no formal error guarantees and gives a representation that does not support downstream tractable operations such as multiplication with other circuits or conditioning on evidence. Monte Carlo methods [32, 53, 65, 62] sample concept assignments to estimate gradients, which also extends to continuous settings, but Maene et al. [32] show that the underlying gradient estimation from samples is itself #P-hard and can require an exponential number of samples to converge. Naturally, they also do not produce circuits that can be reused for downstream operations, targeting a different use case than ours.

Error bounds

We investigate how the different approximations impact the final WMC error. The independence approximation is crude, with an unbounded error. This approximation depends not only on the program semantics but also on how it is represented, which can lead to unpredictable behavior. As we will see in our results and as we derive analytically in Section E, the independence approximation for Sudoku derives estimates that vary by many orders of magnitude depending on the encoding used (categorical or binary).

The other approximations have more controlled error propagation. First, the ϵ\epsilon error bound on the factor approximation introduced by TT-SVD in APRICOT pipelines propagates linearly with the number of factors when multiplying them exactly.

Theorem C.1. Let X∗=Xj∗Xl\mathcal{X}^{*} = \mathcal{X}_{j} * \mathcal{X}_{l} the element-wise product of two tensors. Let X~∗=X~j∗X~l\widetilde{\mathcal{X}}^{*} = \widetilde{\mathcal{X}}_{j} * \widetilde{\mathcal{X}}_{l}, where ∥Xj−X~j∥F≤ϵj\lVert\mathcal{X}_{j} - \widetilde{\mathcal{X}}_{j} \rVert_{F} \le\epsilon_{j} and ∥Xl−X~l∥F≤ϵl\lVert\mathcal{X}_{l} - \widetilde{\mathcal{X}}_{l} \rVert_{F} \le\epsilon_{l}. Then, ∥X∗−X~∗∥F≤∥Xj∥∞ϵl+∥Xl∥∞ϵj+ϵjϵl\lVert\mathcal{X}^{*} - \widetilde{\mathcal{X}}^{*} \rVert_{F} \le\lVert\mathcal{X}_{j} \rVert_{\infty} \epsilon_{l} + \lVert\mathcal{X}_{l} \rVert_{\infty} \epsilon_{j} + \epsilon_{j}\epsilon_{l} where ∥Xj∥∞=max⁡c1,…,cd∣Xj(c1,…,cd)∣\lVert\mathcal{X}_{j} \rVert_{\infty} = \max_{c_{1},\ldots,c_{d}} \lvert\mathcal{X}_{j}(c_{1},\ldots,c_{d}) \rvert is the max norm.

Proof. Let Δj=X~j−Xj\Delta_{j} = \widetilde{\mathcal{X}}_{j} - \mathcal{X}_{j} and Δl=X~l−Xl\Delta_{l} = \widetilde{\mathcal{X}}_{l} - \mathcal{X}_{l}, so that ∥Δj∥F≤ϵj\lVert\Delta_{j} \rVert_{F} \le\epsilon_{j} and ∥Δl∥F≤ϵl\lVert\Delta_{l} \rVert_{F} \le\epsilon_{l}. Expanding the product,

X∗−X~∗=Xj∗Xl−(Xj+Δj)∗(Xl+Δl)=−Xj∗Δl−Δj∗Xl−Δj∗Δl.\mathcal{X}^{*} - \widetilde{\mathcal{X}}^{*} = \mathcal{X}_{j} * \mathcal{X}_{l} - (\mathcal{X}_{j} + \Delta_{j}) * (\mathcal{X}_{l} + \Delta_{l}) = -\mathcal{X}_{j} * \Delta_{l} - \Delta_{j} * \mathcal{X}_{l} - \Delta_{j} * \Delta_{l}.

By the triangle inequality,

∥X∗−X~∗∥F≤∥Xj∗Δl∥F+∥Δj∗Xl∥F+∥Δj∗Δl∥F.\left\|\mathcal{X}^{*}-\widetilde{\mathcal{X}}^{*}\right\|_{F}\leq\left\|\mathcal{X}_{j}*\Delta_{l}\right\|_{F}+\left\|\Delta_{j}*\mathcal{X}_{l}\right\|_{F}+\left\|\Delta_{j}*\Delta_{l}\right\|_{F}.

For any two tensors A,B\mathcal{A},\mathcal{B} of matching shape, the Hadamard product satisfies ∥A∗B∥F≤∥A∥∞∥B∥F\|\mathcal{A}*\mathcal{B}\|_{F}\leq\|\mathcal{A}\|_{\infty}\|\mathcal{B}\|_{F}—follows from ∑c(A(c)B(c))2≤max⁡cA(c)2∑cB(c)2=∥A∥∞2∥B∥F2\sum_{c}(\mathcal{A}(c)\mathcal{B}(c))^{2}\leq\max_{c}\mathcal{A}(c)^{2}\sum_{c}\mathcal{B}(c)^{2}=\|\mathcal{A}\|_{\infty}^{2}\|\mathcal{B}\|_{F}^{2}. Applied to the first two terms,

∥Xj∗Δl∥F≤∥Xj∥∞∥Δl∥F≤∥Xj∥∞ϵl,∥Δj∗Xl∥F≤∥Xl∥∞∥Δj∥F≤∥Xl∥∞ϵj.\begin{aligned} \|\mathcal{X}_{j}*\Delta_{l}\|_{F}&\leq\|\mathcal{X}_{j}\|_{\infty}\|\Delta_{l}\|_{F}\leq\|\mathcal{X}_{j}\|_{\infty}\epsilon_{l},\\ \|\Delta_{j}*\mathcal{X}_{l}\|_{F}&\leq\|\mathcal{X}_{l}\|_{\infty}\|\Delta_{j}\|_{F}\leq\|\mathcal{X}_{l}\|_{\infty}\epsilon_{j}. \end{aligned}

For the third term, the LpL^{p}-norm inequality ∥Δl∥∞≤∥Δl∥F\|\Delta_{l}\|_{\infty}\leq\|\Delta_{l}\|_{F} (treating the tensor as a vector) gives

∥Δj∗Δl∥F≤∥Δl∥∞∥Δj∥F≤ϵlϵj.\|\Delta_{j}*\Delta_{l}\|_{F}\leq\|\Delta_{l}\|_{\infty}\|\Delta_{j}\|_{F}\leq\epsilon_{l}\epsilon_{j}.

Summing the three bounds yields the claim.

As we study boolean tensors, small ϵj\epsilon_{j} implies ∥Xj∥∞≈1\|\mathcal{X}_{j}\|_{\infty}\approx1 and thus the error on X∗\mathcal{X}^{*} is O(ϵi+ϵj)O(\epsilon_{i}+\epsilon_{j}). By extension, for NN factors, the error on X∗\mathcal{X}^{*} is O(Nϵ)O(N\epsilon) where ϵ=max⁡jϵj\epsilon=\max_{j}\epsilon_{j}.

Recompression after multiplication (§ 3.3) introduces additional errors specific to each strategy. Deterministic TT-ROUND, in particular, can maintain guarantees on the Frobenius error of the recompressed product, which adds to the error of the exact result [43].

Reusing Theorem C.1 and considering the weight tensor P\mathcal{P} such that P(c)=pθ(c∣x)\mathcal{P}(c)=p_{\theta}(c\mid x), we first bound the error before the final contraction.

Corollary C.2 (Weighted-tensor error). Let X~\widetilde{\mathcal{X}} be an ϵ\epsilon-approximation of X\mathcal{X}, and let P\mathcal{P} be a tensor of weights. Then

∥P∗X~−P∗X∥F≤∥P∥∞ϵ.(9)\|\mathcal{P}*\widetilde{\mathcal{X}}-\mathcal{P}*\mathcal{X}\|_{F}\leq\|\mathcal{P}\|_{\infty}\epsilon. \tag*{(9)}

This controls the full weighted tensor and therefore applies before any marginalization or contraction. Since the WMC is the contraction of this tensor to a scalar, we can derive a separate bound directly. For tensors of matching shape, let us denote ⟨A,B⟩F=∑cA(c)B(c)\langle\mathcal{A},\mathcal{B}\rangle_{F}=\sum_{c}\mathcal{A}(c)\mathcal{B}(c) for their Frobenius inner product.

Corollary C.3 (WMC error). Let X~\widetilde{\mathcal{X}} be an approximation of the constraint tensor X\mathcal{X} such that ∥X~−X∥F≤ϵ\|\widetilde{\mathcal{X}}-\mathcal{X}\|_{F}\leq\epsilon, and let P\mathcal{P} be any tensor of nonnegative weights. Then

∣WMC^−WMC∣≤ϵ∥P∥F.(10)\left|\widehat{\mathrm{WMC}}-\mathrm{WMC}\right|\leq\epsilon\|\mathcal{P}\|_{F}. \tag*{(10)}

If P\mathcal{P} is a normalized probability tensor, then ∥P∥F≤1\|\mathcal{P}\|_{F}\leq1 and consequently ∣WMC^−WMC∣≤ϵ\left|\widehat{\mathrm{WMC}}-\mathrm{WMC}\right|\leq\epsilon.

Proof. Let Δ=X~−X\Delta=\widetilde{\mathcal{X}}-\mathcal{X}. Since the exact and approximate weighted model counts are ⟨P,X⟩F\langle\mathcal{P},\mathcal{X}\rangle_{F} and ⟨P,X~⟩F\langle\mathcal{P},\widetilde{\mathcal{X}}\rangle_{F}, respectively,

∣WMC^−WMC∣=∣⟨P,Δ⟩F∣≤∥P∥F∥Δ∥F≤ϵ∥P∥F,\begin{aligned} \left|\widehat{\mathrm{WMC}}-\mathrm{WMC}\right|&=|\langle\mathcal{P},\Delta\rangle_{F}|\\ &\leq\|\mathcal{P}\|_{F}\|\Delta\|_{F}\leq\epsilon\|\mathcal{P}\|_{F}, \end{aligned}

where the first inequality is Cauchy-Schwarz. And, if P\mathcal{P} is normalized, we have ∥P∥F≤∥P∥1=1\|\mathcal{P}\|_{F}\leq\|\mathcal{P}\|_{1}=1.

CTSketch and Program Dependencies

CTSKETCH [8] approximates each factor ϕj\phi_{j} with a tensor train (§ 3.1), computes the factor WMC independently, and multiplies them progressively following a “tree-like“ structure. We formalize this using factor graphs and show that the tree-like assumption is violated by many NeSy programs, including the Sudoku tasks explored by Choi et al. [8], where we find that CTSKETCH introduces independence approximations (Equation (3)).

Tree-like factorizations

Example D.1 (sum4 [8]). Consider the program sum4 which takes as input four digits c1c_1, c2c_2, c3c_3, c4∈{0,…,9}c_4 \in\{0,\ldots,9\} and outputs their sum y=c1+c2+c3+c4y = c_1 + c_2 + c_3 + c_4. This program can be decomposed using two intermediate sums y1=c1+c2y_1 = c_1 + c_2 and y2=c3+c4y_2 = c_3 + c_4, followed by a final addition y=y1+y2y = y_1 + y_2. The constraint factorizes as

ϕ(c,y)=∑y1,y21[c1+c2=y1]1[c3+c4=y2]1[y1+y2=y].\phi(\mathbf{c},y) = \sum_{y_1,y_2} \mathbb{1}[c_1+c_2=y_1]\mathbb{1}[c_3+c_4=y_2]\mathbb{1}[y_1+y_2=y].

with the corresponding factor graph shown in Figure 6a.

Let c1={c1,c2}\mathbf{c}_1 = \{c_1,c_2\} and c2={c3,c4}\mathbf{c}_2 = \{c_3,c_4\} denote the two disjoint subsets of c\mathbf{c} associated with ϕ1\phi_1 and ϕ2\phi_2 respectively. The WMC rewrites as:

pθ(y∣x)=∑cpθ(c∣x)(∑y1,y2ϕ1(c1,y1)ϕ2(c2,y2)ϕ3(y1,y2,y)).p_\theta(y\mid x) = \sum_{\mathbf{c}}p_\theta(\mathbf{c}\mid x)\left(\sum_{y_1,y_2}\phi_1(\mathbf{c}_1,y_1)\phi_2(\mathbf{c}_2,y_2)\phi_3(y_1,y_2,y)\right).

Assuming pθ(c∣x)=∏ipθ(ci∣x)p_\theta(\mathbf{c}\mid x) = \prod_i p_\theta(c_i\mid x), CTSKETCH simplifies this marginalization in two steps. First, since ϕ3\phi_3 does not depend on c\mathbf{c} and pθ(c∣x)p_\theta(\mathbf{c}\mid x) does not depend on y1,y2y_1,y_2, the two sums commute and ϕ3\phi_3 can be moved outside:

pθ(y∣x)=∑y1,y2ϕ3(y1,y2,y)(∑cpθ(c∣x)ϕ1(c1,y1)ϕ2(c2,y2))p_\theta(y\mid x) = \sum_{y_1,y_2}\phi_3(y_1,y_2,y)\left(\sum_{\mathbf{c}}p_\theta(\mathbf{c}\mid x)\phi_1(\mathbf{c}_1,y_1)\phi_2(\mathbf{c}_2,y_2)\right)
=∑y1,y2ϕ3(y1,y2,y)(∑cpθ(c∣x)∏j=12ϕj(cj,yj)).= \sum_{y_1,y_2}\phi_3(y_1,y_2,y)\left(\sum_{\mathbf{c}}p_\theta(\mathbf{c}\mid x)\prod_{j=1}^{2}\phi_j(\mathbf{c}_j,y_j)\right).

Second, the tree structure of the factor graph and disjoint scopes of ϕ1,ϕ2\phi_1,\phi_2 let us push inner marginalizations down to the leaves.

pθ(y∣x)=∑y1,y2ϕ3(y1,y2,y)∏j=12(∑cjpθ(cj∣x)ϕj(cj,yj)).p_\theta(y\mid x) = \sum_{y_1,y_2}\phi_3(y_1,y_2,y)\prod_{j=1}^{2}\left(\sum_{\mathbf{c}_j}p_\theta(\mathbf{c}_j\mid x)\phi_j(\mathbf{c}_j,y_j)\right).

Read in isolation, this second step has exactly the form of the independence approximation of Equation (3): it computes a per-factor WMC and multiplies the results. The crucial difference is that here the equality is exact because the leaf c\mathbf{c}-scopes are disjoint and the marginals are genuinely independent.

CTSKETCH additionally approximates each ϕj\phi_j as a tensor train, but the same factorization trick applies directly to the dense factor tensors Xj\mathcal{X}_j. MNISTADD [34] satisfies this tree-like assumption, as do other programs that decompose into trees of intermediate variables.

Figure 6. Factor graphs for (a) a tree-like program where marginalization sums can be pushed inside individual factors, and (b) a program with overlapping scopes and cycles where this simplification does not apply.

Overlapping factors

In most NeSy programs the factor graph is not a tree: variables appear in multiple factors and the corresponding scopes overlap substantially.

Example D.2 (Sudoku 4x4). Consider the 4×44 \times4 Sudoku classification task, where the program takes as input 16 concepts ci∈{1,2,3,4}c_i \in\{1,2,3,4\} representing the digits in each cell and outputs whether the grid is valid. The program decomposes into 56 pairwise inequality constraints across rows, columns and blocks. For example, the first row alone factorizes as

ϕrow1(c1,c2,c3,c4)=1[c1≠c2]1[c1≠c3]1[c1≠c4]1[c2≠c3]1[c2≠c4]1[c3≠c4].\phi_{\mathrm{row1}}(c_1,c_2,c_3,c_4) = \mathbb{1}[c_1 \ne c_2]\mathbb{1}[c_1 \ne c_3]\mathbb{1}[c_1 \ne c_4]\mathbb{1}[c_2 \ne c_3]\mathbb{1}[c_2 \ne c_4]\mathbb{1}[c_3 \ne c_4].

The corresponding factor graph is shown in Figure 6b. Each variable already participates in three factors within a single row, and in even more once columns and blocks are considered. These overlapping scopes and cycles in the factor graph prevent us from pushing marginalization sums inside the product, as we did in Example D.1.

Despite the overlap, CTSKETCH applies the same per-factor simplification to Sudoku, pushing each marginalization sum to its associated factor as if the leaves had disjoint c-scopes:

∑cpθ(c∣x)∏jϕj(cj)≈∏j(∑cjpθ(cj∣x) AC⁡(ϕj)(cj))\sum_{\mathbf{c}} p_\theta(\mathbf{c}\mid\mathbf{x}) \prod_j \phi_j(c_j) \mathrel{\approx} \prod_j \left(\sum_{c_j} p_\theta(c_j\mid\mathbf{x})\,\operatorname{AC}(\phi_j)(c_j)\right)

The right-hand side has exactly the form of the (exact) factorization in Example D.1, but here the overlapping cjc_j turn the equality into an approximation: it is the composition of a factor approximation – each ϕj\phi_j replaced by its TT AC⁡(ϕj)\operatorname{AC}(\phi_j) – with an independence approximation. The independence step is the source of the unbounded error analyzed in Section C and empirically illustrated in Section E.

Independence Approximation and Categorical vs. Binary Encoding

We illustrate how the independence approximation can yield drastically different model count estimates depending on whether ϕ\phi is encoded over categorical or binary variables, even though the two encodings describe the same set of valid worlds. We use Sudoku as a concrete example, with the same constraint expressed once over categorical cells and once after the propositionalization required by SDD compilation (§ 2.1).

Independence Approximation under a Uniform Prior

Specializing the independence approximation to a uniform prior pθ(c)=1/∣C∣p_\theta(\mathbf{c}) = 1/|\mathcal{C}|, the WMC reduces to the model count MC=∑cϕ(c)\mathrm{MC} = \sum_{\mathbf{c}} \phi(\mathbf{c}), and the approximation becomes

MC^I=∣C∣⋅∏j=1Npj,pj:=1∣Cj∣∑cj∈Cjϕj(cj)(11)\widehat{\mathrm{MC}}^{\mathrm{I}} = |\mathcal{C}| \cdot\prod_{j=1}^{N} p_j,\qquad p_j := \frac{1}{|\mathcal{C}_j|}\sum_{\mathbf{c}_j\in\mathcal{C}_j}\phi_j(\mathbf{c}_j) \tag*{(11)}

where pjp_j is the fraction of assignments over the scope cj\mathbf{c}_j that satisfy ϕj\phi_j. Both factors of Equation (11) depend on the encoding only through trivial counting, but their product is dominated by very different magnitudes in the two encodings.

Sudoku 4x4: Categorical Encoding

The categorical formulation has variables ci∈{1,…,4}c_i \in\{1,\ldots,4\} for i=1,…,16i = 1,\ldots,16, giving ∣C∣=416|\mathcal{C}| = 4^{16}. The constraint ϕ\phi decomposes into N=56N = 56 pairwise inequalities ϕj(ci,cl)=1[ci≠cl]\phi_j(c_i,c_l) = \mathbb{1}[c_i \ne c_l] over cell pairs (i,l)(i,l) sharing a row, column, or box. Each factor has ∣Cj∣=16|\mathcal{C}_j| = 16 joint assignments of which 12 are satisfying, so pj=3/4p_j = 3/4. Plugging into Equation (11),

MC^catI=416⋅(34)56≈432.9,\widehat{\mathrm{MC}}_{\mathrm{cat}}^{\mathrm{I}} = 4^{16}\cdot\left(\frac{3}{4}\right)^{56} \approx432.9,

which overestimates the true MC of 288 by a factor of ≈1.5×\approx1.5\times.

Sudoku 4x4: Binary Encoding

SDD compilation requires propositionalizing ϕ\phi via indicators bi,v=1[ci=v]b_{i,v} = \mathbb{1}[c_i = v] for i=1,…,16i = 1,\ldots,16 and v∈{1,…,4}v \in\{1,\ldots,4\}, resulting in 64 Boolean variables and ∣C∣=264|\mathcal{C}| = 2^{64}. The constraint becomes a conjunction of N=336N = 336 CNF clauses of four types:

  • At-least-one (16 clauses): bi,1∨bi,2∨bi,3∨bi,4b_{i,1} \lor b_{i,2} \lor b_{i,3} \lor b_{i,4} per cell, with pj=1−(1/2)4=15/16p_j = 1 - (1/2)^4 = 15/16.

  • At-most-one (96 clauses): ¬bi,v∨¬bi,v′\neg b_{i,v} \lor\neg b_{i,v'} for each cell ii and value pair v<v′v < v', with pj=3/4p_j = 3/4.

  • Distinct values across rows and columns (96 + 96 clauses): ¬bi,v∨¬bl,v\neg b_{i,v} \lor\neg b_{l,v} for each row- or column-pair (i,l)(i,l) and each value vv, with pj=3/4p_j = 3/4.

  • Distinct values across boxes (32 clauses): same form, restricted to box-pairs not already covered by rows or columns, with pj=3/4p_j = 3/4.

Plugging into Equation (11),

MC^binI=264⋅(1516)16⋅(34)96+96+96+32≈6.87×10−22,\widehat{\mathrm{MC}}_{\mathrm{bin}}^{\mathrm{I}} = 2^{64} \cdot\left(\frac{15}{16}\right)^{16} \cdot\left(\frac{3}{4}\right)^{96+96+96+32} \approx6.87 \times10^{-22},

underestimating the true MC of 288 by roughly 24 orders of magnitude.

Discussion

The two estimates differ by approximately 24 orders of magnitude despite describing the same 288 valid boards. It is tempting to attribute this entirely to the NN scaling of Equation (11), as propositionalization inflates the factor count from 56 to 336, and each additional sub-unit pjp_j pushes the product toward zero. Our inference experiments in Section 5 show that this picture is misleading: even when the SDD pipeline reduces the propositionalized factors back to a count KK comparable to the categorical NN via exact multiplications, the binary estimate continues to underestimate the true MC while the categorical one continues to overestimate it, and the two remain orders of magnitude apart.

The deeper issue is that the independence approximation, viewed as a fuzzy semantics with the product t-norm, is unbounded and syntax-dependent: its value depends not only on the set of models of ϕ\phi but on how ϕ\phi is written. As a minimal illustration, consider a single Boolean a∈{0,1}a \in\{0,1\}. The formulas ϕ1:=a∧a\phi_1 := a \land a and ϕ2:=a\phi_2 := a have the same single satisfying assignment (MC = 1), yet MC^I(ϕ2)=2⋅12=1\widehat{\mathrm{MC}}^{\mathrm{I}}(\phi_2) = 2 \cdot\frac{1}{2} = 1 and MC^I(ϕ1)=2⋅12⋅12=12\widehat{\mathrm{MC}}^{\mathrm{I}}(\phi_1) = 2 \cdot\frac{1}{2} \cdot\frac{1}{2} = \frac{1}{2}.

Categorical and binary encodings of Sudoku express the same underlying constraint with very different syntactic profiles, and the product t-norm amplifies these differences in opposite directions: even after multiplying propositionalized factors back together, the residual factor structure is not the same as the categorical one and produces a systematically smaller ∏jpj\prod_j p_j. This contrasts with fuzzy semantics built on other t-norms (Gödel, Łukasiewicz), which have more established bounds and structural guarantees. [58] Neither, however, corresponds to a probabilistic relaxation of Equation (1), which is what motivates the use of the product t-norm as the independence approximation in the first place.

Tensor Train Algebra

Addition, Scalar Multiplication and Hadamard Product

We briefly introduce the closed-form algebra of TTs [43]. Figure 7 provides a graphical illustration. Let A\mathcal{A} and B\mathcal{B} denote two TTs over the same dd variables in the same core-to-variable ordering, with cores TA,k\mathcal{T}_{\mathcal{A},k} and TB,k\mathcal{T}_{\mathcal{B},k} of TT ranks rkAr_k^{\mathcal{A}} and rkBr_k^{\mathcal{B}} respectively. We write n=max⁡knkn = \max_k n_k for the maximal mode size and rr for the maximum TT rank, assuming that input TTs share a common rank rr.

Figure 7. Closed algebra over tensor trains: (a) scalar multiplication, (b) addition, (c) Hadamard product, and (d-e) broadcasting with two different insertion positions. The cost of broadcasting is given as the size of the inserted identity cores.

Scalar multiplication (Figure 7a). For c∈Rc \in\mathbb{R}, the TT c⋅Ac \cdot\mathcal{A} is obtained by absorbing cc into any single core, e.g. TA,1(c1)=cTA,1(c1)\mathcal{T}_{\mathcal{A},1}(c_1) = c\mathcal{T}_{\mathcal{A},1}(c_1). The ranks are unchanged and the resulting TT has the same O(dnr2)O(dnr^2) storage as A\mathcal{A}.

Addition (Figure 7b). The sum A+B\mathcal{A}+\mathcal{B} is a TT whose cores stack the input cores block-diagonally,

TA+B,k(ck)=(TA,k(ck)00TB,k(ck)),1<k<d,\mathcal{T}_{\mathcal{A}+\mathcal{B},k}(c_k) = \begin{pmatrix} \mathcal{T}_{\mathcal{A},k}(c_k) & 0 \\ 0 & \mathcal{T}_{\mathcal{B},k}(c_k) \end{pmatrix}, \qquad1 < k < d,

with the boundary cores stacked horizontally (k=1k = 1) and vertically (k=dk = d) so that r0=rd=1r_0 = r_d = 1 is preserved. The TT ranks add: rkA+B=rkA+rkBr_k^{A+B} = r_k^A + r_k^B, giving total storage O(dn(rkA+rkB)2)=O(dnr2)O(dn(r_k^A + r_k^B)^2) = O(dnr^2) for two equal-rank inputs.

Hadamard product (Figure 7c). The element-wise product A∗B\mathcal{A} * \mathcal{B} has cores given by the per-site Kronecker product of Equation (6),

TA∗B,k(ck)=TA,k(ck)⊗TB,k(ck),\mathcal{T}_{\mathcal{A} * \mathcal{B},k}(c_k) = \mathcal{T}_{\mathcal{A},k}(c_k) \otimes\mathcal{T}_{\mathcal{B},k}(c_k),

with multiplied ranks rkA∗B=rkA⋅rkBr_k^{A*B} = r_k^A \cdot r_k^B and storage O(dn(rkA∗B)2)=O(dnr4)O(dn(r_k^{A*B})^2) = O(dnr^4) for two equal-rank inputs. This quadratic per-product blow-up is the exponential rank growth discussed in § 3.2 and motivates the recompression strategies of § 3.3.

Broadcasting

The cores in Equation (6) assume that Xj\mathcal{X}_j and Xl\mathcal{X}_l are TTs over (i) the same scope and (ii) the same core-to-variable ordering. Assumption (ii) is easily enforced by fixing a global ordering σ\sigma of the variables in c\mathbf{c} and decomposing every factor in that ordering. Assumption (i) requires broadcasting: any TT whose scope cj⊂c\mathbf{c}_j \subset\mathbf{c} must be lifted to the common scope c\mathbf{c} before it can be multiplied with another TT.

Identity cores. For a TT Xj\mathcal{X}_j with scope cj\mathbf{c}_j decomposed in the ordering induced by σ\sigma, broadcasting to c\mathbf{c} inserts, for every missing variable ck∉cjc_k \notin\mathbf{c}_j, an identity core Ik\mathcal{I}_k at the position dictated by σ\sigma:

Ik(ck)=Irk−1,ck=1,…,∣Ck∣,\mathcal{I}_k(c_k) = \mathbf{I}_{r_{k-1}}, \qquad c_k = 1,\ldots,\lvert\mathcal{C}_k\rvert,

where rk−1r_{k-1} is the rank of the bond at which Ik\mathcal{I}_k is inserted, so that Ik\mathcal{I}_k has shape rk−1×∣Ck∣×rk−1r_{k-1} \times\lvert\mathcal{C}_k\rvert\times r_{k-1}. Since the slices of Ik\mathcal{I}_k are constant in ckc_k, the broadcasted TT evaluates to the same value as Xj\mathcal{X}_j for every assignment of the missing variables, as required.

Position matters. The position at which an identity core is inserted directly controls its size, and hence the storage and downstream multiplication cost of the broadcasted TT. If ckc_k is inserted within the span of cj\mathbf{c}_j in σ\sigma – i.e., between two original cores – then Ik\mathcal{I}_k has size O(nr2)O(nr^2), where rr is the local rank of Xj\mathcal{X}_j at that bond. If instead ckc_k is inserted outside the span – before the first or after the last variable of cj\mathbf{c}_j – the surrounding bond rank is r0=rd=1r_0 = r_d = 1 and Ik\mathcal{I}_k collapses to a 1×∣Ck∣×11 \times\lvert\mathcal{C}_k\rvert\times1 core of size O(n)O(n), leaving the storage essentially unchanged. Figure 7d and Figure 7e contrast the two cases: inserting the same variable c4c_4 between c2c_2 and c3c_3 costs O(nr2)O(nr^2), while appending it after c3c_3 costs only O(n)O(n).

Choosing a global variable ordering. Different global orderings σ\sigma result in different broadcasting costs because they change which missing variables fall inside or outside each factor’s span. We seek a σ\sigma that minimizes the total cost of broadcasting all factors to their pairwise (or full) common

scopes. We assume for simplicity a uniform rank rr and uniform mode size nn across all TTs.5 The broadcasting cost of factor ϕj\phi_j under σ\sigma scales with its number of interior gaps: the number of positions inside the span of cjc_j that are occupied by variables outside cjc_j. Concretely, denoting by pos⁡σ(ci)\operatorname{pos}_{\sigma}(c_i) the position of cic_i in σ\sigma, the interior gap length of ϕj\phi_j is

gaplen⁡j(σ)=(max⁡ci∈cjpos⁡σ(ci)−min⁡ci∈cjpos⁡σ(ci)+1)−∣cj∣(12)\operatorname{gaplen}_j(\sigma) = \left(\max_{c_i \in c_j} \operatorname{pos}_{\sigma}(c_i) - \min_{c_i \in c_j} \operatorname{pos}_{\sigma}(c_i) + 1\right) - \lvert c_j \rvert \tag*{(12)}

where the parenthesised term is the span of cjc_j in σ\sigma and ∣cj∣\lvert c_j \rvert is the number of own variables it contains. We seek the ordering minimising the total gap length,

min⁡σ∑j=1Ngaplen⁡j(σ).(13)\min_{\sigma} \sum_{j=1}^{N} \operatorname{gaplen}_j(\sigma). \tag*{(13)}

Spectral ordering. Equation (13) is a variant of the (NP-hard) minimum linear arrangement problem on the hypergraph whose hyperedges are the factor scopes cjc_j. We solve it heuristically via spectral seriation, which is fast, parameter-free, and reliably produces orderings that are good enough for our pipelines.

We construct a weighted co-occurrence graph on the variables c\mathbf{c} with adjacency

Wii′=∑j:ci,ci′∈cj1,W_{ii'} = \sum_{j: c_i,c_{i'} \in c_j} 1,

i.e., the number of factors in which cic_i and ci′c_{i'} jointly appear. Variables that co-occur in many factors should sit close together in σ\sigma to keep factor spans short. Letting D=diag⁡(W1)D = \operatorname{diag}(W\mathbf{1}) be the degree matrix and L=D−WL = D - W the graph Laplacian, the Fiedler vector – the eigenvector associated with the second-smallest eigenvalue of LL – provides a one-dimensional embedding of the variables that approximately minimises the weighted sum of squared distances between adjacent vertices [3]. We sort the variables by their Fiedler-vector entries to obtain σ\sigma.

This ordering is computed once per WMC instance, before any TT is built, and is then reused for all factors.

Multiplication Schedules

The bottom-up compilation pipeline of Section 4 pairs factors at two distinct stages: (i) the optional pre-multiplication of Step I, which groups dense factor tensors Xj\mathcal{X}_j and multiplies them in dense space before applying TT-SVD (TT pipelines only), and (ii) the circuit multiplication of Step II, which iteratively pairs and multiplies the NN compiled factor circuits into the K≤NK \le N circuits of Step III. In both stages, we intuitively aim to prioritize the multiplication of factors which share the most dependencies (that would otherwise be approximated by Step III) under some space constraints. The factors grow differently in the different stages, and we therefore use different strategies.

Dense Pre-multiplication: Hypergraph Partitioning

Before converting factors to TTs, we may multiply several sufficiently small factors exactly as dense tensors. This reduces the number of circuits passed to Step II and ensures that dependencies among factors in the same group are represented before any TT approximation is introduced. The grouping must balance two objectives: factors sharing variables should preferably be placed together, but the dense tensor produced by each group must fit within a prescribed memory budget BB.

Grouping objective. Let P1,…,PK\mathcal{P}_1,\ldots,\mathcal{P}_K be a partition of the NN initial factors. The factors in group Pk\mathcal{P}_k are replaced by their dense Hadamard product

XPk=∏j∈PkXj,cPk=⋃j∈Pkcj.\mathcal{X}_{\mathcal{P}_k} = \prod_{j \in\mathcal{P}_k} \mathcal{X}_j,\qquad c_{\mathcal{P}_k} = \bigcup_{j \in\mathcal{P}_k} c_j.

The resulting tensor contains one mode for every variable in the union of the grouped scopes and therefore has size(XPk)=∏ci∈⋃j∈Pkcj∣Ci∣(\mathcal{X}_{\mathcal{P}_k}) = \prod_{c_i \in\bigcup_{j \in\mathcal{P}_k} c_j} |C_i| entries. We require this size to remain below BB.

We seek groups that share as few variables as possible with one another while satisfying this constraint. Equivalently, factors containing the same variable should be kept in the same group whenever the memory budget permits.

Hypergraph representation. This grouping problem has a natural hypergraph representation. We create one node for each factor and one hyperedge for each variable. The hyperedge for variable cic_i connects exactly the factors whose scopes contain cic_i:

ei={j:ci∈cj}.e_i = \{j : c_i \in c_j\}.

If the connected factors are assigned to different groups, then eie_i is cut. A cut hyperedge therefore corresponds directly to a variable shared by multiple output groups. Minimizing the number of cut hyperedges implements the dependency objective above.

Memory constraint. The exact dense size of a group depends on the union of its factor scopes and is not additive across factors. Standard hypergraph partitioners, however, impose balance constraints using additive node weights. We therefore give factor jj the conservative weight

wj=log⁡(∏ci∈cj∣Ci∣).w_j = \log\left(\prod_{c_i \in c_j} |C_i|\right).

For a group Pk\mathcal{P}_k,

∑j∈Pkwj=log⁡(∏j∈Pk∏ci∈cj∣Ci∣)\sum_{j \in\mathcal{P}_k} w_j = \log\left(\prod_{j \in\mathcal{P}_k} \prod_{c_i \in c_j} |C_i|\right)

upper-bounds the logarithm of its actual dense size. The bound may count a shared variable more than once, whereas the dense product contains that variable only once. Consequently, enforcing

∑j∈Pkwj≤log⁡B\sum_{j \in\mathcal{P}_k} w_j \le\log B

is sufficient, though potentially conservative, for keeping the dense product within budget.

The resulting optimization is

min⁡P1,…,PK∣{i:ei is cut}∣s.t.∑j∈Pkwj≤log⁡B∀k.(14)\min_{\mathcal{P}_1,\ldots,\mathcal{P}_K} \left|\{i : e_i \text{ is cut}\}\right| \qquad\text{s.t.}\qquad \sum_{j \in\mathcal{P}_k} w_j \le\log B \quad\forall k. \tag*{(14)}

Thus, the objective keeps factors coupled by shared variables together, while the constraint limits the cost of materializing each resulting dense tensor.

Implementation. We approximately solve this constrained partitioning problem with KaHyPar [49]. Starting from K=1K = 1, we increase the number of groups until the partition satisfies the dense-size budget. We use B∈{106,109}B \in\{10^6, 10^9\} entries in our experiments. The partitioning overhead is negligible relative to dense multiplication and circuit compilation.

Circuit Multiplication Schedules

After Step I, the pipeline contains NN compiled circuits, which Step II reduces to KK through pairwise multiplications. The multiplication schedule balances two objectives. First, factors with important shared dependencies should be combined before the pipeline stops and approximates the remaining groups as independent. Second, intermediate products must remain small enough to store and, for recompressed TT multiplication, simple enough to approximate accurately under the available rank budget.

This scheduling problem is closely related to the contraction-order problem studied for tensor networks [22]. Standard tensor-network contraction normally continues until the entire network has been contracted, so the order is chosen primarily to minimize the sizes of intermediate tensors. Our setting introduces an additional concern: Step II may stop at K>1K > 1, after which dependencies between the remaining groups are ignored by the fuzzy reduction. The schedule must therefore decide not only how to control intermediate size, but also which dependencies should already have been incorporated when multiplication stops. TT recompression adds a further consideration: even when two schedules have comparable memory costs, they may expose different intermediate functions to rounding and consequently result in different approximation errors.

We explore three different scheduling strategies, each which their own focus within these objectives and considerations. These strategies are heuristic. Just as tensor network literature shows no single merge order strategies across problems [22, 21], we empirically find different strategies to perform better in different experiments.

Dependency-first matching. When no more specific program structure is available, we prioritize the first objective directly. At each level of a binary multiplication tree, we pair circuits with the largest scope intersections. Scope overlap serves as a proxy for shared dependencies: multiplying highly overlapping factors first keeps those dependencies inside the same circuit if the pipeline stops early, rather than leaving them to be discarded by the final independence approximation. We choose the pairs jointly through maximum-weight matching [18], with edge weights wjl=∣cj∩cl∣w_{jl} = |c_j \cap c_l|. We use this strategy in our Sudoku experiments.

Variable-elimination scheduling. When a program contains auxiliary variables, we can minimize its intermediate size by quickly eliminating these variables. Auxiliary variables encode dependencies between factors, but they are not queried and ultimately receive uniform weights. Once all factors containing such a variable have been multiplied, it can therefore be marginalized exactly. Doing so immediately can sharply and predictably reduce the scope and ranks of the intermediate circuit before the following multiplications. The variable-elimination schedule consequently prioritizes pairs whose multiplication makes the largest number of auxiliary variables available for marginalization. Note that this still serves the same dependency objective: all factors coupled through an eliminated variable are combined before that variable is summed out, so its induced dependency is retained exactly within the resulting factor. We use this strategy in our experiments with auxiliary variables (MNIST arithmetic and CLEVR-CountDiff).

Ordered contraction. Finally, we explore a strategy inspired by sequential boundary contraction in tensor-network algorithms [41, 50] which helps in intermediate TT rounding steps. Boundary-MPS methods progressively contract a tensor network from one side and compress the resulting boundary after each step. Their guiding principle is that each truncation approximates the complete network prefix contracted so far, rather than an arbitrary subset of its tensors. We transfer this principle to factor multiplication under the variable order of the TT. Each factor is assigned to the last variable in its scope. Factors assigned to the same variable are multiplied together, and the resulting groups are incorporated from left to right into a running product. After processing variable cic_i, the accumulator therefore contains every factor whose scope is contained in the prefix (c1,…,ci)(c_1, \ldots, c_i). Consequently, each TT rounding acts on a complete factor prefix. Dependencies whose factors close within that prefix can interact before ranks are truncated, whereas an arbitrary binary tree may round disconnected or incomplete collections of factors and retain distinctions that later factors would make redundant. This schedule does not guarantee smaller ranks for every program, but it aligns intermediate approximation with the sequential decomposition underlying the TT. CLEVR-Diff uses this schedule.

Final contraction

Compilation generally leaves two TT factors (when feasible), which are contracted jointly with the query weights without materializing their product TT. This final contraction is exact and introduces no independence approximation or additional truncation. Because it avoids storing the inflated product cores, the inner product of mm TTs with rank rr is O(rm)O(r^m) rather than O(r2m)O(r^2m); with two TTs stored in O(r2)O(r^2) memory, this final contraction of two TTs is therefore virtually free in space complexity.

Experiments (cont.)

Conditional WMC

In the conditional WMC setting, we still use a parameterized model pθ(c∣x)p_\theta(\mathbf{c}|\mathbf{x}) over the symbolic concepts, but the logical constraint ϕ(c,y):C×Y→{0,1}\phi(\mathbf{c},\mathbf{y}) : \mathcal{C} \times\mathcal{Y} \to\{0,1\} now also depends on output variables y. The goal is to use the formula to derive a probability of yy given xx:

pθ(y∣x):=∑c∈Cpθ(c∣x)ϕ(c,y)∑y′∈Y,c∈Cpθ(c∣x)ϕ(c,y′)(15)p_\theta(y\mid x) := \frac{\sum_{c\in\mathcal{C}} p_\theta(c\mid x)\phi(c,y)}{\sum_{y'\in\mathcal{Y},c\in\mathcal{C}} p_\theta(c\mid x)\phi(c,y')} \tag*{(15)}

which, given a label l∈Yl \in\mathcal{Y}, is optimized by maximizing pθ(l∣x)p_\theta(l\mid x).

The denominator is a normalizing constant that ensures pθ(y∣x)p_\theta(y\mid x) is a valid distribution over yy. If, for every c∈Cc \in\mathcal{C}, there exists one and only one y∈Yy \in\mathcal{Y} such that ϕ(c,y)=1\phi(c,y) = 1, then the denominator simplifies to 1. Many works [8, 59, 62] take this assumption and write the symbolic program as a function y=f(c)y = f(c). We note however that this is generally not the case for Sudoku completion: some partial boards cc could be completed in multiple ways, and some could not admit any completion. However, the SatNet dataset [66] is constructed so that every cc has only one valid completion, such that in practice works that optimize the numerator alone [8] still achieve good results.

Sudoku compilation ablation

Evaluated pipelines

The Sudoku ablation plot in Figure 3 records the APRICOT compilation pipelines using

N→p×→Rinit→e×→t×K.N \xrightarrow{p\times} \xrightarrow{R_{\mathrm{init}}} \xrightarrow{e\times} \xrightarrow{t\times} K.

Here NN is the initial factor count, pp counts dense pre-multiplications, ee counts exact TT merges, and tt counts recompressed merges. The TT-SVD arrow records the initial rank setting. KK is the resulting number of factors; if K>1K > 1, the baseline uses an independent reduction. Note that some of these operations are optional (e.g., pre-multiplication, recompressions, ...); when they are absent, the arrow is omitted. We test different dense pre-multiplication budgets (none, 10610^6, or 10910^9 entries, see also Section G.1), initial ranks Rinit∈{10,30,500}R_{\mathrm{init}} \in\{10, 30, 500\}, recompression strategies from Section I with a maximum rank of 500, and various reduction targets KK.

SDD pipelines are recorded as

N→KC→e×K.N \xrightarrow{\mathrm{KC}} \xrightarrow{e\times} K.

where the KC arrow denotes exact compilation of the initial clauses, followed by any exact merge arrows. As for the TT pipelines, if K>1K > 1, fuzzy approximations are used.

Multiplication schedule and rank budget

We further ablate the multiplication schedule and maximum rank on Sudoku 6×66 \times6, using TT-ROUND for recompressed TT multiplication and stopping at five factors before fuzzy reduction. The dependency-first schedule from Section G.2 prioritizes factors with overlapping scopes. Its intermediate products can therefore be more difficult to represent within the available rank budget, resulting in fewer exact merges than under a random schedule (169 rather than 183 at rank 500). Similarly, reducing the maximum rank to 50 also leaves fewer merges within the exact rank budget (144). This behavior is expected from the compilation algorithm; the relevant comparison is the accuracy and cost of the resulting pipelines.

PipelineScheduleRankTime (s)∣log⁡10(MC/MCref)∣↓\lvert\log_{10}(\mathrm{MC}/\mathrm{MC}_{\mathrm{ref}}) \rvert\downarrow
216→R=6→169×→42×5216 \xrightarrow{R=6} \xrightarrow{169\times} \xrightarrow{42\times} 5Dependency-first50042.41.30
216→R=6→183×→28×5216 \xrightarrow{R=6} \xrightarrow{183\times} \xrightarrow{28\times} 5Random50094.73.41
216→R=6→144×→67×5216 \xrightarrow{R=6} \xrightarrow{144\times} \xrightarrow{67\times} 5Dependency-first505.11.97

Table 1. Ablation of the multiplication schedule and maximum TT rank on Sudoku 6×66 \times6. All pipelines use TT-ROUND and reduce the 216 initial factors to five before fuzzy reduction.

At rank 500, dependency-first matching is substantially more accurate than the random schedule. Although the random schedule admits more exact merges, its five remaining factors preserve less of the shared dependency structure before fuzzy reduction. The dependency-first matching is also surprisingly faster, perhaps because handling dependencies early on while the TTs are still small is more efficient than in later stage. Comparing the two dependency-first pipelines, rank 50 is much faster, consistent with the cubic dependence of TT multiplication on the rank, whereas rank 500 is more expressive and yields a more accurate model count. Notably, dependency-first matching at rank 50 remains more accurate than the random schedule at rank 500.

Pareto front of log inference error versus compilation time for Sudoku 4x4

Figure 8. Pareto front of log inference error vs compilation time for Sudoku 4x4.

Sudoku 4x4

On Sudoku 4x4, we confirm that both SDD and APRICOT pipelines can derive the exact model count within a tiny ϵ\epsilon error. As SDD can exactly reduce the formula into a single circuit, we also expect that approximate compilation can achieve a reduction to K=1K = 1 with negligible error, which is what we observe in practice. We also notice that, as introducing approximate multiplications is slower than exact ones due to the overhead of recompression (though, they still compile within seconds), they are not beneficial in such small scale settings, and the best point on the Pareto front is achieved by the SDD pipelines.

Neurosymbolic tasks

We describe the Visual Sudoku, arithmetic and scene-understanding tasks used in our experiments. Perception predicts distributions over input MNIST digits or object attributes, and supervision is provided only on the program output. Auxiliary symbolic variables express intermediate computations and are unweighted: compiled pipelines marginalize them jointly, while independence reduction marginalizes them separately within each factor.

Definitions

ViSudo Classification. Let zr,c∈{1,…,9}z_{r,c} \in\{1,\ldots,9\} denote the digit in row rr and column cc. Sudoku requires all digits within each row, column, and 3×33 \times3 box to be distinct. Writing EE for the set of unordered pairs of distinct cells sharing at least one of these units, the constraint is

ϕ(z):=⋀{(r,c),(r′,c′)}∈E[zr,c≠zr′,c′].\phi(z) := \bigwedge_{\{(r,c),(r',c')\}\in E} [z_{r,c} \ne z_{r',c'}].

Each factor is a 9×99 \times9 Boolean tensor with zeros on the diagonal and ones elsewhere. This factorization introduces no auxiliary symbolic variables.

ViSudo Completion. For completion, clue-cell digits are the perceptual concepts cc and missing-cell digits are the output yy. The same constraint is evaluated on the combined board, giving ϕ(c,y)\phi(c,y).

MNISTAdd. Two LL-digit numbers AA and BB are represented by 2L2L MNIST images, and the output is the L+1L+1 digits of their sum YY. Indexing digits from least to most significant, the constraints describe the rules of column addition as:

A0+B0=Y0+10C0,Ai+Bi+Ci−1=Yi+10Ci(1≤i<L),YL=CL−1A_0 + B_0 = Y_0 + 10C_0,\qquad A_i + B_i + C_{i-1} = Y_i + 10C_i\quad(1 \le i < L),\qquad Y_L = C_{L-1}

where CiC_i are binary carries. Each factor involves one column and its adjacent carries, giving a chain of local computations. The variable ordering of both SDD and APRICOT follows this structure.

MNISTMul. The inputs are again 2L2L MNIST images, and the output is the 2L2L digits of A∗BA \ast B. A coarse factorization would connect input digits and carries as

∑i+j=kAiBj+Ck−1=Yk+10Ck,0≤k<2L,\sum_{i+j=k} A_iB_j + C_{k-1} = Y_k + 10C_k,\qquad0 \leq k < 2L,

with C−1=C2L−1=0C_{-1} = C_{2L-1} = 0. However, in this setting, each factor still involves a large number of input digits which exceed our GPU memory at L=3L = 3 in our implementation. We therefore derive a finer factorization that introduces partial products Pij=AiBjP_{ij} = A_iB_j and computes each column sum Sk=∑i+j=kPijS_k = \sum_{i+j=k} P_{ij} through a chain of running partial sums. With these auxiliary variables and factors, the carry logic becomes

Sk+Ck−1=Yk+10Ck,0≤k<2L.S_k + C_{k-1} = Y_k + 10C_k,\qquad0 \leq k < 2L.

with S2L−1=0S_{2L-1} = 0. Notice that this is not possible for the fuzzy baseline, where an independent reduction of the finer factorization has ineffective learning gradients. We therefore retain the coarser carry formulation for fuzzy (explaining why fuzzy runs out of memory at L=3L = 3).

CLEVR-Diff. Each of the mm objects has a key KiK_i, predicted by the perception and consisting of the shape and color of the object. We use D=3×8=24D = 3 \times8 = 24 possible keys. To check whether the mm objects are different, we evaluate a conjunction of factors that indicate whether all keys differ:

ϕ(K):=⋀1≤i<j≤mKi≠Kj.\phi(\mathbf{K}) := \bigwedge_{1 \leq i < j \leq m} K_i \ne K_j.

This constraint consists of (m2)\binom{m}{2} pairwise inequalities and requires no auxiliary symbolic variables.

CLEVR-CountDiff. Here, we use keys consisting of the shape, material, and size of the object, with D=3×2×2=12D = 3 \times2 \times2 = 12 possibilities. The output is the number of distinct keys, Y=∣{K1,…,Km}∣Y = \lvert\{K_1, \ldots, K_m\}\rvert in the scene. The factorization uses auxiliary binary variables Sv,iS_{v,i} that record whether key vv occurs among the first ii objects. Then, running counts TvT_v accumulate the number of keys present:

Sv,0=0,Sv,i↔Sv,i−1∨[Ki=v],T−1=0,Tv=Tv−1+Sv,m,Y=TD−1,\begin{aligned} S_{v,0} &= 0,\qquad S_{v,i} \leftrightarrow S_{v,i-1} \lor[K_i = v],\\ T_{-1} &= 0,\qquad T_v = T_{v-1} + S_{v,m},\qquad Y = T_{D-1}, \end{aligned}

for 0≤v<D0 \leq v < D and 1≤i≤m1 \leq i \leq m.

Datasets

Visual Sudoku. Both tasks use 9×99 \times9 boards with observed digits represented by MNIST images. ViSudo-Classification uses ViSudo-PC [4]: the label indicates whether a board satisfies the Sudoku rules. Training uses only valid boards, while evaluation includes valid and invalid boards. ViSudo-Completion uses the SatNet dataset [66], with the data-leak correction of Chang et al. [6]. Observed clue cells provide the image inputs, and the digits in the remaining cells are the supervised targets. We use the benchmark training and test splits.

Arithmetic. We construct examples separately from the MNIST training and test splits: disjoint groups of 2L2L images are used for the input numbers, and their digit labels determine the arithmetic output. This gives ⌊60,000/(2L)⌋\lfloor60{,}000/(2L)\rfloor training and ⌊10,000/(2L)⌋\lfloor10{,}000/(2L)\rfloor test examples (therefore, increasing the input length LL also reduces the number of available training examples). The generated datasets are shared across methods and run seeds.

Scene-understanding. We extract object crops from annotated CLEVR-Hans3 scenes [54], resize them to 32×3232 \times32, and assemble sets of mm objects as newly constructed scenes. For CLEVR-Diff, we sample distinct keys and, with probability 1/21/2, replace one by a duplicate of another, balancing the two output classes. For CLEVR-CountDiff, keys are drawn independently and uniformly. Each key is instantiated with a randomly selected crop of that type. Training and test examples use crops exclusively from their respective source splits. We generate 10,000 training and 2,000 test examples for each task size, using fixed datasets across methods and runs. Recombining crops permits larger object sets than the original scenes and keeps the per-object sampling distribution fixed across mm.

WMC evaluation

For each arithmetic and CLEVR circuit, we evaluate 64 random weightings, shared across methods using a fixed seed. In each draw, every non-auxiliary variable receives an independently sampled Dirichlet(1) weight vector, uniform over its probability simplex. These include input digits or object keys and, where represented explicitly, output digits or counts. Auxiliary variables receive unit weights and are summed out. No evidence is fixed: the query sums over all satisfying assignments, including all output values. CLEVR-Diff evaluates the all-different constraint without an explicit output variable. These random queries assess circuit fidelity rather than performance under learned neural predictions or observed-label evidence.

Let WMCb\mathrm{WMC}_b and WMC^b\widehat{\mathrm{WMC}}_b denote the reference and estimated WMC for draw bb. For weight draw bb, we measure the absolute log-ratio error

eb=∣log⁡10WMC^bWMCb∣.e_b = \left|\log_{10}\frac{\widehat{\mathrm{WMC}}_b}{\mathrm{WMC}_b}\right|.

We report the median of the 64 resulting errors,

EWMC=median⁡{e1,…,e64}.E_{\mathrm{WMC}} = \operatorname{median}\{e_1,\ldots,e_{64}\}.

Thus, EWMC=1E_{\mathrm{WMC}}=1 means that, for a typical sampled weighting, the estimated WMC differs from the reference by a factor of 10.

Exact references. In tasks where exact compilation breaks in the harder settings (MNISTMul, CLEVR-Diff, CLEVR-CountDiff), the exact references WMCb\mathrm{WMC}_b are derived using task-specific solutions developed separately for each benchmark. These specialized solutions used dynamic programming, inclusion-exclusion, or brute-force enumeration; they are not general-purpose WMC algorithms and are not included as competing methods. The procedures were developed with the assistance of AI and then checked against exact SDD evaluation on the easier instances for which SDD compilation was feasible.

  • MNISTMul. For every pair of LL-digit input numbers (A,B)(A,B), we compute the unique product Y=ABY=AB. The contribution of this assignment is the product of the weights assigned to the digits of AA, BB, and YY. Summing these contributions over all 102L10^{2L} input pairs gives the exact WMC. This direct enumeration is practical for the evaluated instances, where L≤3L\le3.

  • CLEVR-Diff. The required WMC is the total weight of assignments in which all mm objects receive different keys. We process the DD possible key values one at a time. A dynamic-programming state records the subset SS of objects that have already been assigned distinct processed keys. For the next key, we either leave it unused or assign it to one object not in SS, multiplying by that object’s weight for the key. After all keys have been processed, the state containing all objects is the exact all-different WMC. The algorithm has O(2m)O(2^m) states and costs O(Dm2m)O(Dm2^m).

  • CLEVR-CountDiff. Here we require the weighted distribution of the number of distinct keys. For every subset BB of the DD possible key values, we first compute

q(B)=∏i=1m∑v∈Bpi(v),q(B)=\prod_{i=1}^{m}\sum_{v\in B}p_i(v),

the total weight of assignments in which every object chooses a key from BB. These quantities include assignments using all of BB as well as assignments using only a smaller subset. Inclusion–exclusion removes this repeated counting and recovers the total weight of assignments using exactly tt distinct keys, for every tt. The output weights are then applied to this exact distribution. The computation is exponential in the key-domain size DD and linear in the number of objects mm, making it practical here because D=12D=12.

Training and evaluation details

APRICOT configurations. The grid of APRICOT configurations evaluated in the Sudoku compilation ablation is detailed in Section H.2. For the Visual Sudoku learning experiments, the selected compilation stage uses dense pre-multiplication groups of at most 10610^6 entries, leaving 113 initial factors, an initial TT-SVD rank 30, and a maximum rank of 500 during multiplications. For arithmetic and CLEVR, the selected APRICOT C configurations skip pre-multiplications and use TT-ROUND for product recompression, with maximum ranks below of 500 for all experiments, except MNISTMul where we allow a maximum rank of 1200. The multiplication schedules are different in each experiment and detailed in Section G.2.

Compute budgets. The reported configuration uses one NVIDIA A10G GPU with approximately 22 GiB memory. TT compilation runs on the GPU. SDD compilation runs on the CPU process with a 64 GiB memory cap and a two-hour time limit for the compilation study. Training has a six-hour wall-clock limit. Runs exceeding these limits are reported as out of memory or timed out, without increasing the budget. Results are averaged over ten runs.

Learning objectives. We maximize the WMC in Equation (1) and conditional WMC in Equation (15) by setting the weights of the concepts c\mathbf{c} to predicted neural probabilities and the weights of the output variables y\mathbf{y} to the given one-hot labels, and by marginalizing the circuit. Auxiliary variables receive unit weights. In practice, we maximize the logarithm of the resulting WMC.

Inference. In the conditional WMC setting (Section H.1), two strategies can be used to predict the output y\mathbf{y} from the latent concepts c\mathbf{c} at test time. The first, greedy decoding, selects the most likely concept prediction from the neural predictor argmax⁡cp(c∣x)\operatorname*{argmax}_{\mathbf{c}} p(\mathbf{c} \mid\mathbf{x}). The concepts are then fed to a symbolic solver to evaluate the constraint or derive output symbols y\mathbf{y}, e.g., by running a Sudoku solver on the partially filled concepts or computing ordinary exact addition/multiplication for arithmetic. Under this strategy, the WMC is not used at inference time; only during learning. We use greedy decoding for the Visual Sudoku experiments. The second, reasoning-based decoding, uses the WMC at inference to predict argmax⁡y∑cp(c∣x)ϕ(c,y)\operatorname*{argmax}_{\mathbf{y}} \sum_{\mathbf{c}} p(\mathbf{c} \mid\mathbf{x})\phi(\mathbf{c}, \mathbf{y}) – or doing this independently for each yky_k. This approach can pick up on subtle inconsistencies in the predictions and correct them based on the constraints. We use it for the arithmetic and CLEVR experiments.

Architectures and hyperparameters. We use conventional CNNs to process each input image independently (an MNIST image or an object crop) and produce a softmax distribution over its symbol. Architecture details are provided in the repository. We use Adam [26] with the following settings, together with usual techniques such as gradient clipping. There is no validation-based selection or early stopping: metrics use the final epoch.

TaskLearning rateBatch sizeEpochs
MNISTAdd10−310^{-3}32 (8 for L=100L = 100)30
MNISTMul10−310^{-3}3210
CLEVR-Diff / CountDiff10−310^{-3}3240
ViSudo-Completion10−310^{-3}820
ViSudo-Classification10−310^{-3}202000

Table 1 (PDF p. 30).

Approximation Algorithms for TT Multiplication

In this appendix, we detail the four recompression strategies introduced in § 3.3. All algorithms take as input two compatible TTs A\mathcal{A} and B\mathcal{B} (same scope, same core ordering, same mode dimensions nkn_k) and a target maximum rank RR or Frobenius tolerance ϵ\epsilon, and return a TT approximation X~\widetilde{\mathcal{X}} of the Hadamard product X=A∗B\mathcal{X} = \mathcal{A} * \mathcal{B}. We denote by TA,k∈Rrk−1A×nk×rkA\mathcal{T}_{\mathcal{A},k} \in\mathbb{R}^{r_{k-1}^{\mathcal{A}} \times n_k \times r_k^{\mathcal{A}}} the kk-th core of A\mathcal{A}, and similarly for B\mathcal{B} and X~\widetilde{\mathcal{X}}.

Notation. We follow einsum and einops conventions for tensor operations [47]. Given tensors T1,T2\mathcal{T}_1, \mathcal{T}_2:

  • EINSUM("abc, cde -> abde", T₁, T₂) denotes Einstein summation, contracting indices that appear in both inputs but not in the output.

  • REARRANGE("(a b) c -> a b c", T) denotes a reshape/permutation, where parentheses on the left split a single axis into multiple axes (with explicit sizes given as side arguments) and parentheses on the right merge multiple axes into a single axis.

TT-Round

TT-Round [43] computes X~≈A∗B\widetilde{\mathcal{X}} \approx\mathcal{A} * \mathcal{B} by interleaving the Kronecker product of cores with a sweep of truncated SVDs. The naive variant first materializes the inflated cores TX,k=TA,k⊗TB,k\mathcal{T}_{\mathcal{X},k} = \mathcal{T}_{\mathcal{A},k} \otimes\mathcal{T}_{\mathcal{B},k} of Algorithm 1 Hadamard TT-Round

Require: TTs A,B\mathcal{A}, \mathcal{B} with cores {TA,k}k=1d,{TB,k}k=1d\{\mathcal{T}_{\mathcal{A},k}\}_{k=1}^{d}, \{\mathcal{T}_{\mathcal{B},k}\}_{k=1}^{d}; max rank RR; tolerance ϵ\epsilon.

Ensure: TT approximation X~≈A∗B\widetilde{\mathcal{X}} \approx\mathcal{A} * \mathcal{B}.

1: A←RightOrthogonalize⁡(A)\mathcal{A} \leftarrow\operatorname{RightOrthogonalize}(\mathcal{A}) 2: B←RightOrthogonalize⁡(B)\mathcal{B} \leftarrow\operatorname{RightOrthogonalize}(\mathcal{B}) 3: L←1∈R1×1×1\mathcal{L} \leftarrow1 \in\mathbb{R}^{1 \times1 \times1} ▹\triangleright initial left environment 4: for k=1,…,dk = 1, \ldots, d do 5: W←Einsum⁡("\mathcal{W} \leftarrow\operatorname{Einsum}("r ra rb, ra n ra’, rb n rb’ -> r n ra’ rb’",,\mathcal{L}, \mathcal{T}_{\mathcal{A},k}, \mathcal{T}_{\mathcal{B},k})6:6:\mathcal{W} \leftarrow \operatorname{Rearrange}("rnra’rb’−>(rn)(ra’rb’)"r n ra’ rb’ -> (r n) (ra’ rb’)", W)\mathcal{W}) 7: if k<dk < d then 8: U,s,VT←TruncatedSVD⁡(W;ϵ,R)U,s,V^{\mathsf{T}} \leftarrow\operatorname{TruncatedSVD}(\mathcal{W}; \epsilon, R) 9: TX~,k←Rearrange⁡("\mathcal{T}_{\widetilde{\mathcal{X}},k} \leftarrow\operatorname{Rearrange}("(r n) r’ -> r n r’",,U)10:) 10:\mathcal{L} \leftarrow \operatorname{Rearrange}("r’(ra’rb’)−>r’ra’rb’"r’ (ra’ rb’) -> r’ ra’ rb’", diag⁡(s)VT)\operatorname{diag}(s)V^{\mathsf{T}}) 11: else 12: TX~,d←Rearrange⁡("\mathcal{T}_{\widetilde{\mathcal{X}},d} \leftarrow\operatorname{Rearrange}("(r n) 1 -> r n 1"$, W\mathcal{W}) 13: end if 14: end for 15: return TT X~\widetilde{\mathcal{X}} with cores {TX~,k}k=1d\{\mathcal{T}_{\widetilde{\mathcal{X}},k}\}_{k=1}^{d}.

rank rkArkBr_k^{A}r_k^{B} and then applies a standard rounding sweep, paying O(dnr4)O(dnr^4) memory for the inflated cores. The single-pass variant presented here exploits the Matrix-Kronecker structure of the inflated cores to avoid this materialization, reducing the memory cost to O(r3)O(r^3).

The algorithm proceeds in two phases:

  1. Right-orthogonalization. Both A\mathcal{A} and B\mathcal{B} are first right-orthogonalized so that the right unfolding of every core is row-orthonormal. This ensures that the subsequent local SVD truncations are quasi-optimal with respect to the global Frobenius norm.

  1. Left-to-right SVD sweep. A left environment L∈Rrk−1×rk−1A×rk−1B\mathcal{L} \in\mathbb{R}^{r_{k-1}\times r^A_{k-1}\times r^B_{k-1}} accumulates the already-compressed prefix. At each site kk, the algorithm (i) contracts L\mathcal{L} with the (implicit) Kronecker slice TA,k⊗TB,k\mathcal{T}_{\mathcal{A},k} \otimes\mathcal{T}_{\mathcal{B},k} via a single einsum, producing a working tensor W\mathcal{W}; (ii) flattens W\mathcal{W} into a matrix and performs a truncated SVD with target rank RR (or tolerance ϵ\epsilon); (iii) stores the left singular vectors as the new core TX~,k\mathcal{T}_{\widetilde{\mathcal{X}},k} and absorbs diag⁡(s)VT\operatorname{diag}(s)V^{\mathsf{T}} into the next left environment.

The last core requires no SVD truncation since its rightmost rank is already 1 by definition.

Randomized per-site SVD. When the target rank RR is small relative to the working tensor dimensions, the truncated SVD on W\mathcal{W} (Algorithm 1, line 8) can be replaced by a randomized low-rank SVD [23]: W\mathcal{W} is multiplied by a Gaussian sketch of width R+roversampleR + r_{\mathrm{oversample}}, and the dominant left singular vectors are recovered from the resulting tall-and-skinny matrix. We emphasize that this is a purely local, matrix-level acceleration — a fresh sketch is drawn independently at each site, and the sweep structure, orthogonalization, and per-site target ranks are unchanged. This is conceptually distinct from the TT-level sketching used by HATT (§ 17.2), which draws a single random TT once and reuses it across all sites by precomputing right environments, so that no unfolding of X\mathcal{X} is ever formed.

Complexity. At site kk, W\mathcal{W} has shape rk−1nk×rkArkBr_{k-1}n_k \times r_k^{A}r_k^{B} and its truncated SVD costs O(nr4)O(nr^4) for uniform ranks rr. Summed over dd sites, this gives O(dnr4)O(dnr^4) time. Memory is dominated by storing W\mathcal{W} and the left environment, both of which are O(r3)O(r^3) since the Kronecker factors are never explicitly formed. When randomized per-site SVDs are used in place of deterministic ones, the per-site cost drops to O(nr3)O(nr^3) since the SVD operates on a sketched matrix of column dimension O(r)O(r) rather than on the full rkArkB=r2r_k^{A}r_k^{B} = r^2 unfolding, giving an overall time complexity of O(dnr3)O(dnr^3) — matching that of HATT (§ 17.2).

Algorithm 2 Sketched right environments for X=A∗B\mathcal{X}=\mathcal{A}*\mathcal{B}

Require: TT cores {TA,k}k=1d\{\mathcal{T}_{A,k}\}_{k=1}^{d}, {TB,k}k=1d\{\mathcal{T}_{B,k}\}_{k=1}^{d}; sketch TT cores {TS,k}k=1d\{\mathcal{T}_{S,k}\}_{k=1}^{d}.

Ensure: Right environments {Rk}k=1d−1\{\mathcal{R}_{k}\}_{k=1}^{d-1}.

  1. Rd←1∈R1×1×1\mathcal{R}_{d}\gets1\in\mathbb{R}^{1\times1\times1}

  2. for k=d,d−1,…,2k=d,d-1,\ldots,2 do

  3. Rk−1←EINSUM⁡("ra n ra’, rb n rb’, s n s’, ra’ rb’ s’ -> ra rb s",TA,k,TB,k,TS,k,Rk)\mathcal{R}_{k-1}\gets\operatorname{EINSUM}(\text{"ra n ra', rb n rb', s n s', ra' rb' s' -> ra rb s"},\mathcal{T}_{A,k},\mathcal{T}_{B,k},\mathcal{T}_{S,k},\mathcal{R}_{k})

  4. end for

  5. return {Rk}k=1d−1\{\mathcal{R}_{k}\}_{k=1}^{d-1}

HaTT

HaTT [55] replaces the deterministic SVD-based truncation of TT-ROUND with a randomized sketching approach inspired by randomized linear algebra [23, 10]. Like TT-ROUND, it exploits the Matrix-Kronecker structure of the inflated cores TA,k⊗TB,k\mathcal{T}_{A,k}\otimes\mathcal{T}_{B,k} to avoid materializing them. Unlike TT-ROUND—whose per-site SVDs (deterministic or randomized) still operate on full unfoldings of the inflated working tensor W\mathcal{W}—HaTT projects X\mathcal{X} against a TT sketch S\mathcal{S} of width s=R+roversamples=R+r_{\mathrm{oversample}} first and applies SVDs only on small sketched matrices of column dimension ss.

The algorithm proceeds in two phases.

Phase 1: Sketched right environments. A random TT sketch S\mathcal{S} with cores TS,k∈Rsk−1×nk×sk\mathcal{T}_{S,k}\in\mathbb{R}^{s_{k-1}\times n_k\times s_k} of width ss is drawn (e.g., with Gaussian or Rademacher entries) and left-orthogonalized for numerical stability. A right-to-left sweep (Algorithm 2) then produces the right environments Rk∈RrkA×rkB×sk\mathcal{R}_{k}\in\mathbb{R}^{r_k^{A}\times r_k^{B}\times s_k} for k=1,…,d−1k=1,\ldots,d-1. Each Rk\mathcal{R}_{k} represents the contraction of the inflated cores at positions k+1,…,dk+1,\ldots,d projected against the right tail of S\mathcal{S}.

As an extension to the original HaTT formulation, we additionally allow the user to provide a TT G\mathcal{G} as an initial guess of the solution, which is then used in place of a random sketch. This can leverage prior knowledge about X\mathcal{X} – for instance, the result of a previous Hadamard product in a bottom-up compilation – to bias the sketch towards the relevant subspace.

Phase 2: Left-to-right projection sweep. A left-to-right sweep analogous to that of TT-ROUND constructs the cores of X~\widetilde{\mathcal{X}}. At each site kk, the algorithm contracts the left environment L\mathcal{L}, the inflated core TA,k⊗TB,k\mathcal{T}_{A,k}\otimes\mathcal{T}_{B,k}, and the sketched right environment Rk\mathcal{R}_{k} into a small working tensor M\mathcal{M} of shape rk−1×nk×skr_{k-1}\times n_k\times s_k, where rk−1r_{k-1} is the running compressed rank. A truncated SVD on the unfolding of M\mathcal{M} then yields the left singular vectors used as the new core TX~,k\mathcal{T}_{\widetilde{X},k}. The left environment is updated by contracting the new core back against the inflated cores, and the loop proceeds. As in TT-ROUND, the last core requires no SVD since sd=1s_d=1.

Complexity. The dominant cost at each site is the truncated SVD on M\mathcal{M} of shape rk−1nk×skr_{k-1}n_k\times s_k, costing O(nr2s)O(nr^2s) under uniform ranks. Summed over the dd sites, this gives O(dnr2s)O(dnr^2s) time. Memory is dominated by storing the right environments, at O(r2s)O(r^2s) each. The right-environment sweep (Algorithm 2) has the same asymptotic cost of O(dnr2s)O(dnr^2s). For s≈rs\approx r, the overall time becomes O(dnr3)O(dnr^3).

TCI

Tensor Cross Interpolation (TCI) [42, 39] approximates the Hadamard product X=A∗B\mathcal{X}=\mathcal{A}*\mathcal{B} by a TT X~\widetilde{\mathcal{X}} that interpolates X\mathcal{X} at a small set of carefully chosen entries. Unlike TT-ROUND and HaTT, TCI never materializes a Kronecker core nor performs an SVD on a full unfolding of X\mathcal{X}: at each site, a small supercore is formed by contracting a ww-site window of the input cores with their interpolated environments, and an interpolative decomposition picks the rows or columns of that supercore that best interpolate it. We present the algorithm with two-site sweeps (w=2w=2); the generalization to K>2K>2 factors and larger windows is straightforward.

Pivots and shared environments. Let p≤Rp\le R denote the current number of pivots at a given bond. TCI maintains per-factor environments that share the pivot axis across factors:

Algorithm 3 Hadamard HATT

Require: TTs A,B\mathcal{A}, \mathcal{B}; max rank RR; tolerance ϵ\epsilon; sketch width s=R+roversamples = R + r_{\mathrm{oversample}}; (optional) initial guess TT G\mathcal{G}.

Ensure: TT approximation X~≈A∗B\widetilde{\mathcal{X}} \approx\mathcal{A} * \mathcal{B}.

1: A←RIGHTORTHOGONALIZE⁡(A)\mathcal{A} \leftarrow\operatorname{RIGHTORTHOGONALIZE}(\mathcal{A}) 2: B←RIGHTORTHOGONALIZE⁡(B)\mathcal{B} \leftarrow\operatorname{RIGHTORTHOGONALIZE}(\mathcal{B}) 3: S←G\mathcal{S} \leftarrow\mathcal{G} if provided, else RANDOMTT⁡(dims,s)\operatorname{RANDOMTT}(\mathrm{dims},s) 4: S←LEFTORTHOGONALIZE⁡(S)\mathcal{S} \leftarrow\operatorname{LEFTORTHOGONALIZE}(\mathcal{S}) 5: {Rk}k=1d−1←SKETCHEDRIGHTENVS⁡(A,B,S)\{\mathcal{R}_k\}_{k=1}^{d-1} \leftarrow\operatorname{SKETCHEDRIGHTENVS}(\mathcal{A},\mathcal{B},\mathcal{S}) ▷ Algorithm 2 6: Rd←1∈R1×1×1\mathcal{R}_d \leftarrow1 \in\mathbb{R}^{1 \times1 \times1} 7: L←1∈R1×1×1\mathcal{L} \leftarrow1 \in\mathbb{R}^{1 \times1 \times1} ▷ initial left environment 8: for k=1,…,dk = 1,\ldots,d do 9: M←EINSUM⁡("r ra rb, ra n ra’, rb n rb’, ra’ rb’ s’ -> r n s’",L,TA,k,TB,k,Rk)\mathcal{M} \leftarrow\operatorname{EINSUM}(\text{"r ra rb, ra n ra’, rb n rb’, ra’ rb’ s’ -> r n s’"}, \mathcal{L},\mathcal{T}_{\mathcal{A},k},\mathcal{T}_{\mathcal{B},k},\mathcal{R}_k) 10: if k<dk < d then 11: M←REARRANGE⁡("r n s’ -> (r n) s’",M)\mathcal{M} \leftarrow\operatorname{REARRANGE}(\text{"r n s’ -> (r n) s’"},\mathcal{M}) 12: U,⋅,⋅←TRUNCATEDSVD⁡(M;ϵ,R)\mathcal{U},\cdot,\cdot\leftarrow\operatorname{TRUNCATEDSVD}(\mathcal{M};\epsilon,R) 13: TX~,k←REARRANGE⁡("(r n) r’ -> r n r’",U)\mathcal{T}_{\widetilde{\mathcal{X}},k} \leftarrow\operatorname{REARRANGE}(\text{"(r n) r’ -> r n r’"},\mathcal{U}) 14: L←EINSUM⁡("r n r’, r ra rb, ra n ra’, rb n rb’ -> r’ ra’ rb’",TX~,k,L,TA,k,TB,k)\mathcal{L} \leftarrow\operatorname{EINSUM}(\text{"r n r’, r ra rb, ra n ra’, rb n rb’ -> r’ ra’ rb’"},\mathcal{T}_{\widetilde{\mathcal{X}},k},\mathcal{L},\mathcal{T}_{\mathcal{A},k},\mathcal{T}_{\mathcal{B},k}) 15: else 16: TX~,d←M\mathcal{T}_{\widetilde{\mathcal{X}},d} \leftarrow\mathcal{M} ▷ sd=1s_d = 1, so M\mathcal{M} already has shape rd−1×nd×1r_{d-1} \times n_d \times1 17: end if 18: end for 19: return TT X~\widetilde{\mathcal{X}} with cores {TX~,k}k=1d\{\mathcal{T}_{\widetilde{\mathcal{X}},k}\}_{k=1}^{d}.

  • Left environments LiA∈Rp×ri−1A\mathcal{L}^{\mathcal{A}}_i \in\mathbb{R}^{p \times r^A_{i-1}} and LiB∈Rp×ri−1B\mathcal{L}^{\mathcal{B}}_i \in\mathbb{R}^{p \times r^B_{i-1}} holding pp contracted slices of the left tail of A\mathcal{A} and B\mathcal{B} respectively.

  • Right environments RiA∈RriA×p\mathcal{R}^{\mathcal{A}}_i \in\mathbb{R}^{r^A_i \times p} and RiB∈RriB×p\mathcal{R}^{\mathcal{B}}_i \in\mathbb{R}^{r^B_i \times p} holding pp contracted slices of the right tails.

The shared pivot axis encodes the Hadamard product structure without ever forming Kronecker cores: at each bond, both factors are interpolated at the same set of physical-pivot indices.

Interpolative primitives. We use two primitives for selecting pivots and interpolating from them.

  • MAXVOL⁡\operatorname{MAXVOL} [20]: given a matrix M\mathbf{M}, MAXVOL⁡(M;R)\operatorname{MAXVOL}(\mathbf{M};R) returns up to RR column indices of M\mathbf{M} that form a near-maximum-volume submatrix.

  • PRRLDU⁡\operatorname{PRRLDU} [48]: a partially rank-revealing LU decomposition. Its row-pivoted variant PRRLDU⁡row(M;ϵ,R)\operatorname{PRRLDU}_{\mathrm{row}}(\mathbf{M};\epsilon,R) returns an interpolation matrix Z\mathcal{Z} and a pivot set such that M≈Z⋅M[pivot,:]\mathbf{M} \approx\mathcal{Z} \cdot\mathbf{M}[\mathrm{pivot},:]. The column-pivoted variant PRRLDU⁡col\operatorname{PRRLDU}_{\mathrm{col}} analogously yields M≈M[:,pivot]⋅Z\mathbf{M} \approx\mathbf{M}[:,\mathrm{pivot}] \cdot\mathcal{Z}.

Phase 1: Maxvol warm-up. A right-to-left sweep (Algorithm 4) initializes the right environments. At each site, per-factor supercores ΦA,ΦB\boldsymbol{\Phi}_{\mathcal{A}}, \boldsymbol{\Phi}_{\mathcal{B}} are formed by contracting the current right environment with the corresponding core; their joint Hadamard matrix Φ\boldsymbol{\Phi} has rows that range over the outer product of the per-factor left bonds and columns that range over the shared physical-pivot indices. MAXVOL⁡\operatorname{MAXVOL} selects up to RR such columns, and the picked columns of each ΦA,ΦB\boldsymbol{\Phi}_{\mathcal{A}}, \boldsymbol{\Phi}_{\mathcal{B}} become the next right environments.

Phase 2: Alternating sweeps. Sweeps of Algorithm 5 (L2R) and Algorithm 6 (R2L) refine the pivots and emit the cores of X~\widetilde{\mathcal{X}}. At each interior site of an L2R sweep, per-factor supercores are formed by contracting the left environment, two consecutive cores, and the right environment. They are combined element-wise into the joint supercore Φ\boldsymbol{\Phi}, flattened into a matrix, and decomposed by PRRLDU⁡row\operatorname{PRRLDU}_{\mathrm{row}} into an interpolation matrix Z\mathcal{Z} and a row pivot. The interpolation matrix becomes

Algorithm 4 Maxvol right environments for $\mathcal{X}=\mathcal{A} * \mathcal{B}$
Require: TTs $\mathcal{A},\mathcal{B}$; max rank $R$.
Ensure: Right environments $\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}_{i=1}^{d-1}$.
1: $\mathcal{R}^{\mathcal{A}}_d \leftarrow 1 \in \mathbb{R}^{1\times 1}$; $\mathcal{R}^{\mathcal{B}}_d \leftarrow 1 \in \mathbb{R}^{1\times 1}$
2: for $i=d,d-1,\ldots,2$ do
3:   for $\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\}$ do
4:     $\Phi_{\mathcal{Y}}\leftarrow\operatorname{EINSUM}("$r n r', r' p -> r (n p)"$, \mathcal{T}_{\mathcal{Y},i},\mathcal{R}^{\mathcal{Y}}_i)$
5:   end for
6:   $\Phi\leftarrow\operatorname{EINSUM}("$ra q, rb q -> (ra rb) q"$, \Phi_{\mathcal{A}},\Phi_{\mathcal{B}})$
7:   $\operatorname{pivot}\leftarrow\operatorname{MAXVOL}(\Phi;R)$
8:   for $\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\}$ do
9:     $\mathcal{R}^{\mathcal{Y}}_{i-1}\leftarrow\Phi_{\mathcal{Y}}[:,\operatorname{pivot}]$
10:  end for
11: end for
12: return $\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}_{i=1}^{d-1}$
Algorithm 5 Left-to-right TCI sweep
Require: TTs $\mathcal{A},\mathcal{B}$; left envs $\{\mathcal{L}^{\mathcal{A}}_i,\mathcal{L}^{\mathcal{B}}_i\}_{i=1}^{d-1}$; right envs $\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}_{i=1}^{d}$; max rank $R$; tolerance $\epsilon$.
Ensure: Cores $\{\mathcal{T}_{\widetilde{\mathcal{X}},i}\}_{i=1}^{d}$ and updated left envs.
1: $\mathcal{L}^{\mathcal{A}}_1\leftarrow 1\in\mathbb{R}^{1\times 1}$; $\mathcal{L}^{\mathcal{B}}_1\leftarrow 1\in\mathbb{R}^{1\times 1}$
2: for $i=1,\ldots,d-1$ do
3:   for $\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\}$ do
4:     $\Phi_{\mathcal{Y}}\leftarrow\operatorname{EINSUM}("$p r, r n r', r' m r'', r'' q -> p n m q"$, $\mathcal{L}^{\mathcal{Y}}_i,\mathcal{T}_{\mathcal{Y},i},\mathcal{T}_{\mathcal{Y},i+1},\mathcal{R}^{\mathcal{Y}}_{i+1})$
5:   end for
6:   $\Phi\leftarrow\Phi_{\mathcal{A}}*\Phi_{\mathcal{B}}$ ▷ element-wise Hadamard
7:   $\Phi\leftarrow\operatorname{REARRANGE}("$p n m q -> (p n) (m q)"$, \Phi)$
8:   $(Z,\operatorname{pivot})\leftarrow\operatorname{PRRLDU}_{\mathrm{row}}(\Phi;\epsilon,R)$
9:   $\mathcal{T}_{\widetilde{\mathcal{X}},i}\leftarrow\operatorname{REARRANGE}("$ (p n) r' -> p n r'"$, Z)$
10:  for $\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\}$ do
11:    $\mathcal{L}^{\mathcal{Y}}_{i+1}\leftarrow\operatorname{REARRANGE}(\operatorname{EINSUM}("$p r, r n r' -> (p n) r'"$, $\mathcal{L}^{\mathcal{Y}}_i,\mathcal{T}_{\mathcal{Y},i})[\operatorname{pivot},:]$
12:  end for
13:  if $i=d-1$ then
14:    $\mathcal{T}_{\widetilde{\mathcal{X}},d}\leftarrow\operatorname{REARRANGE}("$r' n -> r' n 1"$, $\Phi[\operatorname{pivot},:]$)$
15:  end if
16: end for
17: return cores $\{\mathcal{T}_{\widetilde{\mathcal{X}},i}\}_{i=1}^{d}$, updated $\{\mathcal{L}^{\mathcal{A}}_i,\mathcal{L}^{\mathcal{B}}_i\}_{i=1}^{d}$

the new core TX~,i\mathcal{T}_{\widetilde{\mathcal{X}},i}, and the pivot updates the left environments of A\mathcal{A} and B\mathcal{B}. The R2L sweep is symmetric, processing sites from right to left and using PRRLDU⁡col\operatorname{PRRLDU}_{\mathrm{col}} to update right environments.

Boundary cores. The L2R sweep additionally extracts the rightmost core TX~,d\mathcal{T}_{\widetilde{\mathcal{X}},d} directly from the boundary supercore at i=d−1i=d-1 (whose right rank is already rd=1r_d=1). The R2L sweep mirrors this for the leftmost core.

Complexity. At each interior site, the dominant cost is forming the joint supercore Φ\Phi and applying PRRLDU to its (p⋅n)×(n⋅p)(p\cdot n)\times(n\cdot p) unfolding. The per-factor four-tensor contractions cost O(n2pr2)O(n^2pr^2), the elementwise Hadamard costs O(n2p2)O(n^2p^2), and PRRLDU costs O(n2p3)O(n^2p^3) in the worst case. With p≤R≈rp\le R\approx r, the per-site cost is O(n2r3)O(n^2r^3). Summing over the dd sites and a constant number of sweeps gives an overall time complexity of O(dn2r3)O(dn^2r^3) and memory O(n2r2)O(n^2r^2), dominated by Φ\Phi. The maxvol warm-up has lower per-site cost, O(nr3)O(nr^3), and is dominated by the sweep phase.

Algorithm 6 Right-to-left TCI sweep

Require: TTs A,B\mathcal{A}, \mathcal{B}; left envs {LiA,LiB}i=1d\{\mathcal{L}^{\mathcal{A}}_i,\mathcal{L}^{\mathcal{B}}_i\}_{i=1}^{d}; right envs {RiA,RiB}i=1d−1\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}_{i=1}^{d-1}; max rank RR; tolerance ϵ\epsilon.

Ensure: Cores {T~X,i}i=1d\{\widetilde{\mathcal{T}}_{\mathcal{X},i}\}_{i=1}^{d} and updated right envs.

1: RdA←1\mathcal{R}^{\mathcal{A}}_d \leftarrow1; RdB←1\mathcal{R}^{\mathcal{B}}_d \leftarrow1 2: for i=d,d−1,…,2i=d,d-1,\ldots,2 do 3: &nbsp;&nbsp;&nbsp;&nbsp;for Y∈{A,B}\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\} do 4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ΦY←EINSUM⁡("p r, r n r’, r’ m r’’, r’’ q -> p n m q",Li−1Y,TY,i−1,TY,i,RiY)\Phi_{\mathcal{Y}}\leftarrow\operatorname{EINSUM}(\text{"p r, r n r’, r’ m r’’, r’’ q -> p n m q"},\mathcal{L}^{\mathcal{Y}}_{i-1},\mathcal{T}_{\mathcal{Y},i-1},\mathcal{T}_{\mathcal{Y},i},\mathcal{R}^{\mathcal{Y}}_i) 5: &nbsp;&nbsp;&nbsp;&nbsp;end for 6: &nbsp;&nbsp;&nbsp;&nbsp;Φ←ΦA∗ΦB\Phi\leftarrow\Phi_{\mathcal{A}}*\Phi_{\mathcal{B}} 7: &nbsp;&nbsp;&nbsp;&nbsp;Φ←REARRANGE⁡("p n m q -> (p n) (m q)",Φ)\Phi\leftarrow\operatorname{REARRANGE}(\text{"p n m q -> (p n) (m q)"},\Phi) 8: &nbsp;&nbsp;&nbsp;&nbsp;(Z,pivot⁡)←PRRLDU⁡col(Φ;ϵ,R)(\mathcal{Z},\operatorname{pivot})\leftarrow\operatorname{PRRLDU}_{\mathrm{col}}(\Phi;\epsilon,R) 9: &nbsp;&nbsp;&nbsp;&nbsp;T~X,i←REARRANGE⁡("r’ (m q) -> r’ m q",Z)\widetilde{\mathcal{T}}_{\mathcal{X},i}\leftarrow\operatorname{REARRANGE}(\text{"r’ (m q) -> r’ m q"},\mathcal{Z}) 10: &nbsp;&nbsp;&nbsp;&nbsp;for Y∈{A,B}\mathcal{Y}\in\{\mathcal{A},\mathcal{B}\} do 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ri−1Y←REARRANGE⁡(EINSUM⁡("r m r’, r’ q -> r (m q)",TY,i,RiY)[:,pivot⁡])\mathcal{R}^{\mathcal{Y}}_{i-1}\leftarrow\operatorname{REARRANGE}(\operatorname{EINSUM}(\text{"r m r’, r’ q -> r (m q)"},\mathcal{T}_{\mathcal{Y},i},\mathcal{R}^{\mathcal{Y}}_i)[:,\operatorname{pivot}]) 12: &nbsp;&nbsp;&nbsp;&nbsp;end for 13: &nbsp;&nbsp;&nbsp;&nbsp;if i=2i=2 then 14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;T~X,1←REARRANGE⁡("n r’ -> 1 n r’",Φ[:,pivot⁡])\widetilde{\mathcal{T}}_{\mathcal{X},1}\leftarrow\operatorname{REARRANGE}(\text{"n r’ -> 1 n r’"},\Phi[:,\operatorname{pivot}]) 15: &nbsp;&nbsp;&nbsp;&nbsp;end if 16: end for 17: return cores {T~X,i}i=1d\{\widetilde{\mathcal{T}}_{\mathcal{X},i}\}_{i=1}^{d}, updated {RiA,RiB}i=1d\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}_{i=1}^{d}

Algorithm 7 TCI for X=A∗B\mathcal{X}=\mathcal{A}*\mathcal{B}

Require: TTs A,B\mathcal{A},\mathcal{B}; max rank RR; tolerance ϵ\epsilon; number of sweeps TT.

Ensure: TT approximation X~≈A∗B\widetilde{\mathcal{X}}\approx\mathcal{A}*\mathcal{B}.

1: A←RIGHTORTHOGONALIZE⁡(A)\mathcal{A}\leftarrow\operatorname{RIGHTORTHOGONALIZE}(\mathcal{A}); B←RIGHTORTHOGONALIZE⁡(B)\mathcal{B}\leftarrow\operatorname{RIGHTORTHOGONALIZE}(\mathcal{B}) 2: {RiA,RiB}←MAXVOLRIGHTENVS⁡(A,B;R)\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}\leftarrow\operatorname{MAXVOLRIGHTENVS}(\mathcal{A},\mathcal{B};R) ▷ Algorithm 4 3: for t=1,…,Tt=1,\ldots,T do 4: &nbsp;&nbsp;&nbsp;&nbsp;(cores,{LiA,LiB})←L2R-TCI⁡(A,B,{L},{R};R,ϵ)(\text{cores},\{\mathcal{L}^{\mathcal{A}}_i,\mathcal{L}^{\mathcal{B}}_i\})\leftarrow\operatorname{L2R\text{-}TCI}(\mathcal{A},\mathcal{B},\{\mathcal{L}\},\{\mathcal{R}\};R,\epsilon) ▷ Algorithm 5 5: &nbsp;&nbsp;&nbsp;&nbsp;(cores,{RiA,RiB})←R2L-TCI⁡(A,B,{L},{R};R,ϵ)(\text{cores},\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\})\leftarrow\operatorname{R2L\text{-}TCI}(\mathcal{A},\mathcal{B},\{\mathcal{L}\},\{\mathcal{R}\};R,\epsilon) ▷ Algorithm 6 6: end for 7: return TT X~\widetilde{\mathcal{X}} with cores cores

RSI

Randomized Sketching with Interpolation (RSI) [38] replaces TCI’s maxvol-based right environment construction with random sketching. Like HATT, RSI sketches each input TT independently rather than evaluating exact entries; like TCI, it then performs interpolative-decomposition sweeps to construct X~\widetilde{\mathcal{X}}. Compared to HATT, RSI differs in two ways: (i) it uses a Khatri-Rao product (KRP) sketch rather than a TT sketch, and (ii) it uses interpolative decompositions (prrLDU) rather than SVDs to truncate at each site. Because the sketching is per-factor, RSI side-steps the combinatorial maxvol search of TCI (which is specific to the Hadamard product) and immediately extends to any non-linear operation over multiple TTs.

The original RSI formulation uses a single L2R sweep after sketching. We extend it to alternating L2R/R2L sweeps, which follow naturally from the TCI connection: once a first L2R sweep produces interpolative left environments, subsequent sweeps refine the pivots in both directions exactly as in TCI.

KRP sketches. The original RSI paper uses a Khatri-Rao product sketch: a set of dd matrices {Si∈Rni×s}i=1d\{\mathcal{S}_i\in\mathbb{R}^{n_i\times s}\}_{i=1}^{d} with i.i.d. random entries (e.g., Gaussian or Rademacher), where s=R+roversamples=R+r_{\mathrm{oversample}} is the sketch width. Unlike the TT sketch used in HATT—which has sketch cores have an internal bond structure TS,k∈Rsk−1×nk×sk\mathcal{T}_{\mathcal{S},k}\in\mathbb{R}^{s_{k-1}\times n_k\times s_k}—the KRP sketch has a single “flat” sketch axis ss shared across all dd sites. This makes the contractions in the right-env sweep structurally simpler.

Algorithm 8 KRP-sketched right environments for a TT A\mathcal{A}

Require: TT cores {TA,i}i=1d\{\mathcal{T}_{\mathcal{A},i}\}_{i=1}^{d}; KRP sketch matrices {Si∈Rni×s}i=1d\{\mathcal{S}_i \in\mathbb{R}^{n_i \times s}\}_{i=1}^{d}.

Ensure: Right environments {RiA}i=1d−1\{\mathcal{R}^{\mathcal{A}}_i\}_{i=1}^{d-1}.

  1. RdA←1∈R1×s\mathcal{R}^{\mathcal{A}}_d \gets1 \in\mathbb{R}^{1 \times s} ▷ all-ones vector along the sketch axis

  2. for i=d,d−1,…,2i=d,d-1,\ldots,2 do

  3. Ri−1A←EINSUM⁡("r n r’, n s, r’ s -> r s",TA,i,Si,RiA)\mathcal{R}^{\mathcal{A}}_{i-1} \gets\operatorname{EINSUM}(\text{"r n r', n s, r' s -> r s"},\mathcal{T}_{\mathcal{A},i},\mathcal{S}_i,\mathcal{R}^{\mathcal{A}}_i)

  4. end for

  5. return {RiA}i=1d−1\{\mathcal{R}^{\mathcal{A}}_i\}_{i=1}^{d-1}

Algorithm 9 RSI for X=A∗B\mathcal{X}=\mathcal{A} * \mathcal{B}

Require: TTs A,B\mathcal{A},\mathcal{B}; max rank RR; tolerance ϵ\epsilon; sketch width s=R+roversamples=R+r_{\mathrm{oversample}}; number of sweeps T≥1T \ge1.

Ensure: TT approximation X~≈A∗B\widetilde{\mathcal{X}} \approx\mathcal{A} * \mathcal{B}.

  1. A←RIGHTORTHOGONALIZE⁡(A)\mathcal{A} \gets\operatorname{RIGHTORTHOGONALIZE}(\mathcal{A}); B←RIGHTORTHOGONALIZE⁡(B)\mathcal{B} \gets\operatorname{RIGHTORTHOGONALIZE}(\mathcal{B})

  2. Draw KRP sketches {Si∈Rni×s}i=1d\{\mathcal{S}_i \in\mathbb{R}^{n_i \times s}\}_{i=1}^{d} with i.i.d. random entries

  3. {RiA}←KRP-RIGHTENVS⁡(A,{Si})\{\mathcal{R}^{\mathcal{A}}_i\} \gets\operatorname{KRP\text{-}RIGHTENVS}(\mathcal{A},\{\mathcal{S}_i\}) ▷ Algorithm 8

  4. {RiB}←KRP-RIGHTENVS⁡(B,{Si})\{\mathcal{R}^{\mathcal{B}}_i\} \gets\operatorname{KRP\text{-}RIGHTENVS}(\mathcal{B},\{\mathcal{S}_i\})

  5. for t=1,…,Tt=1,\ldots,T do

  6. (cores,{LiA,LiB})←L2R-TCI⁡(A,B,{L},{R};R,ϵ)(\text{cores},\{\mathcal{L}^{\mathcal{A}}_i,\mathcal{L}^{\mathcal{B}}_i\}) \gets\operatorname{L2R\text{-}TCI}(\mathcal{A},\mathcal{B},\{\mathcal{L}\},\{\mathcal{R}\};R,\epsilon) ▷ Algorithm 5

  7. (cores,{RiA,RiB})←R2L-TCI⁡(A,B,{L},{R};R,ϵ)(\text{cores},\{\mathcal{R}^{\mathcal{A}}_i,\mathcal{R}^{\mathcal{B}}_i\}) \gets\operatorname{R2L\text{-}TCI}(\mathcal{A},\mathcal{B},\{\mathcal{L}\},\{\mathcal{R}\};R,\epsilon) ▷ Algorithm 6; original RSI omits this and stops after the first L2R

  8. end for

  9. return TT X~\widetilde{\mathcal{X}} with cores cores

Phase 1: Sketched right environments. A right-to-left sweep (Algorithm 8) computes the per-TT right environments RiY∈RriY×s\mathcal{R}^{Y}_i \in\mathbb{R}^{r_i^Y \times s} for Y∈{A,B}Y \in\{\mathcal{A},\mathcal{B}\}. At each site, the previous right environment is updated by contracting the core with the per-site sketch matrix on the physical dimension and broadcasting on the shared sketch axis.

Phase 2: Alternating sweeps. The L2R and R2L sweeps of TCI (Algorithms 5 and 6) are reused unchanged: the sketched right environments play the same role in the supercore contractions as TCI’s maxvol-selected ones. After the first L2R sweep, the left environments become interpolative (subset-based) just as in TCI; from then on, the algorithm is identical to TCI. The original RSI corresponds to stopping after this first L2R sweep, before any R2L.

Complexity. Forming the KRP-sketched right environments costs O(dnr2s)\mathcal{O}(dnr^2s) per TT, dominated by the per-site einsum. The subsequent TCI sweeps inherit the per-sweep complexity of O(dn2r3)\mathcal{O}(dn^2r^3) in time and O(n2r2)\mathcal{O}(n^2r^2) in memory. With s≈rs \approx r and a constant number of sweeps, the overall cost matches TCI: O(dn2r3)\mathcal{O}(dn^2r^3) time, O(n2r2)\mathcal{O}(n^2r^2) memory. The savings over TCI come not from asymptotic complexity but from avoiding the combinatorial maxvol search in the warm-up; the savings over HATT come from per-site sketches replacing TT sketches in the right-env sweep.

NeurIPS Paper Checklist

Claims

Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

Answer: [Yes]

Justification: The contributions are listed explicitly at the end of the Introduction. The framework and tensor-train methods are developed in Sections 2 to 4, and the inference and learning claims are evaluated in Section 5. In particular, Section 5.3 distinguishes tasks where independence reduction remains competitive from tasks with shared auxiliary variables, where preserving dependencies through compilation substantially improves learning.

Guidelines:

  • The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.

  • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.

  • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

  • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

Limitations

Question: Does the paper discuss the limitations of the work performed by the authors?

Answer: [Yes]

Justification: A dedicated “Limitations” paragraph follows the Conclusions and discusses the suitability of current recompression methods for sparse Boolean tensors as well as the need to study the effect of program factorization and auxiliary-variable structure across more neurosymbolic methods.

Guidelines:

  • The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.

  • The authors are encouraged to create a separate “Limitations” section in their paper.

  • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

  • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

  • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

  • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

  • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

  • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

Theory assumptions and proofs

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

Answer: [Yes]

Justification: Theoretical results (e.g. Theorem C.1 and the corresponding corollary) are stated with all assumptions and proved in Section C; supporting derivations for the independence approximation are given in Section E.

Guidelines:

  • The answer [N/A] means that the paper does not include theoretical results.

  • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

  • All assumptions should be clearly stated or referenced in the statement of any theorems.

  • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

  • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

  • Theorems and Lemmas that the proof relies upon should be properly referenced.

Experimental result reproducibility

Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

Answer: [Yes]

Justification: We describe the framework and pipeline choices in Section 4; provide tensor-train operations, multiplication schedules, and recompression algorithms in Sections F, F.2, G and I; define the six learning tasks and their factorizations in Section H.3; and report compilation settings, compute budgets, learning objectives, decoding procedures, and hyperparameters in Section H.5.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

  • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

  • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

  • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).

(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

Open access to data and code

Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

Answer: [Yes]

Justification: Code and instructions for reproducing the experiments are available through the public repository linked in the paper. Dependencies are pinned and reproducibly installable with the uv package manager.

Guidelines:

  • The answer [N/A] means that paper does not include experiments requiring code.

  • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

  • While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

  • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

  • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

  • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

  • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

  • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

Experimental setting/details

Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?

Answer: [Yes]

Justification: Section Section 5 describes the benchmarks, baselines, metrics, and main experimental setup. Sections H.3 to H.5 specify the task construction and splits, weighted-inference protocol, compilation configurations, optimizer, learning rate, batch size, number of epochs, and decoding procedure.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

  • The full details can be provided either with the code, in appendix, or as supplemental material.

Experiment statistical significance

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

Answer: [Yes] Justification: Results are averaged over ten runs with fixed datasets across methods and runs, capturing variations across training and compute randomness. Figures report the mean and standard-deviation error bars across runs.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

  • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

  • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

  • The assumptions made should be given (e.g., Normally distributed errors).

  • It should be clear whether the error bar is the standard deviation or the standard error of the mean.

  • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

  • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).

  • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

Experiments compute resources

Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

Answer: [Yes]

Justification: Section H.5 specifies the NVIDIA A10G GPU and its memory, the CPU memory cap for SDD compilation, and the compilation and training wall-clock limits. Compilation times are reported in the inference figures, and runs exceeding the stated time or memory budgets are marked as timed out or out of memory.

Guidelines:

  • The answer [N/A] means that the paper does not include experiments.

  • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

  • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

  • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).

Code of ethics

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

Answer: [Yes]

Justification: We have reviewed the NeurIPS Code of Ethics and the research conforms to it; the work involves no human subjects, no personal data, and does not pose ethical concerns.

Guidelines:

  • The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.

  • If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.

  • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

Broader impacts

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

Answer: [N/A]

Justification: The paper is foundational research on tractable inference primitives for neurosymbolic systems, with no direct path to positive or negative societal applications beyond the general impact of more reliable probabilistic reasoning tools.

Guidelines:

  • The answer [N/A] means that there is no societal impact of the work performed.

  • If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.

  • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

  • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

  • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

  • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

Safeguards

Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?

Answer: [N/A]

Justification: The paper releases no pre-trained generative models, image generators, or scraped datasets with risk of misuse.

Guidelines:

  • The answer [N/A] means that the paper poses no such risks.

  • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

  • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

  • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

Licenses for existing assets

Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes]

Justification: We cite the original works for all datasets, baselines, and external libraries used (e.g., ViSudo datasets, SatNet, KaHyPar, NetworkX), and use them under their standard research licenses.

Guidelines:

  • The answer [N/A] means that the paper does not use existing assets.

  • The authors should cite the original paper that produced the code package or dataset.

  • The authors should state which version of the asset is used and, if possible, include a URL.

  • The name of the license (e.g., CC-BY 4.0) should be included for each asset.

  • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

  • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

  • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

  • If this information is not available online, the authors are encouraged to reach out to the asset’s creators.

13. New assets

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

Answer: [N/A]

Justification: The paper does not release new datasets or pre-trained models. The code is research code provided with reproducibility instructions but does not consist in an asset.

Guidelines:

  • The answer [N/A] means that the paper does not release new assets.

  • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

  • The paper should discuss whether and how consent was obtained from people whose asset is used.

  • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

14. Crowdsourcing and research with human subjects

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

Answer: [N/A]

Justification: The paper involves no crowdsourcing or research with human subjects.

Guidelines:

  • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

  • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

  • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.

15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

Answer: [N/A]

Justification: The paper involves no human subjects research.

Guidelines:

  • The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.

  • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

  • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

  • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

Declaration of LLM usage

Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.

Answer: [Yes]

Justification: We include a voluntary AI use statement in the acknowledgements. LLMs are not part of the core methodology of this paper. Use of generative AI tools was limited to help in coding some experiments, not the model, and was reviewed by the authors.

Guidelines:

  • The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.

  • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

References

  1. [1]Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Semantic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Processing Systems 35 (NeurIPS), volume 35, pages 29944–29959. Curran Associates, Inc., 2022.arxiv.org/abs/2206.00426
  2. [2]Kareem Ahmed, Kai-Wei Chang, and Guy Van den Broeck. Semantic strengthening of neuro-symbolic learning, 2023. URL https://arxiv.org/abs/2302.14207.
  3. [3]Jonathan E. Atkins, Erik G. Boman, and Bruce Hendrickson. A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing, 28(1):297–310, 2003. ISSN 0097-5397. doi: 10.1137/s0097539795285771. URL https://doi.org/10.1137/s0097539795285771.
  4. [4]Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Yang Wang, and Lise Getoor. Visual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. In International Workshop on Neural-Symbolic Learning and Reasoning (NeSy), Windsor, United Kingdom, 2022.
  5. [5]Samy Badreddine, Artur S. d’Avila Garcez, Luciano Serafini, and Michael Spranger. Logic tensor networks. CoRR, abs/2012.13635, 2020. URL https://arxiv.org/abs/2012.13635.
  6. [6]Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger. Assessing satnet’s ability to solve the symbol grounding problem, 2023. URL https://arxiv.org/abs/2312.11522.
  7. [7]Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence., 172(6-7):772–799, 2008.DOI
  8. [8]Seewon Choi, Alaia Solko-Breslin, Rajeev Alur, and Eric Wong. CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning, 2025. URL https://arxiv.org/abs/2503.24123. Version Number: 1.
  9. [9]YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic modeling. Technical report, University of California, Los Angeles (UCLA), 2020.
  10. [10]Hussam Al Daas, Grey Ballard, Paul Cazeaux, Eric Hallman, Agnieszka Miedlar, Mirjeta Pasha, Tim W. Reid, and Arvind K. Saibaba. Randomized algorithms for rounding in the tensor-train format, 2021. URL https://arxiv.org/abs/2110.04393.
  11. [11]Alessandro Daniele, Tommaso Campari, Sagar Malhotra, and Luciano Serafini. Deep Symbolic Learning: Discovering Symbols and Rules from Perceptions. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 3597–3605, Macau, SAR China, August 2023. International Joint Conferences on Artificial Intelligence Organization. ISBN 978-1-956792-03-4. doi: 10.24963/ijcai.2023/400. URL https://www.ijcai.org/proceedings/2023/400.DOI
  12. [12]Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM), 48: 608–647, 2001.DOI
  13. [13]Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50:280–305, 2003.arxiv.org/abs/1301.3847
  14. [14]Adnan Darwiche. SDD: A new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference on Artificial Intelligence, 2011.
  15. [15]Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research (JAIR), 17:229–264, 2002.
  16. [16]Lucile Dierckx, Alexandre Dubray, Siegfried Nijssen, and J Kwok. Learning from logical constraints with lower- and upper-bound arithmetic circuits. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, pages 5012–5020. International Joint Conferences on Artificial Intelligence, 2025.DOI
  17. [17]Ivan Donadello, Luciano Serafini, and Artur d’Avila Garcez. Logic tensor networks for semantic image interpretation, 2017. URL https://arxiv.org/abs/1705.08968.
  18. [18]Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 2010. ISSN 0008-414X. doi: 10.4153/cjm-1965-045-4. URL https://doi.org/10.4153/cjm-1965-045-4.
  19. [19]Bertram Felgenhauer and Frazer Jarvis. Mathematics of sudoku i. 2006. URL https://api.semanticscholar.org/CorpusID:122734246.
  20. [20]S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. How to find a good submatrix. In Vadim Olshevsky and Eugene Tyrtyshnikov, editors, Matrix Methods: Theory, Algorithms and Applications, pages 247–256. World Scientific, 2010. doi: 10.1142/9789812836021_0015. URL https://www.worldscientific.com/doi/abs/10.1142/9789812836021_0015.DOI
  21. [21]Johnnie Gray and Garnet Kin-Lic Chan. Hyperoptimized approximate contraction of tensor networks with arbitrary geometry. Physical Review X, 14(1), 2024. ISSN 2160-3308. doi: 10.1103/physrevx.14.011009. URL https://doi.org/10.1103/physrevx.14.011009.
  22. [22]Johnnie Gray and Stefanos Kourtis. Hyper-optimized tensor network contraction. Quantum, 5: 410, 2021. ISSN 2521-327X. doi: 10.22331/q-2021-03-15-410. URL https://doi.org/10.22331/q-2021-03-15-410.
  23. [23]Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, 2010. URL https://arxiv.org/abs/0909.4061.
  24. [24]Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In CVPR, 2017.arxiv.org/abs/1612.06890
  25. [25]Angelika Kimmig, Guy Van den Broeck, and Luc De Raedt. Algebraic model counting. Journal of Applied Logic, 22:46–62, 2017.
  26. [26]Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations (ICLR), 2015.arxiv.org/abs/1412.6980
  27. [27]Doga Gizem Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In International Conference on Principles of Knowledge Representation and Reasoning, 2014.
  28. [28]Jean-Marie Lagniez and Pierre Marquis. An improved decision-dnn compiler. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 667–673, 2017. doi: 10.24963/ijcai.2017/93. URL https://doi.org/10.24963/ijcai.2017/93.
  29. [29]Lorenzo Loconte, M. Sladek Aleksanteri, Stefan Mengel, Martin Trapp, Arno Solin, Nicolas Gillis, and Antonio Vergari. Subtractive mixture models via squaring: Representation and learning. In The Twelfth International Conference on Learning Representations (ICLR), 2024.arxiv.org/abs/2310.00724
  30. [30]Lorenzo Loconte, Antonio Mari, Gennaro Gala, Robert Peharz, Cassio de Campos, Erik Quaeghebeur, Gennaro Vessio, and Antonio Vergari. What is the relationship between tensor factorizations and circuits (and how can we exploit it)? arXiv preprint arXiv:2409.07953, 2024.arxiv.org/abs/2409.07953
  31. [31]Jaron Maene and Luc De Raedt. Soft-Unification in Deep Probabilistic Logic. Advances in Neural Information Processing Systems, 36:60804–60820, December 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/bf215fa7fe70a38c5e967e59c44a99d0-Abstract-Conference.html.DOI
  32. [32]Jaron Maene, Vincent Derkinderen, and Luc De Raedt. On the hardness of probabilistic neurosymbolic learning. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 34203–34218. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/maene24a.html.arxiv.org/abs/2406.04472
  33. [33]Jaron Maene, Vincent Derkinderen, and Pedro Zuidberg Dos Martires. KLay: Accelerating arithmetic circuits for neurosymbolic AI. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=zest7wYif8G.arxiv.org/abs/2410.11415
  34. [34]Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. arXiv preprint arXiv:1805.10872, 2018.arxiv.org/abs/1805.10872
  35. [35]Emanuele Marconato, Stefano Teso, and Andrea Passerini. Neuro-symbolic reasoning shortcuts: Mitigation strategies and their limitations, 2023. URL https://arxiv.org/abs/2303.12578.
  36. [36]Emanuele Marconato, Samuele Bortolotti, Emile van Krieken, Paolo Morettin, Elena Umili, Antonio Vergari, Efthymia Tsamoura, Andrea Passerini, and Stefano Teso. Symbol grounding in neuro-symbolic ai: A gentle introduction to reasoning shortcuts, 2026. URL https://arxiv.org/abs/2510.14538.
  37. [37]Wannes Meert and Arthur Choi. Pysdd. In Recent Trends in Knowledge Compilation, number 17381 in Dagstuhl Reports, 2017.DOI
  38. [38]Zhaonan Meng, Yuehaw Khoo, Jiajia Li, and E. Miles Stoudenmire. Recursive sketched interpolation: Efficient hadamard products of tensor trains, 2026. URL https://arxiv.org/abs/2602.17974.
  39. [39]Yuriel Núñez Fernández, Marc K Ritter, Matthieu Jeannin, Jheng-Wei Li, Thomas Kloss, Thibaud Louvet, Satoshi Terasaki, Olivier Parcollet, Jan von Delft, Hiroshi Shinaoka, and Xavier Waintal. Learning tensor networks with tensor cross interpolation: New algorithms and libraries. SciPost Physics, 18(3), March 2025. ISSN 2542-4653. doi: 10.21468/scipostphys.18.3.104. URL http://dx.doi.org/10.21468/SciPostPhys.18.3.104.
  40. [40]Ryoma Onaka, Kengo Nakamura, Masaaki Nishino, and Norihito Yasuda. Tensor decomposition meets knowledge compilation: A study comparing tensor trains with obdds, 2025. URL https://arxiv.org/abs/2502.03702.
  41. [41]Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117–158, 2013.DOI
  42. [42]Ivan Oseledets and Eugene Tyrtyshnikov. TT-cross approximation for multidimensional arrays. Linear Algebra and its Applications, 432(1):70–88, January 2010. ISSN 00243795. doi: 10.1016/j.laa.2009.07.024. URL https://linkinghub.elsevier.com/retrieve/pii/S0024379509003747.DOI
  43. [43]Ivan. V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33: 2295–2317, 2011.DOI
  44. [44]Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zach DeVito, Martin Raison, Aly Khan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. CoRR, abs/1912.01703, 2019. URL http://arxiv.org/abs/1912.01703.
  45. [45]David Pérez-García, F. Verstraete, Michael M. Wolf, and Juan Ignacio Cirac. Matrix product state representations. Quantum Information and Computing, 7(5):401–430, 2007. ISSN 1533-7146.
  46. [46]Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured decomposability. In 23rd Conference on Artificial Intelligence (AAAI), volume 8, pages 517–522, 2008.
  47. [47]Alex Rogozhnikov. Einops: Clear and reliable tensor manipulations with einstein-like notation. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=oapxkSVM2bcj.
  48. [48]Dmitry V. Savostyanov. Quasioptimality of maximum-volume cross interpolation of tensors. Linear Algebra and its Applications, 458:217–244, October 2014. ISSN 0024-3795. doi: 10.1016/j.laa.2014.06.006. URL http://dx.doi.org/10.1016/j.laa.2014.06.006.
  49. [49]Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz, and Peter Sanders. High-quality hypergraph partitioning, 2021. URL https://arxiv.org/abs/2106.08696.
  50. [50]Ulrich Schollwoeck. The density-matrix renormalization group in the age of matrix product states. Annals of Physics, 326:96–192, 2010.DOI
  51. [51]Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. In Advances in Neural Information Processing Systems 29 (NeurIPS). Curran Associates, Inc., 2016.
  52. [53]Lennert De Smet, Emanuele Sansone, and Pedro Zuidberg Dos Martires. Differentiable sampling of categorical distributions using the catlog-derivative trick. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL https://openreview.net/forum?id=AQyqxXctsnN.
  53. [54]Wolfgang Stammer, Patrick Schramowski, and Kristian Kersting. Right for the Right Concept: Revising Neuro-Symbolic Concepts by Interacting with their Explanations. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3618–3628, June 2021. doi: 10.1109/CVPR46437.2021.00362. URL https://ieeexplore.ieee.org/document/9578154. ISSN: 2575-7075.DOI
  54. [55]Zhonghao Sun, Jizu Huang, Chuanfu Xiao, and Chao Yang. Hatt: Hadamard avoiding tt recompression, 2025. URL https://arxiv.org/abs/2410.04385.
  55. [56]Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410–421, 1979.DOI
  56. [57]Emile van Krieken, Erman Acar, and Frank van Harmelen. Semi-supervised learning using differentiable reasoning. CoRR, abs/1908.04700, 2019. URL http://arxiv.org/abs/1908.04700.
  57. [58]Emile van Krieken, Erman Acar, and Frank van Harmelen. Analyzing differentiable fuzzy logic operators. Artif. Intell., 302:103602, 2022.
  58. [59]Emile van Krieken, Thiviyan Thanapalasingam, Jakub M. Tomczak, F. V. Harmelen, and Annette ten Teije. A-nesi: A scalable approximate method for probabilistic neurosymbolic inference. ArXiv, abs/2212.12393, 2022.arxiv.org/abs/2212.12393
  59. [60]Emile van Krieken, Pasquale Minervini, Edoardo M. Ponti, and Antonio Vergari. On the independence assumption in neurosymbolic learning, 2024. URL https://arxiv.org/abs/2404.08458.
  60. [61]Emile van Krieken, Pasquale Minervini, Edoardo Ponti, and Antonio Vergari. Neurosymbolic reasoning shortcuts under the independence assumption, 2025. URL https://arxiv.org/abs/2507.11357.
  61. [62]Emile van Krieken, Pasquale Minervini, Edoardo Ponti, and Antonio Vergari. Neurosymbolic diffusion models, 2025. URL https://arxiv.org/abs/2505.13138.
  62. [63]Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Representations, algorithms, learning, and applications. Tutorial at the 35th Conference on Uncertainty in Artificial Intelligence (UAI), 2019.
  63. [64]Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 13189–13201. Curran Associates, Inc., 2021.
  64. [65]Victor Verreet, Lennert De Smet, Luc De Raedt, and Emanuele Sansone. Explain, agree, learn: scaling learning for neural probabilistic logic. In ECAI 2024: 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain–Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024), pages 1349–1356. SAGE Publications Pvt. Ltd 1 Oliver’s Yard, 55 City Road, London, EC1Y 1SP, 2024.arxiv.org/abs/2408.08133
  65. [66]Po-Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. CoRR, abs/1905.12149, 2019. URL http://arxiv.org/abs/1905.12149.
  66. [67]Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Broeck. A semantic loss function for deep learning with symbolic knowledge. In 37th International conference on machine learning (ICML), pages 5502–5511. PMLR, 2018.arxiv.org/abs/1711.11157

Paper details

vlnc:W_g9xgr6tt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents