{"id":"38088c0c-6704-484f-b883-4617104c15dd","arxiv_id":"2507.01439","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"TurboReg estimates 3D transformations from fixed-size three-match cliques in a tightly constrained compatibility graph, found by a linear-time pivot-guided search, matching or beating maximal clique methods at far higher speed.","lead":"This paper introduces TurboReg, a point cloud registration estimator that replaces expensive maximal clique search with a fast pivot-guided search over small three-match cliques. It reports state-of-the-art registration recall on indoor and outdoor benchmarks while running much faster than prior clique-based methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"App. A.1's claim that a stringent threshold makes a 3-clique as stable as a maximal clique rests on an invalid τ→0 limit: the compatibility constraint does not force the pairwise noise difference to zero, so the core stability premise is unproven.","rationale":"The reader's weakest-assumption analysis identified the same load-bearing point: the stability equivalence between a 3-clique and a large clique is the essential condition for the central claim, and it is supported only by a heuristic argument and a single empirical comparison. My stress-test sharpens this into a specific mathematical error in App. A.1: the τ→0 limit does not force the effective noise to zero, because the compatibility constraint restricts e_ij to a sphere, not to the origin. This means the paper has not established that three matches are sufficient for stable transformation estimation in general, independent of the empirical evidence. The empirical results on 3DMatch, 3DLoMatch, and KITTI with multiple descriptors are broad and the speed advantage is real, so I do not recommend rejection; however, the theory should be corrected or weakened, and the synthetic test would determine whether the stability compensation actually holds. This is consistent with the reader's CONDITIONAL verdict, so no change is needed. I agree with the reader that this is the primary concern; secondary issues (CPU/GPU speed mixing, hyperparameter tuning) are important but less central to the core claim.","tokens_in":24301,"tokens_out":13400,"duration_ms":156655,"concrete_test":"Run a synthetic experiment with a known rigid transformation and injected zero-mean Gaussian noise of standard deviation σ on target keypoints (e.g., σ = 0.1, 0.5, 1.0 times the point-cloud resolution), plus random outliers. Build the compatibility graph at τ = 0.5σ, 0.25σ, 0.1σ; sample all 3-cliques and all 10-cliques; estimate the Kabsch transformation for each; and compare the median and variance of rotation/translation error relative to the ground truth. If the 3-clique error does not decrease toward the 10-clique error as τ shrinks, the stability-compensation premise in App. A.1 is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that three carefully selected matches are sufficient depends on the assertion in App. A.1 that pairwise compatibility-induced stability compensates for the loss of data-scaling stability. The argument hinges on the limit τ→0 in Eq. (11): the paper states that the constraint | ||d_ij+e_ij|| - ||d_ij|| | ≤ τ forces e_ij→0, hence r_i→0 and σ_eff→0. This is geometrically false. For τ=0, the constraint set is the sphere {e_ij : ||d_ij+e_ij|| = ||d_ij||}, which has codimension 1 and contains vectors of norm up to 2||d_ij|| (e.g., e_ij = -2d_ij). A single pairwise constraint does not restrict the direction perpendicular to d_ij, and even with three matches the degrees of freedom are not eliminated: the three points can be jointly rotated about the triangle, producing non-zero e_ij while preserving all pairwise distances. Consequently, the inference that the effective noise variance σ_eff vanishes is invalid. All that remains is the heuristic comparison in App. A.2 (3-clique vs 10-clique on 3DMatch+FPFH), which is confounded: at small τ both clique sizes are drawn from tightly compatible inlier sets, and the test does not vary noise level, scene geometry, or descriptor. Thus the paper's theoretical foundation for Definition 1 is unsupported, and the claim that 3-cliques provide stable transformations comparable to maximal cliques is an open question.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TurboReg, a correspondence-based point cloud registration estimator. Instead of searching for maximal cliques in a compatibility graph, TurboReg defines a TurboClique as a 3-clique in a highly constrained compatibility graph, and finds these cliques with a pivot-guided search (PGS) that uses the K1 highest-weighted SC2 edges as pivots and keeps the top-K2 third nodes per pivot. An ordered variant of the SC2 graph (O2Graph) is introduced to avoid duplicate TurboClique detections, and each candidate triple is scored by Kabsch-based inlier count. Experiments on 3DMatch, 3DLoMatch, and KITTI with FPFH, FCGF, and Predator descriptors report state-of-the-art or competitive registration recall with large reported speedups, and code is released.","tokens_in":24666,"tokens_out":4573,"duration_ms":51655,"significance":"If the empirical results hold, TurboReg is a practically valuable contribution: the fixed-size hypothesis structure is GPU-friendly, the benchmark coverage is broad, and the paper includes a detailed ablation study plus released code. The paper also correctly identifies a real limitation of maximal-clique enumeration and demonstrates a credible alternative. However, the theoretical stability argument that underpins the TurboClique definition is not valid as stated, and the headline speedup is based on an asymmetric GPU-vs-CPU comparison. The significance is therefore conditional on revising those claims.","major_comments":[{"comment":"The argument that the constraint |∥d_ij+e_ij∥−∥d_ij∥| ≤ τ forces e_ij→0 as τ→0 is geometrically false. The set {e_ij : ∥d_ij+e_ij∥=∥d_ij∥} is a sphere of codimension 1 and contains vectors of norm up to 2∥d_ij∥, so a single pairwise compatibility constraint does not restrict the component of e_ij perpendicular to d_ij. Consequently the claimed reduction of the effective noise variance to zero, σ_eff→0, is unsupported, and the central premise that a stringent τ lets a 3-clique match the stability of a maximal clique is not established by the provided derivation. The supporting experiment in App. A.2 compares 3-cliques with 10-cliques only on 3DMatch+FPFH and does not vary noise level, scene geometry, or descriptor, so it cannot carry that weight. Please replace the limit argument with a rigorous analysis, or explicitly reframe the stability claim as a heuristic validated only empirically.","section":"App. A.1, Eq. (11)"},{"comment":"The abstract's headline claim that TurboReg (1K) is 208.22× faster than 3DMAC compares TurboReg's GPU time (64.55 FPS) against 3DMAC's CPU time (0.31 FPS). The same table reports TurboReg's CPU implementation at 2.73 FPS, i.e. an 8.8× CPU-to-CPU speedup. Since 3DMAC has no GPU implementation, the GPU-vs-CPU comparison should be clearly labeled as such, and the abstract and contributions should not present a GPU-to-CPU ratio as the primary speed comparison without this caveat.","section":"Table 1 and Sec. 4.1.2"},{"comment":"The hyperparameters τ, K1, and K2 are tuned on the same benchmarks on which the final registration recall is reported. Section 4.1.1 states that τ is 'adjusted based on empirical evaluation' and the ablation summary recommends fine-tuning to 1.2 cm for 3DMatch, while K1 is set to 1K/2K for indoor datasets and 0.25K/0.5K for KITTI based on the per-dataset ablations in Table 5. This selection procedure biases the reported state-of-the-art recall, since the test set is used for parameter choice. Please add a validation split or a sensitivity analysis that shows the method's performance across a fixed parameter range without per-dataset tuning, and report the corresponding recall.","section":"Sec. 4.1.1 and Sec. 4.3"}],"minor_comments":[{"comment":"The heading 'Implemetation Details of PGS' contains a typo; it should read 'Implementation Details of PGS'.","section":"Sec. 3.4"},{"comment":"In the proof of the Unique Assignment Property, the phrase 'denoeted as TC(πz)' should be 'denoted as TC(πz)'.","section":"App. C"},{"comment":"The definition of the pivot set P is ambiguous when several edges tie at the K1-th largest weight: the text says 'all such edges are included until |P| = K1', but including all tied edges can make |P| exceed K1. Please specify the tie-breaking rule precisely.","section":"Eq. (4)"},{"comment":"The ablation table skips rows 20–22, yet the text refers to 'rows 10 vs. 23'. Please renumber the rows and adjust the references so that every cited row exists.","section":"Table 5"},{"comment":"Figure 5 would be easier to read if the horizontal axis labels and units were shown explicitly for each panel, and if the caption stated how many point-cloud pairs contributed to the distributions.","section":"App. A.2, Fig. 5"},{"comment":"The notation 'TurboReg (1K)' is used in the abstract without defining K; please define K1 and K2 at first use. Also, Fig. 1 labels the proposed method as 'ICCV2025'; if this is not the accepted venue, this label should be removed.","section":"Abstract and Fig. 1"},{"comment":"The claim that the GPU implementation 'effectively achieves near-constant time complexity, approximating O(1)' assumes R ≫ K1N and ignores data-transfer and synchronization costs. The measured times in Table 7 show that PGS consumes about 11.4–11.9 ms and model estimation scales with K1; please soften the O(1) claim to match the actual implementation behavior.","section":"Sec. 3.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's core theoretical justification for TurboClique is not sound in its current form, but the empirical contribution is substantial and the method appears to work well in practice. The revision should focus on (i) removing or rigorously replacing the invalid τ→0 stability argument, (ii) presenting the speed comparison fairly with CPU-to-CPU numbers as the primary comparison, and (iii) using a validation protocol that does not tune hyperparameters on the test benchmarks. If these points are addressed, the paper could be a strong practical contribution to the PCR literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper has a real practical result and a real theoretical hole. The work replaces maximal clique search with a fixed-size 3-clique found by pivot-guided linear search on an ordered SC2 graph. That combination is new, it is precisely described, and the empirical evaluation is broad: 3DMatch, 3DLoMatch, KITTI with FPFH/FCGF/Predator, and the method consistently reaches state-of-the-art recall at much lower runtime. Code is released. Credit where due: the PGS algorithm's GPU mapping is clean, the O2Graph's unique assignment property is proven, and the ablations are reasonably thorough. The headline 208x speedup over 3DMAC, however, compares TurboReg GPU time to 3DMAC CPU time; the same table shows CPU-to-CPU is closer to 8.8x. Not fatal, but the abstract should be honest.\n\nThe bigger problem is the theoretical foundation in App. A.1. The paper argues that small tau makes a 3-clique as stable as a maximal clique because the constraint | ||d+e|| - ||d|| | <= tau forces e -> 0 as tau -> 0. That is false. The constraint only restricts the component of e along d; at tau = 0 the constraint set is the sphere ||d+e|| = ||d||, which contains e = -2d and all perpendicular rotations. Three matches can be jointly rotated about the triangle while preserving all pairwise distances, so the effective noise variance does not vanish. The experimental validation in App. A.2 shows 3-clique vs 10-clique discrepancies shrinking with tau on 3DMatch+FPFH, but that is one dataset and one descriptor, with no noise-level variation. So Definition 1's stability claim is not established. The method might still work because stringent SC2 compatibility plus pivot selection yields high-inlier 3-cliques, but the paper should say that is a design heuristic, not a derived guarantee.\n\nThe hyperparameter story is similar: tau is fine-tuned from 0.25x resolution to 1.2 cm on the evaluation benchmark, and K1 is chosen per dataset. The ablations show plateaus, so this is a minor overfitting issue, not a fatal one. The runtime table and ablation table do let a reader recompute fair comparisons, which is good practice.\n\nWho is this for? Anyone working on correspondence-based registration or robust estimation for SLAM/robotics. It deserves a serious referee: the empirical contribution is substantial and the method is likely to be used even if the stability proof is wrong. I would send it to review with a request to either fix the App. A.1 argument or reframe it as empirical motivation, and to report CPU/GPU-matched speedups. Not a desk reject.","headline":"A genuinely faster clique-based registration estimator with solid empirical results, but the paper's central stability justification is a hand-wavy limit that doesn't survive scrutiny.","tokens_in":25199,"tokens_out":3892,"would_cite":true,"duration_ms":47185,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Three mutually compatible correspondences are enough to estimate a rigid transformation as reliably as a maximal clique, turning exponential-time search into a linear-time GPU-parallel algorithm.","keywords":["point cloud registration","robust estimation","compatibility graph","maximal clique","3-clique","pivot-guided search","second-order spatial consistency","GPU parallel search"],"falsifier":"Run the discrepancy experiment from App. A.2 on datasets beyond 3DMatch+FPFH: for a sample of pairs, extract 10-cliques and all their $\\binom{10}{3}$ 3-clique subsets at the recommended threshold $\\tau \\approx 0.25\\times$ resolution, and compare the estimated rotations and translations; if on 3DLoMatch, KITTI, or with FCGF/Predator features the median disagreement grows to a substantial fraction of the success thresholds (15° rotation, 30 cm translation) — or if TurboReg's recall drops noticeably versus a 10-clique variant on the same pairs — then the compensating-stability assumption does not transfer and the reported speedup is specific to the 3DMatch+FPFH regime.","tokens_in":24112,"feed_emoji":"⚡","tokens_out":20296,"duration_ms":157470,"temperature":0.7,"pith_summary":"TurboReg's central claim is that a fixed 3-clique — three correspondences that are mutually compatible under a tight distance-difference bound — estimates a rigid transformation as stably as the maximal cliques used by leading graph-based registration methods, and that this swap turns an exponential-time search into a linear-time, GPU-parallel one. The reasoning is a variance trade-off: the least-squares pose estimate is stabilized either by feeding it many matches, as maximal cliques do, or by suppressing the effective noise through a stringent compatibility threshold $\\tau$, which is the mode TurboClique relies on. To keep the three-match hypotheses rich in inliers, the Pivot-Guided Search ranks the highest second-order-compatibility edges as pivots and expands each into a third compatible match, producing only $K_1 K_2$ hypotheses per frame. If the claim holds, robust registration stops being a combinatorial bottleneck: on the 3DMatch dataset with FCGF features, TurboReg (1K) reports more than 200× the GPU throughput of the 3DMAC maximal-clique method while raising registration recall from 92.79% to 93.59%.","feed_headline":"Three compatible matches can replace maximal-clique search","feed_subtitle":"TurboReg runs 208× faster than 3DMAC on 3DMatch+FCGF, with higher recall.","key_machinery":"The load-bearing objects are (1) TurboClique, a 3-clique in a compatibility graph whose edge exists when $|\\,\\|x_i-x_j\\|-\\|y_i-y_j\\|\\,| \\le \\tau$, with $\\tau$ set near a quarter of the point-cloud resolution; (2) the Pivot-Guided Search (PGS), which orders edges of the second-order compatibility graph $\\hat{G}_{ij} = G_{ij}\\sum_k G_{ik}G_{jk}$, takes the top $K_1$ edges as pivots, and expands each pivot by its common neighbors into triplets scored by summed edge weight, keeping the top $K_2$ per pivot; and (3) the Ordered SC² Graph (O2Graph), a directed version that orients each edge from the lower to the higher node index and provably assigns every TurboClique to a unique pivot. The theoretical engine is the variance identity for the least-squares estimator, which frames clique size and residual noise as interchangeable sources of stability and licenses the swap from maximal to minimal cliques.","core_discovery":"The paper's central claim is that a TurboClique — a 3-clique in a compatibility graph built with a stringent (small) threshold $\\tau$ (Definition 1) — carries enough spatial-consistency information to estimate a rigid transformation as stably as a maximal clique does. The supporting analysis treats the Kabsch solver as a least-squares estimator with variance $\\mathrm{Var}(\\hat{\\beta}|X) = \\sigma^2(X'X)^{-1}$, isolating two stability mechanisms: data-scaling stability from using many matches, and pairwise compatibility-induced stability from enforcing $|\\,\\|x_i-x_j\\| - \\|y_i-y_j\\|\\,| \\le \\tau$ on every pair. The paper argues that as $\\tau$ shrinks, the constraint truncates the matching-noise distribution so that its effective variance $\\sigma^2_{\\text{eff}}$ tends to zero, and that the recommended threshold $\\tau \\approx 0.25\\times$ point-cloud resolution makes a 3-clique estimate agree with a 10-clique estimate to within $0.1^\\circ$ rotation and $0.5$ mm translation on 3DMatch+FPFH (App. A.2). The search side is carried by PGS, which ranks edges of the SC² graph by their second-order score, takes the top $K_1$ as pivots, and keeps the top $K_2$ third matches per pivot, giving $K_1 K_2$ hypotheses in $O(K_1 N)$ time; the directed O2Graph variant guarantees that each TurboClique is generated by exactly one pivot.","pith_inferences":["My inference: the stability trade-off is argued heuristically — a noise-truncation limit rather than a quantitative bound on transformation-error variance as a function of $\\tau$ and clique size — so the compensation claim is a design principle awaiting a theorem; a closed-form variance bound would predict the optimal $\\tau$ without per-dataset ablations.","My inference: the fixed-size-clique-plus-pivot recipe is generic and should transfer to any consensus problem with a pairwise geometric consistency graph, including loop-closure detection in SLAM, multi-view image matching, and wide-baseline stereo, where the same exponential graph-search bottleneck appears.","My inference: the paper's own supplementary analysis suggests the remaining bottleneck is hypothesis ranking, not search — the top-1 inlier-count rule misses correct transformations that sit inside the top-$K$ set, so a better re-ranker on top of PGS could raise recall further without slowing the search.","My inference: the practical ceiling of the method is reached when fewer than three true inliers survive feature matching — at extreme low overlap the 3-clique itself cannot exist, and the method would need a denser or better descriptor rather than a bigger search."],"forward_implications":["Maximal-clique enumeration — costing on the order of $O(d(N-d)3^{d/3})$ for graph degeneracy $d$ — can be replaced by an $O(N)$ fixed-size search, and with enough parallel units on a GPU the search approaches constant time.","Only $K_1 K_2 = 2000$ hypotheses are needed per point-cloud pair at the default settings, orders of magnitude fewer than the millions of RANSAC iterations, and this budget yields the highest registration recall among the compared estimators on 3DMatch, 3DLoMatch, and KITTI.","The speed and accuracy transfer across descriptor families: FPFH, FCGF, and Predator features all feed the same TurboClique pipeline without retraining or per-descriptor tuning beyond the threshold rule.","Runtime becomes predictable: unlike maximal-clique enumeration, whose cost depends on graph density and branching, PGS has a tightly clustered per-frame runtime, which the paper positions as suitable for real-time SLAM-style applications.","The ablations give a simple operating recipe: set $\\tau$ near a quarter of the point-cloud resolution, $K_1 = 1000$, and $K_2 = 2$, and recall stays within a couple of points of its peak over a wide range of $\\tau$ (above 82% for $\\tau$ from 0.01 m to 0.08 m on 3DMatch+FPFH)."],"supporting_citations":[{"why":"The 3DMAC maximal-clique enumeration baseline: TurboReg replaces its exponential-cost search and compares registration recall and runtime against it.","marker":"[61]"},{"why":"Defines the second-order compatibility (SC²) graph whose edge scores the PGS pivot selection ranks.","marker":"[9]"},{"why":"FastMAC, the downsampling-based maximal-clique speedup baseline that calibrates TurboReg's speed and recall comparisons.","marker":"[62]"},{"why":"The Kabsch least-squares pose solver whose variance identity underlies the stability analysis of 3-clique estimates.","marker":"[26]"},{"why":"The edge-oriented k-clique listing strategy cited as the motivation for the O2Graph ordering that gives each TurboClique a unique pivot.","marker":"[47]"},{"why":"Documents the difficulty of parallelizing maximal clique enumeration on GPUs, motivating the fixed-size clique design.","marker":"[2]"},{"why":"RANSAC, the classic sampling-based hypothesis generation paradigm that the paper contrasts with pivot-guided generation.","marker":"[17]"},{"why":"The FCGF descriptor used in the 3DMatch+FCGF experiment where the 208× speedup over 3DMAC is reported.","marker":"[11]"}],"fun_headline_variants":["Three points can replace maximal clique search","TurboReg replaces maximal cliques with 3-cliques for 208x speedup","Small 3-cliques beat maximal cliques in point cloud registration","TurboClique: linear-time alternative to exponential maximal clique search","Pivot-guided 3-cliques make point cloud registration 208x faster"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that tightening the compatibility threshold squeezes the matching-noise variance down fast enough that three compatible matches estimate a transformation as stably as a large clique would, a trade-off supported by a heuristic noise-truncation argument and a single 3-clique-versus-10-clique experiment on 3DMatch+FPFH rather than by a quantitative bound that holds across scenes, descriptors, and noise levels.","fun_headline_variants_meta":{"raw":{"variants":["Three points can replace maximal clique search","TurboReg replaces maximal cliques with 3-cliques for 208x speedup","Small 3-cliques beat maximal cliques in point cloud registration","TurboClique: linear-time alternative to exponential maximal clique search","Pivot-guided 3-cliques make point cloud registration 208x faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00058,"raw_usage":{"total_tokens":2828,"prompt_tokens":1136,"completion_tokens":1692,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":752,"completion_tokens_details":{"reasoning_tokens":1610}},"tokens_in":752,"tokens_out":1692,"duration_ms":13698,"temperature":1.0,"reasoning_tokens":1610,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:51:13.374358+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the discrepancy experiment from App. A.2 on datasets beyond 3DMatch+FPFH: for a sample of pairs, extract 10-cliques and all their $\\binom{10}{3}$ 3-clique subsets at the recommended threshold $\\tau \\approx 0.25\\times$ resolution, and compare the estimated rotations and translations; if on 3DLoMatch, KITTI, or with FCGF/Predator features the median disagreement grows to a substantial fraction of the success thresholds (15° rotation, 30 cm translation) — or if TurboReg's recall drops noticeably versus a 10-clique variant on the same pairs — then the compensating-stability assumption does not transfer and the reported speedup is specific to the 3DMatch+FPFH regime.","supporting_citations":[{"cited_title":"3d registration with maximal cliques","cited_arxiv_id":null,"evidence_quote":"The 3DMAC maximal-clique enumeration baseline: TurboReg replaces its exponential-cost search and compares registration recall and runtime against it."},{"cited_title":"Sc2-pcr: A second order spatial compatibility for efficient and robust point cloud registration","cited_arxiv_id":null,"evidence_quote":"Defines the second-order compatibility (SC²) graph whose edge scores the PGS pivot selection ranks."},{"cited_title":"Fast- mac: Stochastic spectral sampling of correspondence graph","cited_arxiv_id":null,"evidence_quote":"FastMAC, the downsampling-based maximal-clique speedup baseline that calibrates TurboReg's speed and recall comparisons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Kabsch least-squares pose solver whose variance identity underlies the stability analysis of 3-clique estimates."},{"cited_title":"Efficient k- clique listing: An edge-oriented branching strategy","cited_arxiv_id":null,"evidence_quote":"The edge-oriented k-clique listing strategy cited as the motivation for the O2Graph ordering that gives each TurboClique a unique pivot."},{"cited_title":"Parallelizing maximal clique enumeration on gpus","cited_arxiv_id":null,"evidence_quote":"Documents the difficulty of parallelizing maximal clique enumeration on GPUs, motivating the fixed-size clique design."},{"cited_title":"Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography","cited_arxiv_id":null,"evidence_quote":"RANSAC, the classic sampling-based hypothesis generation paradigm that the paper contrasts with pivot-guided generation."},{"cited_title":"Fully convolutional geometric features","cited_arxiv_id":null,"evidence_quote":"The FCGF descriptor used in the 3DMatch+FCGF experiment where the 208× speedup over 3DMAC is reported."}],"review_version":1}