Large Language Models as Common-Sense Heuristics
Andrey Borro, Patricia J Riddle, Michael W Barley, Michael J Witbrock · 2025
Read Large Language Models as Common-Sense Heuristics by Andrey Borro, Patricia J Riddle, Michael W Barley, Michael J Witbrock (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18816.txt.
Introduction
Andrey Borro and co-authors use language models as a compass inside a classic search planner, in a 2025 paper. Dedicated planners beat language models at planning but ignore the rich meaning in task descriptions. Language models hold that meaning yet often emit plans that cannot run. The team's method keeps the planner in charge and asks the model only for guidance: a heuristic score and an estimate of the final solution. Hill-climbing search follows those hints.
In a simulated household world, the method beat comparable systems' success rate by twenty-two percentage points. Its plans were consistently executable, since the planner produced every action in the task's own format. No translation layer between languages was needed. The authors present the split of labor, model for intuition, search for correctness, as the reason it works.
Catalog record
| CREATOR | Andrey Borro, Patricia J Riddle, Michael W Barley, Michael J Witbrock |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18816
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Large Language Models as Common-Sense Heuristics Andrey Borro, Patricia J Riddle, Michael W Barley, Michael J Witbrock Abstract While systems designed for solving planning tasks vastly outperform Large Language Models (LLMs) in this domain, they usually discard the rich semantic information embedded within task descriptions. In contrast, LLMs possess parametrised knowledge across a wide range of topics, enabling them to leverage the natural language descriptions of planning tasks in their solutions. However, current research in this direction faces challenges in generating correct and executable plans. Furthermore, these approaches depend on the LLM to output solutions in an intermediate language, which must be translated into the representation language of the planning task. We introduce a novel planning method, which leverages the parametrised knowledge of LLMs by using their output as a heuristic for Hill-Climbing Search. This approach is further enhanced by prompting the LLM to generate a solution estimate to guide the search. Our method outperforms the task success rate of similar systems within a common household environment by 22 percentage points, with consistently executable plans. All actions are encoded in their original representation, demonstrating that strong results can be achieved without an intermediate language, thus eliminating the need for a translation step. 1 Introduction Emergent reasoning capabilities in Large Language Models (LLMs) have prompted research into their ability to solve planning tasks and generate plans in the formal languages used to encode planning domains Kambhampati et al. (2024a) ; Hao et al. (2024) ; Silver et al. (2024) . This research has demonstrated that LLMs have difficulty with solving even simple tasks and that recent progress, with the introduction of Large Reasoning Models (LRMs) OpenAI (2024) , is insufficient to deal with common planning challenges, such as solving obfuscated domains or analysing the solvability of a given task. Furthermore, initial LRM success in solving small planning tasks fails to scale past toy problems Valmeekam et al. (2024) . The trend in improvement shows that even a modest increase in planning ability comes at the price of a larger, hence, computationally and financially costlier, LLM. This raises questions about the practicality of LLM-based planning, especially when compared to traditional planning systems such as FastDownward Helmert (2011) , which vastly outperform modern LLMs on planning tasks for a fraction of cost and time. One advantage that LLMs have over traditional planning systems is the models’ ability to store vast amounts of parametrised knowledge about a wide variety of topics and interact with the semantic information in their input text. Most planning systems make no distinction between the labels key and object1 , but an LLM is likely to infer that a key could be used to unlock a door or a chest. Research in utilising LLMs for planning in everyday environments, such as a common household, takes advantage of the parametrised world-knowledge of an LLM through fine-tuning existing models Chalvatzaki et al. (2023) or through directly evaluating the pre-trained performance of LLMs on generating plans from task descriptions Huang et al. (2022) . Both methods provide the LLM with a high-level task description (e.g., ‘slice an apple’) and expect a sequence of actions in return. A common challenge for this research comes from ensuring the executability of these action sequences, which require translation from a high-level language to a low-level language used by planning systems to operate within finite, discrete action spaces. Recent studies demonstrate that increasing the amount of information provided to the LLM alongside the task description can improve both success rates and executability. Hao et al. Hao et al. (2023) achieve this by providing an explicit world model, using a natural-language description of the current state, as part of the input to an LLM solving simple block manipulation tasks. Other research proposes to rank planning actions at each step based on a combination of the LLM’s sampling probability and an affordance function; that is, a function which maps actions to a probability estimate of their executability Ahn et al. (2022) . An affordance function can be implemented by using the Q-value function from a pre-trained model. Additionally, many other implementations are possible and can even be applied at the token level Huang et al. (2023b) . Most similar to our research, ProgPrompt Singh et al. (2023) has shown improved rates of success and executability through generating and then iteratively refining solutions in a low-level programming language, increasing the accuracy of the translation step. This result challenges the need for the LLM to output its solution in a high-level language. However, it falls short of removing the translation step altogether. We propose a method to utilise the world knowledge of an LLM by tasking it with action selection for a local search algorithm which controls an agent operating within a household environment. This allows it to function as a heuristic for the search, replacing the numeric heuristics that are more conventionally used. We extend our method by proposing a secondary heuristic in the form of an initial solution estimate to aid the LLM in pursuing long-term goals while selecting actions. Our results demonstrate that our approach is capable of generating plans to perform simple tasks in a household environment, with a success rate 22 percentage points higher than that of ProgPrompt. Furthermore, our method consistently generates executable plans, even when the tasks are solved incorrectly. The performance of our system shows that intermediate languages, whether high-level or low-level, are not necessary and give no notable benefit over operating directly in the same representation language as the agent being controlled by the LLM. 2 Background Automated Planning. Automated Planning is a branch of Artificial Intelligence primarily focused on the generation of plans. Plans are sequences of actions within a given environment that can be sequentially applied to an initial state. A planning task \Pi is a 6-tuple (S,s_{i},S_{g},A,f_{a},f_{t}) consisting of: • A finite and discrete set of all states S , also known as the state space. • The initial state s_{i}\in S . • The set of goal states S_{g}\subseteq S . In our tasks, the set of goal states is defined by a set of goal conditions for each task, which outline the criteria for a state to be a goal state. • The set of actions A . • The applicability function f_{a} , which returns f_{a}(s)\subseteq A , i.e. the set of all actions applicable at state s . In our paper, the applicability function is defined by the preconditions of our action schema, discussed in Section 3.1 • The transition function f_{t} , which maps a state s and applicable action a to the resultant state s^{\prime} of applying a to s , such that s^{\prime}=f_{t}(s,a) , a\in f_{a}(s) . As above, the transition function is defined by the effects of our action schema. In practice, most planning systems Pohl (1970) ; Jiang (2021) perform graph search on a graph G=(V,\,E) , where V is the set of vertices and E is the set of edges. Vertices are states s\in S , while edges are formed from the transition function f_{t} , where \forall\,u,v\in V,\quad(u,v)\in E\iff\exists\,a\in A\colon f_{t}(u,a)=v. A solution for a given planning task is a plan a_{1}...a_{n} such that one can form a path