Compressing State Spaces with Binary Decision Diagrams

294 concepts210 papers1 proposal

When modeling complex systems—whether they are autonomous spacecraft, distributed cryptographic protocols, or biological signaling networks—we invariably run into the state-space explosion problem. As you add more variables to a system, the number of possible configurations grows exponentially. A system with a mere 100 boolean variables has $2^{100}$ possible states, a number that dwarfs the number of atoms in the observable universe.

Traditional "explicit" algorithms attempt to navigate this space by visiting states one by one, tracking them in massive tables or graphs. This approach quickly hits a computational wall. To bypass this bottleneck, a powerful paradigm emerged: symbolic state space representation. Instead of enumerating individual states, symbolic methods compress massive sets of states into unified logical formulas and manipulate them simultaneously using specialized data structures called Decision Diagrams.

The Core Intuition: Sets as Functions

To understand why symbolic representation works, we must shift our perspective from listing items to defining them.

Imagine you want to keep track of a specific collection of states in a system. Instead of storing an explicit list of every state vector, you can write a boolean function that returns True if a state belongs to the collection and False otherwise. For example, if a system is safe only when a valve is closed ($v=0$) or a backup pump is active ($p=1$), the set of safe states can be completely defined by the boolean formula $\neg v \lor p$.

By treating sets of states as boolean functions, the problem of exploring a state space transforms into the problem of representing and evaluating logic. This is where Binary Decision Diagrams (BDDs) come in.

A BDD is a directed acyclic graph (DAG) that represents a boolean function. It achieves compression by enforcing two strict rules:

  1. Merging Redundant Nodes: If two different paths in the diagram lead to sub-graphs that behave identically, those sub-graphs are merged.
  2. Eliminating Unnecessary Tests: If both the True and False branches of a variable lead to the exact same next node, the variable is irrelevant in that context and the node is removed.
       [ Variable X ]
        /          \
    if False      if True
      /              \
 [ Node A ]       [ Node A ]  <-- Redundant! Merge them.

By exploiting structural regularities and symmetries within the system domain, BDDs can compress an exponentially large set of states into a remarkably small graph. As Alessandro Cimatti demonstrated in early foundational work on universal planning, these symbolic representations allow algorithms to scale sub-linearly with the size of the state space, managing millions of configurations within a compact memory footprint.

Why It Works: Set-Level Operations

The true power of symbolic representation is not just that it stores states compactly, but that it allows for set-level manipulation.

If you want to find all states reachable in one step from a current set of states, an explicit planner must iterate through every single state, evaluate every valid action, and collect the targets. In contrast, a symbolic planner performs a single logical operation (typically a combination of conjunction and existential quantification) directly on the BDDs representing the current states and the transition rules.

This means an algorithm can compute the transitions of billions of states in a single step. As Stefan Edelkamp et al. highlighted in their analysis of the resurgence of symbolic search in AI planning, this capacity to operate on entire sets rather than individual points allows symbolic estimators to easily outperform explicit heuristic searches in environments with high structural similarity.

This efficiency extends across several domains:

  • Verification of Multi-Agent Systems: Kaile Su leveraged Ordered Binary Decision Diagrams (OBDDs) to handle the state explosion inherent in distributed systems, using variable quantification to eliminate complex knowledge operators. Similarly, Francesco Belardinelli et al. showed that BDDs can manage the history-dependent state spaces of multi-agent systems, scaling to track agent histories across spaces as large as $10^{18}$ states.
  • Strategy Synthesis: In game theory and verification, Petr Cermák et al. utilized OBDDs to encode both the underlying state space and the strategy assignments of agents simultaneously, facilitating the automated synthesis of Nash equilibria.
  • QBF Solving: Beyond planning, Marco Benedetti applied BDDs to extract compact, verifiable certificates of satisfiability from Quantified Boolean Formulas, avoiding the exponential memory blowup associated with explicit tree-based strategy representations.

Beyond Boolean: Extending the Diagram

Standard BDDs are strictly binary; they map boolean inputs to a boolean output (True/False or 1/0). However, real-world problems often require tracking non-boolean data, such as probabilities, financial costs, or resource utilities. To handle this, researchers extended the core BDD architecture into more expressive variants.

Algebraic Decision Diagrams (ADDs)

An ADD (or Multi-Terminal BDD) relaxes the constraint that the terminal nodes must be 0 or 1. Instead, the leaves of the DAG can be any real number or element of an algebraic structure.

This extension is vital for optimization and probabilistic reasoning. For instance, David Speck 0001 et al. utilized ADDs in oversubscription planning to map sets of states directly to numerical utility values. This allowed their framework to identify the maximum achievable utility within a specific cost layer without evaluating states individually. In the context of stochastic systems, Marta Kwiatkowska et al. applied Multi-Terminal BDDs to represent transition probability functions in multi-player games, executing value iteration entirely through symbolic matrix-vector multiplications.

Edge-Valued Decision Diagrams (EVMDDs)

While ADDs place values at the terminal leaves, Edge-Valued Multi-valued Decision Diagrams (EVMDDs) store additive weights along the edges of the graph. As you traverse down the diagram following the variable assignments, you accumulate these edge values to compute a final cost.

          [ Variable X ]
          / (cost +2)  \ (cost +5)
         /              \
   [ Node B ]        [ Node C ]

Florian Geißer et al. demonstrated that EVMDDs are uniquely suited for planning tasks with state-dependent action costs (e.g., where fuel consumption varies based on a vehicle's current speed). By exploiting the internal logic of the cost functions, EVMDDs prevent the exponential action explosion that occurs when trying to enumerate every possible state-cost combination.

Summary

Symbolic state space representation works because it replaces explicit enumeration with structural compression. By encoding sets of states as decision diagrams, algorithms can exploit the underlying logic of a problem domain to merge redundancies. Ultimately, this turns the curse of dimensionality on its head: instead of being penalized by large state spaces, symbolic algorithms thrive whenever those spaces possess shared, underlying patterns.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 197 papers
  2. Version 1 · 2026-10-04 · 205 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_symbolic_state_representation_symbolic_s_aa5abd20,
  title = {symbolic state representation (symbolic state space representation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-state-representation-symbolic-state-space-representation/rdr_aa5abd204e224c6d8b4f3a03459585fb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_symbolic_state_representation_symbolic_s_aa5abd20_v2,
  title = {symbolic state representation (symbolic state space representation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-state-representation-symbolic-state-space-representation/rdr_aa5abd204e224c6d8b4f3a03459585fb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake