Grid-Bench: Can LLMs Predict How Discrete Worlds Change?

AI summary

Overview

Research area: Natural Language Processing / spatial reasoning and state tracking in large language models.

Technical level: Intermediate. The core idea is intuitive (given a grid, rules, and a list of events, predict the final grid), but the paper uses formal notation for grids, transition operators, and evaluation metrics.

Scope: Grid-Bench is an executable benchmark of eight families of grid operations on two-, three-, and four-dimensional discrete worlds, used to test whether six large language models can predict the complete final state after a sequence of events.

What This Paper Is About

When instructions arrive as a sequence ("move this, then place an obstacle there, then move again"), each step acts on a world that earlier steps have already changed. Grid-Bench asks whether large language models can take an initial grid, a set of explicit rules, and an ordered list of events written as text, and return the entire resulting grid. Because a simulator executes the same events to produce an exact reference state, every single predicted cell can be checked, so the benchmark measures both complete recovery and the size and location of mistakes when recovery fails.

Key Contributions

1. An executable benchmark for complete-state prediction. Grid-Bench supplies an initial grid, explicit rules, and an event history as text, and requires one response containing the full final grid. A reference simulator computes the exact target, making every predicted value checkable.

2. Eight operation families across two, three, and four dimensions. The families are PAINT, REFLECT, STENCIL, MIX, RELABEL, LAYER, MOVE, and COMPRESS, spanning geometric transforms, neighborhood aggregation, connected regions, and movement. Each extends to all supported dimensions under one shared state representation, with single-cell SET assignments interleaved into histories.

3. A controlled instance-construction procedure. Generation varies history length, dimension, and within-family workload. Histories are queried at prefix lengths T = 0, 1, 8, 16, 32, and 64, so the same initial world can be compared across progressively longer event sequences. Dimension comparisons use approximately matched world volumes (252 or 256 cells).

4. A multi-level evaluation protocol. Beyond semantic full-world exact match (EM), the paper defines cell accuracy, wrong-cell counts with median and 90th-percentile summaries, and a partition of errors into cells whose final value must differ from the initial state (C) versus cells whose final value must match it (U). It also compares predictions against copy-initial, all-zero, and partial-execution baselines.

Main Findings

• Long histories break exact recovery. All six models recover the supplied initial state almost perfectly at T = 0, but exact match declines sharply as histories grow. GPT-5.6 Sol falls from 95% after one event to 13% at T = 64.

• One-event accuracy does not predict long-history accuracy. Claude 5 Sonnet, Kimi K2.5, and MiniMax M2.5 start with comparable scores, but Kimi K2.5 and MiniMax M2.5 fall well below Claude 5 Sonnet by T = 8.

• Similar exact match can hide very different errors. On the 84 shared instances at T = 8 where both Kimi K2.5 and MiniMax M2.5 return valid but incorrect states, their median wrong-cell counts are 14 and 67 respectively.

• Success is uneven within a single history. Every model has cases where a later, separately queried prefix is correct even though an earlier positive-length prefix was wrong.

• Long-history errors hit both updating and preservation. At T = 64 most incorrect grids have errors in both the C and U groups, yet at T = 16, 32, and 64 every model has higher cell accuracy on final-unchanged cells.

• Predictions beat naive copying, but unevenly. At T = 64, GPT-5.6 Sol's mean cell accuracy is 81.6 versus 51.0 for copy-initial (about a 31 percentage point gain), while GPT-5.4 Mini (56.1 vs 50.6) and MiniMax M2.5 (52.4 vs 50.9) show much smaller gains. Claude 5 Sonnet reaches 90.5 but returns only 58 valid grids out of 192.

• Executing only the later operations does not solve the task. A baseline applying every SET but executing core operations only in the final half of the history recovers only three of the 192 main targets at T = 64.

• Task family matters. RELABEL is the highest-scoring family for every model under its low-merger policy; relative performance across the other families varies by model.

• More dimensions are harder. Pooled over T = 8–64, accuracy is nonincreasing from two through four dimensions for every model. The early profiles differ: GLM-5 already shows a pronounced dimension gap after one event, while GPT-5.6 Sol has nearly equal one-event scores and only gains its two-dimensional advantage over longer histories.

• Workload effects are task-dependent. In the two-dimensional workload study, every model scores lower at the largest MIX and LAYER targets than at the smallest; comparing the smallest and largest MIX targets at T = 64, reference execution shows roughly fivefold increases in mean cell-value reads and mean changed-cell counts per core event. PAINT shows mixed directions across models, and REFLECT includes nonmonotonic profiles.

Methodology in Plain English

The researchers built a small simulated universe: a bounded grid in two, three, or four dimensions, where each cell holds an integer and 0 means empty. A model is handed the starting grid, a written description of the rules, and a numbered list of events, and must write out the whole final grid in a single answer using a sparse list of nonzero coordinates.

Each trajectory sticks to one core operation family (say, growing and shrinking connected regions), with occasional single-cell SET writes mixed in. A simulator runs the same events to produce the ground truth, so scoring is exact rather than judged by another model.

To keep comparisons fair, the authors freeze generation settings in advance: they fix the family, grid shape, alphabet, and a workload target, then accept candidate trajectories only if they stay nonempty and meet bounds on density, mean workload, and how often a core event actually changes the state. Each accepted trajectory is then queried separately at six prefix lengths, so the same world can be examined at increasing history depth.

Scoring has three layers: does the whole grid match; if not, how many cells are wrong; and are the wrong cells ones that had to change, ones that had to stay the same, or both. Baselines — copying the initial state, returning all zeros, and executing only the later operations — show how much of the score comes from genuine simulation rather than shortcuts.

Why This Matters

Impact on research. Most spatial benchmarks ask targeted questions about relations or single transformations. Grid-Bench scores the entire resulting world, which turns a vague "does the model reason spatially?" question into a measurable one: which cells are wrong, how many, and whether the failures are about applying changes or about preserving what should stay fixed. The executable rules also produce unlimited training examples with exact targets, and the update-versus-preserve split gives a diagnostic that plain accuracy hides.

Real-world applications:

• Robot and embodied instruction following, where a sequence of moves and placements must be simulated to know where things end up, including when an earlier action blocks a later one.
• Warehouse and logistics planning, where compaction, movement, and obstacle placement over a grid mirror how pallets and items are rearranged.
• Geometric and CAD-style design tools, where reflections, region growth, and layer operations are applied in sequence to a structured layout.
• Spreadsheet-style data transformation, where a COMPRESS-like operation removes gaps, merges adjacent equal values, and packs values toward a boundary.

Industry relevance. Models are increasingly asked to reason about state that changes over time rather than answer a single question. The finding that models with equal single-step accuracy separate sharply over longer histories is directly relevant to anyone deploying LLMs in agentic pipelines where a plan is executed step by step and the final configuration must be predicted or verified before acting.

Future Directions

• Transfer beyond the benchmark's conditions. The authors state that whether results carry over to other world sizes, different operation distributions, or environments with uncertain observations remains an empirical question.
• Connecting errors to internal computation. The paper measures only the final values returned; linking update-versus-preserve failure patterns to intermediate representations or execution strategies requires evidence about the steps in between.
• Training from executable rules. Since the simulator yields exact targets, a natural next step is using Grid-Bench-style generation to train models and then checking, via the cell-level diagnostics, whether they improve at making required changes, preserving unchanged values, or both.
• Longer histories and tool use. The study caps histories at 64 events and gives models no tools and a 128,000-token ceiling; whether performance is limited by reasoning or by context, and whether allowing execution helps, are open questions the setup leaves untested.

Target Audience

Researchers and engineers working on spatial reasoning, state tracking, and long-horizon reasoning in language models, plus benchmark designers who want an executable, fully checkable alternative to multiple-choice spatial QA. It is also useful for practitioners building agentic systems that must predict or verify the outcome of multi-step operations on structured state, and for readers who want a clear example of how cell-level error analysis can reveal differences that aggregate accuracy conceals.

Authors’ abstract

Spatial instructions describe how to move objects, transform regions, or modify their surroundings. When several operations are applied in sequence, each acts on a configuration shaped by earlier changes. How accurately can large language models (LLMs) predict the resulting spatial state? We introduce Grid-Bench, an executable benchmark in which eight families of operations transform discrete worlds represented as two-, three-, and four-dimensional grids. Given an initial grid, explicit rules, and an event history expressed as text, a model predicts the complete final grid. Reference execution makes every predicted value checkable, supporting comparisons across spatial operations, history lengths, and workloads. Evaluating six LLMs shows that complete-state accuracy falls sharply as histories grow, with substantial divergence among models that perform similarly on single events. Models with similar exact-match accuracy can nevertheless differ substantially in the number of incorrect cells on shared instances. Even over long histories, some models recover many correct changes beyond what copying the initial state would yield. Grid-Bench makes both complete recovery and these differences in returned states directly measurable across a range of spatial conditions.