Many systems we want to make safe are parameterized. A leader-election protocol has to work on a ring of any size. A conference-management workflow has to keep reviewer identities secret however many papers and reviewers join. Automatically building a correct controller for such systems is a game against an adversarial environment, and over unbounded domains that game is undecidable in general. Existing synthesizers are therefore sound but incomplete: they either return a strategy that is correct for every domain size, or they run until they time out. This proposal changes where the hard question is asked. At runtime the system always faces one concrete, finite configuration, and the question "can I stay safe for the next $N$ moves whatever the environment does?" is decidable for that configuration. We propose an enforcer that sits beside an untrusted controller. At each step it allows a proposed move only if it can certify a winning response over a finite lookahead. That lookahead must end inside a candidate invariant, meaning a description of states believed to be permanently safe, produced by an offline synthesizer that was stopped early. Whenever the certification fails, the enforcer still has the remainder of its previous plan as a guaranteed safety buffer, and the failing configuration is a counterexample that is fed back to the offline synthesizer.
In short, an incomplete offline synthesizer and a predictive runtime monitor cover for each other's weaknesses. The synthesizer supplies a long-horizon argument that the monitor cannot compute on its own. The monitor supplies sound short-horizon guarantees and concrete counterexamples exactly where the synthesizer's argument breaks. If the candidate invariant is truly inductive, meaning it is preserved by every environment move under the controller's responses, the enforcer is safe forever. If it is not, the enforcer still guarantees safety over the horizon and raises an alarm at least $N-1$ steps before any violation becomes possible.
Where the open problems are
The synthesis side has precise negative results. How to Win First-Order Safety Games studies parametric transition systems such as conference management and leader election. It shows that safety games stated in first-order logic, the logic of objects and relations, are undecidable. It also shows that when the safety player wins, a memoryless strategy suffices, and it computes the most permissive strategy by eliminating second-order quantifiers. It cannot express unbounded reachability without invariants supplied by the user. Automated Synthesis of Generalized Invariant Strategies via Counterexample-Guided Strategy Refinement, which introduces the counterexample-guided strategy refinement method (CEGSR), pairs SMT solvers with a model checker to synthesize strategies that hold for every instance of a game family. It solves 8 of 9 domains but times out on Chomp $N\times N$. These two papers supply the offline machinery we reuse, and their failure modes define the target of this proposal. The harder undecidability results of The Church Problem for Countable Ordinals and Synthesis from hyperproperties motivate the general picture of "a winner exists but no strategy can be computed." We do not attack those settings directly.
The monitoring side supplies the soundness template. Formal Verification of Neural Certificates Done Dynamically gives a runtime monitor whose "green light" provably guarantees safety over a horizon $N$. It succeeds where global static verification of an 8-layer network timed out after two hours. Robust Differentiable Predictive Control with Safety Guarantees: A Predictive Safety Filter Approach shows that a terminal safe set combined with an $N$-step lookahead gives recursive feasibility. That paper relies on a hand-supplied terminal set and continuous dynamics. Our terminal set is instead a first-order formula from an incomplete synthesizer, and it may be wrong.
The closest existing work is runtime synthesis. Online Synthesis for Runtime Enforcement of Safety in Multiagent Systems moves multi-agent synthesis online with a lookahead window. It scales to 50 agents where centralized synthesis failed beyond four, but it handles only geometric collision avoidance and has no terminal argument, so it can walk into dead ends. Runtime Enforcement of Hyperproperties enforces specifications at runtime by solving parity games, a standard class of infinite games on finite graphs. It is limited to finite-state, universally quantified specifications and proves that sequential enforcement is undecidable in general. Neither work enforces first-order, parametric specifications, and neither uses an incomplete offline strategy as a terminal condition repaired by runtime counterexamples. Finally, Neural Control and Certificate Repair via Runtime Monitoring feeds runtime violations back into retraining. Its authors note that this provides no global guarantee. We feed violations back into a deductive synthesizer, so that a successful repair yields a proof.
Core Claim
Let $s$ be the current concrete configuration: a finite structure with its current objects and relations. Let $\mathit{Safe}$ be the first-order safety condition, and let $I$ be a candidate invariant. The enforcer allows a proposed system move $a$ exactly when
$$\exists \sigma\ \forall e_{1..N}:\ \bigwedge_{t=1}^{N} \mathit{Safe}(s_t) \ \wedge\ I(s_N),$$
where $\sigma$ is a system response strategy over the horizon, $e_{1..N}$ ranges over environment move sequences, and $s_t$ is the configuration reached at step $t$ after $a$. The environment may create a bounded number of new objects per step. Because $s$ is finite and creation is bounded, this check is a finite alternating query. It can be solved by expanding it into a quantified Boolean formula or by bounded game search, so it is decidable even though the parametric synthesis problem is not.
We claim three things. First, the enforcer guarantees $N$-step safety unconditionally and infinite-horizon safety whenever $I$ is inductive under some response. Second, every step at which no move passes the check exhibits a concrete configuration that refutes the inductiveness of $I$, discovered with $N-1$ guaranteed-safe steps still in hand. Third, feeding these configurations to CEGSR or second-order quantifier elimination makes the synthesizer converge on instances where it times out when run blind. The third claim is empirical and is the one most likely to fail.
Research Program
The first component is the online checker. We will instantiate the first-order transition system on the live structure and unroll $N$ rounds of the system/environment alternation. The resulting formula will be solved incrementally with Z3 and a quantified Boolean formula solver, reusing work across steps as the horizon slides. The memoryless-strategy result of How to Win First-Order Safety Games lets us search over responses that depend only on the current state, which shrinks the existential layer. The checker always keeps the last certified plan. If no move certifies, it executes that plan's next step and raises an alarm.
The second component is the anytime offline synthesizer. CEGSR and the quantifier-elimination solver are run under a fixed budget. If neither finishes, we take the strongest candidate formula they have produced. For CEGSR this is the current invariant, and for the second-order approach it is a strategy predicate with unresolved induction obligations. We record which proof obligations remain open.
The third component is the feedback loop. Configurations where the alarm fires are exported as counterexamples, in the format CEGSR already consumes for local repair, and the synthesizer resumes. We will measure whether runtime counterexamples, which come from reachable states visited under the actual controller and environment, are more useful than those the synthesizer generates itself. That question is the core empirical bet.
The fourth component is analysis. We will characterize the cost of the online check in terms of horizon, structure size, and object-creation bound. We will also prove the alarm-buffer property: an alarm always precedes any possible violation by at least $N-1$ steps.
Baselines
The naive reference point is the untrusted controller running unfiltered. This is a scripted greedy proposer and, separately, a reinforcement-learning policy trained on small instances, both facing an adversarial environment that searches for violations beyond the enforcer's horizon. It sets the violation rate that the enforcer must drive to zero.
The second baseline is a one-step reactive shield in the style of Simplex. It blocks any move whose immediate successor violates $\mathit{Safe}$ and otherwise defers to a conservative fallback. Runtime-Safety-Guided Policy Repair proves that frequent switching of this kind degrades performance quadratically, and it reports 7.1 m/s for the shielded baseline against 7.9 m/s for minimally deviating repair in CARLA. We expect the discrete analogue to be high permissiveness loss and dead ends. Beating it means zero violations together with strictly higher permissiveness.
The third baseline is pure bounded lookahead without a terminal invariant, generalizing Online Synthesis for Runtime Enforcement of Safety in Multiagent Systems from paths to first-order games. It isolates the value of the terminal set. Beating it means a lower rate of dead ends, meaning states with no safe certified move, at equal horizon and per-step time budget.
The strongest competitor, where it terminates, is offline synthesis alone. That means NIWO with Z3 from How to Win First-Order Safety Games, which reports the most permissive strategy for conference management in under a second and noninterference variants in roughly 3 to 7 seconds, and CEGSR, which reports leader election in approximately 367 seconds and success on 8 of 9 domains, failing on Chomp $N\times N$. On domains where these finish, they are the gold standard. We will use NIWO's most permissive strategy as ground truth for permissiveness. Our method must match it with no violations, while costing no more total compute counting both offline and online time. On domains where they time out, offline synthesis gives no controller at all. There the comparison is safe episodes and permissiveness under the same total wall-clock budget. No reported online-enforcement result was found on Lacuna for any of these benchmarks.
The fourth baseline is explicit synthesis on the finite instance present at deployment, using a standard finite-game solver.
The key ablation keeps the terminal invariant but disables counterexample feedback. A second ablation replaces the synthesizer's candidate with the trivial invariant $\mathit{Safe}$. All baselines get identical environments, adversary search budgets, per-step latency caps, and offline compute.
Why not just…?
Why not just give the offline synthesizer more time? On leader election and conference management this is a real threat: the solvers already finish in seconds to minutes, and our method adds nothing except handling of domains that grow at runtime. We will report that plainly. The claim rests on domains where the offline tools stall: Chomp $N\times N$, where CEGSR times out; variants that require unbounded reachability, which How to Win First-Order Safety Games cannot express without supplied invariants; and leader election with dynamic node insertion. The equal-compute comparison decides this. If tripling the synthesizer's budget recovers the same results as our feedback loop, the feedback contribution is refuted.
Why not just solve the concrete finite game exactly at deployment? For a fixed small instance this works and will win on permissiveness. It fails on two counts. State spaces explode quickly, since centralized synthesis in Online Synthesis for Runtime Enforcement of Safety in Multiagent Systems was intractable beyond four agents on a 5×5 grid. And when the environment creates objects at runtime, the instance changes and the solution must be recomputed. We will sweep instance size and object-creation rate to locate the crossover point. If no crossover exists below realistic sizes, the proposal is unnecessary for those domains.
Why not just use bounded lookahead and pick a large horizon? Unrolling an alternating game costs exponentially more with each step of horizon, and no finite horizon rules out traps that lie just beyond it. The terminal-set ablation measures the dead-end rate as a function of $N$. If plain lookahead with a moderately larger $N$ matches our dead-end rate at the same latency, the terminal invariant is not earning its keep.
Why not just use a reactive shield? It is sound for one step but has no buffer. The results on Simplex switching in Runtime-Safety-Guided Policy Repair, and the inertia argument for predictive monitoring generally, predict that it will be either overly restrictive or trapped. The comparison above measures which.
Proposed Experiments
We will use the benchmarks from the file. The first is leader election on rings, in static and node-insertion variants. The second is conference management with the Assign and Review relations, in functional-safety and noninterference variants. Its known most permissive strategy makes permissiveness measurable exactly. The noninterference variant requires two copies of the system to be compared, which tests whether self-composition fits inside the lookahead check. The third is the CEGSR combinatorial suite, centered on 2-Nim as a solved control case and Chomp $N\times N$ as the unsolved stress case. Chomp is apt here: strategy stealing proves that the first player wins, yet no general strategy is known, which is a small instance of the gap between "a winner exists" and "a strategy can be computed." The fourth is the 50×50 multi-agent grid from Raju et al., re-encoded as a first-order safety game with an occupancy relation.
The metrics are violations per thousand adversarial episodes, permissiveness (the fraction of moves allowed by the most permissive strategy that we also allow), dead-end rate, per-step decision latency, alarm lead time, and the number of feedback rounds until the candidate invariant is proven inductive.
The decisive checks are three. On conference management, the enforcer seeded with a deliberately truncated NIWO candidate must reach zero violations and approach the permissiveness of the most permissive strategy as feedback proceeds. On Chomp and on node-insertion leader election, where offline synthesis yields nothing within budget, the enforcer must keep zero violations, and runtime counterexamples must either produce a proven invariant or measurably shrink the open proof obligations faster than equal extra offline compute does. Across all domains, every observed alarm must precede any reachable violation by at least $N-1$ steps, which checks the buffer theorem empirically. A negative result on the second check would still be informative. It would show that the monitor's counterexamples are no more useful to deductive synthesis than the synthesizer's own, and that the gains come entirely from bounded lookahead.
References
- How to Win First-Order Safety Games
- Automated Synthesis of Generalized Invariant Strategies via Counterexample-Guided Strategy Refinement
- The Church Problem for Countable Ordinals
- Synthesis from hyperproperties
- Formal Verification of Neural Certificates Done Dynamically
- Robust Differentiable Predictive Control with Safety Guarantees: A Predictive Safety Filter Approach
- Online Synthesis for Runtime Enforcement of Safety in Multiagent Systems
- Runtime Enforcement of Hyperproperties
- Neural Control and Certificate Repair via Runtime Monitoring
- Runtime-Safety-Guided Policy Repair