Swap-One Credit Assignment for Learned RANSAC Sampling with Black-Box Uncalibrated Solvers

Estimating how a camera moved between two photos is a guessing game. Software draws a handful of point matches at random and solves a small algebra problem to get a candidate motion. It keeps the candidate that agrees with the most other matches. This loop is RANSAC (random sample consensus), and the small algebra problem is a minimal solver, meaning one that uses the fewest matches the geometry allows. A neural network can learn which matches to draw. It is trained with policy gradients, the trial-and-error estimator from reinforcement learning, because the draw is discrete and the solver cannot be differentiated. That training is notoriously noisy.

This note identifies a specific cause of the noise. The reward depends on the drawn set as a whole, and a single bad match ruins the set. Under the standard estimator, every good match in that set is then blamed along with the bad one. We propose giving each slot in the drawn set its own baseline. To do this, swap that one match for a fresh draw, re-run the solver, and use the change in outcome as that match's credit. Minimal solvers are cheap black boxes, so these extra solver calls are affordable. The estimator stays unbiased. It also works with the newest solvers for uncalibrated cameras (unknown focal length, monocular depth cues), which nobody has made differentiable.

Core Claim

Let a minimal set $S=(x_1,\dots,x_k)$ be $k$ matches drawn independently from a learned distribution $p_\theta$ over the image pair's matches. Let $L(S)$ be the loss of the RANSAC run that contains the hypothesis built from $S$. We use the estimator

