Planning in Strawberry Fields: Evaluating and Improving the Planning and Scheduling Capabilities of LRM o1

## Abstract

Abstract The ability to plan a course of action that achieves a desired state of affairs has long been considered a core competence of intelligent agents and has been an integral part of AI research since its inception. With the advent of large language models (LLMs), there has been considerable interest in the question of whether or not they possess such planning abilities, but–despite the slew of new private and open source LLMs since GPT3–progress has remained slow. OpenAI claims that their recent o1 (Strawberry) model has been specifically constructed and trained to escape the normal limitations of autoregressive LLMs–making it a new kind of model: a Large Reasoning Model (LRM). In this paper, we evaluate the planning capabilities of two LRMs (o1-preview and o1-mini) on both planning and scheduling benchmarks. We see that while o1 does seem to offer significant improvements over autoregressive LLMs, this comes at a steep inference cost, while still failing to provide any guarantees over what it generates. We also show that combining o1 models with external verifiers–in a so-called LRM-Modulo system–guarantees the correctness of the combined system’s output while further improving performance.

## 1 Introduction

The recent release of OpenAI’s o1 (Strawberry) [] brings with it the opportunity to freshly evaluate the progress of large pre-trained AI models on planning and scheduling benchmarks.
Unlike the Large Language Models (LLMs) which came before it–which can roughly be viewed as approximate retrievers–o1 seems to have been trained to be an approximate reasoner, capable of scaling the amount of compute it uses depending on the query.(^1^11We speculate that the complete system learns to improve its ability to make appropriate Chain-of-Thought (CoT) moves useful for reasoning in a pretraining RL step with synthetic data, and does inference time prompt-specific rollouts; see Appendix B. In other words, it may be an RL-trained system in the same vein as AlphaGo, but where the ‘moves’ being generated and evaluated are Chains of Thought. Note that this is very different use of RL from that in RLHF, which can be seen as a fine tuning stage for an LLM that keeps the inference step unchanged.) Following OpenAI(^2^22Per the blogpost announcing the model: ”A new series of reasoning models […] for complex reasoning tasks this is a significant advancement and represents a new level of AI capability. Given this, we are resetting the counter back to 1 and naming this series OpenAI o1.”[]), we draw a distinction between previous Large Language Models (LLMs) and o1, a Large Reasoning Model (or LRM), as its new (unknown) architecture, operation, and capabilities all seem to be fundamentally different from those of vanilla LLMs, likely during both the pre-training phase and at inference time. Our aim in this paper is twofold: to comprehensively evaluate the performance of o1 on established planning and scheduling benchmarks as well as more difficult extensions; and to demonstrate how to provide correctness guarantees and boost performance by embedding an LRM in a loop with a sound verifier, in a similar vein to the LLM-Modulo framework [].

To properly evaluate this new kind of model and understand its abilities and limitations will require new tools and evaluation methods, especially if details of the overall model structure are kept secret and internal traces remain inaccessible to outside researchers.(^3^33There are reports that OpenAI is threatening to revoke access to o1 from anyone who tries to extract internal reasoning traces [].) In this paper, we evaluate performance on established benchmarks and compare to previous state-of-the-art results, extending these benchmarks to more difficult problems when possible and necessary. For planning, we use PlanBench [], which consists of both specific test sets and a suite of tools intended for evaluating language models on arbitrary IPC planning domains. To evaluate scheduling capabilities, we test on TravelPlanner [], on the three domains from Natural Plan [], and on graph coloring problems [].

Using these benchmarks as our basis for analysis, we investigate the performance jump that LRMs from the o1 family promise. We then demonstrate how these benchmarks can be elaborated on in order to remain relevant metrics for LRMs. We argue that, to be complete, new approaches to measuring LRM reasoning capabilities must take into account efficiency, cost, and guarantees. We also note the steep inference cost of LRMs and discuss the tradeoffs between using LLMs vs LRMs, arguing that in some cases an LLM-Modulo [] approach may be significantly cheaper than o1 models for comparative performance, and with guarantees.
Our results also show that that same LLM-Modulo approach can indeed be adapted to LRMs to further improve their performance and provide guarantees. In essence, LRMs can replace LLMs as significantly better–but still fallible–generators in the LLM-Modulo framework.

## 2 Background and Related Work

Though they are trained as text completion systems, Large Language Models (LLMs) have shown some promise on many other tasks. Initial claims were wildly positive, claiming they are general purpose reasoning systems [], especially when prompted in just the right way [, ], but later results showed that their seeming reasoning capabilities are brittle and break down even in simple domains [, , , ] and may be attributable to dataset contamination []. In planning, [] showed that LLMs fail even on problems as trivial as three block stacking.

Based on what little has been revealed by OpenAI, o1 seems to be a new class of model (a Large Reasoning Model or LRM), designed to combine the fuzzy language capabilities of LLMs with some implementation of approximate reasoning. With this in mind, we believe it is time to bring up the same questions that were asked about LLMs for these LRMs. We use benchmarks from the LLM literature, extending them where possible and necessary to show how well and how robustly o1 does or doesn’t perform on various planning and scheduling tasks.

### 2.1 Domains: Planning

The LLM literature abounds with claims of the ’emergent’ planning capabilities of LLMs []. However, closer inspection reveals that many of the empirical results supporting these claims comes from evaluations on simpler, commonsense domains, such as ALFworld [], BEHAVIOR [], kitchen environments [, ], and virtual home []. Not only do the the instances tested on tend to have fewer interactions, but many of them conflate reactive acting and deliberative planning [].

In contrast, we focus on classical planning problems, or STRIPS planning problems, which are a formalism for automated planning in discrete, deterministic spaces. To define a planning problem, we specify an initial state, a domain, and a goal. The domain contains all relevant information about the types of objects that may exist and the allowable actions from any given state, specified by defining the preconditions and effects of each named action. Problems and domains are represented in the flexible PDDL (Planning Domain and Definition Language) framework []. Solutions to PDDL problems are correct plans–sequences of actions executable from the initial state which arrive at a goal-satisfying final state.
These are problems in which the the planner already knows all relevant facts about the world and which actions are possible–only deliberation is required.

In the current work, we extend the STRIPS planning evaluation pipeline we first introduced in []. This benchmark provides an extensible suite of domains and tools for evaluating general models, a collection of static test sets across these domains, and ways of easily generating additional instances of problems in these domains. We draw on these static test sets to provide our initial o1 planning results on Blocksworld–a commonsense domain from the International Planning Competition []–and Mystery Blocksworld–an obfuscated version of the same. We also extend these sets to harder instances and examine performance on problems from both Logistics and Sokoban, two other well-known IPC domains.

**Table 1: Performance on 600 instances from the Blocksworld and Mystery Blocksworld domains across large language models from different families, using both zero-shot and one-shot prompts. Best-in-class accuracies are bolded.**
| Domain | Shots | Claude Models | OpenAI GPT-4 Models | LLaMA Models | Gemini Models |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | Claude 3.5<br>(Sonnet) | Claude 3<br>(Opus) | GPT-4o | GPT-4o<br>-mini | GPT-4 | GPT-4<br>Turbo | LLaMA<br>3.1 405B | LLaMA<br>3 70B | Gemini<br>1.5 Pro | Gemini<br>1 Pro |
| Blocks<br>world | One<br>Shot | 346/600<br>(57.6%) | 289/600<br>(48.1%) | 170/600<br>(28.3%) | 49/600<br>(8.1%) | 206/600<br>(34.3%) | 138/600<br>(23%) | 284/600<br>(47.3%) | 76/600<br>(12.6%) | 101/600<br>(16.8%) | 68/600<br>(11.3%) |
|  | Zero<br>Shot | 329/600<br>(54.8%) | 356/600<br>(59.3%) | 213/600<br>(35.5%) | 53/600<br>(8.8%) | 210/600<br>(34.6%) | 241/600<br>(40.1%) | 376/600<br>(62.6%) | 205/600<br>(34.16%) | 143/600<br>(23.8%) | 3/600<br>(0.5%) |
| Mystery<br>Blocks<br>world | One<br>Shot | 19/600<br>(3.1%) | 8/600<br>(1.3%) | 5/600<br>(0.83%) | 0/600<br>(0%) | 26/600<br>(4.3%) | 5/600<br>(0.83%) | 21/600<br>(3.5%) | 15/600<br>(2.5%) | - | 2/500<br>(0.4%) |
|  | Zero<br>Shot | 0/600<br>(0%) | 0/600<br>(0%) | 0/600<br>(0%) | 0/600<br>(0%) | 1/600<br>(0.16%) | 1/600<br>(0.16%) | 5/600<br>(0.8%) | 0/600<br>(0%) | - | 0/500<br>(0%) |

o1’s performance on PlanBench is especially interesting in light of the fact that the benchmark remains very challenging for vanilla LLMs (massive transformer models which have been fine-tuned via RLHF). The lackluster performance of LLMs on even the easiest static test set leads us to continue to believe that planning cannot be generally and robustly solved by approximate retrieval alone. In Table 1, we present the results of running current and previous generation LLMs on a static test set of 600 three to five block Blocksworld problems, as well as on a set of 600 semantically identical but syntactically obfuscated instances which we call Mystery Blocksworld.

Across the models tested, the best performance on regular Blocksworld is achieved by LLaMA 3.1 405B with $62.6\%$ accuracy. Despite the underlying problems being identical, Mystery Blocksworld performance lags far behind–no LLM achieves even 5% on our test set–and performance on one version of the domain does not clearly predict performance on the other. We do not provide Mystery Blocksworld data for Gemini 1.5 Pro only because we haven’t been able to generate it. The model refuses to produce any output, instead claiming that responding to these queries would be harmful. We include this output in Appendix D. Vanilla language models perform better when tested on natural language versions of prompts rather than PDDL [], even though natural language can introduce uncertainty due to polysemanticity and syntactic ambiguity. To make our comparisons "fair" for the models being tested, the results we report are the higher percent accuracy natural language prompting numbers, and can be considered an upper bound on LLM performance on PDDL-specified problems.

PlanBench does not explicitly take efficiency into consideration. As the time taken by a vanilla LLM to produce some output is only dependent on the length of that output, but otherwise independent of the semantic content or difficulty of the instance, this may not have particularly mattered in evaluations at the time. However, as LRMs adaptively vary their time taken and dollar cost per instance in response to the input, measuring efficiency has become much more important. As a comparison point between LRMs and LLMs, we compute prompting costs across models and present them in Table 4.

We also find that, contrary to previous claims, one-shot prompting is not a strict improvement over zero-shot. In fact, for many models it seems to do significantly worse!(^4^44While the reverse is generally true for Mystery Blocksworld problems, it’s important to note that the performance of vanilla LLMs on Mystery Blocksworld has consistently and uniformly been poor (the same as it was when this benchmark was first released), so those results do not provide too clear a picture. Most models do not solve even a single instance in zero-shot mode, and only one (LLaMA 3.1 405B) manages more than one.) This is most notable in our tests of LLaMA family models.

We relegate additional discussion of the particulars of LLM performance to appendix A.

### 2.2 Domains: Scheduling

More recent text-based benchmarks have provided full, static descriptions of their domains, initial states, and goals. However, many of these, despite the word "planning" in their titles, would be better characterized as testing scheduling abilities []. Classical planning problems are canonical graph search problems which are PSPACE-complete. Scheduling problems are only NP-Hard [], and mainly revolve around resource allocation. These problems are equivalent to constraint satisfaction problems, and thus easier than the planning problems we describe above.

We evaluate o1 on three scheduling benchmarks on which LLMs have failed. []’s Natural Plan benchmark consists of three scheduling domains: trip planning, calendar scheduling, and meeting planning. []’s Travel Planning benchmark consists of a large dataset of travel information (flights, accommodations, restaurants, etc.) with prompts that ask the model to create a three to seven day itinerary based on natural language instructions. Finally, [] translate graph coloring, a classical constraint satisfaction problem, into natural language prompts and evaluates GPT-4’s accuracy on these problems. We take their test set and extend it to more difficult instances.

## 3 From Approximate Retrieval to Approximate Reasoning

Figure: Figure 1: These examples are on Mystery Blocksworld. Fast Downward, a domain-independent planner [] solves all given instances near-instantly with guaranteed perfect accuracy. LLMs struggle on even the smallest instances. The two LRMs we tested, o1-preview and o1-mini, are surprisingly effective, but this performance is still not robust, and degrades quickly with length.
Refer to caption: extracted/5897594/images/plan_length_vs_correct_zero_shot.png

**Table 2: Performance and average time taken on 600 instances from the Blocksworld, Mystery Blocksworld and Randomized Mystery Blocksworld domains and 200 instances from the Logistics and Randomized Logistics domains by OpenAI’s o1 family of large reasoning models and Fast Downward (F.D.)**
| Total<br>Instances | Domain | Shots | Instances correct | Average Time Taken (in secs) |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | o1-preview | o1-mini | F.D<br>(satisficing) | o1-preview | o1-mini | F.D<br>(satisficing) |  |
| 600 | Blocksworld | Zero Shot | 97.8% | 56.6% | 100% | 40.43 | 10.84 | 0.12 |
| 600 | Mystery<br>Blocksworld | One Shot | 41.6% | - | 100% | 82.03 | - | 0.12 |
|  | Zero Shot | 52.8% | 19.1% | 100% | 83.37 | 35.54 | 0.12 |  |
| 600 | Randomized Mystery<br>Blocksworld | Zero Shot | 37.3% | 3.5% | 100% | 111.11 | 55.40 | 0.12 |
| 200 | Logistics | Zero Shot | 94% | - | 100% | 84.07 | - | 0.13 |
| 200 | Randomized Mystery<br>Logistics | Zero Shot | 52% | - | 100% | 167.41 | - | 0.13 |

Many researchers have argued that "standard" autoregressive LLMs generate outputs via approximate retrieval, and that, while they show impressive performance on a range of System 1 tasks, they are unlikely to achieve the more System 2-like approximate reasoning capabilities that are critical for planning tasks (c.f. []). From our analysis, we believe that o1’s architecture supplements an underlying LLM with System 2-like abilities, allowing it to outperform previous models.

As far as we can tell, o1 combines an underlying LLM, most likely a modified GPT-4o, into an RL-trained system that steers the creation, curation, and final selection of private Chain-of-Thought reasoning traces. Exact details are currently sparse, and so we can only speculate about its exact mechanisms. Our best guess is that there are two major differences between o1 and LLMs: an additional reinforcement learning pre-training phase (perhaps to learn the q-values of different CoTs from massive amounts of synthetic data) and a new adaptively scaling inference procedure (maybe it further refines learned q-values by something like rollout before selecting a particular CoT; see Appendix B.
Regardless, what looks clear from the detail available is that this model is fundamentally different in nature from previous LLMs.

### 3.1 Planning

##### Evaluating LRMs on PlanBench:

We test o1-preview and o1-mini on the original 600-instance PlanBench test set.(^5^55While for previous models, the model itself enforced the desired plan format, some modifications had to be made to accurately test o1’s abilities. In its current form, o1-preview does not always conform to explicit formatting restrictions. This is right in line with OpenAI’s injunction to keep o1 prompts ”simple and direct” []. In order to extract the generated plans, we used GPT-4o-mini to translate them into PDDL, and wrote a small Python parser to strip any remaining extraneous symbols before evaluating each proposed plan.) The full results can be seen in Table 2. These 600 Blocksworld instances range from three to five blocks, and require plans of between 2 to 16 steps to solve. Far surpassing any LLM, o1 correctly answers 97.8% of these instances. On Mystery Blocksworld, the model does not maintain this level of performance, but it does far surpass all previous models (which barely managed a few percent), answering 52.8% correctly. To test whether the exact obfuscation might be compromised because of data contamination, we also generated a new obfuscation using completely random strings, and presented these problems in a new, semantically equivalent prompt format with fully specified and unambiguous PDDL descriptions of both the domain and problem. This is presented in the table as Randomized Mystery Blocksworld. Exact prompts can be seen in the appendix. While performance did dip further, 37.3% of instances are answered correctly, sharply contrasting the flat zeroes of previous models. The same pattern can be seen when evaluating Logistics and a freshly generated obfuscation of that domain. Despite the higher branching factor of the domain, o1-preview solves 94% of all 200 problems tested and achieves 52% on the obfuscated variant.

Figure: Figure 2: Extending even the (regular, not obfuscated) Blocksworld dataset to problems requiring greater numbers of steps worsens the performance of o1-preview. When tested on 110 instances which each require at least 20 steps to solve, it only manages 23.63%.
Refer to caption: extracted/5897594/images/plan_length_vs_correct_bw_hard.png

##### Increasing Problem Size:

Standard LLM chain-of-thought prompting approaches are brittle, do not robustly scale with problem size, and fail to induce general algorithmic procedure-following []. We extend planbench to a set of 110 harder Blocksworld problems. Problems in this set range from 6 to 20 blocks in length and require 20 to 40 step optimal plans. Without any obfuscation, we see performance quickly degrade from the 97.8% reported earlier. In fact, over these 110 instances, o1-preview only manages 23.63%, and most of this accuracy comes from correctly solving problems which require fewer than 28 steps. While these models are overall impressive, this shows that their performance is still far from robust. These results are collated together with a representative sampling of smaller instances in Figures 1 and 2, showing how performance begins to fall on problems requiring plans of more than 10 steps.

**Table 3: Rate of claiming that a problem is impossible by OpenAI’s o1-preview on 100 unsolvable and 600 solvable instances in the Blocksworld and Randomized Mystery Blocksworld domains. The True Negative rate is the percent of unsolvable instances that were correctly marked as unsolvable. The False Negative rate is the percent of solvable instances that were incorrectly marked as unsolvable. Previous models are not shown in this table as their true negative and false negative rates were generally 0% across the board.**
| Domain | Shots | o1-preview |  |
| --- | --- | --- | --- |
| True Negatives | False Negatives |  |  |
| Blocksworld | 0-Shot | 27% | 0% |
| Randomized Mystery<br>Blocksworld | 1-Shot | 16% | 11.5% |

##### Performance on Unsolvable Instances:

While planning problems normally require the agent to formulate a course of action to achieve a goal, an equally valid use of planning abilities is to recognize that a given goal cannot be accomplished by any plan. A real-world example of this is network vulnerability analysis, where an agent may wish to certify that no plan of attack exists for a specified system []. So far, LLMs have struggled to recognize that some problems cannot be solved, instead confidently confabulating nonsensical answers. o1 was launched with the claim that it has started to overcome this issue, and can now accurately identify unsolvable problems []. To test this systematically, we modified 100 instances from the easier three to five block test set by adding one on(x,y)-type conjunct to each instance’s goal state, making the goal unsatisfiable. We ensured our instances were unambiguous by giving the full PDDL representation of both the domain and the instance, to avoid quibbles such as "A is on B because A is on C and C is on B" where the model redefines the meanings of a potentially ambiguous natural language statement. The results are in Table 3. On Blocksworld, only 27% of all instances were correctly and explicitly identified by o1 as unsolvable. In 19% of all cases, the model returned a dot or some kind of "[empty plan]" marker, without any explanation or indication of unsolvability. We consider these incorrect, as "empty plan" is only the correct answer if the goal is already satisfied. In the remaining 54% of cases, the model generated a full (and therefore impossible and incorrect!) plan.

On Randomized Mystery Blocksworld, these numbers are worse: 16% of cases were correctly identified as unsolvable, 5% returned an empty plan, and the remaining 79% were answered with a full (impossible or goal-unsatisfying) plan. Therefore, unsolvable instances continue to be a problem for LRMs. Furthermore, this ability to sometimes note impossible plans correctly comes at a cost: now the model sometimes falsely claims that solvable problems are actually unsolvable. On Randomized Mystery Blocksworld, 11.5% of instances are incorrectly claimed to be impossible. These results can be seen in Table 3.

##### o1’s Creative Justifications

While our main focus has been on providing a quantitative evaluation of o1’s performance on PlanBench, we have also noticed an o1 idiosyncrasy that is worth commenting on. When the model gives an incorrect answer, it also sometimes provides a creative, but nonsensical, justification for its decision. It is almost as if o1 has gone from hallucinating to gaslighting! In one case, it decided that an unsolvable problem is solvable because a goal condition, while not present in the final state, had been true for at some point during the execution, and thus should continue to count. In another, it declared that on(a,c) was true because, as it explained in a brief parenthetical, a was on b which was on c, and was thus a was somewhere above c, which should count as being "on top" of it. As we mentioned earlier, we changed our unsolvable instance prompts from natural language to PDDL in order to make it extremely clear that divergences from our exact definitions were disallowed.

##### Extending to Harder Domains:

While STRIPS planning is in principle PSPACE-complete, the problems presented above are actually of a lower computational complexity. Plan existence for both Blocksworld and Logistics is polynomial []. Sokoban is a non-ergodic domain in which an agent moves around a constrained grid, pushing boxes by running into them, where the goal is to move every box to one of a set of final locations. It can be represented in PDDL form, and is thus amenable to classical planning techniques, and is known to be PSPACE-complete [].

Using a generator from the 2008 International Planning Competition[], we generate 55 Sokoban instances with grid sizes ranging from $4\times 4$ to $10\times 10$, 1 to 4 boxes, and 1 to 4 walls. We then create corresponding prompts in PDDL. o1-preview answers 12.7% of these instances correctly, while o1-mini is not far behind with 10.9%. For comparison, when evaluated on these same instances, Llama3.1-405B, despite doing the best of all LLMs on the Blocksword sets, does not answer a single question correctly.

### 3.2 Scheduling

We also evaluate o1 on a set of scheduling problems that have previously been used in testing LLM capabilities.

##### Graph Coloring:

We evaluated o1-mini on the set of 220 problems included in the codebase associated with []’s paper, and found that it solved 96%, surpassing the 16% reported by that paper for GPT-4. To test the full capabilities of the model, we extended the test set. Using the same Erdős–Rényi procedure with $p=0.4,n=20$, we generated 50 more graphs, and did not rejection sample for planarity. As in that paper, we precalculate the chromatic number and provide it in the prompt, asking that the model produce a coloring that uses exactly that number of colors. These harder graphs have 20 vertices and around 60 edges each. On this set, o1-mini solves 50%, while o1-preview solves 64%.

##### Travel Planning:

We test o1 models on the 180 instance validation set of the sole-planning mode. In this mode, the model is provided upfront with all relevant information required to construct the requested itinerary. The previous state-of-the-art in direct prompting was 4.4%, achieved by GPT-4-turbo. o1-preview surpasses this, but only barely, solving only 10% of all instances. o1-mini does not beat even GPT-4-turbo, remaining at 1.67%.

##### Natural Plan:

This benchmark consists of three domains: calendar scheduling, trip planning, and meeting planning. On calendar scheduling, o1-mini solves 94% of all instances correctly. Given cost constraints, we did not test o1-preview on this domain, as o1-mini tends to be a lower bound on its performance. Neither model performs well on trip planning–o1-preview reaches 4% and o1-mini only 1%, both lower than the previous state-of-the-art set by Gemini 1.5 Pro. When provided with prompts from the meeting planning domain, both models refuse to respond and flag the input as a potential terms violation (see Appendix E).

### 3.3 Accuracy/Cost Tradeoffs and Guarantees

**Table 4: Cost per 100 instances (in USD). LRMs are significantly more expensive than LLMs.**
| Costs per 100 instances (in USD) |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Large Language Models | Large Reasoning Models |  |  |  |  |  |  |  |  |
| Claude 3.5<br>(Sonnet) | Claude 3<br>(Opus) | GPT-4o | GPT-4o<br>-mini | GPT-4 | GPT-4<br>Turbo | Gemini<br>1.5 Pro | Gemini<br>1 Pro | o1-preview | o1-mini |
| $0.44 | $1.70 | $0.65 | $0.02 | $1.80 | $1.20 | $0.33 | $0.03 | $42.12 | $3.69 |

With LRMs showing better performance on planning and scheduling problems, our evaluations must explicitly take into account the trade-offs that come from choosing general models over established deep and narrow systems. While o1-preview may provide higher accuracy than LLMs, it still fails to provide any correctness guarantees, and it is unclear that it is at all cost-effective. Unlike previous models, whose APIs only charge based on the number of input tokens and the number of output tokens (usually at a rate that is five times higher for the latter), o1’s price-per-call includes a surcharge based on the number of "reasoning tokens" it used–tokens generated as part of inference and not revealed to the user–which are charged at the significantly higher output token rate. Currently, end users have no control over the number of these tokens generated, a number which is expanded or limited by the model in its own opaque way.
We have already run up a bill of over $4000 for just the o1 model experiments reported in this evaluation!(^6^66The rich irony of researchers using tax payer provided research funds to pay private companies like OpenAI to evaluate their private commercial models is certainly not lost on us.))

Without exposing the ability to scale inference time to particular specifications, influence the internal ‘thinking’ process in task-specific ways, or ensure that intermediate steps are evaluated by trusted or sound verifiers, the o1 models are a coarse-grained choice in the space of cost, inference time, guarantees, and performance trade-offs. They aren’t, however, the only choices in that space, and reasonable LRM evaluations must take this into account (see similar arguments in [, ]).

Classical planners like Fast Downward [] achieve 100% on our dataset in a fraction of the time, compute, and cost, while providing guarantees that their answers are correct. Running Fast Downward on a personal computer was essentially free in dollar terms and averaged 0.12 seconds per instance, which is many orders of magnitude faster than the average o1 clock times listed in table 2. It is also generally predictable, and can be scaled to harder instances very directly. Vanilla LLMs are typically very good at translating problems between formats, and could be used to do so in concert with a classical planner at a fraction of the cost of LRMs (e.g. [, ]). For problems which don’t have simple PDDL domain and instance specifications, LLM-Modulo systems may be a safer and cheaper approach: run a smaller, faster LLM in a loop with a sound verifier, so that the combined system will only output guaranteed correct solutions (e.g. [, , ]).

The correctness guarantees provided by these latter two methods are sorely lacking in LRMs like o1. A general reasoning system cannot be deployed in safety critical and non-ergodic domains if it continues to confidently make incorrect plans. o1 is a fully black box system, even more so than previous models, and OpenAI’s decision to not only keep the architecture under wraps and hide the reasoning traces, but to warn away and even ban anyone who attempts to understand what is going on inside them [], makes interpretability nearly impossible, and reduces trust in the system overall.(^7^77The current model is also set to a default temperature of 1.0, which further reduces replicability and interpretability–for any given problem, it is never clear whether the result is merely the result of stochasticity. This compounds a problem with OpenAI models that has existed since at least GPT3. Temperature 0 never gave deterministic outputs, and worse, the logprobs provided by the OpenAI API for any given prompt have long been known to fluctuate wildly [].)

## 4 LRM-Modulo to Improve o1 with Guarantees

**Table 5: Performance of LRM-modulo with o1-preview and o1-mini as the underlying LRMs on our hardest test sets: Blocksworld (20+ length plans), Sokoban, Graph Coloring (20 vertex), Travel Planning, and Trip Planning (10 cities). Due to cost constraints, we run each problem set for up to ten iterations, stopping early if the improvement per iteration levels off.**
|  |  | o1-preview | o1-mini |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | Direct | LRM Modulo | Direct | LRM Modulo |  |  |  |  |  |  |
| Total<br>Instances | Domain | % correct | Cost (in $) | % correct | # of iters | Cost (in $) | % correct | Cost (in $) | % correct | # of iters | Cost (in $) |
| 110 | Blocksworld (hard) | 23.65% | 52.12 | 98.2% | 7 | 139.36 | 0.90% | 16.30 | 10% | 4 | 40.80 |
| 55 | Sokoban | 12.70% | 42.89 | 43.6% | 7 | 203.38 | 10.90% | 5.28 | 12.70% | 4 | 17.49 |
| 50 | Graph Coloring (hard) | 64% | 26.65 | 94% | 10 | 56.16 | 50% | 3.33 | 84% | 15 | 14.18 |
| 180 | Travel Planning | 10% | 68.21 | 65% | 10 | 431.75 | 1.67% | 12.11 | 41.11% | 10 | 97.17 |
| 200 | Trip Planning (10 cities) | 4% | 131.26 | 15.50% | 4 | 535.49 | 1% | 20.01 | 3.50% | 4 | 77.71 |

We propose augmenting o1 with external verifiers to endow the combined system with soundness guarantees. While o1 is a stride in the direction of general-purpose, expressive planning systems, our results show that it cannot plan robustly when faced with harder instances, nor can it consistently recognize when instances are unsolvable, still providing incoherent plans in a majority of such cases. In other words, o1 is still fallible and without guarantees. Prior to the release of these models, the best way to coax planning capabilities out of LLMs has been to pair them with sound external verifier in generate-test frameworks, in what are known as LLM-Modulo systems [, ]. This framework is broadly applicable even beyond LLMs, and–given a sound verifier for some domain–requires only a generator expressive enough to provide guesses for that domain. Moreover, because of the built-in verification, it guarantees that any answer output is correct. For safety-critical systems, this is essential! High accuracies are not sufficient, especially when the underlying system–as is the case for both LLMs and even more so for LRMs–is an opaque black box. Therefore, we investigated integrating LRMs into LRM-modulo systems to both boost their overall performance and to provide much-needed guarantees over their outputs.

Generate-test systems are limited by how good the generator is. A poor generator, such as one that produces completely random strings, may be capable of eventually producing the correct answer, but be so unlikely to do so at each iteration as to be useless, while an incomplete generator may never output the correct answer at all. LLMs and LRMs can be backprompted–that is, we can take feedback from the sound verifier and send it back to the model or modify the next prompt in some other way to increase the diversity of the responses generated–which may steer their next output towards the correct answer. Based on our results, o1 models are much better generators than anything that came before them, but, a priori, it is unclear if they are any more complete or capable of effectively utilizing backprompts or advice.

We test LRM-modulo setups on our five hardest test sets: 20+ length plan Blocksworld, Sokoban, 20 vertex graph coloring, OSU’s Travel Planning, and 10 city trip planning. Due to cost constraints, we limit the number of iterations to a maximum of ten, but we stop the system early once the performance increase from round to round has become mostly flat.(^8^88In the case of trip planning, we stopped early because of mounting costs: for just 4 iterations, we incurred an API access cost of $535!) Even with so few iterations, we see significant jumps in performance across almost all of our domains. o1-preview’s performance on harder Blocksworld saturates within 7 iterations, with the combined system achieving 98.2%. Harder graph coloring shows similar results, going up to 94%. Perhaps most surprising, our most difficult domain, Sokoban, shows a significant jump from 12.7% to 43.6%. o1-mini-Modulo performance, while also impressive, only comes close on graph coloring and travel planning. We present these results in Table 5.

Our results seem to imply that these models are not only better generators, but also benefit more from the sound verification signal and provided feedback. However, we can’t really know how they use the critique provided–this question is likely crucial, but also unanswerable with OpenAI’s current stance against revealing the internal workings of the model or the intermediate reasoning tokens it generates.

With the high cost of o1 model queries, it is also crucial to examine in which situations these models are not just the best option, but the cost-effective one. Returning to LLM-modulo, where we use a smaller, cheaper, and faster LLM in a loop with a verifier, can provide similar or better performance in some domains. For example, in calendar scheduling, o1-mini costs $2.70 to run over the entire test set, and has a final accuracy of 94%. GPT-4o-mini can be run for 50 iterations in a modulo loop for only $2.48, beating that performance to get 97%, a figure that comes with guarantees not provided by just the base model.

## 5 Conclusion

In this paper, we investigated the performance of o1-preview and o1-mini–the new so-called LRMs–on a variety of planning and scheduling benchmarks. While LLMs have thus far failed to make much progress on the obfuscated (or "Mystery") versions of PlanBench domains, o1 shows the first bit of real progress. In general, it seems to have made impressive headway on benchmarks that were previously unassailable. However, when we evaluated the model on longer problems and on the question of determining solvability of potentially impossible instances, we found that these accuracy gains are not general nor robust. While o1 made some gains on scheduling problems, performing much better on graph coloring than previous models, these were not evenly distributed, only making some progress on OSU’s Travel Plan domain and the Natural Plan benchmark suite.
We also discussed the critical accuracy/efficiency tradeoffs that are brought up by the fact that o1 that uses (and charges for) significant inference-time compute, as well as how it compares to other LLM-based approaches (such as LLM-Modulo []) and dedicated solvers. Future evaluations will have to maintain a focus on these factors if they are to remain meaningful or relevant.
Finally, we showed that approaches like LLM-Modulo [] can indeed be adapted to LRMs to further improve their performance and to provide much-needed guarantees. In essence, LRMs can replace LLMs as significantly better–but still fallible–generators in LLM-Modulo frameworks.

## Acknowledgements

We acknowledge support from and spirited discussions with fellow lab members.
This research is supported in part by ONR grant N0001423-1-2409, and gifts from Qualcomm and Amazon.

## Appendix

### A Further Discussion of LLM Planning Performance on Obfuscated Domains

LLMs are highly capable at providing translations between equivalent representations []. This fact, combined with their significantly higher performance on the unobfuscated version of the Blocksworld domain, predicts that–if they are capable of composing reasoning operations–the performance gap between Mystery Blocksworld and classic Blocksworld should shrink substantially if the translation from Mystery Blocksworld back into Blocksworld is explicitly provided. However, when we provide this in the prompt (see Appendix G), performance only improves a very small amount: GPT-4 achieves 10%.

### B Speculations about o1’s Internal Operations

While our evaluation of o1 did not depend on any specific assumption about its operation, we did have a working model of o1 based on the very skimpy description that was provided in the blog post that accompanies o1’s release []. Verifying our model is unfortunately made infeasible by the fact that o1 doesn’t actually provide any trace of its operations (even during the costly inference stage), and OpenAI warns that API access will be revoked if any attempts are made to surface its reasoning tokens.

There are two things–“reinforcement learning" and “Private Chain-of-Thought (CoT)” that are mentioned in the writeup. So imagine you are trying to transplant a “generalized AlphaGo”–let’s call it GPTGo–onto the underlying LLM token prediction substrate.

To do this, you need to know

- 1.
What are the GPTGo moves? For AlphaGo, we had GO moves). What would be the right moves when the task is just “complete the prompt the right way"?
- 2.
Where is it getting its external success/failure signal from? For AlphaGo, we had simulators/verifiers giving the success/failure signal. The most interesting question in transplanting the self-play idea to a general AI agent is where is it getting this signal?

Our guess is that the moves are auto-generated CoTs (thus the moves have a very high branching factor). Let’s assume–for simplification–that we have a CoT-generating LLM, that generates these CoTs conditioned on the prompt. (It is not clear if the CoT’s are domain independent of the “think step by step" variety [] or domain/task specific, or a combination.)

The success signal is likely from massive amounts of synthetic training data with correct answers. When the completed prompt is seen to contain the correct answer (presumably judged by the LLM itself), then the episode is considered a success, and a failure otherwise.

The task for the reinforcement learner then is: Given the original problem prompt, generate and select a CoT, and use it to continue to extend the prompt (possibly generating subgoal CoTs after every few stages). Get the final success/failure signal for the example (for which you do have answer).

The RL stage may involve training on a a huge number of training examples with answers.
The training examples with answers can either be coming from benchmarks, or from synthetic data with problems and their solutions–using external solvers.
In this phase the RL part attempts to learn the q-values of the CoT moves (much like AlphaGo learns the q-values of the moves of the Go). (The q-values learning may be incorporated into the internal weights of the CoT generator LLM). At this point, we have a CoT move generator that is better than the random one before the RL stage

During the inference stage–which OpenAI says can be indefinitely long (although it is currently capped internally by them, with no external control), like AlphaGo, o1 might be further improving its evaluation of the q-values of the CoT moves in the context of the current prompt. While AlphaGo used MCT-based rollouts, we obviously don’t know the mechanism o1 uses. The announcement only says that at inference stage a long chain of thought is added to the original prompt (and o1 does charge the end users for its “reasoning tokens," which are never seen by the end user, at the same high rate as the output tokens). In this sense, our speculations seem to be consistent, even though it is not clear whether the reasoning tokens are proportional to the entire inference-stage computation, or just represent the final sequence of CoT moves that get selected after the rollout-like inference stage.

Some corollaries of our speculation are:

- 1.
Note that this use of RL is very different from that in RLHF, which can be seen as a fine tuning stage for an LLM that keeps the inference step unchanged. It is also different from techniques, including OpenAI’s, that advocated fine tuning both on synthetic data accompanied with derivational traces–these too will be a form of finetuning that leave inference stage unchanged.
Here o1 could, in theory, be getting significantly more leverage out of the data by learning move (auto CoT) generators.
- 2.
There still are no guarantees that the answers provided are "correct"–they may be probabilistically a little more correct (subject to the training data). If you want guarantees, you still will need some sort of LLM-Modulo approach even on top of this.
- 3.
It is certainly not clear that anyone will be willing to really wait for long periods of time during inference (it is already painful to wait for 10 sec for a 10 word last letter concatenation!).
The kind of people who will wait for longer periods would certainly want guarantees–and there are deep and narrow System 2’s a plenty that can be used for many such cases.
- 4.
There is a bit of a Ship of Theseus feel to calling o1 an LLM–considering how far it is from the other LLM models (all of which essentially have teacher-forced training and sub-real-time next token prediction. That said, this is certainly an interesting way to build a generalized system 2’ish component on top of LLM substrates–but without guarantees.

### C LRM-Modulo performance over iterations

See Figure 3

Figure: Figure 3: LRM-Modulo significantly improves performance over direct prompting as we increase the number of iterations.
Refer to caption: extracted/5897594/images/correctness.png

### D Gemini 1.5 Pro Response to Mystery Blocksworld

### E o1-preview and o1-mini Response to Meeting Planning

### F o1 Token Use Versus Problem Difficulty

Figure: Figure 4: The number of reasoning tokens used by o1-preview when solving Blocksworld instances does not track the number of nodes that need to be expanded to solve the problem.
Refer to caption: extracted/5897594/images/nodes_expanded_vs_reasoning_tokens.png

### G Prompt to Translate From Mystery Back to Blocksworld

### H Prompts for Blocksworld

#### H.1 (Solvable) Blocksworld Instances - Zero-Shot in Natural Language

#### H.2 (Solvable) Harder Blocksworld Instances - Zero-Shot in PDDL

#### H.3 (Solvable) Harder Blocksworld Instances - Backprompt

#### H.4 Unsolvable Blocksworld Instances - Zero-Shot in PDDL

### I Prompts for Mystery Blocksworld

#### I.1 Mystery Blocksworld Instances - Zero-Shot in Natural Language

### J Prompts for Randomized Mystery Blocksworld

#### J.1 Randomized Mystery Blocksworld Instances - Zero-Shot in Natural Language

#### J.2 Unsolvable Randomized Mystery Blocksworld Instances - Zero-Shot in PDDL

### K Prompts for Logistics

#### K.1 Logistics - Zero-Shot in PDDL

#### K.2 Randomized Logistics - Zero-Shot in PDDL

### L Prompts for Sokoban

#### L.1 Sokoban - Zero-Shot in PDDL

#### L.2 Sokoban - Backprompt

### M Prompts for Graph Coloring

#### M.1 Graph Coloring - Hard

### N Graph Coloring Backprompt - Hard

### O Prompts for OSU Travel Planning

#### O.1 First Iteration

#### O.2 Back Prompt

### P Prompts for Trip Planning

#### P.1 First Iteration

#### P.2 Back Prompt

### Q Prompts for Calendar Scheduling

#### Q.1 First Iteration

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: No questions.
soundness: 2
strengths: The paper is highly timely and helps readers understand the specific performance of the o1 series models on the two benchmarks.
summary: This paper evaluates the planning capabilities of OpenAI's latest o1 series models on the PlanBench and TravelPlanner benchmarks, and proposes the use of external verifiers to assist the models in planning.
weaknesses: The paper's contribution to the community is relatively limited, as it does not provide any new insights.

The first key observation ``while o1 does seem to offer significant improvements over autoregressive
LLMs, this comes at a steep inference cost'' is already highlighted in OpenAI's official post (https://openai.com/index/learning-to-reason-with-llms/).

The second key contribution in Section 4 — that ``combining o1 models with external verifiers–in a so-called LRM-Modulo system–guarantees the correctness of the combined system’s output while further improving performance.'' — is also not new; it simply tests o1 models within the established LLM-Modulo Frameworks [1], without providing any new insights.

[1] LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: - Can the authors please explain the applicability and scalability of LLM-Modulo outside of the tested benchmarks, e.g., for practical usage? What is the minimum requirement of a task for the LLM-Modulo integration to be implemented?
- What are the potential ways to make the high inference cost of o1 more manageable in practical settings, besides using o1-mini as a replacement?
soundness: 2
strengths: - The paper focuses on important practical considerations such as reliability and efficiency of LRMs
- The paper utilizes established benchmarks while extending them for more rigorous testing and takes a systematic approach to evaluating both basic and complex planning scenarios. The paper presents a thorough evaluation with performance metrics, such as accuracy and inference time clearly reported and supported with comparative data.
- Proposed the integration of LRM-Modulo framework for enhanced reliability and potentially efficiency when coupled with the mini version
summary: OpenAI's o1 (Strawberry) represents a shift from traditional LLMs to Large Reasoning Models (LRMs). The paper evaluates the o1 family (including o1-preview and o1-mini) on planning and scheduling capabilities using established benchmarks like PlanBench, TravelPlanner, and graph coloring problems. The study shows that while o1 models outperform previous LLMs, they result in higher inference costs and lack guarantees for output accuracy. The study also explores methods to enhance reliability through integration with RM-Modulo framework as external verification.
weaknesses: - The reliability of the proposed LLM-Modulo integration when paired with the o1-mini model is unclear to me. While we can observe improved o1-mini performance, in cases such as Blockworld (hard), Sokoban, Trip Planning, o1-mini still significantly lags behind o1 performance. As the inference efficiency is an important consideration, it is unclear whether the LLM-Modulo can reliably deliver better efficiency while preserving the quality of the response.
- The studied problem is important but the novelty of the paper's proposed solution is limited.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: Q1. How is the solution generated by the LLM evaluated? Is it based on finding the optimal path, or is any correct path acceptable? Also, is there only one correct solution path for each example?

Q2. Is there any qualitative analysis of errors? For instance, when does the model typically make mistakes? Does it struggle to begin tasks correctly, or do errors occur more frequently toward the end of the solution? Additionally, what is the average length of the solutions?

Q3. Could you provide more detail on the evaluation protocols? The paper mentions a temperature setting of 1, but was any sampling used, given the non-deterministic nature of results? For example, was each instance evaluated multiple times (e.g., 3-5 runs) to capture potential variance? 

Q4. Could you clarify the distribution details for the Sokoban tasks? Specifically, what are the board sizes and the number of boxes used, and are there specific results for each configuration?

Q5. The paper reports that on Sokoban, o1-mini achieved a 10.9% success rate, while Llama3.1 (405B) achieved 0%. Could you provide some analysis or discussion on why there is such a difference in performance?

Q6. For Gemini 1.5 Pro, were the parameters regarding safety settings configured correctly to produce reasonable answers?

Q7. Could you define "gaslighting" in this context? Are there relevant citations or sources that you could provide on this topic?
soundness: 2
strengths: + The paper demonstrates strong integration with existing framework (LLM-Modulo), leading to cost reductions in the evaluation process.
+ The authors provide thorough documentation of the prompts and their design.
+ The research contributes to our understanding of model capabilities and limitations, which is important for the field’s development and for improving model robustness.
summary: The paper examines the capabilities of large reasoning models (LRMs) for planning and scheduling tasks.  It evaluates two LRMs, o1-preview and o1-mini, on benchmarks (for example PlanBench, Natural Plan benchmark and Travel Planning benchmark) and compares their performance to previous results.  The paper also notes the steep inference cost of LRMs and discusses the tradeoffs between using LLMs versus LRMs, arguing that in some cases an LLM-Modulo approach may be significantly cheaper than o1 models for comparative performance, and with guarantees.
weaknesses: The paper’s introduction could benefit from a clearer motivation. The decision to produce a new benchmark evaluation for each model release raises a question: does this paper bring a unique perspective to the evaluation landscape, or could the model creators be responsible for performance assessments of "established" benchmarks? Given that no new methodology or dataset is introduced, the contribution could appear limited to evaluating 1-2 additional models.

- Structural and Organizational Observations

The structure of the paper could be improved for clarity. For example, the results are presented as early as the related work section and continue sporadically throughout, which may make it challenging for readers to follow the flow of the argument. Additionally, the section on related work doesn’t provide a comprehensive view of the current state of the field, which might leave readers without a solid foundation in the broader research context.

Some terms, like "IPC," are introduced in the introduction but explained only in later sections. Defining these terms earlier could help readers understand the content more easily. Additionally, while the appendix includes sample prompts, adding a detailed example or task illustration in the main text could make the methodology and objectives clearer to readers.

- Evaluation and Methodological Details

The evaluation process might benefit from further clarification, especially concerning the assessment of LL(R)M solutions. For instance, it’s not entirely clear whether the evaluation is based on finding an optimal solution path or whether any correct path is acceptable, and if only one solution path is considered correct per example. Further qualitative analysis of the model’s errors would also be helpful—such as identifying if mistakes are common at the start of a task, or more likely toward the end. Discussing typical solution lengths would add another informative layer to the evaluation.

The evaluation protocols could be explained in more detail. The authors mention using a fixed temperature of 1 (this is fixed temperature for o1 models), but it would still help to run each instance multiple times (e.g., 3-5 runs) to check for any variation in results. This approach would make the findings more reliable. Given the focus on evaluation costs, applying this method to a smaller subset could balance accuracy with resource use.

- Contributions and Added Insights

The paper’s introduction suggests new metrics will be introduced, but no specific metrics are proposed. While the authors argue that “new approaches to measuring LRM reasoning capabilities must consider efficiency, cost, and guarantees,” this point is broadly applicable to all LLMs rather than being specific to LRMs

In the section evaluating Sokoban, some additional details could improve transparency. For instance, providing information about the board distributions (e.g., sizes and number of boxes) and specific results across different board configurations could give readers a clearer picture of the model’s performance. The authors report that o1-mini achieved a 10.9% success rate on Sokoban, while Llama3.1-405B achieved 0%; however, further analysis on this performance gap would be helpful.

- Style and Presentation Suggestions

The paper’s tone in certain sections could be more formal. Phrasing that is occasionally colloquial, along with exclamation marks, can detract from the overall scientific rigor expected in research papers. Additionally, consistency in the figures could improve readability—specifically, in Figure 1, the lines on the left plot are hard to see, and the color scheme is inconsistent between plots, which may make interpretation challenging.

Currently, the absence of code limits the ability of readers to reproduce the findings. Additionally, a discussion on limitations and broader impacts would provide helpful context regarding the scope and implications of the results.

- Cost Analysis Considerations

The cost analysis presented in Table 4 could be better suited to the appendix. Since model costs can vary over time, the information may quickly become outdated.

---

confidence: 3
contribution: 1
initial_rating: 5
presentation: 3
questions: Can you explain the significance of this paper? What is the main contribution besides evaluating a new series of models?
soundness: 3
strengths: - The paper is overall well-written and easy to follow.
- The paper tests the state-of-the-art model, the o1 series, and studies their performance on complex reasoning tasks, including planning and scheduling problems.
summary: In this paper, the authors benchmarked the performance of the newly released o1-preview and o1-mini on a few planning and scheduling datasets, and further evaluate how o1 models can be combined with LLM-Modulo system to enhance the guarantees of the correctness.
weaknesses: - While it is definitely important to understand the actual performance of the newly released o1 models not from the OpenAI team as an advertisement, the contribution seems limited. This paper does not propose a new dataset or a new method. The conclusion is also not surprising given the extremely large amount of work on LLM for planning that has already been published and even cited in the paper  [1, 2, 3]. And the new argument on the cost side seems obvious given the price already released by OpenAI.
- While the overall writing is easy to follow, the style does not follow the typical academic paper but is more like a blog post. Many non-declarative sentences are used.
- The paper does not follow the ICLR template format right now.

[1]. Valmeekam K, Marquez M, Olmo A, et al. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change[J]. Advances in Neural Information Processing Systems, 2024, 36.

[2]. Kambhampati S, Valmeekam K, Guan L, et al. LLMs can't plan, but can help planning in LLM-modulo frameworks[J]. arXiv preprint arXiv:2402.01817, 2024.

[3]. Kambhampati S. Can large language models reason and plan?[J]. Annals of the New York Academy of Sciences, 2024, 1534(1): 15-18.