TOPO-Bench: An Open-Source Topological Mapping Evaluation Framework with Quantifiable Perceptual Aliasing

Jiaming Wang1* Jizhuo Chen1 Diwen Liu1 Jiaxuan Da1 Jiamo Hu1 Zhiwei Xue1 Linh Kästner1 Harold Soh1,2*

1School of Computing, National University of Singapore

2Smart Systems Institute, National University of Singapore

*Corresponding authors: {jiaming, harold}@comp.nus.edu.sg

Overview Video

Abstract

Topological mapping offers a compact and robust representation for navigation, but progress in the field is hindered by the lack of standardized evaluation metrics, datasets, and protocols. Existing systems are assessed using different environments and criteria, preventing fair and reproducible comparisons. Moreover, a key challenge—perceptual aliasing—remains under-quantified, despite its strong influence on system performance. We address these gaps by (i) formalizing topological consistency as the fundamental property of topological maps and showing that localization accuracy provides an efficient and interpretable surrogate metric, and (ii) proposing the first quantitative measure of dataset ambiguity to enable fair comparisons across environments. To support this protocol, we curate a diverse benchmark dataset with calibrated ambiguity levels, implement and release deep-learned baseline systems, and evaluate them alongside classical methods. Our experiments and analysis yield new insights into the limitations of current approaches under perceptual aliasing. All datasets, baselines, and evaluation tools are fully open-sourced to foster consistent and reproducible research in topological mapping.

Formal Proof: Localization Infers Map Success

Definitions and Assumptions

Let \(\mathcal{G}_t = (\mathcal{V}_t, \mathcal{E}_t)\) be the topological graph after \(t\) updates.

Let \(\mathrm{dist}_{\mathcal{G}_t}(u, v)\) denote the shortest-path hop distance between nodes \(u\) and \(v\) in \(\mathcal{G}_t\).

Let \(\mathrm{dist}_R(u, v)\) denote the geodesic route distance between the physical locations represented by nodes \(u\) and \(v\).

We assume an additive update rule: the graph only grows over time, \[ \mathcal{V}_t \subseteq \mathcal{V}_{t+1}, \qquad \mathcal{E}_t \subseteq \mathcal{E}_{t+1}. \] That is, nodes and edges are only added, never deleted or rewired.

We also assume an edge-length regular policy \(P\): every edge \((x,y)\) ever added to the graph (whether a consecutive edge or a shortcut edge created upon a revisit) satisfies \[ \mathrm{dist}_R(x,y) \le \kappa \mu_e, \] for some constants \(\kappa \ge 1\) and \(\mu_e > 0\).

Fix a physical route-distance threshold \(d > 0\). We choose an integer hop budget \(n \ge 1\) such that \[ n \kappa \mu_e \le d. \] A convenient admissible choice is \[ n := \left\lfloor \frac{d}{\kappa \mu_e} \right\rfloor, \] which requires \(d \ge \kappa \mu_e\). Intuitively, one cannot demand a 1-hop guarantee at a physical scale smaller than one permissible edge.

Policy-instantiated edge opportunities. For each time \(t\), let \(\Omega_{P,\le t}\) denote the cumulative set of edge opportunities actually surfaced by policy \(P\) up to time \(t\). Concretely, at each update this contributes exactly one pair:

  1. the accepted revisit pair in the correct-accept case, or
  2. the consecutive exploration pair in the correct-reject case.

Correct localization at every timestep means that at each update the system does exactly one of the following:

  1. Correct accept (revisit): it correctly identifies a previously mapped place and realizes the surfaced revisit opportunity by adding the corresponding revisit edge.
  2. Correct reject (novel region): it correctly rejects all prior nodes in a novel region, creates a new node, and realizes the surfaced exploration opportunity by adding the consecutive edge from the previous node to the new node.

Theorem

Assume the additive update rule, edge-length regularity, and correct localization at every timestep. Let \(n \ge 1\) satisfy \(n\kappa\mu_e \le d\). Then for every \(t \ge 0\), the graph \(\mathcal{G}_t\) satisfies:

\[ \text{(Edge Precision)} \qquad \mathrm{dist}_{\mathcal{G}_t}(u,v) \le n \;\Longrightarrow\; \mathrm{dist}_R(u,v) \le d, \]

\[ \text{(Policy-conditioned Edge Recall)} \qquad (u,v)\in \Omega_{P,\le t} \text{ and } \mathrm{dist}_R(u,v)\le d \;\Longrightarrow\; \mathrm{dist}_{\mathcal{G}_t}(u,v)\le n. \]

Proof

Lemma (Hop-to-route bound): Suppose every edge in a graph \(H\) satisfies \(\mathrm{dist}_R(x,y)\le \kappa\mu_e\). If \(\mathrm{dist}_{H}(u,v)\le n\), then \(\mathrm{dist}_R(u,v)\le d\).
Proof: Let \(u=v_0, v_1, \dots, v_\ell=v\) be a shortest hop path in \(H\), so \(\ell \le n\). By edge-length regularity, \[ \mathrm{dist}_R(v_{i-1}, v_i) \le \kappa\mu_e \qquad \text{for all } i=1,\dots,\ell. \] Concatenating these traversable routes yields a feasible route from \(u\) to \(v\) of length at most \[ \sum_{i=1}^{\ell}\mathrm{dist}_R(v_{i-1}, v_i) \le \ell \kappa\mu_e \le n\kappa\mu_e \le d. \] Since \(\mathrm{dist}_R(u,v)\) is the shortest such route distance, it follows that \[ \mathrm{dist}_R(u,v)\le d. \] \(\square\)

Edge Precision: Fix any \(t \ge 0\) and any \(u,v \in \mathcal{V}_t\) with \(\mathrm{dist}_{\mathcal{G}_t}(u,v)\le n\). Every edge in \(\mathcal{G}_t\) satisfies \(\mathrm{dist}_R(\cdot,\cdot)\le \kappa\mu_e\), so the lemma applies directly and gives \[ \mathrm{dist}_R(u,v)\le d. \] Since \(t\) was arbitrary, Edge Precision holds for all \(t\ge 0\).

Policy-conditioned Edge Recall: We prove this by induction on \(t\).

Base Case (\(t=0\)):
At \(t=0\), the graph is empty or contains only the initial node. There are no nontrivial policy-instantiated edge opportunities, so the recall statement is vacuous.

Inductive Hypothesis:
Assume that at time \(t\), every pair \((u,v)\in \Omega_{P,\le t}\) with \(\mathrm{dist}_R(u,v)\le d\) satisfies \[ \mathrm{dist}_{\mathcal{G}_t}(u,v)\le n. \]

Inductive Step (\(t \rightarrow t+1\)):
Consider the update at time \(t+1\). Because localization is correct, exactly one new policy-instantiated opportunity appears, and there are two cases.

Case 1: Correct Accept (Revisit)

The policy correctly identifies a previously mapped node \(r \in \mathcal{V}_t\) corresponding to the current place, and realizes the surfaced revisit opportunity by adding the revisit edge \((c,r)\), where \(c\) denotes the node representing the current observation at time \(t+1\). Therefore \[ \mathrm{dist}_{\mathcal{G}_{t+1}}(c,r)=1\le n. \] So the newly instantiated opportunity satisfies the recall condition.

Now consider any previously instantiated pair \((u,v)\in \Omega_{P,\le t}\). Because updates are additive, shortest-path hop distances between existing nodes cannot increase: \[ \mathrm{dist}_{\mathcal{G}_{t+1}}(u,v)\le \mathrm{dist}_{\mathcal{G}_t}(u,v). \] By the inductive hypothesis, every old pair with \(\mathrm{dist}_R(u,v)\le d\) already satisfied \(\mathrm{dist}_{\mathcal{G}_t}(u,v)\le n\), and hence still satisfies \[ \mathrm{dist}_{\mathcal{G}_{t+1}}(u,v)\le n. \] Thus the recall statement holds for all pairs in \(\Omega_{P,\le t+1}\).

Case 2: Correct Reject (Novel Region)

The policy correctly determines that the current place is novel, creates a new node \(u \notin \mathcal{V}_t\), and realizes the surfaced exploration opportunity by adding the consecutive edge \((p,u)\), where \(p\) is the previous node on the trajectory. Therefore \[ \mathrm{dist}_{\mathcal{G}_{t+1}}(p,u)=1\le n. \] So the newly instantiated opportunity satisfies the recall condition.

As in Case 1, all previously instantiated opportunities remain within \(n\) hops because additive updates cannot increase shortest-path hop distances. Hence the recall statement also holds for all pairs in \(\Omega_{P,\le t+1}\).

By induction, Policy-conditioned Edge Recall holds for every \(t\ge 0\). Combining this with the direct Edge Precision argument proves the theorem. \(\blacksquare\)

Discussion: Effect of Non-zero Localization Error

The theorem above is an idealized invariance result: if localization decisions are always correct, then the map maintains Edge Precision and Policy-conditioned Edge Recall as it grows. In practice, real systems have non-zero error, so the guarantee becomes approximate rather than absolute. The corrected theorem also makes explicit a necessary scale condition: if \(d < \kappa\mu_e\), then no integer \(n \ge 1\) can satisfy \(n\kappa\mu_e \le d\), meaning a 1-hop precision guarantee at scale \(d\) is impossible under the assumed edge model.

Scale admissibility and interpretation. The theorem makes explicit that the surrogate relationship is scale-dependent: it holds only for hop and route thresholds \((n,d)\) satisfying \(n\kappa\mu_e \le d\). This is not merely a technical artifact, but reflects the intrinsic spatial resolution of the graph induced by the mapping policy. If one edge may span up to \(\kappa\mu_e\) route distance, then no 1-hop guarantee can certify physical precision below that scale. Thus, localization accuracy implies map consistency only at evaluation scales that are compatible with the graph’s edge-length model.

Which assumption fails under error? The key structural requirement is that every added edge remains physically local, i.e., \(\mathrm{dist}_R(x,y)\le \kappa\mu_e\). Consecutive edges created during exploration typically satisfy this automatically. However, an incorrect accept decision (a false loop closure) can add a shortcut edge between physically distant places, violating this bound. Once such a long-range spurious edge exists, the Hop-to-route lemma no longer applies, and Edge Precision can fail immediately, since even a 1-hop connection may exceed the threshold \(d\).

Error asymmetry: false accept vs. false reject. Not all localization errors have the same structural consequences. False accepts are catastrophic: they can introduce an incorrect shortcut that collapses hop distances between distant regions, corrupting the graph and potentially causing cascading failures in later updates. In contrast, false rejects (missed revisits) usually create duplicate nodes connected only by local consecutive edges; this tends to preserve Edge Precision but harms Policy-conditioned Edge Recall by failing to realize valid revisit opportunities, leading to fragmentation and reduced planning efficiency.

Implication for the surrogate relationship. Localization accuracy remains an informative surrogate for map success, but the corrected proof clarifies that the most damaging failure mode is specifically the introduction of non-local shortcut edges. This motivates ambiguity-aware evaluation (A+P, P.O., A.O.): A.O. cases directly probe the tendency to incorrectly accept in novel regions, which is precisely the error mode that can violate edge-length regularity and break the theorem’s assumptions. Conversely, strong A+P and P.O. performance reflects the ability to correctly realize revisit opportunities without sacrificing structural safety.

Practical extension via edge gating. The argument can be extended beyond the zero-error setting if the system enforces a physical consistency gate on accepted shortcut edges. If every accepted edge \((x,y)\) is required to satisfy \[ \mathrm{dist}_R(x,y)\le \kappa\mu_e, \] for example via odometry-based gating, temporal consistency checks, or multi-view geometric verification, then the Hop-to-route lemma continues to hold and Edge Precision is preserved even with non-zero retrieval noise. Under such gating, residual errors primarily manifest as conservative rejects, which degrade recall but do not catastrophically corrupt the map.

Conclusion:

Under additive graph growth, edge-length regularity, and correct localization at every timestep, the evolving graph satisfies Edge Precision and Policy-conditioned Edge Recall at any scale \((n,d)\) for which \(n\kappa\mu_e \le d\). The proof also clarifies why catastrophic false accepts are the critical failure mode in practice: they are precisely what can violate the locality condition needed for the guarantee.

Benchmarking Baselines

We benchmark three baseline localization systems. The values below are the tuned settings used for BLAmax and LA.O.@90, rather than the raw script defaults.

Greedy Matching (GM). The system selects the highest-similarity node and accepts it only when the score exceeds the threshold \(\tau\); otherwise it keeps the previous localization result unchanged.

BLAmax
\(\tau = 0.5\)
LA.O.@90
\(\tau = 0.65\)

Sequence Matching (SM). The system scores each candidate using a temporal window and accepts the best candidate when the aggregated score exceeds \(\tau\). In this implementation, the window is causal: it uses the current keyframe and the previous \(h\) keyframes, so the effective window length is \(h+1\). We report two aggregation variants: SM-Med uses the median similarity over the window (agg="median"), while SM-All requires every frame in the window to individually exceed \(\tau\) and then averages those scores (agg="all").

BLAmax
SM-Med: \(h = 9, \tau = 0.5\)
SM-All: \(h = 9, \tau = 0.45\)
LA.O.@90
SM-Med: \(h = 9, \tau = 0.6\)
SM-All: \(h = 9, \tau = 0.6\)

Probabilistic Belief Update (PBU). The system propagates a belief over map nodes using a hop-limited transition model, then updates that belief using similarity-based observation likelihoods. Here, \(\tau\) is the observation threshold, \(w_u\) is the maximum hop movement per step, \(\alpha\) and \(\beta\) are the legal and illegal transition weights, \(\kappa\) scales the softmax likelihood sharpness, and \(\eta\) is the minimum posterior belief required to emit a localization.

BLAmax
\(\tau = 0.3\), \(w_u = 7\), \(\alpha = 1.0\), \(\beta = 10^{-6}\), \(\kappa = 15.0\), \(\eta = 0.3\)
LA.O.@90
\(\tau = 0.65\), \(w_u = 7\), \(\alpha = 1.0\), \(\beta = 10^{-6}\), \(\kappa = 15.0\), \(\eta = 0.3\)