Means-Ends Analysis Helps LLMs Plan in Continuous-State Domains

Jiayi Li; Carl Kingsford

cs.AIOct 18, 2026

Means-Ends Analysis Helps LLMs Plan in Continuous-State Domains

Authors: Jiayi Li, Carl Kingsford

Organizations: Ray and Stephanie Lane Computational Biology Department Kenneth C. Griffin School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA

Abstract

LLM planning research has traditionally focused on discrete-state domains, where actions form a finite, enumerable set. Existing LLM planning frameworks largely assume actions are enumerable, modeling planning as a search process over candidate actions. However, in continuous-state domains, where actions form a continuum and cannot be enumerated, this assumption breaks down. We find a remedy in Newell and Simon's Means-Ends Analysis (MEA), a general problem-solving technique rooted in heuristics from human psychology. We develop Medaka, an MEA-inspired structured prompting framework that encourages recursive goal decomposition, algebraic derivation, and per-step state tracking. To evaluate native LLM planning abilities in continuous-state domains, we develop Liquidworld, a systematic testbed on liquid mixing. On Liquidworld, Medaka can improve performance across model families, suggesting that classical means-ends analysis elicits LLM-native reasoning abilities that are helpful for continuous-state planning.

Figures & tables

<state>	$::=$	<vessel_decl> (";" <vessel_decl>)*
<vessel_decl>	$::=$	NAME "(" "capacity" FLOAT "L" ")" ":" <contents>
<contents>	$::=$	"empty"
	$\mid$	FLOAT "L" LID // pure vessel
	$\mid$	FLOAT "L" "," <pct> ("," <pct>)* // mixture
<pct>	$::=$	FLOAT "%" LID
<goal>	$::=$	<goal_clause> (";" <goal_clause>)*

Figure 2: Grammar of the LiquidWorld problem specification language. NAME is a vessel identifier (e.g. V1 ), LID a liquid identifier (e.g. L2 ), and FLOAT / INT are numeric literals. The grammar is implicit in the regex-based parser; we present it here in Backus-Naur Form for clarity.

Tag	Criterion	#Probs
linear	The volumes to pour from each source into each target vessel to reach the goal can be obtained by solving a linear system.	136
nonlinear	Sources reach targets only through intermediate pools whose compositions are chosen by the plan; the pour volumes and intermediate compositions cannot be obtained from a linear system.	53
coupling	Liquids recur across sources ( $\#\textit{source--liquid pairs}-\#\textit{liquids}\geq 3$ ), so the pour volumes must be solved as one coupled system.	106
multi-goal	$\geq 5$ target vessels.	76
distractor	$\geq 2$ vessels that are neither targets nor used by the reference plan.	28
Total		189

Table 1: LiquidWorld structure. Each problem is annotated with one or more structurally defined difficulty tags.

Figure 3: Overview of Medaka . Left: the LLM recursively decomposes the goal by identifying a gap

d

between the state

s

and goal

g

and proposes an operator

o

. A plan is returned when no gap remains. Feasibility tests whether

o

is applicable in

s

: when blocked, the LLM derives a subgoal

g^{\prime}

that resolves the blocker algebraically and updates

o

, with deferred subgoals pushed onto a subgoal stack. Once applicable, an action

a_{t}=o

is committed and the state tracker emits the full successor

s^{\prime}=T(s,a_{t})

. Right: An example trace through STEP 1 of a LiquidWorld problem.

Tag	Method	Claude Sonnet 4.6	Gemini 3 Flash	GPT 5.4	GPT 4o	LLaMA 3.3 70B	Gemma4 4B	Gemma4 2B
linear	CoT	95.1	84.8	91.9	32.1	31.1	71.8	32.6
	AoT+	96.6	91.2	90.0	23.5	20.3	67.4	28.7
	MED	97.3	94.1	90.9	45.1	50.5	79.9	37.7
nonlinear	CoT	33.3	16.4	28.9	9.4	15.1	14.5	10.1
	AoT+	55.3	21.4	49.1	10.1	10.7	15.1	11.3
	MED	87.4	50.9	46.5	15.7	15.1	12.6	11.9

Table 2: pass@1 (%) on LiquidWorld grouped by difficulty tag, computed as the mean pass rate over all rollouts on problems with that tag,

3

rollouts per problem. A problem may carry one or more tags (Table 1 ). Shaded rows mark Medaka (“MED”) and the performance of the best method per model is marked in bold. Appendix A.2 reports pass@3 (%).

Figure 4: pass@1 vs. mean output tokens on LiquidWorld . Mean output tokens per trial (log-scale

x

) vs. Pass@1 (

y

). Markers denote methods, colors represent models, and thin lines connect methods of the same model. Medaka is abbreviated “MED”.

	Claude-Sonnet-4.6		Gemini-3-Flash
Medaka	$94.5$		$82.0$
$-$ State Tracking	$90.5$	( $-$ 4.0)	$76.0$	( $-$ 6.0)
$-$ Recursive Module	$91.0$	( $-$ 3.5)	$75.1$	( $-$ 6.9)

Table 3: Ablation of Medaka on Claude-Sonnet-4.6 and Gemini-3-Flash , 3 trials per problem. “

-

Recursive Module” drops the recursive goal decomposition module; “

-

State Tracking” drops the per-step state tracking module, which includes all numeric computation instructions. Each cell reports pass@1 (%) on the full LiquidWorld with the absolute drop (in percentage points) relative to full Medaka in parentheses. See Table 5 in Appendix A.3 for per-tag ablation results.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Tag	Method	Claude Sonnet 4.6	Gemini 3 Flash	GPT 5.4	GPT 4o	LLaMA 3.3 70B	Gemma4 4B	Gemma4 2B
linear	CoT	95.6	86.0	94.9	41.9	39.0	79.4	42.6
	AoT+	97.8	91.2	94.9	29.4	27.9	77.2	39.0
	MED	98.5	94.1	94.9	62.5	68.4	87.5	54.4
nonlinear	CoT	64.2	18.9	49.1	11.3	15.1	17.0	11.3
	AoT+	88.7	22.6	73.6	11.3	15.1	15.1	13.2
	MED	96.2	58.5	75.5	17.0	15.1	13.2	13.2

Appendix

Table 4: Pass@3 (%) on LiquidWorld by difficulty tag. Shaded rows mark Medaka (“Med”).

	Claude-Sonnet-4.6			Gemini-3-Flash
Tag	Medaka	$-$ State	$-$ Recursive	Medaka	$-$ State	$-$ Recursive
linear	97.3	93.6	94.1	94.1	91.4	93.1
nonlinear	87.4	82.4	83.0	50.9	36.5	28.9
coupling	90.3	88.4	89.3	68.9	58.2	56.0
multi-goal	89.5	86.0	87.7	60.5	46.9	43.4
distractor	94.0	90.5	92.9	77.4	69.0	67.9

Appendix

Table 5: per-tag ablation results of Medaka ( pass@1 , %, 3 trials per problem). Columns as in Table 3 .

Failure mode 1: Trial-and-error repair after volume saturation

Example Initial state:

V_{1}

10

L_{2}

;

V_{2}

10

(40\%L_{1},60\%L_{3})

;

V_{3}

10

L_{3}

;

V_{4}

: empty.

Goal:

V_{4}=2

(13.43\%L_{1},30.52\%L_{2},56.05\%L_{3})

pour 1.0L V2 -> V4

\Rightarrow

V_{4}:1

(40,0,60)\%

pour 0.5L V1 -> V4

\Rightarrow

V_{4}:1.5

(26.7,33.3,40)\%

pour 0.5L V3 -> V4

\Rightarrow

V_{4}:2

(20,25,55)\%

volume reached, composition wrong

pour 0.1L V2 -> V4

\Rightarrow

V_{4}:2.1

(21.0,23.8,55.2)\%

repair after saturation

Appendix

Table 6: Representative failed traces illustrating three qualitative failure modes.

Model	Method	Input	Output	Total
Claude-4.6	CoT	962 (876–1425)	1231 (1019–1392)	2185 (1898–2931)
	AoT+	1463 (1357–1873)	1726 (1342–15891)	3134 (2734–17580)
	MED	2381 (2269–2831)	4498 (2432–17725)	6857 (4679–20482)
Gemini3-Flash	CoT	931 (839–1448)	1028 (892–1393)	1989 (1731–2855)
	AoT+	1308 (1181–1874)	1225 (1032–1776)	2543 (2250–3746)
	MED	2206 (2079–2764)	1888 (1555–2954)	4053 (3665–5685)

Appendix

Table 7: Per-trial token usage on LiquidWorld . Each cell reports the median (and Q1–Q3 interquartile range) across all problems and trials.

LLM Planning

Large language model planning studies how models decompose goals, choose actions, and revise plans under constraints.

See all 142 papers

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs
Oct 6, 2026André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi +1Automated Heuristic Design LLM Planning
Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom +1
Latent Chain-of-Thought as Planning: Decoupling Reasoning from Verbalization
Jan 29, 2026Jiecong Wang, Hao Peng, Zhanyi Wang +2LLM Planning Efficient Language Model Reasoning
Beihang University · Didi Chuxing
What We Talk About When We Talk About LLM Planning: Evidence for Two Distinct Planning Abilities
Jul 13, 2026Sukai Huang, Chenyuan Zhang, Fucai Ke +4LLM Evaluation LLM Planning
Faculty of Information Technology, Monash University

Oct 6, 2026J/K move · Enter open · S save

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

André G. Pereira, Augusto B. Corrêa, Felipe Meneguzzi, Jendrik Seipp

Federal University of Rio Grande do Sul Brazil · University of Oxford United Kingdom · University of Aberdeen United Kingdom+1

Automated Heuristic Design LLM Planning Sequential Decision Making Symbolic Planning Formal Verification

Open paper AskPDF arXiv

Frontier large language models (LLMs) can generate heuristic functions that guide search to achieve state-of-the-art performance in satisficing planning, where any plan is acceptable. However, these heuristics are not guaranteed to be admissible and can lead to suboptimal plans. We introduce LeanPlan, the first planning system that finds optimal plans with LLM-generated heuristics whose admissibility is machine-checked. Given a domain description and training tasks, an agentic loop uses planner feedback to iteratively improve a reusable domain-specific heuristic, its admissibility proof and the required domain assumptions. LeanPlan implements the heuristic, its proof and an efficient planner with machine-checked grounding and search in Lean 4. We evaluate LeanPlan on ten domains from the International Planning Competition and three new domains, using test tasks with up to 57 times as many objects as the training tasks. With GPT-5.6 Sol in the agentic loop, we successfully generate heuristics and admissibility proofs for all these domains. With the resulting heuristics, LeanPlan usually expands fewer states than the state-of-the-art Scorpion planner and solves more tasks overall.

Abstract

LLM Planning

Explore similar work

LeanPlan: Optimal Planning with LLM-Generated Heuristics and Admissibility Proofs

Latent Chain-of-Thought as Planning: Decoupling Reasoning from Verbalization

What We Talk About When We Talk About LLM Planning: Evidence for Two Distinct Planning Abilities