Routing-scale profile and bottleneck report

Profiles the deterministic routing path across catalog sizes up to 10k tools (issue #684) and the persistent graph + fitted-index caches (issues #543 / #624 / #685).

Measured on: Linux-6.18.5-x86_64-with-glibc2.39 · Python 3.11.15 · 4 logical cores. Absolute latency is host-dependent; the build_ms column and the cold speedup are the portable signal.

catalog	build ms	cold start ms	warm start ms	warm route p50 ms	cold speedup	graph bytes	index bytes
100	2.4	4.9	2.8	0.913	1.7×	41290	16304
1000	455.3	504.2	53.8	40.538	9.4×	648113	162278
5000	8058.6	9213.9	1185.4	1369.441	7.8×	30138737	825710
10000	30140.1	35620.4	5517.5	6025.966	6.5×	214696952	1628273

Bottleneck

Graph construction (TreeBuilder.build) dominates cold start and grows super-linearly with catalog size — see the build_ms column. The one-time retriever fit is comparatively cheap. Per-query routing latency (warm route p50) also grows super-linearly and is itself significant at 10k, but that is a separate cost from cold start. The cost this work targets is the repeated cold start (graph build + index fit) paid by deployments that re-create routers over the same catalog: a process per request, a worker pool, a CLI in a loop.

Optimization

Persisting both derived artifacts removes that repeated work: the graph via save_graph / load_graph and the fitted index via RoutingIndexCache + CachedRetriever. A warm start loads both from disk and skips the build and the fit entirely (cold speedup column). Warm loads are byte-identical to a cold fit, so routing quality and determinism are unchanged (tests/test_routing_quality_guardrails.py).

Caveats

• The cache shortcuts cold start, not per-query latency: the warm route p50 column is unaffected by it. TreeBuilder.build's super-linear build cost and the super-linear per-query routing cost are separate, pre-existing scaling characteristics — this work mitigates the repeated build+fit via persistence rather than changing the (determinism- and quality-sensitive) build or beam-search algorithms. Reducing those first-pass costs is tracked separately.