Memory algorithm performance audit

Updated: 2026-10-03. Current baseline: default branch master at 5c98ff9c. Current optimized implementation: 9393edbe, after merging that baseline in 6d1511ac. Work remains isolated in codex/memory-algorithm-performance.

中文报告

#Revalidation against the latest master

The default branch is named master. It now includes PR #148: covering edge indexes, scoped supersedes reads, a caller-loaded active-insight snapshot, per-recall ranked-transition caching, embedding keep-alive, mmap and database compaction. Those changes are retained. They are part of the new baseline, not attributed to this PR's incremental gains. The historical audit below preserves the earlier measurements separately.

The merge preserves upstream's correctness rule: rank each complete neighborhood by intent-weighted structure plus cosine similarity before applying the visit budget. Transition ties still use insight ID and edge type. The request-local cache now retains those ranked transitions and reuses precomputed scalar cosine scores instead of recalculating cosine for each edge. Query and intent are fixed for the lifetime of that cache.

An additional change reuses the vector decode buffer within a synchronous embedding scan. DeserializeVector and DeserializeVectorInto share one float32 decoder; callers that need an owned vector still get one. Recall consumes each vector's score before the next row overwrites the buffer. The stored format, arithmetic order, invalid-blob behavior and query lifetime are unchanged.

Against current master, both versions already make at most U successful neighborhood reads for U distinct expanded nodes. Let E_U be the total incident edges loaded, C the reranked candidates, and d the vector dimension. The cosine component changes from O((N + E_U + C)d) to O(Nd + E_U + C). Both versions retain O(sum(deg(v) log deg(v))) neighborhood sorting before traversal, as required by the upstream budget rule. Dense neighborhoods therefore remain expensive; a visit budget does not bound the size of the adjacency lists read.

For fixed dimension d, buffer reuse reduces cumulative temporary decoded-vector allocation from O(Nd) to O(d) per recall. With mixed dimensions it allocates only when a larger capacity is needed. This is an allocation improvement; exact vector comparison remains O(Nd), scalar caches remain O(N), and the reported B/op values are cumulative allocation, not peak resident memory. The ordered-read indexes, local BFS, semantic top-K and transaction statement reuse retain the bounds described in the historical audit.

#Fresh measurements

The fixture and methodology below are unchanged: N=1/10/100/1,000/10,000, 128-dimensional vectors, real temporary SQLite WAL stores, Apple M4, Go 1.25.4, one P, five alternating rounds at 100 ms per case. The final dataset contains 108 cases × 5 rounds × 2 versions = 1,080 samples. It compares 5c98ff9c directly with 9393edbe; intermediate merge-only results are excluded. No other local test suite ran concurrently with these measurements.

CPU µs/op, current master → final PR, median of five runs:

At N=10,000, CPU ms/op (lower is better; ratio is master/final):

Dense graph, CPU ms/op and cumulative allocation KiB/op:

At N=10,000, hybrid recall allocation fell from 78.85 MB to 49.10 MB per operation (37.7% less). Dense recall at N=100 improves 1.09× over current master. The earlier 6.51× figure used a baseline without master's transition cache and covering indexes and does not describe this delta.

Small inputs retain fixed-cost tradeoffs: N=10 neighborhood reads take 59.34 µs versus 50.09 µs; N=1 semantic embedding/token paths take 13.36/13.79 µs versus 11.57/11.75 µs. Known-entity scanning at N=10,000 takes 6.974 ms versus 6.709 ms (about 4% more); retention is near neutral (170.104 → 171.657 ms). Unmodified embedding loading also varies (10.409 → 9.284 ms), so small timing ratios should not be interpreted as algorithm changes. ID lookup is near neutral. The Entity benchmark's large gain is fixture-specific: every record has the entity, so the indexed read can stop after ten matches. An absent JSON entity or substring still requires a linear scan. These shared-host timings are observations, not cold-start or production latency guarantees.

The isolated decode-buffer probe compared the merge commit 6d1511ac with 9393edbe: three alternating rounds, N=10,000, hybrid/WHY recall, 200 ms per case. Hybrid allocation fell from approximately 59.35 MB to 49.11 MB per call, about 17%, matching the eliminated 9,999 temporary 128-element float64 buffers. This probe is separate from the full master-versus-final dataset.

All final samples are saved as current master and final PR. The isolated allocation probe is saved as decode before and decode after.

#Compatibility and validation after the merge

• go build -o mnemon ., make test, and go test -race ./internal/memory/... ./cmd/memory -count=1 passed on the final production implementation.
• MNEMON_EMBED_ENDPOINT=http://127.0.0.1:1 bash scripts/e2e_test.sh: all 258 assertions passed after the buffer change.
• npm test --prefix npm/cli: 13 passed. The imported OpenCode runtime suite and ZCode shell hooks passed locally. The Windows PowerShell hook probe was skipped on this macOS host; it belongs to the manual Windows integration suite.
• The independent full-vector traversal oracle is now copied from 5c98ff9c. Cached scores and via labels match for all four intents, three traversal budgets, repeated/overlapping anchors, ties, cycles, deleted nodes, real/zero/ negative query vectors and mismatched dimensions. Upstream's four best-transition budget regressions remain covered.
• A shuffled caller-supplied snapshot returns the same time anchors without reordering the caller's slice. Decode tests exercise growth, shrinkage, invalid bytes, signed zero, subnormals, infinities and NaNs.
• Existing index-plan/migration, bounded-BFS parity, transaction rollback/panic and supersedes/compaction tests pass. Equal-score anchor/result order still has the pre-existing nondeterminism; no byte-for-byte ordering claim is added.

To reproduce this comparison, use the commands in the historical reproduction section with 5c98ff9c as the baseline and 9393edbe as the optimized revision. Copy the unchanged performance*_test.go files from a21d783b into the baseline archive, compile separate binaries and alternate their execution. Paid live providers, cold filesystem-cache timing and the Agency/Docker integration umbrella remain outside these measurements.

#Historical audit: 4d312c4e → 766c3965

The rest of this document records the original experiment before the master sync. Its timings and gains apply only to those historical revisions. In particular, the original 6.51× dense-recall gain is not the incremental gain over current master; use the fresh comparison above for that decision.

This audit covers the native Memory read/write pipeline: SQLite retrieval, keyword and vector scoring, multi-signal recall, semantic candidates, bounded graph traversal, graph writes and retention. Agency authorization, replay and daemon protocols are outside this change. There is no claim of a universally optimal implementation: input size, graph density, selectivity and durability requirements impose different costs.

#What changed

1. Replace three single-column insight indexes with indexes matching active timestamp, source/timestamp and importance/timestamp reads. Remove the old indexes so writes do not maintain both sets. Query-plan tests verify that these ordered reads no longer need a temporary sort. Existing stores upgrade on writable open; read-only stores continue to work without migration.
2. Load bounded BFS neighborhoods through endpoint indexes, keeping edge insertion order, self-loop deduplication, deleted-node filtering, depth and result limits. Unlimited traversal retains bulk loading. Typed neighborhood reads use two indexed branches: a factored OR can otherwise make SQLite scan every edge of the requested type.
3. Keep per-query keyword and cosine scores instead of retaining every token set and embedding vector. Stream embedding blobs, compute cosine once per vector and reuse it across anchor selection, beam traversal and reranking. Reuse already-loaded active insights and cache successful adjacency reads, including empty neighborhoods, across anchors. Caches die with the query.
4. Keep only the best K semantic or embedding-only diff candidates with a typed heap. Reuse tokenization of the query in semantic token fallback, and merge content/tag/entity tokens directly without allocating separate field maps.
5. Reuse SQL's time ordering when it also matches absolute timestamp ordering; imported timestamps with different UTC offsets still get the original sort.
6. Skip known-entity extraction scans in explicitly provided entity mode. Prepare insight/edge inserts once per transaction and reuse the statements. The transaction closes them on commit/rollback; panic cleanup also rolls back before clearing the transaction-local pointers.

The scoring formulas, weights, similarity thresholds, RRF constant, anchor limits, per-anchor visited sets, beam budgets, supersession demotion, exact duplicate identity checks, causal ordering and embedding failure fallback are unchanged. Equal-score/equal-time candidates still have no guaranteed relative order; the old code already combined unordered maps and non-stable sorts. The optimization does not add approximate nearest-neighbor search or discard low-ranked candidates before a stage that needs them for score normalization.

#Complexity audit

Let N be active insights, E graph edges, L average text/tag/entity size, d embedding dimensions, Q query tokens and K requested results. M is the number of matching rows examined by a filtered SQL read. Hash-map lookups below use expected constant time. Key/payload sizes matter in addition to the row count.

For beam search, let A <= 60 be anchors, P node expansions across all anchors, U <= P distinct expanded nodes, X processed transitions and E_U the sum of incident edges loaded for those distinct nodes. The original path issued up to P adjacency queries, reloaded candidate insights and computed cosine during each transition and final reranking. The new path issues at most U successful adjacency queries, uses the active insight snapshot already loaded at recall start and computes each cosine once. The cosine component changes from O((N + X + C)d) to O(Nd + X + C). Heap traversal itself is unchanged. P is bounded by the existing depth, beam width and per-anchor visit budgets; dense adjacency lists still cost time to read. Cached adjacency consumes O(E_U) space, in addition to the active insight snapshot and O(N) scalar caches.

For a bounded BFS, let V_b be expanded nodes, R_b distinct encountered neighbors and deg(v) their incident degrees. Full-store loading is replaced by approximately O(V_b log E + sum(deg(v) log deg(v)) + R_b log N) indexed work, plus payloads. The degree sort preserves the old insertion order. Work depends on the neighborhood, including missing/deleted endpoints, rather than unrelated history. A high-degree node can still be expensive. Unlimited BFS retains its bulk O(NL + E) loading and traversal path.

#Measurement method

The committed benchmarks use real temporary SQLite WAL databases and synthetic local vectors. N is corpus size, not Go's adaptive benchmark iteration count. Sizes are 1, 10, 100, 1,000 and 10,000. There are 128 vector dimensions, fixed-width record IDs/text, two tags, two entities and ten sources. The regular graph is a causal chain with N-1 edges. A separate dense fixture at N=1/10/100 adds N(N-1) semantic edges.

Read limits are 10, semantic candidate limits remain 3/5 and bounded BFS uses two hops / 20 results. Entity-hit records all contain SQLite; EntityMiss and RankedKeywordMiss deliberately scan for absent terms. Pure scoring benchmarks start with inputs already in memory; recall/BFS include their database reads. Fixtures use historical timestamps, so EngineProvided measures backbone, entity and semantic work without current-window proximity edges. It replaces existing edges inside a transaction, keeping the graph size bounded.

Insert measures N new insights into an empty store in one committed transaction; fixture construction and cleanup are excluded. Retention includes its existing effective-importance writes. None of these timings include CLI startup, provider/network latency, embedding generation or a cold filesystem cache.

Host: Apple M4, Darwin/arm64, Go 1.25.4, -cpu=1. The same benchmark sources were compiled against each production revision. Five independent runs per revision used -benchtime=100ms, alternating before/after order between rounds. Tables show medians. cpu-ns/op is process user+system CPU, including GC, measured with getrusage; it excludes descheduling and blocked I/O. Ordinary ns/op remains wall time. The insert benchmark excludes cleanup from both metrics. Other OSes still run the benchmarks with wall-time/allocation reporting.

The machine was shared, not an isolated performance lab. CPU measurements, unchanged control paths, allocation counts, query plans and operation counts are used together; timing ratios are local observations, not latency promises. B/op is cumulative Go allocation per operation, not peak RSS or database file size. Three timing points alone cannot establish a Big-O bound.

#N=1, 10, 100

CPU µs/op, before → after. Each cell is a median of five runs.

#Larger corpus and allocation results

CPU ms/op, before → after; allocation is KiB/op at N=10,000. Speedup is before CPU / after CPU, not a throughput SLA.

#Dense graph and unchanged controls

At N=10,000, unchanged ID lookup and embedding loading are approximately 1.05× and 1.00×, and retention remains approximately 1.00×. These controls help distinguish the larger algorithmic gains from timing noise. Negative LIKE lookup remains linear and used about 4% more CPU in this run. At N=10, bounded BFS uses 57.7 µs versus 49.4 µs for the bulk baseline: extra indexed calls cost more on tiny graphs. Single-record semantic lookup also has roughly 1.6 µs of extra fixed overhead. These regressions are included, not removed from the data.

The larger indexes initially increased batch-write CPU cost. Transaction-local statement reuse brought the final 10,000-row batch from 551.0 ms to 458.4 ms (about 17% less CPU) with the same commit boundary. Hybrid recall reduced per-operation allocation from about 75.7 MiB to 56.7 MiB; dense recall at N=100 dropped from about 65.3 MiB to 9.8 MiB. Bounded neighborhood allocation at N=10,000 is 9,504 bytes rather than 23,987,320 bytes.

The selector's deterministic comparison-count test forces an eviction for every new item once K=5 is full. Counts at N=1/10/100/1,000/10,000 are 0 / 37 / 440 / 4,491 / 44,991, including final sorting of K items. This supports the code-derived O(N log K) bound without a flaky wall-clock CI assertion.

The complete five-run output for every path, including controls and misses, is saved as before and after. No exploratory or superseded implementation measurements are mixed into these files.

#Correctness and verification

• go build -o mnemon . — passed.
• make test — passed, including vet, deterministic tests and architecture checks. The pure Memory-local top-K leaf is included in the dependency graph and regular deterministic test list.
• go test -race ./internal/memory/... ./cmd/memory -count=1 — passed.
• MNEMON_EMBED_ENDPOINT=http://127.0.0.1:1 bash scripts/e2e_test.sh — all 258 assertions passed, with embedding providers unavailable by design.
• Cached traversal is checked against the previous independent implementation for all four intents, multiple budgets, multiple anchors, cyclic graphs, deleted nodes and mismatched vector dimensions. Scores and via labels agree.
• Indexed bounded BFS is compared with bulk traversal, including order, hop, edge identity, limits, filters, self-loops and missing/deleted endpoints.
• Tests cover top-K/full-sort parity, comparison bounds, token-field boundaries, request refresh after vector/edge/deletion changes, mixed timestamp offsets, index upgrades/reopens, endpoint query plans, transaction commit/rollback, statement reuse, edge replacement and panic cleanup.

The Agency/Docker/provider integration umbrella and paid live suite were not run; these changes do not modify those boundaries. The Memory CLI boundary was exercised directly. The changes do not add goroutines or change transaction commit policy, supersession authority or exact-duplicate write suppression.

#Reproduce

On the PR revision:

go test ./internal/memory -run '^
#39; -bench BenchmarkMemory \
  -benchmem -benchtime=100ms -count=5 -cpu=1
go test ./internal/memory/internal/topk -run TestComparisonBudget -v
go test ./internal/memory/store -run 'Test(ActiveReadPlans|TraversalReadPlans)' -v

For a matched baseline, extract 4d312c4e into a temporary directory and copy only internal/memory/performance*test.go from this PR into its internal/memory/ directory. Compile both with go test -c -o <separate-output-binary> ./internal/memory, then run the binaries with -test.run='^

#Remaining limits

Exact keyword/vector matching, JSON entity misses and retention still have whole-corpus work. Persistent token/entity indexes would need their own migration, update/delete/rollback and tokenization parity contracts. An ANN index would additionally need a recall-quality budget, which this task did not permit sacrificing. Larger composite keys trade some insertion work/storage for ordered reads; transaction-local statement reuse offsets compilation work, but does not make durable writes constant-time. Large or unbounded graph walks still depend on actual graph density. These costs are kept explicit rather than hidden behind a cache that can become stale between commands.