The Case for Petri Nets for Agentic AI

In our recent software engineering blog post on what constitutes "state of the art" in agentic AI, we reviewed the rapidly evolving research landscape of AI task orchestration. Given the pace of development, new findings are emerging every week, but one trajectory seems clear. We are moving toward multi-agent systems tackling long-running, complex tasks.

As we spawn more agents and they become increasingly autonomous, working on tasks that take hours or even days to achieve, it becomes more important for us to enforce sufficient oversight to have trust in their outputs. For this we need systems that prioritise explicit structure, decomposition, traceability and control for AI workflows.

Through our involvement in the Safeguarded AI programme and our own work at HASH, we have been exploring how Petri nets — a mathematical formalism developed decades ago for modelling concurrent systems — offer a surprisingly good fit for addressing these challenges. In this post, we'll explain what Petri nets are, why we think they're well-suited to orchestrating agentic systems, and how we're applying them in practice.

What is a Petri net?

A Petri net is a mathematical model for describing processes where things happen in sequence, in parallel, or both. It was invented in 1962 by Carl Adam Petri, originally to describe chemical processes, but has since been applied to everything from manufacturing workflows to network protocols.

At first glance, Petri nets look like your typical flowcharts and process diagrams, but their mathematical foundations make them far more expressive. They can precisely capture state, concurrency and dependencies in ways that can be formally verified, analysed and simulated before anything actually runs. These properties have proven useful for modelling complex systems thus far, and turn out to be exactly what we also need for orchestrating AI agents.

Requirements for an agentic orchestration system

When deploying multiple agents on long-horizon tasks, we need to think about:

• →

  Planning: generating, auditing, and revising the plan for a given goal.

• →

  State management: tracking the status of work at any given moment such as what tasks have completed, which are in progress, what output has been produced, etc.

• →

  Coordination: how multiple agents and humans can work together to achieve a shared goal through

  • →

    task assignment (who does what, including agent identity, model config, system prompt templates, etc.)

  • →

    sequencing (what order things happen in)

  • →

    interdependency (which tasks rely on which other tasks)

  • →

    resource management (managing potential conflict in or exhaustion of resource access such as context window, API budget, mutexes, and so on).

• →

  Concurrency: having agents work on tasks in parallel, where those tasks are either independent, or where they are overlapping or competitive with one another, can be reconciled or judged afterwards.

• →

  Observability: real-time visibility into the system's current state and behaviours. Whilst state management is about tracking this information, observability is about making the state legible to humans.

• →

  Provenance: records which provide a trace of important information related to any action or product, for example the data relied upon, the actors and other resources involved, when it began and ended, etc.

• →

  Explicability: making clear why the system behaved the way it did. This builds on provenance in providing the reasons behind behaviours, rather than simply describing what was involved in producing them. This may include, for example, human or ostensible AI justification for decisions and action.

The role of Petri nets

Petri nets offer at least partial answers to some of our requirements:

• →

  Plan: the overall plan can be represented by a top-level net.

• →

  State: can be represented by the marking of the net — essentially where the tokens (think of them as work items or signals) currently sit, indicating which steps are completed, in progress or waiting to start.

• →

  Coordination: various elements of the net can represent aspects of agent and human coordination, for example:

  • →

    task assignment can be encoded either as inputs to a transition (a step in the workflow), or in the logic governing how that step executes

  • →

    sequencing is represented in the net structure.

  • →

    dependencies are encoded as preconditions: a transition (step) can't fire (execute) until the required tokens are present

  • →

    resource availability is represented by tokens in specific places — think of a place as a container representing a state or condition. If the token isn't there, the condition isn't met or the resource isn't available.

• →

  Concurrency: Petri nets are explicitly designed to represent work happening in parallel, where multiple branches can be active simultaneously.

• →

  Observability: requires building interfaces that let humans see and interrogate the current state, inputs, outputs and processes involved as execution progresses.

• →

  Provenance & Explicability: partly derived from token flow — tracking where tokens came from tells you about the inputs and actors involved in producing something. Coloured Petri nets, where tokens carry additional metadata, can extend this further by surfacing the reasonings and mechanisms via which steps arrived at their output.

Analysis and simulation

One of the notable advantages of Petri nets is that they are a mathematically rigorous formalism with decades of established analysis techniques. Properties can be analysed and computed before execution begins, to answer questions such as:

• →

  Are we guaranteed to reach some desired terminal state? This may not mean 'the goal was accomplished', but at least 'we are given an answer either way'.

• →

  Do other desirable conditions always hold? For example, that human approval always happens before certain other actions occur.

• →

  Given assumptions about task time and success rate, what is the probability distribution of expected time to complete?

• →

  How does the allocation of different levels of resource (represented via marking) affect the possibility of and time to reach some state?

This is useful to detect failure modes (e.g. infinite looping, insufficient resources, unsafe net construction) during the planning phase rather than during runtime, which would be more costly and potentially dangerous.

Beyond static analysis, Petri nets can also be simulated. The ability to estimate before committing compute resources and time will become increasingly important as agents can run autonomously for longer and longer periods. Given assumptions about task duration and success rates, we can model expected completion times, resource consumptions and bottlenecks before committing to execution.

During live runs, these assumptions are replaced by actual outcomes: an agent fails and triggers a retry loop, a human reviewer rejects an output and requests changes, or an external dataset gets uploaded. The net updates accordingly, and the same analytical tools can re-evaluate the path forward given the new state.

What we're building at HASH

At HASH, we're using Petri nets to coordinate multi-agent workflows that can be formally verified, supporting both correctness and efficiency objectives. As part of our approach to orchestrating agents and executing flows, Petri nets give us:

• →

  A visual representation of what agents are doing and why;

• →

  A versioned history of how plans evolved over time; and most importantly

• →

  Formal guarantees about safety properties (e.g. human approval as a pre-condition to deployment)

Petri nets alone won't solve every problem in agentic AI, but they are able to help us significantly improve oversight on agents and assurance on outputs.

If you're working on similar problems, we'd love to hear from you. Reach out via our contact form, message us on X, or check out our open roles.