Lazy Decentralized Shields: Growing Multi-Agent Safety Filters Inside a SAT Solver

When several learning agents share a space but each sees only part of it, keeping them safe requires a shield: a filter that removes dangerous actions before an agent can take them. In the multi-agent case each agent's filter may depend only on what that agent itself observes, yet all the filters together must keep the joint system safe in every situation the team could actually be in. The current best method compiles such filters offline. It first computes a central safe region, then writes the entire "split this into per-agent filters" problem as one large Boolean formula and hands it to a SAT solver (a program that decides whether a set of logical constraints can all hold at once). We propose leaving most of those constraints unwritten. A small piece of external code plugs into the solver through a standard callback interface. It watches the solver's partial guesses about which actions each agent may take, and it adds a constraint only when a guess actually allows an unsafe joint action in some reachable state. Solvers for scheduling and multi-agent pathfinding already work this way. We expect it to matter more here, because the eager formula grows multiplicatively with the number of agents, the size of each action set, and the length of observation history each filter may condition on.

The opportunity is concrete. Shield Decomposition for Safe Reinforcement Learning in General Partially Observable Multi-Agent Environments showed that SAT-based decomposition succeeds where naive decomposition fails, and that decentralized shields give zero safety violations at comparable reward. It runs the solver once, on a fully pre-written encoding, over small grid and particle worlds. Single-agent work shows that partially observable shielding hits a hard state-explosion wall: Compositional shield synthesis for safe reinforcement learning in partial observability reports monolithic synthesis failing at 400 to 4,600 states. The question we ask is whether lazy constraint generation moves the multi-agent decomposition step past the sizes where eager encoding stops working, while keeping the zero-violation guarantee.

Core Claim

Each agent $i$ has a local observation class $o_i$, meaning its observation together with a bounded history of length $k$. The decentralized shield is a choice of permitted action sets $P_i(o_i)$. It is correct when, for every joint state $s$ in the central safe region, the joint actions allowed by all agents' filters at their observation classes $o_i(s)$ are safe:

$$\prod_i P_i(o_i(s)) \subseteq \mathrm{Safe}(s), \qquad \text{and each } P_i(o_i) \neq \emptyset,$$

where $\mathrm{Safe}(s)$ is the set of joint actions that keep $s$ inside the safe region. Written out eagerly, this needs roughly one clause for every safe state and every unsafe joint action, which is exponential in the number of agents. Our claim is that only a small fraction of these clauses ever matter. Most unsafe joint actions are ruled out once a few "frontier" states pin down the shared observation classes. A propagator that checks candidate assignments against $\mathrm{Safe}(s)$ and returns a short explanation clause should therefore find the same shields while materializing a few percent of the eager formula. This would let synthesis handle more agents and longer histories. A second, smaller claim follows. The solver keeps its learned clauses between calls, so when a shield at history length $k$ is unsatisfiable or too restrictive, it can be refined to $k+1$ incrementally instead of being rebuilt from scratch.

The mechanism comes from two places. The first is the user-propagator interface IPASIR-UP from Satisfiability Modulo User Propagators. It lets external code watch a conflict-driven SAT solver's assignments and inject clauses without restarting the solver. The second is lazy clause generation as used in Lazy CBS, where a constraint engine explains path-cost increases with learned nogoods (short clauses recording combinations that cannot work) only when a conflict appears. Lazy CBS does this in fully observable, centralized pathfinding. We apply the same pattern to the decentralization constraint, which exists only because of partial observability. Partial observability is the regime we study, and the safety guarantee is the constraint the method must not break.

Research Program

We would build the system in three layers. The first layer reuses the setup of the Shield Decomposition paper: an abstract joint model, the central safe region obtained by fixpoint computation, and the map from joint states to per-agent observation classes. The second layer is a CaDiCaL-based solver whose Boolean variables are the "agent $i$ may take action $a$ in observation class $o$" indicators. It starts with only non-emptiness clauses. The third layer is the propagator. Whenever the solver's trail fixes enough indicators that some safe state $s$ has an allowed unsafe joint action $\mathbf{a}$, the propagator returns the clause "not all of these indicators are true." This clause has one literal per agent and is a minimal explanation in the Lazy CBS sense.

To keep the search tractable, the propagator visits states in order of how many observation classes they share with other states. This ordering heuristic is our own design choice. We will check it with an ablation against a random order. Permissiveness is handled by a weighted extension: soft clauses reward each allowed action, solved by iterative re-solving with a cardinality bound. This keeps the shields comparable to the eager method on how many actions they leave available to the learner.

The analysis has two parts. We measure the ratio of materialized clauses to eager clauses as instances scale, which directly tests the core claim. We also measure how total time splits between the central fixpoint and the decomposition. If the fixpoint dominates at scale, faster decomposition is not the bottleneck, and we will report that plainly. Two limitations are known in advance. IPASIR-UP requires every variable mentioned in an external clause to be "frozen" (protected from the solver's simplification routines), which reduces simplification; this is documented in the propagator paper. The interface also has measured overhead in incremental use. Both could erase the gains, so the baselines below are chosen to expose exactly that.

Baselines

The naive reference point is unshielded multi-agent reinforcement learning with the same learner, recurrent independent agents or QMIX (QMIX). It sets the violation count a shield must eliminate. The Shield Decomposition paper reports that it "incurred thousands of violations during training."

The second reference point is that paper's naive decomposition, which is reported to fail to produce shields. It tells us which instances are hard at all.

The strongest competitor is the eager SAT decomposition of Shield Decomposition for Safe Reinforcement Learning in General Partially Observable Multi-Agent Environments. It is the only existing method that produces decentralized, observation-conditioned shields under general partial observability. Its reported results are qualitative: synthesis success on Flashlight, zero safety violations, and comparable or better discounted return than unshielded or centrally shielded agents. We found no reported result on Lacuna for its synthesis runtime or encoding size. To make the comparison fair, we will reimplement it on the same CaDiCaL backend, the same abstract models, and the same history length $k$. Both methods get the same wall-clock and memory caps on the same hardware, and both get the same permissiveness objective. Beating it means three things together. Our method must solve strictly more instances within the cap on a scaling sweep. It must use less memory on instances both methods solve. Its shields must be no less permissive, measured as allowed actions per observation class, and must have zero violations.

Two ablations isolate the key ingredient. The first is a lazy loop without the propagator: solve, check the full model offline, add the violated clauses, and re-solve incrementally through plain IPASIR assumptions. This separates the effect of laziness from the effect of in-search callbacks. The second ablation uses the propagator but replaces our state ordering with random ordering.

Why not just…?

Why not just keep the eager encoding and use a faster solver? On the published benchmarks this may well be enough, and we expect eager and lazy to tie on Flashlight-6. The argument against eager encoding is about growth. Clause count scales with the product of the agents' action-set sizes and with the number of history-extended observation classes. A faster solver changes constants, not that product. The scaling sweep over team size and $k$ answers the question directly. If eager keeps up through 6 agents and $k=3$, the idea has no practical value and we will say so.

Why not just use compositional spatial shields, one per agent? Compositional shield synthesis for safe reinforcement learning in partial observability scales single-agent shielding to 49,000 states by partitioning the map, and intersecting per-region shields is attractive. Those shields are conditioned on a belief support (the set of states the agent might be in) that a single agent tracks. They do not enforce the cross-agent requirement that the product of independently chosen local filters is safe, which is the condition that makes decentralization hard. We will include a per-agent version as a baseline: each agent shields against a worst-case teammate. We expect it to be safe but much less permissive, and we will measure that gap.

Why not just add a cost penalty to the learner instead of shielding? Constrained or penalized reinforcement learning gives no per-step guarantee. The file's evidence is consistent: unshielded agents average over 3,000 violations in single-agent partially observable domains (Safe Reinforcement Learning via Shielding under Partial Observability) and thousands in the multi-agent grids. We keep a penalized learner as a reference point, but it is not a competitor on the guarantee.

Why not a lazy re-solve loop without IPASIR-UP? This is the most serious threat. The propagator paper reports that the interface solved 29% fewer incremental queries than native push/pop. A simple loop that checks a complete model and re-solves could therefore beat in-search propagation. The first ablation is designed to settle this. If the loop matches the propagator, the contribution reduces to "lazy decomposition," and we would report it that way.

Proposed Experiments

The main suite uses the Flashlight-6 and Flashlight-10, Grid-Col, Particle-P, Particle-P-V, and Nearby-Obs environments from the Shield Decomposition paper. We extend them along three axes: team size from 2 to 8, history length $k$ from 1 to 4, and grid side length. The metrics are synthesis time and peak memory, the largest instance solved under a 30-minute cap, materialized clauses as a fraction of the eager count, permissiveness, training safety violations, and discounted return when the resulting shields filter QMIX and recurrent independent learners over 5 seeds each.

Three checks decide the outcome. First, if the materialized fraction does not fall below roughly 10% as team size grows, the core hypothesis is wrong. Second, the solved-instance curve must separate from eager encoding by at least one team-size step. Third, incremental refinement from $k$ to $k+1$ must beat a cold restart on time-to-shield.

As a secondary check that the shields do not hurt learning on richer tasks, we will run TokenEnv-style reach-avoid tasks from Automata-Conditioned Cooperative Multi-Agent Reinforcement Learning with restricted observations. That paper reports near-perfect team success under full observability and lists full observability as its limitation. We would check whether shielded agents keep high success when observations are cut back.