Token-based replay

What is token-based replay?

Token-based replay is a process mining technique that plays a recorded process trace back on a Petri net, one activity at a time. Each activity in the trace tries to fire the matching transition in the model, and the technique keeps a running tally of what happens.

A Petri net uses places, transitions, and tokens to represent process behaviour. A transition can only fire when the required tokens are present in its input places. When it fires, it consumes tokens from those places and produces new ones in its output places, following the arcs in the model.

If a recorded activity cannot fire because the tokens it needs are not there, the algorithm inserts the missing tokens so the case can carry on. If tokens are left behind in places where they do not belong once the case ends, it counts those as remaining. That bookkeeping is a quick signal of where the log and the model disagree.

A simple example

Take a model for an order: receive, check, approve, and ship. The trace receive, check, approve, ship runs through cleanly, with no repair steps needed.

Now take the trace receive, approve, ship, which is missing the check step. If approve needs a token that only the check step produces, that transition cannot fire normally. Replay inserts a token so the case can continue and records the shortfall as a deviation.

A trace that stops after approve can leave tokens behind, because the model never reached its expected end state. The result tells you that model and observation do not fully match, but on its own it does not yet explain why.

The token bookkeeping

A common replay keeps four counts: produced tokens, consumed tokens, missing tokens, and remaining tokens. A perfectly fitting trace has no artificially added tokens and none left stranded at the end.

From those four counts you can compute a replay fitness. It is 1 minus the average of two ratios: missing over consumed, and remaining over produced. Report the exact formula and how the start and end markings are handled, because implementations differ on those details and the numbers will not line up otherwise.

The method can show results per trace, per activity, or per place. That is what lets you see, for instance, that a particular control is often skipped, or that cases regularly stop before the final step.

Token-based replay versus alignment

Token-based replay repairs the case locally whenever a transition cannot fire. It is usually fast and gives you readable diagnostics, but the repair path it finds is not necessarily the smallest overall deviation.

An alignment instead searches for an optimal synchronisation between the trace and the model. It separates moves in the log from moves in the model and minimises a configured cost, so it tends to give a more precise explanation at the level of individual activities. The trade-off is compute: alignments ask for more time and memory.

For a first scan of large event logs, replay is often the practical choice. For formal compliance analysis or a precise location of deviations, an alignment can be the better fit.

Handling choices and parallelism

Petri nets can contain choice paths, loops, silent transitions, and parallel activities. Replay then has to decide which enabled transition or hidden route best matches the next events, and that decision is not always obvious.

Duplicate activity labels make it harder still: one logged activity can correspond to several transitions, and a careless mapping makes the outcome arbitrary. Record how you handle labels, lifecycle transitions, and silent transitions before you trust the totals.

The order of events that share a timestamp deserves the same care. An apparent deviation can come from a source that only stores dates or minutes, while the activities really ran in parallel or in a different order than the sort suggests.

What to watch out for with token-based replay

Many missing tokens can mean skipped steps, incomplete logging, or a model that describes the real process too strictly. Remaining tokens can point to cases that were cut off, missing end events, or a wrongly defined end marking. The counts tell you where to look, not what to conclude.

A high fitness does not prove a model is good. A model that allows almost any behaviour can replay every trace and still explain very little, so read fitness together with precision, simplicity, and usefulness. Replay also does not flag a violation on its own, since a deviation can be permitted exception handling. Knowledge of the process and the policy behind it decides what the numbers mean.

In practice, check the case id, the activity mapping, the timestamps, and the start and end criteria first. Replay a small sample by hand before you rely on aggregated scores, and always tie the standout patterns back to the source data and the people who own the process.