Certified Pruning of Match Hypotheses for Many-Piece Fracture Assembly

Putting a shattered object back together from 3D scans of its pieces gets dramatically harder as the piece count grows. On the Breaking Bad benchmark, a learned baseline's part accuracy falls from about 31% on objects broken into 2–20 pieces to 4.8% on objects broken into 51–100 pieces (Breaking Bad). The strongest recent methods also report degradation beyond about 20 pieces. Much of the difficulty is not finding plausible pairwise fits; detectors of which pieces touch already reach recall above 0.80 on real Pompeii frescoes. The difficulty is that about half of those candidate fits are wrong (precision near 0.50, RePAIR), and wrong fits interact combinatorially. Current systems shrink the problem with heuristics. The most effective one, PuzzleFusion++, merges any pair its verifier scores above 0.9 and never revisits the decision.

We propose borrowing a tool from parameterized complexity called kernelization: polynomial-time "reduction rules" that provably shrink a hard instance to a small core without changing its answer. The plan is to prune and contract the candidate-match graph before any expensive global solver runs. We use the slack-preserving variant from constraint programming (On the Kernelization of Global Constraints). Every rule is guaranteed to keep every assembly whose score is within a chosen slack $z$ of the best one. Pieces whose placement is forced get merged with a certificate rather than a confidence threshold. What remains is a small set of genuinely ambiguous pieces, split into independent sub-puzzles. The bet is that real fracture instances have few ambiguous pieces even when $N$ is large. If so, the many-piece regime turns into a collection of small-piece problems, which existing solvers already handle well.

Core Claim

The claim is that a sound reduction step can raise candidate-match precision substantially at large $N$ while provably losing no near-optimal assembly. Sound means it never deletes a hypothesis used by any assembly within slack $z$ of optimum under the given pairwise scores and hard non-penetration constraints. Running a standard solver on the reduced instance should then beat running it on the full instance, and should beat heuristic agglomeration, on Breaking Bad objects with 21–100 pieces.

The guarantee is relative to the scoring model. If the true assembly scores more than $z$ below the best-scoring assembly, no sound rule can save it. We therefore measure how often that happens and report it rather than hide it.

Problem Formulation

A candidate generator proposes, for each pair of fragments $(A,B)$, up to $m$ relative-pose hypotheses $h$, each with a match score $s_h$. Here $s_h$ is a learned or geometric measure of how well the two fracture surfaces interlock. An assembly picks a spanning tree $T$ of hypotheses, which fixes all fragment poses up to one global transform. Its score is

$$ S(T) = \sum_{h \in T} s_h + \sum_{(A,B)\ \text{adjacent under } T,\ (A,B) \notin T} s_{AB}(T), $$

where the second term rewards non-tree pairs that end up touching consistently. $T$ is feasible only if no two fragments interpenetrate beyond a tolerance $\tau$. Write $S^\ast$ for the best feasible score. Our target is the set of feasible assemblies with $S(T) \ge S^\ast - z$.

The parameter we kernelize by is the number $k$ of ambiguous fragments: those still carrying more than one surviving hypothesis after reduction. A second parameter is the physical contact degree $d$, meaning the most fracture neighbors any piece can have. Because pieces of a solid object can only touch a bounded number of others, the contact graph cannot contain dense complete bipartite subgraphs. Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT shows that this kind of biclique-freeness is exactly the structure that rescues polynomial-size (approximate) kernels for weighted SAT. We use that result as motivation, not as a reusable proof.

Limits of Preprocessing constrains the design. It proves that constraint problems parameterized by treewidth or backdoor size admit no polynomial kernel under standard assumptions. We therefore deliberately avoid parameterizing by the treewidth of the adjacency graph and choose ambiguity and degree instead.

Research Program

The reduction rules mirror classical kernel rules, adapted to continuous poses.

The first rule is collision deletion. It removes any hypothesis whose induced pairwise pose makes the two pieces overlap in volume beyond $\tau$. This is sound because non-penetration is a hard constraint. When a pair of hypotheses $AB$ and $BC$ forces $A$ and $C$ to collide, the pair is recorded as a conflict rather than deleted.

The second rule is slack bounding, in the spirit of crown-style rules (On the Kernelization of Global Constraints). A hypothesis $h$ between $A$ and $B$ is deleted if

$$ s_h + U_{-h} < L - z, $$

where $L$ is the score of any feasible assembly found greedily, and $U_{-h}$ is an upper bound on the rest of any assembly containing $h$. $U_{-h}$ comes from summing each fragment's top-$d$ incident surviving scores and halving.

The third rule is forcing, analogous to the degree-one rule for vertex cover. If a fragment has exactly one surviving hypothesis connecting it to the rest, every connected assembly must use it, so the two fragments are contracted into one rigid cluster. Contraction then re-triggers collision and slack checks against the merged cluster.

These certified merges are what separate this work from PuzzleFusion++. PuzzleFusion++ merges on verifier confidence, which can be wrong and is irreversible. Our merges happen only when no near-optimal alternative exists.

The analysis has two goals. The first is a soundness theorem: all rules preserve every assembly within slack $z$. The second is a size bound: under contact degree $d$, the reduced instance has $O(dkm)$ hypotheses and decomposes along cut-free regions into independent components. The constants are not expected to be tight. Empirically, we will measure $k$ and component sizes on real instances, since the practical value rests on $k \ll N$.

