{"id":"db4a0bbf-dac7-4f23-a085-9dd46b3d5065","arxiv_id":"2510.14916","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"GSCSP prunes positive discrete measures to N-point moment-preserving rules in O(N^2) memory and O(MN^2+N^3) time, with a local total-variation Lipschitz stability theorem.","lead":"This paper introduces a streaming, memory-lean version of Carathéodory–Steinitz pruning (GSCSP) that compresses a large positive discrete measure to an N-point quadrature rule using only O(N^2) storage, regardless of the input size M. It matters for large-scale numerical quadrature and cut-cell discontinuous Galerkin simulations, where one-billion-point initial rules are now prunable in practice.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stability theorem's Lipschitz constants grow exponentially in M, making it vacuous for the paper's own numerical regime; §5.3 experiments do not probe the claimed guarantee.","rationale":"The reader correctly identified the Chebyshev system and uniqueness assumptions as load-bearing for the stability theorem, but I find a distinct, more quantitative weakness: even under those assumptions, the theorem's δ0 and Lipschitz constant depend exponentially on M−N. This makes the theoretical stability guarantee vacuous for the large-M examples that motivate the paper. The numerical stability tests use M=10^4, which already yields δ0 far below machine precision, so the experiments do not support the theorem; they only show stability in a regime the theorem does not cover. The algorithmic complexity and correctness claims appear sound, and the stability theorem is mathematically true as a qualitative statement, so rejection is unwarranted. However, the paper should either (1) state the exponential dependence and avoid claiming the numerics support Theorem 4.1, or (2) prove a tighter bound (e.g., using matrix perturbation theory to avoid geometric error accumulation). This warrants conditional acceptance rather than acceptance in current form.","tokens_in":26803,"tokens_out":16669,"duration_ms":134016,"concrete_test":"Instrument the Section 5.3 disk example (M = 10^4, N = 113) to record the cokernel vectors n_j and weights w_j at each SCSP iteration. Compute N_j = ||n_j||_1/|n_{j,m_j}|, ϵ_j = min_{k≠m_j} (w_{j,k} − |n_{j,k}/n_{j,m_j}| w_{j,m_j}), and C_j via (21). Then compute δ0 = min(1/3, δ2, δ3, δ4, δ5). If δ0 is orders of magnitude smaller than 10^{-10} — the smallest perturbation in Figure 5 — then the experiments do not test Theorem 4.1, confirming the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 4.1's proof (Appendix A) defines δ0 via δ2 = (1/(3|µM|)) min_j ϵ_j / C_j, where C_j = (1+N_j)C_{j−1}+1 ≥ 2^{j+1}−1. Even if all N_j = 1, C_{M−N} grows like 2^{M−N}. For the Section 5.3 example (M = 10^4, N = 113), this puts δ0 below ~10^{-3000}, far below the TV perturbation sizes (10^{-10}–10^{-2}) tested in Figure 5. The numerical stability experiments therefore operate entirely outside the theorem's guaranteed neighborhood and cannot be cited as 'supporting evidence' for the theorem. Moreover, the proof's error accumulation is inherently geometric, so the 'local Lipschitz' statement has constants that are astronomically large and radii that are astronomically small for the large-M streaming regime that is the paper's main selling point. This does not invalidate the theorem's truth, but it substantially weakens the 'robust' half of the central claim in practice.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a streaming implementation of Carathéodory–Steinitz pruning for compressing a positive M-node quadrature measure to an N-node measure preserving N moments in a finite-dimensional space V. The SCSP algorithm (Alg. 2) retains only N+k rows of the Vandermonde-like matrix at a time, and the GSCSP variant (Alg. 3) uses Givens row downdates/updates so that each iteration costs O(N^2), giving total O((M-N)N^2+N^3) work and O(N^2) storage. Theorem 4.1 asserts local Lipschitz continuity in a normalized total-variation metric under admissible perturbations, assuming a Chebyshev-system condition, fixed ordering, k=1, and unique selection at every iteration. The numerical section compares GSCSP with NNLS and LP, demonstrates large-scale pruning, and includes a cut-cell discontinuous Galerkin application.","tokens_in":27100,"tokens_out":11902,"duration_ms":104116,"significance":"The algorithmic contribution is solid and practically relevant: for the M≫N regime, GSCSP removes the dominant storage bottleneck of naive CSP, and the Givens downdate/update mechanism is an appropriate and well-executed device. The paper provides clear pseudocode, a complexity analysis, a detailed proof of Theorem 4.1 in Appendix A, and reproducible open-source code in CaratheodoryPruning.jl. The stability theorem is a step toward understanding perturbation behavior of pruning algorithms, and the experiments usefully contrast GSCSP, NNLS, and LP. However, as detailed below, the quantitative stability guarantee is currently far too weak to justify the practical 'robust' claim in the advertised large-M regime, and the numerical stability experiments are not actually covered by Theorem 4.1. With an honest reframing of the stability claims, the paper would be acceptable.","major_comments":[{"comment":"The stability theorem is stated as a quantitative Lipschitz bound, but its constants are exponential in M-N and the admissible radius is astronomically small in the paper's own target regime. From C_j=(1+N_j)C_{j-1}+1 and N_j≥1, one gets C_{M-N}≥2^{M-N+1}-1; in the Figure 5 example M=10^4, N=113, so C_{M-N}≳2^{9888}≈10^{2977}. Consequently δ2 ≤ (1/(3|µM|)) min_j ϵ_j/C_j is below ~10^{-2977} even if every ϵ_j were of order 1, and the Lipschitz constant C in the theorem contains the same exponential factor. The perturbations tested in Figure 5 begin at d_TV=10^{-10}, so every plotted point lies outside the radius for which the bound is proven. Therefore the statement in Section 5.3 that these experiments provide 'supporting evidence' for the TV-stability theorem is not justified. The theorem may be true, but it currently establishes only qualitative continuity, not practical robustness in","section":"Section 4.2 / Appendix A, Eq. (21) and the definition of δ2"}],"minor_comments":[{"comment":"The complexity entry for SCSP appears inconsistent with Section 3.1. The table lists per-iteration complexity M N^2 for SCSP, but the text states that fixed-k SCSP computes a cokernel vector of an (N+k)×N matrix at cost O(N^3) per iteration and O((M-N)N^3) total. If the table is per-iteration, the entry should be N^3; if it is cumulative, the CSP and SCSP entries need to be adjusted accordingly.","section":"Table 1"},{"comment":"Please temper the language that the numerical stability tests 'support' Theorem 4.1. Since the tested perturbations are many orders of magnitude larger than the proven δ0, the experiments should be described as empirical stability observations in a regime not covered by the theorem, rather than as confirmation of the theorem.","section":"Section 5.3"},{"comment":"The output line 'k ← M∗{N+1}' appears garbled; presumably it should be 'n ← Q_{*,N+1}' or similar. As printed, it is not readable pseudocode.","section":"Algorithm 3"},{"comment":"The sentence 'This result immediately applies to the GSCSP algorithm' should be qualified: the theorem is proved for the exact SCSP procedure in exact arithmetic. The floating-point Givens updates in GSCSP introduce roundoff, and no roundoff analysis is supplied, so the formal stability guarantee does not automatically transfer to the implemented floating-point algorithm.","section":"Section 4, intro"},{"comment":"There is a typo: 'Figure Figure 6' should read 'Figure 6'.","section":"Section 5.2.2"}],"recommendation":"major_revision","confidential_remarks":"The main algorithmic contribution is sound and the complexity claims are credible; the reader's accept verdict is understandable. My concern is scope and framing: the title and abstract promise 'robust' pruning, but Theorem 4.1 has constants exponential in M-N and a radius far below the values tested in Section 5.3. This is fixable by rewriting the stability claims to be qualitative or by adding a serious discussion of the constants, but it is a load-bearing part of the paper's advertised contribution. I would not reject the paper on this basis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. First, the algorithmic contribution is real: GSCSP is a clean streaming version of Carathéodory–Steinitz pruning, with O(N^2) storage independent of M, O((M-N)N^2 + N^3) time, and a sensible use of Givens QR up/downdates. The billion-point demonstrations and the cut-cell DG application are legitimate evidence that the method works. Second, the stability theorem that gives the paper its \"robust\" half is proven, but the radius is exponentially small in M-N; the numerical stability experiments in §5.3 sit far outside the theorem's guaranteed neighborhood, so they do not validate it the way the paper suggests.\n\nWhat is actually new: the streaming buffer idea plus Givens updating, as a package, is new, and the TV-stability result for SCSP under admissible perturbations is new. I checked the complexity analysis against the pseudocode and it holds: the first QR factorization is O(N^3), then each downdate/update is O(N^2). The proof of Theorem 4.1 is detailed, and the assumptions are stated clearly.\n\nSoft spots, in proportion. The big one is the stability theorem's practical bite. In Appendix A, δ0 includes δ2 = (1/(3|μ|)) min_j ϵ_j/C_j with C_j ≥ 2^{j+1}-1. In the paper's own stability example, M=10^4 and N=113, so M-N is nearly 10^4 and δ0 is below 10^{-3000}. Perturbations in Figure 5 start at 10^{-10}. So the experiments are not \"supporting evidence\" for Theorem 4.1; they are in a regime the theorem never touches. The theorem is not wrong, but its Lipschitz radius is so small that for the large-M setting that is the paper's selling point it does no work. The observed stability of GSCSP in those experiments is valuable, but it is empirical, not a consequence of the theorem.\n\nSecond, Assumption 4.1 is restrictive: Chebyshev system, k=1, unique argmin, fixed ordering. The paper says this, but it should also say plainly that multivariate polynomial bases on structured node sets (tensor-product grids, for instance) do not generally satisfy the Chebyshev condition, and that the stability result does not cover reordering of the original nodes. This limits the \"robust\" claim more than the abstract suggests.\n\nThis is a solid paper for numerical analysts working with positive quadrature rules, measure compression, and DG methods. I would send it to peer review. The referee should ask for a clear separation between what Theorem 4.1 proves and what the numerics actually demonstrate, and for a remark on the exponentially small radius. With that revision, it is a good addition to the literature.","headline":"Solid algorithmic contribution for Carathéodory–Steinitz pruning, but the stability theorem is proven with an exponentially small radius, so the numerical experiments do not actually probe it in the large-M regime.","tokens_in":27590,"tokens_out":3756,"would_cite":true,"duration_ms":32195,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65D32","65F25","65Y20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that Carathéodory–Steinitz pruning can be run as a streaming algorithm with O(N^2) storage and O((M−N)N^2 + N^3) total work, and that the pruning map is locally Lipschitz with respect to total variation distance.","keywords":["Carathéodory–Steinitz pruning","positive quadrature rules","measure compression","Givens rotations","streaming algorithm","total variation stability","moment preservation","Tchakaloff theorem"],"falsifier":"For the complexity claim, time one full GSCSP run for fixed M and N = 8, 16, 32, 64 and fit the per-iteration cost; if it grows faster than O(N^2), the advertised per-step complexity is wrong. For the stability claim, run SCSP on a Chebyshev-system node set and perturb the weights by total-variation amounts of 10^-8, 10^-6, and 10^-4; if the output distance does not shrink proportionally, the Lipschitz conclusion of Theorem 4.1 is violated.","tokens_in":26716,"feed_emoji":"🧮","tokens_out":5405,"duration_ms":44123,"temperature":0.7,"pith_summary":"The paper's central claim is that Carathéodory–Steinitz pruning—the standard constructive route from an M-point positive quadrature rule to an N-point one that preserves moments—can be made streaming: only a window of N+k rows of the moment matrix is stored, and Givens rotations update the QR factorization of that window in O(N^2) work per pruned node. The total cost is O((M−N)N^2) + O(N^3), linear in the original rule size M, with O(N^2) storage independent of M. On top of the efficiency gain, the paper proves that the pruning map taking an input measure to its pruned output is locally Lipschitz with respect to total variation distance, provided the moment matrix is a Chebyshev system, the input ordering is fixed, and the sign-selection rule has a unique minimizer at every step. The practical upshot is that quadrature rules with billions of nodes can be compressed to a few dozen nodes with modest memory, and the compression is stable under small perturbations of weights or appended nodes.","feed_headline":"Streaming algorithm prunes huge quadrature rules in O(N^2) memory","feed_subtitle":"Carathéodory–Steinitz pruning goes linear in rule size and stays provably stable under small perturbations.","key_machinery":"The central object is the Vandermonde-like moment matrix V ∈ R^{M×N} whose columns are the N basis functions evaluated at the M nodes. CSP repeatedly finds a nonzero vector in the cokernel of V^T, moves the weight vector along that direction until one weight hits zero, and deletes that node. SCSP restricts the working set to N+k rows at a time, and GSCSP maintains a dense (N+k)×N QR factorization, with Givens-rotation downdates and updates to replace one row per iteration; the cokernel vector is a trailing column of Q, available in O(N^2) work per step.","core_discovery":"The core discovery is the GSCSP algorithm: a streaming Carathéodory–Steinitz pruning in which the cokernel vector needed at each step is extracted from a maintained QR factorization of a small (N+1)×N window of the Vandermonde-like matrix, and the factorization is updated after each deletion and insertion using Givens rotations. This reduces per-iteration complexity from O(MN^2) to O(N^2) and storage from O(MN) to O(N^2). The paper also proves Theorem 4.1: under a Chebyshev-system assumption on the moment matrix, a fixed node ordering, and a unique minimizer of the sign-selection rule, the SCSP (hence GSCSP) output is locally Lipschitz with respect to total variation distance, so small admis","pith_inferences":["Because the stability theorem is tied to a fixed ordering of the input nodes, a natural extension is a permutation-invariant or ordering-adaptive variant; the paper gives no such guarantee, and its own analysis shows reordering can change the output.","The Chebyshev-system hypothesis fails for structured multivariate node sets (e.g., nodes on a line for monomial bases); a pivoting strategy or random shuffling of inputs might restore uniqueness generically, at the cost of a different stability statement.","The Lipschitz constant in the proof grows geometrically through the sequence C_j, so the worst-case bound may be conservative; measuring actual output variation across perturbation scales would show whether practical stability is far better than the theorem guarantees.","The O(N^2) storage opens the door to pruning in high-dimensional settings where N is large but M is astronomical, provided the moment matrix can be formed row-by-row; this is exactly the streaming regime the algorithm targets."],"forward_implications":["A positive M-point rule with M ≫ N can be compressed to N points while exactly preserving N moments using storage that depends only on N, not M.","Total runtime is O((M−N)N^2 + N^3), i.e., linear in M, making billion-point compression feasible with modest memory.","Small total-variation perturbations that preserve the node ordering—including perturbations that add new nodes with small weights—change the pruned rule by at most a constant times the perturbation size (Theorem 4.1).","The same pruning can be applied to non-polynomial spaces V, as long as the moment conditions are well-defined.","The algorithm generates positive, moment-preserving quadrature on cut-cell geometries, directly usable in discontinuous Galerkin discretizations."],"fun_headline_variants":["Streaming prune shrinks quadrature rules in O(N^2) memory","Givens rotations make Caratheodory pruning streamable","Prune quadrature on the fly: O(N^2) storage provably stable","Caratheodory pruning goes streaming with Givens rotations"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"For the stability half of the claim, the load-bearing premise is that every N-point subset of the nodes gives a nonsingular moment matrix (a Chebyshev system), together with a fixed node ordering and a unique argmin in the sign-selection step; if any N-by-N submatrix is singular, the cokernel vector is non-unique and the pruning path can jump under arbitrarily small perturbations.","fun_headline_variants_meta":{"raw":{"variants":["Streaming prune shrinks quadrature rules in O(N^2) memory","Givens rotations make Caratheodory pruning streamable","Prune quadrature on the fly: O(N^2) storage provably stable","Caratheodory pruning goes streaming with Givens rotations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001107,"raw_usage":{"total_tokens":4513,"prompt_tokens":865,"completion_tokens":3648,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":3581}},"tokens_in":609,"tokens_out":3648,"duration_ms":24670,"temperature":1.0,"reasoning_tokens":3581,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T09:28:16.850852+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the complexity claim, time one full GSCSP run for fixed M and N = 8, 16, 32, 64 and fit the per-iteration cost; if it grows faster than O(N^2), the advertised per-step complexity is wrong. For the stability claim, run SCSP on a Chebyshev-system node set and perturb the weights by total-variation amounts of 10^-8, 10^-6, and 10^-4; if the output distance does not shrink proportionally, the Lipschitz conclusion of Theorem 4.1 is violated.","supporting_citations":[],"review_version":1}