Do Optimality Certificates Earn Their Latency in a Live Odometry Loop?

Many robot perception steps reduce to finding the best rotation and translation that explain a set of noisy point matches. One example is estimating how a camera moved between two frames. Fast local solvers find an answer in milliseconds but can silently return a wrong one. Certifiable solvers instead turn the problem into a larger convex one, a semidefinite program (SDP: an optimization over positive semidefinite matrices). They then return a proof, called a certificate, that the answer is globally optimal. The cost is speed. Robust certifiable solvers take about a second per relative-pose solve and seconds to minutes on harder problems, and they have been tested almost entirely on synthetic noise or static datasets.

This note proposes two things. The first is a tiered relative-pose solver built for a camera-frame time budget. It runs a fast robust heuristic, then a cheap certificate check, and escalates to a full SDP only when the check fails. The second, and the real contribution, is an empirical audit on real visual and visual-inertial sequences. The audit asks whether a passed or failed certificate tells us anything about tracking failure that simple health checks, such as inlier count or residual size, do not already tell us. If certificates carry no extra predictive signal on real data, that is a useful negative result for the field. If they do, the tiered design shows how to pay for them within a frame budget.

Core Claim

The certifiable-perception literature has made solvers much faster, but it has never measured the thing that justifies them. That thing is how often, on real sensor streams with real artifacts, the fast heuristic is actually wrong and the certificate is the only thing that notices. We claim three things can be established for robust two-view relative pose on frame-rate sequences. First, how often the cheap tier fails to certify. Second, whether certificate failure predicts large pose error better than standard health checks. Third, how certificate pass rates degrade under controlled timing and rolling-shutter corruption.

The closest prior work does not answer this. TEASER pairs a fast heuristic, Graduated Non-Convexity (GNC: gradually sharpening a smoothed robust cost), with a certificate. It does so for pairwise 3D point-cloud registration evaluated scan by scan, not inside a running odometry loop. STRIDE also combines local search with an SDP. Its authors state its seconds-to-minutes solve times are not yet suited to real-time loops.

Research Program

The method side reuses known pieces and assembles them for one setting: robust non-minimal relative pose from many 2D-2D matches.

Tier 0: candidate. GNC on a truncated least squares cost, which caps each match's penalty so outliers stop pulling the solution. The output is a candidate pose and a set of inliers.

Tier 1: cheap check. We check the inlier-conditioned problem using the formulation of Briales et al., the redundant-constraint relaxation with near-zero duality gap. Instead of solving that SDP, we recover the Lagrange multipliers in closed form from the stationarity conditions at the candidate. We then test whether the resulting small matrix is positive semidefinite, which costs a least-squares solve plus one eigenvalue computation. We will also test the bearing-vector cheirality constraints of C2P. C2P removes the separate disambiguation step that costs time in earlier pipelines, but it assumes mostly-inlier input. Using it only after Tier 0 has fixed the inliers sidesteps that assumption.

The Tier 1 certificate is weaker than a full robust certificate. It says the pose is optimal given the chosen inliers, not that the inlier choice itself is optimal. We report the two separately and never conflate them.

Tier 2: robust certificate under a budget. A Douglas-Rachford splitting certificate, in the style TEASER++ uses for rotation, runs on the full truncated-least-squares relaxation. It stops at the frame deadline and reports its current suboptimality bound.

Tier 3: asynchronous fallback. STRIDE, or the triangulation-style relaxations of Semidefinite Relaxations for Robust Multiview Triangulation, runs on frames whose certificate failed, off the critical path. This gives a ground-truth optimality label after the fact.

The analysis side is the audit. For every frame pair we log five things: tier outcomes, Tier 2 bound, pose error against ground truth, wall-clock time per tier, and a set of standard health signals. The health signals are inlier ratio, median residual, condition number of the Gauss-Newton Hessian, and parallax. We also log whether the Tier 3 SDP later found a strictly better solution.

Baselines

Naive reference. RANSAC followed by Levenberg-Marquardt refinement, the standard production pipeline. It is run with the same matches, the same truncation threshold as its inlier threshold, and its iteration count tuned on a held-out sequence to meet the same frame budget. It defines the latency floor and the error rate the certificate must explain. The file reports that SDP triangulation relaxations find lower-cost points than RANSAC under high noise (Semidefinite Relaxations for Robust Multiview Triangulation). That evidence is for triangulation, not two-view pose on real streams.

Strongest certifiable competitor. The full SDP relaxation of Briales et al., solved per frame with an interior-point solver. On TUM RGB-D it reports an optimality gap "consistently near 10^-10" at "~1 second per solve." It defines the accuracy and certification ceiling. Our tiered solver beats it if it matches its certified-frame rate and pose error while meeting the frame budget on a large majority of frames. We run it on identical inlier sets so the comparison isolates solver cost.

Fastest certifiable reference. TEASER++-style GNC plus splitting certification is the strongest existing fast certified design. Its reported numbers, "<10ms" and a "98.6% success rate," come from 3DMatch registration, and the file has no reported result for two-view relative pose on TUM VI or ETH3D. We reimplement its two-stage logic for relative pose; this is our Tier 0 plus Tier 2 without Tier 1.

Ablations. Tier 1 removed (always run Tier 2) and Tier 2 removed (Tier 1 only). Together these isolate whether the cheap inlier-conditioned check is what makes the budget feasible.

Why not just…?

Why not just use RANSAC plus local refinement and monitor inlier count? This is the real threat, and the proposal is built around it. If inlier ratio and residual statistics predict large pose errors as well as certificate failure does, then certificates add latency without information in this regime. The decisive experiment compares the two directly. We measure the area under the ROC curve (AUROC) for detecting frames whose rotation error exceeds a threshold. Contenders are certificate failure alone, the health signals alone (fit with logistic regression on held-out sequences), and both combined. A negligible gain from adding the certificate means we report that outcome as the finding.

Why not just run GNC without any certificate? GNC is a heuristic with no optimality guarantee and can settle in poor minima at high outlier rates (Certifiable Outlier-Robust Geometric Perception). But on real two-view streams outliers may rarely be extreme, so GNC may almost never fail. The Tier 3 labels measure that failure rate directly. If the rate is near zero, the certificate is insurance against a rare event, and we quantify its per-frame price.

Why not just run the full SDP asynchronously and accept the delay? For keyframe-level mapping this may suffice; BAD SLAM already spends about 370 ms per keyframe. For frame-to-frame tracking, a certificate that arrives a second late cannot stop a bad pose from entering the filter. We measure how many tracking failures in the trajectory error happen before a late certificate would have arrived.

Why not just use a learned pose regressor? PCRNet is fast at 1.89 ms per pass, but its authors list unseen categories and occlusion as open problems, and it offers no error bound. It does not address the question here, which is whether bounds are informative. We therefore exclude it from the main comparison.

Proposed Experiments

The main data are the TUM VI benchmark, TUM RGB-D, and ETH3D, the latter two as used by BAD SLAM. They provide motion-capture or reference ground truth. Two-view problems come from consecutive frames and from keyframe pairs, with standard feature matches. For a controlled hardware study we start from ETH3D's synchronized global-shutter RGB-D images and apply two corruptions. The first is a frame-timestamp offset, which mislabels which ground-truth pose belongs to a frame and acts like a camera-to-IMU synchronization error. The second is a synthetic row-wise rolling-shutter warp. These address the artifacts that Simultaneous Time Synchronization and Mutual Localization shows corrupt relative pose. We also sweep injected outlier rates on real matches to locate where Tier 1 stops certifying. This gives an empirical, real-noise counterpart to the order-versus-tightness gap noted in Estimation Contracts.

We report six metrics: per-frame wall-clock latency distribution against the camera frame period, certified-frame rate per tier, Tier 2 suboptimality bound, rotation and translation error, failure-detection AUROC, and trajectory error when the tiered solver feeds a simple odometry chain. As a downstream reference point, BASALT's reported "1.20m" trajectory error on a 918 m outdoor TUM VI loop places our odometry chain in context. We do not expect to beat it, since our chain is not a full visual-inertial system.

The decisive checks are three. First, does the tiered solver hold the frame budget at the 95th-percentile latency while certifying as many frames as the one-second SDP? Second, does certificate failure raise failure-detection AUROC above the health-signal model? Third, under timing and rolling-shutter corruption, do certificates keep passing on frames with large error? That last outcome would be the most important negative finding: it would mean that "certified" on real hardware describes only the internal consistency of a model that the sensor has already broken.