Can an LLM plan? Sokoban as a benchmark

The question

The Tetris write-up ended on "both, in sequence": local models misread the board first, and once thinking fixed their perception they failed at planning instead. That is a two-variable story told from one game. Sokoban isolates the second variable. A 10×10 grid, four boxes, four targets, walls; push every box onto a target. You cannot pull, you cannot push two boxes, and a box shoved into a corner is lost forever. There is no clock, no randomness, and no perception problem: the prompt lists the coordinates of the player, every box and every target in plain text. If a model fails here, it is failing to think ahead.

It also has a property Tetris lacks: a solver that is provably optimal. That gives us an exact distance-to-solution after every move, so we can see the turn on which a model turns a solvable puzzle into a dead one.

Setup

• Levels. DeepMind's Boxoban set, 10×10 with four boxes, in two tiers. Micro: the first 50 "unfiltered" levels whose optimal solution is 30 moves or fewer (actual range 11–30, we use the first 10). Medium: Boxoban's own medium set, levels 0–9, optimal 33–60 moves. Every condition plays the same levels.
• Turn structure. The model sees the ASCII board, a legend, the coordinate list, the legal single moves, and its own recent moves. It answers with a sequence of up to 20 moves. Moves execute in order until the first illegal one; then the model sees the new board and is told which move failed. Answering with a plan rather than a single step is the point: the bench measures lookahead, not reaction.
• Budgets. 20 turns per micro level (the first three coached runs had 40; no solve ever occurred after turn 18), 25 per medium level, with a 200/300-move cap. A level ends on solve, deadlock, or budget.
• Reference solver. A* over (player, boxes) states with dead-square pruning, cost = walking moves + pushes, goal test on pop. It is move-optimal, verified against every model solve in the database (none is shorter). It provides the optimal length for each level, the solver distance before and after every turn, and deadlock detection: when the distance goes to "unsolvable", the model has just killed the puzzle.
• Anchors. The solver as ceiling (100%, at optimal length) and a random legal move each turn as floor.
• Metrics. Levels solved; solves in a single turn; solves at exactly optimal length; levels deadlocked; boxes on targets when the level ended (partial credit); length ratio (moves used ÷ optimal, solved levels only); fallback turns (no parseable move after retries, a random legal move is substituted); tokens and seconds per turn.
• Conditions. Standard: rules plus the response format. Coached: adds a four-step method (list coordinates, pair boxes with targets and decide the push side, check for corners, write the letters). Thinking: the model's hidden reasoning channel, unbounded (32k tokens, 40k context) for local models.

Local models run on two RTX A6000s through Ollama; the Claude 5.5 models run through Azure AI Foundry with the identical prompt and levels. Same hardware, same clients and same model set as the Tetris bench, plus two models that arrived after it: Nvidia's Nemotron 3.5 Bolt and Qwen 3.8 Flash-Next.

Results: micro tier

Ten levels, optimal 11–30 moves. Lighter bars are the cloud models.

Full table, micro

One-shot = solved in a single answer. At optimal = solved in exactly the solver's move count. Deadlocked = the model pushed a box somewhere it could never be recovered from. Length ratio is over solved levels only. Latency is per model call, which may execute up to 20 moves.

What the micro table says

• With the standard prompt, no local model plans. 6 of the local models score 0% and deadlock 50–90% of levels, typically within three or four turns. Random play also scores 0% but leaves more boxes on targets (18%) than Gemma (12%), Qwen 3.8 (15%) or either Nemotron, because a random walk stumbles into fewer corners than a confident wrong plan. Parse failures are zero for most of these rows. The models understand the format; their plans are wrong in the geometry.
• Claude is at ceiling on micro. Sonnet, with or without thinking, and Haiku with thinking solve 10/10, most in one answer, 15–22% over optimal length, in about ten seconds a level. Haiku without thinking gets 70%. Micro does not separate frontier models; that is what the medium tier is for.
• Thinking unlocks the local models, and not by a little. Qwen 3.8 27B goes from 0% (standard) to 50% (coached) to 90% with an unbounded thinking channel, 5 of them one-shot and 6 at exactly optimal length. Nemotron Bolt goes 0% → 0% → 90%, 7 one-shot. Same weights, same prompt, same levels; the difference is whether the model is allowed to reason before the first move letter. The cost is real: Qwen takes 26 minutes per turn and 8 hours for ten levels at a 32k cap; Bolt, which generates at 129 tokens a second, does the same ten in under half an hour. gpt-oss with an unbounded channel is the other fast one: 70%, 5 one-shot, 1.3 hours, no truncation.
• Coaching helps less than thinking and costs almost as much. The method prompt lifts Gemma to 40%, Qwen 3.8 to 50%, Qwen 3.5 122B to 60%. But it makes the Qwen family ruminate in the visible output until the budget cuts them off, so those rows are 40–90% fallback moves. Gemma does not benefit from thinking at all (40% either way, more deadlocks with thinking), which matches its Tetris behaviour: given room, it stalls rather than plans.
• Nothing helps Nemotron 3 Super or Granite. 0% and 10% coached respectively, fewest boxes on targets in the table.

