Self-driving cars need more than the painted shape of lanes. They need a lane graph: a directed map saying which lane segment legally continues into which. Current methods build this graph from multi-camera images in two steps. First they detect lane centerlines. Then they decide, for each pair of detected lanes independently, whether one connects to the other. This note argues that the pairwise step fails in a way that is predictable and that we can measure. The number of candidate pairs grows with the square of the number of lanes, but the number of true connections grows only linearly. As scenes get denser (big intersections) and detections get noisier (night, rain, glare), false connections therefore pile up faster than true ones. Both shifts attack the same weakness.
We propose two changes to the connectivity decision. The first replaces independent per-pair thresholding with a small global decoding step. Each lane end is allowed a limited, predicted number of successors, so the whole graph's connections are chosen jointly by an exact matching solver. The second makes the tolerance for "these endpoints touch" widen when the detector is uncertain about where an endpoint lies. We test the combination on two held-out shifts: denser graphs than seen in training, and real adverse weather and lighting. We also check whether synthetic image corruptions, the usual cheap stand-in for real bad conditions, predict how topology models behave in real bad conditions at all.
Core Claim
Suppose a scene has $n$ detected lane segments and a pairwise head has per-pair false-positive rate $p$. Suppose also that each lane has on average $c$ true successors. The expected precision of the predicted connections is then roughly
$$ \text{precision}(n) \approx \frac{c\,n}{c\,n + p\,n(n-1)}, $$
which falls like $1/n$, because false positives scale with the $n(n-1)$ ordered pairs while true edges scale with $n$. Corruption raises $p$ by blurring endpoint positions, so the two shifts compound. If instead each lane end may keep at most $d$ outgoing connections, false positives are capped at $d\,n$, and precision no longer decays with scene size. The claim is that a degree-constrained global decoder turns a size-sensitive failure into a size-stable one, and that it composes with uncertainty-aware tolerance under sensor degradation. The degree bound is predicted per endpoint, since forks need two or three successors and ordinary lanes need one.
This borrows a lesson from neural combinatorial optimization. There, FrontierCO shows that neural solvers collapse on larger and less regular graphs. For example, one neural TSP solver's gap grows from 0.72% to 77% on its hard set. Pairing learned edge scores with a classical search that does not depend on scale is what let Fu et al. extrapolate from 20–50-node training to 10,000 nodes. We apply that recipe of neural scores plus exact classical decoding to lane graphs. There the graphs are small enough per frame that exact solving is cheap, and the distribution shift comes from perception rather than from instance generation.
Research Program
The base model is a two-stage lane-topology pipeline in the style of TopoMLP. That work pairs Bézier-curve 3D lane detection with simple multi-layer perceptron connectivity heads, and argues that detection quality is the real bottleneck. On top of that model we add three pieces.
The first is a heteroscedastic endpoint head: it predicts a positional variance $\sigma_i^2$ for each lane's start and end points alongside the points themselves. This variance scales the Gaussian-like distance tolerance that TopoLogic introduced with a fixed width. TopoLogic showed that the fixed-width tolerance alone lifts TopoNet's lane-to-lane topology score from 10.9 to 22.3 without retraining. Our change is to make the width follow per-endpoint uncertainty, so that it can grow under corruption.
The second is a small head that predicts each endpoint's out-degree and in-degree bound $d_i$.
The third is the decoder. It takes pairwise log-odds $s_{ij}$ (fusing learned query similarity with the uncertainty-scaled geometric term). It then chooses connections $x_{ij}\in\{0,1\}$ to maximize $\sum_{ij} s_{ij}x_{ij}$, subject to the per-endpoint degree bounds and a heading-consistency mask. This is a bipartite b-matching between lane ends and lane starts. It is solved exactly by min-cost flow in milliseconds at per-frame graph sizes. At training time we use the pairwise loss unchanged. The decoder runs only at inference, which keeps the comparison with pairwise baselines clean.
The analysis side matters as much as the method. We stratify every result by ground-truth lane count and fit the precision-versus-$n$ curve to the form above. That tests the mechanism directly rather than only reporting aggregate scores. We also run the TopoMLP-versus-TopoLogic disagreement under controlled conditions. We feed ground-truth lane geometry perturbed by calibrated endpoint noise into each connectivity rule. This separates how much of the corrupted-condition drop comes from detection failure and how much from connectivity brittleness.
Baselines
The naive reference point is a pairwise head with one global threshold, trained on clean data and applied unchanged under every shift. We use TopoMLP's head for this. TopoMLP reports 41.2% OpenLane-V2 Score (OLS, the benchmark's aggregate score) on subset_A with a ResNet-50 backbone, versus 35.6% for TopoNet in the same paper. The OpenLane-V2 paper itself reports 35.4 OLS for TopoNet.
The strongest existing method on the specific question of connectivity robustness is TopoLogic. It reports lane-to-lane topology score (TOP_ll) 23.9 on subset_A and raises OLS from 39.8 to 44.1. It is the strongest competitor because it already targets endpoint shift, which is exactly the failure that corruption amplifies. We also include SMERF, which injects standard-definition map priors through cross-attention and reports an 83.8% relative gain in connectivity on TopoNet. It attacks the same problem from the detection side. The file reports only relative gains for SMERF, so we will measure absolute values ourselves.
We have no reported result from Lacuna for any of these methods on subset_B, on adverse-condition splits, or stratified by graph size. All shifted-condition numbers will be produced here.
Fairness works as follows. Every method uses the same detector backbone and weights where possible. Each gets the same training data and augmentation, and the same budget for tuning thresholds and tolerance widths on a clean validation split. Our decoder is also applied as pure post-processing on top of each baseline's own pairwise scores. That shows whether the gain transfers, mirroring TopoLogic's zero-shot post-processing experiment.
Three ablations isolate the ingredients. The first uses the decoder with fixed degree $d=1$ versus predicted degree. The second uses uncertainty-scaled tolerance without the decoder. The third uses the decoder without uncertainty scaling. Beating the baselines means two things. The method must match TopoLogic's clean TOP_ll within noise. It must also show a clearly flatter precision-versus-lane-count curve, and a smaller TOP_ll drop on the dense-graph and real-adverse splits, across three seeds.
Why not just…?
Why not just retune the connection threshold per condition? A single well-chosen threshold cannot follow the $1/n$ precision decay, because the right threshold depends on scene density, which varies frame to frame. We will test this directly. We will give thresholding an unfair advantage: an oracle threshold tuned separately for each lane-count bin and each corruption type on test labels. If this oracle matches the degree-constrained decoder, the honest conclusion is that density-adaptive thresholding is enough. The contribution would then shrink to the diagnosis and a cheap density-conditioned threshold. We would report it that way.
Why not just improve the detector, as TopoMLP argues? This is the most serious threat. TopoMLP's own ablations suggest that better detections dominate topology scores, and SMERF shows large connectivity gains from better long-range detection alone. The controlled noise-injection experiment settles it. With ground-truth geometry plus calibrated endpoint noise, detection quality is held fixed. If pairwise and constrained decoding then degrade identically as noise grows, the reasoning step is not the problem and the proposal fails. We will also run the decoder on top of SMERF's stronger detections to check whether the gains stack or vanish.
Why not just train with heavy synthetic corruption (domain randomization)? Two pieces of evidence argue against relying on it alone. S2R-Bench finds that synthetic corruptions badly misjudge real ones for object detection. Real LiDAR under glare performed 85% worse than simulations predicted, and synthetic misalignment was off by 81–82%. So augmentation tuned on synthetic corruption may not transfer. SPiDR shows that plain randomization without uncertainty awareness transfers less safely, though in control rather than perception. Corruption-augmented training is still cheap, so we include it as a baseline both with and without our decoder. If augmentation alone closes the real-adverse gap, the decoder's value is limited to the density shift.
Proposed Experiments
All experiments use OpenLane-V2. We report TOP_ll, lane detection score, lane-to-traffic-element topology score, and OLS, plus edge precision and recall per lane-count bin.
The size-extrapolation test mirrors the neural combinatorial optimization protocol. We train only on frames with at most the median number of ground-truth lanes and test on the densest quartile. We also evaluate on multi-frame merged local maps: several consecutive frames' predictions and labels aligned by ego pose, giving graphs several times larger than any training frame. For merged maps, cross-frame pairs are scored by the geometric term alone.
The sensor-shift test uses the nuScenes-derived subset_B. We identify real night and rain scenes from the nuScenes scene descriptions and use them as the real-adverse split. Clean frames receive matched synthetic fog, blur, glare, low-light and camera-extrinsic corruptions. If the real split turns out small, we report bootstrap confidence intervals rather than claim significance.
The fidelity check extends S2R-Bench's question from bounding boxes to topology. Across all methods, we compute the rank correlation between each method's TOP_ll drop under synthetic corruption and its drop on real adverse scenes. Low correlation would mean that synthetic-corruption leaderboards for topology are not a trustworthy proxy.
The decisive checks are three. First, clean-trained pairwise heads should show precision decaying roughly as $1/n$ across bins while the constrained decoder stays flat. Second, under controlled endpoint noise with ground-truth geometry, the gap between pairwise and constrained decoding should widen as noise grows. Third, on the real night/rain split, the decoder should reduce the TOP_ll drop relative to TopoLogic and corruption-augmented baselines by more than seed variance. If the first holds but the second does not, the method helps with density but not with sensor degradation. If neither holds, TopoMLP's detection-first view wins, and we will say so.
References
- FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization
- Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
- TopoMLP: A Simple yet Strong Pipeline for Driving Topology Reasoning
- TopoLogic: An Interpretable Pipeline for Lane Topology Reasoning on Driving Scenes
- OpenLane-V2: A Topology Reasoning Benchmark for Unified 3D HD Mapping
- Augmenting Lane Perception and Topology Understanding with Standard Definition Navigation Maps
- S2R-Bench: A Sim-to-Real Evaluation Benchmark for Autonomous Driving
- SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfer