Route Concepts as the Bottleneck: Intervenable, Calibrated Gap-Filling for Sparse Vehicle Trajectories

When a taxi's GPS reports a position only every three or four minutes, most of what we want to know happens between the pings. We do not know which streets it took, how fast it went, or whether it stopped. Current recovery models such as transformers and neural differential-equation models fill these gaps as black boxes. They output one path with no calibrated uncertainty and no handle a city analyst can grab. When one of them routes a car across a closed bridge, nobody can say why, and nobody can correct it except by retraining.

This proposal argues that most of the missing information in a sparse gap is a small discrete choice: which of a handful of plausible routes, and which kind of motion (cruising, congested, stopped). The rest is smooth motion that a Gaussian process describes well. A Gaussian process is a probabilistic model over functions with closed-form uncertainty. We build a model in which a neural network sees the trip context but may influence the recovered path only through human-readable route and motion concepts. Given those concepts, the continuous path is an exactly computable Gaussian process bridge along the chosen road. That bridge runs in linear time and never leaves the road network. The payoff is a recovered trajectory that is calibrated, physically plausible, and editable. Tell the model "not via this bridge" and the path and its uncertainty update in closed form. The empirical question is how much accuracy this bottleneck costs.

Core Claim

For sparse vehicle trajectories on road networks, most of the difference between black-box recovery and simple interpolation comes from two discrete per-gap decisions: a route choice among a few map-derived candidates, and a motion regime. We claim that a model forced to pass all learned context through these decisions loses little accuracy relative to the strongest black-box recoverer. Concretely, we expect it to land within a few percent of it on road-segment recovery accuracy. In return, it gains calibrated path-level uncertainty, zero off-road or impossible-maneuver outputs, and test-time intervention that behaves like the interventions in Concept Bottleneck Models.

The claim is falsifiable in both directions. The bottleneck may cost a large accuracy gap, which would show that recovery depends on information not captured by route and regime. Alternatively, a classical map-matching pipeline without learning may match it, which would show the learned concept predictor adds nothing.

Model

The model has three parts, and each borrows from a different line of work.

The first part generates candidate concepts. For each gap between consecutive pings, a k-shortest-path search on the road graph proposes $R$ candidate routes, and each is labelled by its road classes and key segments. Crossing a two-way intersection counts as a turn; U-turns are only allowed where the graph allows them. Motion regimes form a small fixed set. The training labels for both come free. We map-match the original dense trajectory before downsampling, which removes the annotation burden that the file identifies as the main weakness of concept bottlenecks.

The second part is the continuous motion model. Along candidate route $r$, position reduces to arc length $s(t)$, meaning distance travelled along that route. We model the state $(s, \dot s)$ with a constant-velocity stochastic differential equation, whose noise level and mean-speed drift depend on the motion regime. This is exactly the class of linear, white-noise-driven priors for which Batch Continuous-Time Trajectory Estimation as Exactly Sparse Gaussian Process Regression proves that the inverse covariance is block-tridiagonal. Consequences follow directly: inference is linear in the number of pings, and querying the path at any time costs constant work using only the two bracketing states. STEAM itself works in open Euclidean space. Restricting the process to a one-dimensional road route is our way of keeping its exact sparsity while respecting topology, which is Gap 1 in the file. The same "lift to position plus velocity to regain the Markov property" idea underlies Trajectory Inference with Smooth Schrödinger Bridges. That work operates on uncoupled population snapshots, not on individual noisy tracks on graphs.

The third part is the concept predictor, which is the bottleneck. A neural encoder sees the ping sequence, time of day, and road-graph features. It outputs probabilities $\pi_{g}(r, k)$ over route $r$ and regime $k$ for each gap $g$. As in Probabilistic Concept Bottleneck Models, the concepts carry uncertainty, but here that uncertainty is propagated into a continuous-time path distribution instead of a class label. The recovered trajectory is

