PaperlayerView exact revision on arXiv

Source-linked AI summary

LACUNA: Safe Agents as Recursive Program Holes

Yaoyu Zhao, Yichen Xu, Oliver Bračevac, Cao Nguyen Pham, Frank Zhengqing Wu, Martin Odersky

arXiv:2605.28617v1cs.AIcs.PL

TL;DR

LLM agents traditionally separate model-written actions from the runtime’s loop and context, limiting expressiveness while amplifying safety risks when generated code controls execution. LACUNA makes actions typed runtime holes checked in their live lexical context, enabling ordinary code composition with whole-action rejection and scoped authority. Across verifier tests and benchmarks, it functions as a drop-in agent, including 27.1% BrowseComp-Plus accuracy and 76.0% of 392 τ^2-bench tasks, while semantic correctness and capability provisioning remain limitations.

  • Problem

    Existing code-as-action agents leave the runtime’s loop, context, and control flow outside model-written code, while letting generated code shape runtime execution increases the reach of errors and attacks.

  • Method

    LACUNA represents each agent action as agent[T](task), has the model generate code at runtime, and typechecks it against the surrounding lexical context before execution.

  • Results

    LACUNA serves as a drop-in agent across verifier cases, BrowseComp-Plus, and τ^2-bench, with 27.1% BrowseComp-Plus accuracy and 76.0% of 392 τ^2-bench tasks solved.

  • Takeaways & Limitations

    Whole-action checking prevents ill-typed or out-of-scope actions from running while ordinary generated control flow expresses common agent patterns.

  • Takeaways & Limitations

    Static typing checks action shape and authority, not semantic correctness, and capability protection is only as tight as the scope granted to each hole.

Abstract

from arXiv · show

LLM agents increasingly act by writing code, yet a split persists between the runtime that drives the agent and the code the model writes. The runtime owns the loop, context, and control flow, and the model has little say over any of them. Letting model-written code shape the runtime itself would make agents more expressive, but it would also sharpen safety problems. A model can be diverted by a prompt injection, call the wrong tool, or fail partway and leave an inconsistent state, and each such failure reaches further when the code shapes the runtime than when it expresses a single action. We present LACUNA, a programming model for agents that closes this split while preserving safety. Each agent action is a typed call $\texttt{agent[T](task)}$ that the LLM fills with code when execution reaches it, and the code is type-checked against the surrounding program before it runs. Because each action is accepted or rejected as a whole, a rejected one leaves the environment untouched, and its compiler diagnostics drive a retry. The same check also bounds which tools and data an action may use and how they flow. Our primitive expresses ReAct loops, sub-agents, skills, parallel decomposition, and multi-model planning as ordinary control flow. We evaluate LACUNA on a collection of test cases, BrowseComp-Plus, and $τ^2$-bench. On BrowseComp-Plus, $8.6\%$ of generations are rejected before execution, with 0.7 retries per query on average, and the agent reaches $27.1\%$ accuracy. On $τ^2$-bench, LACUNA solves $76.0\%$ of $392$ tasks across four domains with a capable model, on par with the baseline agent.

1 Introduction

LACUNA makes model-written agent actions part of the runtime by filling typed holes with code checked in the surrounding context before execution. This closes the runtime–model split while retaining whole-action rejection, permission bounds, retries, and ordinary control-flow composition.

  • Motivation and contribution: LACUNA places the model call inside the program, where the LLM fills each typed agent action with code checked at the call site.The generated code runs as part of the agent’s own runtime.
  • Typed holes: The runtime compiles generated code against the surrounding program, allowing it to use variables, functions, and tools visible at that point.The expected result type determines whether the snippet is accepted; compiler errors drive retries.
  • Safety: Rejected snippets leave the environment unchanged, while compiler checks catch missing tools, malformed arguments, and incorrect result types before execution.The same checks constrain tool and data access and their flow.
  • Programming model: Nested calls and ordinary code express ReAct loops, skills, sub-agents, and multi-model planning as standard program control flow.Recursive calls receive their own result types and can branch, loop, or route work across models.
  • Evaluation: LACUNA is realized in Scala 3 and evaluated on verifier cases, BrowseComp-Plus, and τ^2-bench, including retry behavior from compiler diagnostics.The evaluation spans both safety-oriented test cases and agent benchmarks.

2 Related Work

