Recursive State Machines for Language Models

Lately there’s been a lot of discourse around recursive language models (RLMs): the idea that the model sits inside a runtime, an IPython kernel, for example that can execute code and spawn further instances of the model. This works well for a couple of reasons. Each call starts with its own model context, session history, kernel, tools, state, and identity. LangChain’s deep agents team benchmarked this and found that RLMs start showing large performance gains over a regular harness at around 128k context tokens. Which, if you think about it, is far less than the context a real software engineering session consumes. Structurally this can be represented as a primary agent delegating to child agent sessions, which fan out into further child sessions.

What RLMs got right

The innovation is not “an agent that spawns agents.” That part is old. What Alex Zhang, Tim Kraska, and Omar Khattab changed is where the context lives. An RLM treats a long prompt as an environment rather than a window: the prompt becomes a variable in a REPL, and the model writes code to examine it, cut it up, and call itself over the pieces. The canonical llm.completion(prompt, model) becomes rlm.completion(prompt, model). That one substitution buys inputs two orders of magnitude past the context window and holds off context rot, because no single call has to carry everything.

The deeper move is that recursion became a call the model can make, not a pipeline somebody drew in advance. Depth follows the input. A short prompt never recurses; a huge one decomposes until the pieces fit. Nobody has to guess the shape of the work ahead of time, which is the part that never survives contact with a real repository.

Prime Agent: an RLM harness in practice

Prime Intellect’s Prime Agent is the clearest build of this so far. The kernel is the model’s only tool, and the model spawns children by calling await rlm("...") inside it. Each child gets its own model, kernel, and history, and parent and child message each other while the work runs. The harness also rewrites its own prompts, skills, memory, and sub-agents from what a run taught it. On ARC-AGI-3 it beats the native harnesses of the models it wraps, and spends fewer tokens doing it, because the model runs functions over data instead of reading data through tools.

What an RLM leaves open

Nothing in an RLM stops a subtree from drifting out of scope, burning tokens, or returning plausible slop that nothing verified. The recursion is real, but it is invisible to everything outside the model. A child returns text, and the parent believes it. There is no state to inspect, no transition to guard, and nothing to resume if the process dies halfway down the tree. We think the next evolution, the thing that makes this pattern usable for scalable coding systems, is the recursive state machine.

The finite state machine (FSM)

State machines are not a new idea. A finite state machine is a set of states and transitions. It’s one of the most stable abstractions in computing because you always know where you are, and every transition is explicitly defined. Write one down and you have written down everything it can ever do.

That is also its ceiling. An FSM has no call stack, so it cannot invoke another machine and come back to where it left off. It can loop, branch, and repeat, but it cannot make a procedure call. For work that decomposes into subtasks, and subtasks of those, that limit is fatal.

The recursive state machine (RSM)

In 2005, Alur, Benedikt, Etessami, Godefroid, Reps, and Yannakakis closed exactly that gap with the recursive state machine (RSM): a state machine whose states may invoke other component machines, with call-and-return semantics. You write a finite set of component machines. Some of their nodes are boxes, and a box stands for a call into another component — including itself. Enter the box and you enter that machine at its entry node; reach its exit node and you return to the box’s successor. That is the procedure call an FSM cannot express, added with one construct.

The consequence is the property this whole post rests on. An RSM’s definition is finite, but its execution unfolds into a tree of activations — as deep as the problem you’re solving requires.

That property is exactly what engineering tasks with coding agents fit well into. You need something that adapts dynamically, spawning sessions to fit the objective while staying controllable, so the task doesn’t leave its scope or run up inordinate cost, and above all so you can effectively verify the work. An RSM is finite to write and verify, and it expands at runtime to fit the work.

Atomic: an RSM runtime in practice

Beyond the theory, you can use an RSM and see how it works through Atomic, which maps to it like this:

A stage is an instance of the harness

Vivek Trivedy defines the harness as every piece of code, configuration, and execution logic that is not the model: agent equals model plus harness, and if you are not the model, you are the harness. So a stage wraps one unit of work in a full harness with its own prompt, tools, filesystem, sandbox, memory, permissions, and loop control.

It also has an explicit lifecycle: pending, running, awaiting input, paused, completed, or failed. Every transition is guarded and recorded, and the runtime validates each state change before appending it to the run’s history. A stage can drive a model session, run a deterministic tool, or wait on human input.

A graph of stages is a workflow. A workflow can call a child workflow, another graph of stages, like the zoomed view above, and the child can call further children. That call-and-return is where the recursion shows up.

Memory sits under the graph

Every transition between stages is checkpointed, including run and stage snapshots, model sessions, and artifacts. This is durable execution. If a run crashes, you resume it, and the runtime replays the workflow so that completed calls return their stored results instead of re-running. Their results are effectively memoized. The same holds one level up, where a completed child workflow returns its recorded outputs without re-running any of its stages.

Deterministic control around a nondeterministic model

This is why RSMs are so powerful for agent workflows. A model call is nondeterministic so the valuable move is making the control plane around your models deterministic. The model lives inside the stage, while the stage’s inputs, outputs, status, and transitions are explicit machine state. Verification is a state as well in which a verifier stage or deterministic gate must pass before the machine transitions to the next step. Retries are also new states with bounded counts. Human approval is just another state as well that the machine holds durably across restarts.

The result is finite and inspectable. Every state the run can enter was written down before it started, and every state it passed through is recorded after. The model still writes the code, and the code it writes is still a guess. What stops being a guess is everything around it.

The verifiable runtime

The machine is only worth building if you can check what it did. A runtime is where agents run: it owns the sessions, tools, models, and state, the way Node is the runtime for JavaScript. Verifiable means every claim comes with evidence you can read — real command output, test results, artifacts, checkpoints — instead of the model saying “done.” Together they make a verifiable runtime, where correctness comes from the system rather than from trusting the model. The runtime tracks every stage, runs every check as a real tool call, saves the result, and leaves a trail you can resume or replay.

The loop, named

The shape is a control loop, a framing we took from Dex Horthy and the HumanLayer team. Acceptance criteria set the target. The workflow policy picks the next move. The agent and its tools make the change. The codebase is what changes. Tests, types, lint, and independent review measure the result and hand the gap back to the policy, which then picks one of four outcomes: pass, repair, fail, or stop when the budget ends.

Output varies. Control stays explicit. You do not need every model response to be predictable. You need feedback and stop rules that live outside the model.

Propose, measure, review, decide

Inside the machine, that loop runs as four moves. The model proposes a change, and nothing yet treats it as correct. Atomic measures it with real checks through a deterministic tool primitive — tests, type checks, builds, browser flows, any command you can run — and saves each result like any other step.

A second kind of check sits underneath. TypeScript holds the declared contracts between stages at build time, and TypeBox checks structured results at run time, which catches missing fields, wrong types, and outputs nobody declared. Those checks prove the data looks right, not that the code works, so they sit beside the executable checks rather than replacing them.

Review runs in fresh sessions that get the changed files and the evidence but not the implementer’s conversation, and that gap is the only reason the review is worth reading. Then a reducer proposes an outcome under a bounded repair and review cap. The model gets a vote. The code decides.

What each stage is allowed to see

All of it is built from one small set of parts: tracked stages, saved checkpoints, tool calls, artifacts, gates, structured outputs, and human approval points. You combine them the way you combine functions, and each one leaves evidence.

Context is one of those parts. A fresh stage starts clean and sees only what you hand it. A fork carries on from an earlier conversation you choose, so a stage can repair its own work without deriving every earlier decision again. Stages pass work to each other through declared values, outputs, files, and reads, and those are the interfaces between them. When a session nears its limit, Atomic drops older messages and keeps the rest word for word, because a summary would lose the exact error text the next step needs.

Where verification stops and judgment starts

What the evidence does not cover

Verification gives you evidence. It does not prove the code is right, and saying that it does would be the same unchecked confidence we started out complaining about. Skip a human review only when the checks are cheap, objective, and hard to fake, which in practice means small, reversible work. Complex, unfamiliar, security-sensitive, or hard-to-undo changes still need a person.

Durable execution carries a matching limit: anything that retries can repeat an action. A tool files a ticket, the process dies before the result is saved, and the retry files a second one. Make outside actions safe to repeat — a key that dedupes, a check for what already exists, or a later pass that reconciles — because the engine will replay a step that already changed the world.

Someone still has to sign

So a person stays in the loop, just not the inner one. You read run status, stage detail, and transcripts. You steer with send, pause, interrupt, and resume. A paused branch survives a restart, because a pause is a state and not a stopped process. Addy Osmani calls this owning the outer loop: agents run the inner loop while people keep intent, constraints, evidence, approval, and consequences.

He draws a sharper line elsewhere, and it is the one that matters here. Taste can be borrowed, copied, or learned from an agent. Judgment cannot, because judgment “is insisting on your name attached to the consequences,” and agents do not have names. Models will keep getting better at ranking options. Someone still has to sign.

That is what all the evidence is for: a signature is worth what the evidence behind it is worth, so the runtime’s job is to make the proof cheap to produce and hard to fake. Putting the recursion in the execution layer does not remove human judgment. It moves that judgment into the design of the machine, and leaves an obvious place to step in.

The recursion belongs in the execution layer

Which brings us back to where we started. Other systems, Prime Agent among them, put the recursive fan-out in the model: the model calls models over slices of its own context. That is a valuable technique, and Atomic uses it inside a stage where a slice of context really is the right unit. We took the same idea up one layer, to the part that owns sessions, tools, checkpoints, and state, and we shaped that layer as a recursive state machine. The unit of recursion stops being a piece of a prompt and becomes a stage. The call stops being a nested completion and becomes a child workflow with an entry, an exit, and a return.

What moving it changes

Moving it changes five things, and none of them are cosmetic.

• Scope stops depending on the model’s judgment. A box has one entry and one exit, so a subtree returns to its call site or it fails, and depth is bounded by a definition you can read.
• Verification becomes possible at all, because a return is now a transition, and a transition can be guarded. In an RLM the child hands back text and the parent has no way to disagree.
• Cost becomes countable, because every activation is a tracked node, so fan-out can be capped per level instead of discovered on the invoice.
• Memory arrives for free, because a call that is a machine transition is a call you can checkpoint. Resume replays completed calls rather than re-running them, and a finished child workflow returns its recorded outputs without touching a model.
• Control becomes a state, so a pause or an approval survives a restart instead of dying with the process.

That is what makes it scale rather than just recurse. A refactor across three files and a migration across three hundred run the same definition; the second one simply unfolds further, with more fan-out, more verify–repair rounds, and deeper child calls. The machine grows to fit the task while the thing you wrote, reviewed, and can reason about stays the same size. Recursion in the model made long context tractable. Recursion in the runtime makes long work tractable, which is the problem an engineering system actually has.

Where this goes

You can imagine a future in which machines like this fan out and delegate to even larger scopes of work with verification, durability, and alignment built in. A world where workflows run for days or weeks at a time while the human steers and oversees, without sacrificing accuracy or quality. We’re not fully there yet, and it will take many more innovations. RSMs are just one piece but within Atomic we’re laying the early foundations, rooted in practical engineering and deep technical research.

None of this is hypothetical. Atomic is fully open source and self-documented, meaning you can ask it how it works and it will tell you exactly how it was built. We hope you learn something useful here and that it inspires more building.

We question, break away from what is accepted. Engineering matters.

References

• Rajeev Alur, Michael Benedikt, Kousha Etessami, Patrice Godefroid, Thomas Reps, and Mihalis Yannakakis, “Analysis of Recursive State Machines” — ACM Transactions on Programming Languages and Systems 27(4), July 2005 (PDF)
• Alex L. Zhang, Tim Kraska, and Omar Khattab, “Recursive Language Models” — arXiv:2512.24601 (project page)
• Prime Intellect, “Prime Agent: A self-improving RLM agent” — Prime Intellect Blog
• LangChain, “How to Use RLMs in Deep Agents” — LangChain Blog
• Dex Horthy, “Advanced Context Engineering for Coding Agents” — HumanLayer
• Addy Osmani, “Own the Outer Loop” — addyosmani.com
• Addy Osmani on taste and judgment — “Taste can be borrowed, copied, derived from others, learned from agents… but judgment cannot be transferred.”
• Vivek Trivedy, “The Anatomy of an Agent Harness” — vtrivedy.com
• Atomic — the open-source verifiable coding agent runtime described here