One-Pass Minimal-Set Proposals for Extreme-Outlier Registration

Many geometry problems in robotics and vision, such as aligning two 3D scans, recover a transformation from a list of candidate point matches, most of which are wrong. The standard tool is RANSAC (random sample consensus). It repeatedly draws a tiny random subset of matches, fits a model to it, and counts how many other matches agree. When 99% of matches are wrong, the number of draws needed to hit one clean subset grows into the tens of thousands or millions. In effect, RANSAC is an iterative refinement loop whose length grows exponentially with the share of bad matches.

Learned samplers shorten this loop. DiffSAC uses a diffusion model, a generator that turns random noise into samples through many small denoising steps, to propose about 20 subsets instead of more than 10,000. It still runs a multi-step denoising process for every input, it is trained separately for each task, and the file reports it at no more than 80% injected outliers.

This note asks one question. Can a single forward pass, trained only on procedurally randomized synthetic match sets, propose a small batch of jointly diverse candidate subsets that matches what thousands of RANSAC draws achieve at 95–99% outliers on real scans?

The word "jointly" carries the idea. A model that scores each match independently ("how likely is this match correct?") breaks down in exactly the hard cases: repetitive or symmetric scenes. There, several internally consistent but mutually incompatible groups of matches exist. Independent sampling from per-match scores then mixes members of different groups and produces contaminated subsets. Iterative generative sampling avoids this by modeling which matches go together, and that is what costs latency. We propose to keep the joint structure and drop the iterations. The training data would come from a synthetic generator that deliberately builds these structured-outlier traps, because real datasets with ground-truth inlier labels at 99% outliers barely exist.

Core Claim

A permutation-invariant network can be trained on domain-randomized synthetic correspondence problems to output $K$ minimal subsets in one pass. Each subset is a set of three matches, enough to fix a rigid 3D transform. The network would be trained with a set-level objective that rewards covering distinct consistent groups. We claim this network transfers zero-shot to real registration benchmarks (3DMatch, KITTI) and preserves most of the accuracy of many-draw consensus at a fixed latency of tens of milliseconds.

The novelty is not "distill a diffusion sampler." The novelty is three choices together. First, the proposal set is treated as the object to be predicted, so diversity across the batch is part of the loss. Second, the synthetic generator is built around the outlier structures that defeat both distance invariants and per-match classifiers. Third, every method is measured against a single exponential cost curve, so the claimed savings can be checked directly.

To make that cost curve explicit, define the proposal recall $R_K$ as the probability that at least one of the $K$ proposed subsets contains only correct matches. The effective RANSAC budget of a proposer is the number of uniform random draws $T_{\text{eff}}$ that would reach the same recall at outlier ratio $\gamma$ with subset size $k$:

$$T_{\text{eff}} = \frac{\ln(1 - R_K)}{\ln\left(1 - (1-\gamma)^k\right)}$$

This follows from the standard RANSAC iteration bound in the file, with the target confidence replaced by the observed recall. A proposer that reaches $R_K = 0.9$ with $K = 20$ at $\gamma = 0.99$ and $k = 3$ is doing the work of roughly 2.3 million random draws. Reporting $T_{\text{eff}}$ against measured milliseconds puts classical, graph-based and learned methods on one axis.

Where This Sits Relative to Prior Work

The proposal draws on four strands of prior work, each in a different role.

Learned samplers and inlier predictors motivate it. DiffSAC shows that generative sampling of a per-match confidence vector cuts hypothesis evaluations to $\kappa = 20$, with a 33 ms total pipeline. It keeps the iterative reverse process, is retrained per task, and is reported only up to 80% outliers. PointDSC embeds pairwise distance consistency into a learned layer and then finds inliers by power iteration on a compatibility graph. It reaches 93.28% registration recall on 3DMatch in about 0.09 s and transfers from indoor training to KITTI. It is supervised on real labels and builds an $O(N^2)$ graph.

Adaptive Reordering Sampler with Neurally Guided MAGSAC updates per-match inlier probabilities after failed draws. It is the closest "marginal-score" competitor and it is still sequential. We differ from all three: we predict the batch of subsets directly, we train only on synthetic data, and we target the 95–99% regime.

Invariant and graph methods set the bar and constrain the design. TEASER++ uses pairwise translation- and rotation-invariant measurements with maximum-clique pruning and a certifiable solver. It handles 99% outliers in milliseconds on standard problem sizes. ROBIN replaces the clique with a max $k$-core. PCR-99 uses triplet scale consistency and records zero large errors over 5,500 Bunny trials at 99% outliers.