Two ways to deadlock

The solver distance lets us watch a plan go wrong. The standard-prompt failure is a correct intention executed from the wrong square. Gemma 4, micro level 0, turn 5, distance 10 → dead:

"Push the box at (8, 7) onto the target at (8, 8)."

(8,8) is the corner of the room. The target is at (8,7), where the box already was; the model's own coordinate list said so one line above. Nemotron Bolt without thinking, same level, turn 1, proposes RRRRRRRR: walk right until something happens.

The thinking-channel failure is different in kind. Muse Glimmer, which plans well when it reads correctly, on the same level: distance 14 → 12 → 10 over three good turns, then

"Push the box on the target at (8,7) to the adjacent target (8,8), then move up to (7,7) and push the box at (6,7) up onto the target at (5,7)."

A three-push plan with the right structure, built on one misread cell. It then spent six turns trying to free a box that could not move. That is the Tetris perception failure appearing in a game that was supposed to have none: the coordinates are in the prompt, and the model still believes its own picture of the room over the list.

For contrast, a one-shot solve. Haiku with thinking, micro level 0, turn 1, distance 14 → 0 in 20 moves:

"Push the bottom box right to (8,6), then slide the middle box (7,6) right to (7,8) and up-push the box at (6,7) onto target (5,7). Drop (7,8) down onto (8,8), push (5,8) up twice to (3,8), then push (8,6) right onto (8,7)."

Bolt with thinking produced the same solution on the same level, in the same order, with one extra move.

How much thinking does a local model need?

Haiku solves micro at ~2k tokens a turn. Qwen 3.8's natural length on the same puzzles is ~7k. Same model, same levels, three caps on the thinking channel:

