acceptodds
Under review as a conference paper at ICLR 2027

Hierarchy-GBP: Accelerating Factor Graph Inference via Abstraction and Recovery

Abstract

Gaussian Belief Propagation (GBP) is a distributed inference algorithm that passes messages in graphical models, making it attractive for scalable spatial intelligence. However, we find GBP most effective locally: it rapidly smooths message errors that vary sharply between neighbor variables, but corrects global errors across distant graph regions incrementally through long-range message propagations. We propose *Hierarchy-GBP (H-GBP)*, an iterative, two-stage framework that accelerates GBP by first solving these global errors with a coarse graph approximation (abstraction) and projecting the results back to the original graph (recovery), then refining the remaining local errors with GBP. We prove H-GBP convergence to the optimum by deriving the combined matrix operator of our abstraction and recovery steps and analyzing its spectral radius. Experiments on linear sparse graphs show that H-GBP converges fundamentally faster than standard GBP. Moreover, we validate H-GBP on two important spatial problems: Pose Graph Optimization (PGO) and Bundle Adjustment (BA). H-GBP markedly accelerates large-scale PGO and achieves state-of-the-art runtime across all tested BA scales.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Gaussian Belief Propagation, Factor Graphs, Hierarchical Message Passing, Multilevel Inference, Distributed Inference, Spatial Intelligence

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_GKYpOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Hierarchy-GBP (H-GBP) to accelerate Gaussian Belief Propagation (GBP) hierarchically. It eliminates global errors via coarse corrections built from local low-eigenvalue modes, and damps local errors using fine-level GBP. The authors derive the joint cycle operator with a conditional convergence analysis. Evaluations on linear systems, PGO, and BA show that H-GBP fundamentally speeds up standard GBP and outperforms state-of-the-art solvers on several large-scale problems.

Critical strengths
  1. Beyond introducing a multilevel perspective to GBP, this paper explicitly analyzes the inconsistency between variable beliefs and messages following coarse correction and derives the joint iteration operator, establishing a solid theoretical foundation for the convergence analysis of hierarchical GBP.
  2. The empirical evaluation benchmarks H-GBP not only against standard GBP, but also against mainstream solvers including g2o, Ceres, and RootBA. H-GBP demonstrates significant runtime advantages across multiple large-scale PGO and BA datasets, highlighting its practical value.
Critical weaknesses

None

Questions for authors
  1. In the BA experiments, the final objective costs vary across different methods. For example, on Dubrovnik356, H-GBP’s final cost is approximately 3.4% higher than that of Ceres. While the appendix provides runtime-vs-cost curves against PowerBA, a complete comparison with Ceres and RootBA is missing. Could the authors provide runtime comparisons under a unified accuracy threshold (i.e., time-to-accuracy)?
  2. While the hierarchical structure is claimed to be key to accelerating GBP convergence, Figure 6 only compares error reduction under equal numbers of GBP sweeps, without accounting for the coarse-solve overhead in the total runtime. Could the authors provide a direct comparison of the total wall-clock time required for standard GBP and H-GBP to achieve the same accuracy?
Reviewer_kiY5OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Hierarchy-GBP (H-GBP), a two-level solver for linear Gaussian factor graphs, Ax=bAx=b, built around Gaussian Belief Propagation (GBP). The variables are partitioned into groups. Each group contributes the rr smallest eigenvectors of a local matrix assembled from the factors inside it, and these form a block-diagonal prolongation PP. Each cycle runs kk synchronous GBP sweeps, solves the Galerkin coarse problem P⊤AP δz=P⊤(b−Ax)P^\top AP\,\delta z=P^\top(b-Ax) directly, and injects PδzP\delta z into the variable beliefs, leaving all messages unchanged (Eq. 6). Nonlinear pose-graph optimization (PGO) and bundle adjustment (BA) are handled by applying the linear solver inside a Gauss-Newton loop.

Contributions as I understand them:

  1. The H-GBP algorithm, with a local low-rank coarse space for general sparse factor graphs (Sec. 4, Alg. 1).
  2. An exact operator description of one cycle, Taug,kT_{\mathrm{aug},k}, reduced to Mk=Qk−1(JCR+U)M_k=Q^{k-1}(JCR+U) on message space (Eqs. 12-13). This comes with a global geometric rate for the precision messages (Thm 6.3) and the criterion that the iteration converges for every admissible initialization if and only if ρ(Mk)<1\rho(M_k)<1, in which case the means converge to x⋆x^\star (Thm 6.5). There is also a local convergence result for the manifold extension (Thm 6.6).
  3. Experiments on linear translation graphs (Figs. 5-6), nine SE(2)/SE(3) PGO benchmarks against g2o, Cycle-PGO, AMM-PGO and Schwarz-PGO (Table 1), and ten BAL scenes against Ceres, RootBA and PowerBA (Table 2).

