Skip to content

Can the workflow keep going? (progress)

Some workflows never really finish: an incident run-book keeps moving between watching, mitigating, paging and resolved as alerts come and go. Others can get stuck: a retry loop that keeps retrying and never closes, or a policy that keeps reading events without ever proposing anything. This check asks, once when the module is built, whether the workflow can keep making progress from its start, and it holds every decision of a module whose workflow cannot.

This page is for people who design workflow charts and for anyone deciding how much to rely on a passing check. It assumes you know what a policy's states and events are (see Write a policy); the other checks are on The six checks. The name of this check in decision records is game.

The question

From the start state, can the workflow be kept running forever so that it keeps coming back to states where it makes progress, and so that its long-run average reward is not negative?

"Making progress" and "reward" are two numbers on each state:

  • a priority, a small whole number. Even (0, 2, …) means "fine to keep coming back here forever"; odd (1, 3, …) means "the workflow must not end up circling here forever". If a run keeps returning to several states, the largest priority among them decides.
  • a payoff, a reward for each step spent in the state. Negative means costly (waking a person, retrying). Default 0.

For a policy written as text, the library sets the priorities for you:

State in a text policy Priority Meaning
proposes an action 2 (even) progress
final (no event leads anywhere from it) 2 (even) finished, fine to stop here
every other state 1 (odd) waiting, not progress

So a text policy passes when, from its start, it can keep reaching states that propose an action or reach a final state. A policy such as (test(ping))*, which reads ping events forever and never proposes anything, fails. All payoffs in a text policy are 0.

For a chart built with Statechart, you set both numbers on each state (priority defaults to 0, so a chart where you set nothing passes the priority test).

Who chooses the next event. By default the check assumes the service steers the workflow: from each state it may pick whichever outgoing event suits it. Mark a state environment=True when someone else picks what happens next there (a customer, a payment network, a pager being acknowledged). The check then assumes the worst choice in that state.

The intuition: a token on the chart

Imagine a token on the start state. Each step it follows one arrow out of its current state. A state with no arrows out is final: the token stays there. The question becomes: can the token be steered (by the service where it chooses, against the environment where that chooses) so that the largest priority it keeps seeing is even, and the average payoff along its route is at least zero?

Here is the incident_response chart as the check sees it. Each arrow shows the event and its reward (the payoff of the state it enters):

graph LR
    W["watch<br/>priority 0, payoff 0"] -- "alert / 1.0" --> M["mitigating<br/>priority 0, payoff 1"]
    M -- "still_bad / -0.2" --> P["paging<br/>priority 2, payoff -0.2"]
    P -- "ack / 1.0" --> M
    M -- "clear / 2.0" --> R["resolved<br/>priority 0, payoff 2"]
    R -- "alert / 1.0" --> M

Every priority is even, so any run is acceptable. The best long-run average comes from cycling between mitigating and resolved: \((2.0 + 1.0)/2 = 1.5\) per step. The check passes.

Worked example

Run the incident example:

uv run grounded-decision examples incident_response

Every decision in it shows:

         game             PASS  can the policy keep making progress (parity win, nonnegative mean)?

and the record's game entry has metrics.parity_win: true and metrics.nonnegative_mean: true. Every shipped example passes this check (every game entry in uv run grounded-decision examples --all --json is passed), so to see it fail you have to build a chart for it. This script builds five small charts, makes one decision on each with healthy evidence, and prints the verdict and the check's summary:

from grounded_decision import Event, Module, Statechart
from grounded_decision.examples.common import well_corroborated_evidence

charts = {
    # A pager whose only escalation is marked "must not stay here" (odd).
    "odd_paging_reachable": (
        "alert",
        Statechart("pager")
        .state("watch", initial=True)  # priority 0, payoff 0
        .state("paging", action="page_oncall", priority=1)
        .on("watch", "alert", "paging"),
    ),
    # Every reachable state costs something.
    "every_state_costly": (
        "fail",
        Statechart("retries")
        .state("queued", initial=True, payoff=-1.0)
        .state("retrying", action="retry", payoff=-2.0)
        .on("queued", "fail", "retrying")
        .on("retrying", "fail", "queued"),
    ),
    # A retry loop that never reaches "closed": the retry state is marked
    # "must not stay here forever" (odd).
    "retry_forever": (
        "fail",
        Statechart("retries")
        .state("submitted", initial=True)
        .state("retrying", action="retry", priority=1)
        .state("closed", action="close")
        .on("submitted", "fail", "retrying")
        .on("retrying", "fail", "retrying"),
    ),
    # Same, with a way out the service controls.
    "retry_or_close": (
        "fail",
        Statechart("retries")
        .state("submitted", initial=True)
        .state("retrying", action="retry", priority=1)
        .state("closed", action="close")
        .on("submitted", "fail", "retrying")
        .on("retrying", "fail", "retrying")
        .on("retrying", "give_up", "closed"),
    ),
    # Same, but the customer (not the service) picks what happens next.
    "retry_customer_decides": (
        "fail",
        Statechart("retries")
        .state("submitted", initial=True)
        .state("retrying", action="retry", priority=1, environment=True)
        .state("closed", action="close")
        .on("submitted", "fail", "retrying")
        .on("retrying", "fail", "retrying")
        .on("retrying", "give_up", "closed"),
    ),
}
for label, (event, chart) in charts.items():
    module = Module(name=label, chart=chart.validate())
    record = module.decide(Event(event), well_corroborated_evidence())
    game = next(check for check in record.channels if check.name == "game")
    print(f"{label:23} {record.verdict.value:8} {game.summary}")

Output:

odd_paging_reachable    abstain  parity_win=False nonnegative_mean=True
every_state_costly      abstain  parity_win=True nonnegative_mean=False
retry_forever           abstain  parity_win=False nonnegative_mean=True
retry_or_close          act      parity_win=True nonnegative_mean=True
retry_customer_decides  abstain  parity_win=False nonnegative_mean=True

Read it row by row:

  • odd_paging_reachable fails. The only way out of watch is to paging, which is final and marked "must not stay here". Every run ends there.
  • every_state_costly fails on the payoff test: the only cycle averages below zero. Every decision abstains.
  • retry_forever fails. The workflow can only retry forever, and retrying is marked "must not stay here". closed is never reached.
  • retry_or_close passes. The service can send give_up from retrying and reach closed, which is final (a final state gets a self-loop at its own priority, here 0).
  • retry_customer_decides fails. The chart is the same, but the customer picks the next event in retrying, and the customer can keep failing forever. The check assumes they will.

Text policies, from the same kind of script with Module.from_expr(label, parse(text)):

ping_forever    False  parity_win=False nonnegative_mean=True     (test(ping))*
ping_then_page  True   parity_win=True nonnegative_mean=True      (test(ping))* ; test(alert) ; act(page)
one_shot        True   parity_win=True nonnegative_mean=True      test(suspicious) ; act(block)
repeat_cycle    True   parity_win=True nonnegative_mean=True      (test(request) ; test(approved) ; act(grant))*

ping_forever never proposes anything, so it fails. The others can always reach a state that proposes an action or a final state.

Events out of order. An event the current state does not handle, whether the policy never names it or names it only later (an approval before any request), leaves the entity where it is and proposes nothing; the record's reason reads, for example, event 'manager_approved' is not handled in state 's0'; nothing proposed (uv run grounded-decision examples step_json_roundtrip, request 3). There is no hidden "dead" state that a stray event could send an entity to, so the states the progress check analysed are the only states an entity can be in.

The exact rule

When the Module is built, the chart is turned into a graph: one vertex per state, one edge per transition, and a self-loop (event _final) on each state with no outgoing transition. A state marked environment=True belongs to the environment; every other state belongs to the service. Two questions are solved on it:

  • parity_win: does the service win the parity game from the start state, that is, can it make the largest priority seen infinitely often even, whatever the environment does in its states? Solved exactly with Zielonka's algorithm.
  • nonnegative_mean: is the best average edge reward over a cycle reachable from the start at least zero (allowing \(10^{-12}\) for rounding)? Solved exactly with Karp's maximum-mean-cycle algorithm. An edge's reward is the transition's payoff plus the payoff of the state it enters.

The check passes when both are true. The two answers are computed separately: no single run is certified to satisfy both at once.

Field / setting Meaning
metrics.parity_win the priority answer
metrics.nonnegative_mean the payoff answer
passed both true
trust lean when passed, operational when failed
Limits.max_game_vertices (200) more states than this: both answers false, every decision abstains
Limits.max_parity_depth (64) deeper solver recursion than this: both answers false, every decision abstains
Limits.max_karp_vertices (200) more states than this for the payoff solver: both answers false, every decision abstains

The answer is computed once and copied into every record. If you change the chart after building the module, build a new module.

What it does not tell you

  • The payoff answer is best-case. environment=True changes the priority answer only. The payoff answer still assumes the best route through the chart, including through environment-owned states.
  • It checks that progress is possible, not that it happens. In service-owned states, the check assumes your service sends the event that keeps the workflow moving. If in practice nobody ever sends give_up, retry_or_close still retries forever. Mark the states where you do not control the next event as environment=True.
  • Your chart's priorities are yours. A chart left at priority 0 everywhere passes the priority test whatever its shape. Give odd priorities to the states the workflow must not circle in forever.
  • It does not look at the evidence. A passing game check says nothing about whether this decision is supported; the four data checks do that (see The six checks).
  • trust=lean on a pass names a catalog result about games. See Trust levels and honest limits.

Unit tests are still worth writing: step a module through every event sequence you expect and assert on the actions it proposes.

What to do when it fails

Every decision abstains, with a reason such as parity_win=False nonnegative_mean=True. Look at the two flags:

  • parity_win=False, text policy: the policy can loop without ever proposing an action, and has no final state to reach. Make every loop end in an action, or give it a way out.
  • parity_win=False, chart: from the start, every way the workflow can run (with the environment choosing in its states) ends up circling among states whose largest priority is odd. Add a transition the service controls out of the odd loop, or reconsider which states are environment=True.
  • nonnegative_mean=False: every reachable cycle costs more than it earns. Make costly states cheaper, or add a cycle that pays.
  • Both false, with a message about vertices or depth: the chart is larger than max_game_vertices or max_karp_vertices (200), or the solver went deeper than max_parity_depth (64). Split the chart, or raise the limit deliberately.

The priorities, payoffs and environment marks are part of your policy (a domain definition) and the size caps are engineering budgets; none of them is learned from outcomes (Where every number comes from). See Troubleshoot: why did it abstain?.

Where next