RunAgent: Interpreting Natural-Language Plans with Constraint-Guided Execution | AI Paper Digest

TL;DR Highlight

LLM이 자연어 플랜을 단계별로 확실히 실행하도록 IF/GOTO/FORALL 같은 제어 구문과 자동 constraint 검증을 붙인 에이전트 실행 프레임워크.

Who Should Read

LLM 에이전트가 복잡한 멀티스텝 태스크를 실행할 때 중간에 틀리거나 빠뜨리는 문제를 겪고 있는 AI 엔지니어. 플랜 기반 워크플로우 자동화를 구축 중인 백엔드 개발자.

Core Mechanics

자연어 플랜에 IF, GOTO, FORALL 같은 제어 키워드를 섞어 쓰는 'agentic language'를 도입해서 LLM의 유연성과 프로그래밍 언어의 결정론적 실행을 동시에 확보했음.
LLM이 'for all 항목에 대해 반복 실행'을 시키면 일부만 처리하는 문제가 있는데, FORALL 키워드로 이 문제를 명시적으로 해결함.
실행 시작 시점에 task와 instance를 분석해서 atomic constraint(단일 조건 하나짜리 제약)를 자동 생성하고, 각 스텝 출력마다 관련 constraint만 골라서 검증함.
각 스텝마다 LLM 직접 호출 / Python 코드 생성+실행 / Tool 호출 중 어떤 방식이 최적인지 자동 판단하고, 개발자가 prefix(LLM:, PYTHON:, TOOL:)로 직접 지정도 가능함.
constraint 검증을 두 단계(reason 생성 → judge 판정)로 나눠서 LLM이 제약 위반 여부를 판단하다가 스스로 문제를 풀려는 현상을 방지함.
스텝 실패 시 에러 메시지를 context에 XML 태그로 임시 추가하고 재시도하는 error correction 루프가 있으며, 최대 재시도 초과 시 fallback LLM으로 강제 진행함.

Evidence

Natural-plan Calendar Scheduling에서 RunAgent 81.1% vs 최신 SOTA PlanGEN Best-of-N(Gemini-2.0-Flash) 68.9%, GPT-4o 직접 풀기 58.3%로 모두 초과.
constraint 검증 모듈을 끄면 75.4%로 떨어짐 → constraint checking이 5.7%p 기여한다는 ablation 결과.
McNemar 검정 결과 chi-square 253.17, p-value 5.29×10⁻⁵⁶으로 RunAgent가 GPT-4o 플랜 구현보다 통계적으로 유의미하게 우수함.
SciBench 수학 데이터셋(Stat/Calc/Diff)에서 GPT-4o 직접 풀기 72.2/70.7/50.0% 대비 RunAgent 80.6/78.1/62.0%로 전 카테고리 개선.

How to Apply

기존 LLM 에이전트가 '모든 항목에 대해 처리' 같은 반복 태스크를 자주 빠뜨린다면, 플랜 스텝에 'FORALL [항목 리스트]: [작업]' 형태로 작성하고 이를 감지해 개별 서브스텝으로 분해하는 컴파일러 레이어를 붙이면 됨.
멀티스텝 워크플로우에서 각 스텝 직후 제약 검증을 넣고 싶다면, 논문 Appendix의 Constraint Generation Prompt를 그대로 가져다 task+instance를 넣어 atomic constraint 리스트를 만들고, Constraint Relevance Prompt로 현재 스텝과 무관한 제약을 필터링한 뒤 검증하는 2단계 구조를 구현하면 됨.
알고리즘/수치 계산 스텝은 LLM 직접 답변보다 Python 코드 생성+실행이 정확도가 높으므로, 스텝 텍스트에 'PYTHON:' prefix를 붙이거나 Python Judge 프롬프트(논문 Appendix)를 써서 자동 분기하는 로직을 추가하면 됨.

Code Example

snippet

# RunAgent Constraint Generation 프롬프트 사용 예시 (논문 Appendix 그대로)
import openai

def generate_constraints(task: str, instance: str) -> str:
    messages = [
        {
            "role": "system",
            "content": """You are an expert at extracting constraints that MUST NOT be violated when solving a task instance.
You will be given:
- A task description
- A specific instance of the task
Your job:
- Output a comprehensive list of constraints that should not be violated while solving the instance.
- Include all explicit hard requirements from the task/instance.
- Include any implicit but necessary constraints/assumptions needed to correctly interpret the instance.
- Do not include any solution, schedule, or plan, ONLY constraints.
Critical constraint quality requirements:
- Make constraints ATOMIC: each numbered item must contain exactly ONE requirement.
- If a requirement contains "and", "or", multiple clauses, or multiple checks, split it into multiple numbered constraints.
- Avoid compound / multi-part constraints.
- Avoid solver goals and optimization goals. Only hard validity/legality constraints.
Output format: Output ONLY a numbered list of constraints as plain text."""
        },
        {
            "role": "user",
            "content": f"Task: {task}\nInstance: {instance}"
        }
    ]
    response = openai.chat.completions.create(
        model="gpt-4o",
        messages=messages
    )
    return response.choices[0].message.content

# 사용 예시
task = "Schedule a meeting for all participants within work hours 9:00-17:00"
instance = "Schedule 1-hour meeting for Alice and Bob on Monday. Alice: busy 10:00-11:00. Bob: busy 14:00-15:30."
constraints = generate_constraints(task, instance)
print(constraints)
# 출력 예:
# 1. The meeting must be scheduled between 09:00 and 17:00.
# 2. The meeting duration must be exactly 1 hour.
# 3. Alice must not have any other meeting during the scheduled time.
# 4. Bob must not have any other meeting during the scheduled time.
# 5. The meeting must be scheduled on Monday.

Terminology

agentic language자연어 문장 안에 IF, GOTO, FORALL 같은 프로그래밍 키워드를 섞어 쓰는 혼합 언어. 사람이 읽기 쉬운 자연어 유연성과 프로그램의 정확한 실행 보장을 동시에 얻는 방식.

atomic constraint조건이 딱 하나인 제약. '미팅은 9시에서 17시 사이여야 한다'처럼 AND/OR 없이 단일 규칙만 담은 제약으로, 여러 조건이 섞이면 어느 게 위반됐는지 파악이 어려워 일부러 쪼개서 씀.

HITL (Human-in-the-Loop)AI 실행 중간에 사람이 개입해서 피드백을 주거나 수정할 수 있는 구조. 자동화가 100% 맞을 수 없을 때 사람이 감시하고 교정하는 안전망 역할.

PlanGEN복잡한 문제 풀이를 위한 플랜을 여러 에이전트가 협력해 생성하고 실행하는 SOTA 프레임워크. RunAgent와 성능 비교 기준으로 사용된 최신 방법론.

Exact Match (EM)모델 출력이 정답과 정확히 일치하는지 측정하는 평가 지표. 캘린더 스케줄링처럼 답이 특정 형식이어야 할 때 씀.

execution context에이전트가 플랜을 실행하면서 쌓아가는 전체 대화 기록. 이전 스텝 결과, 에러, 도구 호출 결과 등이 담겨 있어 다음 스텝 실행의 입력으로 활용됨.

fallback LLM재시도를 최대 횟수까지 해도 실패할 때 최후 수단으로 쓰는 LLM 직접 호출. 검증은 생략하고 일단 플랜 실행이 끊기지 않도록 강제로 진행시키는 안전망.

Related Papers

Original Abstract (Expand)

Humans solve problems by executing targeted plans, yet large language models (LLMs) remain unreliable for structured workflow execution. We propose RunAgent, a multi-agent plan execution platform that interprets natural-language plans while enforcing stepwise execution through constraints and rubrics. RunAgent bridges the expressiveness of natural language with the determinism of programming via an agentic language with explicit control constructs (e.g., \texttt{IF}, \texttt{GOTO}, \texttt{FORALL}). Beyond verifying syntactic and semantic verification of the step output, which is performed based on the specific instruction of each step, RunAgent autonomously derives and validates constraints based on the description of the task and its instance at each step. RunAgent also dynamically selects among LLM-based reasoning, tool usage, and code generation and execution (e.g., in Python), and incorporates error correction mechanisms to ensure correctness. Finally, RunAgent filters the context history by retaining only relevant information during the execution of each step. Evaluations on Natural-plan and SciBench Datasets demonstrate that RunAgent outperforms baseline LLMs and state-of-the-art PlanGEN methods.