Relation write path: O(R) full-manifest rewrite per mutation + unbounded list_relations

[ivklgn]

Summary

The relation read path is well-optimized and documented (.archcore/mcp/read-path-scan-performance.idea.md: cached manifest store, per-call relation index, get_document down to O(stat)). The write path is not. Every relation mutation rewrites the entire .sync-state.json, and list_relations has no cap. Full analysis and reproduction: .archcore/mcp/relation-write-path-graph-growth.idea.md.

Measured on a real corpus (litres/monorepo .archcore/): 153 docs, 513 directed relations (506 undirected edges), 81 KB manifest, snapshot 2026-07-09.

Findings

1. O(R) per mutation + full-file rewrite → quadratic bulk-build

manifestStore.mutate (internal/mcp/tools/manifest_store.go) deep-clones the whole manifest, and SaveManifest (internal/sync/manifest.go) re-serialises and rewrites the entire file on every add_relation / remove_relation. AddRelation additionally does a linear O(R) scan to dedup.

Building m relations into a manifest of current size R₀ costs Σ O(R₀ + i) = O(m·R₀ + m²) — quadratic write amplification. Relations are created in bulk (see finding 3 — cliques), so the quadratic case is the common case, not a corner case.

Projected file-rewrite cost per single add_relation (extrapolated from the measured 162 bytes/relation; maxManifestRelations = 50000 is the design ceiling):

R	manifest size	one add_relation rewrites
513 (measured)	81 KB	81 KB
5,000	~790 KB	~790 KB
50,000 (cap)	~7.9 MB	~7.9 MB for a single edge

Each add_relation also does 2× ReadDocumentContent (endpoint existence) + loadGlobalsFailClosed per call.

2. list_relations is unbounded

The token wall list_documents already closed (default cap 100 / max 500 + truncated) is still open for list_relations: with no path it serialises the whole graph into agent context. Asymmetric with the read-path work already shipped.

3. ~59% of edges are redundant with the filesystem; growth is Σ(cluster²), not N²

Relations form near-complete cliques inside leaf directories:

leaf dir	docs	edges / max	fill
code-quality/tests/e2e	7	21/21	100% (K₇)
translations	5	10/10	100% (K₅)
code-quality/tests/units	14	81/91	89%
auth/iframe	6	12/15	80%
auth/popup	19	99/171	58%

Decisive number: if every leaf directory were a full clique the graph would have 497 undirected edges — it actually has 506. To within 2%, the graph is "each leaf folder is a clique" plus a handful of cross-folder edges.

Growth law: R ≈ ½·Σ kᵢ² over leaf-directory sizes kᵢ, i.e. controlled by max leaf-dir size, not total doc count N:

• many small bounded folders → Σkᵢ² ∝ N → linear (healthy; here Σk²/N = 7.5)
• one folder that keeps accreting → its k² term dominates → quadratic locally (auth/popup at 19 docs already carries up to 171 edges; at 40 docs ≈ 780)

No guardrail exists (no per-node degree cap, no "relate to cluster" primitive). And 59% of edges are intra-directory related — they restate directory co-location the filesystem already encodes; only 41% (cross-directory or typed) carry signal beyond the tree.

Proposed work (priority order)

• Cap + paginate list_relations — mirror the list_documents envelope ({relations, total, offset, returned, truncated}). Cheap; closes the token wall symmetrically.
• O(1) dedup in AddRelation via a key set instead of the O(R) scan (internal/sync/manifest.go). Removes one quadratic factor of bulk builds.
• Batch add_relations (plural): one clone + one SaveManifest per batch. Kills write amplification for clique-building — how cliques are actually created.
• (needs-design) Derive same-folder adjacency from the tree instead of storing it; reserve explicit relations for cross-cluster typed edges. Drops ~60% of edges and bends the growth law back to linear. Touches the reading model, not just storage.
• (needs-design) Soft advisory (doctor / tool response) when a leaf-dir clique or a node's degree crosses a threshold, before one folder pulls the graph quadratic.

The write-amplification rows above are modeled (linear extrapolation of the measured 162 bytes/relation), not benchmarked — a SaveManifest/add_relation write bench in the style of internal/mcp/tools/*_bench_test.go would turn them into measurements.