PaperlayerView exact revision on arXiv

Source-linked AI summary

TAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agents

Jongwon Jeong, Jungtaek Kim, Kangwook Lee

arXiv:2602.19633v1cs.AI

TL;DR

LM agents remain vulnerable to irrecoverable failures under feasibility constraints because of planning and sampling errors. TAPE aggregates plans into a graph, uses a solver to select feasible paths, applies constrained execution, and adaptively replans. Across four constrained benchmarks, it consistently outperforms ReAct and Plan-and-Act, especially on complex tasks and weaker models.

  • Problem

    LM agents can fail irrecoverably under feasibility constraints, with planning limitations and stochastic execution identified as distinct error sources.

  • Method

    TAPE aggregates multiple plans into a graph, uses an external solver to select feasible paths, applies constrained decoding, and adaptively replans after observation mismatches.

  • Results

    TAPE consistently outperforms ReAct and Plan-and-Act across four constrained agentic benchmarks, particularly on complex tasks and for models with limited planning capabilities.

  • Takeaways & Limitations

    TAPE improves success rates by addressing both planning and sampling errors in constrained language-model-agent tasks.

  • Takeaways & Limitations

    TAPE depends on accurate plan-graph construction and a pre-specified solver, which may limit generality across task formulations.

Abstract

from arXiv · show

Language Model (LM) agents have demonstrated remarkable capabilities in solving tasks that require multiple interactions with the environment. However, they remain vulnerable in environments where a single error often leads to irrecoverable failure, particularly under strict feasibility constraints. We systematically analyze existing agent frameworks, identifying imperfect planning and stochastic execution as the primary causes. To address these challenges, we propose Tool-guided Adaptive Planning with constrained Execution (TAPE). TAPE enhances planning capability by aggregating multiple plans into a graph and employing an external solver to identify a feasible path. During execution, TAPE employs constrained decoding to reduce sampling noise, while adaptively re-planning whenever environmental feedback deviates from the intended state. Experiments across Sokoban, ALFWorld, MuSiQue, and GSM8K-Hard demonstrate that TAPE consistently outperforms existing frameworks, with particularly large gains on hard settings, improving success rates by 21.0 percentage points on hard settings on average, and by 20.0 percentage points for weaker base models on average. Code and data available at here.

1. Introduction

LM agents can fail irrecoverably when feasibility constraints make planning or execution mistakes unrecoverable. TAPE addresses both error sources by selecting feasible paths from aggregated plans and enforcing constrained execution with adaptive replanning.

  • Motivation: Feasibility constraints such as budgets, tool limits, and safety requirements make some LM-agent mistakes irrecoverable.Under these constraints, incorrect tool use can exhaust available resources or prevent goal completion.
  • Failure Sources: Planning errors recommend non-viable actions, while sampling errors arise when stochastic generation deviates from the intended plan.The two failure sources can occur independently, including when reasoning is correct but execution samples a different action.
  • Failure Sources: As task horizons increase, compounded failures reduce success rates, while Plan-and-Act remains vulnerable to planning errors despite reducing sampling errors.The introduction reports that this brittleness persists beyond ReAct frameworks.
  • TAPE: TAPE aggregates multiple candidate plans into a graph and uses an external solver to select a feasible path, mitigating planning errors.The framework uses diverse candidate plans and solver-based path selection.
  • TAPE: TAPE applies constrained decoding to planned actions and adaptively replans when predicted and realized observations mismatch, suppressing sampling errors.The plan graph is updated and a feasible plan is re-selected after environmental feedback deviates from expectations.
  • Evaluation: TAPE consistently outperforms ReAct frameworks across constrained Sokoban, ALFWorld, MuSiQue, and GSM8K-Hard benchmarks.The performance gap is reported as largest on hard tasks and for weaker base models.

2. Problem Formulation

The paper models constrained agentic tasks as goal-directed environment interactions where planning and execution must satisfy feasibility requirements. It distinguishes planning errors from sampling errors and formalizes how both can cause failure.

  • 2.1. Agentic Task: Agentic tasks are modeled as goal-conditioned Markov Decision Processes with goals, actions, states, transitions, and binary goal rewards.The agent iteratively selects actions from the current interaction history and receives environmental observations.
  • 2.1. Agentic Task: Budget-constrained success requires reaching the goal while keeping cumulative costs within the budget; dead-end violations terminate unsuccessfully.Budgets can represent time, monetary cost, or limits on tool calls.
  • 2.2. Language Model Agent Framework: LM agents use a stochastic policy and an internal world model to simulate trajectories and choose actions during environment interaction.The internal model approximates transition dynamics, rewards, and costs, while abstract states distill execution-relevant history.
  • 2.2. Language Model Agent Framework: ReAct separates decision-making into internal planning and sampled execution, with the planned next action conditioning the subsequent action choice.The planning stage predicts future abstract states over a lookahead horizon before execution samples an action.
  • 2.2. Language Model Agent Framework: Plan-and-Act generates a full abstract plan before step-wise execution, reducing sampling errors but remaining vulnerable to planning errors.The planned action is induced by the internal abstract world model.
  • 2.3. Errors from Two Different Sources: Planning error produces a non-viable recommendation through imperfect reasoning or world-model mismatch, whereas sampling error executes an action different from correct reasoning.Sampling error can arise from stochastic token generation, prompt sensitivity, and formatting drift.
  • 2.3. Errors from Two Different Sources: The analysis assumes constant, time-invariant per-step error rates and separately models planning and sampling error probabilities.Additional parameters describe whether sampling deviations break viability for viable plans or recover viability for non-viable plans.

3. Our Approach: TAPE

TAPE constructs a graph from multiple candidate plans, uses an external solver to select a feasible path, and constrains execution to the selected actions. It checks predicted against realized states and replans when they diverge.

  • 3. Our Approach: TAPE: TAPE reduces planning and sampling errors through plan graph construction, solver-based path selection, constrained execution, and adaptive replanning.The framework is explicitly designed to address both error sources.
  • 3.1. Plan Graph Construction: TAPE generates multiple abstract plans and folds their shared states and actions into a graph G = (V, E).States with the same observation and task progress are merged into one graph node.
  • 3.1. Plan Graph Construction: The internal world model assigns predicted rewards to terminal nodes and predicted cost vectors to graph edges.In constrained settings, predicted edge costs enforce feasibility under the remaining budget.
  • 3.2. Plan Path Selection: An external solver selects a directed walk from the current node to a terminal node over a finite time-expanded horizon.The optimization uses edge-selection variables and can incorporate budget constraints.
  • 3.2. Plan Path Selection: The solver maximizes accumulated reward while enforcing one action per step, valid start and terminal states, and path continuity.Budget restrictions can be added to the optimization problem when required.
  • 3.3. Constrained Execution: When the current environment node matches the selected path, TAPE restricts decoding to the prescribed next action.Implementation fixes the tool choice and enforces the exact tool-call format.
  • 3.4. Mismatch Check: If the realized state mismatches the predicted state, TAPE regenerates plans, rebuilds the graph with updated estimates, and solves for a new path.Without a mismatch, execution continues with the next planned action.

4. Theoretical Analysis

The analysis models success under feasibility constraints and shows how planning and sampling errors compound over task steps. TAPE improves the theoretical bound by aggregating candidate actions, selecting viable paths, and suppressing sampling error.

  • Success requires reaching the goal while every preceding action remains viable.
  • As task horizon T grows, per-step planning and sampling errors compound and sharply reduce ReAct’s overall success rate.
  • When deviations are more likely to break viability than restore it, reducing planning and sampling errors increases success probability.
  • Plan-and-Act raises the upper success bound by reducing sampling error, but its planning error remains.
  • TAPE aggregates plans into a graph, expands candidate actions, and uses an external solver to select a viable path while constrained decoding eliminates sampling error.

5. Empirical Analysis

Experiments compare TAPE with ReAct and Plan-and-Act across constrained agentic benchmarks, error analyses, model capabilities, plan counts, and component ablations. TAPE consistently performs best, especially as tasks become harder or models become weaker.

  • Overall Results: TAPE is evaluated against ReAct and Plan-and-Act on Sokoban, ALFWorld, MuSiQue, and GSM8K-Hard.
  • Overall Results: TAPE consistently outperforms both baselines across the four benchmarks, including settings where existing frameworks achieve near-zero success rates.
  • Error Analysis: Both planning and sampling errors occur in existing frameworks, while lower error rates are associated with higher success rates.
  • Task Difficulty: As difficulty increases, ReAct and Plan-and-Act success rates decline by averages of 55.4% and 52.4%, whereas TAPE decreases by 27.7%.
  • Model Capability: TAPE outperforms baselines across models with different planning capabilities, with larger gains on less capable models.
  • Sensitivity to M: M = 4 yields optimal performance; increasing to M = 8 causes a decline, potentially because graph construction relies on the LM.
  • Ablation Study: Removing the external solver, constrained execution, or replanning lowers success from 46.0 to 42.0, 36.0, or 38.0, respectively.

6. Conclusion

The paper concludes that TAPE mitigates planning and sampling errors through graph-based feasible-path selection, constrained execution, and adaptive replanning. It reports stronger performance than ReAct and Plan-and-Act, particularly on complex tasks and weaker models, while identifying graph accuracy and solver generality as limitations.

  • TAPE combines plan aggregation, Integer Linear Programming, constrained execution, and adaptive replanning to mitigate planning and sampling errors.
  • Experiments show TAPE outperforms ReAct and Plan-and-Act, particularly on complex tasks and for models with limited planning capabilities.
  • Limitations & Future Work: Plan-graph accuracy depends on the LM’s ability to structure and merge states, and inaccurate construction may misrepresent the true environment.
  • Limitations & Future Work: Reliance on a pre-specified solver may limit generality across tasks with different optimization formulations.

Impact Statement

The work targets more reliable LM agents under time, cost, and tool-usage constraints, while noting that greater reliability may also lower barriers to misuse and increase inference-time resource use.

  • TAPE may enable more dependable and cost-aware automation in benign applications under feasibility constraints.
  • Improved reliability can lower barriers to misuse in harmful or unauthorized settings.
  • Plan generation and plan-graph construction may increase inference-time computation, monetary cost, and energy use.
  • The authors encourage access control, monitoring, logging, and rate limits for responsible deployment.

A. Conceptual Toy Analysis Details

The analysis distinguishes planning and sampling errors as sources of irrecoverable failures under feasibility constraints. TAPE addresses them by selecting feasible paths over plan graphs and constraining execution with adaptive replanning.

  • Motivation: Feasibility constraints make small planning or sampling errors capable of compounding into violations and irrecoverable states.
  • Conceptual Analysis: The framework formalizes planning and sampling errors as two sources of irrecoverable failure in ReAct frameworks.
  • TAPE: TAPE aggregates diverse candidate plans into a plan graph and uses a formal solver to select a constraint-feasible path.
  • TAPE: Constrained decoding selects the planned action during execution, while replanning responds to mismatches between observations and the plan.
  • Constrained G-MDP: The constrained G-MDP formulation accounts for predicted edge costs and requires the selected walk to remain within the remaining budget.

D.1. Proof of Proposition 4.2

The proofs model task success as repeated viable-action selection under planning and execution errors. They show how candidate-action diversity and constrained execution improve the derived success bounds relative to ReAct and Plan-and-Act.

  • ReAct: For ReAct, a viable action can result from a viable plan with successful or non-catastrophic execution, or from accidental recovery after a non-viable plan.
  • ReAct: Task success is represented as the intersection of viable-action events across required steps, with overall probability bounded by the product of single-step probabilities.
  • ReAct: The ReAct upper bound increases as sampling error decreases and as planning error decreases.
  • Plan-and-Act: Plan-and-Act eliminates execution sampling error when the generated plan is followed, but its plan remains subject to planning error.
  • Plan-and-Act: The analysis states UPA ≥ UReAct because effective Plan-and-Act sampling error is no greater than ReAct sampling error.
  • TAPE: With d(vt) candidate actions, TAPE’s single-step success probability is 1 −(ϵp)d(vt) when a solver selects a viable candidate and constrained execution removes sampling error.
  • TAPE: Under the stated assumptions, the proof concludes UOurs ≥ UPA, with equality in the specified single-candidate and zero-effective-error case.

E.1. Experimental Setup

The evaluation uses four agentic benchmarks modified or selected to contain feasibility constraints and frequent irrecoverable states. Experiments vary task difficulty, resource trade-offs, model backbones, and baseline prompting frameworks.

  • Tasks and Datasets: The evaluation covers Sokoban, ALFWorld, GSM-Hard, and MuSiQue, each representing a distinct planning, embodied, mathematical, or retrieval-based setting.
  • Tasks and Datasets: Sokoban difficulty is controlled by optimal solution length, with easy instances at T⋆=6 and hard instances at T⋆=10.
  • Sokoban Mechanics: The Sokoban implementation defines four primitive actions, and invalid wall or blocked-box moves leave the player and boxes unchanged.
  • Tasks and Datasets: MuSiQue introduces five retrievers spanning fast, cheap, inaccurate retrieval to slow, expensive, accurate retrieval, creating an explicit cost–quality trade-off.
  • Language Model Backbones: The study evaluates five language-model backbones: gpt-4.1-nano, gpt-4.1-mini, gpt-4.1, gpt-5-nano, and claude-4.5-haiku.

F. Implementation Details of TAPE

TAPE’s implementation builds and scores a graph of diverse Sokoban plans, then selects and executes feasible action paths under limited steps. The prompting procedure explicitly models states, actions, goals, deadlocks, and coordinate-consistent transitions.

  • Implementation organization: The implementation includes prompts for state projection, plan-graph construction, and graph annotation, with JSON outputs specifying reasoning, merge logs, nodes, and edges.
  • State projection and planning: TAPE extracts the current player, box, goal, and box-on-goal locations before planning a full solution within the remaining steps.
  • State projection and planning: The Sokoban prompts require diverse valid plans with precise reasoning based on player, box, goal, wall, and movement rules.
  • Plan-graph construction: Each plan is simulated step-by-step into alternating node and action entries, with unique node ids and observations containing player and box locations.
  • Plan-graph construction: Identical observation nodes are merged while all plan actions are preserved, producing a graph whose edges encode transitions and whose goal nodes are marked explicitly.
  • Graph annotation: Graph states receive scores of 1.0 for goals, -1.0 for unreachable or deadlocked states, and 0.0 otherwise, based on reachability under Sokoban mechanics.

G.1. Planning & Sampling Error Estimation

The error analysis separates planning from sampling failures by comparing an intended action against its simulated viability and the action actually executed. It uses oracle search to determine whether intended actions preserve feasibility.

  • Error definitions: The analysis extracts the intended next action from the agent’s Thought using gpt-4.1-mini as a parser.
  • Planning-error estimation: Given the current state and intended action, the procedure simulates a one-step transition and applies a Breadth-First Search oracle to estimate minimum remaining steps.
  • Planning-error estimation: An intended action is non-viable when the resulting state requires more steps than the remaining budget or cannot reach the goal.
  • Sampling-error estimation: Sampling error is measured as 1[at≠ât], where at is the executed action and ât is the intended action, averaged over steps.
  • Qualitative error analysis: A representative example shows a plan implying R to push a box toward the goal while execution deviates to U, illustrating stochastic action mismatch.

G.2. Additional Empirical Results

Additional results show that TAPE benefits from matched multi-plan comparisons, larger step budgets, and feasible graph-based execution. Across these analyses, TAPE combines higher success with more reliable or efficient behavior under constraints.

  • Compute-matched comparison: 46.0% success on Sokoban (easy) with M=4 lets TAPE outperform PA (20.0%), PA-best-of-4 (22.0%), ReAct (4.0%), and ReAct-best-of-4 (8.0%).
  • Compute-matched comparison: With the same number of sampled plans per step, TAPE’s gains are not solely attributable to increased sampling, but to plan selection and constrained execution.
  • Larger step budgets: TAPE’s success increases monotonically from 46% to 75% as normalized step budget B/Smin increases, whereas ReAct and Plan-and-Act largely plateau.
  • Larger step budgets: TAPE reduces planning errors and sampling-induced deviations through constrained decoding and mismatch-triggered replanning, allowing additional budget to support recovery.
  • Success–cost trade-off: TAPE achieves higher success while using fewer steps per budget on average than ReAct and Plan-and-Act, indicating improved success–cost efficiency.
  • Graph-based execution: In a Sokoban graph example with 5 steps remaining, an external solver selects a blue feasible path from the constructed graph.
  • Trajectory comparison: Under the same action budget, ReAct fails after an early mistake, whereas TAPE reaches the goal by selecting a feasible plan and executing it more reliably.
Loading 2602.19633v1…