LLMs Can Reason Faster Only If We Let Them
Authors: Bilgehan Sel
Lifu Huang
Naren Ramakrishnan
Ruoxi Jia
Ming Jin
Venue: ICML 2025 poster (2025)
Keywords: large language models
decision-making
planning
Primary area: deep_learning->large_language_models
TL;DR: Enabling faster large language model solutions for autonomous reasoning and planning

Abstract: Large language models (LLMs) are making inroads into classical AI problems such as automated planning, yet key shortcomings continue to hamper their integration. Chain-of-Thought (CoT) struggles in complex multi-step reasoning, and Tree-of-Thoughts requires multiple queries that increase computational overhead. Recently, Algorithm-of-Thoughts (AoT) have shown promise using in-context examples, at the cost of significantly longer solutions compared to CoT.  Aimed at bridging the solution length gap between CoT and AoT, this paper introduces AoT-O3, which combines supervised finetuning on AoT-style plans with a reinforcement learning (RL) framework designed to reduce solution length. The RL component uses a reward model that favors concise, valid solutions  while maintaining planning accuracy. Empirical evaluations indicate that AoT-O3 shortens solution length by up to 80\% compared to baseline AoT while maintaining or surpassing prior performance. These findings suggest a promising pathway for more efficient, scalable LLM-based planning.

LLMs Can Reason Faster Only If We Let Them
Bilgehan Sel Lifu Huang? Naren Ramakrishnan'
Ruoxi Jia Ming Jin
Abstract
et al., 2022: Bai al., 2022; Rafailov al., 2024), optimiza- tion (Jin et al., 2024), and general problem-solving (Brown et al., 2020; Nye et al., 2021; Wei et al., 2022; Huang & Chang, 2022). Despite these successes, their performance in complex tasks requiring diverse thought processes, par- ticularly in planning domains (Kambhampati et al., 2024a; Valmeekam al., 2024), has remained notably limited. This limitation becomes particularly evident scenarios requir- ing long-horizon reasoning, where the models must main- tain coherence and logical consistency across multiple steps while exploring various solution paths.
Large language models (LLMs) are making in- roads into classical Al problems such as au- tomated planning, yet key shortcomings con- tinue hamper their integration. Chain-of- Thought (CoT) struggles in complex multi-step reasoning, and Treu-hf-Thoughts requires mul- tiple queries that increase computational over- head. Recently, Agorithm-of-Thouughh (AoT) have shown promise using in-context examples, at the cost of significantly longer solutions compared to COT. Aimed bridging the solution length gap between CoT and AoT, this paper introduces AoT-O3, which combines supervised finetuning on AoT--stle plans with a reinforcement learn- ing (RL) framework designed to reduce solution length. The RL component uses a reward model that favors concise, valid solutions while main- taining planning accuracy. Empirical evaluations indicate that AoT--03 shortens solution length by up to 80% compared to baseline AoT while main- taining or surpassing prior performance. These findings suggest a promising pathway for more efficient, scalable LL.M-based planning.
The introduction of methods such as Chain-of-Thought (CoT) (Wei et al., 2022), Least-to-Most prompting (L2M) (Zhou al., 2022). hoff-Consiteecy CoT (CoT-SC) (Wang et al., 2022), and Self-Refine (Madaan al., 2024) has failed significantly improve planning capabilities, even with ofte-of-theeart LLMs. These approaches, while effec- tive in simpler reasoning tasks, struggle with the complexity inherent in planning problems where a single misstep can lead to an unrecoverable state. This limitation has sparked the development of various approaches aimed diversify- ing reasoning paths (Long, 2023; Yao al., 2024; Lei et al., 2023; Yao et al., 2023; Besta et al., 2024). These methods have demonstrated considerable improvements in accuracy compared to CoT by allowing models to explore multiple solution paths simultaneously. However, they face signifi- cant challenges: computational expense due to the need for multiple model queries, implementation complexity when applying new problems, and performance that still falls short of human benchmarks (Sel al., 2024b; Kambham- pati et al., 2024b). The gap between model performance and human capability remains particularly pronounced in domains requiring strategic thinking and adaptive reasoning.
1. Introduction
Developments in large language models (LLMs) (Vaswani, 2017; Radford, 2018; Radford et al., 2019; Brown et al., 2020; Chowdhery et al., 2023; Zhao al., 2023, inter alia) have led to remarkable advancements in artificial intelli- gence, particularly in natural language processing. These models, pre-trained on vast corpora of data, have demon- strated impressive capabilities across diverse domains, suc- cessfully transferring their knowledge to downstream tasks including code generation (Chen al., 2021; Li et al., 2022; Jiang et al., 2024), language understanding (Yuan et al., 2022; Katz et al., 2024), instruction following (Ouyang
Recent innovations, notably the LLM-Modulo framework (Valmeekam et al., 2024) and Algorithm of Thoughts (AoT) (Sel et al., 2024b; 2025), have shown promising results in approaching human-level performance. LLM-Modulo ad- dresses the limitations of self-feedback by incorporating external verifiers to provide fine-grained feedback to LLMs, effectively creating a closed loop system that can identify and correct errors in real-time. This approach has demon- strated remarkable success improving model accuracy, but the reliance on external verification tools introduces additional complexity and computational overhead. In con-
'Virginia Tech Blacksburg, USA. University of California, Davis, USA. Correspondence to: Bilgehan Sel <bbee@@ cd.u>>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

LLMs Can Reason Faster Only If We Let Them
Input
Input
Input
Output
Output
Output
CoT
AoT
AoT-03
Figure 1. Illustration showing three reasoning strategies with LLMs: Chain of Thought (CoT), Algorithm of Thoughts (AoT), and AoT-O3, Each box represents thought step, with green indicating promising paths and red showing less promising alternatives. AoT-O3 demonstrates a more streamlined structure while maintaining the key benefits of branching exploration.
trast, AoT presents a pure LLM solution that eliminates the need for external tools or additional prompting mechanisms. achieves self-correction by incorporating in-context exam- ples that mirror human thought processes, either expanding upon search nodes or transitioning to more promising nodes that appear likely to reach the goal. This approach lever- ages the model's inherent ability to learn from examples while maintaining the efficiency of single-query solutions. Subsequent research has revealed that these example search processes need not explicitly contain human intuitions; sim- ply augmenting correct CoT-like solutions with random step-by-step solutions enables models achieve compara- ble performance (Sel al., 2025). This finding suggests that the key to improved performance lies not in mimick- ing human reasoning patterns specifically, but in providing structured examples of successful problem-solving strate- gies.
of training examples? How much of the extended solution length contributes meaningfully to problem-solving versus serving as stylistic overhead? unnecessary search paths ex- ist primarily to match the style training examples, can we enable more efficient mooblem-solving by removing this con- straint while maintaining the benefits of diverse reasoning paths? Understanding these aspects is crucial for developing more efficient approaches that maintain the advantages of AoT while reducing computational overhead.
These solution strategies can be analyzed through the lens of human cognitive systems, providing insights into their op- erational mechanisms and potential improvements. While CoT and L2M align with the analytical System 2 think- ing (Kahneman, 2011), contrasting with reflexive System decision-making recent work (Sel et al., 2025) suggests that AoT activates System 3 thinking (Webb, 2021). This third system, characterized by deliberate contemplation and strategic decision-mann makiin in the face of uncertainty, rep- resents more sophisticated level of cognitive processing. Although acknowledge this perspective, current AoT implementations may be imitating rather than truly engaging in System 3 thinking, pointing to the potential for more efficient and deliberate reasoning path exploration. This distinction between imitation and genuine engagement with different cognitive systems has important implications for the development of more effective problem booblem--olving ap- proaches.
While AoT represents significant advancement perfor- mance requiring only a single query per problem solution, the inclusion of multiple reasoning paths substantially in- creases the total solution length compared to CОТ. This expansion introduces proportional increases in computa- tional requirements and solution time per problem, raising concerns about scalability and efficiency. Excessively long solutions also raise environmental concerns due to increased token usage (Earth. Org, 2024)!. Critical questions emerge regarding the necessity and effectiveness of these additional steps: What proportion of these additional steps represents intentional exploration by the model versus mere imitation
propose that
This paper introduces AoT-O3, named after the highest op- timization level in C++ programming language compilers, which aims to bridge the solution length gap between CoT and AoT while maintaining or improving performance. Our approach represents a fundamental shift how LLMs can
Recenn projections suggest Al-related power demand could grow substantially coming years (Agency, 2024). See Ap- pendix A for an estimate of the potential impact.
2

---

LLMs Can Reason Faster Only If We Let Them
be guided to solve complex problems more efficiently. We employ reinforcement learning (RL) with carefully designed objective reward models to encourage more concise AoT responses without sacrificing solution quality. The reward models are specifically crafted to balance the competing objectives of solution efficiency and accuracy, ensuring that shorter solutions do not come at the cost of reduced perfor- mance. Notably, we pioneer the use of non-LLM reward models that extend beyond simple accuracy metrics, making the fine-tuning process more efficient and memory-friendly This innovation addresses one of the key limitations of ex- isting approaches that rely heavily on LLM-based reward models, which can introduce significant computational over- head and potential biases as illustrated in Figure
icant computational overhead through multiple API calls. The Algorithm of Thoughts framework (Sel et al., 2024b) addressed these efficiency concerns by demonstrating that carefully crafted in-context examples incorporating search trajectories could achieve comparable or superior perfor- mance with a single query. AoT+ (Sel et al., 2025) further improved the ease of use and performance of AoT, although in this paper we will use AoT as the naming for both.
Self- Improvement and Verification in LLMs. The con- cept of autonomous improvement through self-verification has been extensively explored in LLM research. Initial ef- forts focused on constitutional training (Bai et al., 2022) and ethical decision-making (Ma et al., 2023; Sel et al., 2024a), demonstrating that models could be guided to eval- uate and refine their outputs. This approach has shown promise in specific domains such as code generation (Zelik- man et al., 2023; Kim et al., 2024) and question weession-answering (Madaan et al., 2024; Paul et al., 2023). Recent work has ex- panded these concepts through recursive self-improvemmnt (Zelikman et al., 2023; 2024). However, significant chal- lenges remain in symbolic reasoning tasks (Valmeekam et al., 2023; Kamoi et al., 2024), where self-verification often fails to identify critical errors. These limitations have sparked debate about the fundamental capabilities of LLMs in autonomous error correction (Kambhampati et al., 2024a), particularly in domains requiring precise logical reasoning.
We demonstrate our method's is effectiveness across a wide range of open-source LLMs and diverse benchmarks, pro- viding comprehensive evidence of its generalizability and robustness. Our evaluation encompasses various planning domains, from simple sequential tasks to complex strategic problems requiring multiple levels of reasoning. Results show that AoT-O3 achieves an 80% reduction in solution length while improving accuracy, an advantage that becomes even more critical under light token constraints. This re- markable improvement in efficiency does not come at the cost of solution quality; in fact, we observe consistent im- provements in accuracy across most benchmarks. The suc- cess of AoT-03 in maintaining or enhancing performance while dramatically reducing computational requirements represents a significant step toward more practical and seal- able applications of L.MSs in complex problem-solving do- mains.
Reinforcement Learning for LLM Alignment. Rein- forcement learning has emerged as a powerful approach for aligning language models with human preferences and improving their capabilities across various tasks. The foun- dation was laid by InstructGPT (Ouyang al., 2022), which demonstrated that RL from Human Feedback (RLHF) could effectively tune models to better follow instructions. This was further developed by Constitutional AI (Bai et al., 2022), which showed how recursive reward modeling could instill specific behavioral constraints. Recent work has explored alternative reward mechanisms, with Direct Preference Op- timization (DPO) (Rafailov et al., 2024) providing a more computationally efficient alternative to traditional RLHF. The application of RL to improve reasoning capabilities has been particularly noteworthy, with ReAct (Yao et al., 2022) showing how reward signals could encourage more structured exploration of solution spaces.
2. Related Work
Evolution of LLM Reasoning Approaches. The emer- gence of large language models has revolutionized ap- proaches complex problem-solving tasks. Initial work demonstrated that these models, trained on diverse textual data, could tackle various challenges through direct prompt- ing (Brown et al., 2020; Chowdhery et al., 2023). This capa- bility was significantly enhanced through the development of step-by-step reasoning methods that reframe problems as sequential decision processes. Chain-of- ohTThhttt prompting (Wei et al., 2022; Kojima al., 2022) and its variants (Zhang et al., 2022; Nye et al., 2021) marked a crucial advancement in structured reasoning. However, these approaches revealed limitations in inherently sequential domains, particularly planning problems (Long, 2023). Subsequent research intro- duced more sophisticated frameworks like Tree of Thoughts (Yao et al., 2024), which spawned numerous extensions (Lei et al., 2023; Besta al., 2024). While these methods im- proved accuracy by leveraging LLMS as heuristic generators within external search frameworks, they introduced signif-
3. Effect of In-Context Examples in Planning
Before we decide which type of examples to choose for supervised and RI. finetuning for our method, we proceed with exploring how the style of in-context demonstrations affect the LLMs when they are prompted with a test problem. Here, we are interested in the differences between prompt- ing and supervised finetuning. First, let's define planning
3

---

LLMs Can Reason Faster Only If We Let Them
problems of interest.
human-like strategic thinking. but rather in its provision of structured framework for exploring multiple solution paths, regardless of their individual quality.
Classical Planning Problems. (Russell & Norvig, 1995) A classical planning problem can be defined as finding a sequence of actions that transitions the system from an initial state/ / to a goal state G, given:
However, while random demonstrations may be effective for in-context prompting, their utility appears to diminish significantly in model fine-tuning scenarios. As shown in Table I, when testing on the Game of 24 benchmark using the Llama 3.3 70B model (Dubey et al., 2024), prompting with random examples maintains comparable performance to gold-standard demonstrations in both CoT and AoT set- tings. In stark contrast, fine-tuning on random examples leads to a dramatic deterioration in model performance, with accuracy dropping below pre-finetuning levels. This disparity suggests that while models can effectively filter and utilize random demonstrations during inference, incor- porating such noise during training may interfere with the model's 's ability to learn robust reasoning strategies.
A set of possible states S.
A set of actions A, where each action has:
Preconditions that must hold true for the action to be applied,
Effects that describe how the action changes the state.
The goal is to compute a plan = [01, 02,,..., an) such that applying these actions in sequence achieves G starting from I.
3.1. Effect of Random Demonstrations in Finetuning
3.2. Effect of Solution Length in AoT
The role of demonstrations in tfain-of-thoughe prompting was fundamentally reexamined by Min et al. (2022), show- ing that randomly generated reasoning paths could achieve comparable performance to carefully crafted demonstra- tions. Their study revealed that the presence of step-by-step reasoning patterns, rather than their actual correctness op- timality, was the key factor in enabling successful problem- solving behavior in language models. This finding sug- gested that demonstrations primarily serve to elicit a partic- ular problem-solee solving format from the model, rather than to transmit specific solution strategies. Their work challenged the prevailing assumption that high-quality demonstrations were necessary for effective CoT prompting, indicating that the structural aspects of reasoning demonstrations might be more important than their content.
To investigate the relationship between demonstration solu- tion length and model performance, we conducted experi- ments using the OpenAl GPT-4 model (Achiam et al., 2023) on the Game of 24 benchmark (Yao et al., 2024; Sel et al., 2024b). We examined this relationship in both in-context learning (ICL.) and fine-tuning scenarios, with particular attention to how different solution length distributions affect model accuracy and efficiency. For our ICL experiments, we constructed three sets of 10-shot demonstrations (per each test example, we select new 10-shot examples), each following a Gaussian distribution centered around differ- ent mean solution lengths: short (10 steps), medium (30 steps), and long (60 steps) with std of 5.0 with a clip at 3.0 since the minimum number of steps in this game three. These demonstrations maintained consistent solution strate- gies and reasoning patterns while varying in their degree of elaboration and search path exploration.
Accuracy (%)
Method
CoT
AoT
Prompting
8
64
As seen in Figure 2, our results indicate a strong positive correlation between solution length and model performance, with longer demonstrations leading to longer solutions pro- duced by GPT-4 with higher accuracy rates, 15%, 31% and 61 % with temperature of 0.5. These findings indicate that so- lution length serves as more than just stylistic variation- it appears to be fundamentally connected to the model's 's ability to reason effectively about complex problems. The superior performance of longer solutions may be attributed to their more comprehensive exploration of the solution space, al- lowing the model to better understand and replicate success- ful problem-solving strategies. These results have important implications for both prompting and fine-tuning strategies, suggesting that artificially constraining solution length may inadvertently limit model performance.
Finetuning
3
5
Table 1. Random demonstrations performance of Llama-3.3-70B with reeedy-decoding on Game of 24 when prompted in 8-shot setting and finetuned with 900 training and 100 test examples from Yao al. (2024); Sel al. (2024b).
This insight has been recently extended to AoT. It's been demonstrated that augmenting correct AoT solutions with random search trajectories achieved performance compa- rable to carefully designed examples incorporating human intuition (Sel et al., 2025). This shows that the benefits of diverse reasoning paths in AoT persist even when some of the demonstrated search trajectories are suboptimal or irrelevant to the solution. This finding suggests that the key advantage of AOT may lie not in its ability to mimic
4

---

LLMs Can Reason Faster Only If We Let Them
4
For each problem in our training set, first obtain valid solution that successfully reaches the goal state. This solu- tion can be obtained through various means, including tra- ditional planning algorithms even using an LLM. While using an I.LM might initially yield a lower percentage of cor- rect solutions compared to curated datasets, this approach offers greater flexibility and scalability. The efficiency trade- off becomes a design choice based on specific requirements and available resources.
AoT-Short
3
2-
0
40
60
80
100
120
4
Our training examples are structured around the concept of state transitions guided by explicit thinking steps. Each transition follows the format:
AoT-Medium
3-
2-
State: [Current state description] Thinking/Transition [Selection of an action and considering its effects] Next state: [New state description]
1-
0
20
40
60
80
100
120
The thinking component serves as a crucial bridge between states, providing the model with explicit reasoning that jus- tifies the transition. This structured format helps the model learn the relationship between states, actions, and their con- sequences. Importantly, any given state in the sequence starting point for the next transition, allowing for both forward progression and backtracking when necessary.
AoT-Long
2-
1-
0
20
40
60
80
100
120
An example output from the model could be represented as y = {(so G0 Soo), (so s01). 401, S000). (823424
Steps
21
Sgoal) } or = [Ti, T2, Thmal J. As seen from this representation, at each step, the model has a choice to start from a previous state and an action to perform on that state. This leads to partial expansion, which is especially effective for memory usage when the number of branches are very large in classical planning problems with programs. In our case, are limited by the context in two ways: firstly, LLMs have maximum context window limit that they are pre-trained for, and secondly, it is observed the literature that LLMs may fail to attend to some parts the context large context sizes, especially the middle (Liu al., 2024). There exists works showing possible heuristics and algorithms that complete (like A*) such as Partial-Expansion A (Yoshizumi et al., 2000; Felner et al., 2012).
028424
Figure 2. Effect of varying steps for demonstrations to generated solations in AoT
4. AoT-03
In typical RLHF pipeline, have SFT stage, reward model training stage and finally RL training stage. In our framework, we will incentivize models to generate solutions with less total number of steps while still generating valid solutions. Since both of these objectives are objective, we do not necessarily need the second stage which is the reward model training stage, however, will talk about the reward model its own subsection nevertheless.
We generate random but valid exploration paths by starting from either the initial state or intermediate states. At each state, model considers possible actions and their conse- quences through the thinking step before transitioning the next state. This process creates diverse set of trajectories that may include both promising paths toward the goal and dead-ends that require backtracking.
4.1. SFT Stage
The supervised finetuning (SFT) stage aims train the model follow AoT-style planning while maintaining so- lution quality. Similar to how AoT uses carefully crafted in-context examples to guide LLMs' planning process, we create training dataset that demonstrates effective planning strategies. However, instead of relying on human-ann authored intuitions in the search trajectories, we utilize random search paths that lead to valid solutions.
These exploration trajectories are then combined with seg- ments of successful solution paths. The resulting training examples demonstrate both the exploration of the search
5

---

LLMs Can Reason Faster Only If We Let Them
space and eventual convergence valid solutions. This combination teaches the model to balance exploration with goal-directed behavior.
introduce step count penalty term for correct solutions:
V(T. max(1 - na, 3) + KlTTew
if y is correct
if y is incorrect
The SFT objective follows standard language model finetun- ing approaches, using teacher forcing with a cross-entropy loss:
(2)
where is the number of steps in the solution, a is the step penalty factor, , is the cut-off to protect long solutions being given less reward then incorrect solutions, e.g., 3 = -0.5, K controls the incentive if the transition was in the path of the correct solution, and y is the correct CoT solution that can be extracted from a correct solution y. In cases where might be difficult to extract correct solution trace, we can simply set K O. We show in our experiments that K. term is not crucial, though helps with faster adaptation and slightly higher performance. This formulation creates a clear trade-off: while the model is primarily incentivized to find correct solutions, it receives higher rewards for doing so with fewer steps.
(()) -- Σ log pe (yola,,
where x: = (Sstart, Sgeal) is the input problem specification and y is the target sequence containing the state-thinking- transition triplets.
The training process develops several key capabilities in the model. It learns to systematically explore the search space while maintaining accurate state tracking. The ex- plicit thinking steps help the model develop robust reason- ing about state transitions and their consequences. The model also learns to recognize promising solution paths and successfully navigate toward goal states.
The choice of a is crucial and depends on both the problem domain and the context window constraints. For given problem type and context window size w, we aim to set such that:
This supervised learning phase establishes the foundation for the subsequent RL optimization stage. While the SFT stage focuses on teaching the model the basic structure of planning with thinking steps, the RL stage will introduce rewards to encourage more efficient solutions while main- taining these core planning capabilities.
wa Z 3
(3)
This ensures that a correct solution using the maximum available context length receives reward slightly higher than an incorrect solution. Such calibration helps to have more fine fineggrinedd levels of brevity to rewarded correctly.
Our reward model notably differs from traditional ap- proaches in RLHF by eschewing learned reward models in favor of this objective metric. This design choice offers several advantages: it eliminates the need for reward model training, reduces computational overhead during RL train- ing stage and provides clear, interpretable feedback to the model. Most importantly, it creates direct optimization pressure for finding shorter valid solutions while maintain- ing the priority of solution correctness.
4.2. Reward Model
While traditional reward models in language model align- ment often rely on human feedback or complex learned reward functions, our objective is more straightforward: we with the model to generate solutions that are both correct and efficient. To this end, we develop simple but effective reward function that balances solution validity with length efficiency. In this section, we will use V for our reward models due to them actually being value models used in RL frameworks. This difference stem from the fact that most RLHF frameworks consider the whole solution as single action, therefore framing the problem which reward and value models are the same. In our frame- work, we consider each transition step as an action, leading to our following feedback models being value models. If they were to be thought of as actual reward models, due to their definitions, the language model would try to hack the reward by being close the solution but prolonging the solution to receive more total reward, confficting with our intention of shorter solutions.
Reward model alternatives. The problems we focus on, i.e., planning problems, typically have the trait of verifying the solutions are much easier than producing solutions to them. This assumption also affects the reward function we propose in (2). In cases where we have more compute available but the number of examples are more limited, it is possible to have even finer grained feedback to the model still with the assumption of no human-feedback. Consider the following reward model,
single-step RL, in
to Sguat)
(aap:/ro(lll((--aa-000 (soouttion y is correct),
(4)
The base reward structure assigns +1 for correct solutions and 11 for incorrect ones, providing a clear signal for solu- tion validity. However, this alone would not encourage the model to find more concise solutions. To address this, we
where T" refers to the ending state in transition T' and x (T', (goal) is the new problem where we prompt the model. Here, we would like to attract attention to binary reward is coming from not the solution of the model for the starting
6

---

LLMs Can Reason Faster Only If We Let Them
problem, but the newly constructed problem at each state. This enables the model learn per each transitions whether the whole solution was correct or not and whether T; is in the path that lead to the correct solution. In reward function (2), we either gave negative feedback for all transitions in case of an incorrect solution, or gave a positive reward for all transitions when the solution was correct. However, the reward function in (2), also makes the distinction whether transition was indeed important for the solution of the problem by the term.
to help with mode collapse, an unwanted phenomenon that occurs when the model exploits without enough exploration, leading to suboptimal policies (Williams & Peng, 1991; Ziebart et al., 2008; Mnih, 2016).
The training process samples planning problems from our dataset and allows the model to generate complete solutions, receiving rewards based on both correctness and solution length. This creates direct optimization pressure toward finding more efficient solutions while maintaining the fun- damental planning capabilities established during the SFT stage.
4.3. RL Training Stage
The reinforcement learning stage builds upon the supervised finetuning by optimizing the model for solution efficiency while maintaining correctness. The core objective is to maximize the expected reward under the policy distribution:
5. Experimental Results
We evaluate AoT-03 across two challenging planning bench- marks: Game of X and N-Puzzle. Our experiments utilize three open-source models of varying sizes: Gemma2-2B, Llama3- 1B, and Llama3-3B. We compare our approach against two baselines: traditional Chain-of-Thought with su- pervised fine-tuning (CoT-SFT) and Algorithm of Thoughts with supervised fine-tuning (-oT-)FT). Our evaluation fo- cuses on both solution accuracy and efficiency, measured by the number of reasoning steps required to reach solution.
(0) = EEND [By~xo(ia)) [Er (Ti, v)]]
(5)
where D is the dataset of problems, To represents the lan- guage model being trained, r represents the input planning problem, and -( is our length-aware reward function that balances solution correctness with efficiency defined in (2).
5.1. Problem Setups
This optimization can be accomplished through various RL algorithms developed for language models. Trust Region Policy Optimization (TRPO) (Schulman et al., 2015), Prox- imal Policy Optimization (PPO) (Schulman et al., 2017; Ziegler et al., 2019; Ouyang et al., 2022) and REINFORCE leave-one-out (RLOO) (Ahmadian et al., 2024) have all demonstrated success in language model alignment tasks. Each algorithm offers different tradeoff's between training stability, computational efficiency, and implementation com- plexity.
Game of X. We introduce a generalized variant of the Game of 24, which presents a significantly more challeng- ing planning problem. In our version, five numbers are randomly sampled, and players must construct mathemat- ical expressions using arbitrary combinations of addition, subtraction, multiplication, and division operations to reach a target value. This formulation creates a substantially larger search space compared to the traditional Game of 24, requir- ing more sophisticated planning and arithmetic reasoning capabilities.
The key distinction of our approach lies in the reward struc- ture rather than the specific RL algorithm choice. Our re- ward function provides clear, objective feedback about both solution correctness and length efficiency, eliminating the need for learned reward models complex advantage esti- mation schemes. This simplification allows us to focus on the core challenge of finding shorter valid solutions without introducing additional training complexity. In our experi- ments later, we will utilize RLOO.
N-Puzzle. We utilize the classic 8-puzzle variant of the sliding tile puzzle, where eight numbered tiles are arranged 3x3 grid with one empty space. Each puzzle instance is generated by starting from the goal state (tiles arranged in numerical order) and applying random sequence of 80- 120 valid moves to ensure solvability. The objective is to return the tiles to their original ordered configuration by sliding tiles into the empty space. This creates challenging planning problem with branching factor of up to 4 at each step and requires careful consideration of move sequences to avoid cycles or dead ends.
To maintain stability during RL training, we employ a refer- ence model (the SFT model) to ensure the optimized policy does not deviate too far from learned planning behaviors. This constraint can be implemented through various mecha- nisms depending on the chosen RL algorithm, such as KL di- vergence penalties or direct probability ratio clipping. In our setting, the KL divergence has the added benefit of entropy regularization, popular in general RL setting. It is known
Word Ladder. We implement the classic word ladder puzzle, where the objective is to transform one word into another by changing a single letter at a time, with each inter- mediate step forming a valid English word. Our dataset is constructed using the NLTK base words dataset, focusing on
7

---

LLMs Can Reason Faster Only If We Let Them
Accuracy (%)
Solution Length (steps)
Problem
Method
Gemma2-2B
Llama3-IB
Llama3-3B
Gemma2-2B
Llama3-1B
Llama3-3B
CoT-SFT
32
24
35
4
4
AoT-SFT
63
55
66
33.5
31.9
37.2
Game of
AoT-O3 (K = 0)
74
79
18.3
11.6
15.0
AoT-O3
78
72
82
16.3
9.7
14.5
CoT-SFT
34
36
42
8.1
8.3
7.9
AoT-SFT
66
64
71
24.8
26.0
33.1
N-Puzzle
AoT-O3 (K = 0)
71
68
71
18.0
14.9
17.0
AoT-O3
73
68
75
17.9
14.2
15.7
CoT-SFT
11
14
6.3
5.5
6.6
AoT-SFT
59
47
63
32.0
26.1
31.7
W-Ladder
AoT-O3 (K = 0)
59
66
18.6
16.2
20.1
AoT-O3
66
18.2
13.8
16.0
Table Performance comparison CoT-SFT, AoT-SFT, and AoT-O3 across different model sizes on Game of X, N-Puzzle and Word- Ladder benchmarks. Results show both accuracy (percentage of successfully solved problems) and solution length (average number of reasoning steps). AoT-O3 consistently achieves higher accuracy while requiring significantly fewer steps across all models tasks.
words ranging from to 10 letters in length. Test instances are generated by first selecting random word pairs of equal length from this corpus, then verifying that a valid solution path exists between them with lengths ranging from to 10 steps. This formulation creates challenging planning problem where the actions require language knowledge, and success requires careful navigation through the lexical graph while avoiding invalid words or circular paths.
improving accuracy from 55% to 72%. For the N-Puzzle benchmark, we observe moderate but consistent improve- ments. AoT-O3 achieves solution length reductions between 27.8% and 46.0% while maintaining or improving accuracy. The smaller efficiency gains compared Game of X can be attributed to N-Puzzle's larger state space and more complex state transitions. The Word-Ladder results are particularly interesting as they demonstrate AoT--33's effectiveness in domains where actions must be derived from the LLM's prior knowledge of valid English words. Despite this addi- tional complexity, AoT-O3 achieves 47.1% reduction in solution length (from 26.1 13.8 steps) while improving accuracy from 47% to 52% on Llama3-1B BB. This suggests that our approach effectively combines the model's learned knowledge with efficient planning strategies. These im- provements in efficiency do not come at the cost of accuracy we observe consistent accuracy gains across all models and benchmarks. This indicates that our approach not only pro- motes efficient solutions but also helps models develop more robust planning strategies through focused exploration of the solution space. The results are particularly promising for applications where context window limitations or com- putational resources are constrained, as AoT--3 can achieve better performance with significantly fewer tokens.
5.2. Training and Testing Protocols
For both benchmarks, we implement a two-phase training approach. The supervised fine-tuning (SFT) phase consists of 500 training steps with a batch size 128 and a learning rate le-5. This followed by the reinforcement learning phase using RLOO (REINFORCE leave-one-out), where we employ smaller batch size of 32 due to VRAM constraints and reduced learning rate of le-6. During the RL phase, we generate 4 samples per problem to estimate policy gradients while maintaining reasonable computational requirements. Additionally, we set = -0.5 and x = 0.2. Further details are given in Appendix B.
5.3. Results and Analysis
Table 2 presents comprehensive results comparing AoT-O3 against CoT-SFT and AoT-SFT baselines across three bench- marks and multiple model sizes. Our results demonstrate consistent improvements in both accuracy and solution ef- ficiency. In the Game of X benchmark, AoT-O3 achieves substantial improvements across all models, with solution length reductions ranging from 51.3% to 62.4% while simul- taneously improving accuracy by 11-17 percentage points. The most notable improvement is observed with Llama3- IB, reducing solution length from 31.9 to 9.7 steps while
6. Conclusion
In this work, we introduced AoT-O3, RL-enhanced AoT framework that improves the efficiency of LLM-driven plan- ning. By using a reward model that optimizes for both accuracy and conciseness, our approach reduces reasoning steps while maintaining quality. Results show up 80% reduction in solution length across benchmarks, demonstrat- ing how structured learning and reinforcement fine- fine-tuning can make LLM planning more scalable and efficient.
8

---

LLMs Can Reason Faster Only If We Let Them
Impact Statement
Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J.,
Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKin- non, C., et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08000 2022.
This work has significant environmental and accessibility implications for Al deployment. By reducing token usage by up 80% while maintaining or improving performance, our method could substantially decrease the energy consump- tion and carbon footprint of large-scale LLM deployments. Given current LLM usage patterns, even a 30% reduction in tokens could save tens of gigawatt-hours annually, equiva- lent to the electricity usage of thousands homes. However, such efficiency gains could also accelerate I.I.M adoption and lead to higher net resource consumption through the Jevons paradox. Additionally, while improved planning capabilities may enhance AI systems' problem-solving abil- ities, this could accelerate automation in ways that affect human employment. We recommend careful consideration of these tradeoffs as the technology is deployed, along with continued research into techniques that balance computa- tional efficiency with societal impact.
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Pod- stawski, M., Gianinazzi, L.. Gajda, J., Lehmann, T., Niewiadomski, H., Nyezyk, P., et al. Graph of thoughts: Solving elaborate problems with large language models. Proceedings of the AAAI Conference on Artificial In- telligence, volume 38, pp. 17682-17690, 2024.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Chen, M.. Tworek, J., Jun, H., Yuan, Q.. Pinto, H. P. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374. 2021.
Acknowledgments
This work was supported in part by the National Science Foundation under grants 23311233177 and IIS-2312794, the Amazon- Amazon-Virginia Tech Initiative for Efficient and Robust Machine Learning, and the Commonwealth Cyber Initiative. Bilgehan Sel acknowledges support through a grant from the Virginia Tech Initiative for Efficient and Robust Machine Learning. Lifu Huang acknowledges the support by the award No. 2238940 from the Faculty Early Career Development Program (CAREER) of the National Science Foundation (NSF). Naren Ramakrishnan acknowledges the support by the awards, US NSF grants IIS-2312794 CMMI- 2240402.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung. H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Amazon-Virginia
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
Earth. Org.
Generative ai is exhausting the power grid. Earth 2024. URL https:
//earth.org wwtg///ggeaggeeeeeaeeereeee
References
/exhausting the pww-ppooeerrrreeee 2025-01-30.
Accessed:
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
Felner, A., Goldenberg, M., Sharon, G., Stern, R., Beja, T., Sturtevant, N., Schaeffer, J., and Holte, R. Partial- expansion a* with selective node generation. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 471 471-477, 2012.
Agency, I. E. Ai, cryptocurrency, and data centers: Projected energy consumption by 2026. Data Center Frontier, 2024. URL
Huang, J. and Chang, K. C.-C. Towards reasoning in
large language models: survey. arXiv preprint arXiv:22 10403, 2022.
com//eeercy/aarricl//3333444///
tee-study-sees--a-ccyyyoooouuo (consumption-by by 2026. Accessed: 2025-01-30.
Jiang. J., Wang, F., Shen, J., Kim, S., and Kim, S. A survey on large language models for code generation. arXiv preprint 24Xx::246600015 2024.
Ahmadian, A., Cremer, C., Gallé, M., Fadaee, M., Kreutzer, J. Pietquin, O., Üstün, A., and Hooker, S. Back to basics: Revisiting reinforce style optimization for learning from human feedback in lmss. arXiv preprint arXiv:2022. /4740, 2024.
Jin, M. Sel, B., Hardeep, F., and Yin, W. Democratizing energy management with Ilm assisted optimization aut- oformalism. In 2024 IEEE International Conference on Communications, Control, and Computing Technologies

---

LLMs Can Reason Faster Only If We Let Them
for Smart Grids (SmarGrriCComm), pp. 258-2081 263.. IEEE, 2024.
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prahhumoye, S., Yang, Y., al. Self-refine: Iterative refinement with self- feedback. Advances in Neural Information Processing Systems, 36, 2024.
Kahneman, D. Thinking, fast and slow. Farrar, Straus and Giroux, 2011.
Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., and Murthy, A. Lims can't plan, but can help planning in Ilm-modulo frame- works. arXiv preprint arXiv:2402.0/1 2402001817. 2024a.
Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202. 1283, 2022.
Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt. L. P., and Murthy, A. B. Position: Lims can't 't plan, but can help planning in l1m- modulo frameworks. In Forty-first International Confer- ence on Machine Learning, 2024b.
Mnih, V. Asynchronous methods for deep reinforcement learning. arXiv preprint arXiv:1602.0178. 2016.
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H.,
Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint a 12.00/ 14, 2021.
Kamoi, R., Zhang, Y., Zhang. N., Han, J., and Zhang, R. When can lims actually correct their own mistakes? critical survey of self-correction of Ilms. arXiv preprint S.Ki:22406.01297, 2024.
Ouyang. I.., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A.. et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 11227300227444 2022.
Katz, D. M., Bommarito, M. J., Gao, S., and Arredondo, P. Gpt-4 passes the bar exam. Philosophical Transactions of the Royal Society A, 382(2270)):222022454 2024.
Paul, D.,, Ismayilzada, M., Peyrard, M., Borges, B., Bosse- lut, A., West, R., and Faltings, B. Refiner: Reasoning feedback on intermediate representations, arXiv preprint arXiv:2304.0199 2023.
Kim, G., Baldi, P., and McAleer, S. Language models can solve computer tasks. Advances in Neural Information Processing Systems, 36, 2024.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Ad- vances in neural information processing systems, 35: 22199-22213, 2022.
Radford, Improving language understanding by genera- tive pre-training. 2018.
Radford, A.,
Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al. Language models are unsupervised multitask learners. OpenAl blog, 188):9 2019.
Lei, B., Liao, C., Ding, C., et Boosting logical reasoning in large language models through a new framework: The graph of thought. arXiv preprint arXiv:2308. 08614, 2023.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances Neural Information Processing Systems, 36, 2024.
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., et al. Competition-levell code generation with alpha- code. Science, (76644) 1097, 2022.
Rasley, J., Rajbhandari, S., Ruwase O., and He, Y. Deep- speed: System optimizations enable training deep learn- ing models with over 100 billion parameters. Proceed- ings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Dala Mining, pp. 3505-3506. 2020.
Liu, N. F., Lin, K., Hewitt, J., Paranjape, A., Bevilacqua, M., Petroni, F., and Liang, P. Lost the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12: 12:157-173, 2024.
Long, J. Large language model guided tree-of-thought arXiv preprint arXiv:2305.0829) 2023.
Russell, S. J. and Norvig, Artificial intelligence: mod- ern approach. 1995.
Ma, X., Mishra, S., Beirami, A., Beutel, A., and Chen, Let's do a thought experiment: Using counter- factuals to improve moral reasoning. arXiv preprint arXiv:2306. 14308, 2023.
Samsi, S., Zhao, D., McDonald, J., Li, B., Michaleas, A., Jones, M., Bergeron, W., Kepner, J., Tiwari, D., and Gadepally, V. From words to watts: Benchmarking the energy costs of large language model inference. In 2023
10

---

LLMs Can Reason Faster Only If We Let Them
IEEE High Performance Extreme Computing Conference (HPEC), pp- 1-9. IEEE, 2023.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi,
E., Le, Q. V., Zhou, D., et al. Chain-of- -fthoughtt prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-2488 2022.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In Bach, F. and Blei, D. (eds.). Proceedings of the 32nd International Conference on Machine Learning, vol- ume 37 of Proceedings of Machine Learning Research, pp. 1889-1897, Lille, France, 07-09 Jul 2015. PMLR. URLhttpa httpppppoocenn...e/c mlr wwwppprsss//.. schulman15. html.
Williams, R. J. and Peng, J. Function optimization using connectionist reinforcement learning algorithms. Con- nection Science, 3(3):241-268, 1991.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y. React: Synergizing reasoning and acting language models. arXiv preprint urXiv:2210.0300 2022.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint (rXXv:1707.06347 2017.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Sel, B., Shanmugasundaram, P., Kachuee, M., Zhou, K., Jia, R., and Jin, M. Skin-in-the- game: Decision making via multi-stakehooldr alignment in Ilms. arXiv preprint arXiv:2405. 12933, 2024a.
Yao, Y., Li, Z., and Zhao, H. Beyond chain-of-thougee effective graph-of-thone reasoning in language models. arXiv preprint arXiv:2.055. 16582, 2023.
Sel. B., Tawaha, A., Khattar, V., Jia, R., and Jin, M. Algo- rithm of thoughts: Enhancing exploration of ideas in large language models. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp. F. (eds.), Proceedings of the 41st International Conference on Machine Learning. volume 235 of Proceedings of Ma- chine Leurning Research, pp. 44136-44189, PMLR, 21- 27 Jul 2024b. URL https: / htte///pooccee/ proceedings mml.. press/v235/sel22 html.
Yoshizumi, T. Miura, T., and Ishida, T. A with par- tial expansion for large branching factor problems. In AAAI/IAAI, pp. 923-929, 2000.
Yuan, A., Coenen, A., Reif, E., and Ippolito, D. Wordcraft: story writing with large language models. In Proceedings of the 27th International Conference on Intelligent User Interfaces, pp. 841-852, 2022.
Sel, B., Jia, R., and Jin, M. Lims can plan only if we tell them. 2025. URL 2501.13545
Zelikman, E., Lorch, E., Mackey, L., and Kalai, A. T. Self- taught optimizer (stop): Recursively self-improving code generation, arXiv preprint arXiv:2310.02304 2023.
Valmeekam, K., Marquez, M., and Kambhampati, S. Can large language models really improve by self-critiquing their own plans? arXiv preprint arXhv:2310.08118, 2023.
Zelikman, E., Harik, G., Shao, Y., Jayasiri, V., Haber, N., and Goodman, N. D. Quiet-star: Language models can teach themselves think before speaking, arXiv preprint wwXiv:2403.09622 2024.
Valmeekam, K., Stechly, K., and Kambhampati, S. Llms still can't ' plan; can Irms? a preliminary evaluation of ope- nai's ol on planbench. arXiv preprint arXiv:2409.13373, 2024.
Zhang, Z., Zhang. A., Li, M., and Smola, A. Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.034933 2022.
Vaswani, A. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Wang, X., Wei, Schuurmans, D., Le, Q., Chi, F., Narang, S., Chowdhery, A., and Zhou, D. Self-consistency im- proves chain of thought reasoning in language models. arXiv preprini 2203:2203.11177. 2022.
Zhao, W. X., Zhou, K., Li, J., Tang. T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., Dong, Z., et al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
Webb, P. System 3 Thinking: How to Choose Wisely when Facing Doubt, Dilemma, Or Disruption. Inten- tional Training Concepts Pty Limited, 2021. ISBN
Zhou, D., Schärli, N., Hou, L., Wei, J., Scales, N., Wang. X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q. et al. Least-to-mos prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625 2022.
9781922553560. URL https: aattps://books /books..........ooo....k....koo. google. com/books? (aiiissiiiMM111166 1=MI.G622EEAAAA.

---

LLMs Can Reason Faster Only If We Let Them
Ziebart, B. D., Maas, A. L.,, Bagnell, A., Dey, A. K., al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433-1438. Chicago, IL, USA, 2008.
Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P., and Irving, G. Fine-tuning language models from human preferences. arXiv preprint arXiv: 085999999909,9..... 2019.
12

---

LLMs Can Reason Faster Only If We Let Them
A. Energy and Token Usage Calculations
In this appendix, we provide a detailed estimation of the current token usage in ChatGPT and potential energy savings from reducing token counts, All values and references herein are approximate but illustrate the magnitude of efficiency gains possible scale.
A.1. Estimating Token Usage
User Base and Queries. As of December 2024, ChatGPT has over 300 million weekly active users, with users sending more than I billion messages daily.² Assuming each message involves an average 400 tokens - encompassing both user input and model output can estimate the total token usage.
Total Daily and Yearly Token Count. Given over I billion messages daily, the total daily token amounts to 400 billion. Extrapolating to full year results in approximately 146 trillion tokens per year.
A.2. Energy Usage per Token
Energy consumption per token varies with model size, hardware, and data-center efficiency. Research estimates that models like LLaMA 65B consume about 3-4 joules per token (Samsi et al., 2023). Since joule 2.77778 x 10-7 kWh, 3 3 joules per token converts to roughly 8.33 10-7 kWh/token 1.11 10-6 kWh/token. We use the midpoint 9.72 10-7 WWhttoken for calculations.
A.3. Daily and Annual Energy Consumption
Using the midpoint estimate, see 400 billion tokens/day 9.72 10-7 kWh/token ss 388.8 MWh/day.
Over one year, 388.8 MWh/day 365 141.9 GWh/year.
A.4. Potential Savings from Token Reduction
Reducing token usage by 30% results in approximately 42.6 GWh/year.
If we cut token counts by half, approximately 71 GWh/year savings in energy usage.
A.5. Contextualizing the Energy Savings
Residential Electricity Usage. According to the U.S. Energy Information Administration (EIA), the average annual electricity consumption for a U.S. residential utility customer was about 10,791 kWh in 2022.3 Hence:
42.6 GWh/year savings
x electricity usage
42 42.6x10 kWh 10,791 kWishome
2s 3,948 homes for a year.
71 GWh/year savings electricity usage of about
71x 10 kWh 10,791 kWishome
6,580 homes for year.
Carbon Emission Reductions.
Using estimate of 0.81 pounds (0.367 kg) of CO2 emitted per kWh in the U.S.4:
42.6 GWh + 42.6 x10 kWh 0.367 kg CO,/WWh 15,634 metric tons CO2-
71 GWh > 71 x 10 kWh x 0.367 kg CO,/kWh = 26,057 metric tons CO2-
These quantities correspond to removing thousands of gasoline- cars from the road or preserving thousands of acres of forest in terms of carbon offsets (see Fig. 3).5
'https: Phttps://wee
13

---

LLMs Can Reason Faster Only If We Let Them
Scenario 1:
Scenario 2:
CO2
30% token reduction
50% token reduction
Energy savings:
Energy savings:
42.6 6 GWh/year
71 GWh/year
CALCULATOR
"Greanhouse
Carbon emission reduction:
Carbon emission reduction:
Equivalencies Calculator
hntps///wwwsp wwwenerggggeenhoooe gos equivolercic cie colcuiator
15,634 metric tons/year
26,057 metric tons/year
gasoline-powered passanger vehicles driven for one year
3,647
6,078
17,366,480
2,932,036
pounds of coal burned
tons of waste recycled instead landfilled
5,524
9,207
tree seedlings grown 10 years
258,510
430,855
acres of U.S. forests in one year
15,682
26,137 137
Figure 3. Illustration of two scenarios-4 30% (pink) vs. 50% (green) reduction in token usage-andd illustrates their equivalent environ- mental impacts (e.g., cars off the road, coals burned, waste recycled, seedlings grown, of forest). These numhers contextualize the calculations by showing how modest efficiency gains can yield significant benefits for emissions and resource consumption.
Overall, these estimates highlight the potential environmental and cost impact that arises from large-scale LLM inference. Even moderate gains in token efficiency (c.g., 30-50%) can translate tens of gigawatt-hours saved annually and correspondingly meaningful CO2 reductions.
Key Assumptions and Limitations In these estimates, data center energy efficiency (often quantified by Power Usage Effectiveness, or PUE) plays a major role. An ultra-efficien center with a PUE near 1.1 uses roughly 10% extra overhead (e.g., cooling and networking), whereas a PUE above 1.5 can raise total consumption by 50% or more. Thus, even if token usage shrinks by 30-50%, the real reduction in total energy may be proportionally less depending on the facility's PUE. Moreover, the uniform--ooen--saving assumption-that energy reduction scales linearly with fewer tovens-sverlooks fixed overheads (e.g., loading the model into memory each query) that may blunt the full benefits of shorter outputs. Finally, unaccounted training energy can weigh in daily inference usage when models are re-trained frequently or undergo large-scale fine-tuning cycles. Hence, while reducing tokens helps, it alone cannot capture Al's entire environmental footprint. We also did not account for the complex Jevons paradox, i.e., technological improvements increase the efficiency of resource use, which may paradoxically lead to an overall increase in the consumption of that resource.
B. Experiment Details
This appendix provides comprehensive details about our experimental setup, hyperparameters, and implementation choices to ensure reproducibility of our results.
B.I. Model Specifications
We conducted experiments using three open-source language models:
Gemma2-2B: 2 billion parameters, using bfloat16 data type.
Llama3-1B: 1 billion parameters, using 6 data type.
Llama3-30 3B: 3 billion parameters, using 6 1 data type.
14

---

LLMs Can Reason Faster Only If We Let Them
All models trained 8x NVIDIA H100 GPUs with 80GB memory. For multi-GPU training, utilized DeepSpeed (Rasley et al., 2020) with suitable gradient accumulation step of to maintain effective batch sizes while managing memory constraints for the various models we trained.
B.2. Dataset Construction
For each benchmark, we constructed datasets following these specifications:
Game of X
Training set: 64,000 examples
Test set: 100 examples
Numbers sampled uniformly from [1, 100]
Target values sampled uniformly from [1, 100]
Filtered to ensure each problem has at least one valid solution
N-Puzzle
Training set: 64,000 examples
Test set: 100 examples
Initial states generated with 80-120 random moves from goal state
Manhattan distance from initial goal state ranging from 15 30
Word Ladder
Training set: 32,000 examples
Test set: 100 examples
Word length range: 4-10 characters
Solution path length range: 4-10 steps
Dictionary: NLTK Words Corpus (filtered for common English words)
B.3. Training Protocol
Our training process consisted of phases: Supervised Fine-tuning (SFT) and Reinforcement Learning (RL). Here detail the specific parameters and protocols for each phase.
B.3.1. SUPERVISED FINE-TUNING PHASE
Optimization Parameters
Optimizer: AdamW
Base learning rate: le-5
Weight decay: 0.01
Gradient clipping: 0.1 (max norm)
Batch size: 128 (effective, after gradient accumulation)
15

---

LLMs Can Reason Faster Only If We Let Them
Training steps: 500
Wa steps: 50
Learning rate scheduler: Cosine annealing
Implementation Details
Mixed precision training (BF16)
Gradient checkpointing enabled
Token sequence length: 2048
Padding: Dynamic batching with attention masking
B.3.2. REINFORCEMENT LEARNING PHASE
We utilized trl library from huggingface, however, we needed to have a custom RLOO trainer implementation with minor but crucial differences to the original library due to being designed for LLM reward models.
RLOO Implementation
Algorithm: REINFORCE leave-one-out
Base learning rate: le-6
Batch size: 32
Samples per problem: 4
KL penalty coefficient: 0.1
Value loss coefficient: 0.5
Reward Model Parameters
Step penalty factor (a:): 0.02
Minimum reward cutoff (8): -0.5
Solution path bonus (x)): 0.2
Training Schedule
Total steps: 50
Warm-up steps: 50
Learning rate schedule: Cosine annealing
B.4. Evaluation Protocol
During evaluation, used the following settings:
Inference Parameters
Temperature: 0.0
Top-p (nucleus sampling): 0.0
Maximum new tokens: 1024
Repetition penalty: No
16


Reviews:
[{"review_id": "nlIpwU29Gm", "reviewer": "Reviewer_nYkW", "summary": "This paper proposes AoT-O3, a RL based approach that reduces solution length in LLM based planning while preserving improving accuracy. It builds on already popular Algorithm of Thoughts  by adding a reward function. Experiments on 3 benchmarks show a reduction in reasoning steps and higher success rates compared to existing baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. We are encouraged that our paper is recognized as \"computationally viable\" and \"simpler to deploy\". We have acted on the reviewer's suggestions to provide new experimental results and provide clarifications.\n\n****\n**Response to Weaknesses**\n1. Our whole approach includes the identification of unnecessary exploration in AoT, and repurposing already existing RL libraries to improve performance and efficiency. As you have also pointed out, \"boosting model accuracy while cutting power consumption and simplifying the training pipeline is essential\". Recognizing that *simplicity being the ultimate sophistication*, we see our whole approach as much more practical and easier to use.\n\n2. **We have used the same hyperparameters ($\\alpha=0.02$, $\\beta=-0.5$ and $\\kappa=0.2$ ) in all five domains, including the newly added Blocksworld and Logistics**, showing significant improvements in all the domains. We would like to add that **these domains are highly different in terms of their state and actions, implying the generalizability of the hyperparameters we used**. Moreover, we used the same hyperparameters in our new results with PPO, showcasing the generalizability of the hyperparameters.\n\n3. Thank you for these suggestions. We chose RLOO for being more VRAM friendly. However, **we added new results for PPO for Gemma2-2b and Llama-3.2-1B with PPO instead of RLOO**.\n\n| Problem   | Method | Accuracy (%) |           |           | Solution Length (steps) |           |           |\n|-----------|--------|--------------|-----------|-----------|-------------------------|-----------|-----------|\n|           |        | Gemma2-2B    | Llama3-1B | Llama3-3B | Gemma2-2B               | Llama3-1B | Llama3-3B |\n| Game of X | AoT-O3 | 80           | 75        | 83        | 15.1                    | 10.2      | 12.8      |\n| N-Puzzle  | AoT-O3 | 74           | 69        | 77        | 16.4                    | 15.8      | 17.2      |\n| W-Ladder  | AoT-O3 | 61           | 51        | 66        | 19.5                    | 14.4      | 15.7      |\n\n****\n**Response to Questions**\n1. Thank you for this highly relevant question to our comment in the introduction of our paper. As we have shown in the Section 3.2, the solution lengths of AoT are highly effected by the length of the in-context examples. This hinted us that shorter solutions were indeed possible, which lead to our method. In our perspective, shorter solutions being possible, indicates that the model is unnecessarily exploring for significant amount of time before giving an answer. The RL stage reducing these total steps significantly, shows us that the AoT-prompted or the AoT-SFT models imitating a significant part of the exploration, therefore imitating.\n\n****\n**Conclusion**\n\nWe will also fix the typos mentioned in the camera-ready version. **We thank you in advance for checking our rebuttal and reconsidering your score if you believe our explanations and the introduction of new results alleviated your concerns**. If you have further questions, as far as we understand from the new ICML guidelines, you can only respond one more time (review → rebuttal → reviewer reply → author reply). Therefore, we kindly request you to be precise about your remaining concerns in your response. **Also, please be sure to check our responses to other reviewers where we have introduced new results with utilizing fewer training data, and applying RL without the SFT stage to show the importance of AoT-O3, even in cases where we do not have the SFT stage.**", "claims_and_evidence": "The claims made in this paper are coherent.", "methods_and_evaluation_criteria": "The authors demonstrate their approach on multiple diverse tasks (math-based puzzles, sliding tile puzzles, word-ladder transformations), suggesting good generalization potential.", "theoretical_claims": "No major theoretical claims mentioned in the paper.", "experimental_designs_or_analyses": "Experiments looked logical and sound to me.", "relation_to_broader_scientific_literature": "The paper merges a cost sensitive RL alignment with Algorithm of Thoughts to improve the planning capabilities.", "essential_references_not_discussed": "They cite the relevant papers to the best of my knowledge.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well written and easy to understand.\n2. This area of research is highly significant: boosting model accuracy while cutting power consumption and simplifying the training pipeline is essential.\n3. Unlike exploratory techniques like Tree of thought, AoT-O3 operates within a single pass, making it more computationally viable and simpler to deploy.\n\n\nWeakness:\n\n1. Their approach provides only incremental novelty, as it simply extends a standard RL alignment with a step-cost penalty, offering little beyond an otherwise well known method.\n2. The success of the length-aware reward depends upon careful hyperparameter tuning which might be non-trivial for new domains.\n3. Since the paper uses a RLHF design, it would make sense to include SFT with other RL training baselines like PPO.", "other_comments_or_suggestions": "Line 308/309 do not make much sense : \"we with the model to generate solutions that are both correct and efficient\"", "questions_for_authors": "Can you explain why current AoT implementations may be imitating rather than truly engaging in System 3 thinking?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iMkF2Jj1DK", "reviewer": "Reviewer_sDQc", "summary": "The authors claim that while AoT has improved performance compared to CoT, they generally suffer from significantly longer solutions. To deal with this, they proposed AoT-O3, which use AoT generated solutions to optimize models with both accuracy (supervised and RL) and solution length (RL). The proposed method AoT-O3 shortens solution length by up to 80% compared to baseline AoT while maintaining or surpassing performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. In the following, we provided clarifications and our responses to the reviewer's concerns.\n\n****\n**Response to Essential References Not Discussed**\n\n**Although, authors cannot be expected to discuss papers that have not been made public before 4 months according to ICML reviewer guidelines** (arxiv submission: 4th of November, NeurIPS public announcement: 6th of November), we want to assure the reviewer that the work suggested is a way to reduce the number steps in CoT reasoning by skipping steps. Our work on the other hand, is not about skipping steps, but eliminating unnecessary exploration of actions. Therefore that paper does not have much in common with our paper. Our example in our paper's Figure 1 indicates the deliberately exploring promising states, and not exploring for the sake of exploration, a phenomenon we explored further in Section 3.2. **However, we will include these comparisons in the camera-ready version of our paper**.\n\n****\n**Response to Weaknesses**\n\n1. Since we have added comprehensive new set of results as per the request of other reviewers, we will shorten the introduction to include the relevant new results in the main paper instead of adding them in the appendix in the camera-ready version of our paper.\n2. We agree with the reviewer, we will update such usage to prevent confusions regarding to usage of the \"reward\" and \"value\" terms.\n\n****\n**Response to Questions**\n\n1. Figure 2 is a histogram, where Y axis is the number of correct instances. **We'll update Section 3.2 in camera-ready to prevent confusions.**\n\n****\n**Conclusion**\n\nWe will also fix the typos mentioned in the camera-ready version. **We thank you in advance for checking our rebuttal and reconsidering your score if you believe our explanations and the introduction of new results alleviated your concerns**. If you have further questions, as far as we understand from the new ICML guidelines, you can only respond one more time (review → rebuttal → reviewer reply → author reply). Therefore, we kindly request you to be precise about your remaining concerns in your response. **Also, please be sure to check our responses to other reviewers where we have introduced new results with utilizing fewer training data, and applying RL without the SFT stage to show the importance of AoT-O3, even in cases where we do not have the SFT stage.**", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "There are no theoretical claims in the paper.", "experimental_designs_or_analyses": "Yes I have checked the soundness/validity of any experimental designs or analyses", "relation_to_broader_scientific_literature": "See the section below.", "essential_references_not_discussed": "- The paper shares many similarity with another branch of papers that learns to simplify reasoning steps. The authors should also mention/analyze/compare to those related works. For example, [1]. The example in Figure 1 especially look like a skipped step. \n---\n[1] Liu, Tengxiao, et al. “Can language models learn to skip steps?.” arXiv preprint arXiv:2411.01855 (2024).", "other_strengths_and_weaknesses": "Strengths:\n- The paper is very straightforward and easy to understand. \n\nWeaknesses:\n- The introduction parts seem to be a bit too long. The method section only starts from the 5th page.\n- ‘In this section, we will use V for our reward models due to them actually being value models used in RL frameworks. ’ -> this sentence looks a bit weird, you are not using V as the reward model then, you are directly modeling the value function, reward function is a separate thing. For all the parts in the paper that calls V a reward model, they look a bit confusing.", "other_comments_or_suggestions": "- Table 2 is a bit hard to read. Can you also highlight/bold the Solution Lengths?", "questions_for_authors": "- What is the y-axis in Figure 2?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TsEJunkrEZ", "reviewer": "Reviewer_6rq3", "summary": "This paper introduces AoT-O3, a framework that combines supervised fine-tuning and reinforcement learning to enhance the planning efficiency of large language models (LLMs). By using a handcrafted reward function that optimizes both solution validity and length, AoT-O3 reduces reasoning steps while maintaining or improving accuracy. The framework is evaluated on three planning benchmarks using three different-sized models, demonstrating its good performance.\n\n## update after rebuttal\nThe method proposed in this paper demonstrates strong performance across multiple benchmarks and shows good generalization to multiple LLMs. Furthermore, the writing is clear and well-structured. Based on these strengths, I believe the paper is worthy of acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper. We are encouraged that our paper is recognized as \"simple yet effective\" and to demonstrate \"promising results in achieving higher planning accuracy and shorter solution lengths\".\n\n****\n**Response to Weaknesses**\n1. We experimented in BlocksWorld and Logistics domains **without any SFT stage, and simply applying the RL stage directly** (we used the same setup as in the previous results) on models prompted with five in-context examples. We followed the training and testing settings in [1] and for ToT we again used breadth of 5. We used the recently released Gemma3 4B IT model for its good performance and relatively small size, and also that we believe it will be the relevant model to use in the remainder of 2025.\n\n|**Problem**|**Method**|**Accuracy (%)**|**Solution Length (steps)**|\n|:--|:--|--:|--:|\n|BlocksWorld|CoT|27.2|6.3|\n||ToT|56.3|45.2|\n||AoT|59.1|24.2|\n||AoT-O3|**74.7**|11.3|\n|Logistics|CoT|18.5|12.6|\n||ToT|51.5|70.8|\n||AoT|49.3|55.9|\n||AoT-O3|**71.9**|24.8|\n\n[1] https://arxiv.org/pdf/2501.13545\n\n2. Thank you for pointing this out, our preliminary experiments with that reward model was that it performed similarly. However, we will include those results in the appendix in the camera-ready version of our paper.\n\n3. We will again be sure to include qualitative results in the camera-ready version of our paper.\n\n4. We will include limitations of our method in the camera-ready version of our paper.\n\n****\n**Conclusion**\n\nWe will also fix the typos mentioned in the camera-ready version. **We thank you in advance for checking our rebuttal and reconsidering your score if you believe our explanations and the introduction of new results alleviated your concerns**. If you have further questions, as far as we understand from the new ICML guidelines, you can only respond one more time (review → rebuttal → reviewer reply → author reply). Therefore, we kindly request you to be precise about your remaining concerns in your response. **Also, please be sure to check our responses to other reviewers where we have introduced new results with utilizing fewer training data, and applying RL without the SFT stage to show the importance of AoT-O3, even in cases where we do not have the SFT stage.**", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No, there is no theoretical claim.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "A simple yet effective handcrafted reward function can help LLMs reduce reasoning steps while maintaining or improving planning accuracy.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The proposed handcrafted reward function, which balances solution validity and length efficiency, provides clear and direct feedback to the model without the need for complex learned reward models.\n2. The proposed method demonstrates promising results in achieving higher planning accuracy and shorter solution lengths.\n\nWeaknesses:\n1. The paper lacks an experimental comparison with a method that directly applies RL to the model without SFT.\n2. The paper mentions an alternative to the reward model (i.e., Equation (4)), but its effectiveness is not evaluated in the experiments. Including this evaluation would make the study more solid.\n3. The paper lacks qualitative examples for analysis and demonstration.\n4. A discussion on the limitations of the proposed method is missing.", "other_comments_or_suggestions": "On page 7, line 345, the statement \"We evaluate AoT-O3 across two challenging planning benchmarks: Game of X and N-Puzzle.\" should be revised to indicate that there are three benchmarks, including Word Ladder.", "questions_for_authors": "See the weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WQmbCWewqR", "reviewer": "Reviewer_ByNr", "summary": "This work addresses the intermediate step solution length of Chain of Thought style exploration algorithms for planning problems, using supervised fine-tuning of LLMs on Algorithm of Thoughts (AoT)-style plans and utilizing a reinforcement learning mechanism for rewarding less verbose plans and thereby reducing solution length. The experimental evaluation with three small-size LLMs (1-3B) on three different planning game domains indicates that solution lengths are reduced quite significantly, while the accuracy of solved problems is maintained or improved.\n\n## Update after Rebuttal:\nThe authors' further experiments on IPC domains such as Blocksworld and Logistics, and experiments utilizing fewer examples for SFT & RL baselines are appreciated. Although there may be differences in the newly obtained results in the accuracies and solution length steps, especially with the SFT baselines, I believe the performance of the proposed method stands up to the scaling attempts, and conclusions should primarily hold without much perturbation. Other questions have been answered, and clarity/ wording recommendations have been accepted. Thus, my score has been increased from a Reject to a Weak Accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their extremely detailed review. We have acted upon their suggestions to add new experimental results and provide clarifications.\n\n****\n**Response to Claims and Evidence**\n1. In Table 2, we see that AoT-SFT is performing much better than CoT-SFT, indicating better exploration. Furthermore, we chose the word \"systematically\" to highlight the deliberate search in the output of the LLMs, in opposed to within-layer exploration that happens with CoT. However, we will change that sentence accordingly to reviewer's suggestions to prevent any misunderstandings for future readers.\n\n2. The RL stage is first incentivizing correct solutions, and provides a conciseness reward only if the solution is correct, therefore can be considered a \"weak\" reward signal in RL terminology. We agree with the reviewer, and will update this part. However, we want to also add that this way of providing reward to the LLMs is much more realistic, since we are not assuming any heuristic knowledge to give much more fine-grained feedback.\n\n3. In Table 2, CoT-SFT has performed worst in Word-Ladder. Furthermore, LLMs can sometimes have difficulties with identification of individual letters in words due to tokenizers. We will update the paper to include these discussions.\n\n****\n**Response to scalability concerns**\n\nOriginally, we opted to use a high number of training examples to show the improvements we were getting with AoT-O3 was due to SFT models being under-trained. However, this has raised concerns from the reviewers, therefore **we decided to repeat the experiments with reduced number of SFT and RL examples**. For all three tasks (Game of X, N-Puzzle, Word-Ladder), we used 320 examples to supervise-finetune models (batch size = 64, epochs = 10, training steps = 50, lr=2e-4). For AoT-SFT model, we generated new random augmentations at each epoch for the same 320 examples. For RL, we used 160 examples (batch size = 32, epochs = 10, lr = 2e-5). For ToT, we have used breadth of 5. We have evaluated on **1000 test examples**.\n\n|**Problem**|**Method**|**Accuracy (%)**|||**Solution Length (steps)**|||\n|:--|:--|--:|--:|--:|--:|--:|--:|\n|||Gemma2-2B|Llama3-1B|Llama3-3B|Gemma2-2B|Llama3-1B|Llama3-3B|\n|Game of X|ToT|26.4|20.4|27.1|18.2|17.5|18.3|\n||CoT-SFT|30.9|22.3|30.7|4|4|4|\n||AoT-SFT|58.7|53.1|62.9|33.2|30.8|36.9|\n||AoT-O3|76.6|71.2|79.4|17.9|9.7|11.5|\n|N-Puzzle|ToT|29|30|33|80.0|84.9|63.9|\n||CoT-SFT|32.3|33.7|40.3|7.6|7.7|9.2|\n||AoT-SFT|62.1|58.7|66.3|26.7|26.6|32.7|\n||AoT-O3|72.2|66.1|75.7|17.4|16.7|14.1|\n|W-Ladder|ToT|12.5|9.2|17.8|38.5|36.0|32.0|\n||CoT-SFT|10.8|5.0|13.4|10.1|6.8|9.4|\n||AoT-SFT|58.4|48.8|62.1|29.5|28.5|34.1|\n||AoT-O3|62.3|52.6|67.3|18.7|13.2|16.2|\n\n****\n**Response to weak reward signal concerns**\n\nIn order to alleviate concern's for the reward signal, **we experimented in the reviewer's suggestion domains (BlocksWorld and Logistics) without any SFT stage, and simply applying the RL stage (we used the same setup as in the previous results) on models prompted with five in-context examples**. We followed the training and testing settings in [1] and for ToT we again used breadth of 5. We used the recently released Gemma3 4B IT model for its good performance and relatively small size, and also that we believe it will be the relevant model to use in the remainder of 2025.\n\n|**Problem**|**Method**|**Accuracy (%)**|**Solution Length (steps)**|\n|:--|:--|--:|--:|\n|BlocksWorld|CoT|27.2|6.3|\n||ToT|56.3|45.2|\n||AoT|59.1|24.2|\n||AoT-O3|**74.7**|11.3|\n|Logistics|CoT|18.5|12.6|\n||ToT|51.5|70.8|\n||AoT|49.3|55.9|\n||AoT-O3|**71.9**|24.8|\n\n[1] https://arxiv.org/pdf/2501.13545\n****\n**Response to Questions**\n1. Thank you for asking this clarification. For N-Puzzle, after shuffling randomly, we selected examples with almost uniform Manhattan Distances (MD) ranging from 15 to 30 (in the original 100 test examples, 10 examples for MD=15, and 6 examples each for MD=16,..,30). We also followed the same logic for Word-Ladder, this time solution path length range from 4 to 10 steps.\n\n2. We have included ToT without finetuning. However, it's not completely correct that ToT has systematic exploration, since each path is disjointed as they appear in the context, and this can lead to visiting the same states at separate time steps.\n\n3. Figure 2 is a histogram, where Y axis is the number of correct instances. **We'll update Section 3.2 in camera-ready to prevent confusions.**\n\n****\n**Conclusion**\n\nWe thank you in advance for checking our rebuttal and reconsidering your score if you believe our explanations and the introduction of new results alleviated your concerns. If you have further questions, as far as we understand from the new ICML guidelines, you can only respond one more time (review → rebuttal → reviewer reply → author reply). Therefore, we kindly request you to be precise about your remaining concerns in your response.", "claims_and_evidence": "1) The claim that SFT on AOT-style plans makes the LLM learn to **systematically** explore the state space is an oversell, if not completely wrong. There is no reliable evidence that SFT does anything to help systematic exploration of the state space. It is well known that SFT improves the token-level inference and approximate retrieval ability for similar types of problems encountered during fine-tuning. So, in my understanding, all SFT does is make the exploration less random than before.\n\n2) To be clear, the proposed RL stage with step-count penalties for correct solutions to reward concise solutions with a lesser number of intermediate (thinking) steps is only providing a weak reward signal for conciseness or applying optimization pressure, as alluded to in certain parts of the paper, but not directly optimizing for it as an objective.\n\n3) The Word-Ladder domain is claimed to provide additional complexity for LLMs because actions must be derived from the LLMs'\nprior knowledge of valid English words. In my perspective, this is not true. If anything, I believe this domain is an advantage for LLMs. It's not clear why this domain would be more complex for LLMs compared to standard planning domains.", "methods_and_evaluation_criteria": "1) The training set and test sets have a disproportionate number of samples, which opens the possibility for a biased evaluation as the test set may not be fully representative of the data distribution. It is unclear what is the distribution of complexity of problems in the test set.\n\n2) The domains, Game of X and Word Ladder are relatively less sophisticated planning domains compared to standard planning domains such as Blocksworld, Grid, Logistics, etc. It is unclear if this method can be evaluated on such domains as the number of training examples and AOT style plan creation needed for the SFT stage are quite high and effort-intensive.  However, I appreciate the work for using the N-Puzzle domain which is known to be quite complex in planning, as the problems can contain negative interactions between subgoals.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "1) Section 3.2 is largely unclear. I do not understand what is the core motivation and attempt of that experiment. The graph in Figure 2 is also unclear.", "relation_to_broader_scientific_literature": "1) This work tries to address the high solution length problem seen in the Algorithm of Thoughts work. The work's direction could be useful for creating better LLM-based plan generators as it improves the solution length and accuracy metrics for basic planning problems. \n2) The work's direction could also be useful in informing the community involved in post-training techniques for Reasoning Language Models (RLMs) such as O1 and DeepSeek to obtain data with shorter solution lengths to perform post-training LLMs.", "essential_references_not_discussed": "1) References in Section 1 for the LLM-Modulo framework are incorrectly specified.", "other_strengths_and_weaknesses": "## Other Strengths:\n1) The paper is largely clear.\n\n\n## Other Weaknesses: \n1) In my understanding, the method is not scalable. In my view, with SFT technique being heavily involved in the proposed method, there is an inherent difficulty in including standard planning domains such as Blocksworld, Grid, Logistics, and others used in the International Planning Competition, as the SFT stage with AoT style plans utilizes a large number of examples. As for the standard planning domains, it could be harder to create sufficient examples for SFT, only to then have the RL stage weakly influence the LLM to generate shorter solution steps. Thus, the proposed method is not scalable to real-world domains in my opinion.\n\n2) As the RL stage reward formulation only applies optimization pressure by providing a weak reward signal for conciseness, there is no guarantee that there will not be significant backtracking even if the solution length is relatively lesser than CoT plans, since there is no way to keep track of open and closed lists like in standard search algorithms such as A* search. Hence, the optimization pressure could increase action hallucinations and other types of errors from the LLM.", "other_comments_or_suggestions": "Typos:\n1) section 4.2, Line 4.\n\nSuggestions:\n1) Section 3.2 needs to be re-written or made clear. Figure 2 needs to be explained more thoroughly.\n2) Section 4.1 thinking component output examples need to be made more clear, including explaining all the relevant symbols.", "questions_for_authors": "1) I request the authors to indicate the complexity distribution in the test set for each of the domains. For example, in N-Puzzle, in the 100 examples of the test set, what is the distribution of the edit distance that is claimed to be ranging from 15 to 30? I assume the Manhattan distance mentioned is equivalent to the planning edit distance. Similarly, for Word Ladder, what is the soln path length range distribution in the test set?\n\n2) Why is the standard Tree-of-Thoughts baseline without Finetuning not included? In my understanding, ToT may have a more systematic exploration of the state space with possibly lesser solution length.\n\n3) Section 3.2, Figure 2, what does the Y-axis represent? Why does AoT-medium hit 4 and the other 2 settings only hit 3?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes AoT-O3, a RL based approach that reduces solution length in LLM based planning while preserving improving accuracy. It builds on already popular Algorithm of Thoughts by adding a reward function. Experiments on 3 benchmarks show a reduction in reasoning steps and higher success rates compared to existing baselines.
Decision: Accept (poster)