TPS: Tool-Guided Planning Subagents for Agent Harnesses

Planning should be externalized from the agent's reasoning loop. Plans written in text cannot be perfect, and when actions are limited and some cannot be undone, a single plausible plan can exhaust the remaining budget and leave the task unfinishable. TPS externalizes planning into a tool: planning subagents simulate candidate plans, and an external solver selects the route that satisfies the remaining budget. The solver does not miss feasible routes as an LM does when it selects a path itself, and the check precedes execution.

Jongwon Jeong¹ Jungtaek Kim² Minki Kang³ Kangwook Lee^4,5

¹ University of Wisconsin–Madison · ² University of Arkansas · ³ KAIST · ⁴ KRAFTON · ⁵ Ludo Robotics

September 2026

Introduction

Under a limited action budget, a single planning mistake can make a task impossible to finish.

A language model (LM) agent solves a task by acting in an environment: it runs code, calls application APIs, operates a computer. Around the model sits a harness, the software that feeds the model its inputs, executes the actions it proposes, and returns what happened. ReAct [1], which alternates reasoning and acting, is the canonical loop.

Actions are not free. Some change the environment in ways that cannot be undone. Even the reversible ones spend time or an action budget that is never refunded [2]. Every action the agent takes narrows what it can still do.

The plan is written in text, by the same model that reasons in text, and such a plan cannot be perfect [3]. Most mistakes are cheap: the agent notices, undoes the step or routes around it, and goes on. But every action it took, the wrong one and the ones that undo it, is gone from the budget. The task does not get cheaper in the meantime: from any state there is a minimum number of actions that still finishes it. The moment that minimum exceeds the actions that remain, the task is lost. The agent can see the mistake, and it changes nothing, because spent actions never come back. We call this irrecoverable failure [4]. Such failures are hard to detect at the time: the plan that caused them appeared reasonable and often achieved part of the goal.

Our answer is Tool-guided Planning Subagents (TPS), which externalizes planning from the agent's reasoning loop into a tool that plugs into an existing harness. Inside the tool, it separates two tasks that LMs perform unequally well: predicting where a step leads, which they do well, and verifying that an entire plan fits a budget, which they do poorly. When the agent needs a plan, it calls the tool. Planning subagents predict candidate futures and organize them as a graph, and an external solver selects the route through that graph that reaches the goal within the remaining budget. The route is returned as guidance, and the agent continues in its original loop.

TPS

LM subagents predict candidate futures as a graph, and an external solver selects the path within the budget.

When the main agent calls TPS, it hands over three things: its history $h$, the goal $g$, and the remaining budget $b$. If the task limits more than one quantity, say time and a number of actions, $b$ has one entry per limit. Four subagents then run in sequence, using the same LM as the main agent with stage-specific prompts.

1. Multi-plan sampling. The first subagent generates $M$ different candidate plans. A plan is a sequence of subplans, and a subplan is one step the main agent can carry out with one or more concrete actions. "Pin the dependency to version 1" is a subplan; the exact command is left to the main agent.
2. State simulation. The second subagent walks each candidate and predicts the state after every subplan, together with what the step costs. Costs are nonnegative vectors with the same entries as $b$.
3. State merging. The third subagent merges predicted states that are equivalent for the rest of the planning. Candidates that pass through the same state now share a node, each subplan becomes an edge with its predicted cost, and the candidates have become a plan graph.
4. Reward prediction. The fourth subagent labels every node: +1 if the goal is satisfied there, -1 if it is a dead end, 0 otherwise.

The solver then does the part that LMs are least reliable at: constrained selection. The selected path is

$$\pi^\star \in \operatorname*{arg\,max}_{\pi \in \mathcal{P}} R(\pi) \quad \text{subject to} \quad \sum_{e \in \pi} c(e) \preceq b,$$

Because TPS is exposed through the standard tool interface, it plugs into any harness that can call tools without changes to the harness's reasoning loop. The harness does not need to know that planning happened, only that a plan was returned. The figure shows the same call in three harnesses.

Results

Adding the tool to three harness families on eight benchmarks increases success in every case.

For each harness we compare Base, the harness on its own, with Base + TPS, the same harness with TPS exposed as a planning tool, under the same benchmark-specific environment-execution limits. We report success rate and use ILP as the solver. For the game and text-world tasks the harnesses are ReAct [1], Recursive Language Models (RLM, recursion depth 2) [8], and Tree of Thoughts (ToT) [9], all driven by gpt-4.1-mini. The benchmarks are Sokoban, Snake, BlocksWorld, ALFWorld, and ScienceWorld.

The mean gain is 38.7 points across the games and 25.2 across the text worlds, and the pattern follows the problem setting. The largest gains, on Sokoban and ALFWorld, occur in tasks where an early wrong move exhausts the budget. The smallest, on ScienceWorld, occurs in the task with the longest and most open-ended episodes, where predicting the outcome of a subplan is hardest.

Coding agents are the harder test. The harness runs shell commands, calls application APIs, or executes a machine-learning workflow, and each base harness is already tuned for its benchmark. We add TPS to Terminus-KIRA on Terminal-Bench 2.0, to ReAct on AppWorld, and to CodeAct on MLGym-Bench, all with claude-haiku-4.5 as the backbone.

The mean gain is 6.2 points, smaller than in the games, as expected when the harness already encodes most of the task knowledge, but in the same direction on all three benchmarks.

Why it helps

TPS uses fewer environment actions, and the solver finds feasible paths that the LM misses.

Sokoban lets us look inside the gains, because an oracle knows the minimum number of actions T^⋆ needed to finish from any state. That gives a budget with a known amount of slack: B_env = T^⋆ + Δ for Δ ∈ {2, 4, 8, 16}. We compare ReAct with ReAct + TPS, using gpt-4.1-mini and four candidate plans.

More slack alone does not close the gap. As the budget grows, TPS success rises from 70% to 92%. ReAct stays between 8% and 15% across the same range. Planning is what lets the agent turn extra actions into completed episodes.

TPS uses fewer actions while succeeding more often. Averaged over all episodes, including failures, TPS consumes 40.5% of the budget at Δ = 16, compared with 92.9% for ReAct.

It rarely paints itself into a corner. The oracle identifies the first action after which the goal is still reachable but needs more actions than remain. TPS reduces the number of such episodes from 91 to 29 at Δ = 2 and from 75 to 6 at Δ = 16, out of 100 per configuration.

To separate the contribution of the solver from that of the graph, we give gpt-4.1-mini and ILP the identical recorded graph, with the same nodes, edges, rewards, costs, and remaining budget, and ask each for a feasible path, counting only graphs on which one exists.

The LM misses paths that exist, and misses more of them as the graph grows: on graphs with at least 21 nodes it finds a feasible path in 22 of 26 cases, while ILP finds one in all 26. Even with the whole graph in front of it, constrained selection is a job for a solver. This is an error that externalizing planning to a solver removes.

A component ablation asks whether each stage is necessary, or whether generating candidates and selecting one suffices. On Sokoban, with Qwen3-14B as both executor and planner, each stage adds to success.

Best-of-N selection among four plans reaches 20%. Organizing the same candidates into a graph and letting the LM pick a path reaches 29%. Handing the selection to the solver reaches 37%.

Practical considerations

The guarantee holds only on the predicted graph, and planning has an inference cost.

Graph accuracy. Externalizing planning removes the errors the LM makes when it chooses a path itself, not the errors in its predictions. The solver guarantees feasibility only on the graph it is given, and if the graph is wrong, the guarantee is wrong with it. The subagents make three kinds of prediction: which states are the same, what state a step leads to, and which states earn the reward. We checked each against the real environment.

Merging is the most reliable step, and its mistakes fall on the safe side: a pair of equivalent states that stays unmerged cannot add a false path. On ALFWorld, reward prediction is where most of the remaining failures live. A plan that is feasible on the graph can still fall short in the environment, so in deployments where actions have real consequences, the plan still needs task-appropriate permissions and validation before execution.

Inference cost. TPS spends additional LM calls before acting. A natural alternative use of that compute is a larger planning advisor that hands a smaller base model one plan, or four plans with LM-based selection. We compare the two on Sokoban with the Qwen3 family, counting every LM call: base agent, subagents, and advisor. Hover a point for the exact numbers.

The subagents simulate the base model's own futures, so the benefit grows with a base model that can do that well, and at 0.6B the subagents cannot build a usable graph at all. Planning adds inference cost; the trade is favorable for a model that can simulate its own futures.

Harness optimization

Harness optimization is an agentic task under an evaluation budget, and the same tool applies to it unchanged.

Meta-Harness [10] improves an agent's harness automatically. An LM proposer reads the current harness code, its execution traces, and its evaluation scores, then writes a revised candidate. A fixed task model runs the candidate on validation examples, and the scores guide the next revision. Evaluations are the scarce resource, so the proposer has to anticipate which revisions will pay off before spending evaluations on them. This is a planning problem under a budget.

We follow the main Meta-Harness setup: a Claude Sonnet 5 proposer, a fixed gpt-oss-20b task model, and three datasets (reactant prediction on USPTO, disease prediction from symptoms on Symptom2Disease, and charge prediction from case descriptions on LawBench), with three seeds per dataset, 12 iterations, and three candidate evaluations per iteration. The proposer calls TPS to plan its revisions. Each node of the plan graph is a candidate harness and each edge is a revision of its parent. The subagents predict how a revision would change the harness's behavior on training examples, and can extend a predicted candidate with further revisions. The solver picks which candidates to implement and evaluate within the per-iteration budget, and the resulting validation scores inform the next proposals.

Base Meta-Harness reaches 42.4% and plateaus. With TPS the proposer keeps finding improvements and reaches 45.9%. The curves cross along the way, so the claim is about the final best score within the budget, not about every step. It is a small experiment, but it shows the same planning tool moving from acting in an environment to searching over programs.

Future work

Open directions for the objective, the solver, the graph, and the search space.

• Soft targets inside hard limits. TPS enforces strict execution limits. Many tasks also have a preferred completion time, and the objective can take that in directly: keep the budget constraint and subtract a weighted penalty for exceeding the preferred target from the path score. The planner could then spend more time when the predicted gain in quality is worth the delay, and still never break the hard limit.
• A solver chosen per call. Selection is a plain optimization problem, and integer programming, resource-constrained shortest paths, constrained tree search, and greedy selection trade quality against runtime differently as graphs grow. The tool sees the task formulation and the graph before it solves, so choosing the solver from that structure is a natural next step.
• Better graphs. The graph-accuracy figure shows where predictions are weakest: reward prediction and state estimation on ALFWorld. A verifier subagent, environment feedback folded in while acting, or subagents trained on replayed states all plug into the same interface without touching the solver. Adapting the number of candidates and the simulation horizon to the compute available would make each call cheaper as well.
• Planning with exploration. Today the subagents build futures from the model's knowledge and the task history. When the dynamics are unknown, part of the same budget could go to actions that reveal them, so that knowledge acquisition and task progress share one interaction budget.
• Other search spaces. Harness optimization showed the tool planning over programs rather than environment actions. Prompts, tool sets, and agent workflows are search spaces of the same shape: a revision is an action, a candidate is a state, and evaluations are the budget.

References

1. Shunyu Yao et al. ReAct: Synergizing reasoning and acting in language models. ICLR 2023. arxiv.org/abs/2210.03629
2. Yuanhang Zheng et al. Budget-constrained tool learning with planning. Findings of ACL 2024. arxiv.org/abs/2402.15960
3. Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models: A critical investigation. NeurIPS 2023. arxiv.org/abs/2305.15771
4. Zehong Wang et al. Why reasoning fails to plan: A planning-centric analysis of long-horizon decision making in LLM agents. arXiv:2601.22311, 2026. arxiv.org/abs/2601.22311
5. Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1998.
6. John E. Beasley and Nicos Christofides. An algorithm for the resource constrained shortest path problem. Networks, 19(4), 1989.
7. Jongmin Lee, Geon-Hyeong Kim, Pascal Poupart, and Kee-Eung Kim. Monte-Carlo tree search for constrained POMDPs. NeurIPS 2018.
8. Alex L. Zhang, Tim Kraska, and Omar Khattab. Recursive language models. arXiv:2512.24601, 2025. arxiv.org/abs/2512.24601
9. Shunyu Yao et al. Tree of Thoughts: Deliberate problem solving with large language models. NeurIPS 2023. arxiv.org/abs/2305.10601
10. Yoonho Lee, Roshen Nair, Qizheng Zhang, Kangwook Lee, Omar Khattab, and Chelsea Finn. Meta-Harness: End-to-end optimization of model harnesses. COLM 2026.

BibTeX

arXiv preprint (coming soon)

@article{jeong2026tps,
  title         = {Integrating Tool-Guided Planning Subagents into Agent Harnesses as a Tool},
  author        = {Jeong, Jongwon and Kim, Jungtaek and Kang, Minki and Lee, Kangwook},
  journal       = {arXiv preprint arXiv:},
  year          = {2026},
  eprint        = {},
  archivePrefix = {arXiv},
  primaryClass  = {cs.AI},
  url           = {}
}

Jongwon Jeong

Ph.D. student at the University of Wisconsin–Madison, working on LLM/VLM agents.
Homepage More posts