{"id":"831be7ef-41c0-4234-b2ad-de51ed0edd44","arxiv_id":"2502.03702","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Tensor trains are provably more succinct than OBDDs as Boolean function representations and support the same polynomial-time queries and transformations.","lead":"This paper treats tensor trains as Boolean function representations and compares them with ordered binary decision diagrams (OBDDs). It claims tensor trains are at least as succinct as OBDDs, sometimes exponentially more succinct, while supporting the same polynomial-time operations.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The HWB tensor-train witness in Proposition 1 appears to compute the wrong function as typeset; the hard direction of Theorem 1 is unverified until the core matrices are corrected.","rationale":"The reader's weakest_assumption correctly identified the HWB construction and Lemma 5's undefined shift 'by j' as the fragile point. My stress test goes further: the ambiguity is not merely typesetting. For n=2, the published matrix block gives a concrete counterexample to the claimed invariant and to HWB_2, so Proposition 1 is not verified as written. This is load-bearing because without the HWB witness the paper only has the easy OBDD-to-TT translation direction; the exponential succinctness gap and hence the 'more succinct than' claim collapse until a correct construction is supplied. The issue is repairable in principle, and the rest of the paper — the translation upper bound and the polytime operations — does not depend on this particular construction, so I do not recommend rejection. The reader's CONDITIONAL verdict is appropriate: the paper should not be accepted until Proposition 1 is restated with a well-defined and correct core family. The secondary size mismatch (O(n^2) vs O(n^3)) is presentation-level and does not affect the polynomial-vs-exponential separation.","tokens_in":19187,"tokens_out":38650,"duration_ms":361855,"concrete_test":"Run a short script that instantiates the Proposition 1 cores for n=2 exactly as published: I1=[[0,1],[1,0]], I2=I, I'_1=[[0,1],[1,0]], I'_2=I, A0=(1,0,0,0), A3 selecting the third coordinate, and contract A0^T A1(·,a1,·) A2(·,a2,·) A3 for all four assignments. Compare the truth table with HWB_2 = [0,1,0,1] for inputs (00,10,01,11). If it prints [0,1,1,0], the construction as written is incorrect. Then test a corrected indexing, e.g. replacing I'_i with I'_{n-i+1} or an equivalent corrected Lemma 5 shift, and exhaustively verify n=3 before restoring the Theorem 1 separation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The separation OBDD< ≤ TT< in Theorem 1 rests on Proposition 1's claim that HWB_n has a rank-2n tensor train. Taken literally, the construction in the proof of Proposition 1 fails for n=2. With Ai(·,1,·) = [[I1, I'_i],[O, I_{n-1}]] and the standard reading of Ik as a cyclic shift, the cores are 4×2×4 tensors with I'_1 = swap and I'_2 = identity. Starting from A0 = (1,0,0,0) and selecting the (n+1)-st = third coordinate, the assignment (0,1) gives V2 = (0,1,1,0), so f(0,1)=1. But HWB_2(0,1)=x1=0. The assignment (1,1) even produces an intermediate entry 2. Thus Lemma 5's invariant that the (n+1)-th element of Vk equals a_{Σ ai} is false for the stated matrices; the undefined shift 'by j' in Lemma 5(ii) conceals this indexing error. The lower-bound direction of Theorem 1 can likely be repaired, since a rank-2n MPS for HWB is plausible, but as submitted the proof does not verify it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19423,"tokens_out":23441,"duration_ms":203184,"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":[{"comment":"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.","section":"Proof that OBDD< is not as succinct as TT< (Proposition 1, Lemma 5)"},{"comment":"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.","section":"Lemma 2 (OBDD-to-LSBDD transformation)"}],"minor_comments":[{"comment":"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.","section":"Proposition 1"},{"comment":"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.","section":"Lemma 5"},{"comment":"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.","section":"Proof of Theorem 2 (ME)"},{"comment":"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.","section":"Definition 4"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The HWB counterexample in the stress-test note appears to misindex I'_1 and I'_2 for n=2, but the construction nonetheless fails for n=3 as detailed in my major comment. The lower-bound direction of Theorem 1 may be repairable with a correct rank-O(n) tensor train for HWB, but it is not verified in the manuscript. The paper's scope and contribution are appropriate for a revision if the proof is corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is the first paper I've seen that treats tensor trains as a knowledge compilation language with the full Darwiche–Marquis toolkit. The OBDD-to-TT translation via LSBDDs is clean, and the observation that standard tensor algebra operations (Hadamard, inner product, sum) cover the same polytime query/transformation set as OBDD< is a real and useful contribution. The intractability arguments for ∧C, ∨C, and FO via rank lower bounds are also plausible. If the succinctness separation holds, this genuinely extends the KC map outside NNF, which is conceptually interesting.\n\nThe soft spot is the HWB construction that carries the hard direction of Theorem 1. As typeset, it does not compute HWB even for n=2: with the stated cores, the assignment (0,1) yields a 1 in the (n+1)-th position of V2, while HWB_2(0,1)=0, and (1,1) produces an intermediate entry 2. Lemma 5(ii) refers to a shift 'by j' that is never defined, which is where the indexing goes wrong. On top of that, the paper claims O(n^2) size for the HWB tensor train, but the construction has n cores each 2n×2×2n, so Theta(n^3) elements. The size overclaim is more than a constant factor.\n\nNone of this invalidates the OBDD-to-TT direction or the tractability results; those look solid. But the 'more succinct' direction of Theorem 1 currently rests on an unverified witness, and the proof as submitted does not establish it. I suspect the intended construction can be repaired—a rank-O(n) HWB tensor train is plausible, and the overall approach is sound enough that the claim is probably true. It needs a corrected Proposition 1 and a clean statement of Lemma 5 before the separation is credible.\n\nIf I were the editor, I would send this to review with a request for major revision, specifically asking for a fixed HWB construction and a reconciled size bound. The paper deserves refereeing because the conceptual bridge is valuable and the tractability half is strong. I would not cite the separation result in its current form.","headline":"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.","tokens_in":19996,"tokens_out":5103,"would_cite":false,"duration_ms":43886,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["tensor trains","ordered binary decision diagrams","knowledge compilation map","Boolean function representation","hidden weighted bit function","succinctness","tractable queries and transformations","model counting"],"falsifier":"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.","tokens_in":18963,"feed_emoji":"🧮","tokens_out":11170,"duration_ms":89365,"temperature":0.7,"pith_summary":"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.","feed_headline":"Tensor trains beat OBDDs on size without losing polytime queries","feed_subtitle":"Tensor trains support the same polynomial-time operations as ordered BDDs while compressing some functions exponentially.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the tensor-train decomposition and the polytime algorithms for sum, Hadamard product, and inner product that the tractability results rely on.","marker":"Oseledets 2011"},{"why":"Introduces OBDDs, the representation class that tensor trains are compared against.","marker":"Bryant 1986"},{"why":"Defines the knowledge compilation map, the succinctness notion, and the query and transformation framework used throughout the paper.","marker":"Darwiche and Marquis 2002"},{"why":"Proves the exponential OBDD lower bound for the hidden-weighted-bit function that the separation half of Theorem 1 depends on.","marker":"Bollig et al. 1999"},{"why":"Defines SDD and the conditioning conventions used for the CD operation, and serves as the comparison class in the discussion of where TT sits relative to NNF languages.","marker":"Darwiche 2011"}],"fun_headline_variants":["Tensor trains: exponential compression with OBDD-level queries","More succinct than OBDDs, same polytime power: tensor trains","Tensor trains shrink OBDDs exponentially, keep all polytime ops","A new knowledge compilation class: tensor trains top OBDDs","Tensor trains: OBDD queries, smaller size, outside NNF"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tensor trains: exponential compression with OBDD-level queries","More succinct than OBDDs, same polytime power: tensor trains","Tensor trains shrink OBDDs exponentially, keep all polytime ops","A new knowledge compilation class: tensor trains top OBDDs","Tensor trains: OBDD queries, smaller size, outside NNF"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000184,"raw_usage":{"total_tokens":1296,"prompt_tokens":903,"completion_tokens":393,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":519,"completion_tokens_details":{"reasoning_tokens":301}},"tokens_in":519,"tokens_out":393,"duration_ms":3733,"temperature":1.0,"reasoning_tokens":301,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:06:59.850643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces OBDDs, the representation class that tensor trains are compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the knowledge compilation map, the succinctness notion, and the query and transformation framework used throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves the exponential OBDD lower bound for the hidden-weighted-bit function that the separation half of Theorem 1 depends on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines SDD and the conditioning conventions used for the CD operation, and serves as the comparison class in the discussion of where TT sits relative to NNF languages."}],"review_version":1}