{"id":"3926dd25-25fe-4bc7-b77d-cbb00385b4a4","arxiv_id":"1908.02021","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"NAPA and DIBP accelerate A* consensus maximization tree search by orders of magnitude while preserving global optimality, making exact robust fitting practical on previously infeasible inputs.","lead":"This paper speeds up exact consensus maximization, a robust model fitting method in computer vision, by removing redundant paths in the search tree and adding a dimension-insensitive pruning technique. The combined method solves instances that previously took hours in seconds, often hundreds to over a thousand times faster.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The global-optimality claim is unverified in the non-linear homography experiments because the inner minimax problems (4)/(14) are solved by fminimax, a local optimizer.","rationale":"The most load-bearing weakness is exactly the one identified by the reader: the theoretical guarantees of A* tree search, NAPA, and DIBP all presuppose exact inner minimax solves, yet the non-linear homography experiments rely on fminimax. This concern is not a manufactured contradiction; it follows from the paper's own experimental setup. The linear KITTI experiments are unaffected, and the algorithmic contributions are plausible, so the paper should remain conditionally accepted rather than rejected. A concrete check with a certified global solver on the small homography instances would settle whether the non-linear results actually exhibit global optimality. I agree with the reader's assessment, and therefore the verdict should remain CONDITIONAL, which is represented here as UNCHANGED because the reader's verdict already reflects this condition.","tokens_in":13025,"tokens_out":14673,"duration_ms":171839,"concrete_test":"Re-run the five homography experiments from Table 2 with an independent, certified global solver for the minimax subproblems (4) and (14), invoked at every node visited by A*-NAPA-DIBP using the released code. For example, use interval branch-and-bound or exhaustive active-set enumeration on these d=8 problems, and compare the returned consensus values, NUN, NOBP, and runtimes against Table 2. If the global solver produces the same bases, levels, and DIBP pruning decisions, the concern is resolved. If any fminimax solve was suboptimal, the claimed global optimality and the specific speedups on homography data must be qualified as heuristic, pending a solver that actually solves each subproblem to global optimality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim that NAPA and DIBP accelerate A* tree search without sacrificing global optimality is conditional on exact solutions to the minimax subproblems (4) and (14). Section 2.2 asserts that problem (4) has a unique optimal solution and can be solved efficiently with standard solvers, but in Section 6.3 the authors state that, for the non-linear homography experiments, the problems (4) and (14) were solved by the MATLAB function fminimax. fminimax is a local optimizer and provides no global optimality certificate. If a returned solution is not the global minimizer, then the computed basis, violation set, and level l(B) are not the LP-type quantities assumed by the A* admissibility argument, and the subsequent NAPA test in Algorithm 3 line 11 (l(B') > l(B)) and the DIBP pruning condition in (18) are evaluated on incorrect data. The homography residuals in (3) are fractional and the paper does not describe an initialization strategy, multi-start, or any verification that fminimax outputs are globally optimal. Thus the 'globally optimal' results in Table 2 are not supported by the evidence presented. The linearized fundamental-matrix experiments in Section 6.2 use an exact vertex-to-vertex solver and are not affected, but the homography experiment is the only nonlinear demonstration and is the load-bearing evidence for the claim that the techniques work beyond linear residuals.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper revisits A* tree search for exact consensus maximization and proposes two accelerations. The first, NAPA (Non-Adjacent Path Avoidance), observes that when a child B' is generated from B by solving on C(B)\\setminus{s}, its violation set satisfies V(B')⊆V(B)∪{s}; if B' is not adjacent to B then l(B')≤l(B), so the generated node can be discarded without losing the adjacent path needed for optimality. The second, DIBP (Dimension-Insensitive Branch Pruning), replaces TOD's search for a single true outlier with a search for a subset S_B of the current basis that must contain at least one true outlier; if condition hins(B|S_B)>g(B) is met, all child branches except those corresponding to points in S_B can be pruned. The authors provide Lemmas 1 and 2 on when TOD is weak and when DIBP can safely start from a larger candidate set, and they evaluate the resulting A*-NAPA-DIBP algorithm on synthetic robust linear regression, linearized fundamental matrix estimation on KITTI, and homography estimation. They report speedups of several orders of magnitude over previous A* and A*-TOD variants, with all KITTI fundamental-matrix instances solved in under 10 seconds.","tokens_in":13226,"tokens_out":11379,"duration_ms":176393,"significance":"If the issues below are addressed, the paper is a meaningful contribution. NAPA is a clean, apparently sound observation about the consensus maximization tree structure, and the reported empirical gains are large. DIBP is a natural and promising extension of TOD that is experimentally much more effective on challenging instances. The release of demo code is a strength, and the synthetic and KITTI fundamental-matrix experiments provide convincing evidence for the linear-residual setting. The theoretical novelty is modest — both techniques build directly on the authors' earlier TPAMI tree search — but the practical acceleration is substantial and the paper is clearly written. The main risk is that the homography experiments, which are the only nonlinear demonstration, currently do not support the global-optimality claim because the inner problems are solved with a local optimizer. Fixed within the manuscript's scope, the paper would be a solid step toward practical exact consensus maximization.","major_comments":[{"comment":"The homography experiments are load-bearing for the claim that NAPA and DIBP work beyond linear residuals, but the inner minimax problems (4) and (14) are solved with MATLAB fminimax, a local optimizer that provides no global optimality certificate. Section 2.2 asserts that problem (4) has a unique optimal solution and can be solved efficiently with standard solvers, and the A* optimality argument, the NAPA discard rule (Algorithm 3, line 11), and the DIBP pruning test (18) all depend on the computed basis, violation set, and level being the exact LP-type quantities. If fminimax returns a non-global solution, the violation set V(B), the level l(B), the heuristic hins, and the upper bound g(B) are all incorrect, so the 'globally optimal' homography results in Table 2 are not supported by the evidence presented. The linearized fundamental-matrix experiments in Section 6.2 use an exact vertex-to-vertex solver and are not affected. Please either use an exact global solver for the non-linear minimax subproblems or explicitly restrict the global-optimality claims to the linear-residual experiments and present Section 6.3 as a heuristic demonstration.","section":"Sec. 6.3, Table 2; Sec. 2.2, Eqs. (4), (14)"},{"comment":"The correctness of DIBP is asserted but not formally established. The paper defines hins(B|S_B) by analogy with hins(B|s) and claims that condition (18) identifies a subset S_B containing at least one true outlier, but it never states or proves the subset analogue of the TOD equivalence (11) — namely that h*(B|S_B)>h*(B) holds exactly when S_B contains a point outside the largest feasible subset of C(B) — nor does it prove that hins(B|S_B) is an admissible lower bound on h*(B|S_B). Because DIBP prunes |B|-|S_B| branches on the basis of (18), this missing argument is load-bearing. Please add a formal lemma with proof, or an explicit reduction to the TOD proof in [6].","section":"Sec. 4.2, Eq. (18); Algorithm 3, line 14"}],"minor_comments":[{"comment":"The sentence 'the repeated basis check heuristic in Algorithm 1 assumes that the level of the child node B' is always lower than the parent B by 1' appears to be a typo: along an adjacent edge the child's level is l(B)+1, not lower. Please correct this, as it obscures the NAPA argument.","section":"Sec. 3, paragraph after Eq. (10)"},{"comment":"Please state how many random instances each curve in Figure 5 averages over and include error bars or variance information; it is currently unclear whether each point is a single run.","section":"Sec. 6.1, Fig. 5"},{"comment":"The speedup row uses '>6400' for timed-out baselines; since the exact termination time is unknown, these are lower bounds. Please state this explicitly in the caption or text.","section":"Sec. 6.2, Table 1 caption"},{"comment":"The claim that 'the value of φ in the non-linear case was usually also much smaller' is not supported by any measurement in the paper. Please provide the actual φ values or a reference.","section":"Sec. 6.3"},{"comment":"The quantity φ is described as the 'average size of all Brem during Algorithm 2,' but the average is not specified precisely (over what set of bases or runs). Please define it formally before Lemma 1.","section":"Sec. 4.2, Lemma 1"},{"comment":"When l(B')≤l(B), the generated B' is discarded but s is not added to S_B, whereas Section 5 says s can be added to S_B 'even though it leads to repeated bases.' Please clarify whether the non-adjacent case is intentionally treated differently from the repeated-basis case and why.","section":"Algorithm 3, lines 8–18"},{"comment":"There are several typos, including 'non-adjacenct' in the algorithm list, 'seach' in Section 6.2, and 'algebaric' in Section 6.2. Please proofread.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper depends heavily on the authors' own prior TPAMI paper [6] for the admissibility of hins and the upper-bound property of g(B). This is not a circularity problem, but the manuscript should state explicitly which correctness results are inherited from [6] and which are new. The main risk is the fminimax issue in the homography experiments: if the authors cannot replace the local solver with an exact method, they should substantially soften the global-optimality claims for Section 6.3. With that fixed, the paper is likely acceptable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, this paper has two genuinely new algorithmic tricks for exact consensus maximization: NAPA, which avoids redundant non-adjacent paths in the LP-type tree, and DIBP, which generalizes the TOD pruning to subsets. Both are clean, the safety arguments are sound, and the speedups on the fundamental matrix experiments are real and large (hundreds to over a thousand times). Second, the homography experiment does not actually establish global optimality, because the inner minimax problems are solved by fminimax, a local optimizer. That doesn't sink NAPA/DIBP as algorithmic ideas, but it means Table 2 should be read as 'A* with a local inner solver,' not as a certificate of optimality.\n\nWhat's good: The NAPA observation is simple and correct: a generated child satisfies V(B') ⊆ V(B) ∪ {s}, so non-adjacent children have level ≤ l(B) and can be discarded. The DIBP extension is a natural generalization of TOD with decent theoretical motivation, including Lemma 2 for linear residuals. The implementation is released. The KITTI fundamental matrix results are the strong part: the vertex-to-vertex solver is exact, and the time comparisons are striking. The comparison against MIP on synthetic data is also useful and fair (MIP parallelized, tree search sequential).\n\nSoft spots: The fminimax issue is the main one. In Sec 6.3 the paper says the non-linear problems (4) and (14) were solved by MATLAB's fminimax. fminimax is local and gives no global certificate. If the returned solution isn't the global minimizer, the basis, violation set, and level are wrong, which breaks both NAPA's level check and DIBP's pruning. The paper doesn't describe initialization, multi-start, or verification. So Table 2's runtimes may be plausible, but the 'globally optimal' label is not supported there. I'd also note the synthetic timing plots have no error bars, and the choice of homography data isn't justified. Minor: the paper leans on [6] for hins admissibility and the g(B) upper bound; that's a self-citation dependency, but a reasonable one since [6] is published and the authors are extending it.\n\nBottom line: for readers working on globally optimal geometric fitting, this is worth a serious look. The linear-experiment speedups are credible and the new ideas should transfer. The nonlinear experiment needs to be redone with a certified global inner solver, or at minimum multi-start plus reporting of consensus values, before the global-optimality claim covers homography. I'd send this to a serious referee who can check the LP-type arguments and maybe run the code. It deserves peer review, not a desk reject.","headline":"Clean algorithmic improvements to exact consensus maximization that deliver real speedups on linear problems, but the homography results rest on a local inner solver and so do not certify global optimality.","tokens_in":13838,"tokens_out":2202,"would_cite":true,"duration_ms":21683,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that two new techniques, NAPA and DIBP, accelerate A* tree search for consensus maximization by avoiding redundant paths and dimension-sensitive pruning, preserving global optimality and producing speedups of over 1000x…","keywords":["consensus maximization","robust fitting","A* tree search","LP-type problems","branch pruning","global optimization","outlier detection","fixed-parameter tractability"],"falsifier":"Take a small homography instance whose inner constrained minimax problems have known lower residuals than the local optimizer returns; if the search then prunes the branch containing the true optimum or returns a feasible basis with suboptimal consensus, the central claim fails. Concretely, run A*-NAPA-DIBP on a benchmark with a known optimal consensus, once with the local inner solver and once with a certified global inner solver, and check whether both return the same consensus value.","tokens_in":12743,"feed_emoji":"🎯","tokens_out":6953,"duration_ms":70083,"temperature":0.7,"pith_summary":"The paper claims that exact A* tree search for consensus maximization—finding the model consistent with the largest number of measurements despite outliers—can be made orders of magnitude faster without giving up global optimality. It identifies two sources of wasted work in the previous algorithm: tree paths connecting nodes at non-adjacent levels, which are redundant but were previously traversed, and a branch-pruning test whose reliability collapses as the model dimension grows. The proposed NAPA strategy skips any generated child basis whose level is not strictly larger than its parent's, while DIBP prunes by certifying that a small subset of the current basis must contain at least one true outlier. On real KITTI fundamental-matrix instances, the combined method finds the globally optimal solution in under 10 seconds where earlier A* variants often failed to finish in 2 hours.","feed_headline":"A* tree search gets 1000x faster via two pruning tricks","feed_subtitle":"Skipping redundant tree paths and certifying outlier-containing subsets solves KITTI fits in under 10 seconds.","key_machinery":"The object that carries the argument is the basis tree of an LP-type problem. A basis is a minimal subset whose minimax residual equals that of its superset; each node has a violation set $V(B)$ of points whose residual exceeds the minimax value, and its level is $\\ell(B)=|V(B)|$. Two bases are adjacent when their violation sets differ by exactly one point, and the earlier algorithm expanded nodes by computing $\\tau(C(B)\\setminus\\{s\\})$ for each $s$ in the current basis, which can produce a non-adjacent node whose level is not larger than the parent's. NAPA restores the intended search graph with the simple level test $\\ell(B')>\\ell(B)$. DIBP replaces the single-point test with a growing subset $S_B$: it adds points with the largest residual under a cheap upper-bound solution and uses the admissible heuristic bound $h_{\\mathrm{ins}}(B|S_B)>g(B)$ to certify that $S_B$ contains a true outlier, so all branches not removing a point of $S_B$ can be pruned. The level test is what makes DIBP cheap, because the elements added to $S_B$ are often exactly the ones that generated repeated or non-adjacent nodes.","core_discovery":"Consensus maximization is NP-hard, but exact A* tree search is fixed-parameter tractable and can be made practical on moderate inputs by removing two inefficiencies. In the basis tree of the LP-type formulation, a child basis generated by removing one point from the current basis and solving a minimax problem is not always an adjacent child: its violation set can coincide with a basis at the same or lower level. Since tree search only needs adjacent paths, every generated basis $B'$ with level $\\ell(B') \\le \\ell(B)$ can be discarded without changing the optimal solution. The existing True Outlier Detection (TOD) branch pruning decides whether a single point is a true outlier by comparing heuristic bounds, but this decision is systematically unreliable when the outlier rate or dimension is high; DIBP instead greedily accumulates points into a set $S_B$ certified to contain at least one true outlier, a weaker and more frequently satisfiable demand. The paper reports that A*-NAPA-DIBP returns the globally optimal solution on all tested KITTI and homography benchmarks, with speedups of hundreds to more than a thousand times over prior A* variants.","pith_inferences":["NAPA's insight that generated children with non-increasing levels are redundant generalizes to any tree search over LP-type bases: any expansion violating strict level increase is outside the adjacency graph and can be pruned in other LP-type solvers, not just consensus maximization.","DIBP suggests a general pruning principle: instead of certifying a single required object, certify any subset that contains at least one required object, because the larger the subset the weaker the certificate needed; this trade-off is exactly what DIBP exploits by growing $S_B$ greedily.","A testable extension is to replace the residual-based ordering of additions to $S_B$ with data-dependent priorities; if DIBP's gains depend on reaching a certified $S_B$ early, better ordering could reduce the number of constrained minimax solves further.","Since the paper's runtime is dominated by inner minimax solves, substituting a faster certified global solver for the local optimizer used in the non-linear experiments could extend the same acceleration to residual models where inner solves are currently the bottleneck."],"forward_implications":["A*-NAPA-DIBP solves linearized fundamental matrix estimation on KITTI frames with 13 to 22 outliers in 2 to 8 seconds, whereas A* and A*-TOD often exceed 2 hours; if correct, exact robust fitting becomes usable on realistic two-view geometry problems.","The speedups preserve the fixed-parameter tractability guarantee of tree search, so the returned solution carries a certificate of global optimality rather than an approximation guarantee.","NAPA reduces the number of unique nodes generated by large factors, and DIBP further collapses branching; the two gains are separate and combine, making the full method faster than either technique alone on every reported benchmark.","Because the level test and DIBP are stated for any LP-type problem with pseudo-convex residuals, the same acceleration should transfer to other consensus maximization tasks beyond linear regression and fundamental matrix estimation, and the paper demonstrates the transfer to homography estimation."],"supporting_citations":[{"why":"Supplies the original A* tree search with TOD branch pruning and the admissible heuristic h_ins that this paper accelerates.","marker":"[6]"},{"why":"Introduces A* tree search for consensus maximization and serves as a baseline in the experiments.","marker":"[5]"},{"why":"Establishes NP-hardness and fixed-parameter tractability, motivating the exact tree-search approach.","marker":"[4]"},{"why":"Shows that bases of an LP-type problem form a tree with adjacent paths, the structural foundation for NAPA.","marker":"[18]"},{"why":"Defines LP-type problems and the monotonicity and locality properties used throughout the paper.","marker":"[25]"},{"why":"Provides the quasiconvex-programming background for solving the minimax subproblems.","marker":"[10]"},{"why":"The vertex-to-vertex algorithm used in the linear experiments to solve the minimax problems exactly.","marker":"[3]"},{"why":"Textbook result that a linear program's optimum lies at a vertex, used in Lemma 2 to bound the starting size for DIBP.","marker":"[19]"}],"fun_headline_variants":["Exact consensus maximization: A* tree search 1000x faster","Two pruning tweaks accelerate A* tree search for robust fitting","Skipping redundant tree paths and better pruning speed exact fitting","A* tree search rethink: avoid redundant paths, prune better","Making exact consensus maximization practical with two insights"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Every minimax subproblem and its constrained version must be solved to global optimality, but the paper's non-linear experiments use a local numerical optimizer with no global optimality guarantee, so a non-global solution anywhere along the search would invalidate the level test, the heuristic bounds, and the optimality certificate.","fun_headline_variants_meta":{"raw":{"variants":["Exact consensus maximization: A* tree search 1000x faster","Two pruning tweaks accelerate A* tree search for robust fitting","Skipping redundant tree paths and better pruning speed exact fitting","A* tree search rethink: avoid redundant paths, prune better","Making exact consensus maximization practical with two insights"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000202,"raw_usage":{"total_tokens":1387,"prompt_tokens":958,"completion_tokens":429,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":343}},"tokens_in":574,"tokens_out":429,"duration_ms":4916,"temperature":1.0,"reasoning_tokens":343,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:56:57.998870+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small homography instance whose inner constrained minimax problems have known lower residuals than the local optimizer returns; if the search then prunes the branch containing the true optimum or returns a feasible basis with suboptimal consensus, the central claim fails. Concretely, run A*-NAPA-DIBP on a benchmark with a known optimal consensus, once with the local inner solver and once with a certified global inner solver, and check whether both return the same consensus value.","supporting_citations":[{"cited_title":"Efficient globally optimal consensus maximisation with tree search","cited_arxiv_id":null,"evidence_quote":"Supplies the original A* tree search with TOD branch pruning and the admissible heuristic h_ins that this paper accelerates."},{"cited_title":"Efficient globally optimal consensus maximisation with tree search","cited_arxiv_id":null,"evidence_quote":"Introduces A* tree search for consensus maximization and serves as a baseline in the experiments."},{"cited_title":"Robust fitting in computer vision: Easy or hard? In European Con- ference on Computer Vision (ECCV), 2018","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness and fixed-parameter tractability, motivating the exact tree-search approach."},{"cited_title":"Matouˇsek","cited_arxiv_id":null,"evidence_quote":"Shows that bases of an LP-type problem form a tree with adjacent paths, the structural foundation for NAPA."},{"cited_title":"A combinatorial bound for lin- ear programming and related problems","cited_arxiv_id":null,"evidence_quote":"Defines LP-type problems and the monotonicity and locality properties used throughout the paper."},{"cited_title":"Quasiconvex programming","cited_arxiv_id":null,"evidence_quote":"Provides the quasiconvex-programming background for solving the minimax subproblems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The vertex-to-vertex algorithm used in the linear experiments to solve the minimax problems exactly."}],"review_version":1}