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

arXiv:2609.38640 · cs.RO · Submitted 2026-09-29 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa, and with me are Dev and Taro, guest researcher.

Dev: Today's paper: "Yggdrasil: a Layer-First 3D Scene Graph for Real-Time Querying".

Rosa: YGGDRASIL introduces a novel 3D scene graph architecture specifically designed to be efficient for both generation and consumption,

Dev: First, who's behind it and why it matters.

Title and authors: Rosa: Moving on to the specific name of the paper, "Yggdrasil: a Layer-First three dee Scene Graph for Real-Time Querying," it really encapsulates what they're trying to achieve with this new architecture.

Dev: That title really highlights that this isn't just another scene graph; it’s specifically designed around being fast enough for real-time querying, which is a crucial distinction for us in control systems.

Taro: I think the "Layer-First" part of the name suggests a fundamental structural change from previous models, which is what we need to dig into next.

Rosa: Right, so instead of thinking about layers as just a stack you build things on top of, they're proposing a different way to organize the information hierarchy.

Dev: That directly relates to the core design philosophy mentioned in the paper: building from generic nodes, edges, and layers in this specific layer-first manner.

Taro: And I’m thinking about how that structure handles things that aren't perfectly ranked, like outdoor scenes where you don't always have a clear hierarchy of layers.

Rosa: That’s a key point; they want to express existing pipeline representations, whether they are indoor or outdoor, flat or hierarchical, using this new structure instead of forcing everything into one rigid format.

Dev: So it’s about flexibility in expressing what the perception pipeline already produces while simultaneously making it optimized for consumption by answering semantic and spatial queries directly.

Taro: If that's true, then the real impact is that we aren't just changing how we store data, but fundamentally changing how downstream tasks interact with that stored scene information.

Rosa: Precisely; they are giving downstream tasks a direct path to the positional and semantic queries they need without any costly intermediate conversions or steps.

Dev: That means if I’m running a navigation policy, I don't have to stop and rebuild anything just to figure out where an object is relative to me.

Taro: And that speed directly translates into better responsiveness when the world behaves unexpectedly, which is exactly what autonomy needs most.

Rosa: So, the main implication here is enabling a much tighter coupling between scene graph construction and the real-time decision-making process.

Dev: It allows for true construction and consumption together inside a control loop, which I think is where the real engineering payoff lies.

The paper's summary: Rosa: Now, let’s talk about what this paper actually summarizes regarding Yggdrasil, because it outlines the mechanics of how this system functions in practice.

Dev: It summarizes that the core contribution is a layer-first hierarchical graph structure, which is built from generic nodes, edges, and layers that allows it to natively answer positional and semantic queries downstream tasks issue at practical latency without requiring intermediate conversion steps.

Taro: That sounds like the central mechanism that makes it efficient for both generation and consumption simultaneously by avoiding those conversion costs entirely.

Rosa: Exactly; they are describing a system where the graph is structured as a cluster of graphs, with each graph being a layer forming a Directed Acyclic Graph or DAG, which is different from the stack-based hierarchy of prior work.

Dev: That DAG structure means that unlike older systems, one layer can parent more than one child, giving it more expressive power in modeling complex relationships.

Taro: I’m wondering if this DAG structure helps when we have overlapping spatial or semantic information that needs to be represented simultaneously?

Rosa: It does, because the nesting rule they describe is specific: node n1 in layer l1 may nest node n2 in layer l2 exactly when l1 encompasses l2.

Dev: So, this allows for a controlled way to handle nesting and dependency between different abstraction levels within the graph structure.

Taro: That's interesting; it’s a structured way to manage complexity rather than letting the hierarchy become an uncontrolled mess as things get more detailed.

Rosa: Furthermore, they detail the specific query capabilities exposed directly on this graph, which include pattern matching, nearest neighbor searches, field of view checks, and traversal queries.

Dev: Those native APIs are what make consumption so efficient because you don't have to write custom code to perform those searches; it’s built in.

Taro: I can see how having these specific spatial indexes backed by kd-trees per layer and per node makes finding relevant information much faster than scanning the whole scene every time.

Rosa: And they also highlight three integrations spanning human trajectory prediction, object-goal navigation, and human-aware motion planning to show how this system applies across diverse use cases.

Dev: Those integrations are vital because they show that the architecture isn't just a theoretical structure; it’s being tested in actual systems that matter for robotics.

Taro: So, in summary, the paper is summarizing a layer-first DAG structure with generic components and built-in spatial indexing designed to answer specific queries quickly across various real-world applications.

The paper's improvements: Rosa: Now let's look at the specific improvements they suggest for this architecture because it’s not just about what it is, but how they plan to make it even better.

Dev: They focus on exposing a rich set of semantic and spatial queries directly on the graph, such as "nodes matching" or "nodes having" for pattern matching.

Taro: That direct pattern matching capability is powerful because it means we can retrieve nodes by specific features or keys without needing to serialize the entire scene graph first.

Rosa: Right, and then they have spatial and traversal queries like nearest nodes, nodes within a radius, and that inter-layer query called "nearest in subtree."

Dev: Having those per-layer and per-node spatial indexes backed by kd-trees is what powers those efficient spatial searches, which is critical for things like path planning.

Taro: And the field of view query is particularly clever, allowing the system to run a fast frustum check over nodes in a sub-tree of a root node r to confine results to just the agent's occupied room.

Rosa: That confinement capability drastically reduces search space for navigation tasks because it lets an agent focus only on its local surroundings instead of searching the entire scene.

Dev: I also noticed they discuss trade-offs in implementation choices, mentioning configurations like "chocolate," "mint," and "saffron" that balance low memory usage against query times.

Taro: That configuration balancing sounds practical for deployment; choosing the right one based on whether we need to prioritize memory or speed for a specific task.

Rosa: The paper also points out trade-offs concerning the precision needed for graph updates, where "saffron’s fine-grained physical layer allows easier integration with graph generation," while "mint keeps a memory footprint on par with dsg but lacks that precision for operations such as graph update and graph merge."

Dev: So, if we need to change the structure frequently, we might have to accept some latency penalty for that precision because the update latency is visible in those trade-offs.

Taro: That’s a fair caveat; it means the system isn't perfectly optimized for everything at once, and we have to choose our operational mode carefully based on what's changing in the environment.

Rosa: In short, these improvements focus on giving users direct access to powerful, specialized query tools that allow them to leverage spatial and semantic information efficiently while managing their resource consumption effectively.

Conclusion: Dev: So, wrapping up the discussion on "Yggdrasil: a Layer-First three dee Scene Graph for Real-Time Querying," the main takeaway is that this architecture offers a unified scene graph structure that serves both construction and consumption needs effectively.

Rosa: It really boils down to providing substantial performance improvements while maintaining compatibility with existing perception pipelines, which is the core promise of this work.

Taro: The implications are huge because we can potentially ground complex LLM reasoning directly in the scene graph, leading to much more accurate and temporally coherent object-goal navigation plans.

Dev: I think that ability to move from slow scene graph interaction to near real-time querying is what unlocks a new level of autonomy for robotic systems operating in complex, dynamic settings.

Rosa: We’ve seen significant speedups, with queries up to one hundred twenty-one times faster against the published DSG baseline, and they fall between two and one hundred twenty-seven microseconds per query.

Taro: It's exciting because it shows that we can achieve high-speed reasoning without needing massive, slow intermediate processing steps.

Dev: And as a final thought, we’re looking forward to seeing how they tune the update and merge paths to match the actual access patterns construction produces in future work.

Rosa: So, Yggdrasil provides a single queryable graph that is useful for both building and using it, offering real-time performance gains while staying compatible with current perception pipelines.

Dev: That’s our final word on this paper, summarizing the key aspects of "Yggdrasil: a Layer-First three dee Scene Graph for Real-Time Querying."

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

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

cs.RO

Submitted: 2026-09-29

Updated: 2026-09-29

