Regression Testing a Map Matcher in CI

A benchmark that runs when somebody remembers is a benchmark that runs after the regression shipped. The value of the ground truth assembled in building a ground-truth set is realised only when it runs on every change, automatically, and blocks the ones that lose accuracy.

This page covers getting there: the determinism work that has to happen first, pinning the graph so the gate measures code rather than maps, per-stratum tolerances, and the report format that makes a failure actionable instead of merely annoying.

Compatibility and Configuration Requirements

Determinism First

Before any accuracy gate, prove the matcher returns the same answer twice. Non-determinism in map matching usually comes from one of three places: an unordered candidate set, a tie between equal-cost paths broken by hash ordering, or a floating-point reduction whose order depends on thread scheduling.

def test_matcher_is_deterministic(sample_traces, matcher):
    """Gate everything else behind this. A flaky matcher makes every other test flaky."""
    for trace in sample_traces:
        a = matcher.match(trace)
        b = matcher.match(trace)
        assert a.edges == b.edges, f"{trace.id}: matcher is non-deterministic"
        assert a.offsets == b.offsets, f"{trace.id}: offsets differ between identical runs"

Run this against a deliberately non-deterministic build once, to confirm it fails. A determinism test that has never failed is usually a determinism test that compares an object to itself.

Ties are the interesting case. Two candidate paths with identical cost genuinely exist — most often between the two carriageways of a dual carriageway where the trace runs down the middle — and the matcher must break them the same way every time. Sorting candidates by a stable key before selection is the usual fix, and it costs nothing.

The Gate

import json
import pathlib

BASELINE = pathlib.Path("benchmarks/baseline.json")
TOLERANCE_PTS = {"rural": 0.3, "suburban": 0.5, "urban_grid": 0.8, "dense_centre": 1.2}


def run_gate(results: dict[str, float]) -> None:
    baseline = json.loads(BASELINE.read_text())
    failures = []
    for stratum, score in sorted(results.items()):
        delta = (score - baseline[stratum]) * 100
        tol = TOLERANCE_PTS[stratum]
        flag = "FAIL" if delta < -tol else "ok"
        print(f"{stratum:14s} {score:6.3f}  baseline {baseline[stratum]:6.3f}  {delta:+5.2f} pts  {flag}")
        if flag == "FAIL":
            failures.append(f"{stratum} {delta:+.2f} pts (tolerance {tol})")
    if failures:
        raise SystemExit("accuracy regression: " + "; ".join(failures))

Tolerances differ per stratum on purpose. Rural matching is nearly deterministic in its accuracy, so a 0.3-point move there is real. Dense-centre matching is genuinely noisier — a handful of traces can swing it — so the same tolerance would produce false failures. Setting each stratum’s tolerance from its own run-to-run variance is a ten-minute exercise that makes the gate trustworthy.

The baseline lives in the repository. Its git history then becomes the record of every accuracy change the team has accepted, with the reasoning in the commit messages. That artefact is worth more than the gate itself six months later, when somebody asks why dense-centre accuracy is two points lower than it was in spring.

Making a Failure Actionable

An aggregate failure tells a reviewer that something got worse. A per-trace diff tells them what.

def diff_report(new_matches: dict, baseline_matches: dict, limit: int = 20) -> list[dict]:
    """Traces whose matched edge sequence changed, worst first."""
    changed = []
    for trace_id, edges in new_matches.items():
        old = baseline_matches.get(trace_id)
        if old is not None and old != edges:
            changed.append({
                "trace_id": trace_id,
                "edges_removed": sorted(set(old) - set(edges))[:5],
                "edges_added": sorted(set(edges) - set(old))[:5],
                "n_changed": len(set(old) ^ set(edges)),
            })
    return sorted(changed, key=lambda r: -r["n_changed"])[:limit]

Twenty traces with the specific edges that moved is something a reviewer can open on a map in a few minutes. A line saying “dense_centre −1.4 pts” is something they will either ignore or spend an afternoon on, and both outcomes are bad.

Store the per-trace matches alongside the baseline scores. They are small — an edge sequence is a list of integers — and they turn every future failure into a diff rather than an investigation.

Execution and Tuning Guidelines

Bake the graph into the test image. A gate that downloads a graph at run time will eventually run against a different one than the baseline was measured on, and the resulting failure sends everybody looking at the code.

Keep the benchmark set small enough to stay fast and large enough to be stable. Two to four hundred traces is the usual sweet spot: it runs in minutes and each stratum still has enough traces that a single one cannot move it.

Run the full set nightly and a subset per commit if the full set cannot be made fast enough. The subset catches the obvious regressions immediately; the nightly run catches the subtle ones before they compound.

Treat a baseline update as a reviewed change. Requiring that the baseline move only through a pull request is what turns the gate from a nuisance into a record.

Common Pitfalls Specific to This Technique

Gating on the aggregate only. A change that improves suburban accuracy by one point while losing three in dense centres passes an aggregate gate and makes the product worse where it is already worst.

Letting the tolerance be a single global number. Strata have genuinely different variances, and one tolerance means the gate is simultaneously too strict for one stratum and too loose for another.

Updating the baseline to make a failing build green. It is the fastest way to make the gate meaningless, and it is almost always done under time pressure with no note of why. Require a reason in the commit message and the practice mostly stops on its own.

Running the Gate Somewhere Sensible

The benchmark needs a graph, and a graph is large. Where that graph lives shapes how usable the gate is, and there are three workable arrangements.

A tiny purpose-built graph in the repository. Clip an extract down to the few square kilometres the benchmark traces actually cover, and commit the built graph. For a stratified set of a few hundred traces this is typically 60–150 MB, which is large for a repository and entirely manageable in a container image layer or an artefact store. It makes the gate completely self-contained.

A cached image layer. Build the graph once, bake it into a base image tagged with the graph version, and have the CI job pull that. The gate stays fast, the graph stays pinned, and updating it is a deliberate image rebuild.

A shared service. Point the gate at a long-running matcher instance. This is the least work to set up and the least reproducible: the service’s graph can change without the gate noticing, which is the exact failure the pinning was meant to prevent. If you use it, assert the graph version the service reports against the one the baseline expects, and fail on a mismatch.

def assert_graph_pinned(matcher, expected: str) -> None:
    actual = matcher.graph_version
    if actual != expected:
        raise SystemExit(
            f"benchmark expects graph {expected} but the matcher reports {actual} — "
            "the baseline is not comparable"
        )

Cost and cadence

The full apparatus — a pinned graph, a few hundred traces, four metrics and a diff — runs in two to four minutes on an ordinary runner, which is comfortably inside what a reviewer will wait for. That number is worth protecting: as the benchmark grows, keep the per-commit set bounded and move the extra coverage to a nightly job rather than letting the pull-request gate creep past ten minutes.

Where a change genuinely needs the larger set — a matcher rewrite, a parameter overhaul — run it explicitly rather than making everyone else pay for it on every commit. A label on the pull request is enough of a mechanism, and it keeps the default path fast.

Related

• Map matching accuracy validation and benchmarking — parent topic
• Building a ground-truth set for map-matching evaluation — the labels the gate scores against
• Measuring map-matching accuracy with Hausdorff and F1 — the metrics the gate reports
• Validating CRS transforms with round-trip assertions — the same preflight discipline upstream
• Trajectory Analysis & Map Matching Techniques — parent section