Published by Sean Carr
Eliminating Quadratic Bottlenecks in Multi-Session Thread Reconstruction
Replacing catastrophic regex backtracking and unindexed nested loops dropped thread table construction from 19 seconds to 1.5 seconds on 1,293 session histories.
At a Glance
Thread Table Build Time
19.0 s -> 1.5 s
Table reconstruction across 1,293 threads dropped from 19.0s to 1.5s (12.6x speedup) with byte-identical output.
Incremental Store Rebuild
0.15 s
Session memoization in the background daemon reduced post-ingestion table rebuilds to 0.15 seconds.
Warm Pointer Latency
8.5 s -> 0.62 s
Warm pointer lookups accelerated 13.7x from 8.5s (max 9.1s) to 0.62s (max 0.88s).
Cold Pointer Latency
~10.0 s -> 2.47 s
Cold pointer lookups dropped from ~10.0s to 2.47s (max 3.02s), well within the <=3.0 second budget.
| Telemetry Metric | Measured Value | Context & Observability |
|---|---|---|
| Thread Table Build Time | 19.0 s -> 1.5 s | Table reconstruction across 1,293 threads dropped from 19.0s to 1.5s (12.6x speedup) with byte-identical output. |
| Incremental Store Rebuild | 0.15 s | Session memoization in the background daemon reduced post-ingestion table rebuilds to 0.15 seconds. |
| Warm Pointer Latency | 8.5 s -> 0.62 s | Warm pointer lookups accelerated 13.7x from 8.5s (max 9.1s) to 0.62s (max 0.88s). |
| Cold Pointer Latency | ~10.0 s -> 2.47 s | Cold pointer lookups dropped from ~10.0s to 2.47s (max 3.02s), well within the <=3.0 second budget. |
| Full Memory Query (ask2) | 29.0 s -> 12.7 s | Full warm ask2 query latency dropped from 29.0s to 12.7s (max 17.3s). |
Published by Sean Carr
View & print executive brief version →Executive Summary & Core Finding
As an engineering memory store expanded to 1,293 indexed session threads, pointer resolution latency degraded severely due to regex backtracking and quadratic scanning loops during thread table construction. By replacing unmerged regex passes with linear segment parsers, adding service-level open-items memoization, and caching thread vectors on write, we reduced table construction from 19.0 seconds to 1.5 seconds with byte-identical output, accelerating warm pointer lookups from 8.5 seconds to 0.62 seconds.
Method
We profiled the latency regression on a live production memory database containing 1,293 session threads across cold and warm cache states.
To determine whether a specific commit introduced the regression, we performed a git bisect across five clean historical archive points (commits 65c4f22, 2beaf6d, 7a8f572, b8598cd, and 26da2c3), evaluating warm pointer lookup latency against a frozen database snapshot.
The bisect revealed that latency was uniform (~2.05 to 2.11 seconds) on smaller historical snapshots, isolating the regression to organic data growth interacting with quadratic algorithms, compounded by the removal of a daily call cap that exposed uncached planner calls.
We implemented four targeted optimizations: linear segment scanning, open items memoization in the daemon, write-time vector persistence, and deterministic pointer rule planning.
We validated output equivalence on the 1,293-thread snapshot and executed the full unit test suite across both Windows and WSL environments.
What We Measured
Replacing quadratic loops and regex backtracking cut thread table build time from 19.0 seconds to 1.5 seconds (12.6x speedup) with byte-identical output, reducing warm pointer lookups from 8.5 seconds to 0.62 seconds.
Thread Table Build Time
19.0 s -> 1.5 s
Table reconstruction across 1,293 threads dropped from 19.0s to 1.5s (12.6x speedup) with byte-identical output.
Incremental Store Rebuild
0.15 s
Session memoization in the background daemon reduced post-ingestion table rebuilds to 0.15 seconds.
Warm Pointer Latency
8.5 s -> 0.62 s
Warm pointer lookups accelerated 13.7x from 8.5s (max 9.1s) to 0.62s (max 0.88s).
Cold Pointer Latency
~10.0 s -> 2.47 s
Cold pointer lookups dropped from ~10.0s to 2.47s (max 3.02s), well within the <=3.0 second budget.
Full Memory Query (ask2)
29.0 s -> 12.7 s
Full warm ask2 query latency dropped from 29.0s to 12.7s (max 17.3s).
Experimental Notes & Observability Details
- Pre-fix bottleneck: 16.0s regular expression backtracking on unmerged lines, 2.0s quadratic nested loops scanning open items.
- Eliminated runtime re-embedding of ~220 uncached thread vectors on every query by persisting embeddings at write-time ingestion.
- Freshness scan timeout bounded to at most 0.5s for fast terminal response.
- Test coverage: 557 passing tests on Windows, 537 passing tests on WSL.
What We Think It Suggests
- Memory retrieval systems that perform well on small test fixtures can degrade severely as session histories accumulate. Unindexed text parsing and eager regular expression evaluations create insidious quadratic scaling bottlenecks that only surface on production-sized stores.
- Preserving byte-identical output during algorithmic refactors is achievable by replacing backtracking regexes with linear state scanners that operate on token boundaries.
- Decoupling fast pointer resolution from full generative synthesis allows agents to check session references in sub-second time without incurring model invocation costs.
Limits
- Generative Answer Latency: While pointer resolution achieved sub-second latency (0.62s), full conversational answers remain constrained at ~12.7 seconds warm p50 due to two serial LLM calls (planner ~4.6s, synthesis ~7.3s).
- Daemon Memory Growth: In-memory session memoization increases resident process memory in the background daemon, necessitating periodic pruning of inactive sessions.
- Scaling Horizon: While linear scanning reduced build times to 1.5 seconds on 1,293 threads, scaling to tens of thousands of threads will eventually require relational database indexing rather than in-memory table construction.
Reproduce It (Data & Benchmarks)
- Regression profiling and verification test: tests/test_perf1.py (14 tests)
- Implementation commit: selfmem 75a039c (modifications to threads.py, prefetch.py, and cli.py)
- Full test suites: 557 passed on Windows, 537 passed on WSL
Data and prompt templates only; no proprietary code is published.
Detailed Analysis & Field Observations
In persistent agent memory systems, reconstructing multi-session conversation threads is critical for resolving project continuity, open tasks, and historical decisions. Over weeks of active development, our indexed store grew to 1,293 session threads.
Under this data volume, thread reconstruction time silently ballooned to 19.0 seconds, causing fast pointer lookups (--pointers) to exceed their 10.0-second timeout and return empty results.
Profiling revealed two primary computational bottlenecks: regular expression backtracking on unmerged session lines accounted for 16.0 seconds, while quadratic nested loops scanning open items consumed approximately 2.0 seconds.
We eliminated these bottlenecks by replacing the backtracking regular expressions with linear segment parsers, memoizing session open items in the service daemon, and persisting thread vector embeddings at ingestion time. These refactors cut thread table build time from 19.0 seconds to 1.5 seconds (a 12.6x speedup) with verified byte-identical output, reducing warm pointer resolution latency from 8.5 seconds to 0.62 seconds.