• It uses the tokens more than it needs them. 8k buys the same solve rate as 32k in 64% of the time, and the same single level (#0) is the one it misses. The cap shows up as stalls, not losses: the two levels where it kept overrunning burned 20 and 9 turns instead of one to three.
• 2k is below its floor. Twenty turns, twenty cap hits, no answer, no box moved. Qwen cannot compress a Sokoban plan into Haiku's budget; the gap to the frontier model on these puzzles is compression, not capability.
• gpt-oss confirms it from the other side. Given an unbounded channel it also settles at ~7k tokens a turn, solves 70% with 5 one-shots, and never truncates. Every earlier gpt-oss row in this study was a budget artefact. It is the fastest local thinker that is not a 2-bit quant: 1.3 hours for ten levels against Qwen's 5.0.

The same sweep on Nemotron Bolt, whose medium failure was all cap hits. Micro at 8k and 32k; medium at 32k and 64k:

• Bolt is the opposite case: it needs the tokens, and more of them does not help. At 8k on micro it caps on 92% of turns and drops from 90% to 50%, so Qwen's "compression, not capability" result does not transfer. On medium, doubling the cap to 64k removes the budget problem (fallback 46% → 2%) and buys one level: 10% solved, 90% deadlocked, at ~50k tokens a turn. Once Bolt is allowed to finish its thoughts, what is left is a planning failure, the same one Flash-Next and gpt-oss show at a third of the tokens.

Results: medium tier

Ten levels, optimal 33–60 moves. Only the conditions that solved anything on micro were run.

• Without thinking, the frontier models collapse to zero. Sonnet no-think deadlocks 90% of levels, usually on its first answer: it commits to a confident long plan and pushes something into a corner. Haiku no-think dawdles instead, 20 turns on average, few deadlocks, nothing solved. Micro hid both failure modes.
• Haiku with thinking is the best thing we tested here, 60% solved at 1.14× optimal, twice Sonnet's rate. The same inversion as Tetris, and the same caveat: Sonnet's medium-effort "thinking" is a few hundred tokens of nothing. We cannot say what Sonnet does when it actually thinks, because the API would not let us make it.
• Qwen 3.8 27B with thinking ties Sonnet at 30%, including one level solved at exactly optimal length (33 moves, two turns) and one textbook seven-turn descent, 49 → 47 → 36 → 38 → 27 → 8 → 3 → 0. It took 20 hours. On the levels it lost, it often hit the 32k thinking cap several turns in a row at 78 minutes each, so "unbounded" was not, quite.
• Bolt breaks on medium, and the token counts say why. 73% of its turns ran to the 32k cap (average 30k tokens), each cap a random fallback move, 0% solved, every level deadlocked. On micro it averaged 16k and capped on 15% of turns. It can think; it cannot think compactly once the puzzle gets long. Haiku does medium at 4k tokens a turn.
• Flash-Next finishes its thoughts and still loses. 10% solved, 90% deadlocked, only 13% of turns truncated. Unlike Bolt, its failures are planning failures, not budget ones. The 6B-active model is simply weaker at lookahead than the dense 27B from the same family.
• The two other local thinkers do not reach medium. gpt-oss 120B with the unbounded channel, 0% solved and 90% deadlocked at ~10k tokens a turn with no truncation, so this is a planning failure, not a budget one. Qwen 3.8 at an 8k thinking cap, 0% solved with 81% of turns falling back after hitting the cap, over 41 hours. Against the same model's 30% at 32k, the budget that was free on micro is the whole result on medium: the 8k cap that cost nothing on 15-move puzzles removes every solve on 50-move ones.

Results: hard tier

Boxoban's hard set, levels 0–9, optimal 35–84 moves. Both Claude models with thinking (Sonnet at medium and at high effort), and one local model: Qwen 3.8 27B with the 32k thinking channel.

• Haiku's curve is now complete: micro 100% → medium 60% → hard 20%. Boxes on target follow the same slope (100% / 75% / 57%).
• On hard it stalls rather than kills. 20% deadlocks against 20% on medium; seven of the ten levels ran out the 25-turn budget with two or three boxes placed. The opposite of Sonnet's no-think behaviour on medium, where it commits confidently and corners a box on turn one.
• The 20% is a floor, not a ceiling. 27% of its turns were fallbacks because the thinking overran the client's token allowance (4.6k average, 27% of turns truncated) - the first time Haiku has hit a budget in either game. A larger thinking budget is the obvious next run and is cloud-cheap.
• With a 24k thinking allowance, both Claude models reach 40%. Haiku goes from 20% (27% fallback) to 40% with fallback down to 12%, 0% deadlocks and 82% of boxes on target, at ~9k tokens a turn. Sonnet at the same allowance also solves 40%, but by a different route: ~1.8k tokens a turn, zero fallback, and 50% of levels deadlocked, the same commit-and-corner pattern as its no-think medium run. Same score, opposite failure mode; on n = 10 the two are indistinguishable.
• The first local model on hard: Qwen 3.8 27B with thinking solves 10% against 40% for Haiku and Sonnet at 24k. 90% of levels deadlocked, 48% of boxes on target, ~17k tokens a turn with 10% fallback, 25 hours for ten levels. Its curve is micro 90% → medium 30% → hard 10%, steeper than Haiku's, and the failure is Sonnet's commit-and-corner pattern rather than Haiku's stall.
• Sonnet at high effort is the first row past 40% on hard: 50% solved. Against Sonnet at medium-24k (40%) and Haiku at medium-24k (40%), the high row deadlocks 40% of levels (Sonnet medium-24k 50%, Haiku 0%), spends ~7.2k tokens a turn (Sonnet medium-24k ~1.8k, Haiku ~8.9k) and takes 152 s a turn (Sonnet medium-24k 53 s, Haiku 76 s). The thinking is real this time, and it buys one extra level on n = 10, with 11% of turns falling back from overrunning the allowance.

Two new models, and what quantisation costs

Both arrived mid-study and both ship in forms that make them interesting as engineering objects, not just as scores. The speed numbers are warm, thinking off, identical prompt, each model alone on the GPUs.

• Nemotron 3.5 Bolt (74B-A9B, IQ2_XXS). Nvidia's only shipped format is a 2-bit quant, so the quant is not a confound here; it is the product. It is the fastest model on this box by 2× and fits on one GPU. Without thinking it is the worst model in the table at anything spatial: it misreads Tetris column heights by 3.2 rows (the second-worst of 17 models in that probe), survives 10.8 Tetris pieces, and plays Sokoban at 59% illegal moves. With thinking it solves 90% of micro Sokoban, one-shots 7 of them, and plays the best local Tetris we have seen (92 pieces, 21.5 lines, roughly Sonnet-no-think territory). The reading we would defend: the 2-bit quant damaged the model's direct perception and left its reasoning mostly intact, and the speed that comes with 2 bits is what makes 16–25k tokens of reasoning per move tolerable at all. Where it breaks is reasoning length: on medium Sokoban it cannot bring a plan in under 32k tokens.
• Qwen 3.8 Flash-Next (125B-A6B, Q4). The opposite trade. Best no-think local on every count (first no-think local Sokoban solve, 17 Tetris pieces, better column reading than Bolt), and the least improved by thinking: 10% → 60% on micro, 10% on medium, 34 Tetris pieces with thinking, the same plateau as Gemma and gpt-oss. Its public benchmarks are agentic coding; nothing here tests that, and nothing here suggests the planning transfers.

Reading across the two games

Put next to the Tetris results, Sokoban changes the story in one place and confirms it in two.

• Confirmed: the no-think floor is below random. In both games, every local model with the standard prompt does worse than a random legal move. In Tetris we could blame perception. In Sokoban the coordinates are written out and the result is the same. The failure is that a one-shot answer commits to the first plausible plan, and the first plausible plan is usually geometrically impossible.
• Confirmed: thinking is where the capability lives. The same 27B model is 0% or 90% depending on whether it has a reasoning channel. No amount of prompt engineering in the visible output got close.
• Changed: the local "plateau" is not a plateau. In Tetris every local thinking run landed at 32–36 pieces and we called it a ceiling. In Sokoban the same runs span 40% (Gemma) to 90% (Qwen, Bolt), and Bolt's Tetris run broke the plateau outright. The ceiling was partly a Tetris artefact: a 250-piece game is 250 chances to make the one misread that ends it, and Sokoban's micro levels are 15 moves long. Short-horizon planning in a thinking channel works for the better local models. Long-horizon error accumulation, Tetris at 1,000 pieces or Sokoban at 50 moves, is where the gap to Haiku reopens.

What I'd change

• Thirty levels per tier, not ten. Every difference in the medium table is one to three levels.
• A real Sonnet-thinking row through the direct Anthropic API, where thinking can be forced on with a budget. Until then "Haiku beats Sonnet" is "Haiku-thinking beats Sonnet-not-really-thinking".
• A perception-free control for the local no-think rows: remove the ASCII board and give only the coordinate list. If Muse and Gemma still push into corners, the failure is not reading; it is building a spatial model from either representation.
• Sonnet at high effort on micro and medium, so its curve is measured with thinking actually on at every tier, not just hard.

Changelog

• November 03, 2026 - Hard tier: Claude Sonnet 5.5 at high effort with a 32k thinking allowance (50%), the first row above 40% on hard.
• October 31, 2026 - Thinking-budget sweep on Nemotron Bolt (8k on micro, 64k on medium) and the first local model on the hard tier, Qwen 3.8 27B with thinking at 32k (10%).
• October 29, 2026 - Hard tier: Haiku and Sonnet with thinking re-run at a 24k thinking allowance (both 40%). Medium tier: gpt-oss 120B with the unbounded channel and Qwen 3.8 at the 8k thinking cap (both 0%).
• October 27, 2026 - Added the Qwen 3.8 thinking-budget sweep (2k / 8k / 32k), a clean unbounded-thinking run for gpt-oss (replacing the budget-contaminated row as its headline number), and the hard tier with Haiku-thinking. Harness fix: moves now commit per turn so cloud and local runs can share the database; the first attempt at this batch aborted on a lock.
• October 23, 2026 - First publication. Micro tier: 9 local models across standard, coached and thinking conditions, plus Claude Haiku/Sonnet 5.5 with thinking on and off. Medium tier: the seven conditions that solved anything on micro. Nemotron 3.5 Bolt and Qwen 3.8 Flash-Next added with a throughput probe. Solver replaced mid-study with a move-optimal version after Haiku beat the original's "optimal" by four moves; all stored distances recomputed by replay.