The surviving components are solved separately. Small ones go to exact branch search, and larger ones go to an off-the-shelf solver: Jigsaw-style RANSAC plus Shonan rotation averaging, or PuzzleFusion++ restricted to that component.

Candidate hypotheses come from two sources so the method is not tied to one front end. One is complementary descriptor matching with Sinkhorn soft correspondence (Jigsaw), keeping the top $m$ poses per pair rather than one. The other is exhaustive breaking-curve registration (Reassembling Broken Objects using Breaking Curves), which isolates fracture boundaries by local covariance analysis and registers them with ICP. Neither source changes. The contribution sits strictly between candidate generation and global solving.

Baselines

The naive reference point feeds all candidate hypotheses, unpruned, to the same downstream global solver: RANSAC plus Shonan averaging as in Jigsaw, or the PuzzleFusion++ denoiser. It uses identical candidate sets and compute. This isolates whether reduction helps at all. Beating it means higher part accuracy and lower rotation error on the 21–50 and 51–100 piece strata at equal or lower wall-clock time.

The strongest existing method is PuzzleFusion++, which reports 70.6% part accuracy and Chamfer distance 6.03 on the Breaking Bad Everyday subset at about 928 ms per sample (PuzzleFusion++). It is the strongest competitor because it already performs reduction by agglomeration. We will run the released model with its default threshold on identical test splits. We will also run a variant where our reduced components replace its input, given the same GPU budget. The paper's reported number is not stratified by piece count, so the comparison of interest is stratified. Beating it means statistically significant gains in part accuracy on 21–100 pieces without losing more than one point on 2–20 pieces.

For rotation error we also compare against PHFormer. It compresses each fragment into a fixed number of proxy patches and predicts adjacency before pose, reporting 22.4° rotation mean absolute error on Everyday. On the Artifact subset we compare against Co-creation Space, which replaces quadratic cross-attention with a shared linear workspace and reports shape Chamfer distance 15.49. For the real-world setting, RePAIR reports that Breaking-Bad-trained models drop from $Q_{pos}$ 0.296 to 0.066, where $Q_{pos}$ is the shared volume with ground truth. Two baselines target the many-piece regime directly. One is the DGL baseline from Breaking Bad, with 4.8% accuracy on 51–100 pieces. The other is BITR, an equivariant pairwise pose model, which we include only on the pairwise wine-bottle setting where it reports 8.4°.

The key ablation is uncertified pruning matched in strength. It deletes hypotheses by score threshold and merges by confidence, tuned so that its reduction ratio equals ours on validation data. If it matches our downstream accuracy, the certificate adds nothing. We also ablate each rule separately: no collision rule, no slack rule, and no forcing contractions.

Why not just…?

Why not just calibrate the verifier and keep threshold merging? A better-calibrated PuzzleFusion++ verifier would reduce false merges, but a calibrated probability still errs at a known rate. Over the dozens of merges a 60-piece object requires, small per-merge error compounds into a likely corrupted assembly. The matched-reduction ablation above tests exactly this. We will also sweep the threshold to trace the full precision-versus-reduction curve against ours.

Why not just rely on robust synchronization such as RANSAC with Shonan averaging? This is the most serious threat. Robust rotation averaging already rejects inconsistent hypotheses, and if it does so as well as our rules at large $N$, our contribution reduces to a speedup. The naive baseline settles this directly by running the same synchronizer on pruned and unpruned inputs. If accuracy is unchanged, we will report the method as a preprocessing accelerator only. Our expectation is that synchronization fails once outliers dominate, which is the 50%-precision regime RePAIR documents. Robust averaging also does not enforce non-penetration, and our collision rule does.

Why not just run breaking-curve extraction with exhaustive ICP? On clean pairwise cases it is excellent, reporting relative rotation error 1.62 on beer bottles versus 78.93 for DGL (Reassembling Broken Objects using Breaking Curves). But it offers no global consistency mechanism for many pieces. We therefore use it as a candidate source and test whether our reduction is what lets it scale.

Why not just use linear-attention models like Co-creation Space? Their linear cost applies to message passing inside the network. They do not shrink the space of pose hypotheses and only softly penalize collisions. Any gap on high-$N$ strata in our comparison speaks to this directly.

Proposed Experiments

We evaluate on the Breaking Bad Everyday and Artifact subsets, stratified into 2–20, 21–50 and 51–100 pieces, and on RePAIR's 117 solved groups, including its distractor pieces as extra fragments.

The metrics are part accuracy, rotation mean absolute error, Chamfer distance, total interpenetration volume, and wall-clock time. Three reduction-specific diagnostics accompany them. The first is the retention rate of ground-truth hypotheses after pruning, which should equal the generator's recall whenever the true assembly is within slack. The second is the precision gain, measured on RePAIR from the reported baseline of about 0.50. The third is the distribution of the kernel parameter $k$ and of component sizes as a function of $N$.

The decisive check has two parts. First, $k$ must grow much more slowly than $N$ on the 51–100 stratum. If it does not, the many-piece problem does not decompose and the approach fails regardless of soundness. Second, the fraction of test objects whose true assembly falls outside slack $z$ must stay small at the chosen $z$. If the scoring model often ranks wrong assemblies far above true ones, certified pruning cannot help, and the bottleneck is the scores rather than the search.