Breaking the Quadratic Scaling Bottleneck in SLAM

34 concepts34 papers1 proposal

The fundamental challenge of Simultaneous Localization and Mapping (SLAM) is a chicken-and-egg problem: to build an accurate map, a robot needs to know its precise location; to determine its precise location, it needs an accurate map.

In classical Bayesian formulations of SLAM, this interdependency is managed by tracking the joint probability distribution of the robot's pose and all environmental landmarks. However, this joint tracking introduces a severe computational barrier. As a robot explores larger spaces, the number of tracked landmarks ($n$) grows, causing the computational and memory costs of traditional filtering methods to scale quadratically ($O(n^2)$). As noted by Andrew Davison et al., this quadratic explosion makes real-time processing impossible for large-scale environments without partitioning the map. Even in optimization-based frameworks like Graph-SLAM or Bundle Adjustment, global optimization scales non-linearly with the number of recorded poses, creating a performance wall during long-duration trajectories (Dieter Sibley et al.).

To make autonomous navigation scalable, researchers have developed several distinct paradigms to break this quadratic bottleneck. These methods work by exploiting the underlying structural properties of the SLAM problem: conditional independence, spatial locality, and hierarchical sparsity.


Factoring the Joint Distribution via Conditional Independence

The first major breakthrough in breaking the quadratic bottleneck came from recognizing a core structural property of SLAM: conditional independence.

If a robot's true path were known with absolute certainty, the observations of different landmarks would be completely independent of one another. The only reason landmark estimates become correlated in a standard filter is because they share the same uncertain robot pose as a common reference point.

Michael Montemerlo et al. leveraged this insight to create FastSLAM. By applying a Rao-Blackwellized particle filter, the authors factored the joint SLAM problem into two separate parts:

  1. A particle filter to estimate the robot's trajectory.
  2. A collection of separate, low-dimensional Kalman filters—one for each individual landmark.

Because each particle represents a specific, concrete guess of the robot's path, the landmarks become conditionally independent for that particle. Instead of updating a massive $n \times n$ covariance matrix, the algorithm updates $n$ independent $2 \times 2$ or $3 \times 3$ matrices. This factorization reduces the computational scaling from quadratic to logarithmic ($O(M \log n)$, where $M$ is the number of particles), allowing systems to map tens of thousands of features. The authors later introduced FastSLAM 2.0 (FastSLAM 2.0: An Improved Particle Filtering Algorithm for Simultaneous Localization and Mapping that Provably Converges), which incorporates the current sensor measurement into the particle proposal distribution. This modification mathematically ensures that the filter converges even with a single particle, yielding near constant-time updates.


Local Submaps and Relative Coordinate Frames

A second paradigm questions the necessity of a single, rigid global coordinate frame. In a global frame, updating a landmark on one side of a city mathematically forces an update to the robot's relationship with landmarks miles away. However, physical sensing is inherently local.

To exploit this locality, John J. Leonard et al. proposed an "inside-out" decomposition strategy using a network of overlapping submaps. By decoupling local feature estimates from global map positions, their framework allows a robot to perform constant-time updates ($O(1)$) within its immediate vicinity while maintaining provable consistency and global convergence.

[Global Frame (Quadratic Scaling)]
Robot Pose ───► Correlated to ───► [Landmark 1] [Landmark 2] ... [Landmark 10,000]
                                        ▲              ▲
                                        └───────┬──────┘
                                         Dense Covariance Matrix

[Relative/Submap Frame (Constant Time)]
Robot Pose ───► [Local Submap A] ───► Relative Link ───► [Local Submap B]
                     │                                         │
              ┌──────┴──────┐                           ┌──────┴──────┐
        [Landmark 1]  [Landmark 2]                [Landmark 3]  [Landmark 4]

This relative philosophy was extended to optimization-based SLAM by Dieter Sibley et al. through Adaptive Relative Bundle Adjustment (RBA). Instead of optimizing poses against a global origin, RBA parameterizes the world as a graph-based relative manifold. When the robot moves and takes measurements, the optimization is mathematically restricted to the local neighborhood. Because errors are parameterized relatively rather than globally, loop closures and map updates can be processed in constant time, preventing the cubic or quadratic scaling typical of standard bundle adjustment.


Sparsification and Information Thinning

Rather than restructuring the coordinate system, another approach directly thins out the dense web of correlations within the filter itself.

Mark A. Paskin introduced this concept via the Thin Junction Tree Filter (TJTF) in Thin Junction Tree Filters for Simultaneous Localization and Mapping. The algorithm represents the joint distribution as a graphical model called a junction tree. As the robot explores, the tree naturally thickens, which corresponds to rising computational complexity. The TJTF introduces a principled "thinning" operation that identifies and removes weak or redundant correlations, bounding the treewidth of the model. This guarantees linear—and often constant—time updates while preserving the critical long-range correlations required for accurate loop closure.

From an estimation perspective, a similar optimization can be achieved by freezing old data. Patrick Geneva developed SEVIS (An Efficient Schmidt-EKF for 3D Visual-Inertial SLAM), which utilizes the Schmidt Kalman Filter formulation. When environmental landmarks become mature and well-estimated, continuing to update their cross-correlations with the robot's current state drives quadratic computational growth. SEVIS treats these mature features as "nuisance parameters." The filter stops updating the landmarks' positions but mathematically retains their cross-covariance terms. This prevents the state space from expanding while still accounting for the landmarks' underlying uncertainty, dropping the computational complexity from $O(n^2)$ to $O(n)$.


Keyframe Selection and Hierarchical Abstraction

In modern Graph-SLAM frameworks, the factor graph expands continuously as the robot operates. To maintain real-time performance, systems must actively manage graph density by selecting what data to keep and how to represent it.

One common approach is to bound the optimization to a local sliding window. For example, the LIO-SAM framework developed by Tixiao Shan et al. optimizes robot poses against a local window of "sub-keyframes" rather than the entire global map. This isolates the real-time state estimation from the scale of the overall environment.

To manage the global map efficiently, systems can use information theory to prune redundant nodes. Yuan Lin et al. developed InfoLa-SLAM, which employs an information-theoretic keyframe selection mechanism. By calculating the information gain of incoming sensor data, the system discards frames that do not contribute novel geometric constraints, significantly reducing the computational load of pose estimation and map refinement.

[Raw Sensor Stream] ──► [Information Gain Filter] ──► [Semantic Abstraction] ──► [Hierarchical Graph]
  (High Data Rate)        (Discards Redundancy)          (Groups into Rooms)       (10x Faster Optimization)

Taking abstraction further, Hriday Bavle et al. introduced S-Graphs 2.0, which organizes the factor graph into a hierarchical semantic structure consisting of four layers: Keyframes, Walls, Rooms, and Floors. Instead of optimizing thousands of individual point-to-point constraints, the system optimizes higher-level semantic relationships. Grouping low-level geometric features into abstract semantic entities compresses the underlying factor graph, allowing the system to run up to 10x faster than flat baselines in complex, multi-floor environments.


Alternative Map Representations

Finally, the quadratic bottleneck can be bypassed by changing the underlying map representation entirely, moving away from explicit landmark tracking.

  • View-Based Skeletons: Kurt Konolige demonstrated in View-based maps that a robot can represent the environment as a sparse "skeleton" of stereo views rather than a dense 3D point cloud. By combining vocabulary-tree-based place recognition with geometric filters, the system eliminates the need to maintain a growing state space of discrete features, enabling instant relocalization and efficient loop closure over kilometer-scale trajectories.
  • Deformable Continuous Surfaces: Rather than relying on rigid pose graphs that expand with every step, Chanoh Park introduced a map-centric approach in Elasticity Meets Continuous-Time: Map-Centric Dense 3D LiDAR SLAM. By treating the robot's trajectory as a continuous function and the map as a deformable, elastic surface, the system decouples loop closure optimization from trajectory length, neutralizing the computational overhead typical of long-duration missions.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_scaling_in_slam_73a49401,
  title = {computational scaling in SLAM},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scaling-in-slam/rdr_73a49401e2ed422a98833b9ca53dbea0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_scaling_in_slam_73a49401_v1,
  title = {computational scaling in SLAM},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scaling-in-slam/rdr_73a49401e2ed422a98833b9ca53dbea0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake