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 p50column 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.