Spending Uncertainty Compute Where Transitivity Breaks

Many grouping tasks, such as deduplicating product records, deciding which author wrote which paper, or linking pronouns to the people they refer to, are solved by a model that looks at two items at a time and asks "are these the same thing?" The answers do not have to agree with each other. A model can say A matches B and B matches C, then say A does not match C. These broken triangles, called transitivity violations, cause most of the expensive failures once pairwise answers are merged into groups. A common response is to make each pairwise answer more trustworthy with sampling-based uncertainty estimates: run the model many times with random perturbations, such as Monte Carlo dropout (randomly switching off parts of the network at test time and averaging), multiple LLM samples, or swapped input orders, and treat disagreement as uncertainty. That multiplies cost by the number of samples $S$, and here it multiplies a cost that already grows with the square of the number of items.

This note proposes using the broken triangles to decide where the sampling goes. The first, deterministic pass over the candidate pairs produces a graph. The places where that graph contradicts itself are visible at no extra model cost, and they mark the edges whose resolution can change the final grouping. We spend the $S$ stochastic passes only on edges that sit in strongly violated triangles or near a clustering merge decision, and keep every other edge at one pass. The central bet concerns confident edges: a pair scored 0.9 that closes an impossible triangle is exactly the "confidently wrong" case that a single-pass confidence threshold cannot see. If the bet holds, the method should match the partition quality of sampling every edge at a small fraction of the cost.

Core Claim

Triangle conflict on the single-pass graph is a cheap, label-free signal for allocating uncertainty compute. It finds a different set of edges than low confidence does, and it finds edges that matter more for the final clusters. Concretely, on a fixed budget of extra forward passes, choosing edges by conflict plus closeness to a merge decision should produce higher cluster-level F1 than choosing them by closeness to probability 0.5. It should also produce higher cluster-level F1 than choosing them at random, and it should approach the quality of sampling every edge.

The conflict score has a simple form. Write $p_{ij}$ for the single-pass match probability of items $i$ and $j$. A triangle $(i,j,k)$ is violated to the degree that two strong links force a third link the model denies. A relaxed version of transitivity, taken from many-valued logic where "A and B implies C" fails by $\max(0, a+b-1-c)$, gives

$$v_{ijk} = \max\left(0,\; p_{ij} + p_{jk} - 1 - p_{ik}\right),$$

and an edge's conflict score $c_{ij}$ sums $v$ over every triangle and every rotation in which the edge takes part. Triangles are counted only inside the candidate blocks that pairwise systems already use, so computing $c$ is cheap compared with model passes.

Relation to Prior Work

Two lines of work motivate the gap. On the structural side, early coreference work showed how independent pairwise decisions chain "the president" → "he" → "the company" into one false group (Noun Phrase Coreference as Clustering). Hypergraph partitioning work characterised the cycles that make naive transitive closure collapse distinct entities (Unsupervised Coreference Resolution with HyperGraph Partitioning). Aberbach et al. showed that pairwise precision and recall give credit to graphs that are internally contradictory (Multipartite Entity Resolution: Motivating a K-Tuple Perspective). All three treat violations as a defect to be repaired after scoring. We use them as a measurement that tells us where to look harder.

On the uncertainty side, UPS filters pseudo-labels by variance across ten Monte Carlo dropout passes and shows that raw confidence is badly miscalibrated (In Defense of Pseudo-Labeling). That evidence motivates us, and the ten-fold cost it accepts is the cost we want to avoid. SCOPE reduces the overhead of pairwise LLM judging to exactly two order-swapped passes and adds conformal error control (SCOPE: Selective Conformal Optimized Pairwise LLM Judging). It treats pairs in isolation and spends two passes on every pair. We borrow its order-swap as one source of stochastic passes, but spend it selectively and judge it by the partition it produces. AdaNSP is the closest analogue in spirit, because it uses uncertainty to trigger extra computation only on hard tokens (AdaNSP). Its trigger, however, is itself a dropout-variance estimate that must be paid for everywhere. Our trigger is a structural property of outputs we already have.

On the structural repair side, S2AND feeds deterministic LightGBM scores into average-linkage agglomerative clustering, which merges groups bottom-up by average pairwise score (S2AND). Integer linear programming and Markov logic encode transitivity as hard or soft constraints (Adapting Coreference Resolution for Narrative Processing; Joint Learning for Coreference Resolution with Markov Logic). These methods supply our final clustering step and limit what we can claim: if the scores they consume are wrong but confident, they will return a consistent but wrong partition. Our contribution sits upstream of them. ComEM switches LLM matching from pairs to selecting among candidates and uses a cheap model as a filter before an expensive one (Match, Compare, or Select?). It is the strongest existing cost-aware system. Its escalation is heuristic and per-anchor rather than driven by graph contradictions.

Research Program

The system has four stages. Stage one runs a single deterministic pass of a pairwise matcher over blocked candidate pairs. Stage two computes, for each edge, the conflict score $c_{ij}$ and a merge-sensitivity score. The merge-sensitivity score is the gap between the edge's contribution to the linkage score at the merge where it is consumed and the clustering threshold, so it measures how close the edge is to flipping a merge. Stage three ranks edges by a combination of the two scores and spends $S$ stochastic passes on the top fraction $\beta$ of edges. The stochastic passes are Monte Carlo dropout for neural cross-encoders (Gal et al.), and order-swapped plus temperature-sampled queries for LLM matchers. Resampling is iterated in rounds, because updating an edge can create or resolve conflicts elsewhere. Stage four clusters using the posterior mean, with an optional variant that replaces each edge with a lower confidence bound so that uncertain bridges cannot drive a merge.

The analysis has three parts. First, we measure how much the edges flagged by conflict overlap with those flagged by a confidence band. Second, we compare error rates within each flagged set. Third, we count how many final cluster changes come from each set. Together these tell us whether conflict carries information that confidence lacks. We also report the triangle-counting cost against model-pass cost, to confirm the selection step is negligible at block sizes found in practice.

One honest restriction applies. On two-table entity matching benchmarks where each table is internally clean, transitivity reduces to a weaker one-to-one constraint: a record matched to two records in the other table forms a conflict. Full triangle structure appears only where an entity has several records, as in author disambiguation and multi-source matching. We therefore treat author disambiguation as the primary testbed and two-table matching as the setting where the method should help least.

Baselines

The naive reference point is a single deterministic pass followed by the same clustering step, with no extra compute. Every method is reported as a gain over this point, at a matched number of extra forward passes or tokens.

The upper reference is full sampling: $S$ stochastic passes on every candidate edge, the UPS-style recipe applied to edges (In Defense of Pseudo-Labeling). It defines the quality ceiling and the cost we aim to cut. Success means recovering at least 90% of its gain over the naive point while spending at most a quarter of its extra passes.

The strongest selective competitor is confidence-band triage, which spends the same $S$ passes on the edges with $p_{ij}$ closest to the clustering threshold. This is what a skeptical practitioner would build first, and we run it with the same matcher, the same $\beta$ grid, and the same tuning budget on a held-out split. Our method beats it only if it wins on cluster-level F1 at equal budget across most datasets. Random selection at equal budget is included to show that any selection rule matters at all.

The strongest existing systems come from the cited papers. On author disambiguation it is the S2AND reference pipeline (S2AND). The file reports only a relative result, an error reduction of over 50% in $B^3$ F1 against the Semantic Scholar production algorithm, so we rerun the released pipeline on the same splits. On entity matching it is ComEM, reported at 86.42 F1 with GPT-4o Mini at a cost of 0.09 (Match, Compare, or Select?); the file does not give units for the cost. We rerun ComEM with the same LLM and matched token budgets rather than comparing against the quoted figure across setups.

The key ablations isolate the two scores. A conflict-only variant and a merge-sensitivity-only variant are compared with their combination. A "structure without resampling" variant runs correlation-style clustering that repairs conflicts directly from single-pass scores. That last variant tests whether the extra passes add anything beyond structural repair.

Why not just…?

Why not just threshold single-pass confidence and resample the borderline edges? This is the real threat, and it appears as the confidence-band baseline above. The case against it rests on the miscalibration evidence. UPS reports that confidence-based pseudo-labeling reached 22.02% error on CIFAR-10, against 8.18% with uncertainty filtering. SCOPE reports that softmax confidence and verbalized confidence fail to separate correct from incorrect pairwise judgments on JudgeBench. A band around 0.5 never selects a confidently wrong edge, and a confidently wrong edge closing a triangle is the case that merges two entities. The decisive measurement is the error rate among edges that are flagged by conflict but lie outside the band. If that rate is no higher than the band's own error rate, the core claim is wrong and we will report it.

Why not just run average-linkage clustering or an exact solver on the point estimates? S2AND already does the former and still degrades on hard facets such as common names and large blocks. Exact integer programming scales with the cube of the number of items and optimizes whatever scores it is given. The "structure without resampling" ablation answers this directly. If repairing conflicts from single-pass scores matches our method, the extra passes are unnecessary and the contribution shrinks to a diagnostic.

Why not just let an LLM select among candidates, as ComEM does? Selecting gave a 16.02% average F1 gain over pairwise matching, but Wang et al. document position bias, and context limits force a filtering stage. Our method is compatible with ComEM: conflicts in the graph built by its cheaper filtering model can decide which anchors are escalated to the expensive selector. We run that hybrid against ComEM's own escalation rule at equal token cost.

Proposed Experiments

The primary testbed is the eight harmonized S2AND datasets. Here the pairwise scorer is a neural cross-encoder over SPECTER embeddings and metadata with dropout, so that Monte Carlo passes are meaningful and costly; the LightGBM reference model is kept as an external baseline. The second testbed is the entity matching suite of Abt-Buy, Amazon-Google, Walmart-Amazon, DBLP-ACM, DBLP-Scholar, IMDB-TMDB, IMDB-TVDB and TMDB-TVDB. On this suite we use two matchers: a fine-tuned cross-encoder with dropout, and an LLM matcher whose stochastic passes are order swaps and samples. The media datasets have three sources, which also allows a multipartite variant in which records from three tables are merged into one graph so that real triangles appear.

Metrics are $B^3$ F1 for clusters, with pairwise F1 reported only alongside it given the evaluation problems Aberbach et al. raise. We also report the fraction of output clusters that are fully consistent cliques under the model's own scores. Cost is measured in extra forward passes and, for LLMs, in tokens and wall-clock time. The main result is a curve of quality against extra compute for each selection rule, with $\beta$ swept from 1% to 100%.

Three checks decide the outcome. First, on every dataset, the conflict-plus-sensitivity curve should dominate the confidence-band curve at low budgets ($\beta \le 10\%$). Second, the gain should be largest on S2AND's hard facets and on large blocks, where triangles are dense, and smallest on clean two-table matching. That pattern is what the mechanism predicts, and a uniform gain would suggest something else is at work. Third, the out-of-band conflict edges should have higher error than in-band edges. If the first check passes but the third fails, the gains come from merge sensitivity, not transitivity, and the note's framing would be revised accordingly.