Code: https://github.com/brdsdsu/yggdrasil

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: YGGDRASIL introduces a novel 3D scene graph architecture specifically designed to be efficient for both generation and consumption, addressing the latency costs incurred by existing perception

Key concepts

Layer-First Hierarchical Graph Structure: This is the core organization of YGGDRASIL. Instead of a simple stack, it organizes data into layers that form a Directed Acyclic Graph (DAG). Layers can parent multiple children, unlike previous methods, allowing for complex nesting relationships while maintaining an efficient structure for querying.
Generic Nodes and Edges: Unlike traditional scene graphs with fixed node types, YGGDRASIL uses generic nodes and edges. This means nodes can store any arbitrary information and features, rather than being restricted to predefined categories. Edges are also unbound by a specific vocabulary, offering greater flexibility for representing diverse 3D data.
Layer Isolation and Nesting: Layers in YGGDRASIL are mostly isolated, but they can nest precisely when one layer encompasses another. This structure is designed to handle hierarchical scene representations naturally. This allows the system to express existing pipeline formats while maintaining a queryable graph structure.
Direct Query Capabilities: The system supports various direct queries like pattern matching, nearest node searches, and field-of-view checks directly on the graph. These queries operate on the graph without needing to convert it into other formats or rebuild indexes, leading to very fast results.

Terminology

Core — 8× in this paper · explained in 2 episodes
Abstraction — 7× in this paper · explained in 1 episode
Downstream Tasks — 6× in this paper · explained in 2 episodes
Grounding — 5× in this paper · explained in 3 episodes
Benchmark — 4× in this paper · explained in 2 episodes
Directed Acyclic Graph — 4× in this paper
Graph Construction — 3× in this paper · explained in 3 episodes
Ablation — 2× in this paper · explained in 1 episode
Computer Vision and Pattern Recognition — 2× in this paper
Open Scene Graph — 2× in this paper
Point Clouds — 2× in this paper · explained in 2 episodes
Task Planning — 2× in this paper · explained in 2 episodes
Embeddings — 1× in this paper · explained in 2 episodes
Embodied AI — 1× in this paper · explained in 2 episodes

Summary

YGGDRASIL introduces a novel 3D scene graph architecture specifically designed to be efficient for both generation and consumption, addressing the latency costs incurred by existing perception pipelines that must work around their scene graphs. The core contribution is a layer-first hierarchical graph structure that natively answers positional and semantic queries downstream tasks issue at practical latency without requiring intermediate conversion steps.

Core Design Philosophy

YGGDRASIL is designed to be efficient for both generation and consumption: a layer-first hierarchical graph built from generic nodes, edges, and layers. It expresses existing pipeline representations—indoor or outdoor, flat or hierarchical—while natively answering semantic and spatial queries. Architecturally, it is a cluster of graphs, where each graph is a layer forming a Directed Acyclic Graph (DAG). Layers are almost pairwise isolated, with the exception of nesting relations where node n1 in layer l1 may nest node n2 in layer l2 exactly when l1 encompasses l2. This DAG structure allows a layer to parent more than one child, unlike the stack-based hierarchy of prior work.

Layer and Node Structure

The system is built from generic components:

Built from generic nodes, edges, and layers...

Nodes are generic in that, unlike scene graph technologies offering a fixed set of node types, allowing them to encode any information, carrying a list of features and an optional field for geometric coordinates. Edges are also generic in the same sense, bound to no predefined vocabulary and directed.

Query Capabilities

YGGDRASIL exposes a rich set of semantic and spatial queries directly on the graph, avoiding serialization or re-materialization:

Pattern Matching: Queries like nodes matching and nodes having retrieve nodes by specific features or keys.
Spatial and Traversal Queries: This family includes nearest nodes, nodes within radius, and the inter-layer query, nearest in subtree. These are supported by per-layer and per-node spatial indexes backed by a kd-tree.
Field-of-View Query: Given an observer, YGGDRASIL runs a fast frustum check over the nodes lying in the sub-tree of a root node r, allowing confinement of results to the agent's occupied room rather than the whole scene.

Performance and Evaluation

