buildGraphClusters breaks out of the seed loop on an already-visited seed, collapsing insights into a few mega-clusters

[wstczyw]

Summary

buildGraphClusters exits its seed loop with break when a seed has already been
visited, instead of continue. Because the inner BFS marks a seed's entire
two-hop neighbourhood as visited, on any dense connected concept graph the second
seed is almost certainly inside the first cluster's neighbourhood — so the whole
loop terminates after a handful of seeds. The result is a few enormous clusters
instead of maxClusters distinct ones, and the insights generated from them are
near-duplicates of one another.

A second, independent issue in the same function: conceptNodes.find() is called
inside the BFS inner loop even though the conceptNodeIds Set is already built,
making cluster construction O(n²).

Environment

• @agentmemory/agentmemory 0.9.28
• iii engine 0.11.2
• Windows, engine launched as a Session 0 scheduled task
• Real graph at reproduction time: 10,518 nodes (5,128 of type concept), 21,770 edges

The code

registerReflectFunctions → buildGraphClusters:

for (const seed of sorted) {
  if (visited.has(seed.id) || clusters.length >= maxClusters) break;   // <-- should be continue for the visited case
  const cluster = []; const queue = [seed.id]; const seen = new Set(); let depth = 0;
  while (queue.length > 0 && depth <= 2) {
    const levelCount = queue.length;
    for (let i = 0; i < levelCount; i++) {
      const current = queue.shift();
      if (seen.has(current)) continue;
      seen.add(current);
      if (conceptNodeIds.has(current)) {
        const node = conceptNodes.find((n) => n.id === current);       // <-- O(n) inside BFS
        if (node) cluster.push(node.name);
        visited.add(current);
      }
      const neighbors = edgeMap.get(current) || new Set();
      for (const neighbor of neighbors) if (!seen.has(neighbor)) queue.push(neighbor);
    }
    depth++;
  }
  if (cluster.length >= 2) clusters.push(cluster);
}

visited.has(seed.id) means "this concept is already in some cluster" — that is a
reason to skip this seed, not to stop clustering. Only clusters.length >= maxClusters
is a terminating condition.

Reproduction

Extracting the function verbatim and running it on a synthetic graph shaped like a
real concept graph (one hub region plus random edges), with maxClusters = 10,
alongside the same function with only the two fixes below applied:

graph: 5128 concept nodes, 21127 edges, maxClusters=10

as shipped: clusters=6 seedsTried=7 reason="break on already-visited seed" 28ms
            sizes=[398, 396, 470, 394, 395, 382]
with fixes: clusters=10 10ms
            sizes=[398, 396, 470, 394, 395, 382, 309, 308, 307, 308]

Seven seeds are tried, the seventh is already visited, and the loop breaks — so
six clusters are returned instead of the ten requested. With continue in place of
break the function returns all ten, and replacing the find() with a Map lookup
makes it 2.8× faster on the same input.

Expected: seeds already assigned to a cluster are skipped; clustering continues
until maxClusters distinct clusters exist or the seed list is exhausted.

Self-contained reproduction script (node or bun, no dependencies)

