Bottom-up clustering builds groups by repeatedly joining the two most similar clusters. Every join is permanent. If an early join is wrong, for example two biomedical mentions linked to the wrong concept or two broken pottery fragments glued at the wrong orientation, every later join builds on that mistake. Current systems defend against this in two ways. They refuse to merge unless confidence is very high, or they repair the tree after the fact. We propose a third defense taken from submodular optimization, the study of set functions with diminishing returns. The clusterer keeps two candidate clusterings that agree on every confident merge and are forced to disagree on every ambiguous one. Because the two candidates never make the same ambiguous commitment, at least one of them avoids each trap. A small online coordination rule, borrowed from fast equilibrium solvers, moves contested items between the candidates as later evidence arrives.
In plain terms, a wrong merge only cascades when there is no alternative on hand. We keep exactly one deliberately different alternative, and only where it is needed. The design comes from the Interlaced Greedy and TwinGreedy algorithms. These hold two disjoint candidate sets and certify a deterministic 1/4 approximation for objectives where adding an item can hurt, where a single greedy set can be trapped arbitrarily badly. We carry that guarantee into the merging regime and test whether it prevents cascades more cheaply than beam search, conservative thresholds, or tree grafting.
Core Claim
For clustering problems whose merge objective can be written as a non-monotone submodular function over item-to-anchor assignments, the following procedure has a deterministic constant-factor guarantee on the ambiguous part of the problem. First, commit confident merges to a shared core. Second, route each ambiguous merge decision into one of two candidate clusterings, under the rule that no ambiguous assignment appears in both. Our empirical claim is that this twin structure cuts cascading errors on entity linking and fracture assembly more than a beam of the same width. Beam search keeps near-duplicate hypotheses that tend to agree on exactly the hard decisions. The twin structure differs from them on precisely those decisions.
Grounding in Prior Work
The mechanism comes from disjoint candidate set maintenance. Interlaced Greedy alternates greedy additions between two disjoint sets. It uses the inequality $f(O\cup A)+f(O\cup B)\ge f(O)$, where $O$ is the optimal set, to obtain a deterministic $(1/4-\epsilon)$ guarantee under a cardinality limit. It also adds an end-of-run "stealing" heuristic that moves elements between the sets and improved quality by up to 45% on Barabási–Albert graphs. TwinGreedy extends the idea to matroids, which are constraint families such as "each item picks at most one option." It gives a 1/4 guarantee in $O(nr)$ time and a nearly linear-time variant. Both treat the two sets as rival final answers and coordinate them only at the end. We reuse their routing rule. We change two things: the unit being routed is a merge decision inside a clustering, and coordination happens during construction rather than afterward.
The objective class comes from Maximizing Sums of Non-monotone Submodular and Linear Functions. That paper analyzes submodular-plus-linear objectives in the unconstrained case. We use its observation that a coherence reward minus a linear cost per assignment is non-monotone submodular, and we pair that objective with a matroid constraint so that TwinGreedy's bound applies.
The application regime is irreversible merging, and here the prior work motivates the gap. Clustering-based Inference for Biomedical Entity Linking names the cascading error. It limits damage with a hard rule that allows at most one knowledge-base entity per cluster, and reaches 74.1% accuracy on MedMentions and 91.3% on BC5CDR. It cannot undo a wrong merge between two mentions that both lack an entity. PuzzleFusion++ merges 3D fragments only when a learned verifier scores the fit above 0.9. That paper both motivates and constrains this proposal: its threshold works (70.6% part accuracy on Breaking Bad Everyday), but the authors report stalls on 180° symmetric ambiguities. That is exactly where a second hypothesis should help. GRINCH repairs trees online by moving whole subtrees ("grafting"). It reaches purity 1.0 on chain-shaped data where rotation-only methods reach about 0.85, but it needs nearest-neighbor indices and search caps near the root. The earlier iterative improvement procedure hill-climbs over a finished tree. Both methods repair mistakes after the fact. Ours avoids committing to them. Neither of these repair methods, nor the thresholding systems, carries any approximation guarantee.
The coordination step borrows from equilibrium search. Predictive Blackwell approachability shows that adding a lag-1 loss prediction to regret matching (PRM+) damps oscillation and speeds convergence by several orders of magnitude when dynamics are stable. The same paper also reports that the method fails to beat Discounted CFR in the River poker endgame, where randomly dealt private cards make losses noisy. We treat that negative result as a warning. Our coordination losses may also be noisy, so predictive coordination is a falsifiable sub-claim, not a load-bearing one.
Research Program
We first set up the objective. Each item $i$, such as a mention or a fragment, may be assigned to at most one anchor $a$, such as a knowledge-base entity or a super-fragment. This "at most one" rule is a partition matroid. A solution is a set $S$ of assignments $(i,a)$, and its value is
$$f(S)=\sum_{a}\ \sum_{j\in N_a}\ \max_{(i,a)\in S} w_{ij} \;-\; \lambda\,|S|.$$
Here $N_a$ is the set of reference points associated with anchor $a$, $w_{ij}\ge 0$ is a learned affinity between items $i$ and $j$, and $\lambda>0$ is a per-assignment cost. The first term is facility location, the value of letting each reference point be represented by its best-matching assigned item. It is monotone submodular. Subtracting the linear cost makes the whole objective non-monotone, so adding an assignment can lower the score. For hierarchies, we apply the same objective level by level, treating super-clusters from the previous level as items.
The algorithm then runs in two phases. Any merge whose score margin over its runner-up exceeds a threshold $\tau$ goes into a shared core. The remaining ambiguous decisions are routed TwinGreedy-style: each ambiguous assignment enters whichever candidate, $A$ or $B$, gains more from it, and never both.
We will prove that, conditioned on the core, the better of $A$ and $B$ achieves at least $1/4$ of the best completion of the core. We will also bound how much a $\tau$-margin core can lose. Gap 4 in the file asks whether thresholding breaks the twin guarantee, and this bound answers it.
Coordination is online. An ambiguous connected component is a group of items whose ambiguous decisions interact. For each one, we keep a two-action regret learner that asks whether the component should follow $A$'s or $B$'s choice. Its loss is the change in $f$ as later merges land. The learner uses PRM+ with lag-1 prediction. An item moves between candidates only when the learner's probability mass crosses one half. The final output takes, per component, whichever candidate the learner favors.
Finally, we will measure cost. We report the overhead as a function of the fraction of ambiguous decisions. The overhead should be close to one clustering when ambiguity is rare, because the shared core does most of the work.
Baselines
The naive reference is ordinary greedy agglomeration with the same learned affinities and no threshold. It shows how much cascading error there is to remove.
The strongest problem-specific systems are the published pipelines. For entity linking, we will run the constrained clustering of Clustering-based Inference for Biomedical Entity Linking with its cross-encoder affinities. Its reported MedMentions ST21PV accuracy is 74.1%. Beating it means exceeding that number with identical affinities and candidate generation, so that any gain comes from the merge procedure. For fracture assembly, we will run PuzzleFusion++ with its denoiser and verifier held fixed. Its reported figures are 70.6% part accuracy and Chamfer distance 6.03 on Everyday. We replace only its threshold rule with the twin rule and report runtime against its roughly 928 ms per sample.
The strongest general repair method is GRINCH. It reports purity 1.0 on synthetic chains versus about 0.85 for Perch and Online HAC. We run it on the same affinity graphs at equal wall-clock time.
The most dangerous competitor is width-2 beam search over merge sequences, keeping the two highest-scoring partial clusterings at equal objective evaluations. We found no reported result on Lacuna for beam-search agglomeration on these benchmarks, so we will establish it ourselves.
Three ablations isolate the key ingredients. Removing the disjointness rule turns the twins into a two-member beam. Replacing online coordination with Interlaced Greedy's end-of-run stealing tests the coordination step. Replacing PRM+ with plain regret matching+ tests whether the prediction term matters.
All methods share affinity models, tuning budgets for $\tau$ and $\lambda$ on the validation splits, and hardware. Beating a baseline means a gain larger than seed-to-seed variation across five seeds.
Why not just…?
Why not just use beam search? This is the real threat. A width-2 beam already keeps two hypotheses. Our argument is that beams fill with near-duplicates that share the same ambiguous commitments and differ only on trivial ones, so both members inherit the same cascade. The twin rule forces the two candidates apart exactly on ambiguous decisions and carries a worst-case bound that beams lack. The disjointness ablation settles the question directly. We will also measure how often the two hypotheses disagree on ambiguous decisions under each method. If a matched-compute beam matches our accuracy on MedMentions and Breaking Bad, the empirical claim fails, and what remains is the guarantee.
Why not just raise the confidence threshold? PuzzleFusion++ shows that strict thresholds prevent false merges but stall on symmetric ambiguities. The entity-linking paper recovered 14–19% of mentions only by letting ambiguous mentions borrow context from their neighbors, which a pure singleton policy forbids. We sweep the threshold to trace its accuracy-versus-coverage curve against ours.
Why not just graft afterward, as GRINCH does? Grafting fixes geometry-driven errors well. It does not help when affinities themselves are symmetric, as with 180° flips or two equally plausible entities, because there is no higher-affinity target to graft to. It also needs nearest-neighbor indices and root capping. We compare the two methods directly and also test twin-plus-graft, since the methods may combine.
Why not just use randomized greedy for its better 1/e ratio? Interlaced Greedy reports that its deterministic method beat FastRandomGreedy empirically. Randomization also gives no per-run guarantee in pipelines that need reproducibility. We will still include randomized greedy on the assignment objective.
Why not just use plain regret matching, or no coordination at all? The file's evidence for prediction comes from games with stable dynamics, and prediction failed under noise. If PRM+ does not beat plain regret matching+ or end-of-run stealing on reassignment churn and final accuracy, we drop it and report that finding.
Proposed Experiments
On MedMentions ST21PV and BC5CDR, we report linking accuracy and the number of mentions affected per erroneous merge. We measure the latter by counting how many downstream mentions inherit the wrong entity, which directly measures the cascade.
On Breaking Bad, Everyday and Artifact subsets, we report part accuracy, Chamfer distance, and the rate of stalled assemblies, broken down by fragments with rotational symmetry.
On GRINCH's synthetic chains, we report dendrogram purity under adversarial arrival order.
A synthetic max-cut and assignment suite on Erdős–Rényi and Barabási–Albert graphs, where the optimal solution is computable, checks that the empirical ratio stays above the proven 1/4 bound and tracks how it degrades as $\tau$ loosens.
The decisive check is the comparison of twin candidates against a width-2 beam at equal compute on the symmetric-ambiguity slice of Breaking Bad and the low-margin slice of MedMentions. If the twins do not reduce cascade size there, the proposal has failed.
References
- Interlaced Greedy Algorithm for Maximization of Submodular Functions in Nearly Linear Time
- Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
- Maximizing Sums of Non-Monotone Submodular and Linear Functions: Understanding the Unconstrained Case
- Clustering-based Inference for Biomedical Entity Linking
- PuzzleFusion++: Auto-agglomerative 3D Fracture Assembly by Denoise and Verify
- Scalable Hierarchical Clustering with Tree Grafting.
- An Iterative Improvement Procedure for Hierarchical Clustering
- Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent