Pith. sign in

REVIEW 2 major objections 5 minor 32 references

Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Tensor trains are claimed to be strictly more succinct than ordered binary decision diagrams while supporting exactly the same set of polynomial-time queries and transformations.

desk verdict Useful bridge between tensor trains and the KC map, but the HWB witness in Proposition 1 fails for n=2 as typeset, so the main separation is not yet proven. read the letter →

arxiv 2502.03702 v1 pith:FAHDTUU3 submitted 2025-02-06 cs.DS

Ryoma Onaka , Kengo Nakamura , Masaaki Nishino , Norihito Yasuda This is my paper · ORCID
classification cs.DS
keywords tensortrainsorderedbinarydecisiondiagramsknowledgecompilationmapBooleanfunctionrepresentationhiddenweightedbitsuccinctnesstractablequeriesandtransformationsmodelcounting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper seeks to establish that tensor trains, a linear-algebraic format for compressing high-dimensional arrays, can be read as Boolean function representations and that, under a fixed variable order, they are strictly more succinct than ordered binary decision diagrams (OBDDs) while supporting the same polynomial-time queries and transformations. The argument has two directions: a polynomial-size translation from any OBDD into a tensor train, and a family of functions, the hidden-weighted-bit functions, that have polynomial-size tensor trains but exponential-size OBDDs. If the results stand, tensor trains form a knowledge-compilation language outside the negation-normal-form family, combining OBDD-level tractability with better worst-case space.

What carries the argument

The central object is the tensor train representation of a Boolean function: a $2\times m$ binary tensor decomposed as $A_1\cdots A_m$, where each $A_i$ is a ternary three-dimensional tensor, paired with a mapping $\pi$ that assigns the tensor modes to input variables in the chosen order. The succinctness proof runs through two constructions: first, an OBDD is converted into a level-wise smooth OBDD (LSBDD), where each tensor $A_i$ encodes the edges between nodes labeled by consecutive variables, giving a polynomial blow-up; second, the hidden-weighted-bit function is built as a rank-$2n$ tensor train whose state vector maintains a one-hot encoding of the number of ones seen so far together with a shifted copy of the input bits. The tractability results reduce each query or transformation to the sum, Hadamard product, and inner product of tensor trains, with a mode-alignment lemma that lets two tensor trains share one mapping without changing their ranks.

What would settle it

Run the paper's HWB construction for $n=4$ and $n=5$, evaluate the resulting tensor train on all assignments, and compare with the truth table of $HWB_n$; a single mismatch falsifies Proposition 1 and with it the exponential separation. One could also count the nodes produced by Lemma 2's OBDD-to-LSBDD procedure to check the claimed $|B|(|V(B)|-1)$ bound.

Watch

Extended reading notes

Core claim

The central claim is that the class $\mathrm{TT}_<$ is more succinct than $\mathrm{OBDD}_<$: for a fixed variable order, every OBDD of size $s$ has an equivalent tensor train of size polynomial in $s$, while the hidden-weighted-bit functions $HWB_n$ have tensor-train size $O(n^2)$ but OBDD size $\Omega(2^{0.2n})$. The paper further proves that $\mathrm{TT}_<$ supports exactly the queries and transformations that $\mathrm{OBDD}_<$ supports in polynomial time — consistency, validity, clause entailment, equivalence, implication, model counting, model enumeration, conditioning, binary conjunction, binary disjunction, negation, and singleton forgetting — and, like $\mathrm{OBDD}_<$, cannot support arbitrary conjunction or disjunction of many functions or forgetting of a variable set in polynomial time. From this the paper concludes that tensor trains are a distinct knowledge-compilation class outside NNF, achieving a trade-off that among NNF subsets was previously associated with SDD.

Load-bearing premise

The strict-succinctness claim rests on the construction showing that $HWB_n$ has a rank-$2n$ tensor train; if the inductive invariant that the state vector stores a one-hot count plus a shifted copy of the input bits fails at any step, only the OBDD-to-tensor-train direction survives.

Editorial extensions

If this is right

  • Every function with a size-$s$ $\mathrm{OBDD}_<$ has a $\mathrm{TT}_<$ representation of size polynomial in $s$, so existing OBDD compilation methods can be reused to produce tensor-train representations.
  • The hidden-weighted-bit functions separate the classes exponentially: $\mathrm{OBDD}_<$ needs $\Omega(2^{0.2n})$ nodes while $\mathrm{TT}_<$ uses $O(n^2)$ elements.
  • $\mathrm{TT}_<$ and $\mathrm{OBDD}_<$ have the same polytime query and transformation sets, including model counting and model enumeration, while both exclude polytime arbitrary conjunction, arbitrary disjunction, and variable-set forgetting.
  • $\mathrm{TT}_<$ is a class outside the NNF family, so the knowledge compilation map gains a representation that differs from all NNF subsets rather than being another special case of NNF.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the HWB construction is correct, tensor trains should also be small for other functions built from counts and selected bits, such as threshold and majority functions, where OBDDs are known to blow up.
  • The mode-alignment lemma suggests a practical recipe: compile OBDDs once, translate to tensor trains, and then use tensor algebra for the query workload, potentially on parallel hardware built for tensor networks.
  • A direct succinctness comparison between $\mathrm{TT}_<$ and SDD is the natural next step; the paper conjectures that TT is not more succinct than SDD and that NNF subsets are not more succinct than TT, but it does not prove either.
  • The unfolding-matrix rank lower bound used to prove Theorem 3 could become a general tool for finding new succinctness separations by identifying Boolean functions with high matrix rank but low tensor-train rank.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper introduces tensor trains (TT) as Boolean function representations and compares them with ordered binary decision diagrams (OBDDs) under the knowledge compilation map. It claims that TT< is strictly more succinct than OBDD<, via an OBDD-to-LSBDD-to-TT translation for the upper bound and a rank-2n tensor train construction for the HWB function for the lower bound. It further claims that TT< supports exactly the same set of polynomial-time queries and transformations as OBDD<, with lower-bound arguments for the unsupported operations ∧C, ∨C, and FO. Full proofs are provided in the appendix.

Significance. If the main theorems are correct, this is a valuable contribution: it would place a non-NNF representation into the knowledge compilation map, showing that a tensor decomposition method can be strictly more succinct than OBDDs while matching their tractable operations. The paper's framing is original, and the broad proof strategy (LSBDD encoding, HWB separation, reduction of operations to tensor algebra) is natural. The operation-tractability results are supported by standard tensor-train algebra and are largely convincing. However, the central separation result currently rests on a HWB construction whose proof does not verify the claimed function, and the OBDD-to-LSBDD smoothing step has a gap; these need repair before the main claims are established.

major comments (2)
  1. [Proof that OBDD< is not as succinct as TT< (Proposition 1, Lemma 5)] The tensor-train construction for HWB_n does not compute HWB_n as written. With the standard reading of I_k as the n×n cyclic right-shift matrix and I'_k as its left-right inversion, take n=3 and assignment (1,0,0). Then A0^T = (1,0,0,0,0,0), and V1 = A0^T A1(·,1,·) = (0,1,0,0,1,0). Since a2=a3=0, V3=V1, and selecting the (n+1)=4th component gives 0, whereas HWB_3(1,0,0)=x1=1. The same failure occurs for (0,0,1). Thus the invariant claimed in Lemma 5(ii), that the (n+1)-th element of Vk equals a_{Σ ai}, is false for the stated matrices. The phrase 'cyclically left-shifting ... by j' in Lemma 5(ii) never defines j, and the invariant does not hold for the constructed cores. This gap is load-bearing for the lower-bound direction of Theorem 1. The construction may be repairable, but as submitted the proof does not verify the separation.
  2. [Lemma 2 (OBDD-to-LSBDD transformation)] The smoothing procedure and its size bound need correction. The procedure inserts a node for an affected edge, and each non-terminal node has two outgoing edges, so the bound 'at most |V(B)|−1 nodes for every non-terminal node in B' undercounts by at least a factor of two. More seriously, when an edge points to a terminal, the procedure inserts a single node u with var(u)=max V(B); if var(v) is not the largest variable, the new edge v→u still skips the intermediate variables in V(B), so the resulting graph need not satisfy condition (ii) of Definition 8. The smoothing step therefore needs a more careful construction (e.g., a chain of inserted nodes) or a clarified definition that terminal edges are exempt. The intended polynomial bound may still be achievable, but the proof as written does not establish it.
minor comments (5)
  1. [Proposition 1] The proposition states that HWB_n can be represented by a tensor train of size O(n^2), but the displayed construction uses n cores of size (2n)×2×(2n), giving Θ(n^3) elements. This does not affect the polynomiality needed for Theorem 1, but the stated bound should be corrected to O(n^3) or the construction should be changed.
  2. [Lemma 5] The phrase 'cyclically left-shifting (a1,…,ak,0,…,0) by j' is undefined because j is not introduced. The shift amount should be stated explicitly, and the invariant should be verified against the actual matrices.
  3. [Proof of Theorem 2 (ME)] The model-enumeration proof says that f∧xπ(1) and f∧¬xπ(1) 'can be obtained by CD'. Conditioning on a literal yields the residual function f|x or f|¬x, not the conjunction with that literal. The enumeration can be repaired by using ∧BC for the conjunctions, or by recursing on the conditioned functions directly; as written the justification is incorrect.
  4. [Definition 4] The description of which assignments are constrained by the mapping π is confusing: 'satisfying xj = a_{π^{-1}(j)} if j ∈ Q' mixes indices j and π(j). Clarifying that x_{π(i)}=a_i for i∈[m] would improve readability.
  5. [Throughout] There are several LaTeX/formatting artifacts (e.g., the garbled 'mz}|{2 × · · · ×2 tensors' near the tensor-train definition) and notational overloads (ℓ is used both for the number of modes of g and for the number of literals in a term or clause). These should be cleaned up.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims are derived from external benchmarks and self-contained constructions.

full rationale

The paper's central assertions are not assumed in their inputs. Theorem 1 has two directions. The OBDD< to TT< direction is proved by an explicit translation through LSBDDs (Lemma 2, Lemma 3), with node-level induction establishing correctness; it does not presuppose the theorem. The separation direction relies on the HWB function: the exponential OBDD lower bound is quoted from Bollig et al. 1999 (an external result), and the polynomial-size tensor train upper bound is an explicit rank-2n construction (Proposition 1) whose correctness is argued by the inductive invariant in Lemma 5. Whether that construction is correctly typeset is a soundness concern, not a circularity concern: the proof does not define HWB in terms of tensor trains, nor fit the tensor train to the OBDD lower bound. Theorem 2 reduces queries and transformations to sum, Hadamard product, and inner product, citing Oseledets 2011 for the tractability of these tensor train operations; the reduction is shown by explicit tensor algebra in Lemma 8 and the appendix. Theorem 3 uses external rank lower bounds (Oseledets 2011) and derives contradictions rather than assuming the conclusion. The FO impossibility proof uses the already-proved Theorem 1, which is legitimate internal reuse, not circularity, because Theorem 1 was established independently. There are no load-bearing self-citations: all cited results are by other authors and are external to the present paper's fitted values or constructions. The knowledge compilation map framework is also imported from Darwiche and Marquis 2002 as a standard external benchmark, not as a tool that forces the paper's conclusions. The fragile point identified by a skeptical reader is the HWB tensor train witness; if the matrices in Proposition 1 do not compute HWB as typeset, the hard direction of Theorem 1 is unproven, but that is a correctness risk, not a case of the paper deriving its conclusion from itself. Overall, no step in the derivation chain reduces by construction to its inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters and no invented entities. The central claims rest on standard external theorems (HWB lower bound, tensor train algebra) and the KC map framework; these are prior results, not the target of the paper.

assumptions (4)
  • standard math HWB_n has OBDD size Omega(2^{0.2n}) for every variable order (Bollig et al. 1999).
    Lemma 4, used in Theorem 1 to show OBDD< is not as succinct as TT<.
  • standard math The rank of the unfolding matrix of a tensor is a lower bound on tensor train ranks (Oseledets 2011).
    Used in Theorem 3 to prove polytime lower bounds for ∧C, ∨C, and FO.
  • standard math Sum, Hadamard product, and inner product of tensor trains are computable in the stated polynomial times (Oseledets 2011).
    Basis for Theorem 2's upper bounds.
  • domain assumption The knowledge compilation map definitions of succinctness and polytime operations, and the set of operations that OBDDs support in polytime (Darwiche and Marquis 2002).
    Frames the comparison; the paper assumes these are the right criteria.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs." pith.science (2026). https://pith.science/paper/FAHDTUU3

@misc{pith2026250203702,
  author       = {Pith},
  title        = {Pith review of: Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FAHDTUU3}},
  note         = {Machine review of arXiv:2502.03702}
}
read the original abstract

A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets.

Figures

Figures reproduced from arXiv: 2502.03702 by the authors.

Figure 1
Figure 1. Example of transforming an OBDD into an equivalent tensor train. We first transform an OBDD into an equivalent [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 28 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Bollig, B.; L \"o bbing, M.; Sauerhoff, M.; and Wegener, I. 1999. On the complexity of the hidden weighted bit function for various BDD models. RAIRO - Theoretical Informatics and Applications - Informatique Th \'e orique et Applications , 33(2): 103--115

    work page 1999

  4. [4]

    Bollig, B.; and Pr \"o ger, T. 2012. An efficient implicit OBDD-based algorithm for maximal matchings. In Proceedings of the 6th International Conference on Language and Automata Theory and Applications, 143--154. Springer

    work page 2012

  5. [5]

    Bova, S. 2016. SDD s are exponentially more succinct than OBDD s. In Proceedings of the 30th AAAI Conference on Artificial Intelligence, 929--935

    work page 2016

  6. [6]

    Bryant, R. E. 1986. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, C-35(8): 677--691

    work page 1986

  7. [7]

    Bryant, R. E. 1991. On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Transactions on Computers, 40(2): 205--213

    work page 1991

  8. [8]

    D.; and Chang, J.-J

    Carroll, J. D.; and Chang, J.-J. 1970. Analysis of individual differences in multidimensional scaling via an n-way generalization of `` Eckart - Young '' decomposition. Psychometrika, 35: 283--319

    work page 1970

Show all 32 references
  1. [9]

    Chavira, M.; and Darwiche, A. 2008. On probabilistic inference by weighted model counting. Artificial Intelligence, 172(6-7): 772--799

    2008

  2. [10]

    Choi, Y.; Vergari, A.; and Van den Broeck, G. 2020. Probabilistic circuits: a unifying framework for tractable probabilistic models. Available at: http://starai.cs.ucla.edu/papers/ProbCirc20.pdf

    2020

  3. [11]

    Darwiche, A. 1999. Compiling knowledge into decomposable negation normal form. In Proceedings of the 16th International Joint Conference on Artifical Intelligence, 284--289

    1999

  4. [12]

    Darwiche, A. 2001 a . Decomposable negation normal form. Journal of The ACM, 48(4): 608–647

    2001

  5. [13]

    Darwiche, A. 2001 b . On the tractable counting of theory models and its application to truth maintenance and belief revision. Journal of Applied Non-Classical Logics, 11(1-2): 11--34

    2001

  6. [14]

    Darwiche, A. 2011. SDD : A new canonical representation of propositional knowledge bases. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 819--826

    2011

  7. [15]

    Darwiche, A. 2014. Tractable Knowledge Representation Formalisms, 141–172. Cambridge University Press

    2014

  8. [16]

    Darwiche, A.; and Marquis, P. 2002. A knowledge compilation map. Journal of Artificial Intelligence Research, 17(1): 229--264

    2002

  9. [17]

    M.; and Vardi, M

    Dudek, J. M.; and Vardi, M. Y. 2020. Parallel weighted model counting with tensor networks. arXiv:2006.15512

    2020 arXiv

  10. [18]

    Fannes, M.; Nachtergaele, B.; and Werner, R. F. 1992. Finitely correlated states on quantum spin chains. Communications in Mathematical Physics, 144: 443--490

    1992

  11. [19]

    Fargier, H.; and Marquis, P. 2008. Extending the knowledge compilation map: Krom, Horn, affine and beyond. In Proceedings of the 23rd National Conference on Artificial Intelligence, volume 1, 442--447

    2008

  12. [20]

    Fargier, H.; Marquis, P.; and Niveau, A. 2013. Towards a knowledge compilation map for heterogeneous representation languages. In In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 877--883

    2013

  13. [21]

    Hackbusch, W.; and K\" u hn, S. 2009. A new scheme for the tensor representation. Journal of Fourier Analysis and Applications, 15: 706--722

    2009

  14. [22]

    Hong, X.; Zhou, X.; Li, S.; Feng, Y.; and Ying, M. 2022. A tensor network based decision diagram for representation of quantum circuits. ACM Transactions on Design Automation of Electronic Systems (TODAES), 27(6): 1--30

    2022

  15. [23]

    Huang, J.; and Darwiche, A. 2004. Using DPLL for efficient OBDD construction. In Proceedings of the 7th International Conference on Theory and Applications of Satisfiability Testing, 157--172

    2004

  16. [24]

    Khrulkov, V.; Novikov, A.; and Oseledets, I. 2018. Expressive power of recurrent neural networks. In In Proceedings of the 6th International Conference on Learning Representations

    2018

  17. [25]

    Knuth, D. E. 2011. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional

    2011

  18. [26]

    G.; and Bader, B

    Kolda, T. G.; and Bader, B. W. 2009. Tensor decompositions and applications. SIAM Review, 51(3): 455--500

    2009

  19. [27]

    Manhaeve, R.; Dumancic, S.; Kimmig, A.; Demeester, T.; and De Raedt, L. 2018. DeepProbLog : neural probabilistic logic programming. In Proceedings of Advances in Neural Information Processing Systems 31 (NeurIPS 2018)

    2018

  20. [28]

    M.; Thornton, M

    Niemann, P.; Wille, R.; Miller, D. M.; Thornton, M. A.; and Drechsler, R. 2016. QMDD s: efficient quantum function representation and manipulation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35(1): 86--99

    2016

  21. [29]

    Oseledets, I. V. 2011. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5): 2295--2317

    2011

  22. [30]

    Tucker, L. R. 1966. Some mathematical notes on three-mode factor analysis. Psychometrika, 31: 279--311

    1966

  23. [31]

    Xu, J.; Zhang, Z.; Friedman, T.; Liang, Y.; and Van den Broeck, G. 2018. A semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of PMLR, 5502--5511

    2018

  24. [32]

    Yang, Y.; Krompass, D.; and Tresp, V. 2017. Tensor-train recurrent neural networks for video classification. In Proceedings of the 34th International Conference on Machine Learning, 3891--3900

    2017

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.