arXiv CSopen access

Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

artificialintelligence knowledgerepresentation reasoning

artificial intelligence, reasoning, knowledge representation

Preprint. Under review.

Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym Lars Benedikt Kaesberg Tianyu Yang Bela Gipp∗ University of Göttingen, Germany [email protected]

Niklas Bauer

Terry Ruas

Jan Philip Wahle∗

arXiv:2604.09338v1 [cs.AI] 10 Apr 2026

Abstract Spatial reasoning is central to navigation and robotics, yet measuring model capabilities on these tasks remains difficult. Existing benchmarks evaluate models in a one-shot setting, requiring full solution generation in a single response, unlike humans, who work in interactive environments step-bystep. We introduce Spatial-Gym, a Gymnasium environment that isolates spatial constraint reasoning by testing pathfinding in 2D-grid puzzles as a sequential decision task with optional backtracking. We evaluate eight models in three settings (one-shot, step-by-step, step-by-step with backtracking) against human, random, and A* baselines on 500 episodes. The best model, GPT-OSS 120B, achieves a solve rate of 16.0%, 82 points below the human baseline (98.0%). Step-by-step format helps weaker models (up to +5.4%) by removing formatting errors, but hurts stronger models (up to −5.6%) by constraining global planning. Backtracking improves episode completion, but increases solve rate only for weaker models; stronger models rarely backtrack and do not benefit from it. Our experiments have three key findings: (1) models fail to scale reasoning effort with difficulty, (2) vision models receiving images of the spatial environment reduce solve rate by 73%, and (3) extended chain-of-thought reasoning retains a 3 − 5× accuracy advantage over standard inference even in the step-by-step setting. Spatial-Gym enables diagnosis of model limitations and provides a framework for improving spatial reasoning through reinforcement learning.

Introduction

Spatial reasoning is a central human ability for navigating the real world and for designing some of humanity’s most complex inventions, including robotic motion planners and printed circuit boards (Uttal et al., 2012). Large language models (LLMs) are increasingly deployed as high-level planners for such tasks, generating decision sequences that maintain overarching goals (Ahn et al., 2022; Song et al., 2022; Zhou et al., 2025). Yet it remains unclear how well these models can perform spatial reasoning, because current evaluations rely on one-shot, non-interactive tasks rather than step-by-step environments that capture how humans solve such problems. Most benchmarks require models to produce a complete solution in a single pass, making it difficult to assess where reasoning mistakes occur and to distinguish whether a failure reflects flawed reasoning or an inability to express a valid output (Aghzal et al., 2023; Dao & Vu, 2025). A recently presented dataset for testing spatial reasoning (Kaesberg et al., 2025b) combines path planning with interacting constraints and shows a large human–model gap (98% vs. 15.8%), unaffected by architecture, scale, or prompting. Prior work on textual gridworlds (Kim et al., 2024) and maze navigation (Poudel et al., 2026) shows that when models perform stepwise reasoning, they improve performance, but these environments use simple rule constraints that may overlap with pretraining data, and do not support backtracking prior steps. Qin et al. (2025) show that backtracking can improve model performance on structured tasks such as Sudoku, but harms them in less constrained tasks such as Countdown (Katz et al., 2025). Existing spatial reasoning tasks lack a combination of sequential decision-making, rule-based constraints, and backtracking in an interactive reinforcement learning (RL) environment. ∗ Equal contribution. Author order randomized by coin flip.

Preprint. Under review.

Spatial-Gym Rules & Actions

Backtracking Rule Violated!

ALLOWED ACTIONS: ↑ ↓ ← →

Termination Criteria 1. Reach End Node (Path rules verified for success)

- Pair of same color Stars need to be grouped - Must separate colored Squares - Path must be continuous, non-intersecting

2. Dead End (No valid actions) 3. Step Limit (100 total steps)

3. Mistake Branch (Rule Violated: Black Stars)

1. Start State

2. First Steps

4. Correct Path

Figure 1: Overview of the Spatial-Gym task.

(Rules Satisfied)

We introduce Spatial-Gym (cf. Figure 1), a Gymnasium environment (Towers et al., 2024) that formulates 2D grid pathfinding with interacting constraints as a sequential decision task with automatic solution verification and outcome and process rewards for RL. The environment builds on Kaesberg et al. (2025b) and provides 1,000 tasks across five difficulty levels. Agents select to construct one path tile at a time, given the current grid state, path history, and legal moves, with optional backtracking to undo prior steps. We evaluate eight models across three settings: one-shot, stepwise (Spatial-Gym), and stepwise with backtracking (Spatial-Gym+backtracking). We compare models with human, random, and A* baselines (§4). Our results reveal four key findings. First, the best model, GPT-OSS 120B, achieves 16.0% accuracy in the Gym setting, 82 points below humans (98.0%). Spatial-Gym isolates spatial reasoning as the primary bottleneck in current models and shows that this limitation is independent of scale, architecture, and evaluation format. Second, we observe a trade-off between instruction-following of models to format the correct response and actual reasoning capabilities. The interactive environment format helps smaller models by removing formatting errors (up to +5.4% accuracy) but hurts frontier models (up to −5.6% accuracy), possibly because their long reasoning traces can lead to long-context issues (§4.1). Third, backtracking reduces deadlocks (i.e., when no legal actions are available anymore) for all models but improves accuracy only for weaker models; stronger models rarely use it and lose performance when they do (§4.2). This behavior suggests that model training incentives discourage exploration in constraint-heavy tasks. Fourth, models fail to scale reasoning effort with puzzle difficulty and use backtracking to shorten paths rather than explore alternatives. Visual language models receiving the entire puzzle as an image perform generally worse than regular LLMs (§4.6). Key Contributions:

▶ (§3) Spatial-Gym, a Gymnasium environment that formulates 2D grid pathfinding with interacting rule constraints as a sequential decision task with optional backtracking. We also provide verification and reward signals for future RL methods. ▶ (§4.1) An evaluation of eight models in one-shot, step-by-step, and step-by-step with backtracking against human, random, and A* baselines showing a 82-percentage-point human–model accuracy gap. ▶ (§4.2) The identification of a new formatting–reasoning tradeoff and a backtracking paradox in which the step-by-step format helps smaller models (up to +5.4% accuracy) but hinders frontier ones (up to −5.6% accuracy) while backtracking improves path completion but increases accuracy only for smaller models. ▶ (§4.3 to 4.7) Additional experiments on path generation effort, rule type difficulty, algorithmic baselines, and spatial reasoning with visual language models. ▶ A public release of code and data for evaluating frontier models and training better ones for spatial reasoning.1 1 Code and data are anonymously available under: Spatial-Gym and Spatial-Gym-Analysis

Preprint. Under review.

Related Work

Spatial reasoning. Early spatial datasets such as bAbI (Weston et al., 2016), SpartQA (Mirzaee et al., 2021), and StepGame (Shi et al., 2022) are based on multiple-choice formats, commonsense knowledge, or highly predictable sentence structures, and not on complex spatial logic. Recent work raised the difficulty by introducing more complex abstract visual reasoning tasks (e.g., VisualPuzzles (Song et al., 2025), ARC (Chollet, 2019; Chollet et al., 2024)). Aghzal et al. (2023) proposed a benchmark on spatial-temporal reasoning and showed that LLM performance on grid-based path planning collapsed with grid size and obstacle count. The SPaRC dataset (Kaesberg et al., 2025b) combined path planning with interacting rule constraints and found a human–model performance gap that neither architecture, scale, representation, nor prompting could explain. However, all of these evaluations were one-shot (in the evaluation sense, not in the model-prompting sense). The model produced a single complete answer, which was scored against a (set of) ground truth solutions. This is not how humans typically solve these problems, and could conflate output formatting ability with spatial reasoning ability, motivating Gym-based environments. Stepwise spatial navigation and LLMs as agents. Reformulating spatial tasks as sequential decisions can mitigate the aforementioned issues and mimic how humans would solve such tasks (Zamprogno et al., 2023). Highlighting this shift, the recently introduced ARC-AGI-3 (Foundation, 2026) benchmark transitioned abstract reasoning into an interactive, turn-based environment in which agents must explore and efficiently plan action sequences. Similarly, Kim et al. (2024) showed that cognitive-map-style chain-of-thought (CoT) (Wei et al., 2022) (where individual steps were abstracted in the verbalization) improved extrapolation to larger grids in textualized gridworld tasks. Dao & Vu (2025) combined supervised finetuning with GRPO (Shao et al., 2024) for step-by-step maze solving, reaching 93% accuracy. Both results showed that stepwise interaction helped, but the mazes were comparably simple, containing only walls and open cells without interacting rule constraints. Whether these gains transferred to constraint-heavy tasks remained an open question. Beyond spatial domains, language models were evaluated as sequential decision agents in web browsing (Zhou et al., 2023), code execution (Liu et al., 2023), and other interactive settings (Chen et al., 2024). Qin et al. (2025) found that backtracking improved performance on structured constraint tasks, but limited models on less constrained problems. These studies motivate the need for an environment that operates in a step-by-step, interactive manner and supports the evaluation of more complex mechanisms, such as backtracking. This work. Recent Gymnasium-based platforms such as KORGym (Shi et al., 2025) and Reasoning Gym (Stojanovski et al., 2025) included spatial tasks as subcategories of broader reasoning benchmarks, but none focused on spatial constraint reasoning or provided interacting rule constraints and backtracking. To the best of our knowledge, Spatial-Gym is the first Gymnasium environment dedicated to spatial constraint reasoning. It reformulates 2D grid puzzles as a sequential decision process and eliminates path-construction errors by providing only valid moves at each state.

Spatial-Gym

Humans do not generate complete solutions to puzzles in a single pass (Zamprogno et al., 2023). They make assessments, reason about the next step, and backtrack when needed. Yet most constraint benchmarks evaluate models by requiring a complete solution in a single response, from logic grid puzzles (Lin et al., 2025) to combinatorial tasks (Mittal et al., 2024; Gevers & Daelemans, 2025). We propose Spatial-Gym to reframe spatial reasoning as sequential single-step decisions, matching how humans naturally solve such puzzles and isolating reasoning from formatting. The Gym builds on Kaesberg et al. (2025b) and consists of 1,000 2D grid pathfinding puzzles (500 train, 500 test) across five difficulty levels. Unlike Kaesberg et al. (2025b), it formulates the task as a Markov Decision Process via the Gymnasium interface, introducing step-bystep rule evaluation, partial rewards, and backtracking. Each puzzle is an m × n grid of rule cells with a start and end point on the grid edges. The goal is to draw a continuous, 3

Preprint. Under review.

non-self-intersecting path along grid edges from start to end while satisfying all rule cell constraints. The Gym has seven rule types: Dots (path must pass through), Gaps (path cannot cross), Stones (color separation), Stars (pairing with same-color elements), Triangles (edge counting), Polyominoes (shape fitting), and Ylops (shape subtraction). Puzzle difficulty is a weighted combination of distinct rule count, total rule cells, rule density, grid size, and estimated rule interactions, normalized to a 1–5 scale. Full rule definitions are available in Appendix C. We use the same 500 test puzzles from Kaesberg et al. (2025b) for evaluation. We formalize Spatial-Gym as a Markov Decision Process (S, A, T, R) using the Gymnasium interface (Towers et al., 2024). Each state st ∈ S consists of the current environment grid (including rule cells and their types), the path traced so far (as a sequence of visited edge nodes), the agent’s current position, and the set of legal actions available from that position. The action space is A = {up, down, left, right}. At each step, only actions leading to valid, unvisited adjacent nodes are offered to the agent. This eliminates invalid-path errors, such as disconnected lines, self-intersections, rule-cell crossings, and incorrect start/end conditions. The transition function T (st+1 | st , at ) defines how the environment updates the agent’s position and extends the traced path. The agent receives the updated board state as a text representation, including the grid with the previously walked path, a list of legal actions, and the current position coordinates. An episode terminates when either of the following conditions is met: (1) the agent reaches the end node, at which point the path is evaluated against all rule conditions to determine success or failure; (2) the agent reaches a deadlock with no valid moves remaining; or (3) hits a 100-step limit. This prevents infinite loops without bottlenecking performance; only 3.9% of episodes reach it, mostly during unproductive backtracking loops. By default, the Gym setting prevents the agent from backtracking, but the Gym can enable a mode that allows previous actions to be reverted. The reward function R(st , at ) provides two reward signals designed for RL training. The outcome reward is +1 if the agent reaches the end node and all rule conditions are satisfied, and −1 otherwise (deadlock or step limit). The process reward is +0.01 for each step that results in a path from start to the current location, which matches with a sub-path of the solution, and −0.01 for any other case.

Experiments

