arah2/docs/ROUTING.md

Routing — the deep dive

Arah² routes today. This document explains how, at the level of data structures, algorithms, and measured numbers — and what the committed but unbuilt upgrade lever (ALT landmark preprocessing — ALT landmarks are graph vertices, not POIs; see §0.8) would change if it lands.

Three questions, answered in order — after a short vocabulary primer (§0):

1. How does routing work today? — the CSR road-graph binary, the bidirectional typed-array A* over it, snapping, turn classification, and the two-backend dispatch between the fixture corpus and the live graph engine.
2. How is ALT supposed to work? — the mechanics, precisely, and where it would slot into the existing bidirectional A*. Not built. It is a next-milestone item.
3. Pros and cons of every approach — unidirectional A*, bidirectional A*, fixture routes, ALT, and the graph-pruning experiment — with the numbers this repo actually contains.

Every claim names a real file and a real function. Where a claim is a plan rather than code, it says so.

---

0. Start here — the words this document uses

Routing has a small vocabulary that is easy to nod along to and hard to actually picture. This section defines each term in plain language, using the real example from this codebase, so §1 onward can use the words without stopping to re-explain them.

0.1 "Routing graph" — dots and arrows, not a drawing

A routing graph is a stripped-down model of the road network: a set of nodes (points) and edges (one-way hops between two points), where each edge carries a weight — a number saying how expensive that hop is.

In this repo:

• A node is one distinct coordinate on an OSM way. The build script does not invent intersections: internNode in routing/scripts/build-road-graph.mjs keys every geometry point by its coordinate rounded to 1e-6° (round6) and returns the same id for the same point. An intersection — a coordinate shared by two OSM ways — therefore becomes one node where several road pieces meet; an ordinary bend is a node where exactly two road pieces meet (four directed edges, two each way); the end of a dead-end street is a node where only one road piece meets (two directed edges, unless the street is oneway).
• An edge is one consecutive pair of points along a way. For each pair the script emits two directed edges, one each way: rawEdges.push({ from, to, seconds, flags: reverseOnly ? 1 : 0, nameId }) and its mirror. So "677,068 directed edges" is roughly half that many physical road pieces, each modelled in both directions.
• The weight is seconds — meters / (kmh / 3.6) — travel time, not distance. That is why the router minimizes seconds, and why the returned distanceM has to be recomputed afterwards (§1.3, "Reconstruction and real costs").
• The oneway flag is not a separate structure: it is bit 0 of edgeFlags on the blocked mirror edge. That edge stays in the graph — so snapping can still see its geometry and street name — but A* never traverses it.

A three-node excerpt, using the committed mini-graph's real speed classes (routing/test/fixtures/build-mini-graph.mjs: perimeter 60 km/h, interior 30 km/h, and exactly one oneway pair, grid ids 2→3):

flowchart LR
    classDef node fill:#D9D2C6,stroke:#1A1A1A,stroke-width:2px,color:#1A1A1A
    classDef interior fill:#736B1E,stroke:#4A440F,stroke-width:2px,color:#FFF8F0

    A["Node A — grid id 2<br/>(an OSM geometry vertex:<br/>a perimeter corner)"]:::node
    B["Node B — grid id 3<br/>(an OSM geometry vertex:<br/>the next perimeter corner)"]:::node
    C["Node C — grid id 8<br/>(an OSM geometry vertex:<br/>an interior grid point)"]:::interior

    A -->|"edge A→B · ≈3.3 s<br/>Jalan Persiaran Mini · 60 km/h"| B
    B -.->|"edge B→A is BLOCKED<br/>edgeFlags bit 0 · oneway mirror"| A
    B -->|"edge B→C · ≈6.7 s<br/>Jalan Mini 2 · 30 km/h"| C
    C -->|"edge C→B · ≈6.7 s<br/>the same street, other direction"| B

    linkStyle 1 stroke:#ED3F1C,stroke-width:3px

Two misconceptions this picture is meant to kill: a node is not a city or a category of junction — it is just a coordinate; and an edge is not a road — it is one directed hop between two adjacent coordinates, so a long road is many edges.

0.2 "CSR" — the graph stored as flat arrays

CSR stands for Compressed Sparse Row. The idea is to stop storing one JavaScript object per node and instead store a handful of parallel arrays plus one index array.

Imagine 311k nodes. The obvious JS shape is [{ lat, lng, edges: [...] }, ...] — 311k objects plus 677k edge objects, every one of them a heap allocation and a pointer chase. CSR instead keeps:

Array	What it holds
lat[], lng[]	one coordinate pair per node
edgeStart[]	n+1 numbers; node i's edges are the slice edgeStart[i] .. edgeStart[i+1]
edgeTarget[]	for each edge, the node it arrives at
edgeSeconds[]	the edge weight (travel time)
edgeFlags[]	bit 0 = the oneway mirror
edgeNameId[]	index into the street-name pool

Walking node 42's neighbours is two reads and a short loop:

for (let e = graph.edgeStart[42]; e < graph.edgeStart[43]; e++) {
  const neighbour = graph.edgeTarget[e];
  const costSeconds = graph.edgeSeconds[e];
}

No object dereference, no per-node array, no Map. "Compressed" means the full n × n adjacency matrix is never stored; "sparse row" refers to the row-pointer array (edgeStart) that finds each node's slice. The full binary layout in §1.2 is just this idea written down byte for byte: Offsets is edgeStart, Edges is edgeTarget + edgeFlags, Weights is edgeSeconds.

Why it avoids allocation. decodeGraph in routing/src/graph.ts creates typed-array views over the same ArrayBuffer — new Float64Array(buffer, lay.lat, nodeCount) — not copies and not per-node objects (D-01). The A* hot loop then allocates nothing per node: its per-query state is a fixed set of O(n) typed arrays created once at the top of routeAstar (df, db, fPrev, bNext, the two closed sets, the two heuristic caches, pf). Under a 10 ms CPU ceiling and a 128 MB isolate, 311k objects per request is not an option; the flat arrays are also why the hot loop has no GC pauses. astar.test.mjs A8 pins the discipline structurally: it strips comments from astar.ts and fails if new Map( appears.

0.3 "A*" — search with a guess

Plain Dijkstra explores outward in every direction until it happens to reach the goal. A* adds a guess h(v) of the time still needed from v to the goal, and always expands the node with the smallest

f(v) = g(v) + h(v)        g = seconds already spent, h = seconds still guessed

If the guess never overshoots the truth (the heuristic is admissible), the route A* returns is still optimal; the better the guess, the fewer nodes it has to expand.

In this codebase the guess is

h_f(v) = hav(v, goal) / maxSpeedMps          (routing/src/astar.ts)

maxSpeedMps is the fastest class in the entire graph (graph.maxSpeedKmh, written at build time). That makes the guess admissible — a straight line is the shortest possible path, and dividing by the fastest possible speed gives the shortest possible time — but loose: it assumes a 15 km trip could be driven entirely at 100 km/h. On a local street the real time is longer, so the guess understates the remaining cost and A* explores many nodes it did not need to. That looseness is the root cause ALT attacks (§2.1).

Both directional heuristics are scaled into seconds: haversineM returns metres, divided by metres-per-second.

0.4 "Bidirectional A*" — two searches that meet in the middle

Run the same search from the origin forward and from the goal backward over in-edges (that is why reverseFor exists — a source-grouped CSR cannot list a node's in-edges). Each side keeps its own heap and closed set. When an edge connects a forward-reached node to a backward-reached node, that is a candidate meeting with total cost d_f(v) + d_b(v); keep the best one, mu. Stop when the two frontiers' smallest keys sum to at least mu — no unexpanded node can then beat the best meeting.

flowchart LR
    classDef origin fill:#EB8008,stroke:#8A4C00,stroke-width:2px,color:#1A1A1A
    classDef goal fill:#1A1A1A,stroke:#000000,stroke-width:2px,color:#FFF8F0
    classDef frontier fill:#D9D2C6,stroke:#1A1A1A,stroke-width:2px,color:#1A1A1A
    classDef meet fill:#736B1E,stroke:#4A440F,stroke-width:2px,color:#FFF8F0

    O["origin node<br/>(a GPS fix, after snapping)"]:::origin
    F1["forward frontier<br/>ring 1"]:::frontier
    F2["forward frontier<br/>ring 2"]:::frontier
    M["meeting node<br/>(best mu seen so far)"]:::meet
    B2["backward frontier<br/>ring 2"]:::frontier
    B1["backward frontier<br/>ring 1"]:::frontier
    G["goal node<br/>(a gazetteer POI, after snapping)"]:::goal

    O --> F1 --> F2 --> M
    G --> B1 --> B2 --> M
    F2 -.->|"stop when<br/>top_f + top_b ≥ mu"| B2

Why this is meant to halve the work. A one-sided search must grow to radius 2r to touch a goal 2r away; two searches of radius r cover the same corridor with roughly a quarter of the area each, so total work is about half. That is the geometric intuition. In this implementation the measured p95 did not improve, because the potential split (§0.5) halves each side's heuristic steering at the same time. §3.4 carries the measured verdict; the correctness proof is unaffected either way.

0.5 "Potential" — the word means two different things here

This is a place where a reader can get lost, so separate the two senses once:

(a) The Ikeda potential used today (§1.3). With the directional heuristics h_f and h_b above, the search uses

p_f(v) = (h_f(v) − h_b(v)) / 2          p_b(v) = −p_f(v)

and relaxes an edge with c + p(u) − p(v) instead of c. Read the formula as "forward distance-to-goal minus backward distance-to-origin, halved". It is a reweighting, not a distance and not a lower bound: it shifts every node's key by a node-dependent constant so the two frontiers are measured on a comparable scale. The phrase "opposite potentials" is literal — p_b is the negative of p_f. A useful intuition: in a symmetric graph h_f + h_b ≈ the whole route length, so p_f ≈ h_f − (route length)/2; the potential recentres the forward guess on the halfway point. The reweighted edge costs stay non-negative, so optimality survives, and the stop rule top_f + top_b ≥ mu becomes valid. The code computes it lazily and caches it in hfCache / hbCache / pf (potential(v) in routing/src/astar.ts).

(b) The ALT potential proposed in §2. There, "potential" means a lower bound on the remaining time, h_ALT(v), built from landmark distances. It replaces the haversine h_f / h_b that feed (a); the Ikeda reweighting then still sits on top. So §2's h_f is an input to §1.3's p_f, not a competitor.

0.6 "Snapping" — GPS point → graph node

A GPS fix is a coordinate, not a node id. snapToGraph(graph, point) answers "which graph node is this fix on?" in three moves (the exact authority is §1.4):

1. Reject fixes outside the graph bbox plus 0.01° — an honest null.
2. Look only in the fix's ~0.002° grid cell and its eight neighbours (the 3×3 neighbourhood).
3. For every road segment touching those cells, project the fix onto the segment in cos-scaled degree space and keep the closest; return the nearer endpoint (t <= 0.5 ? u : v) plus that segment's street name.

Every route query starts and ends with a snap; a snap miss is a designed null / router-pending answer, never a made-up node. Snapping deliberately ignores the oneway flag — geometry is directionless; only A* enforces direction.

0.7 Turn classification and step derivation

classifyTurn(prevBearingDeg, nextBearingDeg) in routing/src/astar.ts is the single authority for "what is a turn". It compares the compass bearing of the segment you arrived on with the bearing of the segment you leave on. Bearings increase clockwise (N=0, E=90), so a negative delta is a left turn. Thresholds: ≤25° straight, ≤60° slight left/right, ≥150° U-turn, otherwise left/right. The pinned example: classifyTurn(0, 40) === "slight-right".

deriveSteps(graph, nodes) turns a node path into human steps. It walks consecutive pairs, computes each bearing, classifies the turn, and starts a new step whenever the turn is not "straight" or the street name changes. The first step is always "depart"; a final "arrive" step anchors the destination. Each step carries kind, name (omitted when the edge is unnamed), distanceM, and polyline6 geometry. It throws on a non-traversable pair — a malformed path is a caller bug, not a route miss.

Fixture routes have empty step arrays (D-10) — honest "not wired"; the live engine populates them.

0.8 The two different things called "landmark"

Read this before §2. This repository uses the English word landmark for two unrelated objects. They share a name and nothing else.

	Search / gazetteer landmark	ALT landmark
What it is	A Point of Interest a user searches for and drives to	A chosen vertex of the routing graph, used only as a distance reference
Real examples	suria-klcc ("Suria KLCC", aliases "KLCC", "KLCC Park"), national-museum, kl-sentral — 30 entries in search/src/data/kl-gazetteer.json	an integer vertex id with no name, address, or POI record (illustrative: none has been chosen yet — no ALT code exists)
Where it lives	search/src/data/kl-gazetteer.json; typed by GazetteerEntry in search/src/types.ts	would live in the landmark table of a layout-v2 graph — nothing exists yet
Who uses it	search (getEntries / getEntryById), fixture corpus endpoints, /api/route's destinationId lookup, snapping targets	only a future A* speedup
How it is chosen	curated by hand, with local aliases	algorithmically, by a farthest-point sweep over graph vertices (§2.2)
Shown to users?	yes — it is the product's destination	never

Which is which, wherever the doc says "landmark":

• Sentences about search, the gazetteer, fixture pairs, POIs, snapping, or "all landmarks in one strongly-connected component" mean gazetteer landmarks.
• Sentences about ALT, preprocessing, the 16–32 reference vertices, or a landmark table mean ALT landmarks.
• §2 uses "landmark" exclusively in the ALT sense; §1.6 and the ladder history use it exclusively in the POI sense.

Why this matters for the graph-pruning story. When §1.9 and §3.5 say the pruned graph "severed the fine mesh tying landmarks to the arterials", that means gazetteer (POI) landmarks — the fixture endpoints such as KL Tower, KL Sentral, and Suria KLCC. Those POIs are reached by snapping to a nearby minor street; dropping tertiary and residential removed the streets that connect those POI coordinates to the arterials, so the pairs became unreachable. It has nothing to do with ALT landmarks: no ALT code existed during that experiment and none exists now.

Conversely, an ALT landmark is just a vertex — but because the farthest-apart vertices in travel-time terms tend to sit on long arterial or motorway chains, an ALT landmark will often look like an arterial intersection. Looking like one is a consequence of the selection, not its definition, and it is still not a POI. An ALT landmark at an arterial junction is not "KLCC"; it is a graph vertex that happens to be far from the other landmarks.

---

1. How routing works today

1.1 The shape of the system

Two routing backends answer the same contract (RoutingSource in routing/src/types.ts), and the client composes them into a ladder (web/src/main.ts:431-436):

const fixtureSource = createFixtureRoutingSource();
const httpSource = createHttpRoutingSource({ endpoint: "/api/route", bearer: () => getSession() });
const routingSource: RoutingSource = {
  name: "ladder",
  route: async (req) => (await httpSource.route(req)) ?? (await fixtureSource.route(req)),
};

• Backend #1 — "fixture" (routing/src/fixture-source.ts): a build-time-precomputed corpus of 15 golden KL pairs, served from the bundle. It matches on destinationId and a 200 m origin tolerance.
• Backend #2 — "engine-a" (routing/src/http-source.ts): a Bearer-gated POST /api/route to the Worker, which runs the real router over the R2-hosted road graph.

The ?? is the load-bearing operator: engine-a first, fixture as the fallback. A null from engine-a (any miss class) falls through to the fixture corpus; a null from both is the honest "router pending" state.

The ladder is documented, not switchable — no env read, no config read, no dynamic registry. The import site constructs the backends in code (T-05-04). The ladder's shape mirrors SearchSource's (docs/CORE-CONCEPTS.md §2).

Where the dispatch actually lives. The fixture-vs-graph-engine choice is client-side (web/src/main.ts:431-436). bot/src/routing/ contains only the graph engine's server arm — handleRoute in worker-router.ts — and has no fixture backend at all. The diagram below is therefore split the same way the code is: orange = the Mini App's ladder, beige = the Worker, red = the R2 data plane, olive = the in-bundle fallback.

flowchart TD
    classDef client fill:#EB8008,stroke:#8A4C00,stroke-width:2px,color:#1A1A1A
    classDef server fill:#D9D2C6,stroke:#1A1A1A,stroke-width:2px,color:#1A1A1A
    classDef store fill:#ED3F1C,stroke:#8C1F0A,stroke-width:2px,color:#FFFFFF
    classDef fallback fill:#736B1E,stroke:#4A440F,stroke-width:2px,color:#FFF8F0
    classDef pending fill:#1A1A1A,stroke:#000000,stroke-width:2px,color:#FFF8F0

    CALL["web/src/main.ts<br/>route request"]:::client
    LADDER["routingSource: 'ladder'<br/>httpSource.route() ?? fixtureSource.route()"]:::client
    HTTP["POST /api/route<br/>Bearer session token"]:::client
    WR["bot/src/routing/worker-router.ts<br/>handleRoute"]:::server
    GRAPH[("R2 ROAD_GRAPH<br/>kl-roadgraph.v1.bin")]:::store
    DEST["getEntryById(destinationId)<br/>gazetteer POI lookup"]:::server
    SNAP["snapToGraph<br/>origin + destination"]:::server
    ASTAR["routeAstar<br/>bidirectional A*"]:::server
    RESULT["200 RouteResult<br/>backend: engine-a"]:::client
    NULL["200 null<br/>(any miss class)"]:::pending
    FIX["routing/src/fixture-source.ts<br/>15 golden pairs · 200 m law"]:::fallback
    PENDING["router-pending state<br/>(honest degradation)"]:::pending

    CALL --> LADDER
    LADDER -->|"1st: graph engine"| HTTP
    HTTP --> WR
    WR --> GRAPH
    WR --> DEST
    DEST --> SNAP --> ASTAR --> RESULT
    RESULT --> CALL
    WR -->|"miss"| NULL
    NULL -->|"?? falls through"| FIX
    FIX -->|"pair matches"| RESULT
    FIX -->|"no match"| PENDING

Every arrow out of handleRoute that is not a RouteResult is the same 200 null — the null contract is the dispatch signal, not an error (§1.7).

1.2 The data plane: the CSR road-graph binary

Engine A routes over a CSR (Compressed Sparse Row) binary — an adjacency structure where each node's outgoing edges are stored contiguously. The codec is routing/src/graph.ts: encodeGraph (build-time) and decodeGraph (runtime) are inverses, and the binary layout has exactly one authority — that file.

The pinned layout (little-endian, documented at routing/src/graph.ts:9-21):

Region	Contents
Header (64 B)	magic 0x41524731 ("ARG1"), version 1, nodeCount, edgeCount, nameCount, namePoolLen, bbox (4×f64), maxSpeedKmh (f32), 4 pad bytes
Nodes	f64 lat[n] ++ f64 lng[n]
Offsets	u32 edgeStart[n+1] — CSR row pointers; node i's edges are edgeStart[i]..edgeStart[i+1]
Edges	u32 edgeTarget[e] ++ u8 edgeFlags[e]
Weights	f32 edgeSeconds[e] (4-byte aligned)
Names	u32 edgeNameId[e] ++ u32 nameOffset[m+1] ++ UTF-8 namePool

The 60→64 byte header padding is not cosmetic: the f64 node arrays must be 8-byte aligned for zero-copy Float64Array views, and an unaligned Float64Array throws. decodeGraph returns typed-array views over the caller's ArrayBuffer — zero per-node JS objects, which is the whole point (D-01).

Fail-honest decode (T-06-03). decodeGraph validates magic, version, and the exact byte size implied by the header counts, and returns null on any mismatch. It never throws and never returns a half-built graph. The size check runs before any view allocation (T-06-03b), so a hostile header with huge counts rejects on arithmetic, not on allocation. The Worker turns that null into the router-pending state.

The oneway law (edgeFlags bit 0 = "oneway-reverse"). The build emits both directions of every OSM way. The blocked mirror direction stays in the CSR with bit 0 set. This is deliberate: the edge still carries its segment geometry and street name, so the snapper can find it, but A* never traverses it. Snapping ignores direction; A* enforces it. See §1.4.

Build pipeline — routing/scripts/build-road-graph.mjs:

1. The bbox is computed at run start from the committed corpus (gazetteer extremes + golden-pair coordinates ± 0.05°). It tunes itself when the corpus grows; it is never hand-edited.
2. One Overpass query fetches every way whose highway tag is in ACTIVE_CLASSES — 13 classes: motorway, trunk, primary, secondary, tertiary, residential, unclassified, living_street, plus the five *_link ramp classes. footway/cycleway/service/path are deliberately absent (a walking path must never enter a road A*).
3. Ways → nodes (deduplicated by coordinate rounded to 1e-6°, ≈ 0.11 m) → directed edges with oneway flags, speed-derived seconds, and street-name pool ids.
4. encodeGraph produces the pinned binary. Collect-then-write: the file is written only after the encode and the stats gate both pass — any failure exits 1 with the previous binary untouched.

The *_link classes are load-bearing (measured 2026-10-24): without them the graph fragments — 7.7% of nodes sat in severed motorway islands and golden corpus pairs resolved "unreachable". This was a real bug caught by the CPU measurement, fixed in commit ea9584d.

The envelope gate (D-01): a binary over 80 MB is refused; one at or under 1 MB is refused ("not a real road graph"); 30–80 MB is the expected band, with a smaller result printing an advisory warning. The binary is a build artifact, gitignored (routing/data/.gitignore → *.bin) — ODbL-derived data never enters the repo. Forks build and upload their own (docs/ROAD-GRAPH.md).

1.3 The A* core: routing/src/astar.ts

routeAstar(graph, originNode, goalNode) returns { nodes, seconds, distanceM } or null for an unreachable pair.

It is bidirectional — a BH (Bidirectional Heuristic) search with Ikeda potentials. The module header states why: the free-plan 10 ms CPU budget is the design constraint, and the measured unidirectional p95 on the real KL graph was 3–5× over it.

The heap

A NodeHeap over two preallocated typed arrays: Float64Array keys and Uint32Array nodes, grown by doubling. push / pop / peekKey. peekKey returns Infinity on an empty heap — the BH stop rule reads it. Deletion is lazy: stale entries are skipped by the closed-set check in routeAstar.

The hot loop is allocation-free

No Map, no per-node objects. routing/test/astar.test.mjs A8 asserts this structurally: it strips comments from astar.ts and fails if new Map( appears.

State per search:

Array	Type	Meaning
df, db	Float64Array(n)	reduced distances, forward and backward
fPrev, bNext	Int32Array(n)	predecessor / successor on the two chains
fClosed, bClosed	Uint8Array(n)	closed sets
hfCache, hbCache	Float64Array(n)	lazily-computed heuristic caches (NaN = not yet)
pf	Float64Array(n)	the potential, p_f(v)

The BH construction (Ikeda et al.)

With directional heuristics

h_f(v) = hav(v, goal)   / maxSpeedMps
h_b(v) = hav(v, origin) / maxSpeedMps

(each consistent on its own search graph — the speed divisor comes from the graph header's maxSpeedKmh), and the opposite potentials

p_f(v) = (h_f(v) − h_b(v)) / 2      p_b(v) = −p_f(v)

the reductions

forward,  edge u→v:            c + p_f(u) − p_f(v)
backward, in-edge v→u of settled u:  c + p_b(u) − p_b(v)

are non-negative (each feasibility is the sum of the two consistencies, each ≤ c), and the meet keys satisfy

d_f(v) + d_b(v) = real(o→g through v) − p_f(o) + p_f(g)

— a v-independent constant. Therefore stopping when top_f + top_b ≥ mu (the best meeting cost seen) settles the goal provably optimally, at roughly half the explored radius per side.

The stop rule and the alternation knob

if (fHeap.peekKey() + bHeap.peekKey() >= mu) break;   // THE BH STOP RULE
const expandForward = fHeap.size <= bHeap.size;         // BALANCED ALTERNATION

The stop rule carries optimality. The alternation is a work-balancing knob only. This is not a stylistic claim — it was a bug: the first implementation compared raw tops (top_f <= top_b), which starved the backward side (19,501 forward settles to 3 backward) and landed 4× slower than unidirectional. Comparing heap sizes keeps both rings growing. The fix is recorded in .planning/phases/06-turn-by-turn-guidance-live-driving/06-04-SUMMARY.md §2.

The reverse CSR

The backward search needs in-edges. A source-grouped CSR cannot yield them without a reverse index, and reading out-edges as in-edges fabricates phantom arcs — the 06-04 bug where a 6.66 s "path" was found against Dijkstra's 26.67 s.

reverseFor(graph) builds the reverse adjacency once per RoadGraph and memoizes it in a module-scope WeakMap (the same LAW 1 lazy-memoize pattern as the snap grid). It holds rowStart (u32), targets (the in-edge's source node), and edgeIds (the edge's index in the forward CSR, for the weight and flag lookup). Build cost is O(V+E) per isolate, paid by the first route and amortized across the isolate's requests. The pinned binary layout is untouched — the reverse index is a derived in-memory structure.

Reconstruction and real costs

The path is origin →(fPrev)→ meetFrom −[bridge]→ meetTo →(bNext)→ goal. Then the real costs are recomputed along the node path — haversineM for distance, graph.edgeSeconds[edge] for time — so no reduced-cost arithmetic leaks into the returned seconds. distanceM is summed post-hoc over the node path, which is the plan's law (the graph stores travel time, not distance).

The reverse edge lookup

findTraversableEdge(graph, u, v) scans node u's out-edges for one whose target is v and whose flag bit 0 is clear. It returns -1 if none. This is what makes deriveSteps throw on a malformed path — a caller bug is loud, unlike a route miss which stays null.

1.4 Snapping: routing/src/snap.ts

engine A owns snapping — ONE authority for road geometry, so the client and the router can never drift. The server authority: a reroute origin lands here. (Phase 6's client-side guidance walks the selected route polyline instead and never calls this module.)

snapToGraph(graph, point) returns { node, distanceM, nameId } or null.

The grid. A coarse grid of ~0.002° cells, built once per graph and memoized in a module-scope WeakMap<RoadGraph, Grid>. A fix touches only the 3×3 cell neighborhood — O(local), never O(nodes). (A global nearest-node scan is the recorded anti-pattern.)

The projection. Point-to-segment projection, not point-to-node, in cos-scaled degree space (lng × cos(lat)). Pitfall 8's law: projection math scales lng by cos(lat), never raw degree deltas. The parameter t is clamped to [0,1]; the snapped node is the closer endpoint of the best segment (t <= 0.5 ? u : v). The reported distanceM is haversineM — the only distance authority that leaves the module (squared-degree is used for ranking only).

The bbox miss. A fix outside the graph bbox plus SNAP_BBOX_MARGIN_DEG (0.01°) resolves null — the designed router-pending signal. Never a fabricated node, never a throw.

Direction plays no part. A oneway segment's flagged reverse edge still carries segment geometry and its street name, so fixes near a oneway road snap to its endpoints exactly like two-way traffic. A* enforces the direction law; snapping ignores it.

Documented limitation. Candidate segments come from the 3×3 neighborhood of the fix's cell — a segment both of whose endpoints sit more than one cell (~0.002°) away is not a candidate. KL-metro build data densifies at intersections, well inside this window; a miss degrades to null, never a wrong snap.

The nameId field is an additive field on SnapResult — edges carry names, nodes don't — and it is what Phase 7's cron street-hop consumes.

1.5 Turn classification and step derivation

Both live in routing/src/astar.ts.

classifyTurn(prevBearingDeg, nextBearingDeg) — the ONE authority

The convention: compass bearings increase clockwise (N=0, E=90), so a NEGATIVE bearing delta is a LEFT turn. The delta normalizes to (−180, 180].

Threshold	Constant	Result
|delta| ≤ 25°	TURN_STRAIGHT_MAX_DEG	straight
|delta| ≤ 60°	TURN_SLIGHT_MAX_DEG	slight-left / slight-right
|delta| ≥ 150°	TURN_UTURN_MIN_DEG	uturn
otherwise	—	left / right

A note on the convention: the original plan text contained classifyTurn(0, 40) → slight-left, which contradicts its own (0,−90) → left and (0,90) → right cases. The compass-consistent reading is what shipped and what astar.test.mjs A6 pins: classifyTurn(0, 40) === "slight-right".

classifyTurn is exported from the package index because plan 07's cron projection imports this exact classifier — one authority for "what is a turn".

deriveSteps(graph, nodes) — node path → maneuver steps

Walks the node path, computing an initial compass bearing for each consecutive pair, classifying each turn, and splitting the path into steps where:

• the bearing leaves "straight", or
• the street name changes.

Each step carries kind, distanceM (haversine over its segments), geometry (polyline6 of its points), and name (omitted when the edge is unnamed — UNNAMED_NAME_ID). The first step is always "depart"; a terminal "arrive" step anchors the goal node (its geometry is the single goal point).

It throws on a non-traversable consecutive pair — a caller bug is loud, unlike a route miss which stays null.

Fixture-world steps are always empty arrays (D-10): an empty array is honest "not wired"; a fabricated step list would not be. Engine A populates them.

1.6 Backend #1: the fixture source and its 200 m matching law

routing/src/fixture-source.ts — createFixtureRoutingSource(data?).

The dataset (routing/src/data/route-fixtures.json) enters by static import (LAW 2 — esbuild and Vite inline it at build time; bare Node 24 reads it via type-stripping; a runtime retrieval would hard-fail in a Worker, which has no fs). The index (Maps, decoded geometry) is built lazily on first use and memoized (LAW 1 — Workers' 1 s startup limit and the webview's first paint both pay for eager work).

The matching law (D-02/D-03). A pair may serve a request only when:

1. the request's destinationId equals the pair's destinationId, and
2. the request origin sits within ORIGIN_TOLERANCE_M = 200 m (haversine) of the pair's pinned public origin.

The 200 m pad absorbs GPS jitter around a known gazetteer (POI) landmark. It never fabricates a route for an unknown origin. Anything unmatched resolves null — the honest router-pending state, never a nearest-match.

The corpus is 15 golden pairs (23 routes) — every origin and destination is a gazetteer (POI) landmark (suria-klcc, kl-sentral, …), not an ALT landmark — the two senses are distinguished in §0.8. The gate routing/scripts/route-corpus.mjs enforces RT1–RT10 offline, including RT2b, the mechanical D-12 proof: every pinned origin must equal its gazetteer landmark's committed coordinate within 1e-4° (≈ 11 m) on both axes. A user coordinate therefore cannot enter a fixture.

Defensive validation (the bot/src/kv/location-pin.ts precedent): a malformed pair — non-finite distance/duration, geometry that throws on decode, empty or oversized routes array — is skipped at index-build time. It renders as an honest null downstream, never a throw in the webview's render path and never a NaN coordinate.

1.7 Backend #2: the Worker router

bot/src/routing/worker-router.ts — handleRoute(req, env).

POST /api/route  { "origin": {lat, lng}, "destinationId": "<slug>" }

The pipeline, in order:

1. Bearer gate. The token resolves through getClaimByToken (bot/src/kv/sessions.ts) to a claim. No/invalid token → 401 unauthorized. The claim is the identity gate; routing itself is chat-agnostic.
2. Body cap. MAX_ROUTE_BODY_CHARS = 4096, checked against the declared Content-Length and the post-read length, both before any parse work. Over-cap → 413.
3. Shape validation. validateRouteBody — finite lat/lng, destinationId matching ^[a-z0-9-]{1,64}$. Fail → 400 malformed.
4. Graph load. loadGraph(env) — see below. null → 200 null.
5. Bbox range check (V5). The origin is range-checked against graph.bbox before any snap/A* work — untrusted coordinates never reach the compute-heavy path. Fail → 400 malformed.
6. Destination short-circuit. getEntryById(destinationId) from @araharah/search — an unknown destination short-circuits before any graph work. null → 200 null.
7. Snap origin. snapToGraph(graph, body.origin) — null → 200 null.
8. Snap destination. snapToGraph(graph, { lat: dest.lat, lng: dest.lng }) — null → 200 null.
9. Search. routeAstar(graph, originSnap.node, destSnap.node) — null → 200 null (a disconnected pair).
10. Assemble. One option only: geometry (node coordinates + derived cumulativeDistanceM), summary (astar.distanceM, astar.seconds), and steps: deriveSteps(graph, astar.nodes). backend: "engine-a".

ONE best route. Alternatives generation is prohibited on this path — the recorded anti-pattern is 2–3 penalty runs inside an active-drive storm-guard window: CPU risk with zero UX need.

Every miss class answers 200 with a JSON null body. That is the null contract crossing HTTP unchanged (D-03): the router-pending state, never a 500, never a blank map, never a fake route.

Logging law (D-14): the only log lines are "[route] rejected: <category>" — unauthorized, malformed — never coordinates, ids, or payloads.

The graph load: isolate memoization is the cache that works

const graphMemo = new WeakMap<object, Promise<RoadGraph | null>>();

caches.default is useless here — Bearer requests auto-bypass the Workers Cache and cron is never cached — so the decoded graph memoizes in a module-scope map keyed on env. Production effect: one R2 GET per cold isolate, the memo is never reset, and the cron arm imports the same loadGraph, so either arm warming the graph serves the other. Keying on env (not a bare module variable) means distinct bindings — tests, multi-binding tooling — can never read each other's graph.

A missing object, a failed read, or a binary decodeGraph rejects resolves null → 200 null. A failed read degrades exactly like a corrupt binary.

Where the graph lives

bot/wrangler.jsonc binds the R2 bucket:

"r2_buckets": [{ "binding": "ROAD_GRAPH", "bucket_name": "araharah-graphs" }]

The object key is kl-roadgraph.v1.bin, pinned as GRAPH_KEY in worker-router.ts and mirrored in routing/scripts/upload-road-graph.mjs. A bucket is not a KV namespace.

1.8 The client seam: routing/src/http-source.ts

createHttpRoutingSource({ endpoint, bearer, fetchImpl? }) — backend #2's client side.

• The endpoint and the bearer getter are injected by the caller (web/src/main.ts:432). The module never reads storage and never holds a token — bearer is a getter, so a token minted after construction is still sent.
• Fail-honest (the network edition). A thrown fetch, a non-200, a malformed body, or a shape violation resolves null. A 200 with a JSON null body is the null contract crossing HTTP; it resolves null too.
• Defensive validation. Every field is type-checked: the destinationId must answer this request, options must number 1..3, every number finite, the cumulativeDistanceM array must match points 1:1 (the day-one progress contract). A payload failing any check is treated as no answer.
• The slug guard runs first — a hostile destinationId never reaches the network.

1.9 The measured cost, and where the budget breaks

routing/scripts/measure-route-cpu.mjs is the gate. It decodes the real binary, snaps the corpus endpoints, adds quadrant-sampled cross-city pairs (a fixed-seed mulberry32 PRNG, so re-runs sample identical pairs), runs one unmeasured warm-up route (printed, never hidden — the numbers must reflect a warm isolate), then times routeAstar with process.hrtime.bigint().

The gate: p95 ≤ 8 ms — 20% margin under the 10 ms free-plan ceiling. Unreachable probes are reported separately (they are not routed trips and would misdescribe the hot path's budget).

The measured state (2026-10-24, the 311k-node linked graph): GATE FAIL.

Ladder step	Outcome
full graph, unidirectional A*	p95 ≈ 38 ms — FAIL
(a) drop tertiary + residential, rebuild	p95 ≈ 18 ms — FAIL, and 12/25 pairs became unreachable (the dropped classes are the fine mesh tying gazetteer/POI landmarks — the fixture endpoints — to arterials; see §0.8) — rejected on correctness, reverted
(b) bidirectional A* (BH, Ikeda potentials)	p95 ≈ 38 ms — FAIL: the potential split halves each side's heuristic steering, cancelling the halved search radius. Kept: sound (the 625-pair Dijkstra equivalence still passes) and better on short product routes
(c) Workers Paid	NOT applied — breaks the $0 law; needs a maintainer decision

docs/BUDGETS.md records the current measurement as 83.989 ms p95 (runs today: 67.5–84.0 ms; documented band 38–93 ms) against an 8 ms budget — a −76.0 ms headroom, printed as measured, never rounded away. The measurement host is a shared Linux dev box with ≈ 2× run-to-run CPU variance — the best observed run is still ~5× over budget, so the conclusion is robust.

Short product routes (2–8 km — the common reroute) measure 2–8 ms, inside the budget. The failures concentrate on 20–30 km cross-metro routes.

The decided posture (c3): cross-metro CPU exhaustion → the Worker's 1102 path → the client's fail-honest null → the router-pending state. Designed degradation, never a fabricated route. The route-cpu budget gate compares the re-run p95 against a 200 ms drift guard (≈ 2× the worst documented run): inside the band = the documented accepted state; beyond it = uncharted regression, and the gate fails.

1.10 The correctness proof

Optimality is not presumed. routing/test/astar.test.mjs A1 runs an exhaustive 625-pair (25×25) equivalence sweep against a brute-force O(n²) Dijkstra over the committed mini-graph (routing/test/fixtures/mini-graph.bin — a 5×5 grid, 25 nodes, ~80 directed edges, three named streets, exactly one oneway pair, two speed classes). The test-local Dijkstra uses plain arrays (fine in tests) and the same traversal law — oneway-reverse edges are never relaxed.

The sweep asserts: cost equality within 1e-6, path endpoints, and null (never a fabricated path) for unreachable pairs.

The remaining gates:

Gate	What it proves
A2	The flagged edge is never traversed; the pair behind it routes the long way, matching Dijkstra
A3	A disconnected pair resolves the honest miss (null)
A4	90° bearing changes classify left/right; steps carry name/distance/polyline6; step distances sum to the route distance
A5	Even a straight same-name path yields [depart, arrive]
A6	The compass convention is pinned, including the wrap-around (350° → 10° is straight)
A7	The public surface exposes the engine-A exports and createHttpRoutingSource
A8	Structural: no new Map( in astar.ts

---

2. How ALT routing is supposed to work

STATUS: COMMITTED, NOT BUILT. ALT landmark preprocessing is the c2 rung of the measured mitigation ladder, and it is scheduled as Phase 8 — ALT Landmark Preprocessing (Routing Backend v2) in the v1.x milestone (.planning/ROADMAP.md). docs/KNOWN-LIMITATIONS.md lists it as a "Next-milestone item, not built". docs/ROAD-GRAPH.md names it as the still-$0 alternative to Workers Paid. No ALT code exists in this repository. Everything in this section is a description of the intended mechanics, not an inventory of shipped code. The six design decisions Phase 8's plans specify — landmark count, coverage gate, potential combination, gate semantics, drift guard, rollout mechanics — and why each recommendation is the recommended one, are in §2.5.

2.0 ALT, word by word

The name is an acronym: A* (the search already in routing/src/astar.ts) + Landmarks (a fixed set of reference vertices) + Triangle inequality (the rule that turns distances to those references into a guaranteed underestimate).

• "A*" — the algorithm does not change. Same heap, same typed arrays, same bidirectional stop rule, same output. ALT only swaps the body of the heuristic function that supplies h_f and h_b.

• "Landmarks" — in ALT, a landmark is a vertex of the routing graph, chosen once at build time and used as a fixed reference point. It has an id and coordinates; it has no name, address, or POI record. It is not KLCC. This is the single most confusing word in the document — §0.8 separates the two meanings.

• "Triangle inequality" — for any three points x, y, z, going via a third point can never be shorter than going direct:

  d(x, z) ≤ d(x, y) + d(y, z)
  

  Rearranged, d(y, z) ≥ d(x, z) − d(x, y): if two distances from a fixed reference x are known, the third distance gets a guaranteed floor without any search. That is the whole trick — distances to landmarks are precomputed, so the remaining distance can be bounded cheaply.

• What it buys — a tighter h at query time. Same route, same optimality guarantee, fewer expanded nodes.

A surveyor's-benchmarks analogy: if you know how far you are from three fixed benchmarks and how far the destination is from the same three, you can put a floor under how far you must still travel — no route from you to the destination can be shorter than (distance from benchmark to destination) − (distance from benchmark to you). Each benchmark gives one floor; take the highest. Replace "benchmark" with "ALT landmark" and "floor" with "admissible lower bound", and you have ALT.

2.1 The problem ALT solves

The current heuristic is hav(v, goal) / maxSpeedMps — a straight-line bound inflated by the fastest speed in the entire graph. On a 311k-node metro graph where the fastest class is a 100 km/h motorway, the heuristic is extremely loose almost everywhere: on a local street the true route to a goal 15 km away might take 12 minutes, while the heuristic says "15 km at 100 km/h = 9 minutes". The gap between the bound and the truth is the wasted search.

ALT tightens the lower bound using precomputed distances to a small set of ALT landmarks (graph vertices — not POIs; §0.8). Instead of "how far is the goal in a straight line, at the fastest speed possible", it becomes "how far is the goal at all, via the triangle inequality over a set of fixed reference points".

2.2 The mechanics

Step 1 — ALT landmark selection (build time)

Choose a small set L of ALT landmarks — graph vertices, not POIs (§0.8) — typically 16 to 32, spread across the graph. The standard construction (Goldberg–Harrelson) picks them to be far apart, commonly with a farthest-point sweep:

1. Start from any vertex and run Dijkstra over the graph; the farthest reachable vertex becomes landmark 1. That Dijkstra row is also the first row of the landmark table, so selection and preprocessing share work.
2. For every vertex v, keep nearest[v] = min over chosen l of d(l, v).
3. Pick the vertex with the largest nearest[v] as the next landmark, run Dijkstra from it, and update nearest[].
4. Repeat until |L| is 16–32 (or until the sweep stops finding a meaningfully farther vertex).

On this directed graph a single start vertex cannot reach every other vertex, so a practical sweep runs over the largest strongly-connected component (the measured KL build put all gazetteer landmarks in one such component) or over an undirected view used only for selection. Which choice the phase makes is a design decision; it does not change the runtime bound, which comes from the table in Step 2.

Why far apart. A landmark gives a tight bound for a query whose shortest path passes near it; the triangle inequality still holds — just more loosely — when it does not. Spreading the landmarks maximizes the chance that at least one is near any given route.

Why ALT landmarks often look like arterial junctions. Selecting by travel-time distance tends to land on long arterial or motorway chains, because those are the farthest-apart places in seconds. Looking like a junction is a consequence of the selection, not its criterion — and it does not make the vertex a POI (§0.8).

Why this is cheap where it counts. Each iteration costs one Dijkstra run; that run also becomes the landmark's table row (Step 2). At 311k nodes and 677k directed edges the whole pass is minutes on a maintainer machine — entirely off the request path.

Step 2 — the per-vertex landmark distances (build time)

For each landmark l ∈ L and each vertex v, precompute d(l, v) — the shortest time from l to v. The result is a table of shape |L| × |V|: 16 landmarks × 311k nodes × 4 bytes ≈ 20 MB; 32 landmarks ≈ 40 MB.

Units are load-bearing. Distances must be in the same units as the edge weights. Because the search minimizes travel time in seconds (edgeSeconds), the landmark table must be in seconds. A table measured in metres would be dimensionally wrong — it would not bound a seconds-valued edge cost, and the "lower bound" would not be a bound at all.

Directed-graph caveat. This graph is directed — the oneway mirrors make d(l, v) and d(v, l) different, and some vertices are unreachable from a given landmark (d(l, v) is infinite for them; the max simply ignores those terms). The table must therefore be directed shortest-path time d(l, ·) in the direction traffic may actually flow. One from-landmark row per landmark is still enough for both directional heuristics, because both bound a distance from v to a target using d(l, target) − d(l, v). An implementation that stores the transposed distances d(·, l) instead must keep them separate; which storage shape the ALT build chooses is a design decision, not a shipped fact.

This is where the cost moves. The whole point of ALT is that the preprocessing is build-time and the runtime cost is $0 — the table is uploaded once to R2 alongside (or inside) the graph binary, and the Worker reads it exactly like the graph.

Step 3 — the lower-bound potential (runtime)

For a query from s to t, the potential is

h_ALT(v) = max over l ∈ L of  ( d(l, v) + d(l, t) − d(l, s) )

Read it as: the best landmark l gives a lower bound on the cost of a path s → v → t — go from s to l, then from l to v, then from v to t, and subtract the part of the s → l leg that is already covered by s → l → t. The triangle inequality guarantees this is a lower bound on the true distance:

d(s, t) ≤ d(s, l) + d(l, t)          ⟹  d(s, t) ≥ d(l, t) − d(s, l)

and the "via v" variant gives d(s, v, t) ≥ d(l, v) + d(l, t) − d(l, s).

The bound the A* frontier actually consumes — step by step. For one landmark l and a forward search toward target t, the triangle inequality on (l, v, t) gives

d(l, t) ≤ d(l, v) + d(v, t)      ⟹      h_l(v) = d(l, t) − d(l, v) ≤ d(v, t)

so h_l(v) never exceeds the true remaining time from v to t. That is the per-vertex underestimate the search needs; taking the maximum over landmarks picks the tightest one.

For a path that goes s → v → t, both legs get their own floor:

d(s, v) ≥ d(l, v) − d(l, s)        (triangle on l, s, v)
d(v, t) ≥ d(l, t) − d(l, v)        (triangle on l, v, t)

Adding the two cancels d(l, v):

d(s, v) + d(v, t) ≥ d(l, t) − d(l, s)

That surviving quantity is independent of v — which is exactly the property the BH meet-key argument in §1.3 relies on.

Implementation caution — the + d(l, v) term. The formula block above carries a per-vertex d(l, v) term. The part the triangle inequality actually certifies is the cancellation result just derived (d(l, t) − d(l, s), v-independent), plus the per-vertex form h_l(v) = d(l, t) − d(l, v). The ALT implementation must either use one of those proven forms or prove the written expression directly before relying on admissibility. This is not pedantry: on a line graph with l=0, s=10, v=8, t=20, the written expression gives 8 + 20 − 10 = 18, while the true cost of s → v → t is 2 + 12 = 14. Success criterion 2 — "identical tolerance verdicts" on the corpus re-run — is the gate that catches this class of algebra error; it is not a formality.

Why the max over landmarks matters. Each landmark l produces a bound that is tight when the true shortest path from s to t passes near l. Different landmarks are tight for different pairs of endpoints, so taking the maximum picks the best-bound landmark per query. This is the tightness/occlusion tradeoff:

	Effect
More landmarks	Tighter bounds (less search) — but a bigger table (build-time bytes, R2 storage, decode cost, and cache pressure in the 128 MB isolate)
Fewer landmarks	Smaller table — but more "occlusion": for a pair whose shortest path avoids all landmarks, every individual bound is loose and the max is still loose
Poorly chosen landmarks	Clustering wastes the table: all landmarks in one district bound intra-district pairs well and cross-city pairs poorly

The classic mitigation for occlusion is the "covering" refinement: take two "covering" landmarks and use the bound min( d(l1,v) + d(l1,t), d(l2,v) + d(l2,t) ) for a covering pair, combined with the max over the ordinary set. That is a refinement the phase would consider; it is not required for correctness.

Step 4 — admissibility

The ALT potential is admissible (never overestimates) and, with the right conditions, consistent — which means the same optimality proof applies. This is what the roadmap's success criterion 2 means by "Route optimality unaffected (ALT is admissible — the corpus re-run stays green with identical tolerance verdicts)".

Crucially, admissibility is not free: a consistent potential h is required for the plain A* reductions to stay feasible. The ALT bound is consistent with respect to the landmark distances, but the graph's edge weights must satisfy the corresponding inequality for consistency to transfer — this is the technical detail the phase must resolve, and the reason the roadmap's criterion 2 ("identical tolerance verdicts") is a real gate rather than a formality.

Step 5 — where the cost goes: build time vs request time

This is the whole economic argument for ALT in one picture. The expensive work happens once, on a maintainer machine, when the graph is rebuilt. A request on the free-tier Worker only ever reads the resulting table.

flowchart LR
    classDef build fill:#1A1A1A,stroke:#000000,stroke-width:2px,color:#FFF8F0
    classDef buildstep fill:#736B1E,stroke:#4A440F,stroke-width:2px,color:#FFF8F0
    classDef run fill:#EB8008,stroke:#8A4C00,stroke-width:2px,color:#1A1A1A
    classDef runstep fill:#D9D2C6,stroke:#1A1A1A,stroke-width:2px,color:#1A1A1A

    subgraph BUILD["BUILD TIME — paid once per graph rebuild (maintainer machine)"]
        direction LR
        B1["farthest-point sweep<br/>pick 16–32 ALT landmarks"]:::buildstep
        B2["one Dijkstra per landmark<br/>over 311k nodes / 677k edges"]:::buildstep
        B3["landmark table<br/>≈20–40 MB of seconds"]:::buildstep
        B4["encode layout v2<br/>upload to R2"]:::build
        B1 --> B2 --> B3 --> B4
    end

    subgraph RUN["REQUEST TIME — every /api/route call (free-tier Worker)"]
        direction LR
        R1["decode graph + table<br/>once per cold isolate"]:::runstep
        R2["A* inner loop<br/>array reads + adds"]:::runstep
        R3["one optimal route"]:::run
        R1 --> R2 --> R3
    end

    B4 -.->|"static artifact — no request<br/>ever runs the Dijkstra pass"| R1

What "preprocessing at build time, $0 at runtime" buys. The |L| Dijkstra runs are O(|L| · E log V); at this graph size that is minutes of CPU. Moving that to build time means the recurring bill stays at zero: R2 stores the table inside the free tier, and the Worker's per-request cost is lower than today, because a landmark lookup is a couple of array reads where the haversine heuristic calls Math.sin, Math.cos, and Math.asin per node per side. Workers Paid, by contrast, buys CPU by the month — a recurring $5/mo that breaks the $0 law — while ALT pays once in engineering and then costs nothing. That is why ALT is the chosen lever and Workers Paid was rejected.

2.3 How ALT would slot into the existing bidirectional A*

This is the part that matters most for this codebase, because the current engine is not a textbook unidirectional A* — it is a BH bidirectional search with Ikeda potentials.

Bidirectional A* needs two potentials, not one. The current engine has:

• h_f(v) = hav(v, goal) / maxSpeedMps — the forward heuristic,
• h_b(v) = hav(v, origin) / maxSpeedMps — the backward heuristic,
• and the opposite potentials p_f(v) = (h_f(v) − h_b(v)) / 2, p_b(v) = −p_f(v).

So ALT must supply both h_f and h_b:

h_f(v) = max over l ∈ L of ( d(l, v) + d(l, goal)  − d(l, origin) )   // bound on origin→v→goal
h_b(v) = max over l ∈ L of ( d(l, v) + d(l, origin) − d(l, goal)   )   // bound on goal→v→origin

These are the ALT potentials with the query endpoints swapped. Note the sign structure: h_f and h_b are not independent — they share the same landmark table, and the ALT form gives them a natural relationship. The Ikeda potential p_f = (h_f − h_b)/2 is then recomputed from the ALT-derived values, and the feasibility argument (each reduction non-negative because each feasibility is the sum of two consistencies) has to be re-proven for the ALT potentials, not assumed. The same algebra caution as §2.2 applies to these two lines: the proven per-vertex form is d(l, target) − d(l, v), so re-derive before implementing.

The picture the formulas encode:

flowchart LR
    classDef landmark fill:#736B1E,stroke:#4A440F,stroke-width:2px,color:#FFF8F0
    classDef known fill:#EB8008,stroke:#8A4C00,stroke-width:2px,color:#1A1A1A
    classDef unknown fill:#D9D2C6,stroke:#1A1A1A,stroke-width:2px,color:#1A1A1A
    classDef target fill:#1A1A1A,stroke:#000000,stroke-width:2px,color:#FFF8F0

    L["ALT landmark l<br/>(a graph vertex — not a POI)"]:::landmark
    V["vertex v<br/>(where the search is right now)"]:::unknown
    S["source s<br/>(the snapped origin)"]:::known
    T["target t<br/>(the snapped destination)"]:::target

    L ---|"d(l,v) — precomputed"| V
    L ---|"d(l,s) — precomputed"| S
    L ---|"d(l,t) — precomputed"| T
    S -.->|"d(s,v) — NOT in the table"| V
    V -.->|"d(v,t) — the quantity h must never overshoot"| T

Solid lines are rows of the landmark table (known without searching). Dotted lines are the quantities the search is trying to learn. The triangle inequality relates them: d(v,t) ≥ d(l,t) − d(l,v) gives a floor for the dotted edge on the right, and the same move on (l, s, v) gives d(s,v) ≥ d(l,v) − d(l,s). ALT is the art of squeezing the best floor out of those three known lengths.

Concretely, the code changes ALT would require:

File	Change
routing/src/graph.ts	A graph-layout v2 header that carries the landmark table (or a second R2 object holding it). The pinned CSR v1 layout stays readable — v2 must decode v1 unchanged, or v1 must be retired deliberately
routing/src/astar.ts	potential(v) currently computes hav(v,goal)·scale and hav(v,origin)·scale lazily. ALT replaces the body with a landmark-table lookup — still lazy, still allocation-free, but the inner loop reads a Float32Array row instead of calling Math.sin/Math.cos/Math.asin. That is the real win: the ALT evaluation is a handful of array reads and adds, versus a trig-heavy haversine
routing/src/astar.ts	The consistency/feasibility argument must be re-established for the ALT potentials (the BH stop rule's optimality proof depends on it)
routing/scripts/build-road-graph.mjs	A landmark-selection pass + 16–32 Dijkstra runs over the built graph, writing the table
routing/test/astar.test.mjs	The 625-pair Dijkstra-equivalence sweep (A1) re-run — the standing proof must stay green with ALT potentials substituted
routing/scripts/measure-route-cpu.mjs	Re-measure the p95; the roadmap's criterion 1 is "longest KL-metro routes route within the free-plan CPU budget (p95 under the ceiling, measured by the existing CPU gate)"

The runtime cost is $0 — the table is a static artifact uploaded once, and the per-query cost is lower than today (array reads instead of trigonometry). This is precisely why the roadmap calls it "still $0 at runtime" and why it beats Workers Paid on the project's own terms.

2.4 What ALT does not fix

ALT tightens the heuristic. It does not change:

• the graph size — the 311k nodes, the 14.7 MB binary;
• the oneway law — bit 0 is still the traversal authority;
• the snapping behavior, the 3×3-cell candidate window, or the honest-miss contract;
• one-route-only policy on /api/route;
• the fixture backend's 200 m matching law.

It also does not fix the fragmentation failure mode that killed ladder step (a) — that was a graph-construction problem, and it was correctly rejected on correctness rather than patched.

2.5 The six planned decision points — the options, and what Phase 8 recommends

Status: a planning record, not shipped code. These six decisions are specified in the Phase 8 plans (.planning/phases/08-alt-landmark-preprocessing-routing-backend-v2/08-01-PLAN.md … 08-05-PLAN.md). Every "will" in this section means "the plan specifies". The phase's locked user decisions (D-01…D-05 in the phase CONTEXT) are the frame; what follows are the decisions D-01…D-05 deliberately left open, each with the options that were on the table and why the recommendation is the recommendation. The maintainer reviewed all six and accepted the recommendations as written (2026-10-25) — recorded here so the why survives next to the what.

1. How many landmarks — a formula, not a constant (inside D-02's scaling rule)

The decision. D-02 locks that the count is node-count-proportional and measured, in the 16–32 band. It does not lock the formula.

Option	What it means	Why not / why yes
(a) hard-pin a constant ("24, forever")	Simplest; one build, one number	A constant that is right at KL's 311k nodes is wrong at Malaysia's ~6M (per-landmark bytes scale with node count: ~1.19 MB/landmark at KL, ~12–24 MB/landmark at country scale — the trap D-02's wording exists to close). Every future rebuild re-litigates the number by hand.
(b) build once per candidate L, keep the smallest that passes the CPU gate	Maximally "measured"	Turns every rebuild into a multi-build campaign (L=16, 20, 24, 28, 32 — five Overpass-class builds to touch one knob); the gate is the arbiter anyway, so the extra builds buy evidence the gate already provides.
(c) a named formula + a measured override — L = clamp(round(N / 13,000), 16, 32), plus a maintainer-only --landmarks <n> rebuild flag (hard-capped at 128)	Recommended	Self-scales (24 at KL today; re-derived mechanically at any future scale, per D-02's own rationale); the divisor 13,000 is a named, doc-commented constant with its measured justification; the override is the campaign's knob (raise to 32 only if the gate honestly fails at 24 — the pre-committed ladder), and its cap keeps a fat-fingered count from producing an envelope-busting table.

The formula lands on round(311,325 / 13,000) = 24 — mid-band, where the research expects the curve to flatten (more landmarks past ~24 buy little steering at metro scale but linear bytes).

2. The coverage gate — every landmark must reach ≥ 90% of the graph

The decision. Whether the build verifies the landmark tables are actually usable before writing the binary, and how hard.

Option	What it means	Why not / why yes
(a) no coverage gate	Trust the giant SCC	A silently fragmented rebuild (the §1.2 *_link failure mode: 7.7% of nodes severed) would ship tables riddled with 0xFFFF sentinels — steering degrades toward haversine for everyone, nothing prints a warning, and the CPU gate failure would be diagnosed as "ALT didn't work" when the real bug is extract fragmentation.
(b) require 100% reachability per anchor	Strongest-sounding	Too strict for a directed graph with genuine fringe: dead-end driveways and small islands are allowed to be unreachable from a landmark; demanding 100% would fail honest builds forever and tempt someone to lower it quietly later — the worst gate shape.
(c) a named fraction gate — LANDMARK_MIN_COVERAGE_FRACTION = 0.90; any anchor below it → build exits 1, previous binary untouched	Recommended	The measured KL build is one giant strongly-connected component covering ~305k of 311k nodes (≈ 0.98), so 0.90 has honest headroom while still catching a fragmented extract before it becomes a hosted binary. Named constant, doc-commented with the SCC measurement; the build prints per-anchor coverage either way (print-the-measurement law).

3. The runtime potential — max(ALT bound, haversine bound), always

The decision. What h_f(v) / h_b(v) are when at least one landmark's table entries are valid for v.

Option	What it means	Why not / why yes
(a) pure ALT while any landmark is valid; haversine only when every entry is a sentinel	The textbook shape	Creates a steering cliff: a node whose last valid landmark entry flips to sentinel gets a discontinuous heuristic jump. Correctness is unaffected either way (both shapes are admissible + consistent), but the discontinuity is exactly where hard-to-reproduce search-path differences would live.
(b) always take the max of the ALT bound and the existing haversine bound, per direction	Recommended	The max of two admissible heuristics is admissible; the max of two consistent heuristics is consistent — so optimality is untouched (A1's 625-pair sweep re-proves it with ALT live). The haversine term is already computed lazily, so the cost is two comparisons per node touch; the benefit is a heuristic that is continuous across the sentinel boundary and never worse than today's engine at any node (ALT can only add tightness, never subtract it). On the fringe nodes where all landmarks are sentinels, the max simply is the haversine bound — the fallback falls out of the max instead of being a special case.

The §0.5/§1.3 machinery is untouched by this choice: the ALT-derived h_f/h_b feed the same Ikeda potential p_f = (h_f − h_b)/2, whose survey-verified algebra is what the phase actually re-uses.

4. Pairs the frozen record could not snap, but the new build can — "re-snapped", info not violation

The decision. D-03's optimality gate compares post-ALT route seconds against the frozen pre-ALT record (the 100-pair coordinate-pinned alt-baseline.json), per pair. What happens to a pair the old binary could not snap at all?

Option	What it means	Why not / why yes
(a) any outcome-class change is a violation, including unsnappable → routed	Simplest rule to state	Conflates two unrelated things. "Unsnappable" was a property of the old extract's snap grid at that random coordinate — a data statement, not an optimality statement. ALT is steering-only (the A1 law: same edges, same cost model), so a re-snap is extract drift speaking, not an optimality break; failing the gate on it would manufacture a false failure and pressure someone into re-recording the baseline — which D-03's design forbids (the record is immutable; that is what makes the comparison trustworthy at all).
(b) gate exactly D-03's letter — the reachable ↔ unreachable flip is a violation — and report formerly-unsnappable pairs that now route as counted "re-snapped" info, with a printed warning if any exist	Recommended	The seconds-equality gate (± 0.1%) and the reachable/unreachable class law are enforced exactly as decided; the re-snapped rows are printed, counted, and warned about — drift is never hidden, it is just not misfiled as an optimality failure. A mass of re-snapped rows is itself informative (the extract moved) and escalates to a human, exactly like the counts-drift warning the gate also prints.

5. The 200 ms drift guard outlives the c3 class — as hygiene, not acceptance

The decision. §1.9's route-cpu budget gate compares a re-run p95 against a 200 ms drift guard because the documented accepted state was 38–93 ms. When Phase 8 retires c3, what does the gate assert?

Option	What it means	Why not / why yes
(a) delete the guard: any p95 > 8 ms fails budget-audit	Maximally strict	The measurement host is a shared Linux box with documented ≈ 2× run-to-run variance, and the 06-04 history measured 38–93 ms on identical code. An 8 ms hard gate on that host makes the audit flaky at the exact moment the record finally turns green — and a flaky gate trains everyone to ignore it.
(b) keep the two-tier law, re-anchor the wording: ≤ 8 ms → PASS; 8–200 ms → exit 0 with a loud warning ("over the product budget within the shared-host variance guard — the c3 class was RETIRED in Phase 8; re-run on a quiet box before treating it as a regression"); > 200 ms → hard fail ("uncharted regression — the retired class does not explain this")	Recommended	The guard's meaning flips, not its threshold: it is no longer "the accepted degradation band" — that sentence dies with c3 — but "below this, suspect the box before suspecting the code". Beyond 200 ms nothing the host does explains it, so that stays a hard fail. The stale strings ("the DOCUMENTED, ACCEPTED c3 class", "the ALT landmark lever is a next-milestone item") are deleted from the gate law in the same change, so no record anywhere keeps accepting a degradation that no longer exists.

6. The rebuild runs during execution; the R2 upload stays manual

The decision. Where the line between "the phase executes" and "the maintainer acts" sits.

Option	What it means	Why not / why yes
(a) plans stop at code; the maintainer builds, uploads, and measures by hand afterwards	Cleanest separation	The phase's success criteria are measured numbers, and the build stage is exactly the kind of code that can pass every unit gate and still be wrong on the real graph. Stopping at code would turn 08-05's verdicts into "measure it yourself later" — the phase would not be able to retire c3, because D-05's evidence law requires the printed numbers.
(b) the build plan runs the real Overpass fetch + rebuild + --check as an execution task (maintainer-time, minutes, the same public endpoint as the 2026-10-24 build); only the upload remains manual	Recommended	The rebuild is what makes 08-05's campaign evidence rather than hope, and it is fully gated (envelope, coverage, quantum, collect-then-write — a failed gate leaves the previous binary untouched). The upload stays manual deliberately: it is an account-level act on the maintainer's own bucket (the fork contract — your graph, your bucket), and it is the migration's single go-live switch: D-01 makes re-uploading the rebuilt binary the entire rollout, and until that one upload, an old binary is the designed router-pending state, not an outage. Automating it would put a production-data replacement behind a script's exit code.
(c) automate the upload too	Fully hands-off	Breaks the fork contract's ownership boundary and removes the human from the only irreversible step.

---

3. Pros and cons of every approach

3.1 Summary table

Approach	Status	p95 CPU (real KL graph)	Optimality	Correctness risk	Cost	Verdict
Fixture routes (backend #1)	Shipped	n/a — no search	as computed by the OSRM demo at build time	Very low — 15 curated pairs, RT2b-proven public origins	$0, 16,576 B gz / 102,400 B budget	Kept as the demo corpus and the ladder's fallback
Unidirectional A*	Measured, replaced	≈ 38 ms (p95)	Provably optimal	Low	$0	Rejected on CPU; the heuristic's looseness is the cause
Bidirectional A* (BH)	Shipped	≈ 38 ms (p95); current band 38–93 ms; budget record 83.989 ms	Provably optimal (625-pair Dijkstra sweep)	Low — two soundness bugs found and fixed by the gates	$0	Kept: no worse on p95, better on short product routes
Graph pruning (drop tertiary + residential)	Measured, reverted	≈ 18 ms — still FAIL	—	Fatal: 12/25 pairs unreachable	—	Rejected on correctness (D-03) and reverted
ALT landmark preprocessing	Committed, not built	Expected to bring cross-metro routes under the ceiling (the roadmap's criterion 1) — no measurement exists	Provably optimal (admissible; criterion 2 re-runs the corpus)	Medium — new build-time machinery, new binary layout	$0 runtime; build-time engineering + ~20–40 MB table	The committed upgrade lever
Workers Paid	Rejected	Removes the ceiling entirely	unchanged	none	$5/mo — breaks the $0 law	Rejected by the maintainer

3.2 Fixture routes — pros and cons

Pros

• Zero runtime search. No A*, no graph decode, no CPU to speak of. The corpus rides the bundle.
• Deterministic and offline-provable. routing/scripts/route-corpus.mjs recomputes every geometry↔summary consistency (haversine length within 0.85–1.10× the route's own distanceM; average speed within 1.0–30 m/s), proves the polyline6 round-trip exactly, checks the licence header, and enforces the gzip budget — all offline.
• Privacy-clean by construction. Every origin and destination is a gazetteer landmark, and RT2b proves each pinned origin equals the landmark's committed coordinate within 1e-4°. No user coordinate can enter the dataset (D-12).
• Alternatives for free. The corpus carries up to 3 routes per pair (8 multi-route pairs against a floor of 4) — RTNG-02's chip/redraw surface, which the Worker path deliberately does not offer.

Cons

• The 200 m law is a hard ceiling. A driver 250 m from the pinned origin gets null. The pad is sized for GPS jitter at a landmark, not for a real trip.
• 15 destinations. The coverage is the curated KL gazetteer, not the city.
• No maneuvers. Fixture steps are always empty arrays (D-10) — honest, but the guidance surface needs real steps, which is exactly what engine A supplies.
• Build-time dependency on a free best-effort service. The OSRM demo server produced the geometry. That is acceptable precisely because the output is committed — the runtime never touches it. A server policy change breaks the (rare) regeneration script, never the product.

3.3 Unidirectional A* — pros and cons

Pros

• Simplest possible implementation. One search, one heap, one heuristic, one closed set.
• The heuristic is trivially consistent — hav(v, goal) / maxSpeedMps — and the optimality proof is one line.
• Lower per-node overhead than the bidirectional variant (no potential, no reverse index, no meet probes).

Cons

• p95 ≈ 38 ms on the real graph — 4.75× over the 8 ms ladder budget. The weak max-speed heuristic balloons on 20–30 km routes: it assumes every metre of the route is travelled at the fastest speed in the graph.
• Search radius grows with route length. The classic A* pathology on a loosely-heuristic'd graph.

Verdict: replaced by the bidirectional variant. Not revisited — the ALT potential in §2 is the answer to this root cause (heuristic looseness), not to the search direction.

3.4 Bidirectional A* (BH, Ikeda potentials) — pros and cons

Pros

• Provably optimal. The BH stop rule — top_f + top_b ≥ mu — settles the goal optimally, because the meet-sum is a v-independent constant. The 625-pair exhaustive Dijkstra-equivalence sweep is the standing proof, re-run on every pass.
• Better on the routes that matter. Short product routes (2–8 km) improved measurably; the halved radius per side pays off exactly where the product's common trip lives.
• No layout change. The reverse CSR is a derived in-memory WeakMap structure — the pinned binary layout is untouched.
• A real bug-finding machine. The bidirectional implementation exposed two soundness bugs (phantom arcs from reading out-edges as in-edges; mirrored-infeasible reduction signs) that the equivalence sweep and the oneway law caught. A simpler engine would not have been stress-tested the same way.

Cons

• p95 did not improve: still ≈ 38 ms. The diagnosis in the code and the plan summary is exact — the potential split halves each side's heuristic steering, cancelling the halved search radius. Bidirectionality buys radius; the Ikeda potential costs steering. The two effects cancel.
• More machinery. The reverse CSR, the potential computation, the meet probe, the alternation knob — all of it must be correct, and two of those things were wrong at first.
• The alternation knob is a trap. Raw-top comparison starved the backward side (19,501 : 3) and ran 4× slower than unidirectional. Heap-size comparison fixed it. This is a correctness-neutral choice that is easy to get wrong.

Verdict: kept. It is sound, no worse on the p95 class, better on the short-route class, and it is the engine ALT would plug into.

3.5 Graph pruning (dropping road classes) — pros and cons

Pros

• The only lever that actually moved the number. p95 fell from ≈ 38 ms to ≈ 17.8 ms — nearly halving it — and the graph shrank from 311k to 127k nodes.
• Zero runtime cost, zero build complexity. One edit to ACTIVE_CLASSES and a rebuild.
• A real, reproducible experiment with the numbers recorded in measure-route-cpu.mjs's LADDER HISTORY and build-road-graph.mjs's comment block.

Cons

• It broke the product. 12/25 pairs became unreachable, including 8/15 golden corpus pairs. The dropped classes (tertiary, residential) are the fine mesh tying gazetteer (POI) landmarks to the arterial network — the fixture endpoints, e.g. KL Tower and KL Sentral; see §0.8. Without that mesh the graph fragments.
• The failure mode is the worst kind. An unreachable pair resolves null, which renders as "the router is not ready for this trip". Half the product's destinations degrading to that is not a smaller graph — it is a broken one.
• Correctness is not negotiable against CPU. The project rejected it on D-03 grounds and reverted. This is the clearest statement in the repo that the routing CPU budget is subordinate to the routing correctness law.

Verdict: rejected. Reverted to the full 13-class set. The lesson is now encoded in the build script's comment, so the experiment is not silently re-proposed.

3.6 ALT landmark preprocessing — pros and cons

Terminology check: in this subsection "ALT landmark" means a graph vertex, not one of the searchable POI landmarks. §0.8 has the full distinction.

Pros

• $0 at runtime. The expensive part is build-time; the runtime reads a static table. It beats Workers Paid on the project's own terms, which is why the maintainer chose it over the $5/mo plan.
• It attacks the root cause. Every other lever either moved cost around (bidirectional) or broke correctness (pruning). ALT makes the heuristic tight — the one thing that was actually wrong.
• It is cheap at query time. The ALT evaluation is array reads and adds, versus the current haversine call's sin/cos/asin per node per side. The hot loop gets cheaper per node even as the search gets smaller.
• Optimality is preserved. ALT is admissible; the roadmap's criterion 2 re-runs the corpus and the A1 sweep.
• The infrastructure is already there. The build script, the R2 upload path, the CPU gate, the equivalence sweep, the budget record — all of it exists and is exercised. The new work is a preprocessing pass and a layout v2.

Cons

• It is not built. No landmark selection code, no Dijkstra-per-landmark pass, no v2 layout, no ALT potential, no measurement. Every performance claim about it is a projection, not a measurement.
• Build-time cost. 16–32 Dijkstra runs over 311k nodes, plus the landmark selection. Minutes of build time — acceptable, but it is real work.
• Storage cost. ~20–40 MB of landmark table on top of the ~14.7 MB graph binary. R2 is free-tier, but the Worker isolate has a 128 MB memory ceiling and must hold the decoded graph and the table. The decode cost also lands inside the cold-start path.
• Occlusion. Landmarks that do not lie near the true shortest path give loose bounds. More landmarks tighten the bound but grow the table — the tightness/occlusion tradeoff in §2.2 is a genuine design decision, not a knob with a free setting.
• Bidirectional interaction is non-trivial. The BH proof requires both h_f and h_b to be consistent on their own search graphs, and the Ikeda potential p_f = (h_f − h_b)/2 is derived from their difference. ALT's landmark form gives h_f and h_b a different relationship than the current haversine pair, so the feasibility argument must be re-established, not inherited. This is the single largest technical risk in the phase.
• It inherits everything the current engine inherits. The 10 ms ceiling, the 2× measurement variance, the shared dev box.

Verdict: the committed upgrade lever (c2), scheduled as Phase 8, not built.

3.7 The backend ladder as a strategy

The ladder itself is an approach worth naming, because it is the project's answer to "a single backend is fragile":

Rung	What it is	What it buys
#1 fixture	The committed golden-pair corpus	The product always has something honest to draw for the flagship demo trips, even when the graph is absent or the CPU budget blows
#2 engine-a	The live CSR graph router	Arbitrary origins, real reroutes, real maneuvers
#3 (documented)	Fully client-side router (Engine B / WASM)	Routing cost leaves the Worker entirely; origin and destination never touch a server — the privacy audit's best outcome
#4 (documented)	Valhalla on a VPS	A full-featured production router, if the $0 law is ever revisited

The ladder is not switchable — the import site constructs the backends in code. That is a deliberate choice: an env-driven backend switch would put a privacy-relevant behaviour difference behind a config value.

---

4. How this all relates to the project's philosophy

4.1 Dieter Rams — "less, but better"

The design philosophy in DESIGN.md is functional clarity, accented colours, timeless restraint. The routing engine is where that philosophy becomes an engineering constraint rather than a visual one.

"Less" is the 10 ms budget. A phone-based navigator that routes on a $0 Worker cannot afford a heavyweight engine. That single ceiling is why the search is a typed-array A* over a CSR binary rather than a general-purpose routing library, why the graph is class-filtered, why only one route is returned per request, and why the hot loop allocates nothing. The Rams refusal to add ornament maps exactly onto the refusal to add alternatives generation, penalty runs, or a second search.

"Better" is measured, not asserted. routing/scripts/measure-route-cpu.mjs times the real engine over the real binary; routing/scripts/route-corpus.mjs re-derives the fixture corpus's consistency offline; npm run budget-audit compares every number against its documented free-plan ceiling and prints negative headroom as measured. The A1 sweep proves optimality exhaustively rather than by spot check. This is Rams' "good design is as little design as possible" applied to an algorithm: nothing is added that does not earn its cost, and every claim is a measurement.

Honest failure is a designed surface. When routing cannot be done in budget, the answer is the router-pending card — not a blank map, not a wrong line, not a 500. The engine's degradation path is: CPU exhausted → 1102 → the client's fail-honest null → the pending state. That is docs/CORE-CONCEPTS.md §5 ("Honest failure as the design language") applied to the algorithm.

4.2 Privacy-first

D-12 — public-data provenance. The routing data plane is built entirely from public OpenStreetMap data fetched via the public Overpass API, with the ODbL attribution travelling with the derived artifact (docs/ROAD-GRAPH.md is the notice surface; the fixture corpus carries _license / _attribution / _notice / _source inside the file itself). No user coordinate ever enters a fixture — this is not a promise but a mechanically proven property (RT2b).

The origin lives in memory. The live fix is the origin. It is matched in memory and dies with the frame. routing/src/types.ts and fixture-source.ts both state it: "No logging, no storage, no network — request coordinates never leave the caller's frame." The routing/src tree reads no environment, holds no secrets, and performs no network I/O.

One position does leave the device — deliberately. POST /api/route sends the origin to our own Worker. This is the one in-drive position the privacy law permits transmitting (the origin must reach the router), and the audit records the fetch allowlist as relative paths (/api/route), not hosts.

Category-only logs. The router's only log lines are "[route] rejected: unauthorized" / "[route] rejected: malformed" — never coordinates, ids, or payloads. The graph binary is public data; the request is not.

Engine B would make this strictly better. The documented third rung — routing computed in the webview, graph downloaded and HTTP-cached on device — is the privacy audit's best outcome: origin and destination never touch a server at all. ALT is not a privacy change; it is what makes the $0 server-side engine good enough that Engine B remains a choice rather than a necessity.

4.3 Free-first infrastructure

The $0 law is a product constraint, not an aspiration (docs/BUDGETS.md). Every ceiling is a documented Cloudflare limit; every measurement sits beside it.

ALT was chosen over Workers Paid for exactly this reason: $5/mo breaks the law, while ALT costs build-time engineering and stays $0 at runtime. The maintainer's decision (recorded in the 06-04 summary) is unambiguous: "c3 now, c2 next milestone."

The whole engine-A stack is free: Overpass public instance (build-time), Cloudflare R2 free tier (hosting), Workers free plan (compute), OpenFreeMap tiles (map). The routing package has zero runtime dependencies — the whole stack is V8-native.

The honest accounting. docs/BUDGETS.md records the A* CPU row as −76.0 ms headroom against the 8 ms ladder budget, with a 200 ms drift guard rather than a false green. A c3 degradation class is documented as the negotiated posture, not hidden. This is the Rams "honest failure" law applied to a budget: the number is printed where it was found, and the escalation ladder is documented rather than quietly closed.

4.4 The Engine A / Engine B ladder as an architectural statement

The routing ladder (fixture → engine-a → engine-b → valhalla) is the same shape as the search ladder (gazetteer → WASM geocoder → Photon). The point of a ladder is that no capability ever wedges to a single implementation:

• Each rung answers the same contract.
• Failures resolve honestly — null → a designed router-pending surface, never a blank map, never a fake route.
• The ladder is documented, not switchable — the import site constructs the backend in code. A routing backend is not a config value, because a routing backend is a privacy-relevant surface.

Engine A is today's rung: the Worker is the routing oracle (RP1 — worker-router.ts never fetches, never proxies; the graph comes from the bound R2 bucket and the A* is pure CPU). Engine B is the documented future rung, where the Worker serves only data.

ALT sits inside Engine A as its upgrade lever — it does not change the ladder, it makes the current rung good enough on cross-metro trips. That is the minimal, Rams-shaped move: improve the thing that exists rather than add a new thing.

4.5 The one-sentence version

Engine A routes today over a public OpenStreetMap CSR binary on a free-tier Worker with a provably-optimal, allocation-free bidirectional A* that is fast enough for the trips people actually take (2–8 km, 2–8 ms) and honestly degrades on the ones it isn't (cross-metro, 38–93 ms → router-pending). The committed fix — ALT landmark preprocessing, build-time, $0 at runtime — is scheduled and unbuilt, and when it lands it will tighten the only thing that was actually wrong: the heuristic.

---

Appendix A — File map

Path	Role
routing/src/types.ts	The routing contracts: RoutePoint, RouteRequest, RouteResult, RouteOption, RouteStep, RouteGeometry, RoutingSource, FixturePair
routing/src/graph.ts	The CSR binary codec — encodeGraph / decodeGraph, the pinned layout, the oneway flag
routing/src/astar.ts	The engine-A core — routeAstar (bidirectional BH), classifyTurn, deriveSteps, the NodeHeap, the reverse-CSR WeakMap
routing/src/snap.ts	snapToGraph — the server-side snapping authority, the memoized 3×3-cell grid
routing/src/geo.ts	haversineM, deriveCumulativeDistanceM — the distance authorities
routing/src/polyline.ts	decodePolyline6 / encodePolyline6 — the polyline6 codec
routing/src/fixture-source.ts	Backend #1 — createFixtureRoutingSource, ORIGIN_TOLERANCE_M (200 m)
routing/src/http-source.ts	Backend #2's client seam — createHttpRoutingSource
routing/src/index.ts	The package's public export surface
routing/src/data/route-fixtures.json	The committed fixture corpus (15 pairs) with the ODbL envelope
routing/scripts/build-road-graph.mjs	Overpass → CSR build, the envelope gate, the class filter, the ladder history
routing/scripts/measure-route-cpu.mjs	The A* CPU gate (p95 ≤ 8 ms) and the LADDER HISTORY
routing/scripts/route-corpus.mjs	The offline RT1–RT10 fixture gate
routing/scripts/fetch-route-fixtures.mjs	The maintainer-time OSRM fixture regeneration tool
routing/scripts/upload-road-graph.mjs	The R2 upload tool (shells wrangler)
routing/data/kl-roadgraph.v1.bin	The build artifact (gitignored)
routing/test/astar.test.mjs	The A1–A8 gates (625-pair Dijkstra equivalence, oneway, turn pins)
routing/test/fixtures/mini-graph.bin	The committed 5×5 mini-graph
routing/test/fixtures/golden-pairs.json	The pinned 15-pair corpus + thresholds
bot/src/routing/worker-router.ts	handleRoute, loadGraph, GRAPH_KEY — the server arm
web/src/main.ts	The composed ladder (engine-a → fixture)

Appendix B — The measured numbers, in one place

Metric	Value	Source
Free-plan Worker CPU ceiling	10 ms/invocation	docs/BUDGETS.md
The project's own ladder budget (20% margin)	p95 ≤ 8 ms	measure-route-cpu.mjs
Unidirectional A* p95 (311k-node graph)	≈ 38 ms	LADDER HISTORY, 2026-10-24
Pruned-graph p95 (127k nodes)	≈ 17.8 ms — and 12/25 pairs unreachable	LADDER HISTORY
Bidirectional A* p95	≈ 38 ms (documented band 38–93 ms)	LADDER HISTORY / docs/BUDGETS.md
Current budget-record p95	83.989 ms (runs 67.5–84.0 ms), headroom −76.0 ms	docs/BUDGETS.md
Short product routes (2–8 km)	2–8 ms — inside budget	docs/BUDGETS.md, docs/KNOWN-LIMITATIONS.md
Measurement run-to-run variance	≈ 2× (shared dev box)	docs/BUDGETS.md, 06-04 summary
Graph size	311k nodes (linked 13-class build); ~14.7 MB binary	build-road-graph.mjs, 06-04 summary
Graph binary envelope	1 MB floor / 80 MB ceiling / 30–80 MB expected	build-road-graph.mjs
Severed-node rate without *_link classes	7.7% of nodes in motorway islands	build-road-graph.mjs
Fixture corpus	15 pairs / 23 routes; gz 16,576 B / 102,400 B budget	docs/BUDGETS.md
Fixture origin tolerance	200 m (haversine)	fixture-source.ts
Multi-route fixture pairs	8 (floor 4)	route-corpus.mjs
A1 equivalence sweep	625 pairs (25×25), cost equality within 1e-6	astar.test.mjs
Route payload (gz)	79,815 B / 204,800 B	docs/BUDGETS.md
Worker memory ceiling	128 MB/isolate	docs/BUDGETS.md
KV list-op ceiling (cron)	720/day after the */2 retune (limit 1,000/day)	docs/BUDGETS.md

Appendix C — Related documents

• docs/ROAD-GRAPH.md — the fork contract, the build/upload/check flow, the ODbL notice
• docs/BUDGETS.md — the budget record: every measurement beside its free-plan ceiling
• docs/API.md — the POST /api/route contract, the null contract, the error codes
• docs/KNOWN-LIMITATIONS.md — the user-facing statement of the cross-metro degradation
• docs/CORE-CONCEPTS.md — the ladders, the $0 law, the honest-failure language
• docs/ARCHITECTURE.md — the module map
• DESIGN.md — the Rams philosophy