22 KiB
phase, verified, status, score, overrides_applied, re_verification, gaps, deferred, human_verification
| phase | verified | status | score | overrides_applied | re_verification | gaps | deferred | human_verification | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 08-alt-landmark-preprocessing-routing-backend-v2 | 2026-10-25T14:43:22Z | gaps_found | 1/3 roadmap success criteria (SC-2 ✓; SC-1 ✗; SC-3 ✗ as written — correctly not taken). All 5 plans' machinery must-haves verified. | 0 |
|
|
|
Phase 8: ALT Landmark Preprocessing (Routing Backend v2) — Verification Report
Phase Goal: Cross-metro routes route in-budget on the free plan: ALT (A*, Landmarks, Triangle-inequality) preprocessing over the CSR graph upgrades engine A's worst case while staying $0 — the c2 rung of the measured ladder, executed. Verified: 2026-10-25T14:43:22Z Status: gaps_found Re-verification: No — initial verification
Goal Achievement — the honest verdict
The phase's machinery landed completely and at high quality: ARG2 codec, landmark preprocessing, ALT steering, build-stage integration, the D-03 optimality gate, and every record rewritten honestly. The phase's core measurable deliverable did not land: the CPU verdict is a FAIL (p95 107–186 ms across hosts/modes vs the 8 ms budget), the pre-committed ladder ran to its documented stop, and the debug session proved the wall is structural (ALT inert on this binary; the fast configuration is provably unsound under the shared-average BH; the fix is out-of-constraint skeleton work). SC-2 (optimality) is the one success criterion achieved — and it was hard-won: the phase's own gates caught and fixed two real suboptimality bugs (Rule-1 fromTable, RC-1 per-node sentinel skip → F1).
This is the honest-FAIL branch the plan pre-committed to, executed faithfully. The gap that remains is a maintainer strategic decision, not a defect a closure plan can silently fix.
Observable Truths (roadmap contract)
| # | Truth | Status | Evidence |
|---|---|---|---|
| 1 | SC-1: Longest KL-metro routes route within the free-plan CPU budget (p95 under the ceiling, measured by the existing CPU gate) | ✗ FAILED | Campaign: GATE FAIL: p95 152.788 ms exceeds the 8 ms budget (A1) + extended GATE FAIL: p95 185.692 ms (n=53); L=32 probe worse (182.725 / 204.499). This verifier re-ran the gate: GATE FAIL: p95 107.493 ms exceeds the 8 ms budget — same honest band. Post-F1 ALT is inert on the current binary (0/24 clean toTable columns — the 6,285-node island), so the c2 rung bought no measured CPU improvement. |
| 2 | SC-2: Route optimality unaffected (ALT admissible — corpus re-run green with identical tolerance verdicts) | ✓ VERIFIED | Re-ran both gates this session: D-03 gate GATE PASS: 53/53 routed pairs equal within ±0.1%, verdict classes preserved (100/100 record pairs; 6 unreachable + 41 unsnappable preserved, 0 re-snapped), 0 violations, max |Δ| 0.005%, epsilon mirror intact; oracle sweep GATE PASS: 0/200 |Δ| violations (182 routed, 18 unreachable, worst |Δ| +0.000%) on fresh seed-0x08f1 pairs the fixed corpus structurally cannot cover. routing:test 82/82 (incl. A1 625-pair Dijkstra-equivalence, A11/A12/A13 pins). |
| 3 | SC-3: The budget record's c3 degradation class retires; KNOWN-LIMITATIONS updated | ✗ FAILED (as written — correctly not taken) | Retirement never fires on failing numbers (the pre-committed law). The update half IS done: KNOWN-LIMITATIONS carries the quoted post-ALT record, the ALT row reads "Built (Phase 8, 2026-10-25): optimality verified; the CPU verdict measured over budget — the degradation stands"; "next-milestone" purged from all four records (grep = 0). |
Score: 1/3 roadmap success criteria. (All five plans' machinery must-haves — ARG2 codec laws, landmark module, ALT containment, build-stage integration, gates + records — verified; see below.)
Score note: SC-3's failure is compliant behavior, not neglect — the criterion is arithmetically unreachable while SC-1 fails, and faking it would have violated the phase's own honest-engineering law. It is nonetheless reported as not-achieved because the class did not retire.
Plan-Level Machinery (must_haves from the 5 PLANs — all verified)
| Plan | Claimed machinery | Verified evidence |
|---|---|---|
| 08-01 | Pre-ALT baseline frozen BEFORE the codec; ARG1 guard; --extended D-04 flag; default mode byte-compatible | measure-optimality-baseline.mjs refuses non-ARG1 binaries (version check at L153–155); alt-baseline.json is coordinate-pinned (origin/destination lat-lng, never node indices) with the epsilon block {name: OPTIMALITY_EPSILON_PCT, pct: 0.1}; --extended imports generateCrossMetroPairs from the baseline module (ONE pair-set definition, two consumers); P95_BUDGET_MS = 8 grep = 1 |
| 08-02 | ARG2 codec, exact-size-before-allocation, ARG1→null, fixture regenerated through the ONE encode path, landmark.ts the single table authority | graph.ts: magic 0x41524732, version 2, landmarkCount/landmarkQuantumS/landmarkTo/landmarkFrom fields, buffer.byteLength !== lay.total → null at L228 (before view allocation); graph.test.mjs:139 consumes mini-graph-arg1.bin as the rejection vector; mini-graph.bin regenerated (1668→1884 B); landmark.ts exports farthestPointAnchors/landmarkTables/landmarkCoverage + LANDMARK_QUANTUM_S/MAX_QUANTA/I32_WEIGHT_CEILING (WR-04 fix present) |
| 08-03 | ALT inside the proven BH skeleton; clean-columns containment (F1); rollout locks | astar.ts: cleanColumnsFor (L233) + search-scoped activeL (L358–362), LANDMARK_SENTINEL_U16 named constant, haversine max-fallback; landmarkFrom appears ZERO times in astar.ts (the A11 law — stronger than required); rollout.test.mjs RO1/RO2 structural pins ran green in the suite; worker-router.ts and upload-road-graph.mjs contain no version/format branches (grep = 0) |
| 08-04 | Build preprocessing stage via the ONE landmark module; D-02 scaling rule; honest gates; --check | build-road-graph.mjs: imports the landmark module (never re-implements Dijkstra), NODES_PER_LANDMARK = 13000 → clamp(round(N/13000),16,32), LANDMARK_MIN_COVERAGE_FRACTION = 0.9 override-proof, --landmarks knob (cap 128); live --check on the real binary: nodeCount 311,361 / edgeCount 677,126 / landmarkCount 24 / quantum 0.100 / coverage min/mean 0.980/0.980 — the canonical L=24 build, upload-ready |
| 08-05 | D-03 gate with constant-mirror; honest campaign; records tell the post-ALT truth | Gate asserts record.epsilon.name === "OPTIMALITY_EPSILON_PCT" && pct === 0.1 BEFORE measuring (L258); reads the frozen record, never regenerates pairs; budget-gates drift guard ROUTE_CPU_DRIFT_GUARD_MS = 400 with the quoted post-ALT band; BUDGETS/KNOWN-LIMITATIONS/ROAD-GRAPH all quote the same gate lines (53 routed / 152.788 / 185.692 / 182.725 / 204.499) — mutually consistent, verified against the REVIEW.md cross-check |
Required Artifacts
| Artifact | Expected | Status | Details |
|---|---|---|---|
routing/src/graph.ts |
ARG2 single-authority codec | ✓ VERIFIED | Substantive + wired (decoded the real binary live via --check; consumed by bot tests 126/126) |
routing/src/landmark.ts |
ONE landmark compute core | ✓ VERIFIED | All three exports + WR-04 i32 ceiling guard; consumed by build script + fixture builder + tests |
routing/src/astar.ts |
ALT potentials, F1 containment | ✓ VERIFIED | cleanColumnsFor/activeL present; landmarkFrom absent; toTable-only (sound subset) |
routing/scripts/measure-optimality-baseline.mjs |
Baseline recorder + shared pair core | ✓ VERIFIED | ARG1-version guard; exports consumed by measure-route-cpu |
routing/test/fixtures/alt-baseline.json |
Frozen pre-ALT record | ✓ VERIFIED | 29.6 KB, coordinate-pinned, epsilon block; untouched (gate mirror proves per run) |
routing/test/fixtures/mini-graph-arg1.bin |
Preserved ARG1 rejection vector | ✓ VERIFIED | 1668 B, byte-preserved; consumed by graph.test.mjs:139 |
routing/test/fixtures/mini-graph.bin |
Regenerated ARG2 fixture | ✓ VERIFIED | 1884 B; suite-wide consumption green |
routing/scripts/measure-route-cpu.mjs |
CPU gate + --extended | ✓ VERIFIED | Budget constant untouched; extended mode shares the pair core |
routing/scripts/measure-optimality-gate.mjs |
D-03 gate | ✓ VERIFIED | Mirror assert; GATE PASS re-run this session |
routing/scripts/measure-astar-oracle-sweep.mjs |
200-pair fresh oracle sweep | ✓ VERIFIED | WR-01 symmetric |Δ| fix present (L244); GATE PASS re-run this session |
routing/scripts/build-road-graph.mjs |
Preprocessing stage + knobs | ✓ VERIFIED | Scaling rule, coverage gate, --landmarks, --check landmark facts |
routing/test/rollout.test.mjs |
D-01 rollout locks | ✓ VERIFIED | RO1/RO2 pins green in suite; targets verified format-unaware |
scripts/lib/budget-gates.mjs |
Re-anchored route-cpu law | ✓ VERIFIED | Drift guard 400; quoted c3 record; no next-milestone |
docs/BUDGETS.md / docs/KNOWN-LIMITATIONS.md / docs/ROAD-GRAPH.md |
Post-ALT honest records | ✓ VERIFIED | Quoted numbers mutually consistent; ALT row flipped; ARG2 layout section present |
routing/data/kl-roadgraph.v1.bin |
Canonical L=24 ARG2 binary (gitignored) | ✓ VERIFIED | On disk, 45.3 MB; decodes ARG2 with L=24/quantum 0.1/coverage 0.980 |
Key Link Verification
| From | To | Via | Status | Details |
|---|---|---|---|---|
| astar.ts potential() | ARG2 landmark tables | graph.landmarkTo reads via cleanColumnsFor/activeL |
WIRED | L233–242, L358–402 |
| measure-route-cpu --extended | measure-optimality-baseline | import { generateCrossMetroPairs } |
WIRED | L60, L110 — one pair set, two consumers |
| measure-optimality-gate | alt-baseline.json | reads frozen record + epsilon mirror | WIRED | RECORD_PATH L53; mirror assert L258 fires before measurement |
| build-road-graph preprocessing | landmark.ts | dynamic import of the ONE module | WIRED | L202; no second Dijkstra exists (grep across scripts = 0) |
| graph.test.mjs | mini-graph-arg1.bin | ARG1 decode-rejection vector | WIRED | L139 |
| rollout.test.mjs | upload script + worker-router | structural grep pins | WIRED | RO1 pins the R2 key; RO2 pins no version branch — both targets verified clean |
| mini-graph.bin / bot test builders | ARG2 encode path | same encodeGraph authority | WIRED | bot 126/126 green after fixture regen |
Data-Flow Trace (Level 4)
Not applicable to dynamic-UI artifacts (this phase ships no UI). The data-flow analog — real graph bytes → decode → search → gates — was exercised end-to-end this session: the 45.3 MB binary decodes (311,361 nodes / 677,126 edges / L=24), routes (23/25 routed in the CPU sample), and feeds both optimality gates with real measured seconds (D-03: 53 pairs; oracle: 182 routed pairs). No static/hollow data paths found.
Behavioral Spot-Checks (all run by this verifier, this host, 2026-10-25)
| Behavior | Command | Result | Status |
|---|---|---|---|
| Routing suite (A1–A13, G1–G11, L, S, RO suites) | npm run routing:test |
82 passed, 0 failed | ✓ PASS |
| Bot suite (ARG2 fixture consumers) | npm test -w bot |
126 passed, 0 failed | ✓ PASS |
| D-03 optimality gate (SC-2) | node routing/scripts/measure-optimality-gate.mjs |
GATE PASS, exit 0 — 0 violations, max |Δ| 0.005% |
✓ PASS |
| 200-pair fresh oracle sweep (SC-2 pin) | node routing/scripts/measure-astar-oracle-sweep.mjs |
GATE PASS: 0/200 |Δ| violations (182 routed, worst +0.000%) |
✓ PASS |
| CPU gate (SC-1) | node routing/scripts/measure-route-cpu.mjs |
GATE FAIL: p95 107.493 ms exceeds the 8 ms budget |
✗ FAIL (honest — the SC-1 gap) |
| Binary identity + landmark facts | node routing/scripts/build-road-graph.mjs --check routing/data/kl-roadgraph.v1.bin |
ARG2; L=24; quantum 0.100; coverage 0.980; sentinels 150,986 to / 1,365,034 from | ✓ PASS |
| Budget-audit vectors | node scripts/test/budget-audit.test.mjs |
19/19 vectors ok |
✓ PASS |
(Overpass build NOT re-run per instructions; the on-disk binary is the canonical L=24 build.)
Requirements Coverage
| Requirement | Source Plan | Description | Status | Evidence |
|---|---|---|---|---|
| SC3 (carry-over) | 08-01..05 frontmatter | Phase-5 criterion: fixture backend ladder + designed router-pending state | ✓ SATISFIED (no regression) | routing 82/82, bot 126/126; rollout pins hold; router-pending law intact |
| SC4 (carry-over) | 08-01..05 frontmatter | Phase-5 routing-class carry-over | ✓ SATISFIED (no regression) | Same suite evidence |
| Phase-8 requirement ("the budget record's numbers improve") | ROADMAP §Phase 8 | No new REQ ids; the c3 numbers improve | ✗ BLOCKED | The measured numbers did NOT improve (p95 107–186 ms vs the pre-ALT ~38 ms campaign band); the record honestly documents the non-improvement. Covered by the SC-1 gap above. |
| Orphaned requirements | — | none | — | REQUIREMENTS.md maps no additional ids to Phase 8 (grep: SC3/SC4 appear only as ROADMAP-level carry-overs) |
Anti-Patterns Found
| File | Line | Pattern | Severity | Impact |
|---|---|---|---|---|
| — | — | No TODO/FIXME/placeholder/stub patterns in any phase file (grep clean across all 7 scripts + 3 src modules) | — | — |
| routing/src/astar.ts | 315–316, 515, 598 | return null / return [] |
ℹ️ Info | Fail-honest designed degradation (input validation, unreachable miss, empty path) — not stubs |
| measure-*.mjs | various | = [] accumulators |
ℹ️ Info | Local accumulator init, not hardcoded empty data |
Open code-review findings carried for the record (documented in 08-REVIEW.md, not re-litigated here): WR-03 (baseline recorder lacks oversampling — the frozen evidence base is 53 measured pairs, not ~100; maintainer-deferred, record immutable) and IN-01..IN-07 (doc-statement drift, defensive gaps in future-record paths). WR-01/02/04 verified applied: symmetric |Δ| compare at oracle L244, CPU3 honest-SKIP law, LANDMARK_I32_WEIGHT_CEILING guard at landmark.ts L131 — each with its fix commit (11e55c1, 95399ae, e77bbe9) present in history.
Human Verification Required
- The c3 escalation decision (the gap itself — belongs to the USER). Test: Choose the track: (1) direction-split potentials with a re-proven bidirectional meet rule (needs its own phase — skeleton work Phase 8's laws forbade), (2) Contraction Hierarchies (Phase-6 deferral), (3) Workers Paid reversal (needs explicit sign-off against the $0 law), (4) keep c3 as the designed degradation (current shipped posture; zero code). Expected: A recorded decision against docs/BUDGETS.md §c3 that unblocks either Phase 9 (option 4) or a new planned phase (options 1–2). Why human: Strategic trade-off across cost law, scope, and schedule — not decidable from code.
- R2 migration state (D-01's one-time upload).
Test:
node routing/scripts/upload-road-graph.mjs+--checkroundtrip against R2 (maintainer-time, account-gated). Expected: The R2 objectkl-roadgraph.v1.binholds the ARG2 build (v2, L=24, coverage 0.980); production/api/routeserves real routes. Until then, any deploy of the current Worker code is router-pending on every route (ARG1 bytes decode to null by design). Why human: R2 contents and deploy timing are outside the repo; the upload is deliberately manual.
Gaps Summary
One root cause, two failed criteria. The CPU win — the phase's core deliverable — did not land (SC-1), and therefore the c3 retirement correctly did not fire (SC-3). What DID land, verified end-to-end this session: the ARG2 layout (single decode path, fail-honest, exact-size law), the landmark machinery (module, build-stage integration, D-02 scaling rule, honest coverage/quantum gates, the canonical L=24 binary), optimality hardening beyond the plan's bar (D-03 gate + 200-pair fresh oracle sweep, both green — after the phase's own gates caught two real suboptimality bugs), and four records rewritten to the quoted post-ALT truth with zero retirement theater.
The remaining work is not a bug fix: the debug session proved a perfectly implemented two-sided ALT cannot beat haversine in this bidirectional configuration on a graph with sentinel fringes (0/24 clean columns), and the sound fast path (direction-split potentials) requires re-proving the BH meet rule — work this phase's untouchable lines forbade. This is the escalation decision recorded in docs/BUDGETS.md §c3 and 08-05-SUMMARY, and it belongs to the maintainer, not to a closure plan. No later milestone phase covers it: Phase 9 builds on the current posture, Phase 10 is the battery record, and Phase 11 (Engine B) moves routing client-side without promising the Worker path in-budget — so nothing here is deferrable.
Verified: 2026-10-25T14:43:22Z Verifier: OpenCode (gsd-verifier)
Decision addendum (2026-10-25, maintainer)
The SC-1 escalation decision was made: Contraction Hierarchies, as Phase 08.1 (inserted, "Routing Backend v3") — the only lever the measured evidence supports reaching the 8 ms budget. Direction-split potentials are NOT closed: the measured prizes (0.59× expansions unidirectional control; −41% transposed table) and the full proof-obligation surface are handed off in docs/ALT-DIRECTION-SPLIT.md as a standalone experiment (explicitly open to being worked with a different LLM/harness). SC-1 and SC-3 transfer to Phase 08.1; this phase's debt is the honest record above plus that handoff. SC-2's hardening stands as the phase's optimality proof.