LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks — part 2/3

Cleaned-text code points [13662, 29032). Bibliography omitted here; source.md includes it.

Claims about Planning: To analyze planning claims, we need to first understand that solving planning tasks requires (a) having the necessary planning domain knowledge–the actions and their preconditions, effects; the standard hierarchical recipes (e.g. task reduction schemas in HTN planning), past cases/plans, etc., and (b) being able to assemble this planning knowledge into an executable plan that takes care of any subgoal/resource interactions. The first part can be called knowledge acquisition and the second reasoning/planning. On closer examination, many papers claiming LLMs have planning abilities wind up confusing general planning knowledge extracted from the LLMs for executable plans. When all we are looking for are abstract plans, such as “wedding plans,” with no intention of actually executing them, it is easy to confuse them for complete executable plans. Indeed, our close examination of several works claiming planning capabilities for LLMs ( Kambhampati et al., 2023 ) suggests that they either work in domains/tasks where subgoal interactions can be safely ignored ( Yao et al., 2023b ; Shinn et al., 2023 ) 4 4 4 Although domains like AlfWorld ( Shridhar et al., 2021 ) do have sub-goal interactions for successful task completion, ( Yao et al., 2023b ) and ( Shinn et al., 2023 ) largely ignore these interactions by either focusing on single subgoals or relying on the ergodic nature of the domain when prompting LLMs for generating plans ( Verma et al., 2024a ) . –either because they are just working on a single subgoal, or because the world is forgiving and ergodic; or by delegating the interaction resolution (reasoning) to the humans in the loop (who, through repeated prompting, have to “correct” the plan). Sometimes, in common sense domains, or with enough fine-tuning, the “assembling” part may also be obviated by having seen a case that pretty much corresponds to the problem that needs to be solved. Not surprisingly, our work ( Valmeekam et al., 2023c ) shows that if the action interactions are removed by relaxing the world models, then the ability of LLMs to guess executable plans improves. Without these assumptions or mitigations, the plans that come out of LLMs may look reasonable to the lay user, and yet lead to execution time interactions and errors. 5 5 5 These issues are illustrated in part by a recent news story ( Kugel & Hiltner, 2023 ) about the proliferation of travel planning books, mostly auto-extracted from LLMs, and the ensuing disappointment of the unsuspecting end users who buy them mistaking them for usable plans!

Claims about Self-Verification: Coming to the claims about LLM’s self-verification abilities, a closer look at the literature ( Yao et al., 2023a ; Huang et al., 2023a ) shows that those claims are either (i) made in the context of tacit knowledge tasks for which there is little possibility of a verifier (e.g. essay writing)–making it hard to evaluate whether LLM’s critiquing actually helped or (ii) the external verification is carried out either by simulators ( Wang et al., 2023b ; Yao et al., 2023b ) or simple calls to the underlying operating system.

In a related vein, there is the recent Tree of Thoughts (ToT) paper ( Yao et al., 2023a ) , which has been pitched as a way to convert LLMs into some type of systematic search with self-verification. Specifically, ToT employs a problem-specific prompt priming method. The “tree” in ToT is essentially a way to generate diverse priming prompts (that the authors set up in a problem specific way ). In other words, despite the use of terminology of problem-solving agents ( Russell & Norvig, 2010 ) –search tree, expansion etc., there is really no deeper connection to search-based agents.

The guarantees--if any--are coming in terms of soundness of the external verifier. The one clear reasoning problem used in the ToT paper is the 24 puzzle--for which the external verifier can be easily implemented in terms of arithmetic operations (thankfully not done by the numerically challenged LLM!). Here, our experiments show that the LLM’s own criticisms are often quite off the mark. 6 6 6 Note that we can do this check easily because of the formal specification of correctness. For the “improving writing task” also used in ToT, there are no formal quality metrics and so it is hard to say anything concrete about the critiques of the LLM. Because the 24 puzzle’s solutions can be verified by simple arithmetic operations, it is trivial to implement an external verifier for these problems. In general though, the verifier may be more complex and can involve substantial work (you can substitute a simulator for the verifier–but someone has to write that simulator too!).