We evaluate eight models: GPT-OSS 120B, OLMo 3.1 32B, Nemotron 49B, Qwen 3 32B, R1 Distill Qwen 32B, Gemma 3 27B, Magistral Small 24B, and Qwen 3 0.6B. We test these models under three settings. Baseline (one-shot path generation), Spatial-Gym (step-by-step), and Spatial-Gym with backtracking. We report the percentage of puzzles solved (accuracy) and the percentage of puzzles where the agent reached the end node (completion rate). Details on model versions and hardware are provided in Appendix A. General Results 100 75

98%

50 25

16.0% 11.4%

11.0% 10.6%

5.2% 4.0% 2.7% 2.6%

H G PT um -O an O SS LM 12 0B o 3 N em .1 3 2 ot ro B Q n4 9B w e R1 n 3 32 D B is til G em l 3 m 2B a 3 Q 27 w B e M n 3 ag 0. is 6B tr al Sm al l

We run all eight models on Spatial-Gym without backtracking on the full 500-puzzle test set. Each model receives the system prompt with rules, the current board state, and legal actions at each step (see Appendix B for the full prompts and Appendix D for a complete example with GPT-OSS 120B). We plot the human baseline from Kaesberg et al. (2025b), in which humans also solved puzzles step by step via an interactive interface.

Accuracy (%)

4.1

Figure 2 shows the accuracy values per Figure 2: Accuracy (%) of all models on model. GPT-OSS 120B is the leading frontier Spatial-Gym with no backtracking. model (16.0%), followed by OLMo 3.1 32B (11.4%), Nemotron 49B (11.0%), and Qwen 3 32B (10.6%). Other models are below 6%. 4

Preprint. Under review.

10.0 7.5 5.0 2.5 0.0 −2.5 −5.0 −7.5 −10.0

+5.4%

+2.7%

+1.6% +1.0%

+1.6% +1.1%+1.0%

+0.2% -1.0% -1.8%

32 G

PT -O

1 3. o

LM O

B 32 3

49 B Q w

ro n ot

em N

B 27

w Q

l al is

til l

lS m

tr a is ag M

32 B

-5.8%

32 B lS m em al ot l ro n O 49 LM B o 3. G PT 1 32 -O B SS 12 0B N

is D

tr a

til l

27 Q

-4.8% -5.6%

Q w

+3.2% +2.3%

(b) Gym w/ backtracking vs w/o backtracking

-0.4%

∆ Accuracy (%)

(a) Gym w/o backtracking vs Baseline

Figure 3: ∆ Accuracy (%) for each model relative to two settings: (a) Gym accuracy minus baseline accuracy; (b) Gym w/ backtracking accuracy minus w/o backtracking accuracy. Bars above zero show improvement under new conditions; bars below zero indicate collapse. Two findings stand out. First, three reasoning-trained 32B models (OLMo 3.1, Qwen 3, Nemotron) cluster between 10.6% and 11.4%, while R1 Distill 32B reaches only 5.2%. Unlike the other three, R1 Distill is trained through distillation from a larger teacher rather than direct RL on reasoning tasks (DeepSeek-AI et al., 2025), suggesting that the way models learn to reason matters more than parameter count within a size class. Second, Gemma 3 27B, the only model without reasoning-specific tuning, outperforms the smaller reasoning models and almost matches R1 Distill 32B. Full tabular results, including exact breakdowns by difficulty, rule type, and average step counts, are in Appendix G. We also analyzed inter-model agreement and found that while frontier models solve a superset of puzzles, weaker models occasionally find unique solutions, suggesting multi-agent ensembles could be beneficial (details in Appendices E.5 and E.6). Formatting and reasoning tradeoff. We compare each model’s accuracy on the baseline task vs. Spatial-Gym on identical puzzles. Figure 3a shows the accuracy delta of models (SpatialGym − baseline). Delta values correlate inversely with original baseline performance (cf. Figure 2) and model scale. Weaker models in the default setting gain between 2.3% and 5.4% accuracy, while stronger models lose between 4.8% and 5.6%. As later experiments will further demonstrate, weaker models benefit because the Gym eliminates formatting errors, which caused over 50% of failures in the baseline setting. Stronger models rarely produce invalid paths in the one-shot setting but lose performance in the Gym because the per-step decision frame shifts attention toward immediate moves, limiting global planning even though the full grid remains visible. This parallels Kambhampati et al. (2024); Qin et al. (2025), who find that stepwise decomposition helps on locally constrained problems but hurts on tasks requiring long-horizon coordination. 4.2

Backtracking

Humans naturally backtrack when solving spatial puzzles, revising previously made decisions when mistakes become apparent (Zamprogno et al., 2023). In this experiment, we enable models to backtrack, allowing them to undo recent moves. Figure 3b shows the accuracy delta of models (Backtracking − standard Gym). The pattern is similar to the formatting-reasoning tradeoff. Models that performed worse in Figure 2, such as Magistral Small, R1 Distill 32B, and Qwen 3 0.6B, show gains of 1.1% to 2.7% accuracy, while stronger models, such as GPT-OSS 120B and OLMo 3.1 32B, lose 1.8% to 5.8%. Completion rate improves universally (Figure 4). R1 Distill increases completion rate from 50% to 88%, Qwen 3 32B from 60% to 89%, and GPT-OSS from 85% to 94%. While GPT-OSS finishes more puzzles with backtracking enabled, it solves fewer correctly (−5.8% accuracy). Reaching the end node is necessary but not sufficient. Each change from the original one-shot format (Gym w/ or w/o backtracking) results in additional performance loss for the two strongest models, GPT-OSS 120B and OLMo 3.1 32B. This format sensitivity is consistent with pre-training data contamination, as memorized 5

85%

Gym w/ backtracking

Finished

71%

65%

60%

Deadlocked

94% 50%

48%

43%

92%

84%

Deadlocked

89%

88%

55%

42%

49%

76%

PT -O SS O LM 120 B o 3. N em 1 3 2B ot ro n 49 Q w B en 3 R1 32 D B is til G em l 32 B m a 3 Q 27 w B en M 3 ag 0 .6 is B tr al Sm al l

100 75 50 25 0

Gym w/o backtracking

PT -O SS O LM 120 B o 3. N em 1 3 2B ot ro n 49 Q w B en 3 R1 32 D B is til G l 32 em B m a 3 Q 2 7B w en M 3 ag 0. is 6B tr al Sm al l

Rate (%)

Preprint. Under review.

Figure 4: Completion rates (%) in Gym w/o backtracking (left) and Gym w/ backtracking (right) for puzzles that were Finished (solid) or Deadlocked (hatched). solution patterns tied to a specific output format break when that format changes (Zhang et al., 2024). The effect (difference between baseline and Gym w/ backtracking) is strongest for GPT-OSS (−11.4%) and weaker but visible for OLMo (−6.6%).

4.3

al l

is tr

M ag

w en

til

G em

ro n

G PT -O

Steps / Path Edges

Backtracking behavior. We measure the 6 backtracking frequency as the ratio of the total number of steps to the final path length. On average, across models, 4 every third action is a backtrack (shown in Figure 12 in Appendix E.2). Figure 5 shows 2 the per-model distribution of this ratio. Backtracking usage correlates inversely with model accuracy. Magistral Small has the highest median ratio (∼2.2×), and GPTOSS 120B has the lowest (∼1.2×). Models benefiting from backtracking (Magistral Small, R1 Distill, Qwen 3 0.6B, Gemma 3 27B) backtrack heavily, while the four stagnating or collapsing (GPT-OSS, OLMo, Figure 5: Backtracking ratio (steps/path edges) per model in Spatial-Gym. Lines Nemotron, Qwen 3 32B) barely do. show median, boxes show IQR, and whiskers Models that performed worse in Section 4.1 extend to 1.5× IQR. stumble through heavy backtracking but occasionally find correct solutions they would otherwise miss. Stronger models, which could benefit most from targeted error correction, rarely backtrack. This likely reflects training incentives, as RLHF and instruction tuning reward confident responses and penalize selfcorrection (Schulman et al., 2017b), producing agents that commit to initial decisions even when revision is available. Qin et al. (2025) observe a similar pattern. Backtracking affects models differently. Weaker models (see Figure 2) improve their completion rate through exploration, while stronger models rarely question initial decisions. Path Generation Effort

In the baseline evaluation of Kaesberg et al. (2025b), humans spent up to 13× longer on hard puzzles than easy ones, while models barely increased their reasoning effort as measured by token usage. The Spatial-Gym environment makes reasoning efforts observable through path length and step count, in addition to token usage. Figure 6 compares path length against difficulty across four settings. (a) Ground-truth solutions show a clear upward trend, as harder puzzles require longer paths. (b) For the baseline, this upward trend is visible but markedly weaker, with much shorter paths at greater difficulties. (c) In Spatial-Gym, path lengths compress and barely increase with difficulty, and (d) with backtracking, paths become even shorter, as models use backtracking for pruning rather than to explore alternative routes, the opposite of the intended effect. We 6

Preprint. Under review.

Path Length

(a) True Solution

(b) Baseline

50 40 30 20 10 0 0

Difficulty Score

Figure 6: Path length (in edges) per difficulty score (0–5) for: (a) ground-truth solutions, (b) baseline, (c) Spatial-Gym w/o backtracking, and (d) Spatial-Gym w/ backtracking. Each point represents a single puzzle attempt; the solid line shows the per-difficulty mean. observe that models scale their reasoning tokens up to 5x in the Spatial-Gym over baseline and up to 10x when backtracking is enabled (for details, see Appendix E.9). We observe no correlation between token usage and path length, which shows an inconsistency between reasoning effort and solution quality. Spatial-Gym forces models to produce more tokens, and this output scales with difficulty. However, the additional reasoning does not translate into longer or more rule-compliant paths. Models spend tokens navigating toward shorter paths rather than toward paths that satisfy more constraints, consistent with Snell et al. (2024), who show that more tokens improve performance only when the computation targets the task objective (see Appendix E.8, Figure 18 for the tokenaccuracy mapping). We return to this in later experiments (cf. Section 4.5), where the A* baseline explains why path shortening helps some models but hurts others. Beyond path lengths and token usage, we track overall accuracy scaling across the five difficulty levels. While the Gym settings yield smoother scaling curves than the one-shot baseline, accuracy universally converges near zero at the highest difficulty levels. This demonstrates a rigid capability limit across all current models, regardless of the interaction format (see Appendix E.7 for difficulty-scaling curves). 4.4

Rule-Type Analysis

Rule types differ in difficulty, with Gaps being the easiest and Ylops the hardest. We compute solve rates per rule type across all three settings. Figure 7 shows the average across all models.

Polyomino

Square

Spatial-Gym generally helps models improve in all rule types, particularly for Gaps (+2.6%) and Ylops (+2.3%). For some rule types, there is no performance difference between baseline and Gym (e.g., Triangles, Dots). Backtracking has almost no additional advantage. It helps models reach the end node (Section 4.2), but does not improve any particular constraint type.

Gap

Star

Dot

Triangle

Ylop

Baseline Gym w/o backtracking Gym w/ backtracking

Some improvements are expected as SpatialGym eliminates path errors (e.g., Gap rule improvement of 2.6% over baseline). Figure 7: Rule-specific accuracy (%) across Improvements in Ylops of 2.3% are all rule types averaged over all models under interesting because Ylops require shape each of the three evaluation settings. subtraction across path-created regions, making them the most complex rule type. In the one-shot setting, models must simultaneously construct a valid path and reason about shape subtraction. In the Gym setting, this process is iterative, plus models do not need to spend thinking tokens on formatting, freeing capacity for the constraint itself. The Ylop improvement is a concrete 7

Preprint. Under review.

Baselines

20 10

Navigation Outcome LLMs

16.0%

6.4% 2.7%

2.4%

Finished

Rate (%)

Accuracy (%)

Accuracy

75 100%

50 25

0 A*

Qwen 3 0.6B

GPT-OSS 120B

Random

85% 43%

31%

0 Random

Deadlocked

100

Qwen 3 0.6B

GPT-OSS 120B

Figure 8: Accuracy (%) and completion rate (%) for random walk, A*, Qwen 3 0.6B, and GPT-OSS 120B in Spatial-Gym. We separate puzzles into Finished and Deadlocked. instance of the tradeoff between formatting and reasoning from Section 4.1. These effects are averaged, and model-specific rule type effects exist, which we provide in Appendix E.1. 4.5

Algorithmic Baselines

Models struggle with navigation and constraint satisfaction, so we compare them against two algorithmic baselines: a random walk (uniform random choice of valid actions) and an A* agent (shortest path from start to end). The random walk is a lower bound; A* is the ceiling for pure navigation around gaps without rule understanding. We compare both to the smallest (Qwen 3 0.6B) and largest (GPT-OSS 120B) models. Figure 8 shows accuracy and completion for the four methods. The random walk solves 2.4% of puzzles and completes navigation in 31% of cases. A* solves 6.4% with 100% completion, showing that pathfinding is not the bottleneck in Spatial-Gym, but constraint satisfaction. GPT-OSS 120B outperforms A* on accuracy (16.0% vs. 6.4%) but falls short on navigation (85% vs. 100%), indicating that LLMs bring rule comprehension that A* lacks at the cost of navigation reliability. Qwen 3 0.6B solves 2.7% (43% completion), marginally above random. The A* baseline also explains the backtracking results from Section 4.2. With backtracking enabled, models optimize toward shorter paths (as seen in Figure 4), similar to how A* finds the shortest path. This pulls models toward A*’s accuracy level from both directions. Models below 6.4% improve (shorter paths align with A*), while above 6.4% they lose accuracy (needed detours are removed), explaining why backtracking helps weaker models but hurts stronger ones. 4.6

Vision Accuracy (%)

Previous work found that multimodal 15 prompting did not improve performance 10.6% 10.2% compared to text inputs for one-shot visual 10 puzzles Kaesberg et al. (2025b). We test whether vision-language models can benefit from 5 2.8% visual input in the Gym setting. We compare three conditions within the Qwen 3 family: 0 Qwen3-32B text-only model with text input, Qwen3 Qwen3 Qwen3 Qwen3-VL-32B with text input only, and 32B VL-32B VL-32B (Text) (Text) (Vision) Qwen3-VL-32B with text and rendered puzzle images. We use the same puzzle renders shown Figure 9: Vision vs. text input for the to human participants. Qwen3 family. Accuracy (%) for Qwen332B, Qwen3-VL-32B with text input, and Figure 9 shows the accuracy across these three Qwen3-VL-32B with puzzle images. conditions. Qwen3-32B (text) and Qwen3-VL32B (text) perform comparably at 10.6% and 10.2%, showing that the vision backbone alone has no impact on text-based spatial reasoning. Qwen3-VL-32B with vision input collapses to 2.8%. The performance drop is strongest on easier puzzles, where text-based models perform best (Figure 13 in Appendix E.3 provides a per-difficulty breakdown). 8

Preprint. Under review.

The vision results presented here are consistent with Park et al. (2025), who find that visionlanguage models perform notably worse on abstract reasoning tasks when relying on visual inputs compared to equivalent text representations. When both modalities are provided, the model cannot connect them well and has particular issues indexing the grid system. Model Scaling

We evaluate four Qwen 3 model sizes (0.6B, 4B, 14B, 32B) to test whether spatial reasoning scales with model size and whether the two formats produce different scaling trajectories.

12.5

Accuracy (%)

4.7

10.0

Baseline Gym

7.5

5.0 Figure 10 shows the results for the baseline and Spatial-Gym tasks. With the Gym 2.5 setting, accuracy increases monotonically from 2.6% at 0.6B to 10.6% at 32B. Under the 0.0 baseline setting, accuracy rises from 0.6B to 104 105 106 14B, peaking at 12.6%, but the 32B model Estimated Compute (FLOPs) drops to 5.2%, falling below the 4B model. This inversion is specific to the Qwen 3 Figure 10: Accuracy (%) and estimated family. Other 32B models (OLMo 3.1 at compute (FLOPs, log scale) for four Qwen 3 16.2%) and larger models (GPT-OSS 120B at model sizes (0.6B, 4B, 14B, 32B) for the 21.6%) perform well on the baseline setting. baseline and Spatial-Gym. The Qwen 3 32B model likely produces more formatting errors in the one-shot setting, inflating its failure rate. The Gym curve does not show such an artifact. The 32B model improves over the 14B model’s result. Models are restricted in the Gym setting to choose only among valid moves at each step, rather than constructing a full path; formatting errors are not permitted, and the scaling curve becomes monotonic, reflecting the model’s actual spatial capability. At the same time, the persistently low absolute performance indicates that model scaling alone is insufficient to solve the task. We also analyze the behavior of reasoning versus non-reasoning models using Qwen 3 (14B and 32B), finding that extended chain-of-thought retains a 3 − 5× accuracy advantage (e.g., 10.6% vs. 2.2% for 32B) and notably higher completion rates (60-68% vs. 39-45%) in the Gym setting (details in Appendix E.4). Motivated by this, we additionally conduct preliminary reinforcement learning experiments, reported in Appendix F.

Conclusion

We introduced Spatial-Gym, a Gymnasium-based sequential decision environment for 2D grid pathfinding with interacting rule constraints and optional backtracking. This sequential decision-making mirrors how humans solve such tasks step-by-step with the ability to backtrack, and addresses the gap in spatial reasoning evaluation by isolating constraint reasoning from output formatting. We evaluated eight models across three settings (baseline, Gym, Gym+backtracking) against human, random, and A* baselines on 500 puzzles. The best model, GPT-OSS 120B, achieves 16.0% accuracy in the Gym setting, 82 points below the human baseline (98.0%), indicating significant room for improvement in spatial reasoning. Our results show that the Gym format helps weaker models (up to +5.4%) by eliminating formatting errors but hurts stronger models (up to −5.6%) by limiting global planning. Backtracking improves navigation completion universally but only increases accuracy for weaker models that use it heavily, while stronger models rarely backtrack and lose further. Models also fail to scale reasoning effort with difficulty, as path lengths remain compressed in the Gym setting and backtracking is used to shorten paths rather than explore alternatives. Algorithmic baselines such as A* show that navigation is largely solved, while constraint satisfaction remains the primary bottleneck in the task. Spatial-Gym enables RL-based training approaches to directly target the spatial reasoning gap that architecture, scale, and prompting have not closed. 9

Preprint. Under review.

Acknowledgments

This work was partially supported by the Lower Saxony Ministry of Science and Culture and the VW Foundation. Many thanks to Tobias Mark for his thoughtful discussions and feedback. This work used the Scientific Compute Cluster at GWDG, the joint data center of Max Planck Society for the Advancement of Science (MPG) and University of Göttingen. In part funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 405797229.

References Zachary Abel, Jeffrey Bosboom, Michael Coulombe, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy, and Clemens Thielen. Who witnesses the witness? finding witnesses in the witness is hard and sometimes impossible. ArXiv preprint, abs/1804.10193, 2018. URL https://arxiv.org/abs/1804. 10193. Mohamed Aghzal, Erion Plaku, and Ziyu Yao. Can large language models be good path planners? a benchmark and investigation on spatial-temporal reasoning. ArXiv preprint, abs/2310.03249, 2023. URL https://arxiv.org/abs/2310.03249. Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Julian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kanishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, Mengyuan Yan, and Andy Zeng. Do as i can, not as i say: Grounding language in robotic affordances. ArXiv preprint, abs/2204.01691, 2022. URL https://arxiv.org/abs/2204.01691. Jonas Becker, Lars Benedikt Kaesberg, Niklas Bauer, Jan Philip Wahle, Terry Ruas, and Bela Gipp. MALLM: Multi-agent large language models framework. In Ivan Habernal, Peter Schulam, and Jörg Tiedemann (eds.), Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 418–439, Suzhou, China, 2025. Association for Computational Linguistics. ISBN 979-8-89176-334-0. doi: 10.18653/v1/ 2025.emnlp-demos.29. URL https://aclanthology.org/2025.emnlp-demos.29/. Jonathan Blow. The witness, 2016. URL https://en.wikipedia.org/wiki/The Witness (2016 video game). [Online; accessed 15-May-2025]. Dingyang Chen, Qi Zhang, and Yinglun Zhu. Efficient sequential decision making with large language models. ArXiv preprint, abs/2406.12125, 2024. URL https://arxiv.org/ abs/2406.12125. Francois Chollet, Mike Knoop, Gregory Kamradt, and Bryan Landers. Arc prize 2024: Technical report. ArXiv preprint, abs/2412.04604, 2024. URL https://arxiv.org/abs/ 2412.04604. François Chollet. On the measure of intelligence. ArXiv preprint, abs/1911.01547, 2019. URL https://arxiv.org/abs/1911.01547. Alan Dao and Dinh Bach Vu. Alphamaze: Enhancing large language models’ spatial intelligence via grpo. ArXiv preprint, abs/2502.14669, 2025. URL https://arxiv.org/abs/ 2502.14669. DeepSeek-AI et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. ArXiv preprint, abs/2501.12948, 2025. URL https://arxiv.org/abs/2501.12948. ARC Prize Foundation. Arc-agi-3: A new challenge for frontier agentic intelligence. ArXiv preprint, abs/2603.24621, 2026. URL https://arxiv.org/abs/2603.24621. 10

Preprint. Under review.

Ine Gevers and Walter Daelemans. Do you get the hint? benchmarking llms on the board game concept. ArXiv preprint, abs/2510.13271, 2025. URL https://arxiv.org/abs/2510. 13271. Lars Kaesberg, Terry Ruas, Jan Philip Wahle, and Bela Gipp. CiteAssist: A system for automated preprint citation and BibTeX generation. In Tirthankar Ghosal, Amanpreet Singh, Anita Waard, Philipp Mayr, Aakanksha Naik, Orion Weller, Yoonjoo Lee, Shannon Shen, and Yanxia Qin (eds.), Proceedings of the Fourth Workshop on Scholarly Document Processing (SDP 2024), pp. 105–119, Bangkok, Thailand, 08 2024. Association for Computational Linguistics. URL https://aclanthology.org/2024.sdp-1.10/. Lars Benedikt Kaesberg, Jonas Becker, Jan Philip Wahle, Terry Ruas, and Bela Gipp. Voting or consensus? decision-making in multi-agent debate. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Findings of the Association for Computational Linguistics: ACL 2025, pp. 11640–11671, Vienna, Austria, 2025a. Association for Computational Linguistics. ISBN 979-8-89176-256-5. doi: 10.18653/ v1/2025.findings-acl.606. URL https://aclanthology.org/2025.findings-acl.606/. Lars Benedikt Kaesberg, Jan Philip Wahle, Terry Ruas, and Bela Gipp. SPaRC: A spatial pathfinding reasoning challenge. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng (eds.), Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 10370–10401, Suzhou, China, 2025b. Association for Computational Linguistics. ISBN 979-8-89176-332-6. doi: 10.18653/v1/2025.emnlp-main. 526. URL https://aclanthology.org/2025.emnlp-main.526/. Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. Llms can’t plan, but can help planning in llm-modulo frameworks. ArXiv preprint, abs/2402.01817, 2024. URL https://arxiv.org/abs/2402.01817. Michael Katz, Harsha Kokel, and Sarath Sreedharan. Seemingly simple planning problems are computationally challenging: The countdown game. ArXiv preprint, abs/2508.02900, 2025. URL https://arxiv.org/abs/2508.02900. Doyoung Kim, Jongwon Lee, Jinho Park, and Minjoon Seo. How language models extrapolate outside the training data: A case study in textualized gridworld. ArXiv preprint, abs/2406.15275, 2024. URL https://arxiv.org/abs/2406.15275. Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal, Radha Poovendran, Peter Clark, and Yejin Choi. Zebralogic: On the scaling limits of llms for logical reasoning. ArXiv preprint, abs/2502.01100, 2025. URL https://arxiv.org/abs/2502.01100. Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Sheng Shen, Tianjun Zhang, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. Agentbench: Evaluating llms as agents. ArXiv preprint, abs/2308.03688, 2023. URL https://arxiv.org/abs/2308.03688. Roshanak Mirzaee, Hossein Rajaby Faghihi, Qiang Ning, and Parisa Kordjamshidi. SPARTQA: A textual question answering benchmark for spatial reasoning. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4582–4598, Online, 2021. Association for Computational Linguistics. doi: 10.18653/v1/2021.naacl-main.364. URL https: //aclanthology.org/2021.naacl-main.364. Mistral-AI et al. Magistral. ArXiv preprint, abs/2506.10910, 2025. URL https://arxiv.org/ abs/2506.10910. Chinmay Mittal, Krishna Kartik, Mausam, and Parag Singla. Fcorebench: Can large language models solve challenging first-order combinatorial reasoning problems? ArXiv preprint, abs/2402.02611, 2024. URL https://arxiv.org/abs/2402.02611. 11

Preprint. Under review.

NVIDIA et al. Nvidia nemotron 3: Efficient and open intelligence. abs/2512.20856, 2025. URL https://arxiv.org/abs/2512.20856.

ArXiv preprint,

Team Olmo et al. Olmo 3. ArXiv preprint, abs/2512.13961, 2025. URL https://arxiv.org/ abs/2512.13961. OpenAI et al. gpt-oss-120b & gpt-oss-20b model card. ArXiv preprint, abs/2508.10925, 2025. URL https://arxiv.org/abs/2508.10925. Simon Park, Abhishek Panigrahi, Yun Cheng, Dingli Yu, Anirudh Goyal, and Sanjeev Arora. Generalizing from simple to hard visual reasoning: Can we mitigate modality imbalance in vlms? ArXiv preprint, abs/2501.02669, 2025. URL https://arxiv.org/abs/2501.02669. Rohan Poudel, Pollob Mollick Raza, Anand Patwa, Gungun Kumari, Akash Shah, and Sharik Ahmad. Exploring the performance of large language models in novel commandbased tasks. Franklin Open, 14:100447, 2026. ISSN 2773-1863. doi: https://doi.org/ 10.1016/j.fraope.2025.100447. URL https://www.sciencedirect.com/science/article/ pii/S2773186325002324. Tian Qin, David Alvarez-Melis, Samy Jelassi, and Eran Malach. To backtrack or not to backtrack: When sequential search limits model reasoning. ArXiv preprint, abs/2504.07052, 2025. URL https://arxiv.org/abs/2504.07052. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv preprint, abs/1707.06347, 2017a. URL https: //arxiv.org/abs/1707.06347. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv preprint, abs/1707.06347, 2017b. URL https: //arxiv.org/abs/1707.06347. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, Y. K. Li, Y. Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. ArXiv preprint, abs/2402.03300, 2024. URL https://arxiv.org/abs/2402.03300. Jiajun Shi, Jian Yang, Jiaheng Liu, Xingyuan Bu, Jiangjie Chen, Junting Zhou, Kaijing Ma, Zhoufutu Wen, Bingli Wang, Yancheng He, Liang Song, Hualei Zhu, Shilong Li, Xingjian Wang, Wei Zhang, Ruibin Yuan, Yifan Yao, Wenjun Yang, Yunli Wang, Siyuan Fang, Siyu Yuan, Qianyu He, Xiangru Tang, Yingshui Tan, Wangchunshu Zhou, Zhaoxiang Zhang, Zhoujun Li, Wenhao Huang, and Ge Zhang. Korgym: A dynamic game platform for llm reasoning evaluation. ArXiv preprint, abs/2505.14552, 2025. URL https://arxiv.org/ abs/2505.14552. Zhengxiang Shi, Qiang Zhang, and Aldo Lipani. Stepgame: A new benchmark for robust multi-hop spatial reasoning in texts. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pp. 11321–11329. AAAI Press, 2022. URL https://ojs.aaai.org/index.php/AAAI/article/view/21383. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling llm test-time compute optimally can be more effective than scaling model parameters. ArXiv preprint, abs/2408.03314, 2024. URL https://arxiv.org/abs/2408.03314. Chan Hee Song, Jiaman Wu, Clayton Washington, Brian M. Sadler, Wei-Lun Chao, and Yu Su. Llm-planner: Few-shot grounded planning for embodied agents with large language models. ArXiv preprint, abs/2212.04088, 2022. URL https://arxiv.org/abs/2212.04088. Yueqi Song, Tianyue Ou, Yibo Kong, Zecheng Li, Graham Neubig, and Xiang Yue. Visualpuzzles: Decoupling multimodal reasoning evaluation from domain knowledge. ArXiv preprint, abs/2504.10342, 2025. URL https://arxiv.org/abs/2504.10342. 12

Preprint. Under review.

Zayne Sprague, Fangcong Yin, Juan Diego Rodriguez, Dongwei Jiang, Manya Wadhwa, Prasann Singhal, Xinyu Zhao, Xi Ye, Kyle Mahowald, and Greg Durrett. To cot or not to cot? chain-of-thought helps mainly on math and symbolic reasoning. ArXiv preprint, abs/2409.12183, 2024. URL https://arxiv.org/abs/2409.12183. Zafir Stojanovski, Oliver Stanley, Joe Sharratt, Richard Jones, Abdulhakeem Adefioye, Jean Kaddour, and Andreas Köpf. Reasoning gym: Reasoning environments for reinforcement learning with verifiable rewards. ArXiv preprint, abs/2505.24760, 2025. URL https: //arxiv.org/abs/2505.24760. Gemma Team et al. Gemma 3 technical report. ArXiv preprint, abs/2503.19786, 2025. URL https://arxiv.org/abs/2503.19786. Qwen Team. Qwen2.5: A party of foundation models, 2024. URL https://qwenlm.github. io/blog/qwen2.5/. Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo PerezVicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G. Younis. Gymnasium: A standard interface for reinforcement learning environments. ArXiv preprint, abs/2407.17032, 2024. URL https://arxiv.org/abs/2407.17032. David Uttal, Nathaniel Meadow, Elizabeth Tipton, Linda Liu Hand, Alison Alden, Christopher Warren, and Nora Newcombe. The malleability of spatial skills: A metaanalysis of training studies. Psychological Bulletin, 139:352–402, 2012. doi: 10.1037/ a0028446. J. Wahle, T. Ruas, S. M. Mohammad, N. Meuschke, and B. Gipp. Ai usage cards: Responsibly reporting ai-generated content. In 2023 ACM/IEEE Joint Conference on Digital Libraries (JCDL), pp. 282–284, Los Alamitos, CA, USA, jun 2023. IEEE Computer Society. doi: 10.1109/JCDL57899.2023.00060. URL https://doi.ieeecomputersociety.org/10.1109/ JCDL57899.2023.00060. Zihan Wang, Kangrui Wang, Qineng Wang, Pingyue Zhang, Linjie Li, Zhengyuan Yang, Xing Jin, Kefan Yu, Minh Nhat Nguyen, Licheng Liu, Eli Gottlieb, Yiping Lu, Kyunghyun Cho, Jiajun Wu, Li Fei-Fei, Lijuan Wang, Yejin Choi, and Manling Li. Ragen: Understanding self-evolution in llm agents via multi-turn reinforcement learning. ArXiv preprint, abs/2504.20073, 2025. URL https://arxiv.org/abs/2504.20073. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022. URL http://papers.nips.cc/paper files/ paper/2022/hash/9d5609613524ecf4f15af0f7b31abca4-Abstract-Conference.html. Jason Weston, Antoine Bordes, Sumit Chopra, and Tomás Mikolov. Towards ai-complete question answering: A set of prerequisite toy tasks. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http://arxiv.org/abs/1502. 05698. An Yang et al. Qwen3 technical report. ArXiv preprint, abs/2505.09388, 2025. URL https: //arxiv.org/abs/2505.09388. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The eleventh international conference on learning representations, 2022. Giacomo Zamprogno, Emmanuelle Dietz, Linda Heimisch, and Nele Russwinkel. A hybrid computational approach to anticipate individuals in sequential problem solving. Frontiers in Artificial Intelligence, 6, 2023. URL https://api.semanticscholar.org/CorpusID: 266443362. 13

Preprint. Under review.

Hugh Zhang, Jeff Da, Dean Lee, Vaughn Robinson, Catherine Wu, Will Song, Tiffany Zhao, Pranav Raja, Charlotte Zhuang, Dylan Slack, Qin Lyu, Sean Hendryx, Russell Kaplan, Michele Lunati, and Summer Yue. A careful examination of large language model performance on grade school arithmetic. ArXiv preprint, abs/2405.00332, 2024. URL https://arxiv.org/abs/2405.00332. Kangjie Zhou, Yao Mu, Haoyang Song, Yi Zeng, Pengying Wu, Han Gao, and Chang Liu. Ainav: Large language model-based adaptive interactive navigation. IEEE Robotics and Automation Magazine, pp. 2–17, 2025. ISSN 1558-223X. doi: 10.1109/mra.2025.3639793. URL http://dx.doi.org/10.1109/MRA.2025.3639793. Shuyan Zhou, Frank F. Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, Uri Alon, and Graham Neubig. Webarena: A realistic web environment for building autonomous agents. ArXiv preprint, abs/2307.13854, 2023. URL https://arxiv.org/abs/2307.13854.

Models & Hardware

Hardware All model inference and evaluation procedures for the baseline and SpatialGym settings were performed on a uniform hardware configuration. Specifically, we used 4 NVIDIA A100 GPUs, each equipped with 80GB of VRAM. This provided sufficient memory and compute capacity to run all models in a non-quantized mode in our evaluation suite. Evaluated Models We evaluate eight models spanning different sizes, architectures, and training paradigms to assess their spatial reasoning capabilities. The following models were selected for our primary experiments: •

GPT-OSS 120B: An open-weight, 117B-parameter Mixture-of-Experts (MoE) reasoning model optimized for agentic workflows and high-reasoning tasks OpenAI et al. (2025). • OLMo 3.1 32B: An open-science language model developed by the Allen Institute for AI, fine-tuned specifically for complex reasoning and multi-step logic Olmo et al. (2025). • Nemotron 49B: A highly efficient reasoning derivative (Llama-3.3-NemotronSuper-49B) developed through Neural Architecture Search NVIDIA et al. (2025). • Qwen 3 (32B & 0.6B): Part of Alibaba Cloud’s latest model generation featuring native dual thinking and non-thinking modes Yang et al. (2025). Additional variants from this family, including Qwen 3 14B, Qwen 3 4B, and the vision-language model Qwen3-VL-32B, were used specifically for our scaling and vision ablations. • R1 Distill 32B: DeepSeek-R1-Distill-Qwen-32B, a dense model distilled from the sophisticated reasoning traces of the larger DeepSeek-R1 teacher model DeepSeekAI et al. (2025). • Gemma 3 27B: Google’s multimodal vision-language model, built on Gemini technology and designed for long-context reasoning Team et al. (2025). • Magistral Small 24B: A 24-billion parameter reasoning model developed by Mistral AI, fine-tuned for multi-step logic and transparent reasoning traces MistralAI et al. (2025).

Prompts

This section lists the system prompts used across the three evaluation settings. All prompts share the same rule definitions and symbol legend; they differ in the instructions for backtracking and input modality. The user message at each step contains the current observation (grid state, position, legal actions) and is generated dynamically by the environment. For the visual setting, the user message additionally includes a rendered image of the current puzzle state. 14

Preprint. Under review.

B.1

Observation Format

At each step, the environment generates a user message containing the step number, the agent’s current coordinates, the set of legal actions, and the grid state. The grid encodes the agent’s path progress using the symbol legend from the system prompt (V for visited nodes, L for the current position). The model must end its response with Final: <action>, where <action> is one of the four cardinal directions. The text-based settings (Spatial-Gym and Spatial-Gym with backtracking) use the template below; the visual setting replaces the grid state with a rendered puzzle image while retaining the position and legal-action text. User message template. Step: {step} Current Position: ({x}, {y}) Legal Actions: [{digit=DIRECTION, ...}] Grid State: {observation grid} You MAY think step-by-step, but you MUST end your response with: Final: <action> Where <action> is one of 0=RIGHT, 1=UP, 2=LEFT, 3=DOWN (you may also write the direction name, e.g. Final: right).

Example observation (step 1). The following shows the first observation for a difficulty-5 puzzle with a 3×2 grid containing a polyshape, two blue squares, and a dot. The agent starts at position (0, 1), marked L. Step: 1 Current Position: (0, 1) Legal Actions: [1=UP,3=DOWN] Grid State: ['+', '+', '+', '+', '+', '.', '+'] ['L', 'N', '+', 'P-R-16', '+', 'o-B', '+'] ['+', '+', '+', '+', '+', '+', '+'] ['+', 'N', '+', 'N', '+', 'o-B', '+'] ['+', '+', 'E', '+', '+', '+', '+'] You MAY think step-by-step, but you MUST end your response with: Final: <action> Where <action> is one of 0=RIGHT, 1=UP, 2=LEFT, 3=DOWN (you may also write the direction name, e.g. Final: right).

B.2

Spatial-Gym (Step-by-Step without backtracking)

You are an autonomous agent controlling a path-finding puzzle solver. Your goal is to find a valid path (a continuous line) from the specified Start Node to the End Node on the provided grid, adhering to all puzzle rules. Core Concepts & Grid Basics: Grid Dimensions: You can find the puzzle grid size in the info Path: The solution is a single, continuous line connecting adjacent nodes either horizontally or vertically. Revisiting: You can not traceback your path. You can not visit a cell twice. Rule Cells: Cells containing rule symbols (squares, stars, etc.) have coordinates where both x and y are odd. The path goes around these rule cells, never on them. They are also marked as gaps. Regions: The drawn path divides the grid cells into one or more distinct enclosed areas (regions). Many rules apply based on the contents of these regions. Valid Path Cells: The path travels along the grid lines (edges between nodes). It can only occupy positions marked '+' or '.' in the grid layout (these correspond to positions with at least one even coordinate). Symbol Legend (Grid Notation) S: Start Node (Path begins here) E: End Node (Path ends here) V: Visited Node (Path has passed through this cell)

Preprint. Under review.

L: Current Node (Path is currently on this cell) +: Valid cell for the path to occupy N: Empty rule cell (no rule) G: Gap (Path CANNOT cross this cell) .: Dot (Path MUST pass through this cell) o-X: Square of color X *-X: Star of color X A-X: Triangle (touch 1 edge) B-X: Triangle (touch 2 edges) C-X: Triangle (touch 3 edges) D-X: Triangle (touch 4 edges) P-X-Y: Polyshape (positive) of color X and shape ID Y Y-X-Y: Negative Polyshape (ylop) of color X and shape ID Y Color Codes: R=Red, B=Blue, G=Green, Y=Yellow, W=White, O=Orange, P=Purple, K=Black Detailed Solving Rules: The drawn path must satisfy ALL applicable constraints: 1. Path Constraints: Path connects adjacent nodes (horizontal/vertical moves only). Nodes CAN NOT be revisited. You cannot visit a cell twice. Path MUST pass through all Dot cells. Path CANNOT pass through any Gap cells. 2. Region-Based Rules (Apply to areas enclosed by the path): Squares: All squares within a single region MUST be the same color. Squares of different colors MUST be separated into different regions by the path. Stars: Within a single region, each star symbol MUST be paired with exactly ONE other element of the same color. Other colors within the region are irrelevant to this specific star's rule. Polyshapes (poly): The region containing this symbol MUST be able to contain the specified shape (defined in Polyshape Definitions). The shape must fit entirely within the region's boundaries. If multiple positive polyshapes are in one region, the region must accommodate their combined, non-overlapping forms. Rotation of polyshapes is NOT allowed. They must fit within the provided space in their given orientation. Negative Polyshapes (ylop): These subtract shape requirements, typically within the same region as corresponding positive polyshapes. A negative polyshape cancels out a positive polyshape of the exact same shape and color within that region. If all positive shapes are canceled, the region has no shape constraint. 3. Path-Based Rules (Edge Touching): Triangles: The path MUST touch a specific number of edges of the cell containing the triangle symbol. (1): Path touches EXACTLY 1 edge of the triangle's cell. (2): Path touches EXACTLY 2 edges of the triangle's cell. (3): Path touches EXACTLY 3 edges of the triangle's cell. (4): Path touches EXACTLY 4 edges (fully surrounds) the cell. Polyshape Definitions: Shapes are defined by 2D arrays where 1 indicates an occupied cell and 0 indicates an empty cell. {polyshapes} At each turn you'll receive the current state: - Step: The current step number - Current Position: Your current (x, y) location - Legal Actions: Available moves with format [digit=DIRECTION, ...] - Grid State: The current grid showing your path progress

B.3

Spatial-Gym with backtracking

The backtracking prompt is identical to the standard Gym prompt (Appendix B.2) except for the revisiting policy and the corresponding path constraint. All other sections (symbol legend, solving rules, polyshape definitions, observation format) remain unchanged. Below we list only the two segments that differ. Core Concepts (Revisiting). Revisiting: You can traceback your path, but you MUST do so in the same way you came, without crossing over your own path. When tracing back, you can only move to the last cell you occupied, and then continue from

Preprint. Under review.

there. Also when you traceback, the nodes you no longer use in your path are free to be used again.

Path Constraints. 1. Path Constraints: Path connects adjacent nodes (horizontal/vertical moves only). Nodes CAN be revisited. But only if you traceback to the last cell you occupied (and from there again and again ...). Otherwise you CANNOT cross your own path. Path MUST pass through all Dot cells. Path CANNOT pass through any Gap cells.

B.4

Spatial-Gym Visual

The visual prompt replaces the text-based grid representation with a rendered image of the puzzle state at each step. The model receives both the image and a text message containing coordinates and legal actions. The system prompt describes the visual appearance of all puzzle elements so the model can ground symbols in the image. You are an autonomous agent controlling a path-finding puzzle solver. Your goal is to find a valid path (a continuous line) from the specified Start Node to the End Node on the provided grid, adhering to all puzzle rules. ## Input Format At each step you receive TWO inputs: 1. An image of the puzzle showing the current state, including your path progress 2. A text message with your current position coordinates and available legal moves Use both together -- the image helps with spatial reasoning and visual pattern recognition, while the text provides precise position and action information. ## Visual Appearance of the Puzzle Image The image shows a Witness puzzle grid with a dark teal/green background. Here is how elements appear visually: Board structure: - Teal/green cells separated by dark gray grid lines (the path network) Navigation markers: - Start Node: A large filled circle on the grid edge -- this is where the path begins - End Node: A small rounded nub/extension protruding outward from the grid edge -- this is where you must reach - Visited Path: Marked with a WHITE LINE showing where you have already traveled - Current Position: Located at the END of the white line (where the line stops) Rule symbols in cells (located in cells where both x and y are odd -the path goes AROUND these cells, not through them): - Colored Squares: Colored rounded rectangles inside cells (e.g., black, red, blue) - Colored Stars: 8-pointed star shapes in their respective color - Triangles: Small colored upward-pointing triangles inside cells -- the count (1-4 triangles) indicates how many edges of that cell the path must touch - Polyshapes (positive): Tetromino-like colored filled block patterns inside cells, showing the shape the region must match - Polyshapes (negative/ylop): Same block patterns but drawn as hollow/outlined squares instead of filled -- these cancel out positive polyshapes Path elements (located on grid lines): - Dots: Small black hexagons on the grid lines -- the path MUST pass through these - Gaps: Broken/missing segments on the grid lines -- the path CANNOT cross these ## Coordinate System

Preprint. Under review.

- Nodes are indexed (x, y) where (0,0) is the top-left node - x increases to the right, y increases downward - The path travels along grid edges, connecting adjacent nodes horizontally or vertically ## Solving Rules 1. Draw a continuous line from START to END without visiting the same node twice 2. The line can only be placed on valid path cells (not on rule cells) 3. The line acts as a boundary, dividing the grid into regions 4. All rule symbols must be satisfied: - Dots (black hexagons on grid lines): The line MUST pass through each dot - Colored Squares (filled rounded rectangles in cells): All squares in a single region must be the same color. Different colors MUST be separated into different regions - Colored Stars (8-pointed stars in cells): Each star must be paired with EXACTLY one other element of the same color in its region - Triangles (small triangles in cells): The line must touch EXACTLY the number of edges specified by the triangle count (1-4 edges) - Polyshapes (filled block patterns in cells): The region must be shaped exactly like the defined polyshape - Negative Polyshapes (hollow block patterns in cells): Cancel out regular polyshapes if they overlap {polyshapes} ## Actions You can move in 4 directions: - 0: Move UP - 1: Move RIGHT - 2: Move DOWN - 3: Move LEFT ## Important - You CANNOT revisit cells you have already visited - You CANNOT cross your own path - Plan ahead to satisfy all constraints ## How to Respond Analyze the puzzle image showing your current position and path progress, together with the text information about your coordinates and legal moves. Determine which direction leads toward the exit while satisfying all puzzle rules.

SPaRC Dataset

SPaRC (Kaesberg et al., 2025b) consists of 1,000 2D grid pathfinding puzzles (500 train, 500 test) inspired by the puzzle mechanics of The Witness (Blow, 2016). Each puzzle is an m × n grid of rule cells with ( x, y) = (0, 0) at the top-left corner, x increasing rightward and y downward. Rule cells are surrounded by edges along which the solution path is drawn. Each puzzle has exactly one start point (large circle) and one end point (edge extension). The goal is to draw a single, continuous, non-self-intersecting path along edges from start to end that satisfies all rule cell constraints. C.1

Rules

Seven rule types can appear in SPaRC puzzles: Item Collection (Dots): The solution path needs to pass through every dot. Path Breaks (Gaps): The solution path cannot go through any edge segment containing a gap. Gaps act as local barriers. Color Separation (Stones): The solution path must be drawn to separate stones of different colors. All stones located within any single enclosed region must be of the same color. 18

Preprint. Under review.

Pairing (Stars): Each star must share its region with exactly one other symbol of the same color. No unpaired stars are allowed. Edge Count (Triangles): The solution path must touch the number of edges shown by the triangles in the cell, e.g., two triangles mean the path must touch exactly two edges of that cell. Shape Fitting (Polyominoes): If a cell contains a polyomino (poly), the solution path must enclose a region that matches its exact shape and area. The region must not rotate or mirror the poly. Multiple polys can share a region if their shapes fit without overlapping. Shape Subtraction (Ylop): A ylop must be enclosed in the same region as one or more polys. Its shape and area subtract from the total required by the polys. If a ylop cancels out a poly exactly, that pair imposes no constraint. C.2

Dataset Creation

Puzzles are generated by randomly creating an m × n grid (m, n ∈ [2, 6]), filling approximately half the cells with rules (rule density), and placing random start and end points. A generation-validation loop solves each puzzle via brute-force search over all valid paths.2 If no solution exists, rule density is decreased; if more than k =50 solutions exist, density is increased, and the puzzle is regenerated. Difficulty estimation. Puzzle complexity is quantified by a weighted sum of the number of distinct rule types, total rule cells, rule density, grid size, and estimated rule interactions, normalized to a 1 (easiest) to 5 (hardest) scale. The test set contains 86 puzzles at level 1, 118 at level 2, 121 at level 3, 86 at level 4, and 89 at level 5.

Example Gym Interaction

Puzzle ID Difficulty Difficulty Grid (H×W) Outcome

c2f1726c32030b96 GPT-OSS 120B 2 (score 1.22) 2×2 Solved

Step 1 of 5 Chosen action: Down Model reasoning We need to analyze puzzle. Grid is 5x5? Represented as rows lines. Coordinates? Current Position: [0 1] means x=0, y=1? Usually x column, y row. Starting at coordinate (0,1). Let’s map grid with coordinates (x from 0 left to 4, y from 0 top to 4). Grid rows given: Row0: [’+’, ’+’, ’+’, ’+’, ’+’] Row1: [’S’, ’*-Y’, ’+’, ’*-Y’, ’+’] Row2: [’+’, ’+’, ’+’, ’+’, ’+’] 2 Brute-force is necessary because many puzzles fall into NP or NP-Complete complexity classes (Abel et al., 2018).

Preprint. Under review.

Row3: [’+’, ’*-K’, ’+’, ’*-K’, ’+’] Row4: [’+’, ’+’, ’E’, ’+’, ’+’] Symbols: S at (0,1). E at (2,4). stars at (1,1) color Y, (3,1) Y, (1,3) K, (3,3) K. Current Position is [0 1] which matches S. Legal actions: up or down. Means cannot go left or right because maybe out of bounds? From (0,1), up goes to (0,0) which is ’+’. Down goes to (0,2) which is ’+’. Goal: Find a path to E covering all dot cells (none) and obey triangle (none) etc. Rule: cannot pass through rule cells (stars) since they are gaps? Stars are rule cells at odd coordinates (both odd). Indeed coordinates (1,1), (3,1), (1,3), (3,3) are rule cells; path cannot go through them. We need to find a path from S to E without crossing those star cells, cannot revisit, and must end at E (2,4). Also there may be region rules: squares none, triangles none, poly shapes none. Only stars: each star must be paired with exactly one other element of same color within its region. Stars of color Y at (1,1) and (3,1). Stars of color K at (1,3) and (3,3). They are each color with two stars; they need to be paired with exactly one other element of same color inside same region. The other element could be maybe another star? Actually "each star symbol MUST be paired with exactly ONE other element of the same color." Could be another star? Probably star pairs themselves count? Not sure. Usually in puzzles like ’Star Pairing’, each star must be paired with a dot of same color. But here maybe another element (could be dot, square, etc.). No other same color elements exist besides the stars themselves. So each star must be paired with the other star of same color, but they are separate stars. "Each star symbol must be paired with exactly ONE other element of the same color. Other colors within region are irrelevant." So if there are two Y stars in same region, they could pair with each other; each star paired exactly one other element (the other star). That satisfies rule if they are in same region. But if they are separated by path into different regions, they’d each lack a partner. So we need to ensure that stars of same color are in same region. So the path must not separate Y stars from each other, same for K stars. Thus we need to draw path from S to E that encloses a region containing both Y stars together, and another region containing both K stars together, or maybe they can be in same region as each other? But if Y star paired with K star? No, must be same color, so not. Simplify: we can make a path that goes around all four star cells maybe creating a region that contains them all together (both colors). That would put Y stars with K stars together, but each Y star still has partner? It could be the other Y star in same region (still there). So okay. But path cannot go through them, can go on surrounding ’+’ cells. We need to find any path from S (0,1) to E (2,4) that doesn’t cross star cells and doesn’t revisit. Let’s attempt to design moves. Grid visualize with coordinates (x,y): (0,0) + ; (1,0)+ ; (2,0)+ ; (3,0)+ ; (4,0)+ (0,1) S ; (1,1)*-Y ; (2,1)+ ; (3,1)*-Y ; (4,1)+ (0,2)+ ; (1,2)+ ; (2,2)+ ; (3,2)+ ; (4,2)+ (0,3)+ ; (1,3)*-K ; (2,3)+ ; (3,3)*-K ; (4,3)+ (0,4)+ ; (1,4)+ ; (2,4)E ; (3,4)+ ; (4,4)+ We can move through any ’+’ cells. We start at (0,1). Allowed moves up to (0,0) or down to (0,2). Need to eventually go to (2,4). Let’s think simple path: go down, right, down, right, down, right? But must avoid stars at (1,3) and (3,3). Also (1,1) and (3,1) are stars. Potential path: from S down to (0,2), then down to (0,3), then down to (0,4), then right to (1,4), right to (2,4) reaching E. This path would be: S (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) E. This does not cross any star cells. Does it satisfy star pairing region rules? The path will create only one region (outside) and maybe interior region? The path is a simple line that does not enclose any area because it’s not closed loop; path divides plane but region concept maybe only closed loops create enclosed areas. But stars are not in the path, they are on the other side of path. For star pairing, they need to be in same region; path does not partition them separate as they

Preprint. Under review.

are on same side (since path is on left side of them). All stars are to the right of path (since path stays at x<=0 then x=1 at (1,4) but still left of stars). Since they stay together, they are in same region (the region not occupied by path). So they are paired within same region. So rule satisfied. Thus this simple path seems valid. No dot constraints. Thus first move: we must choose from legal actions: up or down. Down leads to (0,2) which continues as described. Up would go to (0,0) maybe also possible but then need to navigate. Both may lead to solution. Pick down (3). So final answer digit 3. We must output "Final: 3".

Step 2 of 5 Chosen action: Down Model reasoning We need to decide next move. Let’s interpret grid. Coordinates? Current position [0 2] means x=0, y=2? Grid indexing probably row,column? Given grid displayed as rows. Row0: [’+’, ’+’, ’+’, ’+’, ’+’] Row1: [’V’, ’*-Y’, ’+’, ’*-Y’, ’+’] Row2: [’L’, ’+’, ’+’, ’+’, ’+’] Row3: [’+’, ’*-K’, ’+’, ’*-K’, ’+’] Row4: [’+’, ’+’, ’E’, ’+’, ’+’] Current position L at row2 col0. Legal actions: [0=RIGHT, 3=DOWN]. So can go right to col1 row2 or down to row3 col0. Goal is to reach End E at row4 col2. Must also pass through any dots ’.’ (none visible). Must avoid gaps G (none). Must go around rule cells squares, stars etc. We have stars at positions (row1 col1) and (row1 col3) color Y. Also stars at (row3 col1) and (row3 col3) color K. Triangles? none. Squares? none. Need to satisfy region constraints: each region squares same color; not relevant. Stars: each star must be paired with exactly one other element of same color within same region. That element can be? Probably another star of same color? Or maybe something else? Rule says each star must be paired with exactly ONE other element of same color. Other colors irrelevant. Likely need to have stars of same color paired together within same region. So Y stars must be paired together, K stars together. Must be in same region (enclosed area separated by path). So path must separate Y and K stars maybe each region contains both Y stars? Actually they are currently separate cells: Y stars at (1,1) and (1,3). K stars at (3,1) and (3,3). Path can separate them into regions such that each region contains exactly two stars of same color perhaps? The rule: each star must be paired with exactly one other element of same color. So each Y star must pair with another Y (the other Y star). So both Y stars should be in same region. Similarly K stars in same region. Therefore path must not separate Y stars from each other; same for K. Currently path started at some start node at maybe top-left? We have visited cell V at row1 col0, indicating path from start has moved down? Let’s track: Starting location? Not given, but currently visited V at row1 col0. L at row2 col0. So path goes from start somewhere above row0 maybe? Probably start at (0,0) top-left? Actually grid top-left row0 col0 is ’+’. Possibly start S is at that location but not shown because visited? Wait V at row1 col0 indicates that cell was visited earlier. So start maybe at row0 col0? Then moved down to row1 col0 (now V), then down to row2 col0 (now L). So path downwards column0. Goal is to reach E at (4,2). Need to navigate around stars. Since stars are at (1,1) (1,3) (3,1) (3,3). Path cannot go through them because they are rule cells (odd coordinates both). Indeed they are ’*’ entries. Path can go around them. Current path column0. Options: Right to column1 row2, which would move into a cell currently ’+’ at row2 col1. That cell is adjacent to Y star at (1,1) (above) and K star at (3,1) (below). Passing through there will affect region boundaries.

Preprint. Under review.

Alternatively down to row3 col0 which is ’+’ (currently). Let’s consider overall plan: need to end at (4,2). Likely path will go down to bottom then right to column2. Must also ensure stars are paired properly: both Y stars must be in same region. If we draw a path that separates top row Y stars from each other? They are separated by column2 (col2 is ’+’), but they are at col1 and col3 with a plus cell between. Path can go between them to separate them into different regions. To keep them together, we need to ensure path does not cut between them. Similarly for K stars. Thus, we should avoid creating a wall that cuts between the two Y stars horizontally across row1 between col1 and col3. That would be at row1 col2, which is currently ’+’. If path passes through row1 col2, it would separate Y stars into different regions (above? Actually path goes through that cell; the region on one side might separate). Hard to reason. Given start column0, maybe we go down to row3 col0 then right across bottom row, then up etc. Let’s sketch potential path: currently at (2,0). Down to (3,0), then down to (4,0), then right to (4,1), right to (4,2) which is E. That would be straightforward, not intersecting any stars. Does any rule forbid passing adjacent to stars? No. Check legal actions: after moving down from (2,0) to (3,0), would there be legal moves? Need to see if path passes through any ’.’ none. Thus probably best move is DOWN (digit 3). Let’s ensure not revisiting: (3,0) is not visited yet. No constraints broken. Thus final decision digit 3.

Step 3 of 5 Chosen action: Down Model reasoning We have a path-finding puzzle. Need to decide next move. Step 3, current position [0 3]. Coordinates likely x y? Grid representation: rows? They show grid as 5x5. Indices maybe [x y] means column x, row y? Starting at (0,3) which is first column, fourth row (0-index). Grid shows row order: first row [’+’, ’+’, ’+’, ’+’, ’+’]; second row [’V’, ’*-Y’, ’+’, ’*-Y’, ’+’]; third row [’V’, ’+’, ’+’, ’+’, ’+’]; fourth row [’L’, ’*-K’, ’+’, ’*-K’, ’+’]; fifth row [’+’, ’+’, ’E’, ’+’, ’+’]. At current position L at row4 column0 (0-index). Adjacent moves: Right would go to ’*-K’ (a star) which is a rule cell (odd coordinates) maybe not allowed for path (path cannot go onto rule cells). According to core concept: Path travels only on positions marked ’+’ or ’.’ . In grid, ’*’ cells are rule cells - path can’t go on them. So right is not legal. Up would go to row3 column0 which is ’V’ (visited). Cannot revisit? Path cannot revisit cells. So up not legal. Left would go out of bounds. Down goes to row5 column0 which is ’+’ (bottom row). Legal actions list only 3=DOWN. So must go down. So final answer digit 3.

Preprint. Under review.

Step 4 of 5 Chosen action: Right Model reasoning We need to decide the move. Let’s understand grid layout. Coordinates: current position [0 4] meaning x=0, y=4? Probably (col, row) with origin top-left (0,0). Grid shown rows from top (row0) to bottom (row4). Row0: [’+’,’+’,’+’,’+’,’+’] columns 0-4. Row1: [’V’,’*-Y’,’+’,’*-Y’,’+’] Row2: [’V’,’+’,’+’,’+’,’+’] Row3: [’V’,’*-K’,’+’,’*-K’,’+’] Row4: [’L’,’+’,’E’,’+’,’+’] Current position L at row4 col0. End E at row4 col2. There’s a plus at row4 col1 between L and E. Also gap? no. Legal actions: [0=RIGHT] only. So must move right to column1 row4. That’s allowed. Check other constraints: path cannot revisit, and must pass through all dots (none). Should be okay. Thus final action 0. But ensure cannot go through gap? The cell at row4 col1 is ’+’, not gap. Thus answer.

Step 5 of 5 Chosen action: Right Model reasoning We need to understand the puzzle. Grid is 5x5 rows? Let’s map coordinates. Provided grid rows list: Row0: [’+’, ’+’, ’+’, ’+’, ’+’] Row1: [’V’, ’*-Y’, ’+’, ’*-Y’, ’+’] Row2: [’V’, ’+’, ’+’, ’+’, ’+’] Row3: [’V’, ’*-K’, ’+’, ’*-K’, ’+’] Row4: [’V’, ’L’, ’E’, ’+’, ’+’] Current position [1 4] presumably (x, y). Need to confirm coordinate system: likely (x column, y row) zero-index? Starting with positions like row indices. The current position is at row4, column1? Actually [1 4] meaning x=1, y=4. Row index 4 is bottom row (row4). Column index 1 within that row is element ’L’ (makes sense). So L is at row4 col1. Grid includes ’E’ at row4 col2 (x=2,y=4). So end node is adjacent to current position horizontally to the right. Legal actions list: [0=RIGHT] only move possible (maybe no up etc). So we must move right to reach E. The path will go from L at (1,4) to E at (2,4). That would end puzzle. We must output Final: 0 (RIGHT). We should ensure that moving right is allowed (not a gap or visited). Row4 col2 currently ’E’ which is end; moving into E is allowed, I think. So final step. Thus answer: Final: 0

Preprint. Under review.

Final frame

(after last move: Right)

terminal state

Additional Results

E.1

Per-Model Rule-Type Analysis

Figure 11 shows the rule-type profile for GPT-OSS 120B, which exhibited the largest performance variation across evaluation formats. The radar chart illustrates a striking consistency in the model’s relative strengths and weaknesses. The geometric shape of the performance polygon remains nearly identical across the Baseline, Gym without backtracking, and Gym with backtracking settings, merely scaling inward as overall accuracy degrades. Specifically, the model consistently performs best on the Gap, Square, and Dot constraints. In the Baseline setting, accuracy on these rules peaks at or slightly above 20%, but uniformly contracts to roughly 10% to 15% in the standard Gym setting, and drops even further inward when backtracking is enabled. Conversely, the Ylop constraint represents a rigid lower bound; performance on this complex shapesubtraction rule remains exceptionally low (hovering near or below the 5% mark) under all three formats, showing almost no variation. Mid-tier rules, such as Triangles, Stars, and Polyominoes, follow the exact same proportional degradation trend.

GPT-OSS-120B Polyomino Square

Gap

Star

Dot

Triangle

Ylop

Baseline Gym w/o backtracking Gym w/ backtracking

Figure 11: Rule-specific accuracy (%) across all seven rule types for GPT-OSS 120B under each of the three evaluation settings: SPaRC, Spatial-Gym, and Gym with backtracking.

This uniform contraction indicates that the accuracy differences GPT-OSS 120B experiences across settings reflect a global shift in its ability to navigate the sequential format, rather than a selective improvement or disadvantage regarding any specific spatial constraint.

Preprint. Under review.

E.2

Backtracking Details

Total Steps Taken

Figure 12 visualizes the relationship between the total number of environment No backtracking steps taken and the final length of 100 Linear fit (slope=1.66) the generated path (in edges) for all 80 puzzle attempts within the Gym with backtracking. The dashed gray line 60 establishes the no-backtracking baseline (slope = 1), representing a direct trajectory 40 where every action consecutively extends 20 the path. The orange line, depicting a linear fit with a slope of 1.66, quantifies 0 the average utilization of the backtrack 0 10 20 30 40 mechanism. This slope indicates that Final Path Edges models generally dedicate approximately two-thirds of their actions to forward progress and one-third to retracing their Figure 12: Total steps taken versus final path length (in edges) for all puzzle attempts in the steps. Gym with backtracking setting. The dashed Beyond the average, the plotted line denotes the no-backtracking baseline distribution provides deeper insight (slope = 1); the orange line shows the linear into how models behave when given the fit (slope = 1.66). ability to revise their decisions. A dense cluster of points lies immediately along the baseline, indicating that models frequently commit to their initial decisions and advance without utilizing the correction mechanism at all. In stark contrast, the wide vertical dispersion above the diagonal highlights episodes of extensive backtracking. In these instances, models actively leverage the backtracking feature to undo sequences of moves, occasionally reaching the environment’s 100-step maximum. However, these high step counts generally correspond to short final paths. This behavioral pattern suggests that instead of using the backtrack ability to explore alternative, longer routes necessary to navigate complex rule constraints, models tend to use it to recursively prune their paths, returning to earlier states without successfully advancing deeper into the puzzle grid. Vision Ablation Details

Figure 13 provides a breakdown of the vision ablation experiments across the five puzzle difficulty levels. As expected, all three configurations show a decline in accuracy as puzzle complexity increases, ultimately converging to near-zero performance at levels 4 and 5. This convergence indicates that the most complex spatial constraints exceed current model capabilities regardless of the provided input modality.

Accuracy (%)

E.3

Qwen3-32B (Text) Qwen3-VL-32B (Text) Qwen3-VL-32B (Vision)

0 1

Difficulty Level

Notably, the performance of the two text- Figure 13: Accuracy (%) broken down by based evaluations (the standard Qwen3- difficulty level (1–5) for Qwen3-32B (text), 32B model and the vision-language variant Qwen3-VL-32B (text), and Qwen3-VL-32B Qwen3-VL-32B) tracks almost identically (vision). across the entire difficulty spectrum. Both models achieve their peak accuracy of approximately 35% on the easiest puzzles and decline in tandem. This confirms that integrating visual processing architectures into the VL model does not degrade its underlying text-based spatial reasoning capacity. In contrast, supplying rendered puzzle images to the Qwen3-VL-32B model severely impairs its performance right from the start. Even at difficulty level 1, the vision-enabled agent 25

Preprint. Under review.

achieves only about 12% accuracy, roughly a two-thirds reduction compared to its textonly counterpart. By difficulty level 2, the vision model’s performance collapses to near zero, whereas the text-based models still maintain a solve rate above 10%. This massive divergence on the easiest puzzles underscores that current multimodal models struggle to reliably extract structured, relational logic from raw pixels, becoming overwhelmed by visual input on tasks they can otherwise partially solve when the state is represented purely as text. E.4

Reasoning Mode

Reasoning models with extended CoT outperformed instruction-tuned models in the baseline evaluation (Kaesberg et al., 2025b). In Spatial-Gym, direction choice is limited to one of the four possible ones. We test whether extended reasoning remains important at this low per-step complexity, or whether the structured environment compensates for its absence. We compare Qwen 3 14B and 32B in reasoning mode (extended thinking enabled) versus non-reasoning mode (standard output) across baseline and Spatial-Gym. Gym

Navigation Outcome Finished

12.6%

10.6%

10.2%

10 5.2% 1.2%

1.4%

Qwen 3 14B

Qwen 3 32B

3.4%

2.2%

0 Qwen 3 14B

Qwen 3 32B

Reasoning

Rate (%)

Accuracy (%)

Baseline

100 75 50 25 0

No Reasoning

68%

45%

Qwen 3 14B

Deadlocked

60%

39%

Qwen 3 32B

Figure 14: Reasoning versus non-reasoning mode ablation for Qwen 3 14B and Qwen 3 32B. Accuracy (%) is shown for both baseline and Spatial-Gym settings (left and center), and completion rate (%) is shown for the Gym setting (right). Each group compares the reasoning-enabled (dark) and reasoning-disabled (light) variants of the same model. Figure 14 shows accuracy and completion for both modes across the two settings. In the baseline evaluation, reasoning mode yields large gains. Qwen 3 14B achieves 12.6% accuracy with reasoning enabled, but only 1.2% without, and Qwen 3 32B reaches 5.2% but only 1.4% without. In Spatial-Gym we still see the same difference, but not as prominent. The 14B model scores 10.2% with reasoning versus 3.4% without, and the 32B model achieves 10.6% versus 2.2%. Reasoning mode provides a 3 − 5× advantage even in the step-by-step setting. Completion follows a similar pattern, as reasoning-enabled models finish 60–68% of puzzles while those without reasoning reach only 39–45%. Non-reasoning models become deadlocked more often, suggesting they cannot reliably plan even a single step without extended thinking. The structured Gym environment does not compensate for the absence of reasoning. SpatialGym partially closes the gap between reasoning and non-reasoning variants relative to the baseline, but a 3–5× difference persists. Non-reasoning models fail at both rule satisfaction and basic navigation, confirming that spatial constraint reasoning requires deliberate multistep reasoning that the structure of the sequential environment alone cannot replace. This aligns with Sprague et al. (2024), who show that CoT provides the largest gains on tasks requiring sequential constraint evaluation rather than single-step pattern matching. E.5

Inter-Model Agreement

Figure 15 visualizes the agreement between the different models in the Spatial-Gym evaluation format. The Jaccard similarity matrix on the left measures the direct overlap between the sets of puzzles successfully solved by each model pair. On the right, the conditional probability matrix illustrates the likelihood that a particular model successfully solves a puzzle given that another specific model has already solved it. The high conditional 26

Preprint. Under review.

Jaccard Similarity GPT-OSS

1.00

0.51

0.39

0.25

0.18

0.15

0.13

OLMo-3.1

0.51

1.00

0.42

0.34

0.32

0.20

0.19

0.15

Nemotron

0.39

0.42

1.00

0.40

0.31

0.15

0.13

0.10

Qwen3-32B

0.39

0.34

0.40

1.00

0.30

0.16

0.14

R1-Distill

0.25

0.32

0.31

0.30

1.00

0.21

0.18

0.08

Gemma-3

0.18

0.20

0.15

0.16

0.21

1.00

0.27

0.32

Magistral

0.15

0.19

0.13

0.14

0.18

0.27

1.00

0.24

Qwen3-0.6B

0.13

0.15

0.10

0.14

0.08

0.32

0.24

1.00

0.8 0.6 0.4 0.2

1.00

0.57

0.47

0.46

0.26

0.19

0.15

0.14

0.81

1.00

0.58

0.49

0.35

0.23

0.19

0.16

0.69

0.60

1.00

0.56

0.35

0.18

0.15

0.11

0.70

0.53

0.58

1.00

0.34

0.19

0.15

0.81

0.77

0.73

0.69

1.00

0.31

0.23

0.12

0.75

0.65

0.50

0.40

1.00

0.35

0.40

0.92

0.85

0.62

0.46

0.54

1.00

0.38

0.85

0.69

0.46

0.62

0.23

0.62

0.38

1.00

1.0 0.8 0.6 0.4 0.2

PT -O LM SS oN 3 em .1 Q otr o w en n 3R1 32B -D i G stil em l m M a-3 ag i Q w stra en l 30. 6B

0.0

PT -O LM SS oN 3 em .1 Q otr o w en n 3R1 32B -D i G stil em l m M a-3 ag i Q w stra en l 30. 6B

0.0

P(col solves | row solves)

1.0

Figure 15: Inter-model agreement matrices for the Spatial-Gym setting. (left) Jaccard similarity between each pair of models’ solved puzzle sets. (right) Conditional probability P(col solves | row solves), where entry (i, j) denotes the fraction of puzzles solved by row model i that are also solved by column model j. probabilities observed in the rows of the strongest models, such as GPT-OSS 120B and OLMo 3.1 32B, suggest that they generally solve a superset of the puzzles completed by weaker models. This pattern implies shared failure modes and similar reasoning limitations across different architectures when navigating spatial constraints. Unique Solves Analysis 80

Total Solved Uniquely Solved

60 40 20

en 332 N em B ot ro O LM n o3. R1 1 -D i Q st w i en ll 30. 6 G em B m aM 3 ag is tr al

PT -O

Figure 16 shows a comparison of the total number of puzzles solved by each model (blue bars) with the subset of puzzles uniquely solved by that model alone (orange bars) within the Spatial-Gym setting. Unsurprisingly, the top-performing model, GPT-OSS 120B, dominates both metrics, solving exactly 80 puzzles in total and accounting for the largest share of uniquely solved instances (nearly 20).

Puzzles

E.6

However, a closer examination of the mid-tier reasoning models reveals a nonlinear relationship between overall spatial capability and solution uniqueness. For Figure 16: Total number of puzzles solved instance, while OLMo 3.1 32B solves (blue) versus puzzles solved exclusively by slightly more puzzles in total than both that model and no other (orange) in the Nemotron 49B and Qwen3-32B, it produces Spatial-Gym setting, for each of the eight fewer than half as many unique solves. This evaluated models. shows that OLMo mostly solves the same puzzles as the other top models. In contrast, Qwen3-32B and Nemotron use unique approaches that allow them to solve specific puzzles that the others cannot. Furthermore, it is notable that almost all of the weaker models (including the small Qwen30.6B and the non-reasoning Gemma 3 27B) manage to uniquely solve at least one or two specific puzzles that the stronger models fail on entirely. The only exception is Magistral, 27

Preprint. Under review.

whose successful trajectories are entirely subsumed by other agents. This distribution suggests that while overall spatial capability tightly correlates with model strength, differing architectural biases or random walk variations during step-by-step generation occasionally allow weaker agents to find valid paths that highly confident models systematically overlook. Consequently, this diversity implies that multi-agent ensemble methods (Becker et al., 2025) or majority-voting strategies (Kaesberg et al., 2025a) could yield measurable performance gains in constraint-heavy spatial environments. E.7

Performance Scaling Across Difficulty (a) SPaRC

(b) Gym w/o backtracking

Accuracy (%)

60 40 20 0 1

Difficulty Level Qwen 3 0.6B Qwen 3 32B

Difficulty Level OLMo 3.1 32B R1 Distill 32B

Gemma 3 27B Magistral Small

Difficulty Level Nemotron 49B GPT-OSS 120B

Figure 17: Accuracy (%) by difficulty level (1–5) for all eight models across the three evaluation settings: (a) original SPaRC, (b) Gym without backtracking, and (c) Gym with backtracking. Each line corresponds to one model. Figure 17 demonstrates how model performance degrades as puzzle difficulty increases from level 1 to level 5 across the three distinct evaluation settings. Across all formats, accuracy drops substantially on harder puzzle configurations. In the baseline SPaRC setting, certain models exhibit sharp, non-monotonic drops, which heavily conflate formatting difficulties with reasoning failures. In contrast, the two Spatial-Gym settings yield notably smoother scaling curves, confirming that the stepwise environment successfully isolates spatial reasoning capabilities by eliminating strict formatting requirements. At the highest difficulty level, accuracy universally converges near zero, emphasizing a rigid capability limit that current models cannot bypass regardless of the prompting or interaction format. E.8

Accuracy versus Reasoning Effort

Figure 18 maps overall model accuracy against the average token count generated per puzzle in a logarithmic scale. The sequential Spatial-Gym formats inherently require substantially more token generation than the one-shot SPaRC baseline due to the continuous back-andforth interactions. However, producing an increased volume of tokens does not reliably translate into higher reasoning accuracy. This disconnect becomes especially apparent in the backtracking setting, where models generate the most tokens. Instead of leveraging this extra computational effort to explore complex constraint satisfaction, models tend to spend their tokens navigating toward shorter, simpler paths, which ultimately harms the performance of stronger agents. E.9

Token Usage

Figure 19 shows the average token count per puzzle across difficulty levels (note that the difficulty level is the ceiling of the continuous difficulty score). (a) The baseline shows no consistent scaling trend. (b) Under Spatial-Gym, all models show a clearer upward trend, with token consumption increasing more than 5× compared to baseline. (c) With backtracking, token counts roughly double, though the scaling with difficulty flattens. 28

Preprint. Under review.

Model GPT-OSS-120B Gemma-3-27B Magistral-Small Nemotron-49B OLMo-3.1-32B Qwen3-0.6B Qwen3-32B R1-Distill-32B

Accuracy (%)

Variant Baseline Gym w/o backtracking Gym w/ backtracking

0 100

101

102

Avg Tokens per Puzzle (K)

Figure 18: Accuracy (%) versus average token count per puzzle (K, log scale) for all eight models across the three evaluation settings (Baseline: ▲, Spatial-Gym: , Backtracking: ■). Each color denotes a distinct model.

15 10 5 0 1

(b) Gym w/o backtracking 100

0 1

Difficulty Level Qwen 3 0.6B Qwen 3 32B

Avg Tokens per Puzzle (K)

(a) Baseline

Avg Tokens per Puzzle (K)

•

Difficulty Level OLMo 3.1 32B R1 Distill 32B

Gemma 3 27B Magistral Small

100

Difficulty Level Nemotron 49B GPT-OSS 120B