These methods tell us two things. Pairwise distance consistency must be an input to our network, because it is the physical law that makes transfer possible. And the network must avoid building the full $N^2$ graph, or it inherits their scaling. Our model therefore computes distance-consistency features only within local neighborhoods and against a small set of sampled anchor matches, roughly $O(N \cdot m)$ for $m$ anchors.

Synthetic-to-real work supplies the training recipe. Domain Randomization for Scene-Specific Car Detection and Pose Estimation shows that aggressive, unrealistic randomization pushes networks toward invariant geometry. Diversity is Definitely Needed shows that diversity beats realism in synthetic training data. Deep Reinforcement Learning for Subpixel Neural Tracking gets about 84% zero-shot coverage on real microscopy from noisy synthetic splines. We apply this logic to match sets rather than images, randomizing what matters for consensus: outlier ratio, noise model, density, overlap, and above all outlier structure.

Single-pass distillation work supplies a method we test but do not assume. DCFold collapses AlphaFold3's recycling and diffusion into one pass at 15× average speed. It also reports that consistency training concentrates the output distribution. Trajectory Consistency Distillation reaches 4-step FID 12.68 on COCO2017, against 15.03 for latent consistency models.

DCFold's concentration finding cuts directly against naive distillation for our purpose. A sampler whose $K$ outputs collapse to the same group of matches has $R_K$ no better than $K = 1$. This is why the core objective is set-level coverage, and why plain consistency distillation of a DiffSAC-style teacher appears only as a competing variant.

Research Program

Synthetic generator. The generator samples a source shape: a ModelNet40 CAD model, a procedural room made of planes and boxes, or a random point cloud. It applies a random rigid transform, crops for partial overlap, resamples density, and adds heteroscedastic noise. It then builds a correspondence set at an outlier ratio drawn up to 0.995.

Outliers come from a mixture of five types. Uniform outliers are the easy case. Clustered outliers simulate bad descriptor regions. Symmetric outliers are matches that are consistent under a symmetry of the shape. Repetitive outliers come from duplicated substructures, which create competing consistent groups. Decoy-transform outliers are a second, smaller set that is consistent under a different rigid motion.

The last three types are the point of the generator. They produce several internally consistent groups, so per-match scores are ambiguous and pairwise invariants admit spurious cliques. This is the documented failure mode of invariant methods in repetitive geometry. Ground-truth inlier labels come for free.

Proposer. A transformer over matches takes each match's coordinates in both clouds plus its local and anchor-based distance-consistency features. It has $K$ learned query slots. Each slot outputs a soft selection over matches, and a subset is read off as the top three selections, with a diversity penalty across slots.

Training uses a winner-take-all, set-coverage loss. For each training problem, the true inlier group and any decoy groups are known. The loss rewards the best-matching slot for selecting a clean triple from the true group, and it penalizes slots that duplicate one another's selections. A small auxiliary head predicts the per-match inlier score, which serves as the "marginal" ablation.

Verification. All $K$ hypotheses are scored by truncated inlier count in $O(KN)$. The winner is refined on its inliers. Optionally, the winner's inlier set goes to TEASER++'s certifier, so the output carries the same a posteriori optimality check that invariant methods offer. This keeps the learned part as a proposer only.

Analysis. For every method we measure $R_K$ (or its equivalent), $T_{\text{eff}}$, wall-clock latency, and final registration accuracy, as functions of $\gamma$ and $N$ and broken down by outlier type. Separating the synthetic results by outlier type tells us why a method wins or loses, not just whether it does.

Baselines

The naive reference is plain RANSAC with three-point subsets at the same latency budget as our method, about 30 ms. We also run it at its theoretical iteration count, to show what the budget cap costs. It sets the "do nothing" floor and anchors the $T_{\text{eff}}$ curve.

The strongest existing invariant method is TEASER++, run with its released solver on identical FPFH and FCGF correspondence sets. The file reports "up to a 98.6% success rate" for TEASER on 3DMatch and millisecond runtimes on standard problem sizes. We also run PCR-99 on the Stanford Bunny protocol, where it reports zero large errors in 5,500 runs at 99% outliers.

To beat TEASER++ we do not need higher success on 3DMatch at moderate $N$. We need one of two things. Either we match its success while staying under a fixed latency as $N$ grows past $10^4$, where its pairwise graph becomes a bottleneck. Or we exceed it on the repetitive and symmetric subsets, where spurious cliques are expected. If it wins on both, the proposal has failed.