$$ \hat g=\sum_{i=1}^{k}\nabla_\theta \log p_\theta(x_i)\,\bigl(L(S)-b_i\bigr),\qquad b_i=\frac{1}{M}\sum_{m=1}^{M}L\bigl(S_{-i}\cup\{x'_m\}\bigr),\; x'_m\sim p_\theta, $$

where $S_{-i}$ is the set with slot $i$ removed and $x'_m$ are $M$ fresh replacement draws. The baseline $b_i$ depends only on the other $k-1$ matches and on draws independent of $x_i$. It is therefore a valid control variate for slot $i$, so the estimator stays unbiased, by the same argument that makes leave-one-out baselines unbiased.

The baseline also removes most of the noise in the sampler's gradient. If a set fails because of one outlier, swapping out an inlier still fails, so that inlier gets near-zero advantage. Swapping out the outlier often succeeds, so the outlier gets a large, correctly signed advantage.

We predict the gain over set-level baselines grows with $k$. There should be none at $k=1$ (the single-affine-correspondence solver), and a large gain for the 6–7 point uncalibrated solvers. This prediction is falsifiable and is our central check.

A structural fact makes this cheap at the level of a whole RANSAC run. Swapping a point changes only one hypothesis. The run's output therefore changes only if the new hypothesis outscores the current winner, or if the swapped hypothesis was the winner. Each counterfactual costs one solver call plus one consensus scoring, with no re-run of RANSAC.

Relation to Prior Work

Three papers supply the setup we build on. DSAC made hypothesis selection probabilistic and trained it with the log-derivative trick. Its minimal sets are still drawn uniformly. NG-RANSAC learned the sampling distribution itself with REINFORCE, using calibrated 5-point and 7-point solvers. It reported needing as few as 10 hypotheses where standard methods need thousands. Both papers motivate this work: the research file records that NG-RANSAC's baselines are elementary and that, in the combined NG-DSAC system, gradients had to be blocked to avoid collapse. That is the variance problem we target. Our estimator differs from both in what it assigns credit to: individual slots of a set, not the set or the run.

The obvious import from language-model RL is a cohort baseline. RLOO centers each sampled completion's reward against the mean of the others. LOOP does the same for diffusion trajectories. Pinto et al. use a two-sample baseline to tune vision models on non-differentiable metrics. All of these treat the sampled output as one indivisible action.

The research file flags "action granularity" as an open limitation of these sequence-level baselines, and the optimal token baseline work attacks the per-step version of it for long LLM rollouts. RANSAC minimal sets are the ideal case for fixing granularity. The action factors exactly into $k$ independent draws, and the environment, which here is the solver, can be queried counterfactually at almost no cost. That is not possible for an LLM rollout. Set-level leave-one-out applied to RANSAC is the closest unpublished idea. We treat it as a baseline, not as our contribution.

The constraining work is ∇-RANSAC and its generalized version. They avoid sampling variance altogether with a Gumbel-Softmax relaxation, a smooth stand-in for discrete sampling, and by writing the solvers in PyTorch autograd. They reach AUC@5° of 0.41 for essential matrices on PhotoTourism. That is strong evidence that the plain policy gradient is not competitive. Our claim is narrower. Their route requires a differentiable solver, and the uncalibrated solvers we target do not have one.

The application regime comes from the uncalibrated-solver literature. The relative-depth fundamental matrix solvers (4p4d, 4p3d, 3p3d) combine point matches with depth ratios from SIFT scale or Depth Anything and run in 1.5–7 ms. They degenerate under pure rotation. The 1AC+D solver combines one affine correspondence with monocular depth. It degenerates on fronto-parallel planes. Both use uniform or Graph-Cut RANSAC sampling, a hand-designed sampler that favors spatially coherent inliers. Neither has a learned sampler.

Research Program

We will build a sampler network in the style of NG-RANSAC. It takes per-match inputs: coordinates, matcher confidence, SIFT scale ratio, monocular depth and its local variance, and affine patch parameters where available. It outputs $p_\theta$.

The solvers are called as compiled black boxes: the 5-point essential solver, the 7-point fundamental solver, the 3p3d and 4p3d relative-depth solvers, and 1AC+D/1AC+1PC from the semicalibrated_1AC_D code.

Training uses ground-truth pose error of the RANSAC output as $L$. A second, self-supervised variant uses negative inlier count. For that variant we add a check described below, because unknown focal length opens a route to reward hacking. A wrong focal length can flatten the epipolar geometry and inflate inlier counts. This mirrors the metric gaming that Pinto et al. documented for captioning.

Hypotheses far from winning give zero swap effect and hence no gradient. That is correct credit, but it may make the learning signal sparse. We will measure this and, if needed, add each hypothesis's own consensus score as a dense auxiliary term with the same swap baseline. Replacement draws are made with replacement, which keeps the factorization exact. Duplicate draws simply produce failed hypotheses.

Baselines

The do-nothing reference is uniform-sampling RANSAC with each solver. Graph-Cut RANSAC with the same solver is the strong hand-designed reference. For 1AC+D on PhotoTourism, Hruby et al. report a mean pose error of 14.6°, against 17.7° for the 6-point and 19.5° for the 7-point solver. A learned sampler must improve on 14.6° at equal hypothesis budget to count.

The original NG-RANSAC estimator, with its simple baseline, is the method we aim to replace. It is run with the same network, data, and hypothesis budget. We expect our method to train stably without the gradient blocking NG-DSAC needed, and to reach a lower final error.

The most important baseline is set-level leave-one-out. It uses a cohort of independent minimal sets, each centered against the mean loss of the others. We run it at matched solver calls: our $kM$ extra calls per set are given to it as extra cohort members. Tuning budgets are equal, with the same learning-rate sweep and seeds. This baseline isolates the key ingredient, per-slot counterfactual credit, from simply spending more solver calls on variance reduction. Beating it means lower measured gradient variance at equal calls, and better AUC on the $k\ge3$ solvers.

The strongest existing method is ∇-RANSAC. For the 5-point essential task its reported PhotoTourism AUC@5° is 0.41 (Generalized Differentiable RANSAC), and we run its released code on the same splits and matcher. Matching it there would show that a black-box policy gradient is viable at all. For uncalibrated solvers it cannot run natively. We therefore use it as a transfer baseline: train its sampler with a differentiable 7-point F surrogate, then sample for 4p3d or 3p3d at test time.

For the relative-depth solvers, the research file gives no AUC figure for PhotoTourism, KITTI, or ScanNet. No reported result was found on Lacuna for those configurations, so we will produce them ourselves under the uniform and Graph-Cut baselines.

Finally, a learned critic is a further variance-reduction baseline. It is a value network that predicts expected run loss from global pair features.

Why not just…?

Why not just use ∇-RANSAC's Gumbel-Softmax relaxation? Where the solver is differentiable, this is a real threat. On 5-point essential estimation it may simply win, and we will report that honestly. Its limit is that gradients must pass through root-finding. For the elimination-based 3p3d/4p3d solvers and the 1AC+D solver with its unknown scale, no differentiable implementation exists in the file. Companion-matrix eigenvalue gradients become unstable near repeated roots.

The real question is whether a sampler trained through a differentiable surrogate transfers to the uncalibrated solver. The transfer baseline settles this. If it matches our method on 4p3d, the black-box argument loses most of its force. We expect it to fail on solver-specific degeneracies: pure rotation for the depth solvers, fronto-parallel planes for 1AC+D. The surrogate never experiences those failures.

Why not just use a set-level leave-one-out cohort, as RLOO does for language models? This is the obvious idea, and for small $k$ it should be as good as ours. At $k=1$ (1AC+D) the two estimators are identical. Our claim stands or falls on the matched-solver-call comparison as $k$ grows from 3 to 5 to 7. If the per-slot variance advantage does not widen with $k$, the contribution is not real.

Why not just train a critic? Ahmadian et al. found critic-based PPO outperformed by leave-one-out in language models, citing lag and tuning cost. The issue is sharper here. A critic sees the image pair, not the specific $k-1$ partners of a slot, so it cannot represent "this inlier was unlucky to be paired with an outlier." We include the critic baseline to show this directly through measured gradient variance.

Why not just rely on Graph-Cut RANSAC or matcher-confidence ordering? These heuristics are fast and strong, and 1AC+D already uses Graph-Cut RANSAC. They cannot know which configurations a particular solver finds degenerate. NG-RANSAC showed that learned guidance beats ratio-test side information. If the learned sampler gives no gain over Graph-Cut RANSAC at equal wall-clock time, we will say so.

Proposed Experiments and Decisive Checks

The first experiment directly measures gradient variance. Freeze $\theta$ at several training checkpoints. Draw 200 independent gradient estimates per estimator at matched solver calls, and record variance as a function of $k$ (1, 3, 4, 5, 7) and of outlier ratio. This is controlled by perturbing PhotoTourism matches. The decisive prediction is that the variance ratio between set-level and per-slot estimators is near 1 at $k=1$ and grows with $k$ and with outlier ratio.

Second, we train end to end on PhotoTourism, KITTI, and ScanNet. We report AUC@5°/10°/20° and mean pose error for each solver, at hypothesis budgets of 10, 100, and 1000. We also report training wall-clock time, including counterfactual solver calls.

Third, we run a degeneracy analysis. On KITTI segments with near-pure rotation, and on ScanNet frames dominated by planes, we measure the fraction of sampled sets that the solver rejects or that yield degenerate hypotheses. We compare our sampler against uniform sampling and against the ∇-RANSAC transfer sampler. This tests whether swap-based credit teaches the sampler solver-specific avoidance.

Fourth, for the self-supervised inlier-count reward under unknown focal length, we check for hacking. We track the gap between rising inlier counts and ground-truth pose error and focal-length error. If the gap widens, the self-supervised variant is reported as failing, not tuned away.

Finally, we remove NG-DSAC-style gradient blocking and train the sampler jointly with the matcher's confidence head. If this trains stably under our estimator but collapses under the set-level baseline, that is direct evidence that the original instability came from credit assignment, not from sampling itself.