Horizon Dependent Depth Scaling in Differentiable Planning

20 concepts11 papers1 proposal

When we use a classical algorithm like Value Iteration to find a path through a maze, information flows backward from the goal. In the first iteration, only the states immediately adjacent to the goal learn their optimal values. In the second iteration, that information propagates one step further out. If the shortest path from the start to the goal requires $H$ steps, the algorithm must run for at least $H$ iterations for the start state to receive any planning signal at all.

Differentiable planning networks attempt to embed this algorithmic structure directly into neural network architectures so they can learn to plan end-to-end. However, this creates a strict structural constraint: the depth of the neural network must scale linearly with the planning horizon of the task.

Understanding why this "depth wall" occurs, how it limits generalization, and how researchers are overcoming it is central to scaling neural planners to complex, real-world environments.

The Core Bottleneck: Local Receptive Fields

The fundamental alignment between planning iterations and network depth was popularized by Value Iteration Networks. In this architecture, Aviv Tamar et al. showed that a single step of the Bellman update can be mathematically mirrored by a convolutional layer followed by a max-pooling operation over the action channels.

Because standard convolution kernels operate locally (typically spanning a $3 \times 3$ or $5 \times 5$ neighborhood), information can only travel a few pixels per layer. As a result, the planning horizon is bounded by the network's receptive field. To propagate value signals from a distant goal back to the agent's current position, the architecture requires a deep stack of layers. As noted by Nantas Nardelli et al. in their work on Value Propagation Networks, this linear dependency means that long-range navigation tasks naturally demand deep, computationally expensive models.

Even when shifting away from explicit value iteration to alternative neural architectures, this spatial propagation limit persists. For instance, Tomas Kulvicius et al. developed a single-pass, fully convolutional network for one-shot multi-path planning in One-Shot Multi-Path Planning Using Fully Convolutional Networks in a Comparison to Other Algorithms. They observed that to maintain global connectivity and ensure information propagates across high-resolution maps, the network depth must still scale linearly with the spatial dimensions of the environment.

The Generalization Failure of Fixed-Depth Models

This horizon-proportional depth requirement introduces a severe vulnerability: fixed-depth neural planners fail to generalize to larger problem instances.

Imagine a network trained to solve $15 \times 15$ mazes using 20 convolutional layers. If this exact model is deployed on a $50 \times 50$ maze, it will fail completely for distant goals. Because the architecture is static, the value signal from a goal 40 steps away will physically never reach the agent's starting state within 20 layers. The agent is left blind, possessing no planning gradient to guide its initial actions.

This limitation is not just an empirical nuisance; it is a theoretical certainty for relational and graph-based planners as well. In What Planning Problems Can A Relational Neural Network Solve?, Jiayuan Mao et al. analyzed the circuit complexity of relational neural networks. They proved that to achieve perfect generalization as the number of objects or the causal chain length increases, the network depth must scale proportionally with the planning horizon. Fixed-depth models inherently lack the structural capacity to process the extended chains of reasoning required by larger environments.

Pushing the Depth Wall via Gating and Highway Connections

If solving long-horizon tasks requires thousands of layers or iterations, standard deep learning architectures collapse due to training instability, vanishing gradients, and optimization friction. To make horizon-proportional scaling viable, researchers have redesigned how gradients flow through these deep planning chains.

An early breakthrough came from reframing the rigid, hard-to-optimize updates of traditional planners as gated recurrent processes. In Gated Path Planning Networks and LSTM Iteration Networks: An Exploration of Differentiable Path Finding, Lisa Lee et al. replaced standard convolutional updates with LSTM-style gating mechanisms. These gates allow the network to learn how to pass information smoothly across long recurrent sequences, stabilizing the optimization process and drastically reducing sensitivity to initialization.

Traditional VIN Layer:  [Input] ---> [Conv + MaxPool] -------------------------> [Output] (Gradients vanish over deep horizons)

Gated/Highway Layer:    [Input] ---> [Conv + MaxPool] ---> [Gating/Highway] ---> [Output] (Information & gradients bypass smoothly)
                          |                                      ^
                          +--------------------------------------+

More recently, this paradigm has been scaled to extreme depths. Yuhui Wang et al. integrated reinforcement learning principles with specialized gating and exploration modules in Highway Value Iteration Networks, successfully training models with over 300 layers.

The authors pushed this boundary even further in Scaling Value Iteration Networks to 5000 Layers for Extreme Long-Term Planning. By introducing a dynamic transition kernel and an adaptive highway loss, they scaled value iteration networks to an unprecedented 5,000 layers. This extreme depth directly accommodates tasks requiring thousands of planning steps, proving that if the gradient highways are sufficiently stable, neural planners can maintain high success rates over massive spatial scales.

Bypassing the Depth Bottleneck

Rather than engineering deeper networks to survive the depth wall, another branch of research focuses on changing the underlying representation to bypass the linear depth requirement entirely.

State Aggregation and Larger Kernels

One approach is to accelerate the speed of information flow per layer. In Value Iteration Networks with Gated Summarization Module, Kenji Tei et al. utilized larger convolution kernels to expand the receptive field more aggressively. To prevent the loss of fine-grained details that large kernels can cause, they introduced a ConvLSTM-based "Gated Summarization" module to aggregate intermediate states across variable iteration depths, maintaining high accuracy on large maps without requiring thousands of layers.

Hierarchical Abstraction

Alternatively, we can compress the environment itself. Daniel Schleich introduced Abstract Value Iteration Networks (AVINs) in Value Iteration Networks on Multiple Levels of Abstraction. By mapping a large environment into multiple hierarchical levels of abstraction, the effective path length between the start and the goal is drastically shortened. Planning occurs over a compact, high-level graph, bypassing the computational overhead of fine-grained spatial propagation.

Global Attention Mechanisms

The most radical departure from local propagation is the use of Transformers. In Differentiable Spatial Planning using Transformers, Devendra Singh Chaplot et al. replaced local convolutional updates with global self-attention mechanisms. Because self-attention allows every pixel or state to communicate with every other state simultaneously regardless of distance, Spatial Planning Transformers (SPTs) can route information across an entire map in a single layer. This completely breaks the linear dependency between map diameter and network depth, offering a highly parallelizable alternative to traditional iterative planners.

Key Foundational Work

Value Iteration Networks (2017) — contributed 1 concept elements to this direction.
LSTM Iteration Networks: An Exploration of Differentiable Path Finding (2018) — contributed 1 concept elements to this direction.
Gated Path Planning Networks (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_iterative_planning_complexity_25d28849,
  title = {iterative planning complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-planning-complexity/rdr_25d28849011a4a2a8dcd35f8a5e64076},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_iterative_planning_complexity_25d28849_v1,
  title = {iterative planning complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-planning-complexity/rdr_25d28849011a4a2a8dcd35f8a5e64076/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake