Self-Programmed Execution for Language-Model Agents

arXiv:2605.06898 · cs.AI · Submitted 2026-05-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: Today's paper: "Self-Programmed Execution for Language-Model Agents".

Jane: As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to synthesize a comprehensive,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: The paper defines the SPE state x zero such that a model completion can load any embedded copy of the machine, meaning it’s subject to no fixed turn-to-turn orchestration policy >

Jane: And they prove this is true using Theorem two point five, which establishes that in a CEK-style evaluator utilizing model calls and evaluation, the seed program reaches such an SPE state x* >

Lu: The core contribution here is formalizing SPE using agentic machines, defining the agentic machine as a tuple X = (S, p, h), where S is a state space, p: S to P is a prompt function mapping states to prompts, and h: S times C to S one is a harness function mapping a state/completion pair to the next state > <ref:2605.06898#pg2>

Meng: That sounds like a lot of notation. How does that actually translate into something I can see when I'm looking at my code?

Tom: It’s just formal abstractions, but it proves that the machine operates exactly one LM call per state transition, and this is what defines the SPE architecture >

Jane: And they show that this structure is robust because they isolate the agentic machine from any outer agent loop, which is what makes it so clean >

Lu: They confirm that this structure encodes an SPE state and that a Universal Seed x zero exists from which every realizable agentic machine can be generated, which is Corollary A.twenty-one >

Meng: So the paper is saying the architecture itself isn't inherently flawed, it just needs the right language to express it properly >

Tom: That’s what they’re arguing. The harness evaluates this program but doesn't impose its own orchestration policy on top of it >

Jane: It means we aren't stuck with a fixed set of actions; the model can select any subsequent state rather than being constrained to prescribed actions >

Lu: That’s a huge theoretical win because it shifts the burden from external logic to self-generated logic >

The paper's summary: Tom: They introduce Spell as the Lisp-based language because it lets programs edit and re-evaluate themselves >

Jane: And that’s crucial because it means we can handle context persistence as code, which is a major headache when you have dynamic instructions >

Lu: Spell allows for prefix building, letting the LM construct a new prefix from scratch by selectively adding pieces of information >

Meng: So if I want to prune context, how do I tell the model what to remove? Does it require me to write specific commands?

Tom: They have subtraction or pruning methods where the LM can subtract unwanted pieces from its current completion to refine the context >

Jane: And they also have these effectful expressions for model invocations that are structured so that re-evaluating an edited program doesn't cause side effects to replay, which is a major concern for us >

Lu: The appendix mentions mechanisms like self-reference quines and double evaluation for effectful expressions >

Meng: That sounds like it adds complexity on top of the complexity we already have. I’m worried about the operational cost there.

Tom: It's about making sure that when you edit a program, the system remains deterministic and manageable rather than just letting things get chaotic >

Jane: And they also mention error recovery mechanisms like deterministic namespace fixup and trailing expression error recovery to handle failures in model-written programs >

Lu: These mechanisms let the model rewrite trailing expressions after an initial failure, which improves resilience >

Meng: So it’s about making the system robust enough to actually be deployed in a production environment, not just theoretical concepts >

The paper's improvements: Tom: The paper "Self-Programmed Execution for Language-Model Agents" shows that the key isn't just in the expressiveness of the orchestration policy itself, but in what entity is responsible for expressing it >

Jane: So, while SPE lets us express any computable orchestration policy, we see current models primarily using Spell for simple, practically useful tasks >

Lu: Future research should focus on training models natively to use Spell so that they can choose and express more sophisticated strategies themselves >

Meng: I still need to worry about the real-world cost of running this kind of system at scale, especially with those complex self-calls >

Lalam: I'm pretty sure that the framework is sound, and based on what I see in the literature, it's a solid foundation for future work >

Tom: Yeah, we’re going to keep pushing for models that can do this without needing all these added complexity >

Jane: It’s exciting stuff, but it’s important to remember that we need to stay focused on making sure the next step is practical and deployable >

Conclusion: Tom: So we've looked at how this paper, "Self-Programmed Execution for Language-Model Agents," formalizes SPE, which is essentially saying the model is its own program and it can pick any next step >

Jane: Right, so the core idea is that you take a language model and stop treating it like a fixed tool and start treating its output as executable code for the next action >

Lu: The formal stuff in Theorem two point five proves that this isn't just a fancy idea; it shows that in certain evaluation setups, the model can reach this state where it has no fixed orchestration policy >

Meng: But how does he make sure that when you let the model write its own code, it doesn't just start writing nonsense and break your system at scale >

Lalam: The Spell language they introduce is designed specifically to handle that; they’ve got mechanisms like self-calling so it can recursively build on its own logic >

Tom: And I like the idea of context management through prefix building and subtraction; it sounds like a direct way to control what information the model keeps around >

Jane: It's about giving the model tools to edit its own instructions, which is powerful because if it can prune unneeded stuff from its context window, that saves tokens >

Lu: They also addressed the issue of side effects when re-evaluating edited programs using specific structures for effectful expressions to keep the state deterministic >

Meng: Deterministic namespace fixup and trailing expression error recovery sounds like they are trying to build in some kind of self-healing for those model programs, which is what I need when deploying stuff >

Tom: So it's not just about making the model smarter; it's about giving it a controllable execution environment so we can actually ship these agents >

Jane: Exactly. The paper shows that current frontier models can already use Spell for simple tasks, but they aren't necessarily choosing the most complex orchestration games unless they are told to try them >

Lu: That suggests the real challenge isn't just having the capability, it’s training models natively to use this self-programming ability for complex strategy selection >

Meng: If we can get that training right, then we might see agents that handle really intricate multi-step workflows without us having to hand them a rigid plan >

Lalam: I'm confident the direction they're pointing toward is solid; the concept of SPE fundamentally shifts where the intelligence resides >

Tom: So yeah, "Self-Programmed Execution for Language-Model Agents" gives us a very clear blueprint for how to make language model agents truly autonomous in their execution >

Jane: It opens up a whole new door for how we design AI systems that can adapt their own plans on the fly >

Lu: And that leads us nicely into what some of the other papers are doing, like SEVerA, which focuses on verifying these self-evolving agents to ensure they don't just get weird >

Meng: Yeah, so if we can program the orchestration so well, then we need a way to verify that it actually does what it’s supposed to do when it’s running in the wild >

Lalam: We can look at how Composition-RL is trying to make sure those self-composed problems are still useful and aligned with our goals >

Tom: We'll keep digging into these agentic structures and see if we can get away from fixed orchestration policies entirely, that’s what this paper is all about >

Harvard Medical School

cs.AI

Submitted: 2026-05-07

Updated: 2026-10-15

Comments: Camera-ready version; accepted at NeurIPS 2026. 77 pages, including appendices and checklist

Code: https://github.com/lukejoconnor/spell

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 89/100

The gist: As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to synthesize a comprehensive, detailed summary of the paper "Self-Programmed Execution for

Key concepts

Self-Programmed Execution (SPE): SPE is an architecture where the language model's completion acts as the orchestrator program itself. Instead of following a fixed sequence of actions, the model generates code that dictates all subsequent steps, allowing it to load any successor state up to an embedding without external policy constraints.
Spell: Spell is a specialized Lisp dialect designed for self-programming. It enables programs to modify and re-evaluate themselves. Crucially, effectful expressions like model calls are structured so that re-evaluating the edited program does not cause side effects to replay, ensuring controlled execution.
SPE State: An SPE state is a condition where a model completion can load any possible successor state. This means the model is not locked into one path; it has the capability to select any valid next step based on its generated code, formalizing its ability to choose its own orchestration policy.

Terminology

Agentic Task — 1× in this paper
Agentic Tasks — 1× in this paper

Summary

As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to synthesize a comprehensive, detailed summary of the paper Self-Programmed Execution for Language-Model Agents. The goal is to create a single, authoritative description that captures both the theoretical framework (SPE) and the practical implementation details (Spell).

Here is the combined, detailed summary:

Comprehensive Research Summary: Self-Programmed Execution for Language-Model Agents (SPE & Spell)

This paper introduces Self-Programmed Execution (SPE), a novel agent architecture designed to fundamentally shift the role of the orchestrator program from a fixed external entity to the language model itself. In this paradigm, the model's completion is not merely an action but is the orchestrator program. The system is evaluated by a harness that assesses this self-generated program without imposing its own fixed turn-to-turn orchestration policy, formalizing SPE as a state where a model can select any subsequent state rather than being constrained to prescribed actions.

Core Concepts and Theoretical Foundation (SPE)

The central theoretical contribution is the formalization of SPE using agentic machines. An SPE state (x 0) is defined such that the model's completion can load any embedded copy of the machine, meaning it operates without a fixed orchestration policy governing turn transitions. This concept is rigorously proven by Theorem 2.5 (SPE), which establishes that in a CEK-style evaluator utilizing model calls and evaluation, the seed program reaches such an SPE state (x*).

The core philosophy underpinning this architecture is encapsulated in the design principles of Spell:

Orchestration is ordinary program logic: The orchestration policy itself is treated as executable code.
The completion is the program: The output generated by the language model is the operational code for the next step.
The model controls what its program does: The LLM dictates the flow of execution through its self-generated logic.

Implementation: Spell Language and Mechanism

To realize SPE in practice, a specialized Lisp-based language called Spell is introduced. Spell is engineered to handle the inherent challenges of making models self-programmers, specifically addressing context persistence as code, managing side effects during re-evaluation, and mitigating turn-boundary interference.

Key mechanics within Spell include:

Self-Calling: The core mechanism is the !llm-self function, which allows for recursive calls to the model completion. This enables continuous Chain-of-Thought (CoT) development and dynamic modification of the context window.
Context Management: Spell provides two high-level methods for managing accumulated state:

Prefix Building: The LM can construct a new prefix from scratch by selectively adding desired pieces of information.
Subtraction/Pruning: The LM can subtract unwanted pieces from its current completion to refine the context.

Effect Handling: Effectful expressions, such as model invocations, are structured so that re-evaluating an edited program does not cause side effects to replay, ensuring deterministic and manageable state transitions.

