Is It the Scene or the Serialization? Hop-Controlled Spatial Reasoning over Hierarchical Scene Graphs

Language models are increasingly asked to reason about physical spaces: which room holds the drill, how to reach the third-floor kitchen, what is next to the sofa. They usually receive these spaces as text. A robot's map is converted into a list of facts or a paragraph of description, and the model answers from that. When the model fails, we cannot tell why. The space may be hard to reason about. The text format may have scattered related facts so far apart that the model must chain many lookups. Or the model may be answering from memorized expectations ("fridges are in kitchens") and ignoring the scene it was given. This proposal builds a generator of fresh, checkable indoor reasoning problems that separates these three causes. It then tests one specific claim: a hierarchical text layout keeps facts that depend on each other close together, and this layout removes most of the penalty models pay for deep spatial hierarchies.

The tool is a 3D scene graph, a tree-plus-links structure in which a building contains floors, floors contain rooms, rooms contain objects, and doors and stairs connect rooms. Each scene graph can be written out as text in many ways, a step called graph linearization. Our claim is that accuracy on a scene question is governed mainly by how many separate pieces of text the model must stitch together under a given layout, and much less by how deep the scene hierarchy is. We also measure how often models override the given scene with world-knowledge priors, which plays the same role for spatial reasoning that test-set memorization plays in benchmark contamination.

Core Claim

Two findings from the literature point in opposite directions. DyVal generates reasoning problems from random directed acyclic graphs. It found that accuracy falls much faster as dependency chains get longer than as the number of parallel premises grows. It also found that reversing premise order cost GPT-4 13.6% on reachability. Scene graphs are deep by construction, as shown in the four-layer hierarchy of 3D Scene Graph and the keyframe–wall–room–floor levels of S-Graphs 2.0. DyVal therefore predicts that models will collapse on multi-level spatial questions. On the other side, Link Prediction on Textual Edge Graphs writes graph neighborhoods as nested documents with section headers and cross-references. It reports gains over flat linearization, which suggests that layout can absorb some of that depth. Divide-and-Conquer prompting splits problems into independent sub-tasks. It shows formally and empirically that this limits error compounding.

To make this precise, define the serialized hop count $h(q, F)$ of a question $q$ under text format $F$. It is the minimum number of non-adjacent text spans whose contents must be combined to derive the answer. If each cross-span combination fails independently with probability $1-p$, accuracy should behave like

$$\text{acc}(q, F) \approx a_0 \, p^{\,h(q,F)},$$

where $a_0$ is accuracy on questions answerable from a single span. The exponential form comes directly from assuming independent per-step errors, the same compounding argument the Divide-and-Conquer paper makes. The testable claim is that once $h$ is controlled, scene depth $d$ has little remaining effect on accuracy. Hierarchical layouts help because they lower $h$ for containment questions. They do not help by giving the model any special understanding of space. The claim is falsifiable. If accuracy still tracks $d$ when $h$ is held fixed, the claim is wrong.

Research Program

The first component is a procedural scene generator. It samples buildings with a controlled number of floors and rooms per floor and a controlled nesting depth. The containment chain runs building to floor to room to region to furniture to object, giving depths from 2 to 6. It also controls connectivity: doors, stairs, and dead-end corridors. Room-type and object-placement statistics are seeded from the region and object annotations in MMScan, so scenes look plausible. Every scene is new, and every answer is computed exactly by a graph algorithm. This follows DyVal's approach to contamination resistance, carried over into spatial structure, which DyVal did not address.

Questions fall into four families. Containment asks which floor holds the object that is on the table in the room with the piano. Topological routing asks for the fewest doors from A to B, including stair transitions; this family deliberately includes diameter-style questions that probe the "longest path fallacy" that GraphOmni documented. Aggregation asks how many chairs are on floor 2. Mixed questions combine a commonsense step with a structural step, for example "where is the nearest place to wash a dish," which requires inferring which objects afford washing and then routing to them.

Each scene also has a prior-violating twin. The topology is identical, but objects are swapped into atypical rooms (a fridge in a bedroom, a bathtub on the landing). The accuracy gap between twins measures how far the model answers from expectations rather than from the scene. This is the spatial counterpart of the memorized puzzle answers described in Studying and improving reasoning in humans and machines.

The second component is a family of text formats for the same graph, each with $h(q,F)$ computed automatically per question:

  1. A naive prose caption in the style of SQA3D.
  2. A randomly ordered triple list.
  3. A flat edge list ordered by degree with rank-based node relabeling, following Graph Linearization Methods.
  4. An adjacency list, the format GraphOmni found most broadly robust.
  5. A hierarchical document: nested sections per floor and room, objects listed inside their room's section, and doors and stairs as explicit cross-references.
  6. The hierarchical document combined with divide-and-conquer querying. A first call identifies the relevant sections, independent calls answer within each section, and a final call combines the answers.

Formats 5 and 6 are our proposed method. Formats 1 to 4 are baselines.

The third component is transfer to real scenes. We build scene graphs for ScanNet (ScanNet) scenes from MMScan region and object annotations and use them as the text scene input for SQA3D questions. We then apply meaning-preserving perturbations: consistent renaming of object instances, mirrored layouts with left/right questions relabeled to match, and region reordering. If a model's SQA3D accuracy drops under perturbations that leave the correct answer unchanged, that is a direct sign of leaked or memorized benchmark structure on public 2017-era scans.

The models are Llama-3 8B/70B and Qwen-2.5, matching the models in the linearization study, plus o4-mini and Claude-3.5-Sonnet. GraphOmni found the closed models more sensitive to format and the open models more sensitive to prompting, so both kinds are needed.

Baselines

The do-nothing reference is the naive prose caption (format 1) with direct prompting. This is the interface SQA3D found inadequate. On real scenes we also report SQA3D's question-only "blind" model at 43.65% accuracy as the floor any scene-using method must clear.

The strongest flat-linearization competitor is degree-ordered, relabeled edge lists from Graph Linearization Methods. That paper reports roughly a 35% accuracy improvement on GraphQA maximum-degree estimation over random ordering. It is the best published evidence that ordering alone fixes much of the problem. Next to it we run the adjacency list from GraphOmni. On synthetic graphs GraphOmni reports o4-mini at only 17.53% on hard triangle counting, which shows how low accuracy can be even with a good format. No reported result exists on Lacuna for any format on hierarchical scene graphs, so all synthetic baselines are new measurements.

The strongest reasoning-side competitor is a reasoning model (o4-mini) given the best flat format with unrestricted chain-of-thought. A code-execution baseline in the LLM-Modulo style gets the scene graph as JSON and writes a program to answer. Its counterpart in the 3-SAT study reached nearly 100% by handing search to a solver.

On real scenes, the strongest published 3D model is ScanQA with auxiliary position and rotation losses, at 47.20% on SQA3D. Human performance is 90.06%.

Fairness rules apply to every comparison. All formats encode the same graph facts, and their token counts are reported. Where lengths differ by more than 10%, a padded control (neutral filler added to the shorter format) separates length effects from structure effects. Each method gets the same number of prompt-variant trials, five per format, chosen on a held-out development split. For format 6 we count its total tokens across all calls and give single-call baselines an equal output budget.

The key ablation removes the proposal's main ingredient while keeping everything else. It keeps the hierarchical document's section headers but scatters each room's objects across other sections. This raises $h$ without changing content. We also run reversed nesting (children before parents) to see whether DyVal's reversal effect carries over to containment.

Beating the flat baselines means two things. Format 5 or 6 must improve accuracy on depth-4 to depth-6 containment and routing by a margin that clears seed-to-seed variance, and the scattered ablation must lose most of that gain.

Why not just…?

Why not just use the best flat format with good ordering? For node-centric questions this may well be enough, and we expect it to tie the hierarchical document on aggregation. The disagreement is about containment chains. A degree-ordered edge list places "mug on table" and "table in kitchen" wherever their node degrees put them. That leaves $h$ high even when the scene is simple. The decisive check is accuracy plotted against $d$ at matched $h$. If flat ordered lists match hierarchical documents once $h$ is equalized, the benefit was ordering, not hierarchy, and we will report it that way.

Why not just give the graph to code and let a program answer? This is a real threat. For pure containment, routing, and counting, we expect the code baseline to approach the near-perfect accuracy that solver delegation reached on 3-SAT. If it does, the useful contribution on those families is diagnostic: understanding why text-only reasoning fails, which still matters because many deployed systems, such as the frontier summaries that ASCENT sends to its LLM planner, pass text rather than structured data. Mixed questions are where code should struggle, because the affordance step resists formalization. If code also wins there, the conclusion is that linearization is the wrong lever for embodied reasoning, and the paper says so.

Why not just rely on a reasoning model's chain-of-thought? The 3-SAT study found that GPT-4 produced more reasoning tokens near the hardness peak while accuracy still fell to about 10%. Divide-and-conquer beat Tree-of-Thoughts on long multiplication (76.92 vs. 69.41 F1). Both results suggest that longer reasoning does not remove compounding error. Reasoning models are newer than those results, however, and could flatten the $p^{h}$ curve. We fit $p$ separately for each model. A reasoning model with $p$ near 1 would mean the hop penalty has been solved by scale, which is a result worth reporting.

Why not just use SQA3D or ScanQA as they stand? Both are static and built on widely circulated scans. In SQA3D, the blind model scores 43.65% against 47.20% for the best 3D model, so most of the measured accuracy can be reached without the scene. Our perturbation test checks this directly. If accuracy is unchanged under renaming and mirroring, the real-scene numbers are trustworthy. If it drops, static scores overstate spatial reasoning.

Decisive Checks

Three results settle the core claim.

The first is a regression of accuracy on $h$ and $d$ jointly across all synthetic questions and formats. The claim holds if $h$ explains most of the variance and $d$'s coefficient is small at fixed $h$. It fails if accuracy keeps falling with depth under the hierarchical document even when $h=1$.

The second is the scattered-section ablation. It should reproduce the flat-format curve, showing that locality, not section headers, does the work.

The third is the prior-violating twin gap. We expect the gap to be largest for naive captions and smallest for hierarchical documents. If the gap stays large across all formats, layout cannot correct prior reliance, and that becomes a separate, reportable limitation.

On real scenes, success means two things. Hierarchical text input must beat the 43.65% blind floor and approach or exceed the 47.20% ScanQA model with no 3D training. And this advantage must survive the meaning-preserving perturbations, while any advantage of naive captions does not.