Prior systems either execute generated code without pre-checking or constrain model outputs while leaving workflow composition to developers. LACUNA instead typechecks generated host-language programs in their live lexical scope and uses those programs to compose agent behavior.

  • Recursive code generation: Recursive language models execute generated code without checking it first, so failures can occur partway through and leave the environment inconsistent.LACUNA addresses this with pre-execution host-compiler checking.
  • Language-integrated frameworks: LMQL constrains generated strings and DSPy uses typed call signatures, but developers compose larger workflows manually in fixed code.Their constraints focus on model inputs and outputs rather than runtime-generated control flow.
  • LACUNA: LACUNA emits a host-language program, typechecks it against the expected type and lexical scope, and feeds compiler diagnostics back for retries.It neither constrains sampling nor parses the model output into fields.
  • Typed-hole distinction: Unlike edit-time typed-hole completion, LACUNA fills recursive runtime actions against live context and executes them in the same process.The runtime setting makes the generated code dynamically dependent on current program state.

3 LACUNA: Typed Holes as Agents

LACUNA exposes agent[T](task) as a runtime typed hole: the model generates Scala code in the live lexical context, and the compiler accepts it only if it produces T. Nested holes make decomposition and recovery ordinary program behavior.

  • Typed holes: agent[T](task) asks the model for code that produces expected type T from a natural-language task.The snippet is compiled as though written at the call site and runs only after passing the host compiler’s checks.
  • Generated programs: Generated code can use in-scope variables, functions, control flow, tools, and local definitions rather than emitting only a single tool call.Tools are ordinary functions whose calls are typechecked without a separate registry or protocol layer.
  • Type contracts: The expected result type constrains what the model can return, with richer types imposing tighter contracts on generated code.Examples include List[Int], algebraic data types, and function types.
  • Nested calls: Nested agent calls receive their own task and result type, enabling sequential or parallel decomposition with progressively richer context.Outer snippets can introduce intermediate values, comments, and control-flow structure that nested calls can use.
  • Termination: Nested recursion has no static depth bound, so the runtime tracks call depth and exposes a configurable cap for cost or latency control.Hitting the cap causes the offending call to fail.
  • Retries and failure: Each call retries after compiler diagnostics, up to a configurable budget, and can instead return diagnostics through agentSafe[T].Failure is appropriate when the requested network access or return shape is unavailable in the surrounding context.

4 Safety

LACUNA applies the host compiler to model-generated snippets in their original lexical context, enforcing name, type, capability, and information-flow constraints before execution. This yields whole-snippet atomicity and scoped authority, while leaving semantic correctness and capability provisioning as boundaries.

  • Static guarantees: Model-generated snippets are checked by the host compiler in the original lexical context before any code runs.The same compiler rules govern names, result types, exhaustiveness, nullability, effects, and information flow.
  • Static guarantees: Undefined names, wrong argument types, and invalid constructors are rejected before execution rather than discovered after partial effects.Compiler diagnostics identify the offending binding or type mismatch.
  • Atomicity: Atomicity ensures that if any statement fails checking, earlier side effects in the snippet never execute.This prevents the inconsistent state that runtime-only checking can leave behind.
  • Capability safety: Capture checking treats lexical scope as the permission set, constraining which capabilities and data generated code may access or carry onward.Capabilities are ordinary unforgeable values, and information-flow constraints apply to generated code and the surrounding program.
  • Information flow: Nested runtime generation can adapt processing to protected content while capture checking prevents effectful content from leaking outside its pure scope.A local model can generate code with the content in view without granting the hosted model access to it.
  • Boundaries: Reflection and raw process execution remain ambient-authority escape routes unless the host’s safe mode or deployment controls address them.These mechanisms can reach members or external processes without an explicit capability.

5 Modeling Agent Patterns with LACUNA

LACUNA expresses common agent patterns through ordinary control flow over typed agent holes. Skills combine fixed, compiler-checked interfaces with bodies that can adapt through generated code and nested agent calls.

  • Typed Skills: Skills occupy a middle ground between unenforceable text guides and fixed code by combining procedural guarantees with per-call adaptability.Text-based skills can be skipped or deviated from, whereas fixed code cannot adapt to new situations.
  • Typed Skills: Typed skills fix and check their signatures while allowing generated bodies to mix ordinary code with nested agent calls.
  • Self-Improvement: Self-improvement updates a skill library by shadowing an existing function with a newly emitted definition of the same name and signature.Later agent calls resolve to the updated version in a long-running REPL session.
  • ReAct Loops: ReAct loops become tail-recursive agent calls that repeatedly emit tool-using snippets until the surrounding scope contains enough information to return the expected result type.Each recursive call preserves the same expected return type T while accumulating context.
  • Other Patterns: Sub-agents with isolated context, parallel reasoning, and multi-model task assignment follow the same control-flow recipe.

6 Realization in Scala 3

LACUNA realizes runtime code generation in Scala 3 by recompiling model-written snippets within their live lexical context. Reusing the host compiler preserves typing and capability checks before generated code executes.

  • Why eval is Hard: The central challenge is evaluating runtime-generated strings inside a statically typed host while preserving static guarantees.Static languages normally lose compiler bindings by runtime, so the inner compilation must reconstruct the original context.
  • eval: LACUNA’s eval[T](source) type-checks source against T and call-site scope, with the compiler supplying bindings, expectedType, and enclosingSource.
  • Agent Wrappers: agent[T](task) and agentSafe[T] wrap eval by sending prompts and captured context to an LLM, compiling returned Scala, and retrying with compiler diagnostics after failure.
  • Runtime Transformation: Runtime transformation proceeds through rewrite, splice, recompile, extract, and evaluation in the original execution context.The fresh compilation uses the same typing, capture-checking, and error-reporting options as the original compiler.
  • Safety Preservation: Reusing the unmodified compiler applies the surrounding program’s safety properties to generated code embedded at the correct call site.
  • Portability: The prototype depends on Scala-specific capture checking and in-process recompilation, but the design could transfer to typed hosts with analogous capabilities and runtime recompilation.

7 Evaluation

LACUNA’s verifier passes its standalone tests and supports complex single-turn and multi-turn tool use. It preserves pre-execution safety while achieving 27.1% BrowseComp-Plus accuracy and solving 76.0% of 392 τ 2-bench tasks with a capable model.

  • Type-System Protection: All roughly 400 verifier cases pass, including well-formed snippets that evaluate correctly and ill-formed snippets rejected before execution.
  • Complex Tool-Using Benchmark: 27.1% accuracy is achieved on BrowseComp-Plus by deepseek-v4-flash while driving 5.9 research rounds and 15.5 searches per query.gemini-3.1-flash-lite reaches 26.2% under the same benchmark setup.
  • Complex Tool-Using Benchmark: 8.6% of BrowseComp-Plus generations are rejected before execution, with 0.7 retries per query and a 91.4% end-to-end compile-success rate.Rejected snippets do not reach the corpus.
  • Multi-Turn Conversation Benchmark: 76.0% of 392 τ 2-bench tasks are solved across four domains, ranging from 58.8% on retail to 88.6% on telecom, on par with the reference tool-calling agent.
  • Multi-Turn Conversation Benchmark: 22.4% of deepseek-v4-flash’s retail generations are rejected on τ 2-bench, versus 8.6% on BrowseComp-Plus.The paper attributes the higher rejection rate to combining parsed tool results, prior-turn state, and policy-conditioned actions.
  • Scope and Outlook: The study expects prompt optimization or fine-tuning for typed agent code to improve solve rate and first-try compile success.

8 Discussion and Future Work

LACUNA is presented as a flexible, safer foundation rather than a replacement for existing agent architectures. The paper also identifies refinement-typed holes as a future direction for constraining result properties beyond shape.

  • A foundation, not a replacement: LACUNA can serve as a foundation for existing architectures, while specialized harnesses may remain useful for tasks such as efficient long-conversation history management.Agent calls can still provide type- or capability-safe behavior where needed.
  • A foundation, not a replacement: Nested calls and ordinary control flow support common agent patterns, including ReAct loops, skills, and multi-model planning.
  • Future work: Refinement-typed holes could constrain generated results by properties such as bounds, fixed lengths, or relational invariants, not only by result shape.The paper suggests discharging such predicates with verifiers such as Lean or Stainless.

9 Conclusion

LACUNA makes an agent action a typed hole filled with code in the host program’s lexical context. Its type and capability checks support compositional agent behavior while preventing rejected snippets from executing.

  • agent[T](task) treats an agent action as a typed hole whose generated code is compiled against T in the original lexical context.
  • Recursion and composition over the primitive express tools, typed skills, ReAct loops, and multi-model planning as ordinary control flow.
  • Rejected snippets never run, while the type system enforces scope and result-shape constraints on generated actions.

Limitations

The main limitations concern semantic correctness, capability scoping, model coding ability, latency, host-language requirements, and termination or resource budgets.

  • Correctness: Static typing checks result shape and authority, but not whether a generated snippet implements the right algorithm or uses the right in-scope tool.Human review or test oracles remain necessary for semantic correctness.
  • Authority: Capability guarantees depend on developers granting each hole a least-authority scope; over-provisioning reopens the attack surface.Some injection trials still succeed when attackers steer the model toward legitimately granted capabilities.
  • Latency and cost: Each agent call requires model completion and compilation, so retries and nested recursion increase cost; the current implementation is a poor fit for ultralow-latency settings.Generated bodies reused across applications can amortize compilation.
  • Host-language requirements: LACUNA assumes a statically typed host with capability or effect discipline, in-process recompilation, and safe mode that closes reflection and raw process execution.Without these defenses, model-generated code remains exposed to ambient authorities and harmful actions.
  • Termination and resource use: Recursion depth, termination, and resource use are bounded by user-configured runtime caps rather than by the type system.Caps can bound cost and non-termination but may abort legitimate long-horizon tasks when set too low.

A Richer Result Types

LACUNA uses richer expected types to constrain generated results, from algebraic data structures to reusable functions, while compiler checks reject common invalid constructions. The same typed, capability-aware discipline extends to tool composition and generated control flow.

  • Richer result types: Algebraic data types constrain generated results to a fixed shape and field types.A Person result cannot omit a field or return a wrong-typed value.
  • Richer result types: Function types ask the model to generate an implementation matching the declared input and output types.The generated Int => String function converts integers to Roman numerals.
  • Compiler-enforced failures: The type system rejects null assigned to String and nonexhaustive matches over sealed shapes.Compiler diagnostics identify both the invalid Null-to-String assignment and the missing Color.Blue case.
  • Typed tool composition: Tools are ordinary in-scope functions whose signatures let the compiler check end-to-end composition without a separate registry or schema.A generated snippet can search memory, destructure the returned pairs, and pass correctly typed values to sendEmail.
  • Capability safety: Capture checking treats lexical scope as a capability boundary, preventing generated code from invoking or returning capabilities that are unavailable or disallowed.Function types record capability use, while pure types cannot invoke capabilities.

F.4 Planning and Task Assignment

LACUNA supports multi-model planning by assigning different agent calls to configured models within ordinary typed control flow. This permits local cost, capability, and privacy choices, while the routing split itself does not enforce isolation without the capability barrier.

  • Planning and task assignment: Different agent calls can use specialized models for routine subtasks, planning, sensitive data, or other work.Each model is represented as a configured agent instance with its own call site.
  • Planning and task assignment: A powerful planner can emit scaffolding code that delegates subtasks to a smaller agent.Cost and capability decisions remain local to each call, and the type system is independent of the provider.
  • Planning and task assignment: The multi-model pattern generalizes dual-LLM designs by choosing the partition across configured agents separately for each call.The split is flexible rather than fixed by the framework.
  • Planning and task assignment: Routing alone is only a convention: a misrouted call can still leak, so enforced capability barriers are required for isolation.The text distinguishes flexible model assignment from the later enforcement mechanism.

G Experimental Setup

The evaluation exercises LACUNA through compiler-backed tests and benchmark drivers that connect Scala REPL agent calls to BrowseComp-Plus retrieval and τ^2-bench conversations. Runs use hosted models, fixed or programmatic scoring, tracing, and explicit resource limits.

  • Test suite: Roughly 400 Scala 3.9.0 REPL tests exercise parsing, typing, and capture checking in the real compiler pipeline.The cases are contributed to the Scala 3 compiler test suite.
  • BrowseComp-Plus: BrowseComp-Plus evaluates 830 queries through one agent[String] call per query with fixed retrieval and exactly two tools.The tools are search(query), returning five corpus hits, and getDocument(docid), returning one full document.
  • BrowseComp-Plus: Each BrowseComp-Plus query runs in its own REPL under a 600s wall-clock budget with recursive nesting capped at depth 128.The setup compares three hosted models and logs inputs, answers, tool calls, generated snippets, and compiler feedback.
  • τ^2-bench: τ^2-bench covers 392 tasks across retail, airline, telecom, and telecom-workflow domains with programmatic reward scoring and no LLM judge.A Python driver routes each simulated-user turn through the Scala REPL and forwards generated tool calls to the server.
  • Model and budget: All models are hosted endpoints using inference only, while local computation is limited to retrieval and Scala compiler passes.The experiments require no local GPU and enforce the stated per-run resource budgets.
Loading 2605.28617v1…