{"id":"c3532ea8-2d60-4b7c-ac4f-22bcce0fb175","arxiv_id":"2611.17221","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"A new CPU solver, FanCyQPALM, solves multi-horizon optimal control by factoring each scenario branch in parallel and combining branch contributions through a single shared root system.","lead":"This paper introduces FanCyqlone, a solver for multi-horizon optimal control that solves all future-scenario branches in parallel and merges them through one shared first-step problem. It reports large speedups over existing solvers on spring-mass and quadruped benchmarks, and the code is open source.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"Correctness rests on the DP/Schur-equivalence lemma [12, §9.2], cited from a same-group arXiv preprint and invoked in one line in the Appendix proof of Proposition II.1.","rationale":"The reader's weakest_assumption — the DP/Schur-equivalence lemma from [12, Sec. 9.2], cited from the same group's arXiv preprint and not re-derived — is exactly the hinge I identify; agreement is full. I read the rest of the argument in good faith and found it sound: the augmentation is benign (the dummy input enters only ½‖ũ0‖² so it vanishes at the optimum and V_j(x1) equals the value function of the original tail problem (3)); the Kfirst system (12) and the Schur complements (10) and (15) are correct, including the signs and the uniqueness-of-Cholesky step giving L0 = L_P. The whole scheme therefore reduces to one cited, unverified lemma, invoked in a single line of the Appendix proof. Per the review rules, attacking a cited result is legitimate when the source is an unpublished same-group arXiv preprint rather than a peer-reviewed publication, and when the result is used outside a stated hypothesis or with added structure — here the dummy augmentation and Cyqlone's permutation are exactly the added structure. The concern is real but modest: the equivalence is classical, and both the augmentation and the permutation are benign in principle, so the most likely outcome of the proposed numerical check is confirmation. That does not overturn the reader's verdict; rather, it sharpens the justification for CONDITIONAL: the authors should supply an independent derivation or restatement of the [12, §9.2] lemma (or the numerical confirmation above) before the speedup claims are taken at face value. The disclosed per-solver tolerance adjustments (Hpipm complementarity relaxed to 1e-6, PIQP duality-gap check disabled) and the spring-mass crossover where treeQP wins are secondary relative to the correctness hinge; they are honestly reported and do not change my assessment. I therefore keep the verdict UNCHANGED.","tokens_in":15248,"tokens_out":9338,"duration_ms":62661,"concrete_test":"Verify Proposition II.1 numerically in the exact regime used by the solver. For random instances (stages k=0..N-1 with A,B,Q∈S++,R∈S++, S,f,q,r drawn from a fixed distribution; nx∈{3,10,30}, nu∈{2,5}, N∈{10,50,200}, J=1): (i) compute P_j,p_j by the standard Riccati recursion for problem (3); (ii) run Cyqlone's factorization and forward solve (as in Algorithms 1-2) on the augmented problem (8) with x = f̃0j; (iii) check ‖L0,j L0,j^T − P_j^{-1}‖/‖P_j^{-1}‖ < 1e-10 and ‖L0,j λ̂0j − (f̃0j + P_j^{-1}p_j)‖ < 1e-8. If both hold across the full random family, the [12, §9.2] equivalence is confirmed in the augmented/permuted setting and the concern is resolved; if any instance fails, the root-combination scheme is invalidated. This uses only the existing open-source code and requires no new theory, targeting the exact hinge.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central identity Proposition II.1 (L0,j L0,j^T = P_j^{-1} and L0,j λ̂0j = x + P_j^{-1} p_j) is what lets FanCyqlone extract each branch's value-function factor directly from Cyqlone's factorization of the augmented problem (8) and combine branch contributions in the reduced root system (F1–F5, S1–S5). If that identity fails, the root combination — which builds L_Bj = B0j^T L0j^{-T} and the reduced root Hessian R = R0 + Σ_j S_Bj — produces the wrong first-stage solve, and the benchmarked method collapses. The paper's proof is otherwise complete and standard: the augmented problem (8) has value function V_j(x1) equal to the original (3) since the dummy input appears only in its own cost ½‖ũ0‖², so ũ0 = 0 at the optimum; the Kfirst system (12), the Schur complements (10) and (15) agreeing with L0L0^T = −K_Cyq/(Π1KΠ1^T) and with (−P^{-1}, −P^{-1}p−x), and the uniqueness-of-Cholesky step giving L0 = L_P all check out. The single external step is the assertion 'Elimination using dynamic programming and Schur complements are equivalent [12, §9.2]', cited, not derived, from the same group's arXiv-only preprint (arXiv:2512.09058v2). The equivalence is classical in the un-augmented setting, but here it must survive (i) the dummy-state/dummy-input augmentation of (8) with its extra nx+nu blocks and R̃0 = I, and (ii) Cyqlone's permutation [12, §4.1] placing the x1 = x constraint block last in each branch's KKT matrix. Both are benign in principle — permutation invariance and the quotient rule for Schur complements are standard — but that is precisely what the proof asserts rather than demonstrates at the hinge. Because [12] is not peer-reviewed and shares authorship, the load-bearing lemma lacks independent confirmation; this is the single most consequential gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper proposes FanCyqlone, a CPU parallel linear solver for multi-horizon (scenario-tree) optimal control problems in which branches share only the first-stage control, i.e., robust horizon one. The solver extends the same group's Cyqlone parallel-in-time KKT solver: each branch is augmented with a dummy initial state/input, Cyqlone factorizes and forward-solves the branch systems in parallel, the bottom-right nx-by-nx block L0,j of each branch's Cholesky factor is identified with the Cholesky factor of the inverse of the branch value-function Hessian P_j (Proposition II.1), and the branch contributions are combined in a small reduced root system for u0; branch solutions are recovered by parallel backward substitution. FanCyqlone is then used as the inner linear solver of QPALM to obtain FanCyQPALM for inequality-constrained multi-horizon LQ problems, with semismooth Newton inner systems of the same structure. Numerical experiments on spring-mass and quadruped centroidal MPC benchmarks report substantial speedups over Hpipm, treeQP, and PIQP, with all residuals verified externally. The paper includes the key proof for Proposition II.1 in an appendix, with the load-bearing DP/Schur-equivalence step cited from the companion Cyqlone preprint [12, Sec. 9.2].","tokens_in":15807,"tokens_out":3538,"duration_ms":23821,"significance":"If the central identity is correct, the paper makes a genuine contribution: it gives a clean way to extract per-branch value-function factors from a parallel factorization of an augmented branch KKT system, avoiding a separate Riccati recursion, and it provides an open-source SPMD implementation with reproducible benchmarks. Strengths include the explicit algorithmic presentation (Algorithms 1-2), a proof of the main structural identity that reduces the external dependency to one cited equivalence, disclosed per-solver tuning choices (initial_inner_tolerance, t0_init=0, complementarity tolerances), external residual checking, and open-source code. The claimed advantage over GPU-based approaches for the moderate-number-of-scenarios regime is plausible. The central claim is a mathematical identity plus a benchmark; the derivation itself has no fitted parameters, so the speedup claims are falsifiable.","major_comments":[{"comment":"The load-bearing step is the asserted equivalence between dynamic-programming elimination and Schur-complement elimination in Cyqlone's factorization, cited as [12, Sec. 9.2] from a same-group arXiv-only preprint. The Appendix supplies the quotient-rule and permutation-invariance arguments that connect this equivalence to the augmented problem, but it does not justify the underlying equivalence for the permuted, batch-wise factored branch KKT matrices. Since the proof of Proposition II.1 is the only thing the solver's correctness rests on beyond standard Schur-complement manipulations, the paper should either state the precise form of [12, Sec. 9.2] (including its hypotheses on augmentation and permutation), or include a self-contained proof. As written, the argument 'eliminating via DP and via Schur complements are equivalent' is asserted for the augmented problem and the identity L0,j = L_Pj then follows only to the extent that the cited lemma covers Cyqlone's exact elimination order.","section":"Section I and II-A","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The step from the primal factorization (Algorithm 1) to the semismooth Newton systems relies on the generalized Hessians H^ and R^0 having the same sparsity structure as the LQR KKT blocks. This is stated briefly in Section III and the generalized Hessian formulas are given, but the paper does not show explicitly that Proposition II.1 continues to apply with these modified diagonal blocks, in particular that the bottom-right block of the factored augmented branch KKT matrix remains the Cholesky factor of (P̂_j)^{-1} with P̂_j now the Riccati result for the regularized Hessians. Although this is a benign structural observation, it is load-bearing for the claim that the inner Newton systems are solved by exactly the same L0,j-extraction procedure. A one-line argument in Section III would close the gap.","section":"Section III, FanCyQPALM","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The benchmark comparison is careful in several respects, but the reported speedups are software-version-dependent, and the paper does not report the exact versions or commits of PIQP, treeQP, and Hpipm used, nor the full list of solver settings beyond the disclosed adjustments (t0_init=0, complementarity tolerance 10^-6, duality-gap disabled, initial_inner_tolerance). Given that the paper already discloses these adjustments, adding a version table or a reproducibility script would strengthen the claim that the benchmarks reflect the current state of the art rather than just the configuration used here.","section":"Section IV, numerical experiments","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The notation for P_j^{-1} is used before its Cholesky factorization is defined; in F1, the factor L_Pj is introduced only after P_j was defined in Eq. (4). Define L_Pj directly after Eq. (4) for readability.","section":"Notation and Section II-A","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The statement 'L0,j = L_Pj' should specify that the equality holds for the positive Cholesky factor; the LDL^T form in Eq. (7) has D = -I, so the positive factor L0,j is the one meant. This is clear from the proof but should be stated in the proposition for clarity.","section":"Proposition II.1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The claim that A0j, Q0j and S0j are not accessed because Cyqlone eliminates the initial state is correct for the augmented problem, but the paper should note explicitly that this is why the root problem's S0j x_initj term is handled separately in Algorithm 2 (line 7); a reader may otherwise wonder whether the root term is double-counted.","section":"Section II-C3 and Remark 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The figures' captions do not state whether the boxplots show medians, 25/75 percentiles, or min/max whiskers, nor how many runs per boxplot other than 'median of ten solves'. Add a sentence in each caption or in Section IV defining the boxplot elements.","section":"Figures 2-6","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Short version: this is a genuine, clean extension of the group's own Cyqlone solver to multi-horizon KKT systems, and the core identity holds up. It deserves a serious referee. My main reservation is moderate and it is about sourcing, not math: the load-bearing DP/Schur-equivalence lemma is cited from the same group's arXiv-only preprint [12, §9.2] instead of derived here.\n\nWhat is actually new: FanCyqlone extracts each branch's value-function factor L0,j directly from Cyqlone's block-Cholesky factorization of an augmented branch problem, then combines branch contributions in a reduced root system. That trick avoids a separate Riccati recursion per branch and works on indefinite KKT systems, which the concurrent GPU solver [8] cannot handle. The appendix proof of Proposition II.1 is largely complete: the Schur-complement identity (10), the Kfirst setup (12), and the final step via the quotient rule and permutation invariance all checked out when I followed them. The derivation uses no fitted parameters, and the benchmarks are disclosed honestly — the HPIPM tolerance relaxations, the PIQP duality-gap disable, the quadruped R regularization, and the spring-mass crossover at large M where they concede treeQP. That is good discipline.\n\nSoft spots, in proportion. The stress-test note flags the one-line quote of [12, §9.2] as the single most consequential gap. I read it as real but modest: the DP/Schur equivalence is classical — Riccati recursion is block Gaussian elimination on the same KKT matrix — and the appendix already supplies the permutation-invariance and quotient-rule justification for the rest of the chain. Low risk. But citing your own unpublished preprint for an identity the whole method leans on is a fair referee objection even when the result is true, and the fix is easy: restate or derive the equivalence inside the appendix. Two minor items: the code ships without a commit hash, and the coupled-only-at-first-stage scope (robust horizon one) is stated openly but is a real boundary against deeper trees.\n\nFor whom: people working on multi-horizon and contingency MPC solvers on CPUs, and anyone benchmarking scenario-MPC tooling. It is not a deep theoretical result, and it is a narrow engineering speedup within an established class — but it is a real one, with open source code and externally checked residuals.\n\nRecommendation: send it to peer review. Ask for the lemma derivation and a commit hash; do not hold the method hostage to them. My own confidence in the central claim is higher than the reader's — everything except that one citation is on the table and standard.","headline":"Sound branch-parallel extension of Cyqlone to multi-horizon KKT systems — the load-bearing lemma is cited from their own unpublished preprint, but it is classical and the proof skeleton is there, so treat it as a hygiene issue, not a correctness risk; send to review.","tokens_in":16389,"tokens_out":2305,"duration_ms":16026},"pith_extraction":{"msc":["90C20","49M37","65F05","93B40"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"FanCyqlone Solves Multi-Horizon KKT Systems by Extracting Branch Contributions from a Parallel-in-Time Solver","keywords":["multi-horizon optimal control","parallel solver","Cholesky factorization","model predictive control","branch MPC","augmented Lagrangian","KKT system","scenario tree"],"falsifier":"A direct verification would be to compute the per-branch value-function matrix P_j via the standard Riccati recursion and compare it to the inverse of L_{0,j} L_{0,j}^T extracted from Cyqlone's factor for a random branch problem; if the two differ by more than machine precision for a problem with well-conditioned dynamics, the identity in Proposition II.1 would be violated, and the method would fail.","tokens_in":16929,"feed_emoji":"⚡","tokens_out":1678,"duration_ms":17257,"temperature":0.7,"pith_summary":"This paper introduces FanCyqlone, a CPU-based linear solver for the KKT systems that arise in multi-horizon optimal control problems, where multiple future scenarios (branches) are coupled only at the first stage. The method exploits parallelism across both time steps and scenario branches by computing each branch's contribution directly from Cyqlone's parallel factorization of an augmented branch problem, combining those contributions in a reduced root system, and then recovering branch solutions through parallel back-substitution. If correct, FanCyqlone enables the solver FanCyQPALM to achieve substantial speedups over state-of-the-art solvers on benchmarks with spring-mass systems and quadruped control, especially when the number of branches is modest (e.g., 2 to 8) and the horizon length is long. The paper's central object is a block-Cholesky factorization identity that connects Cyqlone's output to the per-branch value-function factors, eliminating the need for a separate Riccati recursion. A sympathetic reader would care because this work addresses a computational bottleneck in model predictive control under uncertainty, where solving for multiple scenarios is often too expensive for real-time applications.","feed_headline":"FanCyqlone solves multi-horizon KKT systems by extracting branch contributions from a…","feed_subtitle":"The method eliminates the need for a separate Riccati recursion, achieving speedups over existing solvers on spring-mass and quadruped…","key_machinery":"The key machinery is the block-Cholesky factorization identity in Proposition II.1: for each branch j, the bottom-right n_x-by-n_x block L_{0,j} of the Cholesky factor of Cyqlone's permuted KKT matrix for the augmented branch problem equals the Cholesky factor of $P_j^{{-1}}$, where P_j is the value-function Hessian from dynamic programming. This identity allows the algorithm to extract the per-branch value-function factors directly from Cyqlone's output, eliminating the need for a separate Riccati recursion. The root problem's factorization and solve then combine these contributions via a Schur complement of the branch-level factors.","core_discovery":"The paper claims that the KKT system of a multi-horizon LQR problem can be solved by (i) augmenting each branch problem with a dummy initial state and input, (ii) applying Cyqlone's parallel-in-time factorization and forward solve to each augmented branch, (iii) extracting the bottom-right n_x-by-n_x block of each branch's Cholesky factor (which equals the Cholesky factor of the inverse value-function matrix $P_j^{{-1}}$), (iv) combining these branch contributions into a reduced root system, and (v) recovering all branch solutions via parallel backward substitution. The load-bearing identity is Proposition II.1: the bottom-right block L_{0,j} of Cyqlone's factor satisfies L_{0,j} L_{0,j}^T = $P_j^{{-1}}$ and L_{0,j} = L_{P_j}, so no separate Riccati recursion is needed to obtain the per-branch value-function factors. The paper further integrates FanCyqlone into the proximal augmented Lagrangian solver QPALM to handle general linear stage-wise constraints, yielding FanCyQPALM.","pith_inferences":["The paper's reliance on Cyqlone's factorization order suggests that the method is tied to the specific elimination order of Cyqlone; adapting FanCyqlone to other parallel-in-time solvers would require re-deriving the identity in Proposition II.1 for that solver's permutation.","The benchmark results show a crossover where treeQP becomes faster for large state dimensions (M > 22) in the spring-mass problem, hinting that FanCyqlone's advantage may diminish for problems where the per-stage cost Hessians are diagonal and constraints are simple boxes, as treeQP exploits those structures more directly.","The paper does not test FanCyQPALM on GPU hardware; given the CPU focus, a natural extension would be to port the branch-level computations to GPU for larger numbers of branches, though the authors note that GPU overheads currently outweigh benefits for modest branch counts.","The method's restriction to a single shared root stage (robust horizon one) limits its applicability to deeper scenario trees; extending the approach to deeper trees would require a recursive application of the root-combination scheme."],"forward_implications":["FanCyQPALM can solve multi-horizon LQR problems with general linear constraints faster than existing solvers (Hpipm, treeQP, PIQP) on CPU for typical problem sizes (horizon lengths 64–256, branches 2–8, state dimension up to 60).","The two-level parallelism (over branches and over time) gives consistent speedups over single-level parallelism (time only) when the number of branches exceeds one.","The method handles indefinite KKT systems (arising from equality constraints in augmented Lagrangian or interior-point methods), unlike GPU-based direct solvers that require positive definite matrices.","FanCyQPALM's open-source implementation (C++ with Python bindings) makes the method accessible for real-time MPC applications with modest numbers of scenarios."],"supporting_citations":[{"why":"Supplies the Cyqlone parallel-in-time solver that FanCyqlone builds on; provides the factorization identity and the equivalence between dynamic programming and Schur complements used in Proposition II.1.","marker":"[12]"},{"why":"Provides the QPALM proximal augmented Lagrangian solver that FanCyQPALM extends; supplies the framework for handling general linear inequality constraints via ALM and semismooth Newton steps.","marker":"[13, 14, 15]"},{"why":"Provides Hpipm, a tree-structured QP solver based on a modified Riccati recursion, used as a baseline in numerical comparisons.","marker":"[16, 17]"},{"why":"Provides treeQP, a dual Newton strategy for tree-sparse QPs, used as a baseline; its handling of general linear constraints via qpOASES is contrasted with FanCyQPALM's approach.","marker":"[19, 20]"},{"why":"Provides PIQP with a parallel KKT solver for multistage optimization, used as a baseline; its requirement of two triangular solves per iteration is noted as a disadvantage.","marker":"[22]"},{"why":"Provides the quotient rule for Schur complements, used in the proof of Proposition II.1 to equate successive and simultaneous elimination.","marker":"[31]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"The correctness of FanCyqlone rests on the lemma, cited from the Cyqlone paper [12] and not re-derived here, that eliminating states via dynamic programming is equivalent to eliminating them via Schur complements in Cyqlone's block-Cholesky factorization of the augmented branch problem, and that this equivalence survives the dummy-state augmentation and Cyqlone's permutation of the KKT matrix.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":7.1e-05,"raw_usage":{"cost":7.14532e-05,"is_byok":false,"cost_details":{"upstream_inference_cost":7.14532e-05,"upstream_inference_prompt_cost":7.10892e-05,"upstream_inference_completions_cost":3.64e-07},"total_tokens":988,"prompt_tokens":986,"completion_tokens":2,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":986,"tokens_out":2,"cost_source":"openrouter_usage","duration_ms":3009,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T09:06:01.582368+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"A direct verification would be to compute the per-branch value-function matrix P_j via the standard Riccati recursion and compare it to the inverse of L_{0,j} L_{0,j}^T extracted from Cyqlone's factor for a random branch problem; if the two differ by more than machine precision for a problem with well-conditioned dynamics, the identity in Proposition II.1 would be violated, and the method would fail.","supporting_citations":[{"cited_title":"Cyqlone: A parallel, high- performance linear solver for optimal control,","cited_arxiv_id":null,"evidence_quote":"Supplies the Cyqlone parallel-in-time solver that FanCyqlone builds on; provides the factorization identity and the equivalence between dynamic programming and Schur complements used in Proposition II.1."},{"cited_title":"Parallel KKT solver in PIQP for multistage optimization,","cited_arxiv_id":null,"evidence_quote":"Provides PIQP with a parallel KKT solver for multistage optimization, used as a baseline; its requirement of two triangular solves per iteration is noted as a disadvantage."},{"cited_title":"An identity for the Schur complement of a matrix,","cited_arxiv_id":null,"evidence_quote":"Provides the quotient rule for Schur complements, used in the proof of Proposition II.1 to equate successive and simultaneous elimination."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}