The evaluation uses three integrations spanning human trajectory prediction, object-goal navigation, and human-aware motion planning. The results demonstrate significant speedups:

Against a published DSG baseline, YGGDRASIL answers queries up to 121× faster...

Every query measured falls between 2 and 127 µs, which is three to five orders of magnitude inside the 200 ms keyframe budget a 3DSG consumer lives in. In one case study (LP2), YGGDRASIL removed up to 99% of the time each spends on its scene graph.

Design Trade-offs

The paper explores trade-offs across different implementations:

chocolate balances low memory consumption against reasonably fast query times, while mint and saffron buy further speed at the price of memory.

The choice between mint and saffron concerns "the upstream as much as the downstream: saffron’s fine-grained physical layer allows easier integration with graph generation, since a single point can be modified without rewriting an array, whereas mint keeps a memory footprint on par with dsg but lacks that precision for operations such as graph update and graph merge." The cost of this precision is visible in update latency.

Case Studies

YGGDRASIL was integrated into three pipelines:

LP2 (Long-Term Human Trajectory Prediction): Removes 99.6% of scene graph time by eliminating the need to rematerialize the graph as a NetworkX copy and rebuilds a KD-tree every iteration.
OSG (Zero-shot LLM-Guided Object-Search Navigation): Reduces total graph latency from 488.1 ms to 229.3 ms, showing gains in retrieving nodes by type and checking node types.
S3DSG (Social 3D Scene Graphs for Human-Aware Reasoning): Shows a speedup of 1.39 in the cost field query compared to the original, demonstrating that moving the indexes inside the scene graph gains performance rather than costing it.

Conclusion

YGGDRASIL provides a single queryable graph that serves both construction and consumption, offering substantial performance improvements while remaining compatible with existing perception pipelines. The authors note future work will focus on "Tuning update and merge paths to the access patterns construction actually produces, inferring schemas automatically, and supporting concurrent readers and writers.

Improvements for AI systems

Here are the specific improvements to AI systems based on the YGGDRASIL paper, and what these improved systems can achieve:

) Use YGGDRASIL as a native, single-store scene graph for both generation and consumption, eliminating the need for slow intermediate conversions or costly re-materializations of graphs during real-time control loops.

) Implement a layer-first Directed Acyclic Graph (DAG) architecture instead of a stack hierarchy to better express complex environmental relationships (like those in outdoor scenes where layers are not strictly ranked) and allow a single graph to simultaneously encode different types of information (positional, semantic, interaction).

) Integrate YGGDRASIL's native query APIs into perception pipelines for real-time spatial reasoning:

Perform high-speed nearest-neighbor searches (Q1a) for object detection and path planning using per-layer and node-level indexing.
Execute field-of-view checks (Q2) to constrain agent attention to the subscene relevant to the agent's current location, drastically reducing search space for navigation tasks.
Perform semantic retrieval (Q3) by querying labels directly on nodes or sets of nodes within specific layers, enabling rapid identification of objects carrying specific properties without iterating over the entire scene.

) Create perception systems that can dynamically adjust their memory footprint based on query needs:

Utilize the chocolate configuration to maintain a low memory cost while retaining decent query performance for common indoor tasks.
Employ the mint or saffron configurations when high precision is needed for graph updates (e.g., merging or adding new entities) without incurring the massive memory overhead of a fully dense, point-level physical layer.

) Enhance task planning and navigation systems (like SayPlan or SG-Nav) by leveraging YGGDRASIL's native query capabilities to ground LLM reasoning directly in the scene graph, leading to more accurate and temporally coherent object-goal navigation plans.

) Develop human-aware motion planning systems that can use YGGDRASIL's interaction layers (human-interaction layer) to explicitly model and avoid physical collisions or undesirable social interactions between agents based on their semantic relationships.

) Build robust SLAM/Mapping components that can leverage the layered structure for more efficient memory management and localized indexing, allowing for faster updates to the scene graph while maintaining consistency across different levels of abstraction (e.g., separating room-level positional data from object-level semantic data).