- 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
-
How does TPS compare with representative planning-agent systems under the same backbone and comparable interaction and inference budgets?
-
Do the improvements persist with stronger backbones on text-world and coding tasks, and are they sufficient to justify the additional planning cost?
-
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
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.
| Benchmark | Backbone | Method | Success (%) | Gain (points) | Mean input tokens (k) | Mean output tokens (k) | Mean wall time (s) |
|---|---|---|---|---|---|---|---|
| ALFWorld | gpt-4.1-mini | ReAct | 38.8 | 25.7 | 0.6 | 14.4 | |
| ALFWorld | gpt-4.1-mini | ReAct + TPS | 78.4 | +39.6 | 136.7 | 7.2 | 47.6 |
| ALFWorld | gpt-4.1 | ReAct | 47.4 | 26.1 | 0.6 | 12.9 | |
| ALFWorld | gpt-4.1 | ReAct + TPS | 76.9 | +29.5 | 126.6 | 7.8 | 40.5 |
| AppWorld | Claude Haiku 4.5 | ReAct | 64.1 | 222.8 | 4.7 | 41.9 | |
| AppWorld | Claude Haiku 4.5 | ReAct + TPS | 71.9 | +7.8 | 635.9 | 37.9 | 199.1 |
| AppWorld | Claude Sonnet 5 | ReAct | 81.2 | 190.1 | 2.8 | 32.5 | |
| AppWorld | Claude Sonnet 5 | ReAct + TPS | 82.8 | +1.6 | 1,219.7 | 76.4 | 303.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.
| Benefit | Matched example | Result 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 accuracy | Sokoban | ALFWorld | Consequence |
|---|---|---|---|
| State merging | Precision 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 rewards | 97.1% of transitions correct | 78.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 replanning | 74 of 77 | 67 of 126 | The 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. |
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)
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.