cs.AIFeb 23, 2026
SaveTAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agents
Organizations: Electrical and Computer Engineering, University of Wisconsin–Madison · KRAFTON · Ludo Robotics
Abstract
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.
Figures & tables
Figure 1: Overview. We illustrate our work using Sokoban, where the goal is to push all boxes onto target locations. (a) Sources of Irrecoverable Failure in the ReAct Framework. A planning error occurs when the internal reasoning suggests a non-viable action (e.g., pushing a box against a wall); this makes the goal unachievable as the agent cannot pull the box from the wall, while a sampling error arises when LM stochasticity leads to an action deviating from the plan. (b) Conceptual Toy Analysis. We model simplified agents by injecting planning and sampling errors into a feasible policy for Sokoban. We measure success rates as the task step increases, observing that existing frameworks degrade rapidly as grows. See Appendix A for details. (c) Our Framework. TAPE generates and aggregates multiple plans into a graph and uses a solver to select a feasible path, thereby reducing planning errors. Then, it enforces constrained execution to suppress sampling errors.
Figure 2: Overview of TAPE. The proposed framework consists of four steps. (a) Plan Graph Construction : The LM samples multiple trajectories, which are aggregated into a plan graph with predicted costs and scores. (b) Plan Path Selection : An external solver (e.g., ILP) identifies the optimal path (blue arrows) subject to constraints. (c) Constrained Execution : The agent executes the selected actions using constrained decoding to eliminate sampling errors. (d) Mismatch Check : If a mismatch occurs between the predicted and realized state, the agent re-performs plan graph construction and path selection; otherwise, the agent executes the next planned action.
Figure 3: Success rates across four agentic tasks. We evaluate our framework against ReAct and Plan-and-Act on Sokoban, ALFWorld, Musique, and GSM-Hard. We use gpt-4.1-mini for LM backbone. We find that TAPE consistently demonstrates superior performance over existing frameworks in both easy and hard settings.
| Framework | Planning Error (%) | Sampling Error (%) | Success Rate (%) |
| ReAct | |||
| Plan-and-Act | |||
| TAPE |
Table 1: Planning and sampling error analysis on Sokoban. We estimate planning and sampling error rates across all states and find that both errors occur in existing frameworks. TAPE substantially reduces both errors, showing an improvement in success rate. Best is in bold and second-best is underlined .
Figure 4: Cross-model success rates and sensitivity to the number of generated plans in Sokoban. (a) Success rates of TAPE and baselines across LMs with different planning capabilities. TAPE consistently improves over other frameworks, with larger gains on weaker models, indicating effective mitigation of planning errors. (b) Sensitivity of TAPE to the number of generated plans used to construct the plan graph. The best performance is achieved at , suggesting that moderate plan aggregation via node merging effectively expands the candidate action space.
| External Solver | Constrained Execution | Replanning | Success Rate |
| ✓ | ✓ | ✓ | |
| - | ✓ | ✓ | |
| ✓ | - | ✓ | |
| ✓ | ✓ | - | |
| ✓ | - | - | |
| - | ✓ | - |
Table 2: Ablation study. We compare TAPE against variants that remove components from: (i) External Solver , (ii) Constraint Execution , and (iii) Replanning in Sokoban. A checkmark (✓) indicates the component is enabled; a blank (-) indicates it is removed. Result shows that all components are crucial to improve the success rate. Best is in bold and second-best is underlined .
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
| Thoughts | Planned | Executed |
| The player is at (6, 4), right below the box at (6, 5). The player can push the box right from (6, 5) to (7, 5), which is the goal. This push will complete the task. The immediate next action is to push the box right by moving right from (6, 4) to (7, 4), pushing the box from (6, 5) to (7, 5). | R | U |
Table 3: Example of sampling error. Although the plan specifies the immediate next action as , the executed action is .
| Method | Success Rate (%) |
| TAPE (M=4) | |
| Plan-and-Act | |
| Plan-and-Act (M=4) | |
| ReAct | |
| ReAct (M=4) |
Table 4: Comparing TAPE with best-of- integration on the ReAct and PA frameworks ( Wang et al., 2023b ) . Results are on Sokoban (easy) , and we report mean standard error . For a compute-matched comparison, the Best-of- variants sample the same number of plans per step ( ) as TAPE. Even under this matched sampling budget, TAPE consistently achieves higher success rates, suggesting that the gains are not solely due to increased sampling.
Figure 5: Impact of larger step budgets and success-cost trade-off on Sokoban. (a) Success rate as a function of the normalized step budget , where denotes the oracle minimum number of steps (here and ). Error bars indicate standard error across runs. Our framework is more higher success rate as step budget increases. (b) Success rate versus step consumption (steps used divided by the budget). Methods closer to the top-left achieve higher success while consuming fewer steps per budget, indicating a better success–cost trade-off. TAPE can be both efficient and powerful compared to other frameworks.
Figure 6: Graph construction and plan selection example in Sokoban . Graph is constructed by multiple paths from LLM lookahead plans. Then, a blue path is selected by a formal solver (ILP). When performing constrained execution, TAPE can accurately performs its plan, achieving the goal.
Figure 7: Qualitative comparison between ReAct and TAPE. We visualize representative execution trajectories under the same action budget ( ). (a) ReAct makes a mistake at (red), after which it repeatedly deviates and fails to reach the goal within the budget, terminating at (END/FAIL). (b) TAPE selects a feasible path and executes it reliably, reaching the goal within the same budget at (blue).