From Tensor Networks to Tractable Circuits, and back

• URL: http://arxiv.org/abs/2605.00106v1
• Date: Thu, 30 Apr 2026 18:01:40 GMT
• Title: From Tensor Networks to Tractable Circuits, and back
• Abstract summary: We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties.<n>In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams.
• Score: 4.942278642834429
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Tensor networks and circuits are widely used data structures to represent pseudo-Boolean functions. These two formalisms have been studied primarily in separate communities, and this paper aims to establish equivalences between them. We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties that have been studied in knowledge compilation as \emph{tractable circuits}. In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams and that tree tensor networks exactly correspond to structured-decomposable circuits. These correspondences enable direct transfer of structural and algorithmic results; for example, canonicity and tractability guarantees known for circuits yield analogous guarantees for the associated tensor networks, and vice versa.

Related papers

• Many Circuits, One Mechanism: Input Variation and Evaluation Granularity in Circuit Discovery [49.50794188352666]
  We show that structural differences between circuits are not sufficient evidence for distinct mechanisms.<n>Standard evaluation practice obscures this pattern, while edge-level evaluation reveals the many-to-one mapping from structure to function.
  arXiv  Detail & Related papers  (2026-06-04T15:10:14Z)
• From Circuit Evidence to Mechanistic Theory: An Inductive Logic Approach [4.3997570047987775]
  This work provides a formal infrastructure for cumulative mechanistic science by treating circuit interpretation as inductive theory construction.<n>Each circuit is characterised at two levels: a Causal Functional Signature (CFS), which grounds component behaviour in causal attribution evidence, and an architectural signature $_mathrmarch$, learned by inductive logic programming (ILP) from scale-invariant structural predicates.
  arXiv  Detail & Related papers  (2026-05-20T15:33:14Z)
• Seeing Through Circuits: Faithful Mechanistic Interpretability for Vision Transformers [54.2202951543048]
  We investigate whether useful mechanistic circuits can be identified through computational graphs in vision transformers.<n>We propose an effective method for Automatic Visual Circuit Discovery (Vi-CD) that recovers class-specific circuits for classification.<n>We find that insightful and actionable edge-based circuits can be recovered from vision transformers, adding transparency to the internal computations of these models.
  arXiv  Detail & Related papers  (2026-04-15T23:25:46Z)
• An order-theoretic circuit syntax and characterisation of the concept lattice [0.0]
  We take an order-theoretic approach to circuit (string diagram) syntax, treating a circuit as a partial order with additional input-output structure.<n>We define morphisms between circuits and prove a factorisation theorem showing that these can, in the finite case, be regarded as formalising a notion of syntactical circuit rewrites.
  arXiv  Detail & Related papers  (2025-07-07T19:18:37Z)
• Semantic Loss Functions for Neuro-Symbolic Structured Prediction [74.18322585177832]
  We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training. It is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby. It can be combined with both discriminative and generative neural models.
  arXiv  Detail & Related papers  (2024-05-12T22:18:25Z)
• Towards Rigorous Understanding of Neural Networks via Semantics-preserving Transformations [0.0]
  We present an approach to the precise and global verification and explanation of Rectifier Neural Networks. Key to our approach is the symbolic execution of these networks that allows the construction of semantically equivalent Typed Affine Decision Structures.
  arXiv  Detail & Related papers  (2023-01-19T11:35:07Z)
• Entangled Residual Mappings [59.02488598557491]
  We introduce entangled residual mappings to generalize the structure of the residual connections. An entangled residual mapping replaces the identity skip connections with specialized entangled mappings. We show that while entangled mappings can preserve the iterative refinement of features across various deep models, they influence the representation learning process in convolutional networks.
  arXiv  Detail & Related papers  (2022-06-02T19:36:03Z)
• Neural networks adapting to datasets: learning network size and topology [77.34726150561087]
  We introduce a flexible setup allowing for a neural network to learn both its size and topology during the course of a gradient-based training. The resulting network has the structure of a graph tailored to the particular learning task and dataset.
  arXiv  Detail & Related papers  (2020-06-22T12:46:44Z)
• Neural Anisotropy Directions [63.627760598441796]
  We define neural anisotropy directions (NADs) the vectors that encapsulate the directional inductive bias of an architecture. We show that for the CIFAR-10 dataset, NADs characterize the features used by CNNs to discriminate between different classes.
  arXiv  Detail & Related papers  (2020-06-17T08:36:28Z)
• Training End-to-End Analog Neural Networks with Equilibrium Propagation [64.0476282000118]
  We introduce a principled method to train end-to-end analog neural networks by gradient descent. We show mathematically that a class of analog neural networks (called nonlinear resistive networks) are energy-based models. Our work can guide the development of a new generation of ultra-fast, compact and low-power neural networks supporting on-chip learning.
  arXiv  Detail & Related papers  (2020-06-02T23:38:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.