// Verbatim extraction of buildGraphClusters from
// @agentmemory/agentmemory 0.9.28 dist/index.mjs, instrumented only to report
// why the seed loop ended. Confirms the numbers quoted in the upstream issue.
function asShipped(nodes, edges, maxClusters) {
  const conceptNodes = nodes.filter((n) => n.type === "concept" && !n.stale);
  if (conceptNodes.length === 0) return { clusters: [], seedsTried: 0, reason: "no concept nodes" };
  const edgeMap = new Map();
  for (const edge of edges) {
    if (edge.stale) continue;
    if (!edgeMap.has(edge.sourceNodeId)) edgeMap.set(edge.sourceNodeId, new Set());
    if (!edgeMap.has(edge.targetNodeId)) edgeMap.set(edge.targetNodeId, new Set());
    edgeMap.get(edge.sourceNodeId).add(edge.targetNodeId);
    edgeMap.get(edge.targetNodeId).add(edge.sourceNodeId);
  }
  const degree = new Map();
  for (const node of conceptNodes) degree.set(node.id, (edgeMap.get(node.id) || new Set()).size);
  const sorted = [...conceptNodes].sort((a, b) => (degree.get(b.id) || 0) - (degree.get(a.id) || 0));
  const visited = new Set();
  const clusters = [];
  const conceptNodeIds = new Set(conceptNodes.map((n) => n.id));
  let seedsTried = 0;
  let reason = "seed list exhausted";
  for (const seed of sorted) {
    seedsTried++;
    if (visited.has(seed.id) || clusters.length >= maxClusters) {
      reason = visited.has(seed.id) ? "break on already-visited seed" : "reached maxClusters";
      break;
    }
    const cluster = [];
    const queue = [seed.id];
    const seen = new Set();
    let depth = 0;
    while (queue.length > 0 && depth <= 2) {
      const levelCount = queue.length;
      for (let i = 0; i < levelCount; i++) {
        const current = queue.shift();
        if (seen.has(current)) continue;
        seen.add(current);
        if (conceptNodeIds.has(current)) {
          const node = conceptNodes.find((n) => n.id === current); // O(n) inside BFS
          if (node) cluster.push(node.name);
          visited.add(current);
        }
        const neighbors = edgeMap.get(current) || new Set();
        for (const neighbor of neighbors) if (!seen.has(neighbor)) queue.push(neighbor);
      }
      depth++;
    }
    if (cluster.length >= 2) clusters.push(cluster);
  }
  return { clusters, seedsTried, reason };
}

// Same logic with only the two proposed fixes applied, to size the delta.
function withFixes(nodes, edges, maxClusters) {
  const conceptNodes = nodes.filter((n) => n.type === "concept" && !n.stale);
  if (conceptNodes.length === 0) return { clusters: [] };
  const edgeMap = new Map();
  for (const edge of edges) {
    if (edge.stale) continue;
    if (!edgeMap.has(edge.sourceNodeId)) edgeMap.set(edge.sourceNodeId, new Set());
    if (!edgeMap.has(edge.targetNodeId)) edgeMap.set(edge.targetNodeId, new Set());
    edgeMap.get(edge.sourceNodeId).add(edge.targetNodeId);
    edgeMap.get(edge.targetNodeId).add(edge.sourceNodeId);
  }
  const degree = new Map();
  for (const n of conceptNodes) degree.set(n.id, (edgeMap.get(n.id) || new Set()).size);
  const sorted = [...conceptNodes].sort((a, b) => (degree.get(b.id) || 0) - (degree.get(a.id) || 0));
  const byId = new Map(conceptNodes.map((n) => [n.id, n])); // fix 2: O(1) lookup
  const visited = new Set();
  const clusters = [];
  for (const seed of sorted) {
    if (clusters.length >= maxClusters) break;
    if (visited.has(seed.id)) continue; // fix 1: skip the seed, do not stop
    const cluster = [];
    const queue = [seed.id];
    const seen = new Set();
    let depth = 0;
    while (queue.length > 0 && depth <= 2) {
      const levelCount = queue.length;
      for (let i = 0; i < levelCount; i++) {
        const current = queue.shift();
        if (seen.has(current)) continue;
        seen.add(current);
        const node = byId.get(current);
        if (node) {
          cluster.push(node.name);
          visited.add(current);
        }
        const neighbors = edgeMap.get(current) || new Set();
        for (const neighbor of neighbors) if (!seen.has(neighbor)) queue.push(neighbor);
      }
      depth++;
    }
    if (cluster.length >= 2) clusters.push(cluster);
  }
  return { clusters };
}

// Synthetic graph shaped like the real one: a hub region plus scattered edges.
const N = 5128;
const nodes = Array.from({ length: N }, (_, i) => ({
  id: "n" + i, type: "concept", name: "c" + i, stale: false,
}));
const edges = [];
for (let i = 1; i < N; i++) edges.push({ sourceNodeId: "n" + (i % 50), targetNodeId: "n" + i, stale: false });
for (let i = 0; i < 16000; i++) {
  edges.push({ sourceNodeId: "n" + (i % N), targetNodeId: "n" + ((i * 7 + 3) % N), stale: false });
}

let t = Date.now();
const a = asShipped(nodes, edges, 10);
const ta = Date.now() - t;
t = Date.now();
const b = withFixes(nodes, edges, 10);
const tb = Date.now() - t;

console.log("graph: " + N + " concept nodes, " + edges.length + " edges, maxClusters=10");
console.log("");
console.log("as shipped: clusters=" + a.clusters.length + " seedsTried=" + a.seedsTried +
            " reason=\"" + a.reason + "\" " + ta + "ms");
console.log("            sizes=[" + a.clusters.map((c) => c.length).join(", ") + "]");
console.log("with fixes: clusters=" + b.clusters.length + " " + tb + "ms");
console.log("            sizes=[" + b.clusters.map((c) => c.length).join(", ") + "]");

Observed downstream effect

Feeding ~400-concept clusters to the insight prompt yields generic, mutually
redundant conclusions. In this installation the insights table holds 1,604
records tracing back to only 4 distinct sourceConceptCluster values:

  715x  ['compression', 'headroom']
  625x  ['/v1/compress', 'large-block', 'read-cache']
  210x  ['AgentMemory service', 'Kompress', 'local embeddings']
   54x  ['integration,', 'mcp/tooling']

All carry confidence between 0.95 and 0.98, so confidence is not a usable
signal for deduplication. There is also no way to clean this up through the API:
/insights is GET-only, POST /governance/bulk-delete filters memories only, and
mem::insight-decay-sweep requires confidence <= 0.1.

Note that the 4th cluster's members are 'integration,' (with a trailing comma)
and 'mcp/tooling' — these are lesson.tags and whitespace-split sem.fact
terms, i.e. the shape produced by buildJaccardClusters, not concept node names.
Combined with 1,545 of the records carrying sourceLessonIds, this shows the
Jaccard fallback path produced all of them, which means buildGraphClusters
returned zero usable clusters on the real graph despite 5,128 concept nodes being
present.

Requested fixes

1. Change the visited-seed case to continue; keep break only for
   clusters.length >= maxClusters.
2. Replace conceptNodes.find() with a Map<id, node> built once alongside
   conceptNodeIds.
3. Return usedFallback (and ideally the cluster provenance) in the mem::reflect
   result and in functionMetrics. Today the only way to tell which clusterer ran
   is to inspect the shape of sourceConceptCluster on stored insights.
4. Deduplicate insights before write, or gate on semantic novelty. With clusters
   this large, the same conclusion is regenerated on every run.
5. Consider a bound on cluster size — a cluster spanning 400 concepts is not a
   coherent unit for insight extraction regardless of how it was formed.

Separate but related: unbounded state enumeration

mem::reflect applies maxClusters only after fully enumerating five KV scopes:

const [graphNodes, graphEdges, semanticMemories, lessons, crystals] = await Promise.all([
  kv.list(KV.graphNodes), kv.list(KV.graphEdges), kv.list(KV.semantic),
  kv.list(KV.lessons), kv.list(KV.crystals),
]);

So maxClusters cannot bound the initial transfer or allocation. On this graph
POST /agentmemory/reflect returns {"error":"Invocation stopped"} within 3–10
seconds at both maxClusters: 1 and maxClusters: 10. The string is emitted by
the iii engine (engine/src/invocation/mod.rs), not by AgentMemory or iii-sdk; the
failure is not recorded in functionMetrics, so it aborts before or very early in
the function body. I could not determine the exact engine predicate (response
size, KV scan bound, worker cancellation), so I am not claiming one.

This overlaps #655, which analysed the sequential-KV cost in semantic and
reflect on 0.9.21. Confirming here that on 0.9.28 the same class of failure
persists, with these additional data points:

• episodic 141s ✅ and semantic 91s ✅ both succeed when the client timeout is
  raised past 180s — they are slow, not broken. (memory_consolidate (semantic) and memory_reflect timeout due to sequential KV operations #655 saw semantic time out under
  Claude Code's 120s MCP default.) Running these two took this installation's
  distilled memory count from 53 to 103.
• procedural reliably consumes exactly 180s and returns an empty body, matching
  default_timeout: 180000 in iii-config.yaml. Its branch has the same
  unbounded shape: kv.list(KV.memories) followed by an unbounded prompt.
• reflect fails in 3–10s, i.e. it does not reach the timeout path at all —
  a different failure mode from the one in memory_consolidate (semantic) and memory_reflect timeout due to sequential KV operations #655.

The clustering bug above is independent of all of this: it is what makes the
insights redundant, whereas this is what makes reflect unable to finish. Fixing
either one alone leaves the other in place. Fix (1) is by far the smaller change.