Validation: Thms 6.3 and 6.5 are proved in App. B. The theory does not cover the BA construction, as the paper states (L414-416). The empirical claims are faster convergence than GBP on linear graphs, and competitive-to-fastest runtimes on PGO and BA at matching or near-matching final cost.

Critical strengths
  1. A correct analysis of a two-level cycle with a stateful message-passing smoother. A multigrid smoother normally has no internal state. GBP carries messages, so a coarse correction has to say what happens to them, and the paper derives the resulting cycle operator exactly. I checked the main steps:
  • the canonical reference of Lemma B.8, which makes the error dynamics exactly homogeneous even while the precisions are still converging;
  • the reduction to MkM_k and the spectral equivalence of Lemma B.10;
  • the precision-contraction proof behind Thm 6.3;
  • the equivalence in Thm 6.5.

They are correct. The operator also simplifies further: a plain GBP sweep satisfies Q=JR+UQ=JR+U, so Mk=Qk−Qk−1JΠPRM_k=Q^k-Q^{k-1}J\Pi_PR with ΠP=P(P⊤AP)−1P⊤A\Pi_P=P(P^\top AP)^{-1}P^\top A. One H-GBP cycle is therefore kk GBP sweeps minus a low-rank correction. On a reconstruction of the two-lap graph of App. D.2, my implementation of Alg. 1 gives spectral radii similar to Table 5. This is a genuine technical contribution to GBP theory, and it is what makes the convergence behaviour of the method checkable at all.

  1. A strong runtime result on bundle adjustment. H-GBP is the fastest method on all ten BAL scenes in Table 2. This holds at one thread against one thread (e.g. Final3068: 12.40 s against 586.17 s for Ceres-Sparse), not only with 16 threads. It also beats PowerBA, the fastest competing 16-thread method on nine of ten scenes, in both runtime and final cost on every scene. On the large, loop-dense PGO graphs (Grid, Globe10k, Globe100k) it is also faster than single-thread Cholesky at equal thread count. These results show the method can be practically competitive within the reported implementations and budgets.
Critical weaknesses
  1. The central claim, that the hierarchy accelerates GBP, is neither guaranteed by the theory nor isolated by the experiments.

Theory. Thm 6.5 is a criterion. It does not compare ρ(Mk)\rho(M_k) with the plain-GBP rate ρ(Q⋆)k\rho(Q^\star)^k, and no such comparison holds in general. On small vector-valued graphs that satisfy Assumption 6.2, I find instances where plain GBP converges but H-GBP does not (ρ(Q⋆)=0.86\rho(Q^\star)=0.86, ρ(M1)=1.26\rho(M_1)=1.26). Running Alg. 1 literally with k=1k=1 on one of them, the error grows to 101510^{15}, while GBP reaches 10−810^{-8}. Across 40 such random instances and k∈{1,2,4,8}k\in\{1,2,4,8\}, ρ(Mk)>ρ(Q⋆)k\rho(M_k)>\rho(Q^\star)^k in 156 of 160 cases. These are my constructions, not the paper's benchmarks. They do not contradict Thm 6.5, which assumes ρ(Mk)<1\rho(M_k)<1. But the "predict[ed] large improvement" (L91-92) is an instance-by-instance computation, not a consequence of the theory, and Table 5 and Fig. 5(b) report ρ(M50)\rho(M_{50}) without the ρ(Q⋆)50\rho(Q^\star)^{50} it should be compared with.

Experiments. Neither Table 1 nor Table 2 includes plain GBP, so the acceleration over GBP is shown only on the linear two-lap graph. That graph is poorly conditioned (a 10−610^{-6} anchor, L1509), which is a legitimate test for a coarse correction but a narrow one. There is also no ablation that replaces GBP by a block-Jacobi or Gauss-Seidel smoother with the same coarse space, and none comparing message preservation with resetting.

This matters because the method's parts are individually established. The coarse space is closest to spectral-aggregation multigrid (GenEO / spectral AMGe), and GBP has been used as a multigrid smoother before (El-Kurdi et al., 2014, 2015). That earlier work keeps the precision messages but reinitializes the information messages after each correction, whereas H-GBP keeps both. What would be specific to this paper (GBP smoothing with an algebraic coarse space, and the preservation rule) is exactly what the experiments do not isolate.

  1. The size of the empirical advantage is overstated by the comparison protocol.
  • PGO. The headline speedups over g2o-Cholesky (126.6×, 17.5×, 30.2×; L401-403) compare 16-thread H-GBP with single-thread Cholesky, using a simplicial CHOLMOD build whose factorization is serial (L1589-1590). At equal thread count they are 30.6×, 4.6× and 7.3×. On the other six PGO datasets, single-thread Cholesky is faster than single-thread H-GBP by 2.4× to 19.9×.
  • BA. Methods are compared under a cap of 20 nonlinear iterations rather than at a shared accuracy target, and H-GBP ends at a higher cost than Ceres-Sparse on seven of ten scenes (by up to 3.4%, Dubrovnik356).

So the "state-of-the-art runtime" claim is supported against the reported configurations, but its magnitude against a tuned direct solver, and at matched accuracy, is not established.

Questions for authors
  1. (Clarification) Why preserve the information messages at injection, rather than resetting them as FMGaBP does? Consistency with the corrected mean does not determine the messages uniquely, so please specify a reset rule and report ρ(Mk)\rho(M_k) under it. A related observation: with a full coarse space (P=IP=I), the returned mean is exact after one correction, yet the internal messages evolve under Qk−1UQ^{k-1}U, which can have spectral radius above one. An answer showing that preservation is the better choice would bear directly on Weakness 1.

  2. (Clarification) Please report ρ(Q⋆)k\rho(Q^\star)^k next to ρ(Mk)\rho(M_k) in Table 5 and Fig. 5(b). Is there any condition on the graph, the coarse space or kk under which ρ(Mk)<ρ(Q⋆)k\rho(M_k)<\rho(Q^\star)^k can be guaranteed, or a smoothing property for GBP established?

  3. (Clarification) Ablations that would attribute the gains: (a) plain GBP on the PGO and BA benchmarks; (b) the same two-level solver with a block-Jacobi or Gauss-Seidel smoother instead of GBP. Results here could change my assessment of Weakness 1.

  4. (Clarification) For the size of the advantage: (a) PGO timings against a supernodal or multithreaded direct solver (CHOLMOD supernodal, or GTSAM), at equal thread counts; (b) for BA, time-to-target profiles at shared cost targets, as in the RootBA and PowerBA papers, with failures to reach the target counted.

  5. (Clarification) Theory and implementation.

  • Thm B.21 requires running H-GBP until the relative-residual rule (27) holds, but the PGO runs use fixed cycle and sweep budgets (L1609-1611). Is (27) met?
  • The implementation freezes the precisions at a finite tolerance (App. D.1). By Lemma B.8's own algebra, this adds a forcing term [Fa(Λˉ)−Λˉa]xi⋆[F_a(\bar\Lambda)-\bar\Lambda_a]x^\star_i to each sweep, so the limiting output can be biased. Is this checked or bounded?
  • Is the εI\varepsilon I stabilization of the Schur denominators (Remark after Assumption B.2) consistent with the AA, bb used for the residual and the coarse solve?
  • What is the nonlinear update for BA and for robust PGO (damping rule, robust reweighting)?
  1. (Clarification, minor)
  • App. A.2 says the variables are two-dimensional (L816), but Fig. 8 uses three-dimensional pose errors. Which is it?
  • How was the Cubicle graph "PSD-conditioned" (L1601)?
  • Showing the absolute times of Table 6 next to Fig. 5(c) would make clear that the panel shows lower sensitivity to fill-in, while Cholesky remains faster in absolute terms on all five variants.
  1. (Future-work suggestion; does not affect my score) The motivation is distributed spatial inference (L52-53), but the implementation is shared-memory with a direct coarse solve (L1489-1495). A distributed or message-passing coarse level, and an evaluation of communication cost, would test the setting the paper argues for.
1 comment
AuthorsOpenReview ↗

Reviewer kiY5 Question 5

5. Theory and Implementation

Q: Thm B.21 requires running H-GBP until the relative-residual rule (27) holds, but the PGO runs use fixed cycle and sweep budgets (L1609-1611). Is (27) met?

A: Yes, (27) is met. All 180 inner solves across nine PGO datasets numerically satisfy the residual inequality in Eq. (27) with a common tolerance ηˉ=0.88\bar\eta=0.88, evaluated before nonlinear line search.

Here ηt\eta_t is the relative linear-system residual in the At−1A_t^{-1} norm; γ⋆\gamma_\star measures the normalized difference between the true Hessian and the Gauss-Newton matrix at a stationary point.

DatasetMax. ηt\eta_t (20 solves)Estimated γ⋆\gamma_\star(1−γ⋆)/(1+γ⋆)(1-\gamma_\star)/(1+\gamma_\star)
FR0790.7104020.0365140.929545
FRH0.7171555.829e-60.999988
M35000.7472820.0418240.919711
ParkingGarage0.8748480.0269220.947567
Sphere0.1682250.0318050.938350
Cubicle0.6796420.0619200.883382
Grid0.0947820.0524360.900353
Globe10k0.2045260.0254940.950280
Globe100k0.1016750.0272010.947039

The curvature estimates use the true Huber Hessian and the same gauge. Across all datasets, max⁡tηt=0.874848<0.88<0.883382\max_t\eta_t=0.874848<0.88<0.883382, where the last value is the smallest estimated admissible threshold.

Q: The implementation freezes the precisions at a finite tolerance (App. D.1). By Lemma B.8's own algebra, this adds a forcing term Fa(Λˉ)−Λˉaxi⋆F_a(\bar\Lambda)-\bar\Lambda_a x^\star_i to each sweep, so the limiting output can be biased. Is this checked or bounded?

A: Finite-tolerance freezing can introduce bias. For a frozen linear H-GBP cycle, let ee collect the mean and message errors, TT be the cycle matrix, and ff be the forcing accumulated over one cycle. Then e+=Te+fe^+=Te+f. If ρ(T)<1\rho(T)<1, precision freezing introduces a bounded steady-state perturbation, e∞=(I−T)−1fe_\infty=(I-T)^{-1}f. We checked this empirically: disabling freezing on all nine PGO datasets changed final costs by at most 1.64×10−81.64\times10^{-8} relatively; tightening the BA precision tolerance to 10−1210^{-12} with a 512-sweep cap changed final costs by at most 5.39×10−75.39\times10^{-7} across ten datasets. These differences are negligible at the reported benchmark accuracy. Precision freezing is therefore a practical accuracy-efficiency trade-off, similar in purpose to choosing solver tolerances or floating-point precision: it reduces repeated precision computations while preserving the measured solution quality.

Q: Is the ϵ\epsilon stabilization of the Schur denominators (Remark after Assumption B.2) consistent with the A,bA,b used for the residual and the coarse solve?

Yes. PGO uses ϵ=10−7\epsilon=10^{-7} for all SE2 and ϵ=10−10\epsilon=10^{-10} for all SE3. All BA uses scale-aware stabilization, ϵ=10−12max⁡(1,max⁡i∣Dii∣)\epsilon=10^{-12}\max(1,\max_i|D_{ii}|), to keep the perturbation small relative to the local Schur denominator while maintaining a floor.

Q: What is the nonlinear update for BA and for robust PGO (damping rule, robust reweighting)?

BA uses Levenberg–Marquardt damping adjusted by the actual-to-predicted cost reduction, with Armijo backtracking of the joint camera–point update and no robust loss. Robust PGO recomputes Huber weights wf=min⁡(1,5/rf⊤Ωfrf)w_f=\min(1,5/\sqrt{r_f^\top\Omega_f r_f}) at each relinearization, using step-halving until the Huber objective does not increase.

Reviewer_dhoROpenReview ↗
Rating
4(+1)
Confidence
4(+1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper aims to accelerate Gaussian belief propagation by combining local message passing with coarse correction. Variables are grouped, and local eigenvectors define a smaller problem that captures errors which ordinary message passing removes slowly. The authors analyze the resulting iteration and evaluate it on pose graph optimization and bundle adjustment.

Critical strengths

s1: The motivation is convincing. Local updates can smooth differences between neighboring variables, but coordinating distant regions takes longer. A coarse correction is a sensible response to that problem. The algorithm follows naturally from this observation.

s2: I particularly appreciate the treatment of message inconsistency after coarse correction. Updating beliefs while preserving messages creates a complication that cannot simply be ignored. The separate analysis of the next message update gives the theoretical contribution real substance.

s3: The experiments consider solution quality alongside runtime. This matters. The larger pose graph results show substantial acceleration without an apparent loss in the reported final objective, and the bundle adjustment results suggest that the approach has practical value.

Critical weaknesses

w1: The theory provides a convergence criterion, but it does not explain when the proposed coarse space will satisfy that criterion or improve on ordinary belief propagation. That is still largely an empirical observation. What properties of the grouping and retained eigenvectors make acceleration likely? A more concrete answer would strengthen the main argument.

w2: There is a gap between the guarantees and the implementation. The bundle adjustment construction does not satisfy the theoretical assumptions, as the authors acknowledge. The nonlinear guarantee also requires an inner residual tolerance, while the pose graph experiments use fixed iteration budgets. It would help to show whether those budgets actually meet the required tolerance.

w3: I am not fully convinced by the runtime comparisons as currently presented. Some baselines retain different objectives, initialization procedures, or timing boundaries. Rescoring the final solutions helps, but does not resolve those differences. How much acceleration remains when the methods solve the same objective from the same starting point and stop at comparable accuracy?

w4: The implementation also benefits from precision caching and specialized numerical operations. These are sensible engineering choices, but their contribution is difficult to separate from the hierarchy itself. Ordinary belief propagation should receive the same optimizations in the comparison. A breakdown of coarse construction, coarse solving, and fine updates would also make the scaling argument easier to assess.

Questions for authors

See above comments. I lean toward acceptance. The analysis of the coupled message dynamics is meaningful, and the experimental gains are substantial. My main reservations concern the connection between the guarantees and the implemented solver, together with the fairness of some runtime comparisons.

6 comments
AuthorsOpenReview ↗

Response to Reviewer dhoR's Comment

We sincerely thank Reviewer dhoR for recognizing the contributions of H-GBP and for the insightful and detailed feedback. We particularly appreciate your recognition of our motivation rooted in low-frequency error modes and our simple yet effective solution. As you highlighted, addressing message inconsistency and achieving state-of-the-art solver performance across multiple datasets are indeed two key strengths of our work.

AuthorsOpenReview ↗

Reviewer dhoR W1&W2

W1. What makes the grouping and retained eigenvectors effective?

You asked a very insightful and constructive question. The philosophy here is that the coarse space should represent the errors left by local messages. Groups should preserve strong connections. Within each group, the lowest eigenvectors of its internal precision matrix, HgH_g then represent collective changes with low local energy.

Let's make the first linearization of Grid data as an example: 8,000 SE3 poses and 22,236 factors. All rows below use damping 0.3, k=50k=50. There are 400 groups. Plain GBP has ρ(Q⋆)50=0.999996\rho(Q^\star)^{50}=0.999996. The accuracy target is relative AA-norm error 10−610^{-6}. NR means the target was not reached within 30,000 sweeps.

Grouping / retained modesRank per groupH-GBP ρ(M50)\rho(M_{50})Fine sweeps to targetTime to target [s]
Contiguous / lowest30.999996NRNR
Contiguous / lowest60.7400391,5000.967
Contiguous / lowest120.4939327500.929
Contiguous / lowest240.3817036501.102
Graph Voronoi / lowest120.4991937500.900
Random grouping / lowest120.999996NRNR
Contiguous / random modes120.999996NRNR
Contiguous / highest modes120.999996NRNR

Two observations explain the HGBP general design. Changing the grouping or the retained modes removes the gain even at the same rank. Also, increasing rank from 12 to 24 reduces sweeps but increases total time. Coarse accuracy and coarse cost must be balanced.

This choice relies on a local approximation property. For PSD factors, if the first discarded local eigenvalue satisfies β=min⁡gλrg+1(Hg)>0\beta=\min_g\lambda_{r_g+1}(H_g)>0, then ηt=∥rt∥At−1∥bt∥At−1\eta_t = \frac{\Vert r_t\Vert_{A_t^{-1}}}{\Vert b_t\Vert_{A_t^{-1}}}. Thus the retained modes represent low-energy errors well. The spectral experiments test how this property interacts with the GBP message dynamics.

A family admits a strict acceleration guarantee. Consider homogeneous periodic 2D/3D grids with scalar Gaussian difference factors, uniform positive edge and unary precisions, and identical synchronous damping 0<α<10<\alpha<1. A full-column-rank coarse space containing the constant mode give ρ(Mk)<ρ(Q⋆)k\rho(M_k)<\rho(Q^\star)^k for all sufficiently large kk. Any connected group formulation that retains their lowest local mode meet this condition.

Let dd be the graph degree, w,ν>0w,\nu>0 the edge and unary precisions, and λ⋆\lambda^\star the stationary message precision. Set a=w/[w+ν+(d−1)λ⋆]a=w/[w+\nu+(d-1)\lambda^\star]. The unique dominant message mode is constant, with eigenvalue q=α+(1−α)a(d−1)q=\alpha+(1-\alpha)a(d-1). Coarse correction removes its mean component but leaves the memory multiplier s=α−(1−α)as=\alpha-(1-\alpha)a. The remaining modes decay faster, so ρ(Mk)/qk→∣s∣/q<1\rho(M_k)/q^k\to |s|/q<1.

For example, with w=1w=1, ν=10−3\nu=10^{-3}, α=0.3\alpha=0.3 and one constant mode per connected group:

Periodic gridGroupskkGBP ρ(Q⋆)k\rho(Q^\star)^kH-GBP ρ(Mk)\rho(M_k)
6×66\times6Six row groups200.9930280.066341
4×4×44\times4\times4Eight groups of eight nodes200.9965070.159504

These scalar examples give concrete sweep budgets. The sufficient threshold, again, depends on the graph and coarse space.

W2. Do the fixed PGO budgets meet the required inner tolerance?

Yes: all 180 inner solves across the nine PGO datasets numerically satisfy Eq. (27).

We measured rt=bt−AtΔxtr_t=b_t-A_t\Delta x_t before nonlinear line search and formed ηt=∥rt∥At−1/∥bt∥At−1\eta_t=\|r_t\|_{A_t^{-1}}/\|b_t\|_{A_t^{-1}}. We also estimated γ⋆\gamma_{\star}, the normalized difference between the true Hessian and the Gauss-Newton matrix at a high-accuracy stationary point.

Each row reports the maximum residual ratio over all 20 linearizations:

DatasetMaximum ηt\eta_tEstimated γ⋆\gamma_\star
FR0790.7104020.036514
FRH0.7171555.829e-6
M35000.7472820.041824
ParkingGarage0.8748480.026922
Sphere0.1682250.031805
Cubicle0.6796420.061920
Grid0.0947820.052436
Globe10k0.2045260.025494
Globe100k0.1016750.027201

The same tolerance works across all datasets: max⁡tηt=0.874848<0.88<0.883382\max_t\eta_t=0.874848<0.88<0.883382. The final value is the smallest estimated admissible threshold.

For BA, the message model and the target system have distinct roles. H-GBP supplies preconditioning through a sparse Gaussian camera model after point elimination. FCG evaluates corrections using the full Schur operator. Nonlinear acceptance uses the original reprojection objective. The sparse message model does not replace that objective. H-GBP's empirical BA performance is distinguished from the conditional guarantee above.

AuthorsOpenReview ↗

Reviewer dhoR W3

W3. How much acceleration remains at the same objective, initialization, and accuracy?

You are correct to notice that some objectives and initializations differ. We intentionally retain method-specific choices that matter for each baseline’s performance. Our aim is to let each baseline perform at its best, providing the strongest comparisons for H-GBP.

To clarify the same and differences: All methods receive the same graphs, including identical Cubicle preprocessing, and all reported PGO costs use the same full-information Lie-log quadratic metric. H-GBP, g2o-Cholesky, g2o-PCG, and Schwarz use Huber-5 and the odometry poses as initialization (this is standard in SLAM settings). In the H-GBP appendix, Cycle initializes its edge variables from measurements and retains its quadratic loss. After further experiments, we found that on successful datasets, the final Huber-5 and quadratic scores are identical, while the other dataset still fails. So, short conclusion: we can unify all baselines except AMM-PGO with the same Huber-5 objective.

Preserving AMM's native initialization avoids weakening the baseline. AMM uses its native chordal objective and initialization (very distinct). ** We changed only its initialization, keeping the optimizer and iteration budgets fixed. These are AMM's own final objectives, not rescored costs:

DatasetAMM iterationsFrom supplied posesFrom native chordal initialization
M3500300413.599193.939
Cubicle3008,535.1682,054.133
Grid203,484,889.20784,343.500
Globe10k3006,079.5716,079.652

Starting AMM from odometry requires 367 updates on Grid to come within 0.5% of its chordal-initialized 20-update objective. M3500 and Cubicle still miss their corresponding targets after 1,000 updates.

BA: time-to-target comparisons with 16 CPU threads.

Following the shared-target definition used by RootBA and PowerBA, we use Fτ=F∗+τ(F0−F∗)F_\tau=F_*+\tau(F_0-F_*), where F0F_0 is the common initial cost and F∗F_* is the best accepted cost across all five methods within 20-outer budget. All methods use the same BAL inputs and initial estimates.

At τ=0.001\tau=0.001, H-GBP reaches the shared target fastest on all ten datasets, with 1.9-29.5x speedups over the fastest other successful method. It also leads on all ten at τ=0.1,0.01,0.003\tau=0.1,0.01,0.003 (see Response 1 to Reviewer GKYp).

Each entry is time [s] / attained cost / outer index, measured at the first accepted iterate reaching the target. NR entries show the final cost and actual outer count.

DatasetH-GBPCeres SparseCeres IterativeRootBA-QRPowerBA
Ladybug490.024 / 27,906.647 / 30.102 / 26,921.487 / 30.108 / 27,003.924 / 30.111 / 27,001.693 / 30.070 / 28,228.577 / 5
Venice890.165 / 596,640.936 / 31.431 / 574,726.060 / 21.027 / 597,892.647 / 21.302 / 594,280.597 / 30.737 / 599,948.486 / 4
Final930.077 / 293,534.994 / 20.823 / 291,117.882 / 20.565 / 291,745.119 / 20.443 / 291,733.605 / 20.267 / 295,306.113 / 2
Trafalgar2570.091 / 221,984.288 / 20.601 / 226,863.025 / 10.693 / 238,032.053 / 30.678 / 239,163.898 / 30.194 / 235,252.881 / 2
Dubrovnik3560.328 / 1,135,850.355 / 24.694 / 1,034,613.339 / 22.691 / 1,140,390.567 / 32.010 / 1,139,194.111 / 21.408 / 1,140,688.937 / 3
Final3940.427 / 602,534.281 / 62.924 / 603,171.058 / 21.901 / 601,347.566 / 34.659 / 602,304.476 / 3NR / 611,100.526 / 20
Ladybug17230.839 / 792,647.863 / 719.001 / 814,354.152 / 123.295 / 818,456.203 / 84.003 / 789,310.503 / 82.070 / 859,009.613 / 13
Venice17782.502 / 3,717,188.570 / 630.608 / 3,784,301.449 / 2NR / 6,932,848.797 / 2044.662 / 3,736,936.567 / 144.697 / 3,604,056.808 / 3
Final30681.716 / 3,323,260.243 / 7104.363 / 3,399,098.143 / 11NR / 3,452,710.684 / 2050.633 / 3,356,666.866 / 9NR / 3,520,615.186 / 20
Final45853.673 / 10,999,534.350 / 4454.010 / 11,155,126.575 / 13NR / 13,021,323.891 / 2072.964 / 10,882,285.457 / 710.897 / 10,847,127.204 / 6

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Rebuttal Summary

We appreciate all reviewers’ (dhoR, kiY5, GKYp) valuable and constructive feedback. Here we briefly summarize their views and our response/improvement.

All reviewers recognize our observation of GBP error mode and HGBP’s simple&effective principle of abstraction and recovery. Reviewer dhoR and GKYp appreciate the message preserving innovation while reviewer kiY5 also appreciate the exact operator analysis. The authors

  1. Clarified where HGBP is theoretically (dhoR, kiY5) gauranteed or experimentally (kiY5, GKYp) to be faster than GBP.
  2. Showed that fixed PGO budgets meet the required inner tolerance (Eq27, dhoR, kiY5).
  3. Added more ablations that furthur supoort the algorithm. E.g. replacing smoothers (with jacobi, gauss seidal) or replacing message preservation hurts an amount of datasets (kiY5).

As a general factor graph solver, reviewers admire the experiements in PGO(SE2&Se3) and BA. They admit the leading speed and competitive solution quality as practically valueble. We

  1. Added BA comparison experiments under unified accuracy criterions (dhoR, kiY5, GKYp) following root-BA. HGBP is still SOTA by a large margin.
  2. Clarified concerns in terms of initialization/objective setting, wall-time breakdown (dhoR), and spectral radius comparison (kiY5).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.