Recursive state machines and coding agent execution

“Recursive state machine” is a precise term from program analysis that is increasingly borrowed to describe how coding agents execute. The borrowing is a useful lens, and it is not an implementation claim; the two get confused often enough to be worth separating carefully. This guide defines the formal models in ordinary English, compares them, and then states what Atomic’s runtime materializes and validates today, with every behavioral claim pinned to one commit of the open-source repository.

Four models, defined plainly

These four terms are routinely used as if they were interchangeable. They are not. Each answers a different question: what can this machine express, where does its recursion live, and what can you inspect while it runs?

Finite state machine

A finite state machine has a fixed, finite set of states connected by labelled transitions. One state can encode several bounded facts at once — for example, a parser mode together with one of three fixed return labels — so bounded call-and-return behavior can be compiled into a larger finite state set. The constraint appears when the number of pending returns must grow with the input. Encoding every possible chain would require infinitely many states, which is outside the finite-state model. A recursive state machine adds a finite component interface while allowing an execution to retain an unbounded stack of pending calls.

Recursive state machine

The construction that supplies the missing mechanism is set out in “Analysis of Recursive State Machines” by Alur et al., published in ACM Transactions on Programming Languages and Systems (volume 27, issue 4, 2005; DOI 10.1145/1075382.1075387). An RSM is a finite family of component machines. Alongside plain nodes, a component may hold boxes, and a labelling gives each box the index of the component it invokes — possibly the very component holding it.

Every component publishes two sets: a set of entry nodes and a set of exit nodes. Neither set has to be a singleton. The paper’s own worked example gives its first component two entry nodes, and its results tables treat single-entry and single-exit machines as restricted subclasses that happen to admit cheaper analysis. Those two sets form what the paper calls the component’s control interface, glossing entry nodes as arguments and exit nodes as returned values. Pairing a box with one of the invoked component’s entry or exit nodes yields what the paper terms a port, and ports are vertices of the calling component rather than of the callee. An edge inside the caller therefore runs to an entry port — that box paired with one entry node of the component it invokes, a call vertex. When the invoked component reaches one of its exit nodes, control resumes in the caller at the matching exit port, the same box paired with that exit node, a return vertex, and the caller’s own outgoing edges continue from there. The written diagram stays finite while one execution stacks boxes as deep as the input warrants. Expressive power coincides with pushdown systems, which is precisely why the model is studied: reachability and cycle detection stay decidable.

Recursive language model

Zhang, Kraska, and Khattab put forward recursive language models (arXiv preprint 2512.24601) as an inference-time paradigm, and its defining move concerns storage rather than orchestration. A long prompt is placed in an external programming environment as a variable instead of being pushed through the network in one pass. The root model writes code that measures and cuts that variable, then issues sub-queries against the fragments its own code selected. Depth is a dial the implementer turns, not a constant the paradigm supplies: the paper sweeps maximum recursion depths from zero through three across two model families, treats depth one as the default when a run does not say otherwise, and finds that going deeper is not uniformly better, because for one of those families the root model’s syntax errors propagate into its sub-calls and average scores fall as depth rises. Its limitations section calls the best mechanisms for building guardrails around recursive language models highly under-explored, and leaves runaway sub-call cost as an unsolved problem for later work.

What the paradigm specifies is deliberately thin. An RLM presents the same external interface as a plain model — a string prompt in, a string response out — and says nothing at all about persisting the work behind that interface. Execution records, guarded transitions, spend caps, depth limits, and recovery after a crash are all things a harness may supply, and the authors’ own reference implementation keeps a persistent REPL whose trajectories they inspect. Those are engineering decisions taken around the paradigm, not properties it hands you. The contrast that matters for the rest of this guide is a narrow one: recursion during inference and durable, guarded execution state are separate concerns, and a system that wants the second has to build it on purpose.

Workflow execution graph

Atomic’s unit is neither a declared state nor a nested completion. A workflow definition is an ordinary TypeScript module whose run function calls tracked primitives. As that function executes, the runtime records nodes and parent edges and builds a directed acyclic graph of the work that actually happened. Nothing is drawn in advance, and nothing is submitted to a planner. The graph is a record of execution order that the runtime then validates and persists.

How the four models compare

Why explicit execution state matters for long work

The argument for holding execution state outside the model is practical rather than aesthetic. Picture an operator six hours into a repository-wide migration, checking on a run nobody watched. Three things decide whether that run is manageable: a record of what happened, a limit something can actually enforce, and a defensible answer to whether the run may go on.

A record. Say a subtask reports that it converted forty call sites. Delivered as prose inside a conversation, that report can be believed or discarded and offers nothing to attach a check to. Delivered as a transition between tracked nodes, with the diff and the test output addressed to it, it can carry a gate on the transition and can be re-read later by somebody who was not there. “Done” becomes a recorded status carrying artifacts instead of a sentence carrying confidence, and that shift belongs to the execution layer rather than to the model, which is the same model either way.

A limit. A bound is only real if something enforces it, and enforcement is available at more than one layer. The recursive-language-model paper’s own harness makes the point: reach its configured maximum recursion depth and the sub-call function is substituted for a plain model call, in code, with nothing left to the model’s discretion. Atomic applies a separate pre-start check: it compares the supplied workflow depth with the configured maximum and returns a failed result carrying atomic-workflows: maxDepth exceeded (max N) before recording the deeper run’s start. Both are real limits. They differ in where the check runs and what result it produces.

An answer about continuing. “Resume” is a request a runtime ought to be allowed to refuse, and refusing it means knowing the run’s real condition. Atomic reads that condition off the record instead of trusting the request: a workflow still executing is never a valid target, since dispatching it twice is worse than declining, and a run whose heartbeat has gone stale is reported as crashed rather than offered as available. Both answers come from stored run state, which is not the same place as the run’s own account of itself.

None of this requires the formal recursive state machine model, and Atomic does not implement it. What it requires is that the execution layer, rather than a model’s context window, owns the nodes, the edges, and the transitions between them.

What Atomic implements today

Everything in this section is checked against commit cf95cb7 of bastani-inc/atomic, dated 18 August 2026. Upstream moves quickly; treat the links as a dated snapshot and the workflow documentation as the current source of truth.

The graph is inferred from execution order, not declared

Atomic does not ask an author to enumerate nodes and edges. A frontier tracker infers parents from JavaScript execution order: when a node spawns, the current frontier is snapshotted as its parents; when a node settles, its parents leave the frontier and the node joins it. Edges therefore only ever point backward in settle order, which makes the recorded topology acyclic by construction rather than by a later repair pass.

Source: frontier inference algorithm · dynamic topology guidance

Cycles are rejected by code, on execution, replay, and hydration

Because definitions are dynamic TypeScript, neither the type system nor workflow discovery can prove acyclicity ahead of time; discovery loads the module and checks its exports, schemas, and run function, but it does not compile run into a complete graph. The runtime therefore treats topology checks as the authoritative boundary. A depth-first cycle check runs over merged child topology and returns direct child stage topology contains a cycle before any cache, control target, or child dispatch is exposed, and a boundary that lists itself among its own parents is refused outright. The same validation applies when durable state is restored, so malformed persisted topology cannot slip past on resume.

Source: cycle detection · self-parent rejection · runtime and replay as the authoritative boundary

Loops unroll into distinct tracked iterations

A repair loop is the obvious place a back edge would appear, and it is exactly where Atomic forbids one. An implement, review, validate, repair sequence must not point repair back at the existing implement node. Instead each pass creates new tracked nodes — review 1, validate 1, repair 1, review 2 — with stable per-iteration identity and call order so resume and replay reconstruct the same shape. A regression test builds a bounded loop, asserts three distinct boundary stage identifiers and child run identifiers survive hydration, then makes one stage its own ancestor and asserts the validator still reports a cycle.

Source: worked unrolled-loop example · hydration and mutation probe

Nesting is bounded by a number you can read

Two independent limits apply. Workflow composition goes through ctx.workflow(childDefinition, options) boundaries, and nested child workflows count against a configured maximum depth that defaults to four total workflow levels; exceeding it returns a failed run carrying the exact message atomic-workflows: maxDepth exceeded (max N), with tests pinning behavior on both sides of the boundary. Subagent delegation is guarded separately, with a hard maximum of five delegated levels and an admitted policy that may choose any value from zero to five; deeper admission is refused rather than inherited from process state. Calling a child definition’s run function directly is not the composition path and is documented as something authors and agents must not do.

Source: depth enforcement · boundary tests · subagent recursion guard · composition boundary rule

Status is an enumeration, and transitions are conditional

A stage carries one of eight statuses: pending, running, awaiting input, paused, blocked, completed, failed, or skipped. A run and a durable tool node each carry their own separate enumerations. Status changes are compare-and-set against the expected prior status, and terminal states are absorbing, so a stale writer cannot reopen a finished generation. That is the difference between a status field and a lifecycle.

Source: status enumerations

From an execution graph to a checkable process

Explicit execution state earns its cost only if it lowers the price of checking the work. Four moves carry a recorded graph to a process an auditor can follow.

1. Generate. A model stage emits a candidate change. At that moment the change has a node and an author, and no standing beyond those two facts.
2. Evidence. Checks run through the durable tool primitive, which allocates a tracked graph node before the callback executes and stores the serializable result keyed by call order together with a content hash of the name and arguments. A suite run, a compiler pass, a bundle, a browser flow: each lands as a node with retained output rather than as a claim inside a transcript.
3. Judgement. Independence here is a setting with declared visibility, not a virtue. Atomic’s guidance assigns reviewers, guards, and judges context: "fresh", whose stated view is the contract, the candidate, the decision artifacts, and the files as they now stand; context: "fork" is reserved for implementation, debugging, and repair roles that need continuity with an earlier session they own. The prohibitions are equally explicit: do not fork a guard from the worker it judges, and never let a guard watch itself.
4. Disposition. Plain TypeScript folds structured reviewer results into approve, repair, block, or escalate under a bounded iteration cap. Atomic’s guidance is to read schema-typed decision fields instead of pattern-matching free-form prose, and to gate on real tool results instead of a model’s account of them.

Verification supplies evidence and gates. It is not proof that the change is right or safe, and reading a green gate as proof restores exactly the unexamined trust the structure was built to remove. The verification guide covers contracts, artifacts, reviewer independence, retries, and escalation in depth.

Source: durable tool primitive · evaluation and quality gates

Durable execution and repeat-safe side effects

Checkpointing has a boundary, and the boundary is the interesting part. Tracked ctx.* operations are checkpointed; the ordinary TypeScript sitting between them is not. Inside that boundary a resumed run serves a settled call from its stored result — a durable tool node is keyed by its call ordinal together with a content hash of its name and arguments — and a child workflow that already finished hands back its declared outputs from the record, with no model invoked to produce them a second time.

The price of that reuse is that anything replayable can run a second time, and identity decides whether it does. A durable tool node’s key folds in more than the call itself: repeated calls carrying identical arguments are separated by an occurrence counter kept per key, and when a call is configured to hand back its failures rather than throw them, that setting is hashed into the identity too, so flipping it yields a different node with no stored result to serve. Cancellation writes no replayable checkpoint, so the cancelled call runs again under the same identity once the run resumes. Exhausted callback failures then split by mode: the default throwing path stores an inspection-only failure record that replay lookup excludes, so a resume or rerun invokes the callback again; failureMode: "return" stores the typed failed outcome in a replayable checkpoint, so replay returns that same outcome with cached: true. An operation whose effect lands somewhere the runtime does not control therefore has to be built repeat-safe.

Durability is also conditional on a backend. Atomic uses DBOS on Postgres, provisioning an embedded local cluster when no connection string is supplied. If no durable backend can be provisioned at all, workflows still run but degrade to a process-local in-memory backend with a loud warning, and a later resume has nothing to restore.

Source: checkpoint scope · replay identity · cancellation and replay · backend degradation

Human input, pauses, and what survives a restart

Human input in Atomic is a runtime call rather than a declaration. A workflow definition does not declare where a person will be asked something; runtime ctx.ui.* calls create awaiting-input nodes that appear in the graph, including when the prompt lives inside an imported child workflow. Answering one resumes the run internally and deliberately does not wake the model, because a notice for every internal transition would defeat the decision that paused the work.

Quitting a run closes tool admission, aborts the outstanding set, and only then records the durable paused transition and marks the run resumable — so the pause outlives the process. Two guards keep that honest: a workflow that is currently running is never a resume target, since resuming it would dispatch it twice, and a stale heartbeat surfaces as crashed rather than as available. Post-mortem chat about a finished run is inspection only; it never resumes, retries, or rewinds execution.

Raw answers to prompts are held in a private in-memory ledger and are never written to snapshots or persistence, so a replayed run may re-ask rather than reuse an answer it no longer holds.

Source: runtime-only human input · resume guards

Further reading

The field note linked above, “Recursive State Machines for Language Models” on the Mixture of Experts Blog, is the deeper reading for the conceptual argument. It is an opinionated account rather than API documentation: it supplies the motivation and the diagrams, while the implementation boundaries are the ones stated on this page and in the maintained documentation. Where the two differ on a detail, prefer the source.

For primary references, read the recursive state machines paper for the formal model and the recursive language models paper for the inference-time technique. For Atomic itself, the runtime explainer covers how workflow graphs execute, coding agent workflows covers workflow design, the TypeScript SDK guide covers the authoring surface, and the built-in workflow examples compare shipped control and review shapes. The resources index collects documentation, source, and field notes in one place.