Technical Summary: TrajDLM

Problem Statement

The generation of high-fidelity synthetic GPS trajectories is critical for transportation management, urban planning, and scenario simulation, particularly as privacy concerns restrict access to real-world mobility data. Existing deep generative models face a fundamental trade-off between efficiency and topological faithfulness:

• Continuous-space methods (e.g., DiffTraj, TrajFlow) enable fast generation but ignore road network topology, often producing physically implausible routes that deviate from valid roads.
• Topology-aware methods (e.g., TS-TrajGen, HOSER) represent trajectories as sequences of road segments and enforce connectivity via iterative search-based autoregressive decoding. While these ensure valid routes, the sequential nature of search algorithms significantly limits generation speed, making them unsuitable for large-scale simulations requiring millions of trajectories.

The paper identifies a gap for a model that can generate topologically coherent trajectories efficiently, without relying on slow, iterative search mechanisms.

Methodology

The authors propose TrajDLM, a framework that models trajectories as sequences of discrete road segments using a Block Diffusion Language Model (BDLM) backbone. The approach integrates three core components to bridge the gap between efficiency and topological constraints:

1. Block Discrete Denoising Diffusion Language Model (BD3-LM)

Instead of generating road segments token-by-token (autoregressive) or point-by-point (continuous diffusion), TrajDLM partitions trajectories into contiguous blocks of road segments.

• Process: It employs a discrete diffusion process (D3PM) where tokens are masked and iteratively denoised.
• Architecture: The model uses a semi-autoregressive structure where blocks are generated autoregressively, but tokens within a block are denoised in parallel. This allows for intra-block parallelism while maintaining long-range dependency modeling across blocks.
• Objective: The model is trained by minimizing the Noise-Conditioned Evidence Lower Bound (NELBO) over these blocks.

2. Road Network Encoder (RNE)

To address the limitation of standard language models treating tokens as independent units, TrajDLM replaces standard token embeddings with topology-aware representations.

• Graph Representation: The road network is modeled as a directed graph $G = \langle V, E \rangle$, where nodes are road segments and edges represent intersections.
• Embedding Construction: Road segment embeddings are constructed by concatenating learnable IDs with attributes (length, highway type, coordinates). Edge embeddings capture directional connectivity and steering angles.
• Fusion: A Graph Attention Network (GATv2) fuses segment and intersection embeddings to propagate topological context. These refined embeddings are projected into the LLM's input space, replacing standard token embeddings for road segments.

3. Topology-Constrained Sampling (TCS)

Since the diffusion process itself does not inherently enforce road connectivity, the authors introduce a sampling strategy to guarantee valid transitions during the reverse diffusion process.

• Adjacency Penalty: A log-space penalty matrix is applied to the model's logits. Transitions between non-adjacent road segments receive a penalty of $-\infty$, effectively zeroing their probability.
• Left-to-Right Decoding within Blocks: While diffusion is parallel, the authors adopt a left-to-right decoding scheme within each block during sampling. Each prediction conditions on the previously generated segment in that block, ensuring $(\hat{r}_{i-1}, \hat{r}_i) \in E$.
• Destination-Aware Termination: The generation is truncated at the first occurrence of the destination road segment to ensure the trajectory ends correctly.

Key Contributions

1. Topology-Aware Block Diffusion: TrajDLM is the first application of block diffusion language models to trajectory generation, combining semi-autoregressive block-wise discrete diffusion with road segment-based modeling.
2. Graph-Constrained Synthesis: The integration of a Road Network Encoder and Topology-Constrained Sampling enforces structurally coherent trajectory generation, ensuring all generated paths are valid within the road network.
3. High-Fidelity and Efficiency: The framework achieves strong performance on fine-grained local similarity metrics while being significantly faster than prior topology-aware methods.

Experimental Results

The model was evaluated on three city-scale datasets (Beijing, Porto, San Francisco) and tested for zero-shot transfer on the GeoLife dataset.

• Performance vs. Baselines: TrajDLM achieved the best or second-best performance on 13 out of 15 metrics across the three cities.
  • It outperformed HOSER (a state-of-the-art topology-aware baseline) on local metrics like Dynamic Time Warping (DTW) and Hausdorff distance, particularly in Porto and San Francisco.
  • On Beijing, it achieved the lowest DTW (3.98 vs. 5.98 for HOSER), though it remained competitive on global metrics.
  • It significantly outperformed continuous-space models (DiffTraj, TrajFlow) on local metrics, demonstrating the necessity of explicit topological modeling.
• Efficiency: TrajDLM was up to 2.8× faster than HOSER. Despite having a larger parameter count (0.6B vs. HOSER's 2–5M), the block diffusion paradigm allowed for parallel generation within blocks, avoiding the computational bottleneck of HOSER's iterative search.
• Zero-Shot Transfer: When trained on the Beijing taxi dataset and evaluated on GeoLife (diverse transport modes, different years), TrajDLM demonstrated strong cross-domain transferability, outperforming baselines on local metrics (Hausdorff and DTW).
• Ablation Studies:
  • Road Network Encoder: Removing the RNE caused significant performance drops, confirming the importance of topology-aware embeddings. Interestingly, a "Road only" encoder (without zone-level features) outperformed the full HOSER-style encoder, suggesting static road properties are more robust for generalization than trajectory-dependent zone aggregations.
  • Block Length: Optimal block length depends on dataset characteristics (e.g., $L'=32$ for shorter Beijing trips, $L'=64$ for longer Porto/SF trips).
  • Topology-Constrained Sampling: This component was crucial for improving global metrics (Distance), ensuring trajectories did not drift from the road network.

Significance and Claims

The paper claims that TrajDLM successfully bridges the efficiency-faithfulness trade-off in trajectory generation. By modeling trajectories as discrete road segments and leveraging the parallelism of block diffusion, the framework enables the generation of millions of high-fidelity, topologically valid trajectories at speeds previously unattainable for topology-aware models.

The authors highlight that this approach is particularly valuable for downstream applications like city-scale simulation and "what-if" planning, where both the statistical distribution of movement and the local geometric validity of routes are required. The work suggests that block-wise discrete diffusion is a scalable paradigm for accurate and efficient trajectory synthesis, capable of generalizing across domains and transportation modes without retraining.

Note: The authors acknowledge limitations, including the requirement for map-matched data (not raw GPS), scalability challenges for extremely large road networks (e.g., Sydney), and the lack of explicit temporal modeling in the current formulation.