Incremental by Accident: Clustering That Only Grows

We ran a streaming algorithm over data that never streamed anywhere. It cost us our issue catalog.

Our platform watches AI agents work. It detects findings — moments where an agent failed a user — and clusters them into issues: the distinct underlying problems worth fixing. One agent we monitor had a simple, honest gap: it had tools to create things but no tools to delete them. Users kept hitting this. One capability gap, one product decision to make.

Our issues page said there were forty problems.

Unable To Delete Records. Missing Ability To Delete Records. Unable To Delete List Records. Unable To Delete Records From Lists. Unable To Delete Duplicate Records. Unable To Delete Temporary Records. Plus parallel families for fields, sections, lists, and views. Sprinkled among them, four issues with the literally identical title "Unable To Delete Workspaces," created within five minutes of each other on the same afternoon.

(Issue titles are lightly anonymized. The shape — the near-duplicates, the four identical ones — is verbatim.)

This is a story about why that happened — and why the answer turned out to be a decade-old result from clustering theory, hiding in a system that never thought of itself as a streaming system at all.

The system's own ruler says they're duplicates

The pipeline's identity rule is simple. Every twenty minutes, a run takes the new findings, embeds their descriptions, clusters them, and compares each cluster against the existing issues. Closer than a threshold to some existing issue: attach. Farther than the threshold from every existing issue: mint a new one. The threshold is the system's operational definition of "same problem."

So we applied the system's definition to the system's output. Embed every finding, build a centroid per issue, and measure the issues against each other. Thirty percent of issue pairs sat closer than the threshold the pipeline itself uses — each of those pairs a merge the system's own logic endorses, except both issues exist anyway. Worse: findings inside one issue averaged 0.31 apart, while entire neighboring issues sat 0.05–0.15 apart. The issues were internally looser than they were distinct from each other. The boundaries between them carved nothing; they were accidents of which findings happened to arrive in the same twenty-minute window.

If your clustering's boundaries dissolve under its own similarity metric, the interesting question stops being "which threshold is right?" and becomes "what kind of process produces boundaries like this?"

Deterministic is not repeatable

The clustering algorithm is deterministic: same input, same output. It's tempting to conclude that its decisions are therefore stable. They aren't, because no two runs ever see the same input.

Each run sees one window's sample of an ongoing phenomenon. The same capability gap generates different findings every hour — different users, different phrasings, LLM-written descriptions that vary in prose even when the facts are identical. The cluster centroid lands somewhere slightly different each time, and when the true distance to an existing issue hovers near the threshold, one run's sample measures just under and attaches, the next measures just over and mints. The existing issue's embedding, meanwhile, is frozen at creation — built from its first ten findings and never updated — so an issue anchored by an unrepresentative early sample systematically mis-measures against the very findings that belong to it.

And here's the asymmetry that turns noise into ruin: a correct decision changes nothing, a wrong attach disappears quietly into an existing issue, but a wrong mint adds a permanent row. The catalog had operations for add, assign, and close. It had no operation for merge. Minting is the only mistake that changes the catalog's size, and nothing ever subtracts. With any error rate above zero and seventy-two runs a day, the expected number of excess issues grows linearly, forever. Tuning the matcher changes the slope. It cannot change the sign.

We watched somebody try the bulldozer alternative mid-investigation: wipe the catalog, recompute from scratch. It worked — the count dropped by a third — and it destroyed every issue's history, status, and accumulated impact in the process. New duplicates appeared the next day. The ratchet doesn't care that you reset it.

The threshold was never going to save us

The obvious response is to tune the threshold, so we measured whether a good value exists. We labeled finding pairs by the object of the missing capability — labels from keyword rules, deliberately independent of the embeddings — and split every pair into same-gap and different-gap. The two distance distributions overlap heavily at every point in time. Even in the system's best month, 41% of different-gap pairs sat under the merge threshold; the best possible single threshold scores about 0.7 accuracy. There is no cut. Raise the threshold and we verified what happens empirically: average-linkage chaining assembles a 149-finding grab-bag spanning eight different objects, while the things that should stay separate start fusing. Lower it and the shattering accelerates.

The distributions also move. A prompt improvement — a good one, which taught the finding analyzer to ground its claims in tool evidence — made descriptions richer, more scenario-specific, more variable. Same-gap pairs drifted 21% farther apart in six weeks, because the text that defines an issue's identity was also serving as human-readable evidence, and evidence wants specificity while identity wants canonical form. One string, two masters. Every future improvement to the descriptions will degrade the clustering again, as long as the clustering reads the descriptions.

The theorem we were unknowingly re-proving

At this point the empirical picture — online decisions, permanent commitments, inevitable fragmentation — started to sound familiar, and it turns out to have a name. Ackerman and Dasgupta (NIPS 2014) proved that incremental clustering is strictly weaker than batch clustering: there are cluster structures that any batch algorithm can find but that no incremental algorithm can identify, because an incremental learner must commit to boundaries before seeing the data that would justify them. It's not a matter of a smarter similarity function. The information needed to draw the boundary correctly hasn't arrived yet when the commitment is forced.

Check the definition against our pipeline. Sequential arrival with immediate commitment: yes — each run assigns its window's findings permanently. Summarized memory: yes, and worse than the textbook version — the matcher never sees past findings, only each issue compressed to one frozen embedding. No revision: emphatically yes — the merged_from column sat empty on every row; no code path ever compared two existing issues.

So the forty-issue catalog isn't a bug in our matcher. It's the theoretically expected output of an incremental clustering protocol. And Ackerman and Dasgupta's positive result points directly at the remedy: the limitation is overcome by letting the incremental phase keep more clusters than the true number, then consolidating afterwards. Over-generate, then merge offline. The stream-processing world built its canonical architecture on the same insight — CluStream keeps many small online micro-clusters and re-clusters them offline with full information — and the entity-resolution world arrived there too, with incremental record linkage that treats merging and splitting existing clusters as first-class corrections.

But there was one more twist, and it's the one that stung. The formal streaming model assumes bounded memory because the data is gone — points flow past and cannot be revisited. Our findings were all still there, every one of them, sitting in the warehouse. We were running an incremental protocol over data that never required one. The impossibility applied to our protocol, not our situation. We had been choosing the constraint, run by run, for five weeks, while everything a batch algorithm needed sat in a table underneath.

What actually fixes it

Not a better matcher. Three things, in order of leverage:

A merge operation. A periodic job that reads the catalog it already owns, proposes candidate duplicate pairs with embeddings (a job embeddings do fine — proposing is recall, and recall is easy), and has an LLM rule on each pair by reading both issues with their findings and answering the only question that defines issue identity: would one fix resolve both? Confirmed merges reassign findings, record provenance, and retire the duplicate. This is the structural fix because it changes the failure class: with corrections in the loop, the online matcher's mistakes stop being permanent, and the catalog converges to equilibrium instead of growing forever. Every other improvement becomes optional the day this exists.
Erring toward fragments, on purpose. Once merging exists, the two error directions stop being symmetric in a new way: merging two clean shards is one cheap, auditable decision, while splitting a contaminated blob means re-adjudicating every member — the original clustering problem, reopened inside a cluster whose title misdescribes half its contents. So the online phase should run tight, over-fragmenting into pure shards, and every correction should flow merge-ward. This is exactly the theory's prescription, and it inverts the instinct to loosen thresholds when you see duplicates.
Splitting identity from evidence. The deepest cause was making one LLM-written paragraph serve as both the human-readable evidence and the machine-readable identity. We tested the alternative on real data: have the analyzer emit a tiny canonical claim alongside its rich description — a verb from a closed list, an object, and a why (missing tool vs. unsupported API vs. permission). Two hundred twenty-one messy findings collapsed to twenty-six exact identities by nothing fancier than GROUP BY, with the fix-relevant distinctions preserved and nothing left for a threshold to get wrong. Structure where structure is cheap; similarity only for the residue that resists it.

The lesson

If your system assigns identities incrementally — issue deduplication, entity resolution, crash bucketing, intent taxonomies, anything that answers "have I seen this before?" one arrival at a time — ask two questions. Can a wrong identity ever be corrected? If not, your error rate is your permanent damage rate, and no amount of model quality changes the direction of drift. And: is the incrementality actually forced? If the raw data still exists, the streaming constraints you're suffering under are self-imposed, and the provably correct architecture — over-generate online, consolidate offline — is one scheduled job away.

We spent five weeks measuring our way to a conclusion a 2014 paper states in its title. The catalog only grows because we only ever let it grow. The fix is not to make the 3 a.m. decision infallible. The fix is to let the system change its mind.