Modular Specification Decomposition for Reactive Synthesis

24 concepts16 papers1 proposal

Reactive synthesis is the "holy grail" of formal methods: the ability to automatically transform a high-level logical specification into a correct-by-construction implementation. However, this process faces a fundamental "complexity wall." As Bernd Finkbeiner notes, synthesizing distributed systems is mathematically undecidable in the general case, and even for decidable fragments, the state-space explosion is often exponential or double-exponential.

To bypass this wall, researchers have moved away from monolithic synthesis—where a single, massive automaton is built for the entire specification—toward modular specification decomposition. The core intuition is simple: if a complex requirement can be broken into smaller, independent pieces, we can solve each piece separately and combine the results. Because the cost of synthesis grows exponentially with the size of the specification, solving two small problems ($2^n + 2^m$) is orders of magnitude faster than solving one large combined problem ($2^{n+m}$).

Breaking the Monolith

The most common form of decomposition is conjunctive decomposition. Many real-world specifications are naturally written as a conjunction of properties (e.g., "the elevator must eventually arrive" AND "the doors must never open while moving").

Lomuscio et al. demonstrate that for multi-agent systems, decomposing a goal into smaller conjuncts to build individual automata significantly reduces peak memory usage. Similarly, the SynKit tool, described by Camacho et al., treats complex formulas as a collection of smaller, simpler automata. By treating these as a "battery of constraints" rather than a single memory-intensive structure, the system avoids the traditional double-exponential bottleneck of building a monolithic deterministic automaton.

Logical and Structural Decomposition

Decomposition can happen at different levels of the synthesis pipeline:

  1. Logical Decomposition: Kretinsky et al. and Kretinsky et al. propose a "Safraless" approach to LTL translation. By decomposing complex temporal formulas into modular sub-components—such as isolating liveness properties into separate tracking units or intersecting simpler safety and suffix-closed languages—the authors achieve logically transparent translations that yield significantly smaller automata than traditional methods.
  2. Structural Decomposition: Brenguier et al. show that monolithic safety specifications (in AIG format) can be decomposed into smaller sub-specifications. By solving these sub-problems compositionally, they enable tools to tackle problems that are otherwise intractable.
  3. Dependency-based Decomposition: Finkbeiner et al. introduce an incremental approach that partitions systems based on internal variable dependencies. Instead of finding a global strategy at once, they synthesize "dominant" strategies sequentially, allowing later components to rely on the known behavior of previously synthesized parts.

Scaling to Complex Domains

This modular philosophy extends beyond pure logic into practical programming tasks. In data transformation, Wu et al. use an iterative approach that "patches" only the incorrect parts of a program rather than regenerating it from scratch. In the realm of data visualization, Wang et al. synthesize multi-layered visual outputs by decomposing the problem into independent sub-problems for each visual layer.

Even the synthesis of the specifications themselves benefits from this approach. Park et al. argue that decomposing a target specification into a conjunction of smaller properties reduces the search space for underlying SMT solvers, making it possible to efficiently generate complex specifications that would otherwise be computationally prohibitive.

The Limits of Decomposition

While decomposition is powerful, it is not a universal panacea. Tabajara et al. found that in certain contexts, such as LTL over finite traces (LTLf), partitioning can actually hinder performance. This occurs because breaking the problem apart can prevent the synthesis engine from exploiting state-space minimization, leading to larger intermediate structures.

Furthermore, Bansal et al. suggest that while basic conjunctive decomposition is effective, the field must investigate more advanced, non-conjunctive decomposition schemes to continue scaling. Despite these challenges, the consensus across the literature—from the results of the SYNTCOMP competition (Brenguier et al.) to recent modular frameworks (Geier et al.)—is that decomposition is the primary mechanism for bypassing the exponential complexity barriers of reactive synthesis.

Key Foundational Work

Transforming Undecidable Synthesis Problems into Decidable Problems (2013) — contributed 2 concept elements to this direction.
From LTL to Deterministic Automata: A Safraless Compositional Approach (2014) — 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_compositional_synthesis_3194d119,
  title = {compositional synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-synthesis/rdr_3194d11907514bb7837a4d165ba916d2},
  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_compositional_synthesis_3194d119_v1,
  title = {compositional synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compositional-synthesis/rdr_3194d11907514bb7837a4d165ba916d2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake