acceptodds
Under review as a conference paper at ICLR 2027

Integrating Tool-Guided Planning Subagents into Agent Harnesses as a Tool

Abstract

While Language Model (LM) agents show remarkable performance on tasks requiring multiple interactions with the environment, their imperfect textual reasoning can produce plans that fail to satisfy task requirements. When environment interactions cannot be freely undone, acting on such plans can lead to irrecoverable failure under limited execution budgets. To mitigate this problem, we propose Tool-guided Planning Subagents (TPS), a plug-and-play planning tool for LM agents' harnesses. Specifically, TPS lets an LM agent delegate planning to subagents through a tool call when needed. It deliberately spends additional internal inference before acting to preserve the environment-execution budget. These subagents use an external solver to select a feasible plan. To provide the solver with an appropriate input, the subagents generate diverse candidate plans, simulate their consequences, and merge shared estimated states into an estimated plan graph. The solver then selects a path satisfying the remaining environment constraints within this graph. The selected plan guides the agent's next actions within its original interaction loop. Under the same environment-action budgets, TPS improves success rates by 38.7 and 25.2 percentage points on average across game and text-world benchmarks, respectively, and improves coding benchmark success by 6.2 points on average. We further demonstrate that TPS improves best mean validation accuracy by 3.5 percentage points in Meta-Harness under the same evaluation budget, extending its application to the harness-design process.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Model, Language Model Agent, Language Model Harness, Tool-integrated Planning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9GccOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes TPS, a planning tool that generates and simulates candidate plans, merges them into a graph, and uses an external solver to select a path under resource constraints. Experiments evaluate its integration into several agent harnesses across game, text-world, and coding tasks, with an additional application to harness optimization.

Critical strengths
  • TPS addresses a relevant practical problem: an agent may take actions that leave insufficient budget to complete a task, even if it later recognizes its mistakes. Separating LM-based prediction from constrained path selection is a reasonable approach to this problem, and exposing the planner as a tool makes it easier to integrate into existing agent harnesses.

  • The evaluation covers several types of tasks and multiple harness configurations. The reported gains on both structured games and more complex text-world and coding tasks provide useful evidence that the approach is not restricted to one particular environment. This breadth is valuable for a method presented as a reusable planning component.

  • The component ablations help assess whether the proposed components contribute beyond simply generating additional plans. In the Qwen3-14B experiment, success increases from 20% with Best-of-N to 29% with Graph+LM and 37% with TPS. The identical-graph comparison further supports the specific role of the external solver in finding feasible paths.

Critical weaknesses
  • The comparisons do not sufficiently establish the additional value of TPS over existing planning-agent approaches. Most experiments compare an existing harness, such as ReAct, with the same harness augmented by TPS. These results demonstrate that adding planning support can help, but leave unclear how TPS compares with systems that already incorporate planning, search, verification, or replanning. Single Plan and Best-of-N are useful controls, but stronger comparisons with representative planning-agent systems, using the same backbone and comparable interaction and inference budgets, are needed to assess the proposed framework's contribution.

  • The choice of backbones makes the broader effectiveness of TPS difficult to judge. The main task-agent experiments predominantly use GPT-4.1-mini and Claude Haiku 4.5, with particularly low baseline performance in some settings. This leaves open whether the large improvements mainly compensate for the planning limitations of these models. The GPT-5-nano experiment provides some additional evidence, but only on Sokoban, where the improvement is much smaller, from 90% to 96%. Stronger-backbone results on representative text-world and coding tasks would help clarify whether the benefits generalize and justify the additional planning overhead.

  • The main-text analysis relies heavily on describing quantitative results and then restating them as takeaway statements. There are seven such statements, but several provide little interpretation beyond what is already visible in the figures and tables. Although the appendix contains execution examples and failure analyses, the main discussion does not sufficiently use them to explain which errors TPS resolves, when graph merging or solver-based selection is necessary, and why the benefits vary across tasks. This presentation makes it difficult to develop a clear understanding of the method's practical strengths and limitations despite the amount of experimental material.

Questions for authors
  1. How does TPS compare with representative planning-agent systems under the same backbone and comparable interaction and inference budgets?

  2. Do the improvements persist with stronger backbones on text-world and coding tasks, and are they sufficient to justify the additional planning cost?

  3. Can the authors connect matched success and failure examples to the roles of graph merging and solver-based selection, explaining when these components help beyond simpler planning alternatives?

6 comments

We thank the reviewer for recognizing the practical problem that TPS addresses and the value of the component ablations. Below, we respond point by point, connecting the comparisons to concrete execution examples.


W1 & Q1 (Comparisons with planning agents)

W1. The comparisons do not sufficiently establish the additional value of TPS over existing planning-agent approaches. Most experiments compare an existing harness, such as ReAct, with the same harness augmented by TPS. These results demonstrate that adding planning support can help, but leave unclear how TPS compares with systems that already incorporate planning, search, verification, or replanning. Single Plan and Best-of-N are useful controls, but stronger comparisons with representative planning-agent systems, using the same backbone and comparable interaction and inference budgets, are needed to assess the proposed framework's contribution

Q1. How does TPS compare with representative planning-agent systems under the same backbone and comparable interaction and inference budgets?

We thank the reviewer for recognizing the practical problem that TPS addresses and the value of the component ablations. Below, we respond point by point, connecting the comparisons to concrete execution examples.

We thank the reviewer for requesting direct comparisons with planning agents under comparable budgets. Our evaluation includes ToT, a representative planning agent that already incorporates planning, search, and replanning. At every step, ToT proposes candidate action sequences, evaluates them with the LM, keeps the best ones by beam search, and searches again from the new observation. Table R3 reorganizes the existing Sokoban results for comparison under the same backbone and action budget. These methods use gpt-4.1-mini and B = T* + 2, and their success rates are already reported in Figure 3. The additional Sokoban experiment is ReAct + self-reflection, which adds verification as one LM review of each proposed action before execution.

ReAct + TPS reaches higher success than ToT, a harness that already performs search, at a similar episode time. ReAct + TPS reaches 70% success at 71.9 seconds, compared with 29% at 70.4 seconds for standalone ToT. Adding TPS to ToT further raises its success from 29% to 93%, with mean episode time increasing from 70.4 to 217.4 seconds. These results show both the benefit of integrating TPS into ToT and the success--latency trade-off of using TPS with ReAct. Appendix C.3 describes the ToT integration; similar observed latency does not establish matched inference compute.

Table R3. Direct planning-agent comparison on Sokoban using gpt-4.1-mini and the action budget B = T* + 2.

MethodSuccess (%)Mean actionsMean wall time (s)
ReAct87.547.6
ToT (b = 2, d = 3)297.2070.4
ReAct + self-reflection107.7014.6
ReAct + TPS706.4871.9
ToT + TPS936.22217.4

W2 & Q2 (Backbone strength & planning overhead)

W2. The choice of backbones makes the broader effectiveness of TPS difficult to judge. The main task-agent experiments predominantly use GPT-4.1-mini and Claude Haiku 4.5, with particularly low baseline performance in some settings. This leaves open whether the large improvements mainly compensate for the planning limitations of these models. The GPT-5-nano experiment provides some additional evidence, but only on Sokoban, where the improvement is much smaller, from 90% to 96%. Stronger-backbone results on representative text-world and coding tasks would help clarify whether the benefits generalize and justify the additional planning overhead.

We thank the reviewer for asking whether the improvements persist with stronger backbones. We respectfully note that the improvement from 90% to 96% with GPT-5-nano is a 60% reduction in the failure rate, from 10% to 4%. ReAct already reaches 90% success in this setting, so at most 10 percentage points of improvement are possible, and TPS closes 60% of that gap, as shown in Figure 8 (Figure 7 in the original submission).

Q2. Do the improvements persist with stronger backbones on text-world and coding tasks, and are they sufficient to justify the additional planning cost?

To examine text-world and coding tasks, we ran ReAct with and without TPS using gpt-4.1 on ALFWorld and Claude Sonnet 5 on AppWorld. Due to evaluation cost, AppWorld uses a 64-task subset. In Table R4, we found that TPS improves success with the stronger backbone on both benchmarks. On ALFWorld, ReAct with gpt-4.1 still fails in 52.6% of the episodes, and TPS reduces the failure rate to 23.1%. On AppWorld, ReAct with Claude Sonnet 5 already reaches 81.2% success, and the gain decreases from 7.8 points with Claude Haiku 4.5 to 1.6 points.

Table R4. ReAct with and without TPS across backbones.

BenchmarkBackboneMethodSuccess (%)Gain (points)Mean input tokens (k)Mean output tokens (k)Mean wall time (s)
ALFWorldgpt-4.1-miniReAct38.825.70.614.4
ALFWorldgpt-4.1-miniReAct + TPS78.4+39.6136.77.247.6
ALFWorldgpt-4.1ReAct47.426.10.612.9
ALFWorldgpt-4.1ReAct + TPS76.9+29.5126.67.840.5
AppWorldClaude Haiku 4.5ReAct64.1222.84.741.9
AppWorldClaude Haiku 4.5ReAct + TPS71.9+7.8635.937.9199.1
AppWorldClaude Sonnet 5ReAct81.2190.12.832.5
AppWorldClaude Sonnet 5ReAct + TPS82.8+1.61,219.776.4303.0

Regarding the planning cost, the additional cost is LM inference inside the planning call, and it is worthwhile where the base agent still fails and a failed execution is costly. Table R4 reports the token usage and elapsed time of each setting. TPS targets tasks with tight execution budgets or irreversible state changes, where a planning error can make the task impossible to complete. Where the base agent already solves most tasks, as with Claude Sonnet 5 on AppWorld, the additional planning brings a small gain for its cost.

In the revised paper, the stronger-backbone results with token usage and elapsed time are in Appendix F.6 (Table 17), and Section 6 refers to them.

W3 & Q3 (Connecting component roles to execution examples)

W3. The main-text analysis relies heavily on describing quantitative results and then restating them as takeaway statements. There are seven such statements, but several provide little interpretation beyond what is already visible in the figures and tables. Although the appendix contains execution examples and failure analyses, the main discussion does not sufficiently use them to explain which errors TPS resolves, when graph merging or solver-based selection is necessary, and why the benefits vary across tasks. This presentation makes it difficult to develop a clear understanding of the method's practical strengths and limitations despite the amount of experimental material.

Q3. Can the authors connect matched success and failure examples to the roles of graph merging and solver-based selection, explaining when these components help beyond simpler planning alternatives?

We thank the reviewer for this suggestion. In short, TPS helps when the plan graph contains a correct plan that is hard to select under a limited budget, and its remaining failures arise mainly when the graph lacks such a plan or predicts it inaccurately.

1. Benefits of TPS

TPS avoids the planning errors of Section 1, with graph merging making a correct plan available and solver-based selection finding it. Section 5 already reports the component comparisons and the budget analysis (Tables 1 and 2, Figure 5). To connect them to examples, the new Section 7 explains the advantages of the plan graph and the external solver with a qualitative example for each (Figure 6), and Appendix E.8 adds a comparison with ReAct (Figure 12). Table R5 pairs each benefit with its example and result.

Table R5. Benefits of TPS, each with a matched example and the location of its result in the paper.

BenefitMatched exampleResult in the paper
TPS avoids the planning errors of Section 1, which make the goal unreachable or leave too few actions to finish.On the same Sokoban instance, ReAct's third action pushes the box away from the goal and leaves 4 actions for a goal that needs 6. With TPS, the agent follows the selected plan and reaches the goal in 5 of 7 actions (Figure 12, Appendix E.8).Figure 5(c), Section 5. Episodes that lose budget feasibility drop from 91 to 29 of 100 at T* + 2.
Graph merging makes a correct plan available where Single Plan and Best-of-N have none.In a qualitative example on Sokoban, all four candidates fail. The merged graph links the first five actions of one candidate (DDLUL) to the final push of another (D), and the selected plan reaches the goal (Figure 6a).Table 1, Section 5. Best-of-N reaches 20%, and TPS reaches 37% with the merged graph and the solver.
Solver-based selection finds a feasible path that Graph + LM misses.On the same 30-node graph, one of the LM misses in Table 2, the LM-selected route creates a deadlock at its seventh action, and the ILP-selected route reaches the goal when executed (Figure 6b).Tables 1 and 2, Section 5. On graphs with at least 21 nodes, the LM finds 22 of 26 feasible paths and ILP finds all 26. Replacing LM selection with the solver raises success from 29% to 37%.

2. Why the benefits vary across tasks

The benefits follow how accurately the graph is built. Section 6 and Appendix F.1 (Tables 12 and 13) already report the graph accuracy, and Appendix F.2 already reports the execution of selected plans. Section 6 now connects the two, stating that most selected plans reach the real goal on Sokoban, compared with about half on ALFWorld. Table R6 relates each measurement to its consequence.

Table R6. Graph accuracy and its consequence.

Measured accuracySokobanALFWorldConsequence
State mergingPrecision 99.7%, recall 75.4%Precision 92.4%, recall 41.3%Merging rarely introduces an invalid path, and on Sokoban it retains every correct candidate plan (76 of 76 calls). Lower recall leaves equivalent states separate, so links across candidates arise less often.
Simulation and rewards97.1% of transitions correct78.9% of actions applicable, goal-label precision 60.2%A wrong transition or goal label leads the solver to a plan that fails in the real environment.
Selected plans that reach the real goal when executed without replanning74 of 7767 of 126The gains in Figure 3 follow the same order, with ReAct improving from 8% to 70% on Sokoban and from 38.8% to 78.4% on ALFWorld.
Reviewer_BmrcOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Tool-guided Planning Subagents (TPS), a plug-and-play planning tool for language model (LM) agents operating under tool-use frameworks. TPS allows LM agents to delegate planning to subagents via tool calls, which internally generate and simulate multiple candidate plans, aggregate their predicted outcomes into a plan graph, and then use an external solver to select a feasible plan that satisfies task constraints and remaining action budgets. This approach aims to reduce irreversible failures caused by imperfect LM reasoning, especially when environment interactions are costly or irreversible. Experiments across game, text world, and coding benchmarks show that integrating TPS significantly improves average success rates compared to baseline agent frameworks under the same execution budgets. The method also demonstrates higher efficiency in action usage and more reliable feasible plan selection via external solvers.

Critical strengths

The writing is well-organized, the theoretical analysis is sound, and the experimental results support the authors' claims.

Critical weaknesses

The approach proposed in this paper is not particularly novel, and the method of selecting plans and the number of graph nodes may not be very practical in real-world applications. Besides, solvers are hard to produce planning results that align with human priors, and the robustness to constraints appears to be quite weak.

Questions for authors

a) what is the rationale for the selection of these experimental datasets? If the focus is on strong planning scenarios, why not use more complex agentic benchmarks such as Terminal-Bench b) how can the approach be extended to more scenarios where vague natural language instructions need to be translated into explicit conditional constraints

2 comments

We thank the reviewer for noting that the writing is well-organized and that the experimental results support our claims. Below, we address each concern by clarifying the contributions of TPS and the existing results.


W1 (Novelty)

W1. The approach proposed in this paper is not particularly novel,

We appreciate the comment on the novelty and practicality of TPS. However, we respectfully disagree that this paper is not particularly novel.

The novelty we claim is a planning framework that turns LM-generated candidate plans into a shared search space for solver-based planning before execution, reducing the risk of planning errors that lead to irrecoverable failure. By merging shared predicted states, TPS can construct a successful path even when none of the individual candidates succeeds, as illustrated in Figure 6a. The solver then selects paths satisfying the constraints represented in that graph, finding feasible paths that LM selection misses on identical inputs (Figure 6b; Table 2 and Table R2). This combines candidate recombination with constrained selection without requiring a predefined formal environment model. The selected natural-language plan is returned through a tool interface within the existing agent harness. Table R1 shows higher observed success than the simpler planning alternatives on ALFWorld and AppWorld, providing evidence of the framework's benefit beyond games.

The method of selecting plans and the number of graph nodes may not be very practical in real-world applications.

We respectfully note that we already report TPS's effectiveness on realistic tool-based benchmarks, including AppWorld, Terminal-Bench, and MLGym-Bench, in Section 4. These results support the practical use of LM-generated plan graphs as inputs for solver-based planning. Once a graph is constructed, the solver finds feasible paths more reliably than LM selection: on identical predicted graphs containing a feasible path, ILP finds one in every evaluated case, whereas the LM sometimes misses it (Table 2, Table R2). The revised paper also shows a qualitative example of this difference (Figure 6b).

Regarding solver efficiency, Appendix E.5 already shows that solver-based selection remains fast across the evaluated graph sizes. On 8,461 Sokoban graphs from an earlier experimental pipeline, ranging from 1 to 80 nodes, ILP takes 2.4–9.7 ms per call across size groups, and RCSP takes less than 0.1 ms. These results indicate that solver execution adds little overhead relative to LM inference.


Q1 (Benchmark selection)

Q1. what is the rationale for the selection of these experimental datasets? If the focus is on strong planning scenarios, why not use more complex agentic benchmarks such as Terminal-Bench?

We respectfully note that Section 4 already includes Terminal-Bench 2.0, AppWorld, and MLGym-Bench to evaluate TPS in complex agentic tasks (Figure 4).

Our benchmark selection follows the evaluation objectives already described in Section 4. These benchmarks evaluate multi-step planning across game, text-world, and coding tasks, consistent with the focus in Section 1 on planning errors that can prevent completion within limited execution budgets. Game tasks support controlled analysis of planning errors and remaining budgets, with Sokoban enabling oracle-based checks of budget feasibility (Section 5). We have made this reason explicit at the beginning of Section 5. Text-world tasks assess transfer to household and science environments requiring subgoal ordering and prerequisites, while coding benchmarks assess transfer to shell, API, and machine-learning workflows that reflect real-world use cases.


W2 (Human priors & constraint robustness)

W2. Besides, solvers are hard to produce planning results that align with human priors,

We respectfully clarify that TPS's solver selects and combines natural-language subplans generated by the LM, so the resulting plan remains human-interpretable (Section 3). The solver uses LM-simulated outcomes and LM-predicted rewards and costs to select a plan. To the extent that these predictions reflect task-relevant human priors, those priors also guide solver-based selection. The qualitative planning examples in Figure 1 and Appendix D.2 (Table 7) provide support for this interpretation.

The robustness to constraints appears to be quite weak

We respectfully note that Figure 5(a) already shows higher success rates with TPS across all four evaluated Sokoban action budgets, with the largest relative gains under the two tightest limits. Specifically, at T* + 2 and T* + 4, TPS achieves 70% and 74% success, respectively, compared with 8% for ReAct at both budgets. Table 9 also shows fewer failures caused by insufficient remaining actions across all tested budgets, supporting TPS's ability to preserve sufficient budget for task completion.

Q2 (Vague natural language instructions)

Q2. how can the approach be extended to more scenarios where vague natural language instructions need to be translated into explicit conditional constraints

Thank you for the question. We respectfully clarify that translating vague natural-language instructions into explicit conditional constraints is beyond the scope of the current paper. As described in Sections 1 and 3 and Appendix C, our work addresses planning under explicit interaction constraints, such as action limits and task timeouts.

Nevertheless, Appendix I already discusses incorporating soft preferences into solver-based planning as a future direction. This offers a possible extension for vague preferences such as "finish quickly if possible": after clarifying a preferred completion time, the solver could penalize delays beyond that target while retaining strict resource limits. Handling mandatory conditionals would further require encoding the relevant conditions in graph states, preserving them during merging, and enforcing them during path selection.

Reviewer_zPFFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes TPS, a planning tool that can be added to existing LLM-based agents. Planning subagents generate candidate plans, predict their outcomes, and merge shared states into an estimated graph. An external solver then selects a path that satisfies the remaining budget constraints. Experiments across eight game, text-world, and coding-agentic benchmarks show improved success under the same environment-execution limits.

Critical strengths
  • TPS provides a practical planning interface for existing agents without replacing their interaction loops. Assigning candidate generation and outcome prediction to the LLM, while using a solver for budget-constrained path selection, makes useful use of their different capabilities.

  • The evaluation covers multiple harnesses and eight benchmarks, with substantial gains on Sokoban and ALFWorld. Component comparisons on Sokoban and LM–solver comparisons on identical graphs provide further evidence for graph organization and external path selection. The paper also reports prediction errors and additional inference costs.

Critical weaknesses

The evidence for TPS as a broadly applicable planning tool is incomplete. Direct comparisons with Single Plan, Best-of-N, and Graph + LM are limited to Sokoban, where the component experiments use ten short maps with ten repetitions each. On text-world and coding tasks, the main success-rate comparisons show the benefit of adding TPS, but do not establish whether the full TPS design is better than these simpler planning methods. Since TPS adds internal inference, additional computation may also contribute to the gains. Including these comparisons on representative text-world and coding tasks, with comparable inference budgets where possible, would better support the method’s broad applicability.

Questions for authors
  • Could the authors compare TPS with Single Plan, Best-of-N, and Graph + LM on representative text-world and coding tasks, using comparable inference budgets where possible? How much of the improvement remains over these simpler methods in those domains?

  • Figure 7 shows a smaller gain from TPS for GPT-5-nano, from 90% to 96% success. Does this suggest that TPS becomes less useful as the base model’s planning ability improves? How do the authors expect TPS to remain useful as models continue to improve, and how much of this result reflects a ceiling effect?

2 comments

We thank the reviewer for recognizing TPS as a practical planning interface for existing agents and the breadth of our evaluation. Below, we address each point with the added experiments.

W1 & Q1 (Beyond Sokoban Task's ablation study)

W1. The evidence for TPS as a broadly applicable planning tool is incomplete. Direct comparisons with Single Plan, Best-of-N, and Graph + LM are limited to Sokoban, where the component experiments use ten short maps with ten repetitions each. On text-world and coding tasks, the main success-rate comparisons show the benefit of adding TPS, but do not establish whether the full TPS design is better than these simpler planning methods. Since TPS adds internal inference, additional computation may also contribute to the gains. Including these comparisons on representative text-world and coding tasks, with comparable inference budgets where possible, would better support the method’s broad applicability.

Q1. Could the authors compare TPS with Single Plan, Best-of-N, and Graph + LM on representative text-world and coding tasks, using comparable inference budgets where possible? How much of the improvement remains over these simpler methods in those domains?

We appreciate the suggestion to extend the component comparisons beyond Sokoban. To address this, we compared Single Plan, Best-of-4, Graph + LM, and TPS on ALFWorld (text-world tasks) and AppWorld (API-based coding-agent tasks). We used gpt-4.1-mini and Claude Haiku 4.5, respectively. Due to evaluation costs, all AppWorld methods in Table R1 use the same 64-task subset, which contains the 37 tasks on which ReAct failed in the main evaluation and 27 on which it succeeded.

We found that TPS exceeds the strongest simpler baseline by approximately 3.8 percentage points on ALFWorld (Best-of-4) and 4.7 points on AppWorld (Single Plan), as shown in Table R1. It also uses fewer environment actions on ALFWorld and a similar number on AppWorld. This ablation study on two additional benchmarks can support our claim in Section 5 beyond Sokoban.

Table R1. Success rates and mean environment actions in the added planning comparisons.

MethodALFWorld success (%)ALFWorld actionsAppWorld success (%)AppWorld actions
Single Plan70.19.467.221.19
Best-of-474.69.262.520.98
Graph + LM73.19.065.621.34
TPS78.48.571.921.55

In addition to the success rate comparison, we examined whether additional computation explains the gain. We found that with matched LM usage, TPS still reaches higher success than Graph + LM on AppWorld and Best-of-N on ALFWorld. On AppWorld, TPS improves success from 65.6% to 71.9% over Graph + LM, while mean input and output token counts per episode each differ by less than 1%. On ALFWorld, we increased the number of candidates in Best-of-N from 4 to 32, so that each planning call uses at least as many input and output tokens as a TPS planning call. Best-of-32 does not improve over Best-of-4 (70.5% versus 74.6%) and remains below TPS (78.4%), as shown in Table R1b. These results support that the gain of TPS does not come from additional computation alone.

Table R1b. Success and LM usage per planning call on ALFWorld.

MethodSuccess (%)LM callsInput tokens (k)Output tokens (k)
Best-of-474.69.012.51.1
Best-of-3270.565.087.67.8
TPS78.432.685.45.4

To further verify the external solver's contribution, we compared LM and ILP selection using identical predicted graphs containing a feasible goal path. We found that ILP finds feasible paths that LM selection misses, without additional LM predictions (Table R2). These results are consistent with Table 2 & 10 and extend it to both added domains. This result also supports the solver's contribution without attributing the entire Table R1 gain to selection alone.

Table R2. Feasible-path finding, conditional on a feasible path being present in the predicted graph.

BenchmarkLM selectionILP selection
Sokoban93.8%100%
ALFWorld95.5%100%
AppWorld97.4%100%

In the revised paper, the ALFWorld comparison is in Appendix D.4 (Table 8) and the feasible-path results on ALFWorld and AppWorld graphs are in Appendix E.4, and the ablation study in Section 5 refers to both.

Q2 (TPS effectiveness with stronger models)

Q2. Figure 7 shows a smaller gain from TPS for GPT-5-nano, from 90% to 96% success. Does this suggest that TPS becomes less useful as the base model’s planning ability improves? How do the authors expect TPS to remain useful as models continue to improve, and how much of this result reflects a ceiling effect?

Thank you for raising this question. We agree that higher baseline success leaves less room for absolute improvement. The absolute benefit is smaller in this setting, where only 10 percentage points of improvement are possible. However, TPS still reduces GPT-5-nano's observed failure rate by 60%, from 10% to 4%, as shown in Figure 8 (Figure 7 in the original submission). The observed 6-point gain closes 60% of the remaining gap, showing an improvement in execution reliability on this evaluation.

We expect that TPS can remain useful when tight execution budgets or irreversible state changes make a missed feasible plan costly. TPS searches for a complete path satisfying the constraints represented in the predicted graph before execution. This expectation is conditional: as a model reliably performs this planning itself, the marginal benefit can decrease. Better predictions may improve the graphs available to the solver, but the future gain will depend on both model capability and task demands. We have added this interpretation next to Figure 8 in Appendix D.1, together with the failure types of both configurations.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response

We thank the reviewers for their time, effort, and constructive feedback, which have strengthened this work. We are encouraged that the reviewers found TPS a practical planning tool that integrates into existing agent harnesses [zPFF, 9Gcc], the evaluation broad across harnesses and benchmarks [zPFF, 9Gcc], and the experimental results supportive of our claims [Bmrc]. We also appreciate that the reviewers engaged closely with the paper and provided detailed suggestions on component comparisons beyond Sokoban [zPFF, 9Gcc], stronger backbones and planning cost [zPFF, 9Gcc], and the connection between the analysis and execution examples [9Gcc], together with questions on novelty and benchmark selection [Bmrc]. These suggestions helped sharpen both the empirical support and the presentation of the paper.

Below we summarize the key clarifications added during the rebuttal:

  • TPS improves success beyond simpler planning alternatives [zPFF, 9Gcc]. TPS achieves the highest observed success among Single Plan, Best-of-4, and Graph + LM on ALFWorld and AppWorld (Table R1). On AppWorld, TPS reaches 71.9% versus 65.6% for Graph + LM, while mean input and output token counts each differ by less than 1%. ReAct + TPS also reaches higher success than ToT, a harness that already searches, at a similar episode time on Sokoban (70% versus 29%), and adding TPS to ToT raises its success to 93% with additional planning computation (Table R3).
  • The external solver contributes beyond LM selection and is practical [zPFF, Bmrc, 9Gcc]. On identical predicted graphs containing a feasible path, ILP finds one in every evaluated case, while the LM misses some, across Sokoban, ALFWorld, and AppWorld (Table R2). The solver takes a few milliseconds per call, so it adds little overhead relative to LM inference.
  • The gains from TPS persist with stronger backbones and become smaller as the base agent becomes stronger [zPFF, 9Gcc]. With GPT-5-nano on Sokoban, where ReAct already reaches 90% success, TPS reduces the failure rate by 60%. With gpt-4.1 on ALFWorld and Claude Sonnet 5 on AppWorld, the gains are 29.5 and 1.6 points, compared with 39.6 and 7.8 points with the weaker backbones (Table R4).
  • The plan graph and the external solver have distinct roles, and the unresolved cases are identified [9Gcc, Bmrc]. We connected the ablation to qualitative examples, where the plan graph increases path coverage and the external solver avoids a selection error (Table R5). Three cases remain unresolved, namely no correct candidate plan, unclear task or environment information, and an agent that does not follow the selected plan.

In addition, we updated the manuscript as follows, with all changes marked in blue:

  • We added Section 7 (Discussion) to explain the advantages of the plan graph and the external solver with qualitative examples (Figure 6) and the cases that TPS does not resolve (Table 5) [9Gcc W3, Q3; Bmrc W2].
  • We added Appendix D.4 (Table 8) to report the component comparison on ALFWorld [zPFF W1, Q1].
  • We extended Appendix E.4 with the identical-graph comparison on ALFWorld and AppWorld and a qualitative example [zPFF W1, Q1; Bmrc W1].
  • We added Appendix F.6 (Table 17) to report the stronger-backbone results with token usage and elapsed time [9Gcc W2, Q2], and extended Appendix D.1 with the failure types for GPT-5-nano [zPFF Q2].

Again, we appreciate the reviewers again for the constructive insights that helped improve the clarity and the supporting evidence of this work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.