Structural Sharing via Directed Acyclic Graphs

57 concepts43 papers

The Tyranny of Tree Growth

When we model symbolic expressions, logical formulas, or mathematical equations computationally, our default instinct is to use a tree structure. Trees are intuitive: operators sit at the branches, and variables or constants reside at the leaves. However, trees possess a fundamental flaw: they cannot handle reuse. If an intermediate expression or variable appears multiple times across a formula or a system of equations, a tree forces us to duplicate that entire subtree every single time it occurs.

This structural redundancy triggers a catastrophic issue known as exponential size explosion. In automated theorem proving, for instance, a single inference step in the resolution calculus can cause a formula to balloon exponentially if sub-expressions are copied blindly, making even "short" proofs computationally impossible to process (Letz in On the Polynomial Transparency of Resolution). A similar bottleneck arises when an AI agent tracks its beliefs over time in a partially observable environment; updating state descriptions using flat formulas causes the knowledge base to grow exponentially with the sequence of actions (Shahaf et al.).

The core insight of this research direction is that the computational bottleneck in these systems is often not the inherent complexity of the logic itself, but rather the redundancy of the representation.

The Core Mechanism: Folding Trees into DAGs

To bypass exponential growth, we must transition from tree structures to Directed Acyclic Graphs (DAGs). By allowing a single node to have multiple parents, we can replace literal duplication with reference pointers. This technique is known as structural sharing or sub-expression deduplication.

    Tree Representation (Redundant)          DAG Representation (Shared)
             [ AND ]                                  [ AND ]
            /       \                                /       \
     [ OR ]           [ OR ]                        /         \
    /      \         /      \                      v           v
[ A ]    [ B ]   [ A ]    [ B ]                  [ OR ]     [ NOT ]
                                                /      \       |
                                            [ A ]    [ B ] <---+

The foundational intuition dates back to early work in automated theorem proving. Aubin demonstrated that pointer-based representations allow identical subterms to be shared across a proof tree, ensuring that simplifying one instance of a term automatically updates all identical instances (Strategies for Mechanizing Structural Induction).

Instead of performing expensive string or tree copying during logical unification, systems can simply update pointers within a graph structure to reflect variable assignments (Agron et al.). Similarly, introducing "extension variables" can act as pointers or abbreviations for existing sub-formulas, effectively folding tree-structured proofs into compact DAGs and significantly increasing their expressive power (Knop et al.).

Why It Works: Taming Updates and Proof Derivations

Representing formulas as DAGs fundamentally alters the computational complexity of manipulating logic.

When an agent updates its knowledge base over a long sequence of actions, a DAG representation keeps the size of the formula polynomial relative to the environment features rather than exponential (Shahaf et al.). Instead of rewriting the entire history at each step, the update algorithm merely constructs a small number of new gates or nodes that point back to the existing graph structure (Shahaf et al.).

This linear relationship between derivation size and representation size is also crucial in Quantified Boolean Formulas (QBF). By using DAGs to represent logical strategies, Blinkhorn et al. prevent the exponential size blow-ups typical of tree-based proof systems, maintaining a strict linear bound relative to the proof itself. Monitoring dynamic systems via temporal progression benefits from the same mechanism: DAGs mitigate state explosion by sharing common sub-structures as new data arrives over time (Eiter et al.).

Structural Caching and Early Pruning

Beyond saving memory, structural sharing unlocks a powerful computational superpower: structural caching.

If a representation is designed to be canonical, logically equivalent formulas are guaranteed to share the exact same memory address. As shown by the authors of On the Role of Canonicity in Knowledge Compilation, this uniqueness enables perfect caching, allowing compilers to completely bypass redundant calculations and achieve massive practical speedups.

In modal logic solvers, structural caching ensures that equivalent sub-formulas are translated only once, preventing exponential growth in the output Conjunctive Normal Form (CNF) (Caridroit et al.). For Stochastic Local Search (SLS) in SMT solvers, representing bit-vectors as DAGs allows for rapid score updates and early pruning of redundant calculations, drastically lowering the cost of evaluating variable changes across massive formulas (Fröhlich et al.).

Generalizing Beyond Logic: Queries, Math, and Planning

The intuition of DAG-based structural sharing extends far beyond pure logic into any domain governed by rigid structural rules:

  • Database Queries: Naive query expansion or higher-order functional evaluation can lead to unmanageable SQL or non-elementary complexity. By applying graph reduction techniques to represent shared sub-expressions within a DAG, Vu avoids redundant logic duplication (HOMES: A Higher-Order Mapping Evaluation System; Higher­Order Functions and Structured Datatypes). Similarly, tracking query history as an arithmetic circuit DAG prevents exponential growth in data provenance tracking (Ramusat et al.).
  • Mathematical Reasoning: Traditional tree structures struggle with multi-variable algebraic systems because variables and intermediate calculations are frequently reused. Representing equations as DAGs explicitly encodes operator hierarchy and allows deep sub-expression reuse (Cao et al.; Feng et al.). In symbolic regression, searching over a space of DAGs rather than trees allows algorithms to cover a much broader variety of functional forms within strict complexity constraints (the authors of Scaling Up Unbiased Search-based Symbolic Regression). This structural clarity also helps Graph Neural Networks learn more robust embeddings for higher-order logic (Paliwal et al.).
  • Probabilistic Inference and Planning: Storing logical proofs in prefix trees or tries exploits structural redundancies to minimize memory footprints during exact probability calculations (Kersting et al.; Kimmig et al.). In large-scale planning problems, representing value functions or policies as decision diagrams (which are specialized DAGs) compresses millions of states by merging identical sub-structures that lead to the same outcome (Hoey et al.; Wang et al.; Nielsen et al.).

Key Foundational Work

A Unification Algorithm for Infinite Trees (1983) — contributed 2 concept elements to this direction.
Theorem Proving with Structure Sharing and Efficient Unification (1977) — contributed 1 concept elements to this direction.
Theorem Proving with Structure Sharing and Efficient Unification (1977) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_dag_based_formula_representation_b9b41b23,
  title = {DAG-based formula representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dag-based-formula-representation/rdr_b9b41b23c9ab42b4836f7c9a1c3dc369},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_dag_based_formula_representation_b9b41b23_v1,
  title = {DAG-based formula representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dag-based-formula-representation/rdr_b9b41b23c9ab42b4836f7c9a1c3dc369/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake