Compositional Decomposition for Program Verification and Logical Reasoning

91 concepts61 papers1 proposal

When evaluating a massive codebase for bugs, proving that a recursive algorithm terminates, or translating complex natural language into formal logic, systems face a fundamental barrier: the state explosion problem. If a system attempts to reason about a complex problem globally and monolithically, the combination of variables, execution paths, and logical dependencies grows exponentially.

To overcome this bottleneck, a powerful paradigm has emerged across formal verification, logic programming, and artificial intelligence: compositional decomposition. Instead of analyzing or generating a system as a single black box, this approach breaks the problem down into isolated, independent modules, computes compact behavioral summaries for each component, and composes these summaries to reason about the global system.

The Monolithic Bottleneck and the Power of Summarization

In traditional program analysis, verifying a property across a large software system often requires "inlining" functions—replacing a function call with the function's entire body. As Haoze Wu notes in Lemur: Integrating Large Language Models in Automated Program Verification, this lack of modularity forces solvers to ingest programs as monolithic blocks, creating severe scalability limits and frequent analysis timeouts.

Compositional verification bypasses this exponential growth by generating reusable function summaries. Instead of re-evaluating a function's internal execution paths every time it is called, a modular analyzer evaluates the function exactly once in isolation to produce a summary—a logical contract mapping valid input states (pre-conditions) to their corresponding output states (post-conditions).

Monolithic Analysis (Inlining):
Main Program ---> Call Fn A ---> Evaluate Fn A Internal Paths
             ---> Call Fn A ---> Re-evaluate Fn A Internal Paths (Redundant!)

Compositional Analysis (Summarization):
Fn A ---> Analyzed Once In Isolation ---> Stored Summary (Input -> Output)
Main Program ---> Call Fn A ---> Substitute Stored Summary Instantly

The power of this mechanism is demonstrated across several verification domains:

This principle extends even to complex data structures and memory blocks. For instance, Supratik Chakraborty et al. show in Verifying Array Manipulating Programs by Tiling that global array properties can be decomposed into localized, iteration-specific regions. By proving that a generic loop iteration satisfies a local requirement without disrupting others, the system verifies the entire memory block compositionally without exploding the state space.

Splitting Logic Programs Without Breaking Dependencies

The challenge of decomposition becomes more nuanced in declarative logic programming, such as Answer Set Programming (ASP) and Datalog. In these environments, rules are highly interconnected, and a naive split can easily break recursive cycles or invalidate nonmonotonic negation. As Thomas Eiter observes in Towards Automated Integration of Guess and Check Programs in Answer Set Programming: A Meta-Interpreter and Applications, if generating and verifying modules are not cleanly decoupled, a failure in a verification subprogram can inadvertently wipe out the entire solution candidate.

To safely decompose logic programs, researchers rely on dependency graph partitioning. The fundamental mathematical constraint is the preservation of strongly connected components (SCCs)—or loops—within the predicate dependency graph.

In Symmetric Splitting in the General Theory of Stable Models, Paolo Ferraris et al. prove that a logic program can be mathematically reduced to smaller sub-problems as long as no individual loop is split across the partition boundaries. This allows separate modules to treat each other's outputs as non-deterministic, arbitrary inputs, facilitating parallel execution and separate compilation.

Monolithic Dependency Graph:
[Atom A] <---> [Atom B] ---> [Atom C] <---> [Atom D]
\_____________________/      \_____________________/
      Loop 1 (SCC 1)               Loop 2 (SCC 2)

Safe Modular Split:
Module 1 (Contains Loop 1)  ---> Outputs treated as inputs ---> Module 2 (Contains Loop 2)

When predicates are universally shared, standard predicate-level splitting fails because it detects false circularities. To bypass this bottleneck, Jorge Fandinno and Yuliya Lierler introduce a more granular framework in Splitting Answer Set Programs with Respect to Intensionality Statements. By analyzing dependencies based on specific predicate arguments and temporal conditions rather than the broad predicate name alone, they successfully isolate iterative processes (like planning steps), ensuring that the stable models of the original program can be perfectly reconstructed from the solutions of the independent components.

Once these boundaries are established, modules must communicate cleanly. Chitta Baral et al. outline how declarative import rules allow a parent module to iterate over the answer sets of a sub-module in A Language for Modular Answer Set Programming: Application to ACC Tournament Scheduling. This structure allows developers to factor a massive search space into independent constraint sets without relying on procedural control structures, preserving the purely logical nature of the program.

From Formal Solvers to Language Models

The structural benefits of modular decomposition are not confined to classical solvers; they are increasingly vital for scaling logical reasoning in Large Language Models (LLMs). When an LLM attempts to generate a long, complex program or a formal mathematical proof monolithically, it faces a cognitive equivalent of the state explosion problem: subtle bugs compound over long contexts, leading to logical drift and incorrect code.

By forcing LLMs to adopt a divide-and-conquer strategy, recent frameworks mirror the exact principles of classical interprocedural analysis:

Whether implemented via automated SMT solvers or prompted inside a neural language model, the core intuition of compositional decomposition remains identical. By isolating logical components, establishing strict input-output interfaces, and summarizing local behaviors, we can transform computationally intractable, global reasoning problems into a series of simple, highly scalable tasks.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_modular_logic_decomposition_aed29be0,
  title = {modular logic decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modular-logic-decomposition/rdr_aed29be08c0040b8bec2a4ff50f3dfc7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_modular_logic_decomposition_aed29be0_v1,
  title = {modular logic decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/modular-logic-decomposition/rdr_aed29be08c0040b8bec2a4ff50f3dfc7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake