Lazy Memory: Growing Small Controllers for Multi-Objective Games from Boolean Conflicts

A controller that must meet several goals at once, such as "service request A infinitely often and keep queue B from starving and never deadlock," usually needs internal memory: it must remember which goal it is currently working toward. The theory of these games tells us that finite memory suffices, but not how little memory will do. Synthesis tools meanwhile build memory for every goal everywhere in the state space. This proposal borrows the central trick of Boolean abstraction from temporal-logic satisfiability checking and applies it to controller memory. In that trick, a complex specification is replaced by its propositional skeleton, a cheap engine finds candidate assignments, and a precise checker returns a small conflict whenever a candidate fails. Here the analogue is to start with a controller that tracks almost no goals. Where it loses, we extract the small set of goals whose joint tracking is actually necessary, and we add memory only for those goals and only in the region of the game where the conflict arose.

The setting is generalized parity games. A parity game is a two-player game on a graph where each state carries an integer priority, and a play is won when the largest priority seen infinitely often is even. A generalized parity game uses a Boolean combination of $k$ such conditions as its winning objective. Generalized Parity Games proves that finite-memory winning strategies exist and explicitly leaves memory minimization open. Partial Solvers for Generalized Parity Games makes solving fast but never measures controller memory. The claim is that counterexample-guided refinement over which objectives are remembered, and where produces controllers with substantially fewer memory states than full-product constructions. We further claim that it matches or beats generic post-hoc controller minimization at a fraction of that method's cost.

Core Claim

Memory in a generalized parity controller exists to handle conjunctions. The winner must interleave progress on several parity conditions that cannot all be served by one fixed move per state. Two facts suggest that most of this memory is wasted in practice. The first is local. Inside a subgame, meaning the region left over after the recursive solver strips away attractor sets, a parity condition often becomes constant. If every priority of condition $i$ that remains in the region is even, every play staying there satisfies it; if every remaining priority is odd, every such play violates it. Condition $i$ is then a "don't care" in that region, in exactly the sense used by Boolean Abstraction for Temporal Logic Satisfiability. That paper replaces temporal sub-formulas with propositional variables, simplifies them by polarity, and bypasses sub-formulas that cannot affect the outcome. We transplant this reasoning from formula space to memory space. The second fact is relational. Even among conditions that are live in a region, often only a small subset actually conflicts, so that serving one forces neglecting another. Only such conflicting subsets need a memory bit.

The idea is new in the following way. Prior uses of Boolean information in game solving guide search, not memory. Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis re-injects propositional sub-formula "trueness" into parity-game states to initialize strategy improvement and to shape Q-learning rewards. That work is restricted to memoryless strategies on single-parity games and motivates us by showing that specification-level Boolean information shrinks controllers. It does not construct or prune memory. The lexicographic line, Stochastic Games with Lexicographic Reachability-Safety Objectives and Stochastic games with lexicographic objectives, proves that $2^n-1$ memory classes are necessary in the worst case. It shows that this memory only records which goals are satisfied or violated. That result constrains us: we cannot beat worst-case bounds, only instance-level waste. It also licenses a per-instance search, because the memory it describes is propositional bookkeeping over goals.

Research Program

The algorithm, which we call lazy memory refinement, maintains a memory assignment. For each region produced by the Zielonka-style recursion of Generalized Parity Games, it records the subset $S$ of parity conditions that the controller tracks there, using a round-robin counter over $S$. The initial assignment comes from Boolean simplification alone. We compute each region's local don't-care conditions by the constant-condition test above and replace them with true or false in the objective's skeleton. We then apply polarity simplification in the style of Boolean Abstraction for Temporal Logic Satisfiability and keep only conditions that appear under a conjunction still live after simplification.

The main loop proceeds in three steps. First, we solve the product of each region with its current memory using the partial solvers and antichain machinery of Partial Solvers for Generalized Parity Games. Second, we compare the resulting winning region to the true winning region, which is obtained once from the unrestricted solver. Third, at any state that is truly winning but lost under the current memory, we take the environment's counter-strategy in the product. We then identify the minimal set of tracked-plus-untracked conditions it violates, using activation variables on the skeleton in the manner of Computing Unsatisfiable Cores for LTLf Specifications. That set becomes the region's new $S$.

The loop terminates because $S$ only grows and is bounded by $k$. It is sound because the final strategy is checked against the true winning region.

The theory component has two targets. The first is to characterize classes of skeletons for which the initial assignment is already exact, so that no refinement is needed, for example conjunctions whose conditions have disjoint odd-priority supports within each region. The second is to state the gap between our output and true minimum memory. We expect it to be at most the cost of committing to round-robin counters rather than arbitrary memory machines. We will measure that gap empirically against exact minimization rather than assert it.

A second, smaller application tests whether the idea transfers to the lexicographic stochastic setting. There we prune the $2^n-1$ memory classes of Stochastic games with lexicographic objectives by two means: propositional implications between targets (reaching $T_1$ may already imply having visited $T_2$), and unreachability of class combinations in the given arena. Only instance-level reductions are sought; the worst-case lower bound stands.

Baselines

The naive reference point is the full-memory controller. We solve with the recursive algorithm of Generalized Parity Games and extract the strategy with a counter over all $k$ conditions in every region. This is what one gets by doing nothing about memory. Its memory count and total controller size, measured as states of the product machine, set the ceiling.

The strongest existing solver is the hybrid partial-solver approach of Partial Solvers for Generalized Parity Games. On its 152 SYNTCOMP-derived generalized parity benchmarks it reports solving 86% with a mean non-timeout time of 56 ms, and improved performance on 75% of generalized parity games. It is the right competitor for time and coverage. No reported result found on Lacuna for controller memory size under that method, so we will extract and measure its strategies ourselves with the same full-memory extraction. Our loop calls this same solver internally, which makes the time comparison fair. Any added cost is attributable to refinement.

The strongest competitor on memory is post-hoc minimization. We take the full-memory controller and minimize it as an incompletely specified Mealy machine, both with a fast heuristic and with an exact SAT-based encoding. For this minimization, the don't-care entries are exactly the state-memory pairs unreachable under the strategy. No reported result on these benchmarks was found on Lacuna for this baseline either. All methods get the same machine, the same per-instance timeout, and no per-family tuning. We would count as beating minimization if we reach at most its heuristic's memory count at lower total time. We would also count it a win if we land within a small margin of its exact optimum on instances where the exact encoding times out or needs far longer.

We also adapt semantic initialization, the $SI_{sem}$ method of Semantic Labelling and Learning for Parity Game Solving in LTL Synthesis. That method reports that controllers occupied 14% of the game graph versus 26% with standard strategy improvement on SYNTCOMP. We run it on the full-memory product, to test whether search guidance alone shrinks memory usage.

Three ablations isolate the key ingredients. The first removes conflict cores and adds conditions one at a time in a fixed order. The second removes region locality and uses one global $S$. The third removes the Boolean initialization and starts from $S=\emptyset$ everywhere.

Why not just…?

Why not just minimize the controller after solving? This is the real threat. Mealy-machine minimization with don't cares is mature, and on small instances it may find smaller machines than our round-robin memory ever can. Our bet is that minimization must first build the full product, which grows multiplicatively with $k$, and that exact minimization is expensive. Refinement never builds the product where it is not needed. The experiments settle this directly. If minimization alone matches our memory counts and our total time across the benchmark families, the proposal fails and we will say so. If it matches size only at much higher cost, our contribution is scalability. We will also report our method followed by minimization, since the two may compose.

Why not just reduce to a single Streett or Rabin game and use a classic solver? Generalized Parity Games shows that such one-size-fits-all reductions ignore internal structure and pay worst-case factors that grow like $k!$. Partial Solvers for Generalized Parity Games finds exact standalone solvers timing out on SYNTCOMP where hybrid decomposition succeeds. The reduction also bakes full memory into the translated game, so it cannot shrink memory by construction. We include it only as a timing reference on instances where it finishes.

Why not just use semantic heuristics to find small strategies without changing the memory? Semantic initialization does shrink the portion of the arena a strategy uses. However, a strategy over a full-memory product still carries every memory bit, even if it visits few states. The adapted $SI_{sem}$ baseline tests whether this confound matters: if it matches our memory counts, the Boolean conflict machinery is unnecessary.

Why not just learn a policy with reinforcement learning? Learned policies give no guarantee on hierarchical or parity constraints and do not expose a memory structure to minimize. On lexicographic games, Stochastic games with lexicographic objectives reports the exact method solving Virus in 28 seconds against 405 seconds for reinforcement learning. We therefore do not treat learning as a competitor for exact memory-minimal synthesis.

Proposed Experiments

The primary benchmark is the set of 152 generalized parity games generated from SYNTCOMP TLSF specifications used by Partial Solvers for Generalized Parity Games. We add its 240 standard parity games as a sanity check: with $k=1$, our method should add no memory and no overhead. The metrics are memory states per controller, total controller states, synthesis time, the fraction of instances solved within the timeout, and the number of refinement iterations. Each is reported per specification family, because Computing Unsatisfiable Cores for LTLf Specifications shows that Boolean methods are highly sensitive to formula structure.

Three decisive checks follow. The first is correctness: every synthesized controller must win from the full winning region, checked by model checking the product. The second is the head-to-head on memory against exact minimization, on instances where the exact encoding finishes. This measures our optimality gap, and a large gap would mean round-robin memory is the wrong shape. The third tests whether conflict-core overhead pays off. Boolean Abstraction for Temporal Logic Satisfiability reports that its conflict feedback sometimes slowed execution overall. We therefore report the fixed-order ablation's time against the full method, expecting cores to cost more time while saving memory. The trade-off will be reported, not hidden.

The secondary experiment runs lexicographic memory-class pruning on the PRISM-games case studies from Stochastic Games with Lexicographic Reachability-Safety Objectives: Dice, Charlton, Hallway, CleaningRobot, Avoid the Observer, and Virus. We count memory classes actually retained against the $2^n-1$ bound. We check that solving time stays within the reported 1.25x–1.7x overhead of single-objective solving on Hallway and Avoid the Observer.