acceptodds
Under review as a conference paper at ICLR 2027

A Minimal Agent for Planning Based on Reusable Domain Strategies

Abstract

In planning, an agent must compute a sequence of actions that transforms an initial state into a goal state. Frontier large language models (LLMs) now compete with state-of-the-art planners, but they are proprietary and expensive to run, while small open-weight LLMs remain behind. Planning problems, however, are organized into domains whose instances share the same actions and structure. In this paper, we exploit this structure with a minimal planning agent that adds two components to a small LLM, a domain strategy and feedback on its mistakes. The domain strategy is a natural-language text that explains how to compute a plan for any instance of the domain. The agent uses the strategy to guide the LLM, which returns a plan. A sound plan validator either accepts the plan or rejects it with feedback, and the LLM revises the plan with this feedback until the plan is valid or the call budget runs out. A frontier LLM writes the strategy once per domain, and the agent reuses it for every instance of that domain. We evaluate the agent with two small open-weight LLMs on the International Planning Competition (IPC) 2023 benchmark and on a benchmark of novel domains. The strategy increases the number of solved instances for both models, on both benchmarks, and at every budget. With up to five calls and feedback, GPT-OSS-20B improves from 28.3% to 40.6% on the IPC benchmark and from 0.4% to 17.4% on the novel benchmark. On the IPC benchmark, Gemma-4-31B solves 62.5% of the instances, more than a strong planner (56.7%) and GPT-5 (56.9%). To reach the coverage of GPT-5, it costs 9.8 times less than GPT-5 and 13.0 times less than Gemini 3.1 Pro. With feedback and up to 42 calls, Gemma-4-31B solves the same number of instances as the frontier model Gemini 3.1 Pro at a fraction of the cost. Overall, with only a strategy and feedback, small open-weight LLMs compete with planners and frontier models, and the computation spent once per domain is reused across all of its instances. This suggests that the same agent could be applied to problems beyond planning whose instances share a common structure from which a strategy can be defined.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
classical planning, large language model, agents, domain strategies, open-weight models, reasoning

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_LwXmOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper asks whether reusable domain-level guidance can improve the classical planning performance of open-weight language models. For each PDDL domain, a frontier model first writes a Python solver and then translates it into a natural-language strategy. A 20B or 31B model receives that strategy with each problem instance, generates a plan, and revises it when the VAL validator identifies an invalid action or an unmet goal. The authors evaluate this workflow on 360 IPC instances and 270 instances from three newer domains. Adding the strategy substantially increases the number of valid plans produced by both models; validator feedback provides a further gain. The paper also compares the resulting coverage with classical planners and frontier language models.

Critical strengths
  1. The paper measures valid plans and isolates the effect of adding a strategy. VAL checks the generated action sequences rather than relying on an LLM judge. Table 2 compares the same student models with and without the domain strategy at matched call budgets, and separately compares independent attempts with feedback-based revision. The resulting coverage gains are credible evidence that the supplied guidance helps these models.
  2. The evaluation extends beyond a small demonstration domain. It includes eleven domains, and per-domain results that reveal both gains and failures. The newer domains are particularly useful for testing whether the strategy helps on tasks the student models are unlikely to have memorized.
Critical weaknesses
  1. The experiments do not establish the value of the proposed strategy-generation method over simpler reusable skills. A domain strategy is, in practical terms, a reusable natural-language skill. The principal ablation compares this skill with no domain-specific skill; it does not compare against a guide written directly by the frontier model without the intermediate Python program, or an adapted prior strategy-plus-feedback method. The paper itself identifies closely related work using a stronger model’s strategy and validator feedback. These omissions make it difficult to identify what the proposed method contributes beyond providing reusable instructions.
  2. Limited methodological novelty beyond a reusable skill. The domain strategy is a domain-specific natural-language instruction sheet reused across instances—functionally a skill supplied in the prompt. The other component is revising an invalid plan using validator feedback. The paper identifies prior planning work that already combines a stronger model’s strategy with feedback-based revision. Its clearer contribution is evaluating this recipe with open-weight models across more and harder domains, rather than introducing a distinct agent mechanism.
  3. The practical “minimal small-model” claim is narrower than the framing suggests. The students have 20B and 31B parameters and already possess substantial capability; the paper does not show whether the approach enables genuinely resource-constrained models to plan. The authors acknowledge that running the 31B model requires GPUs with tens of gigabytes of memory. The comparison with frontier models also mixes inference budgets: the proposed agent may use five or up to 42 calls per instance, whereas the imported frontier results use one.
Questions for authors
  1. What test coverage does each teacher-generated Python program achieve on the same 11 domains?
  2. Under the same student model, validator, and call budget, how do the proposed strategies compare with domain guides written directly by the frontier model, expert-written guides, or an implementation of the closest prior strategy-plus-feedback approach?
  3. How does the method perform with a substantially smaller student model?
2 comments
AuthorsOpenReview ↗

Response to Reviewer LwXm: contribution, strategy forms, a smaller model, and inference budgets

Thank you for your review and for your suggestions! We clarify your questions below.

W1 and W2: Contribution Relative to Borro et al. (2025)

Borro et al. (2025) show that strategies help proprietary o1 models plan in Blocksworld. Their evaluation covers this single domain, with instances of 5 to 19 blocks, and they point to two open questions that our study addresses.

First, they state that "without exploring a wider range of domains, it is not possible to make any claims about the effect of applying the right strategy on solving increasingly large planning tasks." We evaluate eleven domains, with instances of up to 477 blocks in Blocksworld. Three of these domains were released after the LLMs were trained, which rules out data contamination on them.

Second, they state that "it is also important to explore domains that might not have clear and easily generalisable solutions." We include such domains: Sokoban, which is PSPACE-complete, and Cisterns.

We also analyze each component of the agent. We measure the strategy and the feedback separately, at three matched budgets, with two open-weight models from different families. We check each strategy before using it, through a program whose plans we validate on training instances. Unlike Borro et al. (2025), we find that feedback with the strategy solves more IPC instances than independent attempts: 146 against 134 with GPT-OSS-20B, and 225 against 210 with Gemma-4-31B.

The result is a small open-weight model at the level of planners and frontier LLMs. With up to five calls, Gemma-4-31B solves 225/360 IPC instances, more than LAMA (204) and GPT-5 (205). With up to 42 calls, it matches Gemini 3.1 Pro (245) and surpasses Scorpion Maidu (234), the winner of the IPC 2023 satisficing track. We will state this explicitly in the revision.

W1, Q1, and Q2: Strategy Forms

We compared three forms of strategy, all written by GPT-5.6 Sol:

  • Code: the Python program, given to the planning model as text;
  • Code$\to$NL: its translation into natural language, used in the paper;
  • Direct: a strategy written directly in natural language.

The table reports feedback@5 coverage. E2E has no strategy.

Planning modelBenchmarkE2ECodeCode$\to$NLDirect
GPT-OSS-20BIPC (360)102125146138
Total (630)103161193190
Gemma-4-31BIPC (360)211216225223
Total (630)320391399402

Every form improves both models over E2E, so the gain comes from the strategy itself. The translation solves more instances than its program: 32 more with GPT-OSS-20B and 8 more with Gemma-4-31B, over all 630. On the IPC benchmark, it also gives the highest coverage of the three forms for both models.

Direct strategies reach comparable coverage, but only the program can be checked: we validate its plans on training instances with VAL before translating it. We will include this comparison in the revision. Executing the program instead would replace the planning LLM rather than evaluate it, and we did not evaluate expert-written guides.

W3 and Q3: Smaller Model

We also evaluated Gemma-4-E4B, a much smaller model, on the easy and medium instances: 240 from the eight IPC domains and 180 from the three novel domains. Each cell gives the instances solved without the strategy →\to with the strategy.

Domainpass@1pass@5feedback@5
Blocksworld2$\to$52$\to$83$\to$8
Childsnack8$\to$1817$\to$2620$\to$25
Floortile0$\to$00$\to$00$\to$2
Miconic10$\to$1216$\to$2014$\to$18
Rovers0$\to$01$\to$32$\to$4
Sokoban0$\to$23$\to$50$\to$4
Spanner3$\to$203$\to$293$\to$28
Transport2$\to$19$\to$915$\to$18
IPC (240)25$\to$5851$\to$10057$\to$107
Novel (180)0$\to$22$\to$40$\to$4

The strategy roughly doubles IPC coverage at every budget, and at feedback@5 it improves all eight domains. On the novel domains, the model solves at most 4 instances with or without the strategy. "Minimal" refers to the components added to the LLM, not to the hardware. We will add these results, keep the hardware limitation, and make this scope explicit.

W3: Inference Budgets and Cost

The agent makes more calls than the frontier models, which are called once per instance. We therefore report its coverage at each budget and charge every call, on solved and unsolved instances, plus the one-time cost of generating the eight strategies:

  • at pass@1, with one call, it solves 188 of the 360 IPC instances;
  • at feedback@5, it solves 225 instances for USD 5.88, 6.6 times less than GPT-5 (205 instances, USD 38.87);
  • at feedback@42, it solves 245 instances for USD 17.74, 7.7 times less than Gemini 3.1 Pro (245 instances, USD 136.80).

The agent costs less because Gemma-4-31B is a cheaper model. We will report the budgets and total costs explicitly and replace Figure 2(c) with this accounting.

AuthorsOpenReview ↗

Follow-up on our rebuttal

Dear Reviewer LwXm,

Thank you again for your constructive review. In the rebuttal, we ran the experiments you asked for—testing the strategy as a program, as a translated program (paper), and as natural language—and extended our study to a much smaller model, Gemma-4-E4B. We also showed that the agent remains several times cheaper than GPT-5 and Gemini 3.1 Pro when every call is charged. Finally, we clarified how our work differs from Borro et al. (2025).

As the discussion period closes, please tell us if any concern remains. If your concerns are resolved, we kindly ask you to consider updating your score.

Best regards, The Authors

Reviewer_c7WuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Planning Agent combining domain strategy + feedback mechanism

Good metrics on experiments with several domains + relevant baselines.

Use-case: guiding smaller models with domain knowledge is more cost-effective than using frontier models, suggesting this approach could extend beyond planning to other structured problems.

Critical strengths

Very relevant problem on how to best leverage small models while keeping cost-efficient

Critical weaknesses

Applying this agent to new domains requires upfront investment in formal specification and validator development, limiting real-world adoption.

There has been other works in the same area - unsure what are the additional improvements relative to previous works methodology-wise (ignoring new LLMs and benchmarks, ).

Questions for authors

Token Efficiency vs. Plan Quality: Strategy reduces output tokens but increases plan length. Longer plans mean slower execution. Did you further investigate this trade-off?

Did you apply any refinement on the plans generated? If no, have you considered an improved why to speed up the refinement to further improve overall planning agent.

Can you elaborate on what is the differential of this work relative to previous works? I'm unsure what are the additional improvements methodology-wise (ignoring new LLMs and benchmarks , which are not proposed by this paper).

2 comments
AuthorsOpenReview ↗

Response to Reviewer c7Wu: contribution, formal specifications, and plan quality

Thank you for your review and for your suggestions! We clarify your questions below.

W2 and Q3: Contribution Relative to Borro et al. (2025)

Borro et al. (2025) show that strategies help proprietary o1 models plan in Blocksworld. Their evaluation covers this single domain, with instances of 5 to 19 blocks, and they point to two open questions that our study addresses.

First, they state that "without exploring a wider range of domains, it is not possible to make any claims about the effect of applying the right strategy on solving increasingly large planning tasks." We evaluate eleven domains, with instances of up to 477 blocks in Blocksworld. Three of these domains were released after the LLMs were trained, which rules out data contamination on them, so the gains there show that the strategies help beyond familiar benchmarks.

Second, they state that "it is also important to explore domains that might not have clear and easily generalisable solutions." We include such domains: Sokoban, which is PSPACE-complete, and Cisterns, for which we know of no polynomial algorithm.

We also analyze each component of the agent. We measure the strategy and the feedback separately, at three matched budgets, with two open-weight models from different families, while Borro et al. (2025) use two models of one family. We check each strategy before using it, through a program whose plans we validate on training instances, while their strategies are used without a check. Unlike Borro et al. (2025), we find that feedback with the strategy solves more IPC instances than independent attempts: 146 against 134 with GPT-OSS-20B, and 225 against 210 with Gemma-4-31B. Finally, we compare two frontier LLMs as strategy writers.

The result is a small open-weight model at the level of planners and frontier LLMs. With up to five calls, Gemma-4-31B solves 225/360 IPC instances, more than LAMA (204) and GPT-5 (205). With up to 42 calls, it matches Gemini 3.1 Pro (245) and surpasses Scorpion Maidu (234), the winner of the IPC 2023 satisficing track. As in Requena et al. (ICML 2026), the minimal architecture enables a controlled evaluation of which components improve reasoning performance. We will state this contribution and its relationship to Borro et al. (2025) explicitly in the revision.

W1: Formal Specifications and Validators

Applying the agent to a new domain requires only the formal description of the domain, and no validator development. For PDDL planning, VAL is a general validator: it checked the plans of all eleven domains, including the three novel ones, without changes. The domain strategy also requires no manual work, because a frontier LLM generates it from the domain description, as a program whose plans we check on training instances and then translate into natural language. The formal description is the same input that any planner requires, and it is written once per domain, since all instances of the domain reuse it. The agent therefore applies wherever a planning problem already has a formal model, as stated in the limitations. We will make this distinction and the scope of the deployment claim explicit in the revision.

Q1 and Q2: Plan Quality and Refinement

