# Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning

arXiv: https://arxiv.org/abs/2607.05359 · HTML: https://mlsanity.com/paper/2607.05359/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 35 references that are in the map.
- First posted on arXiv 6 Jul 2026.

## Builds on (most cited first, 30 of 30)

- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [ScanNet: Richly-annotated 3D Reconstructions of Indoor Scenes](https://mlsanity.com/paper/1702.04405/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [DUSt3R: Geometric 3D Vision Made Easy](https://mlsanity.com/paper/2312.14132/) (2023)
- [VGGT: Visual Geometry Grounded Transformer](https://mlsanity.com/paper/2503.11651/) (2025)
- [Grounding Image Matching in 3D with MASt3R](https://mlsanity.com/paper/2406.09756/) (2024)
- [Continuous 3D Perception Model with Persistent State](https://mlsanity.com/paper/2501.12387/) (2025)
- [MonST3R: A Simple Approach for Estimating Geometry in the Presence of Motion](https://mlsanity.com/paper/2410.03825/) (2024)
- [Fast3R: Towards 3D Reconstruction of 1000+ Images in One Forward Pass](https://mlsanity.com/paper/2501.13928/) (2025)
- [Learning to (Learn at Test Time): RNNs with Expressive Hidden States](https://mlsanity.com/paper/2407.04620/) (2024)
- [Titans: Learning to Memorize at Test Time](https://mlsanity.com/paper/2501.00663/) (2024)
- [Neural RGB-D Surface Reconstruction](https://mlsanity.com/paper/2104.04532/) (2021)
- [3D Reconstruction with Spatial Memory](https://mlsanity.com/paper/2408.16061/) (2024)
- [Global Structure-from-Motion Revisited](https://mlsanity.com/paper/2407.20219/) (2024)
- [ReFusion: 3D Reconstruction in Dynamic Environments for RGB-D Cameras Exploiting Residuals](https://mlsanity.com/paper/1905.02082/) (2019)
- [Streaming 4D Visual Geometry Transformer](https://mlsanity.com/paper/2507.11539/) (2025)
- [Test-Time Training Done Right](https://mlsanity.com/paper/2505.23884/) (2025)
- [TTT3R: 3D Reconstruction as Test-Time Training](https://mlsanity.com/paper/2509.26645/) (2025)
- [Point3R: Streaming 3D Reconstruction with Explicit Spatial Pointer Memory](https://mlsanity.com/paper/2507.02863/) (2025)
- [STream3R: Scalable Sequential 3D Reconstruction with Causal Transformer](https://mlsanity.com/paper/2508.10893/) (2025)
- [InfiniteVGGT: Visual Geometry Grounded Transformer for Endless Streams](https://mlsanity.com/paper/2601.02281/) (2026)
- [ZipMap: Linear-Time Stateful 3D Reconstruction via Test-Time Training](https://mlsanity.com/paper/2603.04385/) (2026)
- [LongStream: Long-Sequence Streaming Autoregressive Visual Geometry](https://mlsanity.com/paper/2602.13172/) (2026)
- [Test3R: Learning to Reconstruct 3D at Test Time](https://mlsanity.com/paper/2506.13750/) (2025)
- [VGG-T3: Offline Feed-Forward 3D Reconstruction at Scale](https://mlsanity.com/paper/2602.23361/) (2026)
- [tttLRM: Test-Time Training for Long Context and Autoregressive 3D Reconstruction](https://mlsanity.com/paper/2602.20160/) (2026)
- [TTSA3R: Training-Free Temporal-Spatial Adaptive Persistent State for Streaming 3D Reconstruction](https://mlsanity.com/paper/2601.22615/) (2026)
- [STAC: Plug-and-Play Spatio-Temporal Aware Cache Compression for Streaming 3D Reconstruction](https://mlsanity.com/paper/2603.20284/) (2026)
- [HorizonStream: Long-Horizon Attention for Streaming 3D Reconstruction](https://mlsanity.com/paper/2605.23889/) (2026)
- [MeMix: Writing Less, Remembering More for Streaming 3D Reconstruction](https://mlsanity.com/paper/2603.15330/) (2026)

## Abstract (arXiv)

Planning under uncertainty in continuous domains is essential for autonomous systems, yet computationally demanding. Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular, but their branching structure can require sampling budgets that grow exponentially with lookahead depth in the worst case. From a tree perspective, continuous state or action spaces become especially challenging, since the planner must decide where to search in an infinite branching hierarchy. We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions, rather than sampling separate successors for each candidate action. This branch-free graph exposes large GPU-friendly batches, while using heuristics to focus computation. We prove finite-sample performance guarantees for GSS covering full-rank or low-rank generative simulators via smoothed backups, and discrete or sampled continuous action spaces. Under suitable overlap, regularity, and action-coverage conditions, these bounds have polynomial dependence on the planning horizon, formalizing when shared futures can avoid the exponential horizon dependence of tree-shaped sparse sampling. We demonstrate continuous-control simulations where GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance, supporting no-branching graph planning as a complementary design principle for online control.