A reactive system, such as an arbiter, a buffer controller, or a robot coordinator, runs forever. It reads inputs from its environment and writes outputs at every step. Reactive synthesis builds such systems automatically from a logical specification, usually written in Linear Temporal Logic (LTL, a logic of statements like "every request is eventually granted"). Today's tools produce flat state machines or hardware circuits. Readable code is far more useful: a short loop with branches that an engineer can inspect, modify, and trust. One existing method synthesizes such code directly by searching over program syntax with a SAT solver. That search space grows exponentially with the length of the program, and the method runs out of steam on toy examples. A separate line of work has shown that splitting a specification into nearly independent pieces turns impossible synthesis problems into easy ones, but only for state-machine outputs.
This note proposes to join the two. We split the specification by output variables. We synthesize a small program for each piece with a bounded program search. We then compose the pieces in a target language whose parallel operator makes that composition correct by construction. For pieces that depend on one another, we synthesize them in order, treating already-fixed programs as part of the environment. The claim is that this pushes readable program synthesis from toy sizes to the parameter ranges where decomposed state-machine synthesis already works. The open question we test head-on is how much program compactness decomposition costs.
Core Claim
Bounded Synthesis of Reactive Programs shows that LTL specifications can be turned into structured imperative programs (while loops, if-then-else, Boolean variables). It does this by encoding the program's syntax tree and its executions directly as SAT constraints, an approach it calls the "two-wayless" encoding. Even so, it needs 8 minutes 7 seconds on the small latch benchmark, and it is monolithic. The search over programs of bound $k$ statements has roughly $V^k$ candidates, where $V$ is the number of statement choices per position. If a minimal program for the whole specification has $k = k_1 + k_2$ statements, solving two problems of sizes $k_1$ and $k_2$ costs about $V^{k_1} + V^{k_2}$ instead of $V^{k_1+k_2}$. This is the same exponential arithmetic that justifies specification decomposition.
Specification decomposition is the motivating evidence. Specification decomposition for reactive synthesis splits specifications into independent sublanguages over disjoint output sets in under 26 ms on average. With that split, BoSy solves generalized_buffer_3 in 28 seconds, where the monolithic run times out at one hour. Dependency-based Compositional Synthesis orders dependent components and synthesizes each one as a dominant strategy, meaning one that does at least as well as any alternative in every environment. With this it scales n-ary Latch from 5 bits to 1104 bits. Both papers output transition systems or circuits, not programs.
The new piece is that program composition is not free. Two reactive programs with different loop structures cannot simply be concatenated, and merging them into one sequential program can multiply their control states. We avoid this by choosing a synchronous target language with a parallel operator, in the style of synchronous languages, where threads advance together at output steps. With that operator, the independent-sublanguage soundness theorem of Finkbeiner, Geier, and Passing carries over directly to composed programs. For dependent pieces, we encode remorsefree dominance (a component's choice is never beaten by another choice in hindsight) into the two-wayless SAT encoding. The semantics of already-synthesized programs are inlined as fixed environment constraints. We are not aware of prior work that encodes dominance at the level of program syntax trees rather than transition systems.
Research Program
The system has three stages.
Splitting. The front end reuses the syntactic dependency analysis and assumption dropping of Specification Decomposition for Reactive Synthesis. It falls back to the semantic analysis of Dependency-Based Compositional Synthesis when the syntactic split is too conservative. That paper reports this happening on Sensors.
Per-piece synthesis. Each independent piece goes to a bounded program synthesizer that reimplements the direct SAT encoding. The program bound is increased until the solver succeeds, so each subprogram is minimal for its piece. Dependent pieces are handled in dependency order. Each later piece's constraints include the fixed earlier programs as environment behavior, and the solver searches for a dominant rather than a winning subprogram. Winning strategies for parts in isolation rarely exist. Reactive Synthesis of Dominant Strategies shows that dominant strategies are not guaranteed to exist either. When none exists, the system reports failure for that ordering and tries the next ordering, rather than silently returning a weaker best-effort program.
Composition and checking. The pieces are composed with the parallel operator. An independent model checker then verifies the composed program against the original specification, as a guard against implementation bugs.
We will also analyze the cost side. Tabajara et al. ( Partitioning Techniques in LTLf Synthesis) proved that partitioning finite-trace specifications can lose global state-merging opportunities and make intermediate automata larger. This is the paper that most directly contradicts our premise. The program analogue is that two separately minimal subprograms may be larger together than one jointly minimal program that shares a loop between them. We will measure this size overhead directly. We will also characterize when it occurs: we expect it when subprograms share loop guards over the same inputs. In those cases we will test a cheap post-hoc merge, which tries to re-synthesize pairs of threads jointly under a small size budget.
Planning application. Towards a Unified View of AI Planning and Reactive Synthesis reduces planning in non-deterministic environments with temporal goals (FOND planning, where actions can have several possible outcomes) to synthesis games. Through this reduction, the planning domains of Non-Deterministic Planning with Temporally Extended Goals become a second test bed. There, a synthesized program is a compact looping policy rather than a table mapping states to actions. That paper compiles the whole temporal goal into one automaton. Here we decompose the goal first, and planning state-space growth becomes the stress test for whether decomposition helps once domain dynamics couple the outputs.
Baselines
The naive reference point is the monolithic two-wayless bounded program synthesizer ( Bounded Synthesis of Reactive Programs). It runs with the same SAT solver, the same 3600-second timeout per instance, and the same size-increment schedule as our system. Its reported figure is 8 minutes 7 seconds on latch. Beating it means solving instances it cannot solve within the timeout, and reaching larger parameters on the scalable families, while producing programs no more than modestly larger on the instances both solve.
The strongest existing synthesis engine is Strix. SYNTCOMP 2018-2021 reports it as the LTL-track champion, with the top tool solving 98% of the 2020 LTL track. We run Strix, both monolithic and behind the decomposition front end, on identical instances and hardware. Its state-machine output is converted to code by a straightforward translation: a loop over a state variable with a case split. Strix will almost certainly solve more instances than any program synthesizer. The comparison is therefore not about solve rate. It asks whether, at matched solve rates on the decomposable families, our programs are substantially smaller in statements and loop-nesting depth than the translated Strix machines. We found no reported program-size result on Lacuna for translated Strix output, so this baseline is built and measured here. Gate and latch counts from SYNTCOMP give a second size reference.
Two ablations isolate the key ingredients. The first keeps only independent splits and drops the dominance-ordered stage. This shows how much of the gain on coupled families (Generalized Buffer, Robot Fleet) comes from dominance. The second replaces the parallel operator with sequential merging into a single loop, which tests whether the composition design is what keeps program size under control.
Why not just…?
Why not just run Strix and translate the state machine into code? This is the strongest practical alternative, and the experiments are designed to settle it. Translation preserves correctness and inherits Strix's coverage. However, the resulting program has one branch per machine state and transition, so it grows with the machine rather than with the logical structure of the specification. If on the decomposable families the translated machines come out within a small factor of our programs' size, the readability argument fails. In that case we would report the system as a negative result for program-level search.
Why not just decompose and then translate each piece's Strix output? This separates the contribution of decomposition from the contribution of program search, and it is a real threat. Decomposition alone may capture most of the size benefit, since each piece's machine is small. We run it as a third arm. Program search earns its place only if its subprograms are meaningfully smaller than translated per-piece machines. That would be the case, for example, if loops and counters collapse repeated states that a translated machine enumerates.
Why not just give the monolithic program synthesizer more time or a better solver? The exponential growth in the program bound means extra compute buys only a little more program length. The scaling curves on n-ary Latch will show whether the monolithic synthesizer's largest solved parameter moves when the timeout is quadrupled. On the same family, the dependency-based method moved from 5 to 1104 bits through decomposition rather than compute.
Why not just have a language model write the program and model-check it? An LLM can propose plausible reactive code. Thought of Search shows code generation paired with sound search beats step-by-step model reasoning, but it still needed human repair, and it offers no minimality and no completeness. We include an LLM-plus-model-checker arm with a fixed repair budget as a reference. We do not treat it as the main competitor, because a verified-minimal result is something it cannot provide.
Proposed Experiments
The first experiment covers the scalable families of Dependency-Based Compositional Synthesis: n-ary Latch, Generalized Buffer, Sensors, and Robot Fleet. For each method we report the largest parameter solved within one hour, together with program size. The decisive check is whether we reach parameters within roughly an order of magnitude of what the dependency-based method reaches with state-machine outputs, for example hundreds of latch bits. The monolithic program synthesizer should stall at single digits.
The second experiment uses the Boolean-output subset of the 346 SYNTCOMP 2020 benchmarks studied in Specification Decomposition for Reactive Synthesis. On it we measure solve rate, time, and the size ratio of decomposed to monolithic programs wherever both finish. That ratio is the direct test of the Tabajara-style concern. A median ratio near 1 supports the approach. Ratios well above 1, concentrated on shared-guard specifications, would identify where joint re-synthesis is needed.
The third experiment covers Robot Coffee, Lift, and Blocksworld with temporal goals from Non-Deterministic Planning with Temporally Extended Goals: LTL over Finite and Infinite Traces, reduced to synthesis games. We compare policy size and solve time against the PRP compilation reported there. We found no reported numeric runtimes on Lacuna for these domains, so all arms are rerun under one protocol. Every synthesized program, in every arm, is independently model-checked, and any verification failure counts as an unsolved instance.
References
- Bounded Synthesis of Reactive Programs
- Specification Decomposition for Reactive Synthesis
- Dependency-Based Compositional Synthesis
- Specification decomposition for reactive synthesis
- Dependency-based Compositional Synthesis (Full Version)
- Reactive Synthesis of Dominant Strategies
- Partitioning Techniques in LTLf Synthesis
- Partitioning Techniques in LTLf Synthesis
- Towards a Unified View of AI Planning and Reactive Synthesis
- Non-Deterministic Planning with Temporally Extended Goals: LTL over Finite and Infinite Traces
- Bounded Synthesis of Reactive Programs
- The Reactive Synthesis Competition (SYNTCOMP): 2018-2021
- Thought of Search: Planning with Language Models Through The Lens of Efficiency
- Non-Deterministic Planning with Temporally Extended Goals: LTL over Finite and Infinite Traces