We examined whether the reduction in output tokens comes with longer plans. We compare the IPC instances that each model solves both with and without the strategy at pass@1. The table reports means over these common instances, with nn giving their number. E2E is end-to-end planning, and Strat. adds the domain strategy.

Planning modelnnOutput tokens, E2E →\to Strat.Plan length, E2E →\to Strat.
GPT-OSS-20B405,453$\to$4,316 (−20.9-20.9%)33.1$\to$29.5 (−11.0-11.0%)
Gemma-4-31B1517,432$\to$7,011 (−5.7-5.7%)82.5$\to$86.4 (+4.7+4.7%)

With GPT-OSS-20B, the strategy reduces both output tokens and plan length. With Gemma-4-31B, plans are 4.7% longer, and the increase is concentrated: of the 60 plans that become longer among the 151 common instances, 45 are in Miconic and Spanner. In both domains, the strategy is a simple and repetitive procedure, which is easy to follow but uses more actions than necessary. In Miconic, it serves one passenger at a time, which requires more lift movements than grouping passengers. In Spanner, it picks up every spanner on the way, including spanners that the plan does not use. The longer plans therefore come from the procedures of these two strategies. These procedures add actions, but they also let Gemma-4-31B solve more instances, which is our main objective: at pass@1, coverage rises from 25 to 34 in Miconic and from 38 to 44 in Spanner, of 45 instances in each domain.

We did not refine the generated plans. We focus on satisficing planning and return the first valid plan. Shortening validated plans is a useful extension when execution cost matters. We will add the domain-level explanation and discuss refinement as future work.

AuthorsOpenReview ↗

Follow-up on our rebuttal

Dear Reviewer c7Wu,

Thank you again for your constructive review. In the rebuttal, we clarified what our work adds to Borro et al. (2025): more domains, domains released after the models were trained, larger instances, and strategies checked before the model uses them. We also extended the analysis of the trade-off between output tokens and plan length. Finally, we clarified that a new domain requires only its formal description.

As the discussion period closes, please tell us if any concern remains. If your concerns are resolved, we kindly ask you to consider updating your score.

Best regards, The Authors

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

The paper presented a minimal agent that helps a small open-weight LLM plan with a domain strategy that a frontier LLM produces once per domain, and feedback from a sound validator on invalid plans. The experiment covers two open-source models, eight IPC domains and three new domains.

Critical strengths
  1. The framework is simple, and solution correctness is reliably checked. The method requires no fine-tuning, and domain strategies can be reused across instances.
  2. The benefits of strategy guidance are supported by controlled comparisons. Table 2 compares the same model with and without strategies under the same call budget, covering different model families and multiple domains.
Critical weaknesses
  1. The necessity of the additional design choices over prior work is not adequately established, and a direct program-execution baseline is still missing. The main framework already appears in Borro et al. (2025), as the paper acknowledges. The authors therefore need to establish more clearly what additional value comes from generating and validating a program before translating it into natural language. Two key comparisons are missing: generating natural-language strategies directly, and directly executing the generated Python programs. The latter is also an established approach in generalized planning.
  2. The additional benefits of strategy and feedback are inconsistent and concentrated. On the novel benchmark,, Gemma’s total feedback@5 coverage on the three novel domains increases from 109 to 174 instances. However, Orrery alone improves from 21 to 90, contributing 69 additional successes. Compared with pass@5, GPT-OSS feedback actually reduces coverage from 56 to 47.These results do not negate the method’s effectiveness, but they show that aggregate coverage masks substantial domain-dependent differences. The paper should explain which structural properties make strategies useful and whether failures arise from the strategies themselves, the program-to-text translation, or the smaller model’s inability to follow the strategies correctly.
  3. Section 4.2 describes Figure 2(c) as showing the minimum cost of solving a given number of instances. However, it does not clearly explain how successful instances are ordered or selected, or how costs incurred on ultimately unsuccessful instances are included. If the curve is constructed by retrospectively selecting successful, inexpensive instances, it represents a cost lower bound rather than the actual cost of running the method on the full benchmark.
Questions for authors

Are the program-generation and translation steps necessary? Please compare directly generated natural-language strategies, strategies translated from programs, and direct execution of the generated programs.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 1A9D: contribution, strategy forms, domain dependence, and full-benchmark cost

Thank you for your review and for your suggestions! We clarify your questions below.

W1: Contribution Relative to Borro et al. (2025)

Borro et al. (2025) show that strategies help proprietary o1 models plan in Blocksworld. Their evaluation covers this single domain, with instances of 5 to 19 blocks, and they point to two open questions that our study addresses.

