Most benchmarks for language-model planners score a plan as all or nothing: it either reaches the goal or it scores zero. Recent work replaces this with partial credit, such as overlap with a reference plan or the fraction of hand-written subgoals reached. These partial scores have a weakness of their own. They are often computed against a single reference, so a planner that swaps two independent moves or takes a short harmless detour loses as much credit as one that makes a real mistake. Shape analysis has a well-studied version of this problem. The medial axis, a shape's skeleton traced through the centres of the largest circles that fit inside it, grows long spurious branches from tiny bumps on the boundary. That field's main fix is to thicken the reference by a tolerance radius, so that small boundary noise is absorbed while large structural changes still register.
We propose to carry that fix over to plan evaluation. The score is measured in the true state space of the planning domain rather than against a reference string. It gives full credit to any plan that stays within a tube of radius $r$ extra steps around some optimal solution. It reduces credit in proportion to the distance still remaining to the goal. It marks the single "critical step" where a plan becomes unrecoverable. The note claims, and plans to test, two things. First, this score is measurably more stable than existing partial-credit metrics under benign perturbations, while staying just as sensitive to harmful ones. Second, that stability matters in practice: used as a reinforcement-learning reward, it should improve validity on long plans outside the training distribution beyond the best existing partial-credit reward.
What the two directions contribute
The partial-credit literature supplies the motivation and the strongest competitors. AgentBoard defines a Progress Rate from human-annotated subgoals and a state-goal matching score. It shows that models with near-identical success rates (around 2–4%) separate clearly on progress: Mistral-7b reaches 24.6% and Llama2-13b reaches 18.9%. Its authors name manual subgoal annotation as the main bottleneck. Chasing Progress, Not Perfection introduces plan executability and a reward based on the Longest Contiguous Common Subsequence (LCCS) with a reference plan. With that reward, RL fine-tuning of Qwen2-7B raises validity on long out-of-distribution plans by 7% and executability by 9%. The same paper also finds that permutation augmentation alone lifts executability on unseen domains from 20.1% to 75.5%. We read that result as direct evidence that serialization order is a nuisance variable which a reference-string reward wrongly penalizes. PlanBench and LLMs Still Can't Plan; Can LRMs? supply the test domains and show how sharply binary accuracy falls on longer instances: o1-preview drops from 97.8% on standard Blocksworld to 23.6% on 20–40-step instances. Don't Pass@k shows that rankings built from binary pass rates are unstable under small sample budgets, and we reuse that framing for rank stability.
The boundary-noise literature supplies the method, not just a metaphor. Coverage Axis dilates inner balls by a fixed amount before choosing a skeleton by set cover, and the dilation is what stops spurious spikes from surface noise. Skeleton Recall Loss computes the reference skeleton offline and dilates it into a "tube", giving predictions slack near the true centreline at about 8% added training time, compared with about 88% for clDice. Our tube radius $r$ plays the same role over plan length. Enhancing Boundary Segmentation separates boundary errors that change topology ("critical pixels") from neutral ones and weights only the former. Our critical-step marker is the sequential version of that idea.
Two constraints come from the same literature. Manzanera's result is that a digital skeleton cannot be both exactly centred and robust to noise. Its analogue here is that no score can be maximally sensitive to every deviation and also robust to benign ones, so we report a trade-off curve over $r$ rather than claiming a free lunch. The Impact Label Noise and Choice of Threshold warns that apparent fragility can come from a badly chosen cut-off rather than from the underlying signal. That is why we also test whether simply thresholding an existing score differently gets most of the benefit.
Core Claim
Partial credit for plans should be measured as reduction in true distance-to-goal, with a tolerance tube over plan length. Executing a generated plan from initial state $s_0$ until its first precondition violation produces states $s_0,\dots,s_m$. Let $h^*(s)$ be the optimal number of steps from $s$ to the goal, with $h^*(s)=\infty$ for dead-end states from which the goal cannot be reached. The credit is
$$C_r = \frac{h^*(s_0) - h^*(s_m)}{\max\big(h^*(s_0),\; m - r\big)},$$
with the numerator set to zero when $s_m$ is a dead end.
An optimal plan scores 1. Any plan that reaches the goal with at most $r$ wasted steps also scores 1, whatever its action order. A plan that stops partway scores the fraction of distance it actually covered. Wandering beyond the tube is charged in the denominator.
Separately, we report the critical step. This is the first step at which $h^*$ becomes infinite, a precondition fails, or the steps taken minus the distance gained first exceeds $r$. This is the plan-level counterpart of a topological critical pixel. Both quantities come from a planner and a simulator, so no subgoal annotation and no language-model judge is needed.
Research Program
We will compute $h^*$ with an optimal classical planner on PlanBench Blocksworld and Logistics, on the extended eight-domain suite of Chasing Progress, and on the PDDL tasks in AgentBoard via its released code (hkust-nlp/AgentBoard). Optimal planning gets expensive on 20–40-step Blocksworld instances. Where $h^*$ cannot be computed within budget, we bound it with an admissible heuristic and report results separately on those instances.
Blocksworld and Logistics are essentially reversible, so their dead-end branch is never exercised. We will therefore also include domains with irreversible actions from the available suites. If too few exist, we will build irreversible variants of Blocksworld, for example blocks that cannot be unstacked once placed, so that the critical-step marker can be tested where it matters.
The work has three parts. The first is a controlled perturbation suite. We take valid plans and apply benign edits: commuting independent actions, substituting a different optimal plan, and inserting reversible detours of length up to $k$. We also apply harmful edits: dropping a required action, inserting an irreversible wrong action, and swapping an argument. These edits measure each metric's "spur sensitivity", meaning how much its score moves under benign edits relative to harmful ones. The second part is a ranking study across models and sampling budgets. The third is an RL study that swaps the reward in the Chasing Progress setup.
Baselines
The naive reference point is binary plan validity as computed in PlanBench. For orientation, GPT-4 has a reported plan generation accuracy of 34.3% there, and fine-tuned Qwen2-7B has a reported Blocksworld validity of 98.5% in-distribution falling to 13.5% on long plans (Chasing Progress). All metrics, including ours, are computed on exactly the same generated plans, so the metric comparisons involve no tuning-budget asymmetry.
The strongest existing partial-credit method is the LCCS reward together with executability from Chasing Progress. It is the strongest competitor because it is the only one in the file shown to improve training outcomes: +7% validity and +9% executability on long out-of-distribution plans under RLOO with Qwen2-7B. In the RL study we rerun their recipe ourselves with the same base model, data splits, RLOO hyperparameters, rollout count and number of updates, changing only the reward. Beating it means a statistically reliable gain in long out-of-distribution validity over our own LCCS rerun, not over their reported figure.
The second strong baseline is the AgentBoard Progress Rate. Its subgoal-matching score correlates with human judgement at Pearson above 0.95 (AgentBoard). We run it on the AgentBoard PDDL tasks using the released subgoals. Beating it means equal or higher agreement with human ratings and lower benign-edit sensitivity, achieved with no annotation.
We also include a language-model judge that assigns 0–100 partial credit to each trace, using the same model for all conditions.
Two ablations isolate the key ingredients. Setting $r=0$ removes the tube, which tests whether tolerance adds anything over pure distance accounting. Setting $r=\infty$ and dropping the length term reduces the score to final-state distance-to-goal. That is the simplest state-space alternative and the real threat to this proposal.
Why not just…?
Why not just ask a strong language model to grade partial progress? The file gives direct evidence that frontier models misjudge exactly the quantities a grader needs. GPT-4 predicts the result of executing actions correctly only 31.8% of the time in PlanBench. o1 generated full incorrect plans on 54% of unsolvable instances while claiming success (LLMs Still Can't Plan; Can LRMs?). Because we include the judge as a baseline in the perturbation suite, we will measure directly whether it rewards plausible-looking but invalid traces, rather than assuming it does.
Why not just use edit distance or LCCS against a reference plan? These metrics penalize swaps of independent actions and alternative optimal plans as if they were errors. The 20.1% to 75.5% executability jump from permutation augmentation in Chasing Progress suggests that ordering is a large nuisance factor. The perturbation suite quantifies this. If LCCS turns out nearly as stable as tube credit on benign edits, the RL comparison is still the decisive test, and we would report a null result.
Why not just sample more and report Pass@k? More samples reduce variance in a binary estimate but do not add information about how close each failure came. Don't Pass@k shows that rankings stay unstable at realistic budgets. Repeated sampling is also expensive: 100 instances cost $42.12 on o1-preview against $0.44 on Claude 3.5 Sonnet (LLMs Still Can't Plan; Can LRMs?). Our ranking study compares rank stability at a matched sample budget across binary, Pass@k and tube credit.
Why not just use final distance-to-goal, with no tube and no critical step? This is the serious alternative. It already ignores action order and needs no reference plan, and it may capture most of the benefit. It differs from tube credit in two ways. First, it cannot tell an efficient partial plan from one that wanders for many steps before stopping at the same distance. Second, it gives no step-level diagnosis of where a plan became unrecoverable, which matters in irreversible domains. The $r=\infty$ ablation settles this directly. If it matches tube credit both on harmful-edit sensitivity and as an RL reward, the honest conclusion is that state-space distance is the contribution and the tube is unnecessary, and we would write the paper that way.
Proposed Experiments
The first decisive check is the perturbation suite. For each metric we compute the mean score drop under benign edits and under harmful edits, and report their ratio as a function of $r$. That ratio curve is the empirical counterpart of Manzanera's trade-off. We expect tube credit to keep benign drops near zero up to detour length $r$ while retaining the harmful-edit drop of $r=0$. LCCS and the judge should show sizeable benign drops.
The second check is human agreement. On a sample of real model outputs from the AgentBoard PDDL tasks and PlanBench, we compare correlation with expert progress ratings, using AgentBoard's protocol. The target is to match AgentBoard's reported correlation without its annotations.
The third check is ranking stability. Using PlanBench outputs from several open models at small sample counts, we measure bootstrap rank agreement for binary validity, Pass@k, LCCS and tube credit.
The fourth and most consequential check is the RL rerun of Chasing Progress with four rewards: LCCS, final distance-to-goal, tube credit with $r=0$, and tube credit at the $r$ selected on in-distribution validation only. We evaluate validity and executability on the long, unseen and obfuscated out-of-distribution splits.
Following the warning in The Impact Label Noise and Choice of Threshold, we add one inexpensive control: a re-thresholded LCCS reward that gives full credit above a tuned overlap level. This checks that any gain comes from state-space measurement rather than from a better cut-off.
The proposal fails if tube credit does not beat both our LCCS rerun and the final-distance ablation on long out-of-distribution validity. It also fails if its critical-step marker does not locate injected irreversible errors more accurately than the first-divergence-from-reference position.
References
- AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agents
- Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generation
- PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change
- LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench
- Don’t Pass@k: A Bayesian Framework for Large Language Model Evaluation
- Coverage Axis: Inner Point Selection for 3D Shape Skeletonization
- Abstract: Skeleton Recall Loss - Connectivity Conserving and Resource Efficient Segmentation of Thin Tubular Structures
- Enhancing Boundary Segmentation for Topological Accuracy with Skeleton-based Methods
- The Impact Label Noise and Choice of Threshold has on Cross-Entropy and Soft-Dice in Image Segmentation