{"id":"fc73b9ed-4d3d-4d70-9ad2-9bfa89bf5e6a","arxiv_id":"2412.09584","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A GPU-accelerated branch-and-bound planner over neural dynamics models uses adapted CROWN bounds to prune subdomains and beat sampling-based and MIP baselines on long-horizon manipulation tasks.","lead":"BaB-ND plans robot motions by systematically dividing the action space into branches and using neural-network verification bounds to prune unpromising branches, then searches the most promising ones with sampling. It reports better long-horizon results than CEM, MPPI, and MIP on contact-rich manipulation simulations and real-robot executions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The empirical search-integrated lower bounds in Section 3.2 are not valid relaxations, so pruning can discard the subdomain containing the optimum; the paper never measures how often this occurs, which leaves the 'systematic exploration' claim unsupported.","rationale":"The paper's central contribution is a practical planner that outperforms sampling-based methods on open-loop objectives and scales better than MIP. I read the evidence for that practical claim as credible: the paper includes multiple manipulation tasks, real-world execution, ablations, and scalability comparisons, and the limitations section honestly acknowledges dependence on model accuracy and the underlying search algorithm. However, the 'systematic and strategic exploration' framing rests on the branch-and-bound pruning step, and that step is sound only if the estimated lower bounds are true lower bounds. Section 3.2 explicitly relaxes soundness and uses empirical pre-activation bounds from sampling, so invalid pruning is a real possibility. The reader identified the same load-bearing assumption, and I agree. A concrete test with known optima can settle whether invalid prunes actually occur in the tested regimes. If they never occur, the concern is mostly theoretical; if they do occur, the paper should be read as presenting a strong heuristic planner rather than a planner with a pruning guarantee. Either way the practical contribution remains, but the strength and interpretation of the central claim change, so a CONDITIONAL verdict is appropriate rather than an outright rejection or unconditional acceptance.","tokens_in":51879,"tokens_out":3540,"duration_ms":42835,"concrete_test":"On the synthetic function of Section 4 (or on a small MIP-solvable ReLU dynamics instance), compute the true global optimum by dense grid search or by MIP. Instrument Algorithm 1 to record every pruned subdomain Cj, and for each pruned Cj evaluate min_{u in Cj} f(u) by exhaustive enumeration or MIP. Compare this true minimum with the current f* at the moment of pruning. Report the fraction of pruned subdomains whose true minimum is below f* and, in particular, whether the subdomain containing the global optimum is ever pruned. If this fraction is zero across all small instances, the concern is mitigated; if nonzero, the paper should state that pruning is heuristic and remove the 'cannot yield better solutions' language.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Algorithm 1's Pruner removes any subdomain whose estimated lower bound f*_Ci is above the current best upper bound f*. Section 3.2 states that a strictly sound lower bound is not required and that the pre-activation bounds used in Approach 2 are computed as min/max over M samples and 'may underestimate the actual bounds.' If the empirical pre-activation ranges are narrower than the true ranges over a subdomain, the CROWN linear relaxation is not a valid lower bounding function, so the computed f*_Ci can exceed the true minimum of f on Ci. Pruning then removes promising or even optimal subdomains. This does not necessarily invalidate the demonstrated practical improvements, since BaB-ND may still be a strong heuristic, but it breaks the branch-and-bound guarantee language: the paper claims to discard 'subdomains that cannot yield better solutions' and to 'systematically and strategically explore the action space.' The ablation in Table 4 shows that the bounding component helps performance, but it does not test whether pruning decisions are ever incorrect or how much of the reported gain depends on an invalid prune.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents BaB-ND, a GPU-accelerated branch-and-bound framework for motion planning over neural dynamics models. The planner partitions the action space into subdomains, uses a modified CROWN bound-propagation procedure with early stopping and search-integrated empirical intermediate-layer bounds to estimate subdomain lower bounds, and employs a CEM-based searching component to find high-quality action sequences. The method is evaluated on a synthetic high-dimensional nonconvex problem, four simulated manipulation tasks (pushing with obstacles, object merging, rope routing, object sorting), and real-world execution of these tasks, with comparisons against GD, MPPI, CEM, and a MIP baseline, plus scalability and ablation analyses.","tokens_in":52214,"tokens_out":6859,"duration_ms":65605,"significance":"If the empirical claims hold, the paper delivers a practical planner that scales to neural dynamics models with over 500K parameters and planning horizons up to 20 while outperforming sampling-based baselines on long-horizon, contact-rich manipulation tasks. The framework's support for both MLP and GNN dynamics, its real-world closed-loop validation, and its explicit runtime comparison against MIP are notable strengths. The main weakness is that the lower bounds used for pruning are explicitly unsound, which undermines the 'systematic exploration' and 'cannot yield better solutions' claims as stated. With the soundness issue addressed or the claims appropriately hedged, the work would be a solid empirical contribution to model-based planning.","major_comments":[{"comment":"The methodology states that 'We can always prune subdomain Cj if its f*_Cj > f* ... since, in Cj, there is no solution better than the current best objective f*' (Section 3, near Eq. 1). This statement is only valid if f*_Cj is a genuine lower bound on min_{u in Cj} f(u). However, Section 3.2 explicitly says 'a strictly sound lower bound is not required,' and Approach 2 computes pre-activation bounds as min/max over M samples from searching, which 'may underestimate the actual bounds.' When these empirical ranges are tighter than the true ranges over the subdomain, the CROWN linear relaxation in Lemma B.1 is not a valid lower bounding function, so f*_Cj can exceed the true minimum. The pruner in Algorithm 1 (line 13) and Algorithm 2 (line 12) can then discard subdomains containing the optimal or a better trajectory. The paper provides no measurement of how often such incorrect pruning occurs or how much of the reported gain depends on invalid prunes. Because the central claim is that BaB-ND 'systematically and strategically explores the action space,' this inconsistency is load-bearing. Please either make the bounds sound (e.g., compute true interval bounds on each subdomain, or replace sample-based pre-activation bounds with verified ones) and retain the pruning guarantee, or explicitly reframe the pruner as a heuristic and remove the 'always' and 'cannot yield better solutions' language. In either case, add an experiment on small problems where the true optimum is computable that reports the precision of pruning (fraction of pruned subdomains whose true minimum was actually above the pruning threshold).","section":"Section 3 and Section 3.2"},{"comment":"The empirical comparison in Figure 6 and Tables 1 and 7 reports point values without error bars, standard deviations, or statistical tests over test cases or seeds. The main claim is that BaB-ND 'consistently outperforms' all baselines, but in several settings the reported differences are small (e.g., Table 7a: MPPI 26.9970 vs. Ours 26.4841 for (134.2K,20); Table 2: all methods nearly identical on MIP-solvable cases). Please report variance (medians with interquartile ranges as in Figure 4, or mean ± std over seeds) and, where possible, paired tests across the test cases. Additionally, the main experiments do not report wall-clock time or the total number of forward dynamics evaluations used by each method; the only compute-matched comparison appears in the scalability section (Appendix C.1). Without this information the reader cannot determine whether the open-loop improvements stem from systematically better search or from a larger computational budget.","section":"Section 4 and Appendix C.1"}],"minor_comments":[{"comment":"The number of samples M used in the search-integrated bounding is not specified. Please state how M is chosen and whether it is included in the hyperparameter sensitivity analysis.","section":"Section 3.2"},{"comment":"The line 'P ← P S Pruner(...)' in Algorithm 1 (and similarly in Algorithm 2) appears to be a typesetting error; it should read 'P ← P ∪ Pruner(...)'.","section":"Algorithm 1 and Algorithm 2"},{"comment":"The caption states 'GD is excluded from testing due to its poor open-loop performance,' but Table 3 in the appendix includes GD in the comparison. This is acceptable, but the main text should clarify that GD was excluded only from real-world deployment, not from all analyses.","section":"Section 4, Figure 6 caption"},{"comment":"Please clarify the relationship between the sample budget inside BaB-ND's search component (CEM) and the sample counts of the standalone baseline methods, so the reader can assess whether the comparisons are compute-fair.","section":"Appendix D.6"},{"comment":"The hyperparameter analysis in Table 5 varies one hyperparameter at a time but does not report variance across runs or seeds. Adding such variation would strengthen the claim that performance is insensitive to these choices.","section":"Section C.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong empirical contribution, but the unsoundness of the bounding/pruning step is underplayed. The authors should be asked to either restore soundness or clearly reposition the method as a heuristic pruner, and to provide a diagnostic on pruning precision. The empirical claims would also benefit from variance reporting and compute-budget transparency."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a useful empirical paper. BaB-ND consistently finds lower-cost open-loop plans than CEM, MPPI, and projected gradient descent across four manipulation tasks, and it scales to models and horizons where MIP fails. The real-world executions on pushing, merging, rope routing, and sorting give the results more weight than a simulator-only study. The synthetic example with a known optimum is a good sanity check, and the ablations on branching and bounding components show the pieces matter. I believe the practical contribution: if you need a planner for long-horizon tasks with learned neural dynamics, this is a strong candidate.\n\nThe soft spot is the one the paper itself names in Section 3.2: a strictly sound lower bound is not required, and the search-integrated empirical bounds \"may underestimate the actual bounds.\" That is a genuine wrinkle. The Pruner discards any subdomain whose estimated lower bound exceeds the current best upper bound. If those lower bounds are not valid relaxations, you can prune the subdomain containing the true optimum. The paper never measures how often this happens, even though it has the tools to do so (the synthetic example, or small MIP-solvable cases). So the phrases in Section 1 about pruning \"subdomains that cannot yield better solutions\" and \"systematically and strategically exploring\" are stronger than what the algorithm actually guarantees. This is not a fatal flaw in the empirical story, but it is a mismatch between the framing and the method. I would ask the authors to quantify pruning errors on problems with known optima and to report variance or trial counts for the closed-loop results (Figure 6 and Table 1 currently show single numbers).\n\nI do not think the central argument collapses. The planner works better than the baselines in the tested settings, and the authors are transparent about the unsound bound. It is a strong heuristic, honestly labeled, with one overclaimed adjective. For that reason I would definitely give this a serious peer review (and it has already passed one at ICLR). My recommendation: engage with the paper, but treat it as a demonstration of a practical heuristic, not as a systematic search with optimality guarantees.","headline":"A practical, well-tested heuristic for planning over neural dynamics, with an honest but under-explored caveat: the pruning step is not sound, so the 'systematic exploration' framing overstates the guarantee.","tokens_in":52630,"tokens_out":1902,"would_cite":true,"duration_ms":22297,"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":"Long-horizon manipulation planning can be solved by branch-and-bound over neural dynamics, outperforming sampling-based planners and scaling beyond mixed-integer programming.","keywords":["branch-and-bound","motion planning","neural dynamics models","bound propagation","CROWN","manipulation","long-horizon planning","GPU acceleration"],"falsifier":"On a small problem with a known optimum, such as the paper's synthetic $f(u)=\\sum_i (5u_i^2 + \\cos(50u_i))$ with $d=2$, run BaB-ND with a small sample count $M$ for the search-integrated bounds and record every pruned subdomain; if the known global optimum lies inside any pruned subdomain, or if the reported lower bound on a subdomain containing the optimum exceeds the true minimum, the empirical bounds are not sound enough to guarantee the claimed systematic search.","tokens_in":1850,"feed_emoji":"🤖","tokens_out":2039,"duration_ms":70325,"temperature":0.7,"pith_summary":"This paper tries to establish that long-horizon manipulation planning over learned neural-network dynamics can be done systematically rather than by brute-force sampling. It proposes BaB-ND, a GPU-accelerated branch-and-bound planner that partitions the action space into subdomains, computes cheap objective lower bounds by adapting neural-network verification's bound propagation, and prunes subdomains that cannot beat the current best plan. The payoff would be a planner that finds better open-loop trajectories than CEM, MPPI, and gradient descent on contact-rich tasks, while scaling to neural dynamics models that mixed-integer programming cannot handle. The paper demonstrates this on pushing with obstacles, object merging, rope routing, and object sorting, in simulation and on a real robot, using both MLP and graph-neural-network dynamics models. A sympathetic reader would take the central claim as: systematic search guided by approximate bounds is the practical middle ground between sampling and exact optimization for neural dynamics planning.","feed_headline":"Branch-and-bound beats sampling in neural-dynamics planning","feed_subtitle":"A GPU planner splits the action space, prunes with verification-style bounds, and wins at pushing, rope routing, and sorting.","key_machinery":"The central object is the branch-and-bound tree over the action-sequence box $\\mathcal{C} = [\\underline{u}, \\overline{u}]^d$. Branching selects $n$ subdomains per iteration, ranking them by their stored lower and upper bounds and splitting each along the dimension that maximizes $(\\overline{u}_j - \\underline{u}_j) \\, |n^{\\mathrm{lo}}_j - n^{\\mathrm{up}}_j|$, i.e., dimensions with large remaining range and imbalanced top samples. Bounding adapts CROWN linear bound propagation: propagation stops early at chosen intermediate layers, and the pre-activation bounds needed to relax ReLUs are taken as min/max over $M$ samples from the search rather than computed recursively; this makes the bound cheap enough to scale, though the paper states that a strictly sound lower bound is not required. Searching runs CEM inside each subdomain and returns feasible upper bounds, and any subdomain whose lower bound exceeds the global best upper bound is pruned.","core_discovery":"The paper's central claim is that the planning problem $\\min_{u \\in \\mathcal{C}} f(u)$ over a neural dynamics model can be solved much better by branch-and-bound than by sampling alone, and much more scalably than by MIP. The authors argue that because planning wants a concrete near-optimal action sequence rather than a verified lower bound, the branch-and-bound machinery from neural network verification can be redirected: branching heuristics that split on dimensions where good sampled actions are concentrated, bound estimates that stop propagation early and reuse sample statistics as intermediate bounds, and a CEM search inside each surviving subdomain. With this combination, they report consistently lower open-loop objectives than GD, MPPI, and CEM on four contact-rich tasks, and closed-loop real-robot performance that tracks the planned advantages. On scalability, BaB-ND solves problems with a 530K-parameter dynamics model and horizon 20, where MIP fails to return a solution within 300 seconds on most of the 36 tested settings.","pith_inferences":["A consequence the authors leave implicit is that replacing the empirical bounds with sound interval bounds would turn the same algorithm into a certifying planner that could return a global optimality gap, at the cost of the quadratic propagation they avoid.","The pruning behavior suggests the method is closer to adaptive mesh refinement than to exact branch-and-bound; a testable extension is to measure the gap between the estimated lower bound and the true minimum as the sample count $M$ grows, and to choose $M$ per subdomain.","The splitting heuristic, which uses the distribution of top samples to pick a bisection dimension, could transfer to other nonconvex neural-network optimization problems where feasible solutions matter more than certificates, such as robust control synthesis."],"forward_implications":["On the four benchmark tasks, BaB-ND reports better open-loop planning objectives than gradient descent, MPPI, and CEM, and the better plans transfer to better real-robot closed-loop final costs or success rates.","On the synthetic high-dimensional objective, BaB-ND reaches the optimum on 98 to 100 of 100 dimensions at $d=100$, while the sampling baselines saturate at suboptimal values.","MIP-based planning solves only 6 of 36 tested settings within 300 seconds, while BaB-ND handles a 530K-parameter dynamics model with horizon 20, with branching and bounding runtime growing only slowly with model size.","The framework is architecture-agnostic: it works with MLP dynamics and with graph-neural-network dynamics for multi-object and deformable-object tasks.","The pruning is aggressive: reported pruned-space size reaches roughly 0.995 of the domain, and the surviving selected subdomain shrinks to order $10^{-4}$ of the original volume."],"supporting_citations":[{"why":"Supplies the CROWN linear bound propagation that the bounding step early-stops and re-uses with empirical intermediate bounds.","marker":"Zhang et al. (2018)"},{"why":"Establishes branch-and-bound as a framework for neural-network objectives, the structure BaB-ND adapts to planning.","marker":"Bunel et al. (2018)"},{"why":"Beta-CROWN verification approach that demonstrates BaB plus bound propagation scales beyond MIP, motivating the planner's design.","marker":"Wang et al. (2021)"},{"why":"Fast alpha-beta-CROWN verifier whose branch-and-bound performance is the inspiration for combining branching with CROWN-style bounds.","marker":"Xu et al. (2021)"},{"why":"Provides general cutting planes for bound-propagation verification, supporting the modified bounding procedure's accuracy.","marker":"Zhang et al. (2022a)"},{"why":"Formulates model-based control with sparse neural dynamics as MIP, the exact baseline BaB-ND is compared against for scalability.","marker":"Liu et al. (2023b)"},{"why":"Defines the Cross-Entropy Method used as the searching subroutine inside each subdomain and as a baseline.","marker":"Rubinstein & Kroese (2013)"},{"why":"Defines MPPI, the sampling-based planning baseline that BaB-ND outperforms in the experiments.","marker":"Williams et al. (2017)"},{"why":"Provides the learned particle-dynamics architecture used for the graph-neural-network dynamics model in object sorting.","marker":"Li et al. (2018)"}],"fun_headline_variants":["Branch-and-bound outplans sampling for neural dynamics","GPU branch-and-bound prunes neural planning search","Verifier-style bounds speed up contact-rich motion planning","BaB-ND: Cut search space, then plan with neural dynamics","Smaller search, better plans: BaB-ND for neural dynamics"],"cache_read_input_tokens":54784,"weakest_assumption_plain":"Everything rests on the estimated lower bound being at or below the true best objective in each subdomain when the bound is used to prune; the paper lets the bound be computed from a finite sample of trajectories, so a subdomain containing the best action sequence could in principle be discarded if the sample-based bound overshoots the true minimum.","fun_headline_variants_meta":{"raw":{"variants":["Branch-and-bound outplans sampling for neural dynamics","GPU branch-and-bound prunes neural planning search","Verifier-style bounds speed up contact-rich motion planning","BaB-ND: Cut search space, then plan with neural dynamics","Smaller search, better plans: BaB-ND for neural dynamics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2827,"prompt_tokens":978,"completion_tokens":1849,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":1766}},"tokens_in":594,"tokens_out":1849,"duration_ms":13725,"temperature":1.0,"reasoning_tokens":1766,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:53:25.330080+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small problem with a known optimum, such as the paper's synthetic $f(u)=\\sum_i (5u_i^2 + \\cos(50u_i))$ with $d=2$, run BaB-ND with a small sample count $M$ for the search-integrated bounds and record every pruned subdomain; if the known global optimum lies inside any pruned subdomain, or if the reported lower bound on a subdomain containing the optimum exceeds the true minimum, the empirical bounds are not sound enough to guarantee the claimed systematic search.","supporting_citations":[{"cited_title":"Efficient neural network robustness certification with general activation functions","cited_arxiv_id":null,"evidence_quote":"Supplies the CROWN linear bound propagation that the bounding step early-stops and re-uses with empirical intermediate bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes branch-and-bound as a framework for neural-network objectives, the structure BaB-ND adapts to planning."},{"cited_title":"The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning","cited_arxiv_id":null,"evidence_quote":"Defines the Cross-Entropy Method used as the searching subroutine inside each subdomain and as a baseline."},{"cited_title":"Model predictive path integral control: From theory to parallel computation","cited_arxiv_id":null,"evidence_quote":"Defines MPPI, the sampling-based planning baseline that BaB-ND outperforms in the experiments."}],"review_version":1}