acceptodds
Under review as a conference paper at ICLR 2027

Analyzing Agentic benchmarks under subgoal interactions

Abstract

Tool-calling is a core function of LLM agents, and a plethora of benchmarks attempt to evaluate it. These benchmarks divide into stateful benchmarks, where tool calls operate on shared state such as a database or environment, and stateless benchmarks, where a composition of tools computes or retrieves a value. Stateful benchmarks such as TauBench, AppWorld, and AgentBench turn out to be ergodic, or are ergodified by the harnesses agents run in, and so mask a failure mode studied extensively in the AI planning literature: negative subgoal interaction. In ergodic environments, negatively interacting subgoals increase the cost of achieving one another; in non-ergodic environments, they can make the goal unreachable entirely. While AI planning has studied this concept at length, no study has examined how it affects agentic planning. We introduce PlanBench-Gym, an interactive, tool-calling extension of PlanBench that evaluates LLM agents on PDDL Blocksworld instances constructed along a three-way taxonomy of no-interaction, positive-interaction, and negative-interaction goal structure. Even though these instances remain ergodic under our construction, we find that state-of-the-art reasoning models struggle with negative interactions, though the degree varies: closed source models such as GPT-5.2 fails outright on negative-interaction tasks under most agent scaffolds, while Claude Sonnet 5 completes them but at a measurable efficiency cost. Additional experiments on open-source models mirror the finding with Claude Sonnet 5, where Qwen3.6, GLM5.2, and Gemma4 are able to consistently solve tasks, but do so at a measurable efficiency cost. We further find that prompting mode, whether an agent observes its full interaction history or only the current state, has a substantial effect on completion, independent of interaction class.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Agents, 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_LtQAOpenReview ↗
Rating
1
Confidence
3
Informativeness
2(+1)
Presentation
2(+1)
Soundness
1
Read review
Paper summary

This paper introduces PlanBench Gym -- a tool call wrapper for PlanBench. The setup works as follows: an LLM-backed agent executes some actions on Blocksworld tasks, a classic planning domain defined in PPDL (Planning Domain Definition Language) where agents must rearrange blocks to achieve desired configurations, receives feedback in the form of natural language, and continues to interact with the environment until either it achieves the original goal or consume its step budget.

The authors center this paper around the idea of “ergodicity” (an agent’s property to reach any next state from any current state, implying reversibility in their actions), arguing that existing agentic benchmarks are more likely than not ergodic. They classify subgoal interactions into three categories based on how the achievement of a subgoal directly impacts the cost of achieving others: no interaction (no change), positive interaction (reduces costs), and negative interaction (increases costs). The authors evaluate models across different configurations along two different axes: the agent harness (i.e., prompted ReAct, hybrid ReAct, and native tool calling) and the context fetched to the agent (either just the current state, or the full history of states’ interactions).

The three key findings of the paper are that (1) agent scaffolding plays an important role, specifically prompted ReAct outperforms both hybrid and native, across different models/configurations; (2) GPT-5.2 struggles to deal with negative subgoal interactions, to the extent that it even fails the easier tasks that are easily completed by the other models; (3) context management is extremely model-dependent, with some models (e.g., Sonnet 5) benefiting from only the current state (quite counterintuitive) and others (e.g., Qwen 3.6) benefitting from the full-interaction history. Although these differences are clear and explicitly observed, the core reasoning behind them is not properly investigated.

Critical strengths
  • The work centers around the relevant question of whether benchmarks accurately assess planning failures since mistakes can be undone.

  • PDDL provides an explicit and inspectable causal structure, addressing limitations of benchmarks where dependencies are embedded in natural language or tool code.

  • The instance generator validates candidates using Fast Downward, and the plan-length padding scheme effectively scales difficulty without altering class definitions.

  • Separating scaffolding from action elicitation (Prompted vs. Hybrid vs. Native) provides useful experimental control, with prompts clearly documented.

  • The work centers around the relevant question of whether benchmarks accurately assess planning failures since mistakes can be undone.

  • PDDL is a good structured approach for inspecting this problem, because it isn’t subject to the limitations of other benchmarks that put dependencies in language or tool code.

  • The benchmark is generally designed well, especially in how instances were generated and difficulty was controlled:

    • the instance generator relies on the Fast Downward algorithm in order to validate candidate moves/instances;
    • the difficulty of the instance is able to be scaled effectively via the padding scheme, without needing to alter the class definitions.
  • Separating scaffolding from action elicitation (Prompted vs. Hybrid vs. Native) provides useful control and helps to isolate the causes of their results

Critical weaknesses

I generally find the paper evaluation not to be rigorous. I enumerate my soundness concerns first and then the general issues/nits.

1/ Mismatched definition for negative interactions: the paper’s cost definition C(AND g_i) > sum c(g_i) is not satisfied by the negative interaction class in unit cost Blocksworld (e.g., tower variant should be in the no interaction case, given that each subgoal takes two actions, pick up and stack, and their joint optimal plan takes four). A similar issue applies for the Sussman variant (but please correct me if I’m wrong).

1.1/ Why claim this is for planning and PDDL and then only test on Blocksworld, when there are other domains too that could strengthen evaluation

2/ In Section 4, all three classes cost exactly two steps per subgoal, which implies additivity for the negative class. However, verification only checks cost inequalities for positive instances and only solvability for negative instances. This is not effective because all instances are solvable. Instead, these instances test goal ordering or non-serializability (Korf; Barret & Weld). Overall, from 1-3, it seems like the formal definitions are not correct here.

3/ Confounding across classes: Performance drop in negative tasks may stem from tower depth or chain reasoning, not subgoal interaction, because no-interaction instances consist of disjoint pairs, whereas negative instances involve single chained towers, I think there are some papers discussing this issue recently in broader context.

4/ Harness bugs - there are some big score drops that seem anomalous to me - integration or harness issues, such as: Claude Sonnet 5 drops from 100% (current-state) to 0 to 10% (full-history) on positive and negative tasks, Gemma 4 Native current-state scores 2% on no-interaction, which is a trivial task, GPT-5.2 Hybrid full-history scores 0% on every class, including no-interaction.

Without trajectory error analysis, it is difficult to determine whether these results reflect model capabilities or harness artifacts.

5/ Significant overclaiming:

  • "Prompted ReAct is the strongest scaffold across all models, interaction classes, and context management modes"
    • no, i see Prompted scores 2/0/0 and is the worst scaffold for at least one mode
  • "GPT-5.2 fails outright under most scaffolds" and "solves 0% of negative-interaction instances at any step budget"
    • Varies by configuration, e.g. GPT-5.2 reaches 58% under Prompted full-history
    • The headline here is therefore an artifact of configuration choice.
  • "All complete negative-interaction tasks with reasonable consistency"
    • Not true for Qwen 3.6 current-state native or hybrid
  1. Efficiency metric limitations: You measure subopt only over complete runs -- my instinct is this would cause survivorship bias, since the ratio is capped at 2 by design. The gap is only 1.09x at most and without confidence intervals and given small sample size, isn’t conclusive.

General paper problems:

1/ The paper is in a weird place, where it generally reads like significant portions were generated by artificial intelligence without a human in the loop, but is written poorly enough in places that I don’t think any existing frontier tool would write so poorly. The excessive repetition of the term ergodic also stands out to me as natural writing would not repeat it so much or define it far more clearly.

2/ Lots of prior work and terms are used without citation throughout the introduction. There is one cite in all of page 2. Hugging face incident is not cited, Sokoban is not cited, many more examples. Very small number of references in general. PDDLGm is not cited. Back-prompting as a field is generally not included. Logistics is not evaluated at all.

3/ Organization is odd. Why is related work before background? It is very hard to situate the related work before hearing about the background. Also, why not have any planning work in related work?

4/ The title references analyzing existing agentic benchmarks but there’s a new benchmark without good eval of preexisting ones.

Questions for authors
  1. Are tool call rejections accounted in the consumption of the step budget? And what about in the suboptimality ratio?
  2. Could you provide an explanation of Claude’s collapse under the full-history condition, and regarding Gemma’s 2% score on no-interaction under native current-state?
  3. Could you make explicit how many samples per instances were run, and their settings (e.g., temperature, reasoning-effort, …)?
6 comments
AuthorsOpenReview ↗

Modified the Negative Interaction definition

We thank the reviewer for their detailed and critical review. We would like to provide clarifications below.

W1 Mismatched definition for negative interactions

W2 Inconsistent verification pipeline

W3 Structural confounding across classes

The cost inequality definition is a sufficient, but not necessary, condition for negative interaction. The Tower and Sussman anomaly instances exhibit negative interaction under the ordering/serializability-based definition in Korf's taxonomy. Accordingly, we have revised the definitions of subgoal interaction in the paper based on Korf's taxonomy [1] (see Section 2).

Under these definitions, a set of subgoals is considered serializable if there exists an ordering of the subgoals such that they can be solved sequentially without violating any previously achieved subgoal. However, certain subgoal orderings may lead to increased solution costs compared to the optimal cost, even when an ideal ordering would yield an additive solution cost. The Tower problem instances fall into this category.

In contrast, a set of subgoals is considered non-serializable if achieving further progress toward the main goal necessarily requires violating at least one previously satisfied subgoal, regardless of the ordering in which the subgoals are attempted. The Sussman anomaly problem instances fall into this category.

Based on these definitions, we further categorize negative interaction problem instances into two subcategories: (1) serializable problem instances, represented by the Tower problems, and (2) non-serializable problem instances, represented by the Sussman anomaly problems.

The table below presents the results for these two subcategories of negative interaction problem instances using the Claude Sonnet 5 model with Prompted-ReAct scaffolding and the current-state context setting. The results show that, under this setting, the agent solves all Tower problems optimally. However, for the Sussman anomaly problems, although the model achieves a 100% solve rate, it generates suboptimal plans, with a mean suboptimality ratio of 1.18. This indicates that, on average, the agent performs 4 redundant actions compared to the optimal plan length. (Note: the values in parentheses show the range.)

Problem typeSolve rate (%)Suboptimality ratioRedundant actions
Serializable (Tower)100 (25/25)1.000
Non-serializable (Sussman)100 (25/25)1.18 (1.00–1.27)4 (0–6)

We have included the same analysis for the other models, agent scaffolding approaches, and both context settings (current-state and full-history) in the paper (see Section 5).

AuthorsOpenReview ↗

Evaluation on Non-ergodic domain

There are many other relevant PDDL domains that could have been tested.

We have now extended our evaluation to another PDDL domain, the Sokoban environment. Unlike Blocksworld, Sokoban is a non-ergodic environment in which the agent cannot reverse certain actions once it reaches a dead-end state. For example, pushing a box into a corner can make the problem permanently unsolvable. This environment therefore provides a more realistic assessment of the agent's actual solvability rate. In contrast, Blocksworld is an ergodic environment in which, given a sufficiently large step budget, even a random walk can eventually reach the goal state.

We incorporated the Sokoban environment into the PlanBenchGym benchmark. The Sokoban problem instance generator is built on top of DeepMind's Boxoban [2] and it generates problem instances using the reverse-play algorithm [3]. For our evaluation, we generated 20 problem instances on a 1010 grid, varying the number of boxes from 2 to 4. The agent's goal is to push all boxes to their corresponding goal positions. From the reverse-play procedure, a random walk is utilized to carve out a random map topology. Utilizing that topology, two cells are chosen to be the start and goal for each box. The reverse-play algorithm ensures that there is a solution by essentially pulling a box across the map to the start position. In our modified version of reverse play, we increase the number of traps along a solution to increase difficulty. A detailed description of the Sokoban instance generation procedure is provided in Appendix E. The LLM agent interacts with the environment through tool calls that provide access to three actions: walk, push, and give up. We introduced the give up action to allow the agent to explicitly terminate an episode if it believes that the problem instance is unsolvable from the current state.

The tables below present the results on 20 Sokoban problem instances for Claude Sonnet 5 and GPT-5.2 using Prompted-ReAct scaffolding under two context settings: current-state and full-history.

Table 1 reports the failure rates of the two models. The results show that both frontier models exhibit failure rates ranging from 20% to 45% across the 20 Sokoban problem instances.

Table 1: Failure rate

ModelCurrent StateFull History
Claude Sonnet 535% (7/20)45% (9/20)
GPT-5.230% (6/20)20% (4/20)

We further categorize the failure cases into three categories:

  • (a) Dead-state failures: The agent pushes a box into a corner, resulting in an unsolvable state. The environment then terminates the episode.
  • (b) Premature termination: The agent selects the "give up" action even though the goal remains reachable, voluntarily terminating the episode without solving the problem.
  • (c) Step-limit failures: The agent reaches the maximum step limit (2x optimal plan length), resulting in episode termination without achieving the goal.
AuthorsOpenReview ↗

continuation..

Table 2 presents the number of failures in each of the three categories across the 20 Sokoban problem instances for both models, using Prompted-ReAct scaffolding under the current-state and full-history context settings. From the table's results, it is evident that under the current-state setting, Claude Sonnet 5 selected the "give up" action in 6 out of its 7 failure cases, incorrectly assuming that the problems were unsolvable even though solutions remained reachable. This highlights the LLM agent's difficulty in distinguishing between solvable and unsolvable problem states.

Table 2: Why the runs failed (dead state / gave up in a solvable state / hit the max step limit)

ModelCurrent StateFull History
Claude Sonnet 50 / 6 / 16 / 1 / 2
GPT-5.21 / 0 / 53 / 0 / 1

Under the full-history setting, Claude Sonnet 5's actions led the environment into dead states in 6 out of its 9 failure cases. This finding highlights a critical limitation of LLM-based agents in non-ergodic environments, where certain decisions can lead to irreversible states from which recovery is impossible. Since many real-world environments exhibit similar non-ergodic characteristics, such failures raise important concerns about the reliability and safety of deploying LLM agents in real-world settings.

Real-world incidents further illustrate the potential consequences of such failures. In one incident involving Hugging Face, an OpenAI evaluation agent reportedly escaped its intended network boundary and compromised Hugging Face's production systems while attempting to complete a cybersecurity benchmark. Similarly, an OpenAI agent researching public medicine spending reportedly bypassed access controls on Australia's Medicare statistics portal after being denied access, gaining access to non-public files and writing to an internal server. These incidents underscore the importance of evaluating not only whether an agent can achieve its intended goal, but also whether its actions can lead to irreversible and potentially harmful states along the way.

We additionally report in Table 3 the suboptimality ratio within the solved Sokoban problem instances.

Table 3: Suboptimality ratio within the solved instances (mean, with range in parentheses)

ModelCurrent StateFull History
Claude Sonnet 51.28 (1.0–1.5)1.18 (1.0–1.6)
GPT-5.21.27 (1.0–1.64)1.19 (1.0–1.78)
Reviewer_ffFjOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces PlanBench-Gym, a tool-calling extension of PlanBench built on PDDL-based planning. The authors argue that existing stateful tool-calling benchmarks are ergodic, or are made effectively ergodic by agent harnesses and safety checks. In these settings poor planning shows up only as wasted steps, not as failure, and negative interactions are essentially never tested. In the proposed benchmark, each lifted PDDL action schema is exposed as a tool. States, goals, and actions are rendered in natural language. The environment applies STRIPS progression semantics and returns an explanation of unmet preconditions whenever an action is rejected. The authors have tested Claude Sonnet 5, Qwen3.6, GLM5.2, GPT-5.2, and Gemma4. They also find that agent scaffolding and context management substantially influence performance, with Prompted ReAct generally outperforming native tool-calling approaches and the effectiveness of full-history versus current-state observations varying across models.

Critical strengths
  • The paper studies an important and underexplored problem in agentic AI evaluation. Existing agentic benchmarks often focus on task completion without explicitly examining how interactions between subgoals affect an agent's planning capabilities. This paper highlights negative subgoal interactions as an important dimension that may reveal planning deficiencies overlooked by existing benchmarks.
  • The experimental evaluation provides interesting insights into the limitations of current LLM agents. Multiple proprietary models and open-source models are evaluated.
Critical weaknesses
  • I don't think the experiments address the paper's motivation. The paper motivates its work by arguing that existing agentic benchmarks are often ergodic, allowing agents to recover from incorrect actions and potentially masking critical planning failures. However, all evaluated PlanBench-Gym instances are also ergodic, including those with negative subgoal interactions.
  • The experiments focus too much on different LLM backbones instead of agent frameworks. Since this benchmark focuses on the efficiency of tool-use and agentic planning, I would like to see more tool-use/planning frameworks to be tested. This will be more interesting than testing more LLMs.
Questions for authors
  • Why does the verification pipeline check the cost inequality only for positive-interaction instances? Can you report what fraction of negative-interaction instances satisfy the strict inequality?
  • Can you test more agent frameworks besides ReAct-based methods?
  • How do you ensure that the observed performance differences are caused by subgoal interactions rather than other factors?
4 comments
AuthorsOpenReview ↗

Evaluation on Non-ergodic domain

We thank the reviewer for a critical review. We would like to provide clarifications below.

W1 - Evaluation on Non-ergodic domain

To evaluate LLM agents in a non-ergodic domain, we include Sokoban in our analysis. In the Sokoban environment, where an agent cannot reverse certain actions once it reaches a dead-end state. For example, pushing a box into a corner can make the problem permanently unsolvable. This environment therefore provides a more realistic assessment of the agent's actual solvability rate. In contrast, Blocksworld is an ergodic environment in which, given a sufficiently large step budget, even a random walk can eventually reach the goal state. We incorporated the Sokoban environment into the PlanBenchGym benchmark. The Sokoban problem instance generator is built on top of DeepMind's Boxoban [1] and it generates problem instances using the reverse-play algorithm [2]. For our evaluation, we generated 20 problem instances on a 1010 grid, varying the number of boxes from 2 to 4. The agent's goal is to push all boxes to their corresponding goal positions. From the reverse-play procedure, a random walk is utilized to carve out a random map topology. Utilizing that topology, two cells are chosen to be the start and goal for each box. The reverse-play algorithm ensures that there is a solution by essentially pulling a box across the map to the start position. In our modified version of reverse play, we increase the number of traps along a solution to increase difficulty. A detailed description of the Sokoban instance generation procedure is provided in Appendix E. The LLM agent interacts with the environment through tool calls that provide access to three actions: walk, push, and give up. We introduced the give up action to allow the agent to explicitly terminate an episode if it believes that the problem instance is unsolvable from the current state.

The tables below present the results on 20 Sokoban problem instances for Claude Sonnet 5 and GPT-5.2 using Prompted-ReAct scaffolding under two context settings: current-state and full-history.

Table 1 reports the failure rates of the two models. The results show that both frontier models exhibit failure rates ranging from 20% to 45% across the 20 Sokoban problem instances.

Table 1: Failure rate

ModelCurrent StateFull History
Claude Sonnet 535% (7/20)45% (9/20)
GPT-5.230% (6/20)20% (4/20)

We further categorize the failure cases into three categories:

  • (a) Dead-state failures: The agent pushes a box into a corner, resulting in an unsolvable state. The environment then terminates the episode.
  • (b) Premature termination: The agent selects the "give up" action even though the goal remains reachable, voluntarily terminating the episode without solving the problem.
  • (c) Step-limit failures: The agent reaches the maximum step limit (2x optimal plan length), resulting in episode termination without achieving the goal.
AuthorsOpenReview ↗

continuation..

Table 2 presents the number of failures in each of the three categories across the 20 Sokoban problem instances for both models, using Prompted-ReAct scaffolding under the current-state and full-history context settings. From the table's results, it is evident that under the current-state setting, Claude Sonnet 5 selected the "give up" action in 6 out of its 7 failure cases, incorrectly assuming that the problems were unsolvable even though solutions remained reachable. This highlights the LLM agent's difficulty in distinguishing between solvable and unsolvable problem states.

Table 2: Why the runs failed (dead state / gave up in a solvable state / hit the max step limit)

ModelCurrent StateFull History
Claude Sonnet 50 / 6 / 16 / 1 / 2
GPT-5.21 / 0 / 53 / 0 / 1

Under the full-history setting, Claude Sonnet 5's actions led the environment into dead states in 6 out of its 9 failure cases. This finding highlights a critical limitation of LLM-based agents in non-ergodic environments, where certain decisions can lead to irreversible states from which recovery is impossible. Since many real-world environments exhibit similar non-ergodic characteristics, such failures raise important concerns about the reliability and safety of deploying LLM agents in real-world settings.

Real-world incidents further illustrate the potential consequences of such failures. In one incident involving Hugging Face, an OpenAI evaluation agent reportedly escaped its intended network boundary and compromised Hugging Face's production systems while attempting to complete a cybersecurity benchmark. Similarly, an OpenAI agent researching public medicine spending reportedly bypassed access controls on Australia's Medicare statistics portal after being denied access, gaining access to non-public files and writing to an internal server. These incidents underscore the importance of evaluating not only whether an agent can achieve its intended goal, but also whether its actions can lead to irreversible and potentially harmful states along the way.

We additionally report in Table 3 the suboptimality ratio within the solved Sokoban problem instances.

Table 3: Suboptimality ratio within the solved instances (mean, with range in parentheses)

ModelCurrent StateFull History
Claude Sonnet 51.28 (1.0–1.5)1.18 (1.0–1.6)
GPT-5.21.27 (1.0–1.64)1.19 (1.0–1.78)
AuthorsOpenReview ↗

Comparison with different Agentic frameworks

W2/Q2 - The experiments focus too much on different LLM backbones instead of agent frameworks. Since this benchmark focuses on the efficiency of tool-use and agentic planning, I would like to see more tool-use/planning frameworks to be tested. This will be more interesting than testing more LLMs.

In this paper we fundamentally evaluate 3 different agentic frameworks, the native tool-calling agentic framework, which was originally used in TauBench [3]. This agentic framework, following the TauBench paper, utilizes a system prompt that describes the nature of the problem/ domain policy, while relying on the LLM SDK to elicit a tool-call on every turn. The prompted style agentic framework stands on the opposite end, which emits its reasoning and action entirely as natural language text, with a parser to extract the tool-call and execute it. The ReAct style agentic framework utilizes a ReAct style system prompt with the tool-calling mechanism of the LLM SDK’s.

In our Blocksworld experiments, we run and evaluate all three agentic frameworks. As shown in Table 5.1, the prompted framework outperforms the other two. One possible explanation for the performance gap is the channel through which environment feedback reaches the model. In the native tool-calling and ReAct frameworks, observations come back as tool-role messages, which the instruction hierarchy of Wallace et al. [4] places at the lowest privilege level. Models trained under this hierarchy learn to disregard instructions that appear in tool outputs, and we hypothesize that this may also lower the weight they give to the state information those outputs carry. In the prompted framework, the same feedback arrives as a user message.

AuthorsOpenReview ↗

Negative-interaction instances strict inequality

W3 - Why does the verification pipeline check the cost inequality only for positive-interaction instances? Can you report what fraction of negative-interaction instances satisfy the strict inequality?

The cost inequality definition is a sufficient, but not necessary, condition for negative interaction. The Tower and Sussman anomaly instances exhibit negative interaction under the ordering/serializability-based definition in Korf's taxonomy. Accordingly, we have revised the definitions of subgoal interaction in the paper based on Korf's taxonomy [5] (see Section 2).

Under these definitions, a set of subgoals is considered serializable if there exists an ordering of the subgoals such that they can be solved sequentially without violating any previously achieved subgoal. However, certain subgoal orderings may lead to increased solution costs compared to the optimal cost, even when an ideal ordering would yield an additive solution cost. The Tower problem instances fall into this category.

In contrast, a set of subgoals is considered non-serializable if achieving further progress toward the main goal necessarily requires violating at least one previously satisfied subgoal, regardless of the ordering in which the subgoals are attempted. The Sussman anomaly problem instances fall into this category.

Based on these definitions, we further categorize negative interaction problem instances into two subcategories: (1) serializable problem instances, represented by the Tower problems, and (2) non-serializable problem instances, represented by the Sussman anomaly problems.

The table below presents the results for these two subcategories of negative interaction problem instances using the Claude Sonnet 5 model with Prompted-ReAct scaffolding and the current-state context setting. The results show that, under this setting, the agent solves all Tower problems optimally. However, for the Sussman anomaly problems, although the model achieves a 100% solve rate, it generates suboptimal plans, with a mean suboptimality ratio of 1.18. This indicates that, on average, the agent performs 4 redundant actions compared to the optimal plan length. (Note: the values in parentheses show the range.)

Problem typeSolve rate (%)Suboptimality ratioRedundant actions
Serializable (Tower)100 (25/25)1.000
Non-serializable (Sussman)100 (25/25)1.18 (1.00–1.27)4 (0–6)

We have included the same analysis for the other models, agent scaffolding approaches, and both context settings (current-state and full-history) in the paper (see Section 5).

We hope that we addressed all your concerns, if you have any further questions we would be glad to answer them. We would be grateful if you would consider raising your score.

References

[1] Sébastien Racanière et al. Imagination-Augmented Agents for Deep Reinforcement Learning. NeurIPS 2017.

[2] Arthur Guez et al. An investigation of Model-free planning: boxoban levels. https://github.com/deepmind/boxoban-levels/, 2018.

[3] Yao et al. τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains. ICLR 2025

[4] Wallace et al. The Instruction Hierarchy: Training LLMs to Prioritize Privileged Instructions. April 2024. https://arxiv.org/abs/2404.13208

[5] Richard E. Korf. Planning as search: A quantitative approach. Artificial Intelligence, 33(1):65–88, 1987. doi: 10.1016/0004-3702(87)90051-8.

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

This paper presents a new benchmark for AI planning named PlanBench-Gym. It empirically evaluate LLM planning capabilities by testing their task completion performance and suboptimality on different PDDL environments that require subgoal interactions where different subgoal structure poses different challenges in plan suboptimality. Specifically, the authors constructed PDDL environments offline with rules and test LLMs by converting the required state information into natural language.

Critical strengths

This paper is targeting an interesting problem in AI planning that particularlly focues on the subgoal interaction that are not well studied in the literature.

Experimental results find insightful observations in terms of context and subgoal interaction across different models. It suggests that intrinsic planning capability solely does not fully explain the planning performance. One might need to pay more attention to the planning context and interactions also for different LLM models.

Critical weaknesses

This work does not propose new planning methods or new paradigm of planning environments.

Questions for authors

Nil.

2 comments
AuthorsOpenReview ↗

Contribution Clarification and Evaluation on Non-ergodic domain

We thank the reviewer for their positive assessment of the paper. Below, we would like to provide clarifications on their concerns.

W1 - This work does not propose new planning methods or new paradigm of planning environments.

This paper does not propose a new method but rather an analysis of the planning abilities of LLM-based agents, in ergodic and non-ergodic environments. We evaluate LLM-based agents under varying harness configurations by modifying the agentic framework and context management approach. We evaluate three agentic frameworks, native tool-calling, text-formatted ReAct, and Hybrid ReAct, on Blocksworld instances consisting of positive subgoal interaction, negative subgoal interaction and no interaction instances. Based on the results in Sections 5.1 and 5.2, we come to the conclusion that in ergodic environments, models almost always solve instances but at an optimality tax, requiring at least 8-9% more steps in their budget to solve the problem.

We have now included in our evaluation a non-ergodic environment, Sokoban, where an agent cannot reverse certain actions once it reaches a dead-end state. For example, pushing a box into a corner can make the problem permanently unsolvable. This environment therefore provides a more realistic assessment of the agent's actual solvability rate. In contrast, Blocksworld is an ergodic environment in which, given a sufficiently large step budget, even a random walk can eventually reach the goal state.

We incorporated the Sokoban environment into the PlanBenchGym benchmark. The Sokoban problem instance generator is built on top of DeepMind's Boxoban [1] and it generates problem instances using the reverse-play algorithm [2]. For our evaluation, we generated 20 problem instances on a 1010 grid, varying the number of boxes from 2 to 4. The agent's goal is to push all boxes to their corresponding goal positions. From the reverse-play procedure, a random walk is utilized to carve out a random map topology. Utilizing that topology, two cells are chosen to be the start and goal for each box. The reverse-play algorithm ensures that there is a solution by essentially pulling a box across the map to the start position. In our modified version of reverse play, we increase the number of traps along a solution to increase difficulty. A detailed description of the Sokoban instance generation procedure is provided in Appendix E. The LLM agent interacts with the environment through tool calls that provide access to three actions: walk, push, and give up. We introduced the give up action to allow the agent to explicitly terminate an episode if it believes that the problem instance is unsolvable from the current state.

The tables below present the results on 20 Sokoban problem instances for Claude Sonnet 5 and GPT-5.2 using Prompted-ReAct scaffolding under two context settings: current-state and full-history.

Table 1 reports the failure rates of the two models. The results show that both frontier models exhibit failure rates ranging from 20% to 45% across the 20 Sokoban problem instances.

Table 1: Failure rate

ModelCurrent StateFull History
Claude Sonnet 535% (7/20)45% (9/20)
GPT-5.230% (6/20)20% (4/20)

We further categorize the failure cases into three categories:

  • (a) Dead-state failures: The agent pushes a box into a corner, resulting in an unsolvable state. The environment then terminates the episode.
  • (b) Premature termination: The agent selects the "give up" action even though the goal remains reachable, voluntarily terminating the episode without solving the problem.
  • (c) Step-limit failures: The agent reaches the maximum step limit (2x optimal plan length), resulting in episode termination without achieving the goal.
AuthorsOpenReview ↗

continuation..

Table 2 presents the number of failures in each of the three categories across the 20 Sokoban problem instances for both models, using Prompted-ReAct scaffolding under the current-state and full-history context settings. From the table's results, it is evident that under the current-state setting, Claude Sonnet 5 selected the "give up" action in 6 out of its 7 failure cases, incorrectly assuming that the problems were unsolvable even though solutions remained reachable. This highlights the LLM agent's difficulty in distinguishing between solvable and unsolvable problem states.

Table 2: Why the runs failed (dead state / gave up in a solvable state / hit the max step limit)

ModelCurrent StateFull History
Claude Sonnet 50 / 6 / 16 / 1 / 2
GPT-5.21 / 0 / 53 / 0 / 1

Under the full-history setting, Claude Sonnet 5's actions led the environment into dead states in 6 out of its 9 failure cases. This finding highlights a critical limitation of LLM-based agents in non-ergodic environments, where certain decisions can lead to irreversible states from which recovery is impossible. Since many real-world environments exhibit similar non-ergodic characteristics, such failures raise important concerns about the reliability and safety of deploying LLM agents in real-world settings.

Real-world incidents further illustrate the potential consequences of such failures. In one incident involving Hugging Face, an OpenAI evaluation agent reportedly escaped its intended network boundary and compromised Hugging Face's production systems while attempting to complete a cybersecurity benchmark. Similarly, an OpenAI agent researching public medicine spending reportedly bypassed access controls on Australia's Medicare statistics portal after being denied access, gaining access to non-public files and writing to an internal server. These incidents underscore the importance of evaluating not only whether an agent can achieve its intended goal, but also whether its actions can lead to irreversible and potentially harmful states along the way.

We additionally report in Table 3 the suboptimality ratio within the solved Sokoban problem instances.

Table 3: Suboptimality ratio within the solved instances (mean, with range in parentheses)

ModelCurrent StateFull History
Claude Sonnet 51.28 (1.0–1.5)1.18 (1.0–1.6)
GPT-5.21.27 (1.0–1.64)1.19 (1.0–1.78)

We hope that we addressed all your concerns, if you have any further questions we would be glad to answer them. We would be grateful if you would consider raising your score.

References

[1] Sébastien Racanière et al. Imagination-Augmented Agents for Deep Reinforcement Learning. NeurIPS 2017.

[2] Arthur Guez et al. An investigation of Model-free planning: boxoban levels. https://github.com/deepmind/boxoban-levels/, 2018.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.