$$p(x(t) \mid \text{pings}, \text{context}) = \sum_{\mathbf{c}} P(\mathbf{c} \mid \text{context}) \; \mathcal{GP}\big(x(t) \mid \text{pings}, \mathbf{c}\big),$$

where $\mathbf{c}$ is the sequence of per-gap route and regime concepts, and the second factor is the closed-form Gaussian process bridge along the routes in $\mathbf{c}$.

Adjacent gaps share the unobserved velocity at each ping, so they are coupled. The sum is therefore computed by a forward-backward pass over gaps, costing $O(G (RK)^2)$ for $G$ gaps, $R$ routes, and $K$ regimes. The concept predictor and the regime kernel parameters are trained jointly by maximizing this marginal likelihood on held-out dense points, plus a concept cross-entropy term.

The crucial design choice is that there is no side channel. The encoder cannot move the path except through $P(\mathbf{c})$. This rules out by construction the leakage and concept-bypass failures that the file lists for concept bottlenecks. The cost is a hard ceiling on accuracy, and measuring that ceiling is the point of the study.

Research Program

We will build the model above and study three questions.

The first question is the size of the accuracy price. We compare against black-box recovery at the downsampling rates used by Learning Spatio-Temporal Dynamics for Trajectory Recovery via Time-Aware Transformer (TedTrajRec). We also vary the size of the concept vocabulary. The ceiling can be measured directly with an oracle that knows the true concepts: the error of the Gaussian process bridge given true route and regime is the error attributable to the continuous part alone. We will report the gap between oracle-concept and predicted-concept performance separately from the gap to the black box.

The second question is whether intervention works. We simulate an analyst who corrects the most uncertain gap's route to the truth, then the next most uncertain, and so on, following the targeted-intervention protocol of ProbCBM. We plot path error against the number of corrections. We also simulate negative constraints such as a closed segment by removing a candidate route. We then check how often the updated path is correct, compared with a black box that has no mechanism for this edit at all.

The third question is whether the modular structure transfers across cities where black boxes do not. The concept predictor sees generic road features, and the kernels are regime-level physics. We therefore test training on Porto and evaluating on Chengdu with the kernels frozen. The file flags city coupling as an open problem for TedTrajRec.

Baselines

The naive reference point is linear interpolation between pings, together with shortest-path interpolation on the road graph at constant speed. Every learned method must beat these. They also show how much of the problem is solved by map topology alone.

The strongest classical competitor is hidden-Markov-model map matching with Viterbi route selection, followed by constant-velocity Gaussian process smoothing along the selected route. This is our model with the learned concept predictor replaced by a hand-set transition prior based on distance and turn penalties. It is the most dangerous baseline because it already has topology, kinematics, and some uncertainty. It gets the same candidate generator, the same kernels, and its penalty weights tuned by grid search on the validation split with the same number of trials we give our encoder's hyperparameters. Our model beats it only if it wins on route accuracy and path error at 16x downsampling, not merely at 8x.

The strongest black-box competitor is TedTrajRec. It combines a periodic, time-aware graph network with a closed-form continuous-depth neural ODE. Its paper reports a 9.37% relative gain in recovery accuracy and a 13.7% reduction in mean absolute error over prior baselines including MM-STGED, pooled across Porto, Shanghai-L, and Chengdu at 8x and 16x downsampling. The file gives no absolute accuracy value, so we found no reported absolute result on Lacuna for TedTrajRec on these datasets and will rerun it ourselves. Both it and our model will use the same splits, the same downsampling seeds, and a matched GPU-hour budget for tuning. We call the bottleneck "cheap" if our recovery accuracy is within three points of TedTrajRec's. We call it clearly better on the axes it targets if its 90% bands achieve near-nominal coverage while TedTrajRec, sampled with dropout, does not.

We add one generative competitor, DiffMove. It recovers trajectories with a conditional diffusion model, which is a generator that learns by gradually denoising random noise into samples. We evaluate it on calibration of sample-based bands.

Two ablations isolate the key ingredients. The first removes the bottleneck: the encoder also outputs a free residual displacement added to the Gaussian process path. The accuracy it gains is the price of interpretability, and the drop in intervention efficacy is what that price buys. The second replaces the route-restricted one-dimensional process with an open-plane STEAM prior. This isolates the value of putting probability mass only on roads.

Why not just…?

Why not just take TedTrajRec and add conformal prediction bands? Conformal prediction wraps any model with intervals that are guaranteed to contain the truth at a chosen rate, so it would give pointwise position intervals with valid marginal coverage. This is a real threat on the calibration axis alone, and we will run it. However, such bands are unions of discs around a single path. When two routes are both plausible, they cover the city block between those routes. They cannot express "route A or route B," and they offer no edit handle. The experiment that settles this compares interval width and the fraction of interval area that falls off-road, at matched coverage, alongside the intervention curves that conformal prediction cannot produce.

Why not just use classical map matching plus kinematic smoothing? This is the baseline most likely to embarrass the proposal, which is why it is the strongest competitor above. Our model differs from it in exactly one ingredient: the concept probabilities come from a learned context encoder rather than hand-set penalties. If the hidden-Markov pipeline matches us, the honest conclusion is that learned context does not help on these cities, and the contribution reduces to showing that such a pipeline is already competitive with TedTrajRec. Long gaps and non-shortest-path trips, such as commutes that avoid congestion, are where learned context should matter. We will therefore report results stratified by gap length and by whether the true route is the shortest.

Why not just add a concept-prediction head to a black-box recoverer and explain with attention or SHAP? A multitask head would predict route and regime alongside the path. Nothing forces the path to agree with the head, so editing the head changes nothing. Sum-of-Parts additionally shows that per-feature attributions degrade badly on correlated inputs, and consecutive pings are highly correlated. The residual-channel ablation is the direct test. It measures how often editing a concept actually moves the recovered path to the edited route: this should happen always for our model, and we expect it to happen rarely once a free channel exists.

Why not just use a generic scalable Gaussian process, such as inducing points or nearest neighbours, over space and time? Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression and sparse variational methods scale regression over millions of points. However, they work in Euclidean input space and put probability mass through buildings. Approximation-Aware Bayesian Optimization shows that a fixed inducing budget over-smooths sharp local structure such as turns. The open-plane ablation measures this cost directly.

Proposed Experiments

The main benchmarks are the Porto, Shanghai-L, and Chengdu taxi datasets with 8x and 16x downsampling, following TedTrajRec. These leave average gaps of 192 to 240 seconds. The dense originals provide ground-truth road segments, positions, and free concept labels. If the Kampala intermittent GPS data used by BERT4Traj is accessible, it serves as a secondary, lower-infrastructure test. There BERT4Traj reports 71.4% accuracy at 100-metre grid cells, and our output would be scored by discretizing it to the same cells.

We will measure recovery with road-segment accuracy, mean absolute error, and root-mean-square error in metres. Calibration is measured by the empirical coverage of 50% and 90% path bands and by negative log-likelihood on held-out dense points. Physical plausibility is measured as the rate of illegal turns and U-turns, the failure TedTrajRec concedes. Interpretability is measured by concept accuracy and by the intervention curves. Cost is measured as wall-clock inference per thousand trajectories.

Four checks decide the outcome. The bottleneck is vindicated if three results hold together. First, its recovery accuracy is within about three points of TedTrajRec at 16x downsampling. Second, correcting the single most uncertain gap cuts path error substantially more than correcting a random gap. Third, it beats the hidden-Markov map-matching pipeline on long, non-shortest-path gaps. The proposal fails in one of two ways: the oracle-concept model itself trails TedTrajRec, meaning the concept vocabulary is too coarse, or the learned encoder adds nothing over the hand-set prior. Either failure would be a clear, publishable answer about where the accuracy-interpretability trade-off actually lies for sparse mobility data.