Yggdrasil: a Layer-First 3D Scene Graph for Real-Time Querying

Arshia Akhavan; Ermanno Bartoli; Afnan Algharbi; Alireza Hoseinpur; Iolanda Leite; Bryan Donyanavard

cs.ROSep 29, 2026

Yggdrasil: a Layer-First 3D Scene Graph for Real-Time Querying

Authors: Arshia Akhavan, Ermanno Bartoli, Afnan Algharbi, Alireza Hoseinpur, Iolanda Leite, Bryan Donyanavard

Organizations: Department of Computer Science, San Diego State University · Division of Robotics, Perception and Learning, KTH Royal Institute of Technology · Department of Computer Science, University of Illinois Chicago

Abstract

Robotic agents use 3D scene graphs (3DSG) to perform tasks ranging from scene understanding to scene interaction. Although an extensive body of work addresses scene graph generation, little attention has been paid to optimizing the graph for consumption, which leaves state-of-the-art perception pipelines to work around their own scene graph and to pay a latency cost that does not fit the real-time budget a perception loop runs on. We present Yggdrasil, the first 3D scene graph designed to be efficient for both generation and consumption: a layer-first hierarchical graph built from generic nodes, edges, and layers, which expresses the representations existing pipelines already produce, indoor or outdoor, flat or hierarchical, while natively answering the positional and semantic queries downstream tasks issue. Against a published DSG baseline, Yggdrasil answers queries up to $121\times$ faster, and every query we measure falls between 2 and 127 microseconds, three to five orders of magnitude inside the 200 microsecond keyframe budget a 3DSG consumer lives in, on both a workstation and embedded class device. We integrate Yggdrasil into three published pipelines spanning human trajectory prediction, object-goal navigation, and human-aware motion planning, where it removes up to 99% of the time each spends on its scene graph. The implementation, benchmark harness, and all three integrations are available online.

Figures & tables

Panel of Figure 1 — Fig. 1 : Yggdrasil ’s layer-first architecture: a DAG of layers, each an isolated graph, with nesting relations connecting nodes across layers that share an edge in the DAG. A typed query interface answers semantic and spatial queries against this store in place, with no intermediate conversion.

Panel of Figure 2 — Fig. 2 : Porting a scene graph into Yggdrasil . (a) and (b) show the same office scene in the DSG format and in Yggdrasil ’s layer-oriented hierarchy (each color presents a layer); (c) shows what the change buys downstream in LP2.

Fig. 3 : Query latency in

\mathrm{\SIUnitSymbolMicro s}

on the uHumans2 office scene graph, averaged over five runs, every value printed on its bar. Columns are query families; rows are the two machines of Section V-D , each with its own vertical scale. Note the logarithmic axis in (a) and (b). Bars follow the legend order.

target	nodes	memory (MB)	update latency ( $\mathrm{\SIUnitSymbolMicro s}$ )
dsg	3,532 †	40.3	7.54
vanilla	3,746	25.6	7.01
chocolate	3,778	33.7	6.91
mint	3,778	70.9	12.7
saffron	361,980	144.6	129

TABLE I : Static cost of each target on the uHumans2 office graph.

	office		home
query	orig.	Yggdrasil	orig.	Yggdrasil
room of a waypoint	987	1.13	725	1.14
nearest waypoint	169	5.7	134	5.3
waypoints within 0.5 m	8,420	79	5,981	69
shortest-path lookup	0.50	0.63	0.50	0.65
grounding distances	20	23	14	14

TABLE II : Scene-graph query cost in LP2, pooled over five repetitions per scene. The five query rows are median per-call latencies in

\mathrm{\SIUnitSymbolMicro s}

; the two aggregate rows below them are per-run totals in

\mathrm{ms}

. The original builds its NetworkX copy and KD-tree at startup and rebuilds the KD-tree on every iteration, whereas Yggdrasil builds its indexes once and maintains them incrementally.

Panel of Figure 6 — Fig. 4 : OSG’s flat scene graph (left) and the same scene in Yggdrasil ’s layers (right); the is near relation moves down to the shadow nodes in the physical layer.

Operation	OSG (ms)	Yggdrasil (ms)	Result
Total graph-update time	488.117	229.312	2.13 $\times$
Serialize graph to prompt	144.310	20.622	7.00 $\times$
Get nodes by type	59.451	2.223	26.74 $\times$
Check node type	39.903	2.860	13.95 $\times$
Add node	83.763	54.467	1.54 $\times$
Count instances	158.920	145.510	1.09 $\times$

TABLE III : Performance comparison between OSG and Yggdrasil.

Explore similar work

3D Scene Graphs: Open Challenges and Future Directions
Jun 15, 2026Dennis Rotondi, Francesco Argenziano, Sebastian Koch +103D Scene Graphs Scene Understanding
University of Stuttgart · IMPRS-IS · Sapienza University of Rome +7
OP3DSG: Open-Vocabulary Part-Aware 3D Scene Graph Generation for Real-World Environments
Jun 29, 2026Yirum Kim, Ue-Hwan Kim3D Scene Graphs 3D Models
Gwangju Institute of Science and Technology (GIST), Gwangju, Republic of Korea
DeWorldSG: Depth-Aware 3D Semantic Scene Graph Generation via World-Model Priors
Jul 1, 2026Seok-Young Kim, Abdelrahman Elskhawy, Taewook Ha +43D Scene Graphs 3D Gaussian
Korea Advanced Institute of Science and Technology · Technical University of Munich · Munich Center for Machine Learning (MCML) +1

Jun 15, 2026, cs.ROJ/K move · Enter open · S save

3D Scene Graphs: Open Challenges and Future Directions

Dennis Rotondi, Francesco Argenziano, Sebastian Koch, Nathan Hughes+9

University of Stuttgart · IMPRS-IS · Sapienza University of Rome+7

3D Scene Graphs Scene Understanding Geospatial Reasoning Affordances Challenges

Open paper AskPDF arXiv

3D Scene Graphs (3DSGs) have emerged as a powerful representation for spatial AI by combining geometric grounding with semantic and relational abstractions of the environment. Their expressiveness has made them relevant to a broad range of problems in robotics and computer vision, including manipulation, navigation, task planning, scene understanding, and many others. However, the field remains fragmented: different communities adopt distinct formulations, construction pipelines, and evaluation protocols, making it difficult to compare methods, identify common assumptions, and assess remaining challenges for robust real-world deployment. This survey provides a unified and critical review of 3DSGs, with particular emphasis on open challenges and future directions. We first formalize 3DSGs under a common definition and analyze the principal modeling choices that characterize existing formulations, including node and edge attributes, hierarchical structure, dynamic scene representations, and affordance-aware extensions. We then review how 3DSGs are built from raw sensory observations, discussing the most common terminologies, conventions, and techniques. Finally, we examine downstream applications and evaluation strategies, from intrinsic graph quality to task-level performance. To support the community, we also provide a dedicated website that organizes and extends the surveyed content, accessible at https://3dscenegraphs.com/.

Abstract

Explore similar work

3D Scene Graphs: Open Challenges and Future Directions

OP3DSG: Open-Vocabulary Part-Aware 3D Scene Graph Generation for Real-World Environments

DeWorldSG: Depth-Aware 3D Semantic Scene Graph Generation via World-Model Priors