{"id":"268fa03c-94ac-4ead-9497-778b0dc427aa","arxiv_id":"2507.10290","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"TOP uses consensus ADMM with local closed-form updates so that one optimization step costs the same regardless of how many pieces the trajectory is split into, enabling very fast large-scale trajectory optimization.","lead":"This paper introduces TOP, a parallel trajectory optimizer that cuts a long drone path into many small segments, optimizes them at the same time, and stitches them together to keep the trajectory smooth. The authors report more than ten times faster optimization than the state of the art for 100-segment paths, and under one second for a 1000-segment, 538-meter flight, which matters for real-time long-horizon drone planning.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stopping tolerance in Eq. (23) scales with N, so the flat GPU runtime in Fig. 5 may reflect looser convergence rather than constant iteration count; the total-time claim needs an explicit test.","rationale":"I read the paper in good faith. The CADMM decomposition, the local coefficient update, slack projection, and quadratic projection are standard and appear internally consistent; the per-iteration O(1) claim with respect to N is credible. The weakest point is the leap from per-iteration cost to total runtime. The reader's weakest assumption identified the lack of an iteration-count bound in N, and I agree. My reading sharpens that concern with a concrete mechanism: Eq. (23) uses Er = Ed = N E, and since the primal and dual residual vectors concatenate N-1 boundary gaps, this tolerance relaxes the per-boundary convergence requirement by a factor of sqrt(N) as N grows. Therefore the near-flat runtime in Fig. 5 is not conclusive evidence that iteration count is N-independent; it may simply reflect earlier stopping for larger N. This does not invalidate the algorithmic core, but it does mean the conclusion's 'constant time complexity' and the strength of the speedup claims are conditional on an empirical check that is not reported. A direct rerun with a fixed per-boundary tolerance would settle the matter. I recommend keeping the reader's CONDITIONAL verdict, since the central per-iteration contribution appears sound but the total-complexity claim is not yet established.","tokens_in":12051,"tokens_out":7559,"duration_ms":98396,"concrete_test":"Re-run the GPU experiment of Fig. 5 with a fixed per-boundary tolerance instead of Eq. (23)'s N E scaling, e.g., set Er = Ed = sqrt(N) E (which keeps the allowed per-boundary gap constant), for N = 100, 500, 1000, and 5000 segments, and record iteration counts and wall time at both tolerances. If iteration count or wall time grows substantially with N under the fixed per-boundary tolerance, the total-constant-time claim fails; if both stay flat, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's per-iteration complexity claim is well supported: Eq. (20a) is a local dense solve of fixed size m(d+1), and all other updates are local and parallelizable. The load-bearing gap is the passage from the abstract's careful 'O(1) per iteration' to the conclusion's 'constant time complexity' and to Fig. 5's near-flat total runtime. That passage requires the number of CADMM iterations to be independent of N, which is not shown. More specifically, the stopping criterion in Eq. (23) sets Er = Ed = N E. The residuals r_p and r_d are Euclidean norms of vectors that concatenate N-1 per-boundary gaps, so under bounded per-gap error those norms grow like sqrt(N); setting the threshold to N E allows the per-boundary error to grow like sqrt(N) as N increases. Thus the reported flat runtime can occur even if iteration count and total work grow with N, because the algorithm is allowed to stop after weaker convergence. This does not threaten the per-iteration contribution, but it undermines the conclusion's total-constant-time claim and the strength of the experimental evidence for it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes TOP, a trajectory optimization framework that splits a differentially flat trajectory into N polynomial segments and solves the resulting consensus problem with the Consensus ADMM algorithm. Each segment is updated in parallel by solving a local dense linear system whose dimension depends only on the local polynomial degree and the local constraint count, not on N, which gives an O(1) per-iteration parallel complexity. The paper provides closed-form updates for linear and quadratic inequality constraints, a numerical L-BFGS variant for general convex constraints, CPU and GPU implementations, benchmark comparisons with GCOPTER, and a real-world quadrotor experiment with a 1000-segment trajectory. The central claims are a reduction from O(N) to O(1) per iteration and, in the conclusion and title, a move toward constant total time complexity.","tokens_in":12277,"tokens_out":11973,"duration_ms":133940,"significance":"The per-iteration complexity contribution is real and well supported by the update equations: Eq. (20a) is a local dense solve of size m(d+1), and the consensus, slack, projection, and dual updates are all local and parallelizable. If the total iteration count is independent of N, the GPU deployment would be a practically important step for long-horizon trajectory optimization. The paper also ships explicit closed-form projection rules and reports real-world validation, which are strengths. However, the total-complexity claim is not established, and the central update equation as printed contains a factor error relative to the augmented Lagrangian, so the manuscript needs substantive revision before the claims can be accepted.","major_comments":[{"comment":"The O(1)-per-iteration claim is supported by the local update structure, but the paper's stronger conclusion of \"constant time complexity\" requires the number of CADMM iterations K to be independent of N. This is not shown: Sec. III-D2 only states convergence as k goes to infinity, with no bound or empirical study of K versus N. The stopping criterion in Eq. (23) is also problematic for the experimental evidence: Er = Ed = N E, while the residuals in Eqs. (21)-(22) are norms of vectors with O(N) components. For bounded per-boundary error, those norms grow as sqrt(N), so the N-scaled tolerance allows the per-boundary error to grow as sqrt(N) as N increases. The flat GPU runtime in Fig. 5 may therefore reflect progressively looser convergence rather than constant iteration count. The authors should report iteration counts, final per-boundary residuals, and wall-clock time under a fixed per-boundary tolerance, and should soften the conclusion if K grows with N.","section":"Sec. III-D3, Eq. (23), and Fig. 5"},{"comment":"Equation (20a) is not the minimizer of the augmented Lagrangian in Eq. (5). Minimizing L_i with respect to c_i gives (2 eQ + ρ fM^T fM + ρ A^T A + ρ Σ Av^T Av)c = ρ fM^T(z - u) + ρ A^T(b - s - v) + ρ Σ Av^T(φ - w). As printed, the right-hand side of Eq. (20a) omits the factor ρ multiplying fM^T(z-u), A^T(b-s-v), and Av^T(φ-w). If the implementation follows the printed formula, the algorithm is not the advertised ADMM and the fixed-point equations do not match the optimality conditions; if the implementation includes ρ, the formula is a typo. This issue is load-bearing because Eq. (20a) is the core local update used in all experiments, and the authors should correct the formula and verify the implemented version against the derivation.","section":"Sec. III-D1, Eq. (20a)"},{"comment":"The local update in Eq. (20a) is an overdetermined least-squares problem: for polynomial degree 5 and d = 5 in the consensus notation, the matrix fM imposes m * 2d = 10m continuity constraints on m(d+1) = 6m coefficients. The statement in Sec. III-D1 that \"a solution exists due to the relaxation of the constraints in the augmented Lagrangian term\" is too vague: the linear solve always has a least-squares solution, but it does not necessarily satisfy the consensus constraints exactly at any finite iteration, and the fixed-point feasibility depends on the convergence of the ADMM iterations. In addition, the paper conflates two uses of the symbol d: the polynomial degree in Eq. (18) is set to 5, while eβ and fM include derivatives up to order d-1 = 4. The claim in Sec. III-D2 that continuity is enforced up to order 2p-1 = 5 for p = 3 is therefore not consistent with the published definitions; the authors should clarify the continuity order actually enforced and provide a precise solution-existence argument.","section":"Sec. III-D1 and Sec. III-D2"},{"comment":"The benchmark comparison in Table I reports objective costs that differ by roughly a factor of five between the proposed method (about 34-64) and GCOPTER (about 179-297), even though the authors state that both methods use the same constraints and initial values. If both methods converge to the same constrained minimum-control-effort problem, this discrepancy is surprising and suggests that either the problems are not identical or one of the methods has not converged to the reported tolerance. The paper should report constraint violations, stopping criteria, and iteration counts for both methods, not only time and objective cost, so that the claimed superiority in both efficiency and smoothness can be assessed fairly.","section":"Sec. IV-A1, Table I"}],"minor_comments":[{"comment":"The while condition is written as \"while ||r_p||_2 < E_r^2 and ||r_d||_2 < E_d^2\", which would exit immediately when residuals are small, i.e., it stops in the desired terminal region; the condition should be the negation, typically \"while ||r_p||_2 >= E_r^2 or ||r_d||_2 >= E_d^2\".","section":"Algorithm 1, line 3"},{"comment":"The row for Fixedρ(100) contains the value \"237789.0375e−13\", which appears to be a formatting error; the number of iterations for this row should be reported clearly.","section":"Table II"},{"comment":"The similarity metric uses M for the number of evaluation samples, while M is also used in Sec. III-D1 for the number of sample points per segment; this reuse of notation is confusing and should be disambiguated.","section":"Sec. IV-A2"},{"comment":"References [10] and [14] are the same LaValle technical report and should be consolidated to avoid duplication.","section":"References"},{"comment":"The definition g(x) = max{0, g0(x)}^2 should be written with braces as max{0, g0(x)}^2 to avoid ambiguity in the order of operations.","section":"Sec. III-C3, Eq. (15)"},{"comment":"The sentence \"the running speed of the algorithm framework has not been fully explored\" is vague; specify whether this refers to theoretical complexity, wall-clock time, or both.","section":"Sec. II-B"}],"recommendation":"major_revision","confidential_remarks":"The core per-iteration O(1) property is sound and the experimental deployment is valuable, but the total-complexity claim rests on an unexamined iteration-count assumption, and Eq. (20a) as printed does not match the augmented Lagrangian. The missing ρ factors are the kind of issue that could be a typo, but the authors should be asked to confirm the implemented update and to provide iteration-count and tolerance-normalized scaling data before the paper is accepted. The comparison with GCOPTER also needs a clearer statement of convergence criteria to justify the reported cost differences."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The per-iteration claim holds up. Eq. (20a) is a local dense solve whose size depends only on the segment's degree and constraint count, and every other update is local, so the parallel complexity per iteration is genuinely independent of N. That is a real improvement over GCOPTER's O(N) per iteration, and the GPU experiments with thousands of segments are impressive. The 1000-segment / 0.037s result is the kind of number that makes people in real-time planning sit up.\n\nWhat is new here is the specific CADMM reformulation that preserves high-order continuity, plus the closed-form projections for linear and quadratic inequality constraints. The derivation is clean and the convergence claim rests on Boyd's ADMM, so nothing is circular. Credit where it is due: this is a well-executed algorithmic paper with a checkable mathematical core.\n\nThe soft spots are real, though. The paper moves from \"O(1) per iteration\" to \"constant time complexity\" in the abstract and conclusion, and that step is not supported. There is no bound on iteration count versus N, and the stopping criterion in Eq. (23) sets Er = Ed = N E. Since the residuals are Euclidean norms of vectors that concatenate boundary gaps, the per-boundary error is allowed to grow with N. That can produce a flat runtime curve even when total work grows, so Fig. 5 is weaker evidence than it looks. The authors should report iteration counts as a function of N and rerun with a tolerance that does not scale with N. This is the load-bearing gap.\n\nThe comparison with GCOPTER also needs scrutiny. The objective costs differ by a factor of 5–10, which is suspicious; either the cost functions are different or the constraints are not actually identical. The speed comparison against a non-parallel method is fine, but it should be framed as parallel-vs-serial, not just algorithm-vs-algorithm. And there is no code release, which hurts reproducibility for a paper whose contribution is largely empirical.\n\nThese issues are not fatal to the per-iteration contribution, but they do mean the headline claim is overstated. I would send this to peer review, but with a major-revision request that focuses on iteration scaling, a fairer GCOPTER comparison, and ideally code. The work deserves serious referee time; it just needs to be honest about what is proven and what is observed.","headline":"Solid per-iteration O(1) decomposition, but the constant-time total claim is oversold and the stopping criterion scaling is the main load-bearing gap.","tokens_in":12847,"tokens_out":2727,"would_cite":true,"duration_ms":33121,"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":"The paper claims that splitting a trajectory into independently optimized segments under consensus constraints reduces the per-iteration cost of trajectory optimization from $O(N)$ to $O(1)$ in the number of segments.","keywords":["trajectory optimization","CADMM","consensus ADMM","parallel computing","GPU","motion planning","quadrotor","polynomial trajectory"],"falsifier":"Run the proposed algorithm with a fixed stopping tolerance that is not scaled by $N$, and measure the number of iterations to convergence for $N = 100$, $1000$, and $10000$ segments; if the iteration count grows with $N$, the total time complexity is not constant even though each iteration is $O(1)$.","tokens_in":11827,"feed_emoji":"🚁","tokens_out":11419,"duration_ms":110153,"temperature":0.7,"pith_summary":"This paper claims that trajectory optimization can be made parallel by splitting a long trajectory into many short segments and optimizing each segment independently under consensus constraints, so that the cost of a single optimization iteration no longer grows with the number of segments. The proposed framework, TOP, uses Consensus ADMM to enforce high-order continuity at segment boundaries through shared consensus variables, and gives closed-form updates for linear and quadratic inequality constraints. If correct, this reduces per-iteration complexity from $O(N)$ to $O(1)$ in the segment count, which would make very long trajectories (hundreds to thousands of segments) practical to optimize in real time on parallel hardware. The paper reports a tenfold speedup over a state-of-the-art baseline at one hundred segments and sub-second optimization for a thousand-segment drone trajectory on a GPU. It also notes that CPU runtime still grows slightly with segment count because of limited cores, with near-constant behavior appearing on GPU.","feed_headline":"Trajectory optimization drops to O(1) per iteration","feed_subtitle":"Splitting a long path into many small optimizations removes the linear-in-N bottleneck.","key_machinery":"The machinery is the Consensus Alternating Direction Method of Multipliers (CADMM) applied per segment. Each segment keeps its own polynomial coefficients as local variables; a consensus variable $z_i$ at each boundary is updated as the average of neighboring segment boundary derivatives (Eq. 20b), and the dual variables $u_i$, $v_i$, $w_i$ pull the local solutions toward consensus. The per-segment update of coefficients in Eq. (20a) inverts a matrix whose size depends only on the local polynomial degree and the local constraint count, not on the global number of segments $N$; this is what makes the per-iteration cost independent of $N$. Inequality constraints are converted into indicator-function terms and resolved by closed-form projections: a non-negativity projection for linear constraints and a Euclidean-ball projection for quadratic constraints, with a scalar rescaling of the projected vector.","core_discovery":"The central claim is that the constrained minimum-control-effort trajectory optimization problem, traditionally solved with methods whose per-iteration cost grows linearly (or worse) with the number of trajectory pieces, can be reformulated so that each iteration costs $O(1)$ per piece and $O(1)$ total with respect to $N$ on parallel hardware. The reformulation introduces a consensus variable at each shared boundary, so that continuity up to derivative order $d-1$ is enforced by averaging adjacent boundary states rather than by a global linear system. Every segment then solves a small local quadratic program, and inequality constraints are handled either by closed-form projections (linear and quadratic constraints) or by an L-BFGS numerical solve (general convex constraints). The authors demonstrate in simulation and on a real quadrotor that a trajectory with roughly one hundred segments can be optimized more than ten times faster than the GCOPTER baseline, and that on a GPU a one-thousand-segment trajectory can be optimized in tens of milliseconds.","pith_inferences":["Editorial inference: The $O(1)$ claim is per-iteration; the total runtime is only constant if the number of iterations to the stopping tolerance does not grow with $N$, a condition the paper does not establish.","Editorial inference: The closed-form projection for quadratic constraints (Eq. 14) could be reused for any convex set with a known Euclidean projection, so the approach may extend to ellipsoidal or polytopic safety regions without extra solver machinery.","Editorial inference: Because the stopping tolerance in Eq. (23) is scaled by $N$, a fair constant-time test would fix the tolerance and report iteration counts across $N$; otherwise a looser tolerance can hide linear growth in iterations."],"forward_implications":["Per-iteration cost becomes independent of the number of trajectory segments, so the bottleneck in large-scale planning shifts to memory bandwidth and parallel core count rather than to the optimization problem size.","On GPU hardware, trajectories with thousands of segments can be optimized in well under a second, enabling online re-planning of long-horizon paths for aerial robots.","High-order continuity up to derivative order $d-1$ is preserved at segment boundaries, so the method remains usable for agile multicopter control where smoothness is critical.","The closed-form projection for quadratic constraints gives a fast way to enforce velocity or acceleration limits without adding auxiliary optimization variables."],"supporting_citations":[{"why":"baseline method with $O(N)$ per-iteration cost that TOP compares against and whose optimality conditions motivate the segment-wise formulation.","marker":"[6]"},{"why":"Consensus ADMM algorithm and convergence theory that the parallel update scheme implements.","marker":"[8]"},{"why":"prior work splitting trajectory optimization into segments with CADMM; TOP extends it to high-order continuity and multicopter constraints.","marker":"[7]"},{"why":"TrajOpt, whose $O(N^2)$ NLP cost motivates the need for a faster parallel formulation.","marker":"[5]"}],"fun_headline_variants":["Parallel consensus cuts trajectory optimization complexity to O(1)","Trajectory optimization: O(N) to O(1) via parallel splitting","CADMM enables constant-time trajectory optimization per iteration","Split-and-parallel trajectory optimization achieves O(1) per step","From linear to constant: parallel trajectory optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim of constant total time rests on the assumption that the number of CADMM iterations needed to converge does not grow with the number of segments; the paper does not measure this, and its stopping tolerance is relaxed proportionally to $N$, which could mask such growth.","fun_headline_variants_meta":{"raw":{"variants":["Parallel consensus cuts trajectory optimization complexity to O(1)","Trajectory optimization: O(N) to O(1) via parallel splitting","CADMM enables constant-time trajectory optimization per iteration","Split-and-parallel trajectory optimization achieves O(1) per step","From linear to constant: parallel trajectory optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000339,"raw_usage":{"total_tokens":1878,"prompt_tokens":955,"completion_tokens":923,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":841}},"tokens_in":571,"tokens_out":923,"duration_ms":9850,"temperature":1.0,"reasoning_tokens":841,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:36:24.878018+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proposed algorithm with a fixed stopping tolerance that is not scaled by $N$, and measure the number of iterations to convergence for $N = 100$, $1000$, and $10000$ segments; if the iteration count grows with $N$, the total time complexity is not constant even though each iteration is $O(1)$.","supporting_citations":[{"cited_title":"Trajectory splitting: A distributed formulation for collision avoiding trajectory optimization,","cited_arxiv_id":null,"evidence_quote":"prior work splitting trajectory optimization into segments with CADMM; TOP extends it to high-order continuity and multicopter constraints."},{"cited_title":"Finding locally optimal, collision-free trajectories with sequential con- vex optimization","cited_arxiv_id":null,"evidence_quote":"TrajOpt, whose $O(N^2)$ NLP cost motivates the need for a faster parallel formulation."}],"review_version":1}