First, they state that "without exploring a wider range of domains, it is not possible to make any claims about the effect of applying the right strategy on solving increasingly large planning tasks." We evaluate eleven domains, with instances of up to 477 blocks in Blocksworld. Three of these domains were released after the LLMs were trained, which rules out data contamination on them.

Second, they state that "it is also important to explore domains that might not have clear and easily generalisable solutions." We include such domains: Sokoban, which is PSPACE-complete, and Cisterns.

We also analyze each component of the agent. We measure the strategy and the feedback separately, at three matched budgets, with two open-weight models from different families. We check each strategy before using it, through a program whose plans we validate on training instances. Unlike Borro et al. (2025), we find that feedback with the strategy solves more IPC instances than independent attempts: 146 against 134 with GPT-OSS-20B, and 225 against 210 with Gemma-4-31B.

The result is a small open-weight model at the level of planners and frontier LLMs. With up to five calls, Gemma-4-31B solves 225/360 IPC instances, more than LAMA (204) and GPT-5 (205). With up to 42 calls, it matches Gemini 3.1 Pro (245) and surpasses Scorpion Maidu (234), the winner of the IPC 2023 satisficing track. We will state this explicitly in the revision.

W1 and Q1: Strategy Forms

We compared three forms of strategy, all written by GPT-5.6 Sol:

  • Code: the Python program, given to the planning model as text;
  • Code$\to$NL: its translation into natural language, used in the paper;
  • Direct: a strategy written directly in natural language.

The table reports feedback@5 coverage. E2E has no strategy.

Planning modelBenchmarkE2ECodeCode$\to$NLDirect
GPT-OSS-20BIPC (360)102125146138
Total (630)103161193190
Gemma-4-31BIPC (360)211216225223
Total (630)320391399402

Every form improves both models over E2E, so the gain comes from the strategy itself. The translation solves more instances than its program: 32 more with GPT-OSS-20B and 8 more with Gemma-4-31B, over all 630. On the IPC benchmark, it also gives the highest coverage of the three forms for both models.

Direct strategies reach comparable coverage, but only the program can be checked: we validate its plans on training instances with VAL before translating it. We will include this comparison in the revision. Executing the program instead would replace the planning LLM rather than evaluate it, and we did not evaluate expert-written guides.

W2: Domain Dependence and Feedback

The strategy helps when it can replace the hardest decision of a domain with a fixed rule.

Orrery and Floortile have such a rule, so the model no longer makes the decision. In Orrery, the decision is which wheels to twist. Every twist preserves the sum of the wheel positions, so the strategy fixes one wheel at a time, and the last one lands on its target: Gemma-4-31B rises from 21 to all 90 instances, and GPT-OSS-20B from 0 to 44. In Floortile, the decision is the order of painting, because a painted tile can no longer be crossed. The strategy paints the rows farthest from the robots first: GPT-OSS-20B rises from 2 to 6 instances, and Gemma-4-31B from 9 to 14.

Cisterns has no such rule. The decision is which water transfer to make, and a wrong transfer cannot be undone. The model still makes this decision alone, and the strategy does not help: Gemma-4-31B falls from 10 to 3 instances, and GPT-OSS-20B solves none.

Feedback also depends on the domain. On the novel domains, GPT-OSS-20B solves fewer instances with feedback than with independent attempts (47 against 56), because of Orrery (44 against 54). Over all 630 instances, feedback still solves more: 193 against 190 with GPT-OSS-20B, and 399 against 374 with Gemma-4-31B. We will discuss this in more depth in the revision.

W3: Full-Benchmark Cost

Figure 2(c) counts only the calls on solved instances, so it is a lower bound on the cost of the full benchmark. We will replace it with a figure that charges every call on all 360 IPC instances, plus the one-time cost of generating the eight strategies. Under this accounting, the agent remains cheaper:

  • at feedback@5, it solves 225 instances for USD 5.88, 6.6 times less than GPT-5 (205 instances, USD 38.87);
  • at feedback@42, it solves 245 instances for USD 17.74, 7.7 times less than Gemini 3.1 Pro (245 instances, USD 136.80).
AuthorsOpenReview ↗

Follow-up on our rebuttal

Dear Reviewer 1A9D,

Thank you again for your constructive review. In the rebuttal, we ran the comparison you asked for: the strategy as a program, as a translated program (paper), and as natural language. We also extended the analysis of when the strategy helps, and we showed that the agent remains several times cheaper than GPT-5 and Gemini 3.1 Pro when every call is charged. Finally, we clarified how our work differs from Borro et al. (2025).

As the discussion period closes, please tell us if any concern remains. If your concerns are resolved, we kindly ask you to consider updating your score.

Best regards, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.