The appendix further details Spell's design principles, including mechanisms like self-reference quines and double evaluation for effectful expressions.

Empirical Validation and Observations

The paper provides significant empirical evidence demonstrating that frontier models can operate effectively in the SPE regime even when not specifically trained for it or Spell itself:

Observation 1: Strong existing models can successfully utilize Spell to solve challenging agentic tasks.
Observation 2: Current models leverage Spell primarily for practical context management and programmatic tool calling.
Observation 3: Complex orchestration games (e.g., Auction, Telephone, Twenty Questions) elicit nontrivial and sophisticated Spell programs from existing models.
Observation 4: While Spell is competitive on coding benchmarks, its performance is not uniform across all tasks.

Furthermore, the paper notes that current models tend to use Spell for relatively simple orchestration policies (context pruning, tool batching) rather than choosing complex orchestration games unless prompted to do so. The authors suggest that this behavior could change significantly if a model were natively trained to use Spell.

Architectural Formalization and System Integration

The appendix formalizes the sequential language-model agent at the boundary of model calls, treating the ambient evaluator as an abstract machine. This isolates the agentic machine, which records only the prompt exposed at a boundary, the completion returned by the model interface, and deterministic computation until divergence or halt. Crucially, it confirms that this structure—the CEK agentic evaluator—encodes an SPE state and that a Universal Seed (x 0) exists from which every realizable agentic machine can be generated (Corollary A.21).

System Integration and Benchmarking Details

Beyond the theoretical framework, the paper provides a detailed technical description of how Spell integrates into a larger system:

Runtime Components: The Spell runtime involves an evaluator (spell-eval), an execution wrapper (box), and a call mechanism (call-llm).
Configuration: Agents are configured using agent and provider EDN files, clearly separating the agent's configuration (what kind of Spell agent) from the provider's configuration (how it interacts with the LLM).
Transport Mechanisms: The system supports various transport methods for LLM interaction, including prefill transport, message transport, and tool-call transport.
Benchmarking: Extensive benchmarking is conducted comparing Spell against established agents like Codex CLI and Claude Code across demanding benchmarks such as Terminal-Bench 1.1, SWE-bench Lite, LongBench v2, and AppWorld dev. These comparisons analyze accuracy vs. cost (token usage) and sensitivity to budget caps across various models (e.g., GPT-5.4, Opus 4.6).

Conclusion and Future Directions

The paper concludes that the distinguishing feature of SPE is not the expressiveness of the orchestration policy itself, but what entity is responsible for expressing it. While SPE allows for the expression of any computable orchestration policy, current models primarily use Spell for simple, practically useful tasks. The authors strongly suggest that future research should focus on training models natively to use Spell, as this might unlock the potential to solve more complex agentic problems by allowing the model itself to choose and express sophisticated orchestration strategies.

Improvements for AI systems

No fixed orchestration policy: The improved AI system can operate without any fixed orchestration policy because the harness evaluates a model-written program which is solely responsible for orchestration, allowing the model to select successors freely, as formalized by Definition 2.3 of an SPE state.
Self-modifying execution: The system can write and edit its own orchestration logic using Spell, leveraging the property that the same data is both model context and executable program, which allows for a model completion itself to be the orchestrator program.
Programmatic context management: By utilizing Spell's mechanisms like '!peek (which combines !prune with !call-now), the system can manage its context window by pruning unneeded expressions, such as tool call results or long file contents, while retaining necessary information via 'persist'.
Error recovery and resilience: The system can recover from errors in model-written programs using deterministic namespace fixup and trailing expression error recovery, allowing the model to rewrite the trailing expression after an initial failure.
Programmable tool use and chaining: The system can execute complex workflows by chaining tool calls with '!call-now or '!peek, enabling it to perform operations like Search + read context in one turn or Chain tool calls with !call-now, saving turns.
Flexible agent orchestration: The system can implement novel orchestration strategies, such as the Auction, Telephone, and Twenty questions motifs, by writing model-specific self-calls in Spell, demonstrating that Spell supports flexible orchestration policies.

Abstract

At the heart of a language model agent is an orchestrator program which is responsible for the state transition between consecutive turns. In existing systems, this program is implemented in the harness. This paper introduces self-programmed execution (SPE), in which the model completion is itself the orchestrator program, and the harness evaluates this program but does not impose any fixed orchestration policy. Formally, an SPE state of an agentic machine is one from which a model completion can load any successor state up to an embedding, and an instance of an SPE state is one which executes the model completion as a program. In practice, the program requires a language with unusual features, as its source code doubles as the content of the model's context window. I therefore introduce Spell, a Lisp dialect in which programs can edit and re-evaluate themselves, and effectful expressions like model invocations are structured such that re-evaluating an edited program does not replay its side effects. Experiments with existing models, not trained for SPE or Spell, show that frontier models can learn Spell in-context and accomplish challenging agentic tasks. These results demonstrate how a LM can act as an agent without any fixed orchestration policy, and they raise the question of what self-orchestration strategies might be learned by a model trained for self-programmed execution. Code is available at https://github.com/lukejoconnor/spell.