Figure 19: Average token count per puzzle (in thousands) across difficulty levels 1–5 for all eight models under (a) baseline, (b) Gym without backtracking, and (c) Gym with backtracking. Each line corresponds to one model.

Training of Reasoning Agents

Since Spatial-Gym is implemented as a Gymnasium-compatible sequential decision environment, it can also serve as a testbed for reinforcement learning. While the main paper focuses on evaluation, we additionally conduct preliminary RL experiments with Qwen2.5-3B-Instruct (Team, 2024) to investigate whether task-specific interaction and reward optimization can improve spatial reasoning performance. We choose this model scale due to limited compute resources and the high cost of RL training in Spatial-Gym, where each rollout involves relatively long textual state inputs and long-horizon interactions. Our implementation is based on RAGEN (Wang et al., 2025), and we use the default Spatial-Gym setting with backtracking disabled. At each environment step, the model receives a system prompt consisting of the general task instructions (Appendix B.2) together with the current textual state returned by the environment. This state includes the current grid configuration, the traced path so far, the agent’s current position, and the set of legal moves. Conditioned on this input, the model generates a structured response in a ReAct-style format (Yao et al., 2022), where the intermediate reasoning is enclosed in <think> </think> tags and the selected action is enclosed in <answer> </answer> tags. The action extracted from the <answer> block is then parsed and executed in the environment as the agent’s next move. Because interaction with the environment depends on successful parsing, only responses that follow the prescribed format can be executed correctly. To encourage stable interaction, we introduce an additional penalty for invalid outputs, such as missing tags or an unparsable 29

Preprint. Under review.

action. This penalty is used only during training and is intended to discourage malformed responses rather than poor decision-making itself. This design allows the model to produce free-form intermediate reasoning while still interfacing with the environment through a discrete executable action. As the environment state is updated after each step, trajectories are generated auto-regressively through repeated model-environment interaction. We train directly from the base model, without supervised fine-tuning on expert trajectories, using Proximal Policy Optimization (PPO) (Schulman et al., 2017a) with Generalized Advantage Estimation (GAE). Specifically, trajectories are sampled on-policy through interaction with the environment. For each trajectory, the process reward, outcome reward, and format penalty are summed to form the training reward signal. PPO updates are then applied to increase the likelihood of high-return responses while constraining policy drift between updates. We set the maximum number of interaction steps to 31. For these preliminary experiments, we train the model only on difficulty-1 and difficulty-2 puzzles for 200 training steps, since easier instances provide a more stable starting point for RL from a base model by increasing the frequency of successful trajectories and making credit assignment more tractable. The overall results are shown in Table 1. Model

Acc. #Avg. Steps #Min. Steps #Max. Steps Term. D1 D2 D3 D4 D5

Base Trained

2.6 3.6

21.3 21.2

1 1

75 86

35.0 33.6

8.1 4.2 0.8 0.0 0.0 9.3 5.1 2.5 1.2 0.0

Table 1: Performance of the base model and the RL-trained model on Spatial-Gym. Acc. denotes the percentage of puzzles solved successfully. Avg. Steps is the average number of interaction steps over all puzzles in the test set, while Min. Steps and Max. Steps denote the minimum and maximum numbers of steps, respectively. Term. denotes the percentage of trajectories that reach the target endpoint, regardless of whether all constraints are satisfied. D1–D5 report accuracy for puzzle difficulty levels 1–5. The overall results are shown in Table 1. Reinforcement learning yields a modest but consistent improvement over the base model. Overall accuracy increases from 2.6% to 3.6%, showing that direct policy optimization in Spatial-Gym can improve performance even when training starts from the base model without supervised trajectory imitation. The improvement is also reflected in the difficulty-wise breakdown: the trained model performs better on difficulty levels 1 through 4, with gains from 8.1% to 9.3% on difficulty-1 puzzles, from 4.2% to 5.1% on difficulty-2 puzzles, from 0.8% to 2.5% on difficulty-3 puzzles, and from 0.0% to 1.2% on difficulty-4 puzzles, while both models fail on difficulty-5 puzzles. At the same time, the gains remain small in absolute terms. The average number of interaction steps is nearly unchanged (21.3 vs. 21.2), and the termination rate slightly decreases from 35.0% to 33.6%, suggesting that the trained model is not simply learning to reach the endpoint more often, but only modestly improving its ability to satisfy the full set of puzzle constraints. More broadly, the persistently low performance, even after task-specific RL training, highlights the difficulty of the environment and further supports the value of Spatial-Gym as a benchmark for spatial reasoning. These results suggest that the challenge posed by Spatial-Gym is not merely due to prompt format or lack of interaction, but reflects a more fundamental gap in current models’ spatial reasoning and planning abilities. Overall, our preliminary RL results show that Spatial-Gym is not only a viable training environment but also a demanding benchmark whose difficulty cannot be overcome by straightforward policy optimization alone.

Full Tabular Results

This appendix provides the comprehensive numerical data for all experiments discussed in the main text. The tables detail both the overall performance metrics across difficulty levels and the granular performance across specific rule types for the eight evaluated models. Table 2 presents the baseline performance on the original SPaRC one-shot evaluation, including overall accuracy, solve rates for difficulty levels 1 through 5, and the average 30

Preprint. Under review.

number of steps taken per puzzle. Table 3 details the exact metrics for the standard SpatialGym setting without backtracking, again providing the solve rates for the five difficulty levels alongside the average step counts. Table 4 displays the corresponding results for the Spatial-Gym setting with the backtracking feature enabled, allowing for a direct assessment of how backtracking influences step counts and accuracy across the difficulty spectrum. Model GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

Accuracy

Avg. Steps

21.6 11.4 5.2 16.2 3.6 0.8 1.6 0.4

64.0 45.3 19.8 51.2 9.3 1.2 3.5 0.0

26.3 7.6 4.2 20.3 5.9 0.8 2.5 0.8

9.9 5.0 2.5 9.1 1.7 1.7 0.8 0.8

8.1 2.3 1.2 2.3 1.2 0.0 1.2 0.0

3.4 1.1 0.0 0.0 0.0 0.0 0.0 0.0

19.8 20.0 20.0 16.1 19.3 17.6 20.3 15.5

Table 2: SPaRC results. Overall accuracy (%) and per-difficulty solve rate (%, D1–D5) for all eight models, along with the average number of steps taken per puzzle. Best results in bold. Model GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

Accuracy

Avg. Steps

16.0 11.0 10.6 11.4 5.2 4.0 2.6 2.7

52.3 32.6 34.9 27.9 20.9 9.3 7.0 7.4

22.9 14.4 11.9 16.1 4.2 5.1 2.5 3.5

4.1 5.8 5.8 7.4 2.5 4.1 3.3 2.5

2.3 1.2 2.3 4.7 0.0 1.2 0.0 0.0

1.1 2.2 0.0 1.1 0.0 0.0 0.0 0.0

14.7 18.1 15.7 14.8 13.6 11.8 12.8 14.4

Table 3: Spatial-Gym results. Overall accuracy (%) and per-difficulty solve rate (%, D1–D5) for all eight models, along with the average number of steps taken per puzzle. Best results in bold. Model GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

Accuracy

Avg. Steps

10.2 11.2 9.6 9.6 6.8 5.0 5.3 3.8

31.4 29.1 31.4 29.1 22.1 12.8 12.9 7.0

13.6 19.5 11.9 13.6 9.3 5.9 6.8 5.1

5.0 5.0 2.5 3.3 2.5 5.0 5.9 3.3

2.3 2.3 4.7 2.3 1.2 0.0 0.0 2.3

0.0 0.0 0.0 1.1 0.0 1.1 0.0 1.1

20.3 33.4 29.3 24.6 34.4 57.4 45.4 20.2

Table 4: Spatial-Gym with backtracking results. Overall accuracy (%) and per-difficulty solve rate (%, D1–D5) for all eight models, along with the average number of steps taken per puzzle. Best results in bold.

Preprint. Under review.

Furthermore, the results are broken down by the specific spatial constraints present in the puzzles, which include Dot, Gap, Polyomino, Ylop, Star, Square, and Triangle. Table 5 lists the rule-specific accuracies for the SPaRC baseline setting. Table 6 isolates the rule-specific performance within the standard Spatial-Gym environment. Finally, Table 7 shows the rule-specific accuracy when backtracking is enabled in the Gym environment. Model

Dot

Gap

Polyomino

Ylop

Star

Square

Triangle

GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

21.9 13.7 5.5 17.5 2.4 0.3 0.3 0.0

20.8 9.6 5.1 15.0 3.8 0.3 1.6 0.3

9.8 5.2 2.3 6.6 0.3 1.0 1.6 0.7

4.0 4.0 0.0 0.0 0.0 0.0 0.0 0.0

10.0 2.9 1.4 4.3 2.4 0.0 1.0 0.0

21.4 11.0 4.2 16.3 3.4 1.1 1.7 0.6

15.5 5.2 2.1 10.7 2.1 0.0 0.4 0.0

Table 5: SPaRC accuracy (%) broken down by rule type for all eight models. Best results in bold. Model

Dot

Gap

Polyomino

Ylop

Star

Square

Triangle

GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

16.8 9.9 9.2 9.6 4.8 1.4 0.7 0.4

16.3 10.9 9.6 11.2 5.8 3.8 2.6 2.3

7.2 3.0 5.6 5.2 1.0 3.0 1.3 2.7

4.0 0.0 4.0 4.0 0.0 4.0 0.0 0.0

7.1 6.2 4.8 6.7 1.4 2.4 1.4 1.5

14.1 10.7 9.6 11.8 4.8 3.4 2.3 2.1

9.0 9.0 3.9 7.3 2.1 0.4 0.4 0.4

Table 6: Spatial-Gym accuracy (%) broken down by rule type for all eight models. Best results in bold. Model

Dot

Gap

Polyomino

Ylop

Star

Square

Triangle

GPT-OSS 120B Nemotron 49B Qwen 3 32B OLMo 3.1 32B R1 Distill 32B Gemma 3 27B Magistral Small Qwen 3 0.6B

9.2 10.3 8.2 7.5 6.2 2.4 2.4 2.5

11.2 11.8 9.9 9.6 7.3 4.5 5.5 8.8

4.9 3.0 3.9 3.6 2.3 3.3 4.0 6.0

4.0 4.0 4.0 0.0 4.0 0.0 4.2 7.7

3.8 5.7 4.3 4.8 3.3 3.8 3.4 7.7

9.3 10.4 8.7 9.0 6.5 5.1 3.4 8.6

5.6 9.0 5.2 6.0 3.0 1.3 2.6 1.9

Table 7: Spatial-Gym with backtracking accuracy (%) broken down by rule type for all eight models. Best results in bold.

Preprint. Under review.

AI-Usage Card

AI Usage Card

PROJECT DETAILS

PROJECT NAME Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym

DOMAIN Paper

KEY APPLICATION Spatial Reasoning

CONTACT(S)

NAME(S) Lars Benedikt Kaesberg

EMAIL(S) [email protected]

AFFILIATION(S) University Göttingen

MODEL(S)

MODEL NAME(S) ChatGPT 5.2, Claude Opus 4.6, Gemini 3 Pro

LITERATURE REVIEW

FINDING LITERATURE Claude, ChatGPT

FINDING EXAMPLES FROM KNOWN LITERATURE OR ADDING LITERATURE FOR EXISTING STATEMENTS

COMPARING LITERATURE

WRITING

GENERATING NEW TEXT BASED ON INSTRUCTIONS

ASSISTING IN IMPROVING OWN CONTENT OR PARAPHRASING RELATED WORK Claude, Gemini

PUTTING OTHER WORKS IN PERSPECTIVE

CODING

GENERATING NEW CODE BASED ON DESCRIPTIONS OR EXISTING CODE Claude

REFACTORING AND OPTIMIZING EXISTING CODE Claude

COMPARING ASPECTS OF EXISTING CODE

THE CORRESPONDING AUTHORS VERIFY AND AGREE WITH THE MODIFICATIONS OR GENERATIONS OF THEIR USED AI-GENERATED CONTENT AI Usage Card v2.0

https://ai-cards.org

Wahle et al. (2023)

CiteAssist Citation Sheet Generated with citeassist.uni-goettingen.de Kaesberg et al. (2024)

BibTeX Entry @misc{kaesberg2026, author={Kaesberg, Lars Benedikt and Yang, Tianyu and Bauer, Niklas and Ruas, Terry and Wahle, Jan Philip and Gipp, Bela}, title={Mind the Gap Between Spatial Reasoning and Acting! Step-by-Step Evaluation of Agents With Spatial-Gym}, year={2026}, month={04}, topic={nlp} }

Generated April 13, 2026

Record · ID 6012 · SHA-256 e152836b70e36bd2
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.