The strongest learned baseline is PointDSC, which reports 93.28% registration recall on 3DMatch in about 0.09 s. We run it with its released weights trained on real 3DMatch labels. We also retrain it on our synthetic generator with the same number of gradient steps and the same tuning budget as our model. The two versions separate "our architecture is better" from "our data is better." Beating it means matching 93.28% recall zero-shot from synthetic training at lower latency, or exceeding it at 95–99% injected outliers.

DiffSAC is reimplemented for 3D registration with the same transformer backbone and trained on the same synthetic data, at its default solver steps and at one, two, and four steps. The file gives no reported result on 3DMatch or KITTI registration for DiffSAC, only its 33 ms pipeline time and mAA gains on two-view tasks.

The ablation that isolates our key ingredient replaces the set-level head with the auxiliary per-match score head. It then draws $K$ subsets by weighted sampling, in the manner of neurally guided MAGSAC. A second ablation removes the symmetric, repetitive and decoy outliers from the generator. A third replaces our objective with consistency distillation of the DiffSAC teacher.

Why not just…?

Why not just run DiffSAC with one or two solver steps? This is the cheapest route to the same latency and a real threat. If a one-step DiffSAC matches our $R_K$ at $\gamma = 0.99$, the set-coverage objective adds nothing and we will say so. Our reason to expect a gap is DCFold's observation that collapsing steps concentrates the output distribution. For a proposer, concentration means duplicate subsets. The step-count sweep in the DiffSAC baseline, reported per outlier type, settles this directly.

Why not just predict a per-match inlier probability and sample from it? This is what the marginal-head ablation tests, and on uniform outliers we expect it to do about as well as our method. The argument against it concerns structured outliers. When two consistent groups exist, the per-match marginals are high for both, and independent draws mix them. If the marginal ablation matches us on the repetitive and decoy subsets and on KITTI, the joint-set idea is unnecessary.

Why not just use TEASER++ or maximum-clique pruning with no learning? On many standard problems this is probably the right answer: the file records 98.6% success on 3DMatch and 99% outlier tolerance. Our case rests on two regimes. The first is quadratic graph cost at large $N$, which we test with a sweep from $10^3$ to $10^5$ correspondences under a fixed latency cap. The second is spurious cliques in self-similar geometry, where FPFH alone reaches only 0.7% LiDAR recall in Generative Point Cloud Registration. If TEASER++ stays within budget and accuracy in both regimes, the learned proposer is not worth building.

Why not just train on real 3DMatch labels? Real labels exist at moderate outlier ratios, and PointDSC uses them well. They rarely contain controlled 99% outlier sets or labeled decoy groups. The real-label versus synthetic-retrain comparison of PointDSC, plus our model fine-tuned on real 3DMatch, shows whether synthetic training costs accuracy at standard outlier ratios. It also shows whether it buys accuracy at extreme ones.

Proposed Experiments

The first decisive check is synthetic. On held-out generator problems and on the Stanford Bunny protocol of PCR-99, we plot $R_{20}$ and $T_{\text{eff}}$ against $\gamma \in [0.9, 0.995]$, separately for each outlier type. The prediction is that our method and multi-step DiffSAC beat the marginal-head ablation on the repetitive, symmetric and decoy types but not on uniform outliers. A gap that appears only on structured outliers is the signature of the claimed mechanism. No gap falsifies it.

The second check is zero-shot transfer. We take 3DMatch with FPFH and FCGF correspondences and KITTI LiDAR pairs, without fine-tuning. We report registration recall and latency against PointDSC's 93.28% and TEASER++'s 98.6%. We also downsample true inliers to inject 95% and 99% outlier ratios on the real pairs, and report the KITTI low-inlier-ratio regime where PointDSC is described as robust at 1–3% inliers. ScanNet pairs provide a self-similar indoor stress test.

The third check is scaling. Correspondence counts run from $10^3$ to $10^5$ under a fixed 50 ms budget, with latency and accuracy reported for every method. This directly tests whether avoiding the full pairwise graph matters in practice.

The project succeeds if a single 30-ms forward pass trained only on synthetic data reaches $T_{\text{eff}}$ in the millions at $\gamma = 0.99$ on real scans. It must also match the stronger of PointDSC and TEASER++ on standard 3DMatch and beat both on structured-outlier and large-$N$ conditions. It fails cleanly if the one-step DiffSAC or marginal-score ablation closes the gap.