LLMs as Approximate Knowledge Sources: The fact that LLMs are often good at extracting planning knowledge can indeed be gainfully leveraged. As shown in recent works ( Guan et al., 2023 ) , LLMs can be a rich source of approximate models of world/domain dynamics and user preferences, as long as the humans (and any specialized critics) in the loop verify and refine those models, and give them over to model-based solvers. This way of using LLMs has the advantage that the humans need only be present when the dynamics/preference model is being teased out and refined, and the actual planning after that can be left to sounder planning frameworks with correctness guarantees, such as the LLM-Modulo framework we propose.

Such an overall approach has striking similarities to knowledge-based AI systems of yore, with LLMs effectively replacing the “knowledge engineer” (see Figure 2 ). Given the rather quixotic and dogmatic shift of AI away from approaches that accept domain knowledge from human experts that can be termed “Polanyi’s Revenge” (c.f. ( Kambhampati, 2021 ) ), this new trend of using LLMs as knowledge sources can be viewed as a form of avenging Polanyi’s revenge! Indeed, LLMs make it easy to get problem-specific knowledge as long as we are willing to relax the correctness requirements of that knowledge. In contrast to the old knowledge engineering approaches, LLMs offer this without making it look like we are inconveniencing any specific human (we are, instead, just leveraging everything humans told each other on the Web!). So the million dollar question for reasoning tasks is: “ how would you do robust planning if you have some doddering know-it-all ready to give you any kind of knowledge? ” The LLM-Modulo Framework is a principled method for tackling this challenge.

## 3 LLM-Modulo Framework for Robust Planning

While Section 2 questions the claims that LLMs are capable of planning/reasoning by themselves, it is certainly not meant to imply that LLMs don’t have any constructive roles to play in solving planning/reasoning tasks. On the contrary, as discussed in the Introduction, their uncanny ability to generate ideas/potential candidate solutions–albeit with no guarantees about those guesses–can be valuable in the generate-test-critique setups in conjunction with either model-based verifiers or expert humans in the loop. Accordingly, we propose a general ‘‘LLM-Modulo’’ framework 7 7 7 The name LLM-Modulo is inspired by the SAT-Modulo theories ( Nieuwenhuis & Oliveras, 2006 ) . . While we believe that versions of such an architecture can be of use in a wide variety of planning or reasoning tasks, for the sake of concreteness, we will focus on planning tasks, especially of the type studied in the automated planning community ( Ghallab et al., 2004 ) .

Figure 3 gives a schematic of the LLM-Modulo Framework , as we envision it. As can be seen readily, the underlying architecture is a Generate-Test-Critique loop, with the LLM generating candidate plans and a bank of critics critiquing the candidate. The loop starts with the LLM getting the problem specification and generating its first plan candidate. 8 8 8 Although we focus on planning from scratch, it is easy to accommodate replanning scenarios, where the loop starts with an externally supplied candidate plan. Note that the plans an LLM helps generate in this architecture have soundness guarantees because of the external sound critics. This means that plans coming out of such an compound system will constitute a better corpus of synthetic data for any fine tuning phase carried out to improve/customize the LLM’s generation capability. The completeness of the system depends on the LLM’s ability to generate all potentially relevant candidates.

Design Choices: Before going into the details about the framework and its various modules, it is worth noting some design decisions underlying the proposed architecture. We start by noting that the LLM-Modulo architecture is a “Generate-Test” one that involves LLMs interacting with the external critics/verifiers rather than a LLMs being just front-ends to external solvers. This is a deliberate decision–as this allows the LLM to guess/generate candidates to satisfy the critics, as against dealing with the expressiveness and search complexity issues of the solvers. The critics/verifiers also are also more naturally composable than solvers/planners. As we shall see, we do allow for constructive critics which can be based on solvers, and provide suggestions on specific ways of extending/modifying the candidate plans.

Secondly, the framework explicitly recognizes that the LLMs can generate approximate ideas not just about plan candidates, but domain models, problem reduction strategies, and refinements to the problem specification. The framework also recognizes that LLMs are good at format/syntax changes. Accordingly, the framework leverages all these abilities of LLMs, letting them play multiple roles in planning. Finally, the architecture carefully circumscribes the human’s role–domain experts interact with the LLM to tease out the models used by (some of) the critics, while end users take part in refining any incomplete problem specification in concert with the LLM. A notable, and deliberate, absence is human’s involvement in the inner loop of planning–e.g. with iterative prompting. In addition to posing an infeasible burden on the human’s time for complex planning problems, such iterative prompting strategies are notorious for their Clever Hans effect ( cle, ) .

### 3.1 Critics/Verifers

In the LLM-Modulo framework, critics can evaluate LLM-generated candidates for a planning/reasoning problem over both hard and soft (style) constraints. Hard constraints refer to correctness verification which can include causal correctness, timeline correctness, resource constraint correctness as well as unit tests. For PDDL planning problems, the hard critic can be based on VAL ( Howey et al., 2004 ) , that works off of a model (which itself can be acquired with the help of the LLM ( Guan et al., 2023 ) . It is worth noting that the critics don’t always have to be declarative model-based ones, and can be simulators. Just as LLMs can help humans in coming up with models, they can also help in writing procedural simulators, as seems to be done in systems like Voyager ( Wang et al., 2023a ) .

On the other hand, soft constraints can include more abstract notions of good form such as style, explicability, preference conformance, etc. As discussed in Section 2.3 , while LLMs cannot take on the role of hard critics with soundness guarantees, 9 9 9 If we don’t insist on soundness guarantees, then it is, in principle, possible to train LLMs discriminatively to learn to verify plans; see ( Arora & Kambhampati, 2023 ) . they can help simulate some aspects of the role of soft (style) critics. So our framework does allow for style critics be possibly based on LLMs. For example, in ( Verma et al., 2024b ) we discuss how LLMs can act as a human proxy to evaluate plans in terms of how they would be perceived by humans in the loop. Additionally, in ( Guan et al., 2024 ) , we show how Vision-Language Models (VLMs) can be leveraged to critique the style of robot behaviors in terms of their adherence to the soft common-sense preferences of the humans in the loop. We reiterate that the soundness of the LLM-modulo framework is inherited from the soundness of the correctness (hard) critics.

The bank of critics–hard (model-based) as well as soft (possibly LLM-based) evaluate the current plan candidate to evaluate its fitness/acceptability. If at least all the hard critics sign off on the current candidate, then that is considered a valid solution to be returned to the end-user or the executor. When a critic finds the current plan candidate to be unsatisfactory, it can provide varying levels of feedback, ranging from “ No, try again ” to “ No, try again, here is one thing wrong with the current plan ” to “ No, try again, here are all the things wrong with the current plan .” More importantly, the critics can be constructive , and offer alternatives plan/subplan suggestions. One way of obtaining such constructive critics is to base them on partial planners–operating either on the models themselves or their relaxations ( Bryce & Kambhampati, 2007 ) . These critiques are all pooled at the Meta (Backprompt) Controller (see Section 3.2 )

LLMs as Reformulators: One interesting challenge is that many of the symbolic model-based verifiers tend to be operating on specialized formal representations. Given a central candidate plan (e.g. a mission plan), these critics need translations of that candidate into their representations. This is the role of the reformulator module attached to individual critics. These reformulator modules can be supported to a large extent by LLMs, given that one thing LLMs are very good at is format change across different syntactic representations ( Olmo et al., 2021 ) . Indeed, as discussed in Section 1 , some approaches to combine LLMs with external symbolic solvers just use LLMs as reformulators for these solvers ( Liu et al., 2023 ; Pan et al., 2023 ) . It is worth noting that the syntax conversion itself can be helped with a nested LLM-Modulo framework–where the syntactic correctness of the conversion is checked by syntax critics. We will have occasion to illustrate this in the context of our preliminary work on LLM-Modulo frameworks for travel planning discussed in Section 4 . Our discussion of LLM-Modulo framework should make it clear that syntax reformulation alone is a severely limited role for LLMs!

### 3.2 Backprompt (Meta) Controller

The critiques from the various critics are pooled together by the Meta (Backprompt) Controller, which passes a processed version of them to the LLM as the next iterative prompt to elicit the next guess. This is especially required in the presence of a mix of soft and hard critics, where the Meta Controller can assume the responsibility of compiling the critiques into a consistent feedback to send to the LLM.

The processing in the controller can range from (i) simple round-robin selection of prompts to (ii) generating a summarized prompt (with LLM help) to (iii) employing a prompt diversification strategy to elicit the next candidate from a different part of the implicit search space. This last strategy helps increase the completeness of the LLM candidate generation, and may involve domain/task-specific knowledge (see the discussion of Tree of Thoughts in Section 2.3 ).

### 3.3 Specification Refinement & Critic/Model Acquisition