Learned Spatial Partitions as Interpretable Trajectory Models

Many systems that forecast where an aircraft, vehicle or animal will go first chop continuous space into a fixed hierarchy of grid cells, such as Google's S2 or Uber's H3 hexagons. The cells are then treated like words, and a sequence model predicts the next cell. This is convenient and it looks readable, since "the plane moves from cell A to cell B" is something a person can check. It also throws away information, and the cell boundaries are set by a global standard that has nothing to do with the data. The clearest symptom comes from aircraft forecasting. Coarse H3 cells (resolution 5) gave lower error than finer cells, because fine cells left most of them nearly empty (Soares et al.). The best 30-minute error, about 32 km, was still far outside the 9.26 km aviation separation margin.

We propose to stop treating the spatial index as fixed preprocessing and to learn it as the model. The model is a small hierarchical partition of space, grown split by split on continuous coordinates. A split is kept only if it improves held-out forecasts. Each region carries two things: an explicit table of transition probabilities to other regions, and a linear model that turns the aircraft's exact position and velocity inside the region into its next position. The partition is the explanation, and it is complete and exact. Because the regions keep continuous information, the model should avoid the coarse-versus-fine inversion. Because regions are added only where they help prediction, the number of regions should stay small enough for a person to read.

Core Claim

At a matched number of spatial regions, a partition chosen for predictive value, with linear dynamics inside each region, will forecast more accurately than any fixed S2/H3 resolution. Its error will fall steadily as regions are added instead of rising at fine resolutions. It will do this while remaining a model whose every prediction can be traced to a named region, a transition probability and a few linear coefficients. The claim is about a specific failure: fixed hierarchical indexes lose information both at cell boundaries and inside cells. The claim is not that a glass-box model can beat continuous deep networks. We expect it will not, and we measure how large that gap is.

How This Relates to Prior Work

Three groups of papers play different roles here.

The first group motivates the problem. These papers tokenize trajectories with fixed hierarchical grids and report that discretization limits them.

  • STARE feeds S2 tokens to a Transformer and notes that it cannot capture motion inside a cell and that its vocabulary grows quickly as cells shrink.
  • Soares et al. document the resolution inversion and suggest, without implementing it, converting tokens back to continuous paths.

Both models are opaque, and both keep the grid fixed. We change the grid itself.

The second group supplies the method. These papers fit interpretable trees directly on continuous features instead of on pre-binned ones.

  • CLARITree grows piecewise-linear regression trees with one-step lookahead. It makes lookahead affordable with rank-one Cholesky updates, a fast way to refit each candidate split's linear model.
  • ArborEnum shows that pre-binning continuous features hides near-optimal trees and conceals disagreement among equally good models.

Both were developed only for tabular data. We reuse CLARITree's split search with spatial coordinates as the split variables and a forecasting target at the leaves. CLARITree's cost grows with the fourth power of the feature count, which is harmless here because the per-region state has about six dimensions.

The third group constrains the design.

  • Althoff et al. show that fixed-grid Markov chains give fast, readable risk estimates. They also become over-conservative when behavior departs from their assumed dynamics, which argues for learning the dynamics inside each cell from data.
  • TPK shows that adding physical structure removes kinematically impossible predictions at a small accuracy cost, so we should expect, and report, a similar cost.
  • Spatial concept bottlenecks such as WHE-CBM keep spatial maps of human-defined concepts for images. We deliberately do not build a concept bottleneck. For trajectories, the region is already the concept, and adding a neural concept layer would bring back the risk that the network smuggles hidden shortcuts through the concept values.

Research Program

The state of an agent at time $t$ is $s_t = (p_t, v_t)$, where $p_t$ is position and $v_t$ is velocity. The model is a binary tree. Each internal node splits a region along one coordinate at a continuous threshold, so the result is still a nested hierarchy, like S2 or H3, but with data-chosen boundaries. Each leaf $r$ stores two things. The first is a transition distribution $\pi_r$ over the leaf the agent will occupy at horizon $\Delta$. The second is a linear predictor $\hat p_{t+\Delta} = W_r s_t + b_r$. Trees are grown greedily with lookahead to minimize

$$ \mathcal{L} = \frac{1}{N}\sum_{i=1}^{N} \lVert p^{(i)}_{t+\Delta} - \hat p^{(i)}_{t+\Delta} \rVert^2 + \lambda\,|R|, $$

where $N$ is the number of training samples and $|R|$ is the number of leaves. The penalty $\lambda$ trades accuracy against size, and sweeping it traces an accuracy-versus-regions curve. A split is accepted only if it reduces error on a held-out fold. This is the mechanism expected to prevent the inversion: a fixed grid forces sparse cells into existence, whereas a learned tree simply does not create them.

For long horizons we will compare two forecasting modes. In the direct mode, each region regresses the 30-minute displacement in a single step. In the rollout mode, the per-step model is applied repeatedly. This separates errors that compound over steps from errors caused by the partition itself.

As a secondary analysis, we will take the ArborEnum view of model multiplicity. We will collect many partitions whose loss is within a small margin $\epsilon$ of the best, and measure two quantities. The first is how often these near-equivalent models assign the same flight to different regions. The second is how often they disagree on its forecast. We will compare that disagreement with the disagreement produced by simply shifting the origin of a fixed H3 grid. This tests how much a readable spatial explanation depends on arbitrary boundary placement. No study in the file has measured this for spatial tokenization.

Baselines

The naive reference point is constant-velocity dead reckoning: the aircraft's last velocity carried forward. It has no parameters and needs no tuning. Any model that fails to beat it at 30 minutes has learned nothing useful about the airspace. There is no reported result on Lacuna for dead reckoning on the LFBO data, so we will compute it ourselves.

The strongest existing discrete method on our main benchmark is the H3 resolution-5 CVAE-LSTM of Soares et al.. It reports a best global spatial error of approximately 32 km at a 30-minute horizon with 60-second sampling on the OpenSky LFBO dataset. We will reimplement it on the same date split, sampling rates and error measures (MAE and RMSE in ECEF coordinates, the Earth-centered Cartesian frame). We will first confirm that our reimplementation lands near 32 km before treating any comparison as valid.

Beating this baseline means lower 30-minute error with a partition of comparable or smaller size than the number of active H3 cells. As a stretch target, we will report whether any variant falls inside 9.26 km.

The strongest repair a reviewer would propose is to keep the fixed H3 grid and attach a continuous offset head, in the style of the Offset-guided Network. That network added a regression branch to coarse keypoint heatmaps and reached 74.0 mAP on COCO test-dev. We will add such a head to the Soares model at every H3 resolution, using the same hyperparameter search budget and GPU hours as our method.

Two ablations isolate the key ingredient, which is choosing boundaries by predictive gain.

  • Fixed H3, same leaves: fixed H3 cells, each with exactly our linear leaf model and transition table. This removes the learned partition and keeps everything else.
  • Density quadtree, same leaves: a quadtree that splits wherever the data is dense, as in DeepSPACE, again with the same leaves. This is adaptive, but its splits are driven by density rather than forecast gain.

A third ablation is a piecewise-constant tree on raw coordinates with no linear leaves. It measures how much of any improvement comes from modeling motion inside each cell.

Finally, an unconstrained LSTM on raw continuous coordinates, tuned with the same budget, gives the accuracy ceiling on LFBO. We will report the size of the gap to it rather than hide it.

Why not just…?

Why not just pick the best fixed H3 resolution on validation data? This is what Soares et al. effectively did. It still left them at about 32 km, because one resolution has to serve both dense approach corridors and empty en-route airspace. Our accuracy-versus-regions curve answers the question directly. If the fixed-resolution points lie on or below our learned-partition curve at matched region counts, the idea fails and we will say so.

Why not just add an offset head to the fixed grid? This is the most serious threat. It may recover most of the error lost inside cells, and it keeps a cell vocabulary. Its weakness for our question is that the offset comes from an opaque network. It also leaves the boundaries where the global grid put them, so boundary sensitivity and the sparsity that causes the inversion remain. If the offset-augmented CVAE-LSTM matches our accuracy, the honest conclusion is that learning the partition buys readability and stability but not accuracy. The multiplicity analysis would then be what decides whether learned boundaries are worth having.

Why not just use an adaptive quadtree built from data density? Density-adaptive splitting already addresses sparsity. Dense regions are not, however, necessarily the regions where finer boundaries improve forecasts. Holding approach paths apart, for example, may require splits in sparse airspace. The density-quadtree ablation, which shares our leaf models exactly, tests whether splitting on predictive gain matters or whether density alone suffices.

Why not just use a continuous black box and explain it afterwards? TPK reports that the unconstrained HPTR trajectory model on Argoverse 2 produced at least one physically impossible step in 88% of trajectories. It also reports that attention weights can point to irrelevant agents. Such post-hoc explanations are therefore not faithful accounts of how the model reasons. Our model needs no explanation step, because the prediction is a region, a transition probability and a linear map.

Proposed Experiments

The main benchmark is the OpenSky LFBO ADS-B dataset, using the sampling intervals and 30-minute horizon of Soares et al.

The first decisive check plots spatial error against the number of regions for our model, for fixed H3 resolutions with and without offset heads, and for the density quadtree. Our model must lie below all of them, and its curve must fall monotonically where the fixed-grid curve turns upward.

The second check compares the direct and rollout modes, separating compounding error from partition error.

The third check reports multiplicity among near-optimal partitions versus multiplicity among shifted H3 grids. The prediction is that learned boundaries disagree less, because they sit where the data forces a distinction. If they disagree as much as arbitrary shifts do, region-level explanations are not trustworthy and that is itself a finding.

As a transfer test of generality and cost, we will fit the same method to Argoverse 2 vehicle motion. There, QCNet reports a minFDE6 of 1.19 m, the smallest final-position error over six forecast trajectories. We expect a substantial gap to QCNet and will report it alongside the kinematic infeasibility rate, the share of trajectories with at least one physically impossible step, against HPTR's 88% and TPK's 0%. The aim is to show where a fully readable spatial model sits on the accuracy-interpretability curve in dense, interactive scenes, not to claim a win.