You Don't Need to Rank All States. Just Rank the Actions in Front of You.

How a simple shift in learning objective—from global value functions to local action ranking—yields planning policies that generalize 8x beyond training size. A deep dive into GABAR, our NeurIPS 2025 paper.

The Setup: Planning is Hard, and It Gets Harder Fast

Take the warehouse that has run through this whole series: a robot shuttling packages between zones. With 4 zones and 1 package, a classical planner finds the delivery plan in milliseconds. Scale to dozens of zones and packages — Part 1's animated counter — and the same planner might run for hours, or never finish at all.

This is the fundamental scaling challenge in classical AI planning. The state space grows exponentially with the number of objects, and plan existence is PSPACE-complete. Traditional planners use heuristic search, which works brilliantly on small problems but chokes on large ones.

The natural question: can we learn planning strategies from small, solvable problems and apply them to large, unsolvable ones?

This is exactly what our paper Graph Neural Network Based Action Ranking for Planning addresses. We present GABAR—a system that trains on problems with 6-10 objects and successfully solves problems with 100+ objects, achieving 89% success rate on instances 8x larger than anything it saw during training.

Where GABAR sits in the literature. The two surveys earlier in the series — Part 2 (What to Learn) and Part 3 (Graph Representations) — set up the design space. GABAR is one specific cell: action-ranking objective + grounded-predicate-with-explicit-action-schema-node representation + sequential conditional decoding. Each of the three choices is a response to a specific limitation in prior work. The sections below walk through the technical details of that cell.

The Core Insight: Stop Trying to Learn the Hardest Thing

Most learning-based planning approaches try to learn a value function V(s)—an estimate of how far state s is from the goal. The idea is simple: if you know V(s) for every state, you can greedily pick the action that leads to the state with the lowest value.

The problem? This requires global consistency. Your value function must correctly rank every reachable state relative to every other reachable state. As the problem grows, the number of states explodes exponentially. Learning a globally consistent function over this space is itself an extremely hard problem—and in domains where optimal planning is NP-hard, there's no reason to believe such a function generalizes to larger instances.

Here's our key realization:

You don't need to rank all states. You only need to rank the actions available right now.

At any given state in a typical planning problem, you might have 5-50 applicable actions. Ranking these is a local problem. You don't need to know anything about states three steps ahead. You just need to identify which of the currently available actions is most promising.

This is a fundamentally simpler learning target:

• Value function learning: Learn a function consistent across millions of states
• Action ranking: Learn to pick the best among a handful of local options

The difference matters enormously for generalization. Local patterns—"if a block is clear and needs to be somewhere else, pick it up"—tend to transfer across problem sizes. Global value relationships—"this specific state is exactly 17 steps from the goal"—do not.

What it looks like in action

Concretely: at every state, GABAR looks at the situation, scores all the applicable actions, and takes the top one. No search tree. No lookahead. The same model weights process the state regardless of how many zones or packages there are. Click through the warehouse example below to see one episode end-to-end.

How GABAR Works: Three Ideas Working Together

GABAR combines three architectural choices that each address a specific challenge. Let me walk through each one.

1. Action-Centric Graph Representation

Most GNN-based planners represent a state as a graph of objects connected by predicates. If block A is on block B, there's an edge between them labeled "on."

We add something new: action nodes. Every applicable action in the current state gets its own node in the graph, connected to the objects it involves.

Why does this matter? Consider the action unstack(A, B)—pick up block A from block B. In our graph, this action has explicit edges to both A and B, with edge features encoding:

• Which parameter position each object fills (A is param 1, B is param 2)
• Which predicates each object satisfies in this action's context

This gives the GNN direct access to structured action information during message passing. The network doesn't have to infer action applicability from predicate patterns—it's explicitly represented.

How GABAR converts a planning state to a graph. Object nodes (yellow), predicate nodes (red for current state, green for goals), and action nodes (blue) form a connected graph structure.

2. GNN Encoder with Global Context

Our GNN processes the graph through 9 rounds of message passing. Each round updates edges, then nodes, then a global summary vector.

The message passing equations (in order):

The global node g is crucial. As problems scale up, graphs get larger, but the number of GNN rounds stays fixed at 9. Without a global node, information from distant parts of the graph would never reach each other. The global node acts as a communication shortcut—every node reads from it and writes to it at every round, providing global context regardless of graph size.

3. Conditional GRU Decoder

Here's a subtlety that matters more than you'd expect. Consider the action transport(pkg3, zoneO, zoneD) from the warehouse — the same example Part 3's decoding figure walks through. Selecting pkg3 constrains which source zones make sense (the source has to be wherever pkg3 actually sits). Selecting zoneO as the source further constrains the destination. Parameters are interdependent.

Our decoder uses a GRU (Gated Recurrent Unit) that builds actions sequentially:

1. Initialize hidden state from the global graph embedding
2. Score all action schemas, select one (e.g., "transport")
3. Update hidden state with selected action's embedding
4. Score all objects for parameter 1, select one (e.g., "pkg3")
5. Update hidden state with selected object's embedding
6. Score all objects for parameter 2, select one (e.g., "zoneO")
7. Continue until all parameters are filled

Each selection is conditioned on all previous selections through the GRU's hidden state. We use beam search (width 2) to maintain multiple candidates in parallel, avoiding overly greedy local decisions.

GABAR's full pipeline: (a) PDDL problem converted to action-centric graph, (b) GNN encoder runs L rounds of message passing, (c) GRU decoder sequentially selects action schema and parameters.

Dissecting Each Component: The Ablation Story

Strong results are nice, but understanding why they work is what makes research useful to others. We ran four ablation experiments, each removing one component of GABAR while keeping everything else intact. The results reveal a clear hierarchy of importance.

Ablation 1: GABAR-ACT (Remove Action Nodes)

We strip out all action nodes and action-object edges from the graph, leaving only object and predicate nodes. The network must now infer action quality purely from state features.

Result: Coverage drops from 89.2% to 7.4% on hard problems.

This is the most dramatic drop across all ablations. Without explicit action representation, the network essentially cannot learn to rank actions at all on larger problems. The few problems it solves are likely trivial instances where random action selection might succeed. This confirms that explicitly representing what you're deciding about isn't just helpful—it's essential.

The pattern across difficulties tells the full story:

• Easy: 95.5% → 33.5% (a 62-point drop)
• Medium: 92.2% → 18.4% (a 74-point drop)
• Hard: 89.2% → 7.4% (an 82-point drop)

The gap widens as problems get harder, meaning action nodes become more important, not less, as complexity increases.

Ablation 2: GABAR-RANK (Replace Ranking with Value Learning)

This ablation keeps our entire graph representation (including action nodes) and our GRU decoder, but replaces the action ranking objective with a value function learning objective. Instead of learning "which action is best here?", the model now learns "how far is this state from the goal?"

Result: Coverage drops from 89.2% to 12.1% on hard problems.

This is the second-largest drop and arguably the most informative ablation. Same architecture, same graph, same training data—only the learning objective changes. And performance collapses.

• Easy: 95.5% → 40.2%
• Medium: 92.2% → 27.8%
• Hard: 89.2% → 12.1%

Plan quality also degrades: the Plan Quality Ratio drops from 0.99 on hard problems to just 0.44 for GABAR-RANK. So even when GABAR-RANK does solve a problem, the plans are significantly worse.

This result directly validates our core thesis. The action-centric graph representation alone isn't enough—you also need the right learning objective. Value functions require global consistency that doesn't generalize; local action ranking requires only local consistency that does.

Interestingly, the GPL baseline (which also learns value functions but uses a simpler graph without action nodes) performs comparably to GABAR-RANK on hard problems (6.5% vs 12.1%). This suggests that adding action nodes to a value-function approach provides only marginal benefit—the fundamental limitation is the value learning objective itself.

Ablation 3: GABAR-CD (Remove Conditional Decoding)

Here we replace the sequential GRU decoder with independent parameter selection. Each parameter is chosen independently using only the global embedding, without conditioning on previous selections.

Result: Coverage drops from 89.2% to 60.0% on hard problems.

• Easy: 95.5% → 78.0%
• Medium: 92.2% → 72.7%
• Hard: 89.2% → 60.0%

This is a substantial but not catastrophic drop. The model can still solve many problems because the graph representation captures enough information for independent parameter selection to often work. But the 29-point gap on hard problems reveals where conditional decoding matters most: domains with complex inter-parameter dependencies.

The domain-level breakdown is revealing:

• Logistics (hard): 71% → 6%. A package being "in a city" and "in a vehicle" simultaneously requires the decoder to understand that vehicle choice constrains city choice.
• Rovers (hard): 77% → 19%. Rover capabilities, waypoint accessibility, and experiment requirements create chains of parameter dependencies.
• Blocks World (hard): 100% → 81%. Even relatively simple domains benefit from conditional decoding when problems are large.
• Visitall (hard): 88% → 83%. Grid navigation has fewer parameter dependencies, so the impact is minimal here.

The takeaway: conditional decoding becomes more critical as the relational complexity of the domain increases.

Ablation 4: GABAR-G (Remove Global Node)

We remove the global node from the GNN, forcing all information to flow through local message passing between neighboring nodes.

Result: Coverage drops from 89.2% to 42.5% on hard problems.

• Easy: 95.5% → 80.2%
• Medium: 92.2% → 69.2%
• Hard: 89.2% → 42.5%

The performance gap grows with problem difficulty, which makes sense: larger problems have larger graphs, and without the global node, 9 rounds of message passing cannot propagate information across the entire graph. The degradation is especially severe in domains requiring long-range coordination:

• Logistics (hard): 71% → 4%. Coordinating trucks and airplanes across cities requires global awareness.
• Blocks World (hard): 100% → 32%. Even stacking blocks requires knowing the full tower structure.
• Visitall (hard): 88% → 29%. Path planning across a large grid needs global spatial context.

Meanwhile, domains with more local structure are less affected:

• Gripper (hard): 100% → 77%. Pick-and-place is relatively local.
• Rovers (hard): 77% → 55%. Many rover decisions are locally determined by proximity.

The Ablation Hierarchy

Summarizing the coverage on hard problems:

1. Full GABAR: 89.2%
2. Without conditional decoding (GABAR-CD): 60.0% — a 29-point drop
3. Without global node (GABAR-G): 42.5% — a 47-point drop
4. Without action ranking (GABAR-RANK): 12.1% — a 77-point drop
5. Without action nodes (GABAR-ACT): 7.4% — an 82-point drop

The two most critical components are both about what information is available: the action-centric graph (representing actions explicitly) and the ranking objective (learning the right thing). The decoder and global node are about how that information is processed—important but secondary.

One more revealing data point: GABAR-ACT_CD (removing both action nodes AND conditional decoding) achieves only 2% coverage on hard problems and 9% on easy ones. This confirms that these components don't just add independently—they work synergistically. Action nodes provide the information; the conditional decoder exploits the structure of that information.

Results: What the Numbers Actually Mean

Generalization That Actually Works

Coverage (% of problems solved) across difficulty levels, averaged over 8 planning domains:

GABAR: Easy 95.5% | Medium 92.2% | Hard 89.2%

GPL (value function): Easy 79.1% | Medium 28.5% | Hard 6.5%

ASNets: Easy 76.0% | Medium 65.4% | Hard 48.5%

GRAPL (action ranking, no action nodes): Easy 43.5% | Medium 29.3% | Hard 22.1%

OpenAI O3: Easy 33.4% | Medium 11.6% | Hard 0.4%

Gemini 2.5 Pro: Easy 44.0% | Medium 17.1% | Hard 1.5%

The coverage drop from easy to hard for GABAR is minimal: 95.5% → 89.2%. Compare this to GPL (79% → 6.5%) or state-of-the-art LLMs (33-44% → 0.4-1.5%).

On Blocks World, Gripper, and Miconic, GABAR achieves 100% success rate at all difficulty levels—solving 40-block, 100-ball, and 100-passenger problems after training on instances with fewer than 10 objects.

Plan Quality, Not Just Coverage

GABAR doesn't just solve more problems—it solves them well. The Plan Quality Ratio (plan length from Fast Downward divided by plan length from GABAR) stays at approximately 1.0 across all difficulties:

• Easy: PQR = 1.04 (GABAR plans are slightly shorter than Fast Downward's)
• Medium: PQR = 1.01
• Hard: PQR = 0.99

This means GABAR's plans are comparable in length to those from a state-of-the-art satisficing planner. On several domains, GABAR actually produces shorter plans than Fast Downward's LAMA configuration.

The LLM Comparison

We tested OpenAI's O3 and Gemini 2.5 Pro using one-shot prompting. Both essentially collapse on hard problems (0.4% and 1.5% coverage). This isn't surprising—LLMs lack the structural inductive bias needed for systematic relational reasoning over large state spaces. They can pattern-match small planning problems from training data but cannot compose solutions for novel large instances.

The gap is most striking on hard problems: GABAR solves 89% while the best LLM solves 1.5%. This isn't a matter of prompt engineering—it reflects a fundamental architectural mismatch between sequence models and relational reasoning tasks.

The Deeper Lessons: Invariants for Other Research

Beyond the specific results, GABAR demonstrates several principles that apply broadly.

1. Local Objectives Can Beat Global Ones

The most powerful lesson: you often don't need to learn the globally optimal function. If your downstream task only requires local decisions, formulate your learning objective locally.

This applies far beyond planning:

• Recommendation systems: Rank the items on this page, don't learn absolute item values
• Dialogue systems: Rank the next response candidates, don't model the entire conversation value
• Compiler optimization: Rank the transformations applicable now, don't estimate total program quality

The mathematical intuition: a local ranking function needs to be consistent only within each decision point's option set. A global value function needs consistency across all possible inputs. The former is a strictly easier learning problem.

2. Represent What You're Deciding About

GABAR's largest performance gain comes from explicitly representing actions in the input. This seems obvious in retrospect: if you want to rank actions, give the network direct access to action structure.

More generally: your input representation should explicitly encode the entities you're making decisions about. If you're selecting among candidate programs, represent program structure. If you're choosing among robot trajectories, represent trajectory features. Don't make the network reconstruct this information from indirect signals.

3. Structure Your Decoder to Match Your Output Structure

Actions have structure—a schema and ordered parameters with dependencies. Our GRU decoder respects this structure by building actions sequentially, conditioning each choice on previous ones.

The principle: if your output has compositional structure, decode it compositionally. This is why autoregressive language models work for text, why graph-to-sequence models work for molecules, and why our conditional decoder works for planning actions.

4. Global Context Nodes Enable Fixed-Depth Architectures to Scale

The global node is a simple idea with outsized impact. It lets a fixed-depth GNN (9 layers) process arbitrarily large graphs by providing a "shortcut" for information flow.

This pattern appears in many architectures:

• [CLS] tokens in transformers
• Global pooling in graph networks
• Memory cells in neural Turing machines

If your architecture has fixed depth but variable-size inputs, consider adding an explicit global aggregation mechanism.

5. Train on Easy, Deploy on Hard

GABAR is trained exclusively on problems that are trivial for classical planners (solved in milliseconds). The training data is essentially free—no human labeling, no expensive computation, just run a planner on small instances.

This "easy instances as training signal" paradigm works when:

• The underlying patterns are compositional (small-scale structure composes into large-scale behavior)
• Your architecture has appropriate inductive biases (GNNs handle variable-size relational inputs)
• Your learning objective doesn't fight scaling (local ranking vs. global values)

What This Means Going Forward

For the Planning Community

GABAR shows that learned policies can be practical for large planning problems. The 89% success rate on hard instances—combined with plan quality matching classical planners—suggests that learned policies are ready to be taken seriously as planning tools, not just research curiosities.

The approach also complements classical planners rather than replacing them: GABAR uses planners to generate training data, then handles the problems those planners can't solve in reasonable time.

For the ML Community

The action ranking vs. value learning comparison (GABAR vs. GABAR-RANK) is a concrete case study in how reformulating the learning objective—without changing the training data or model capacity—can dramatically improve generalization. Same architecture, same graph representation, same training data: 89% vs 12% on hard problems. This is a reminder that the choice of what to learn matters as much as how to learn it.

For Anyone Building Systems That Generalize

The combination of structural representation + local objectives + compositional decoding is a recipe that extends beyond planning. Any domain where:

• Inputs are relational and variable-sized
• Decisions are local (choosing among current options)
• Outputs have compositional structure

...is a candidate for this approach. Molecular design, program synthesis, robotic task planning, network optimization—the pattern applies widely.

Technical Details (For Those Who Want Them)

• Training: Adam optimizer, lr = 0.0005, batch size 16, hidden dim 64
• Architecture: 9 GNN rounds, beam width 2, attention-based aggregation
• Data: ~3,000-7,000 training examples per domain, generated by solving random small PDDL instances
• Training time: 1-2 hours per domain on a single RTX 3080
• Evaluation: 8 standard planning benchmarks (Blocks, Gripper, Miconic, Spanner, Logistics, Rovers, Visitall, Grid)
• Cycle avoidance: Maintains visited state history; falls back to next-ranked action if top choice leads to visited state
• Execution limit: 1000 steps maximum per problem

Summary

GABAR demonstrates that a simple conceptual shift—from global value functions to local action ranking—combined with the right structural inductive biases, enables learned planning policies that genuinely generalize. The system trains on toy problems and solves real ones, maintains high plan quality as it scales, and substantially outperforms both classical learning baselines and state-of-the-art LLMs.

The ablation story makes the "why" clear: action nodes provide the right information (82-point impact), the ranking objective asks the right question (77-point impact), the global node enables scaling (47-point impact), and conditional decoding captures output structure (29-point impact). Each component addresses a distinct challenge, and together they enable robust generalization.

The broader takeaway: when you're building a system that needs to generalize, ask yourself—am I trying to learn something harder than I need to? Can I reformulate my objective to be local rather than global? Can I represent my decision space explicitly rather than implicitly? Can I decode my outputs compositionally rather than monolithically?

If the answer to any of these is yes, you might be working harder than necessary.

References

This work was presented at NeurIPS 2025. Paper, code, and project page available at the project website.

Supported by the Army Research Office under grant W911NF2210251.