RunAgent: Bridging Natural Language Plans and Deterministic Execution

Paper: 2605.00798 Authors: Arunabh Srivastava, Mohammad A., Khojastepour, Srimat Chakradhar, Sennur Ulukus Categories: cs.LG, cs.CL, cs.MA

The Gap

LLMs can generate impressive text, but they’re notoriously unreliable when you need them to follow a structured workflow. Prior work splits into two camps: end-to-end LLM execution (flexible but chaotic—the model drifts, hallucinates, or skips steps) and rigid symbolic planners (deterministic but brittle—can’t handle natural language ambiguity). Methods like ReAct and PlanGEN try to bridge this by having LLMs generate and execute plans, but they lack enforcement mechanisms. The model might claim it’s following step 3 while actually doing something from step 5, or it might satisfy the surface instruction while violating implicit constraints.

Problem: LLMs unreliable for structured workflows
    |
    v
Assumption: Need both NL flexibility AND execution determinism
    |
    v
Method: Agentic language with control flow + constraint validation
    |
    v
Evidence: Outperforms baselines on Natural-plan & SciBench
    |
    v
Conclusion: Explicit control + dynamic verification = reliable execution

The Increment

One sentence: Before RunAgent, you chose between flexible-but-unreliable LLM execution or rigid-but-brittle symbolic planning; after RunAgent, you get natural language expressiveness with programming-like execution guarantees through explicit control constructs and constraint validation.

Core Mechanism

RunAgent introduces an “agentic language” that sits between natural language and code. Each plan step gets annotated with explicit control flow constructs (IF, GOTO, FORALL) that dictate execution order, plus rubrics that define success criteria. The system has three execution modes: LLM-based reasoning for open-ended tasks, tool usage for structured operations, and code generation for computational work. At each step, RunAgent doesn’t just check if the output looks right—it autonomously derives constraints from the task description and validates them.

The execution flow works like this: parse the plan into steps with control annotations, execute the current step using the appropriate mode, validate both the step’s explicit rubric and derived constraints, then use the control construct to determine the next step. If validation fails, error correction kicks in—the system analyzes what went wrong and retries with corrections. Context management runs throughout: only information relevant to the current step gets retained, preventing the context window from becoming a junkyard of irrelevant history.

Think of RunAgent as a stage director for an improv troupe. The script (plan) is written in natural language with stage directions (control constructs). Each actor (execution mode—LLM, tool, code) has different strengths. The director (RunAgent) reads the stage directions to know who performs next, watches the performance (step execution), checks both the explicit cues (rubrics) and implicit blocking rules (derived constraints), and decides if the scene worked. If an actor flubs their line, the director stops, explains what went wrong, and they retry. Meanwhile, the prompter (context manager) only feeds actors the lines relevant to their current scene, not the entire play. The control constructs are load-bearing: without GOTO, you can’t loop back to retry; without IF, you can’t branch based on validation results; without FORALL, you can’t iterate over collections. The metaphor maps directly: stage directions → control flow, performance → execution, blocking rules → constraints, scene transitions → step sequencing.

Key Concepts

• Agentic Language: Imagine you’re giving instructions to a very literal assistant. “Handle the customer complaints” is too vague—they might ignore urgent ones or spend all day on spam. You need to be more specific: “FOR each complaint in the queue, IF priority is high, THEN respond within 1 hour, ELSE respond within 24 hours.” That’s what agentic language does—it adds programming-like control flow (loops, conditionals, jumps) to natural language instructions. The “agentic” part means each step can still be executed by an intelligent agent (LLM, tool, code), not just dumb string matching. So you get the expressiveness of “handle complaints naturally” with the precision of “follow this exact workflow.”

• Constraint Derivation: Most systems only check what you explicitly tell them to check. If your rubric says “output should be a valid email,” they verify the format but miss that you sent it to the wrong person. RunAgent reads the task description (“notify the customer about their order”) and the current instance (“order #1234 for [email protected]”) and derives implicit constraints: the email must mention order #1234, must be sent to [email protected], must contain order status. These aren’t in the rubric—the system infers them from context. It’s like a good assistant who doesn’t just follow the checklist but understands what you’re actually trying to accomplish.

• Dynamic Mode Selection: Different tasks need different tools. Answering “What’s the capital of France?” needs LLM reasoning. Querying a database needs tool usage. Computing a statistical correlation needs code execution. RunAgent doesn’t force everything through one interface—it looks at each step and picks the appropriate mode. If the step says “analyze the sentiment,” it uses the LLM. If it says “fetch user records where age > 30,” it generates a database query. If it says “calculate the standard deviation,” it writes Python code. The selection happens automatically based on the step’s structure and requirements, not manual annotation.

Framework Shift

Before (mainstream approach):        After (RunAgent):

Plan: NL text blob                   Plan: NL + control constructs
  |                                    |
  v                                    v
LLM executes freeform                Step-by-step executor
  |                                    |
  v                                    +---> Mode selector
Check output format                    |       |
  |                                    |       +-> LLM / Tool / Code
  v                                    |
Done (hope it worked)                  +---> Constraint validator
                                       |       |
                                       |       +-> Rubric check
                                       |       +-> Derived constraints
                                       |
                                       +---> Control flow interpreter
                                       |       |
                                       |       +-> IF / GOTO / FORALL
                                       |
                                       +---> Error correction
                                       |
                                       v
                                     Next step (guaranteed valid)

From implicit execution to explicit control, the core shift is making the workflow structure first-class and enforceable rather than hoping the LLM remembers to follow it.

Expert Assessment

Problem choice: Real gap. The “LLMs are unreliable for structured tasks” problem is well-documented and matters for practical deployment. This isn’t manufactured—anyone who’s tried to build an LLM-based workflow system has hit this wall. The positioning is smart: they’re not trying to replace LLMs or symbolic planners, just bridge them.

Method maturity: Solid engineering with one clever insight (constraint derivation) and a lot of good systems work (mode selection, context filtering, error correction). The agentic language isn’t revolutionary—it’s basically adding control flow annotations to natural language—but it’s the right level of structure. The constraint derivation is genuinely useful: most systems only validate what you explicitly specify, and inferring implicit constraints from task descriptions is a practical win. The dynamic mode selection feels obvious in hindsight but is often overlooked. No major red flags about simpler approaches being ignored.

Experimental integrity: Baselines are reasonable (GPT-4, Claude, PlanGEN). The datasets (Natural-plan, SciBench) are appropriate for testing structured execution. The paper claims “outperforms” but doesn’t show failure case analysis—I’d want to see where RunAgent still fails and why. The constraint derivation mechanism is described conceptually but the paper doesn’t detail how it actually works (is it prompt engineering? a separate model? rule-based?). That’s a significant omission for reproducibility. The context filtering claims efficiency gains but doesn’t show ablations proving it’s necessary.

Writing quality: The abstract and intro are clear. The method section is where it gets hand-wavy—“autonomously derives constraints” needs a concrete algorithm, not just a description. The evaluation section shows results but doesn’t dig into why RunAgent wins or where it struggles. If they rewrote Section 3 (Method) with pseudocode and concrete examples of constraint derivation, the paper would jump from “interesting idea” to “reproducible system.”

Verdict: weak accept — Addresses a real problem with a practical solution, but the constraint derivation mechanism needs more detail for the contribution to be fully evaluated and reproduced.

Takeaways

The constraint derivation idea is immediately useful: when building any LLM-based system, don’t just validate explicit outputs—infer what must be true from the task context and check those too. The mode selection pattern (LLM for reasoning, tools for structured ops, code for computation) is a good architectural template for multi-capability systems. The context filtering approach (only retain relevant history per step) is a simple way to manage context bloat in long workflows. The agentic language concept—adding minimal control flow to natural language—is a sweet spot between full programming and pure NL that could apply to other domains like robotic task planning or business process automation.