{"id":"5e746316-3583-42cb-b597-55f174e99f7c","arxiv_id":"2412.08059","paper_version":7,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A k-nearest-neighbors classifier using the sparsity graph pseudo-diameter selects the single-to-double precision switching point in mixed-precision CG and achieves near-oracle efficiency on synthetic matrices.","lead":"This paper presents a two-stage conjugate gradient solver that switches from single to double precision at a tolerance chosen by a k-nearest-neighbors classifier. The classifier uses matrix features including a cheap estimate of the sparsity graph diameter, and reports 17 to 30 percent savings in equivalent double-precision iterations on synthetic sparse matrices.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed mechanism for why graph diameter predicts rounding-error growth—delayed fill-in keeping Krylov vectors sparse—is contradicted by the paper's own dense right-hand sides, so the novelty claim is unsupported even if the empirical savings hold.","rationale":"The reader's conditional verdict is justified. The load-bearing weakness is the theoretical basis for the pseudo-diameter feature. The paper's Section 5 mechanism ('delayed fill-in') requires Krylov vectors to be sparse during early iterations, but the paper's own dense right-hand sides make r0 dense immediately. This is an internal inconsistency, not merely a disagreement with consensus: the argument as written cannot explain the claimed diameter effect. A direct density check would settle it. If the check refutes the mechanism, the paper still may have a viable empirical classifier, but the abstract's claim that diameter 'influences the growth of rounding errors' would need to be dropped or replaced by a rigorous explanation. Secondary issues reinforce conditionality: the abstract's 'at most 1.5% worse' conflicts with the reported roughly 3% gap for extended-star matrices (Tables 21–24), and the value of k0 used to compute v is never stated, hampering reproducibility. None of these by themselves necessarily falsify the 17% average savings, so I do not move the verdict; the paper should be accepted only with revisions clarifying or removing these unsupported claims.","tokens_in":28528,"tokens_out":13363,"duration_ms":140278,"concrete_test":"Reproduce the path-graph experiment from Section 5 (n = 1001, µ = 1.1, b = A(1,...,1)) with single-precision CG. For iterations i = 1,...,20, record the density (fraction of nonzeros) of r_i and d_i. If the density is already 100% at i = 1, the premise 'Krylov vectors stay sparse' is refuted for the paper's own test setting. If density builds up gradually for t < ℓ, the premise is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 argues that for t < ℓ the power A^t remains sparse and hence 'Krylov vectors ... tend to stay sparse,' so rounding errors accumulate slowly. In the experiments, the right-hand side is dense: in Section 2, b = Ax with x drawn uniformly from (1,2), and in the star/path illustrations b = A(1,...,1). Consequently r0 = b is dense, and every later residual and search direction becomes dense after one sparse matrix-vector product. The sparsity pattern of A^t is irrelevant to the density of A^t e0 when e0 is dense. Thus the proposed causal link between graph diameter and rounding-error accumulation is not established by the paper's own computations. This matters because the diameter is the paper's novel feature; without a valid mechanism, the empirical correlation between pseudo-diameter and efficiency in Tables 1–3 could reflect confounders such as eigenvalue distribution, and the abstract's 'we show' claim is unsupported. The efficiency reduction claim may still be empirically valid, but the central conceptual contribution is not.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers a two-stage mixed-precision conjugate gradient (CG) solver for sparse symmetric positive definite systems: single-precision CG runs to a switching tolerance epsilon_1, then double-precision CG refines the solution to a final tolerance epsilon_2. The switching tolerance is selected by a k-nearest-neighbors classifier over a feature vector (n, m, pseudo-diameter of the matrix sparsity graph, and the average residual decay rate during the first k_0 single-precision iterations), with training labels obtained by exhaustive evaluation of six candidate epsilon_1 values on generated matrices. The paper claims an average reduction of more than 17% in equivalent double-precision CG iterations, a gap of at most 1.5% relative to the oracle choice of epsilon_1, overhead below 1% of the double-precision solve time, and a novel conceptual result: that the sparsity-graph diameter influences rounding-error growth in CG. Experiments cover three families of sparse matrices (extended stars with random edges, random sparse graphs, and banded matrices) with n up to 1000.","tokens_in":28766,"tokens_out":23167,"duration_ms":217908,"significance":"If the empirical results hold, the practical contribution is a cheap, near-oracle precision-switch rule backed by a consistent evaluation pipeline: optimal labels are computed on training matrices only, predictions are evaluated on held-out test matrices, standard deviations are reported, and the cost model deliberately uses a pessimistic omega = 1/3 iteration-time ratio. The complexity accounting for the pseudo-diameter (2BFS) and for kNN is explicit, and the efficiency evaluation is not circular. However, the advertised novelty—the graph-diameter mechanism and the diameter feature—is the least supported part of the paper: the proposed causal mechanism is contradicted by the paper's own dense right-hand sides, and no ablation quantifies the diameter's predictive contribution beyond the other features. The empirical scheme may remain viable, but the central conceptual claim and the abstract's quantitative claims require substantial correction.","major_comments":[{"comment":"The central mechanism claim is contradicted by the paper's own experimental setup. Section 5 argues that for t < l the power A^t remains sparse and hence \"Krylov vectors (e.g., residuals and search directions) tend to stay sparse as well\", so that rounding errors accumulate more slowly for large-diameter graphs. But in the experiments the right-hand side is dense: in Section 2, b = Ax with x drawn uniformly from (1,2), and in the star/path illustrations of Section 5.1, b = A(1,...,1). Since x_0 = 0, the initial error e_0 = x_hat is dense, r_0 = A e_0 is dense, and every subsequent residual or search direction is dense after one sparse matrix-vector product. In Eq. (13), e_k = (I + sum_t gamma_t A^t) e_0, the vectors A^t e_0 are dense for t >= 1 regardless of the sparsity pattern of A^t; the diameter of the sparsity graph is therefore irrelevant to the density of the iterates in these experiments. The conclusion that delayed fill-in implies slower rounding-error accumulation does not follow. In addition, the star/path comparison (Figs. 2-3, Tables 4-5) is confounded: the modified star matrix has an eigenvalue of multiplicity n-2, so the CG minimal polynomial has degree three, which alone explains the small N_1 values (N_1 = 4 for the star), while the path matrix has distinct eigenvalues and a much larger condition number. The observed difference does not isolate the diameter. The abstract's \"we show\" claim about the diameter influencing rounding-error growth needs either a corrected argument or a control experiment (e.g., equal spectra with different graph diameters).","section":"Section 5 (Eq. (13)); Sections 2 and 5.1"},{"comment":"The predictive contribution of the diameter feature is never isolated. The kNN feature vector includes the residual-decay rate v (Eq. (15)), which is a strong proxy for the eigenvalue distribution and hence for CG convergence and attainable accuracy; n and m are also included. No ablation is reported (e.g., classification with and without the pseudo-diameter, or with and without v), so the roughly 70% classification accuracy and the near-oracle efficiency could be driven entirely by v, with the diameter contributing nothing. The cross-tabulations in Tables 1-3 do not resolve this: within a condition-number band, efficiency and pseudo-diameter are correlated, but both are functions of the same construction parameters (mu, ray length and number of rays, number of added random edges), which also control the spectrum and its multiplicity structure. Moreover, Table 3's well-conditioned banded row shows the opposite association: the above-average-efficiency subset has M_l_tilde = 39.7 versus 66.5 for the below-average subset, a non-monotonicity the paper mentions but does not explain. An ablation study and a control for spectral confounders are needed before the novelty claim—that graph diameter is a useful predictive feature for precision switching—can be accepted.","section":"Section 5.1 (Tables 1-3); Section 8.1"},{"comment":"The abstract's quantitative claim that the speedup is \"at most 1.5% worse than that achieved with the optimal (oracle) choice of epsilon_1\" is inconsistent with the reported data. Section 10.3 states that the gap does not exceed 3.0%, 1.5%, and 1.5% for the three matrix types, and Table 21 (extended stars, n = 1001, omega = 1/3) shows gaps of 3.09 to 4.15 percentage points (e.g., k = 5: 18.71 vs 22.86). Even for the augmented sample in Table 23 the gap reaches 2.64 points. Furthermore, Table 22 (k = 20) reports ME = 27.41 versus ME_opt = 27.20, which violates the definitional inequality E <= E_opt from Section 10.2 and indicates an error in that cell. The abstract, Section 10.3, and the tables must be reconciled before the headline claims can be considered accurate.","section":"Abstract; Section 10.3; Tables 21-22"},{"comment":"The cost model used for the efficiency claims omits part of the cost of computing the feature v, and the experiments omit its parameter k_0. Remark 2 states that \"the residual norms ||r_i||_2 for i <= k_0 are computed in double precision\", which requires an extra double-precision matrix-vector product and norm per probing iteration; the same remark claims this \"does not require any computations beyond those already performed by the algorithm\", which is inconsistent with the stated double-precision residual computation. The efficiency metric in Eqs. (3)-(4) counts only single-precision iterations N_1 (weighted by omega) plus N_2, so the extra double-precision work in the first k_0 iterations is not reflected in the reported savings; depending on k_0, this could reduce the claimed 17-31% efficiencies by a non-negligible amount. In addition, k_0 is never specified: Section 6 only says it is \"determined in advance by sampling\", and no value appears in the experimental sections. The authors should report k_0, state how it was chosen, and account for the probing cost in Eqs. (3)-(4).","section":"Section 6 (Eq. (15)), Remark 2; Eqs. (3)-(4)"}],"minor_comments":[{"comment":"There are several typos: \"detremine\" in Section 8.1, \"is consists\" in Section 8.4, and \"effficiency\" in the Table captions; a proofreading pass is needed.","section":"Section 8.1, 8.4, Table captions"},{"comment":"The appendix states that \"a 3-dimensional feature vector (m, l_tilde, v) - excluding matrix size n - was used in the experiments\", which contradicts Algorithm II and Section 8.1, where the feature vector is defined as chi(A) = (n, m, l_tilde, v). Clarify which feature vector was used in each experiment.","section":"Section 14 (end) vs. Algorithm II / Section 8.1"},{"comment":"Section 9 reports \"extensive computational experiments\" with a multilayer perceptron but provides no numerical results, no accuracy figures, and no direct comparison with kNN; either include the data or present the claim as a conjecture.","section":"Section 9"},{"comment":"The captions say the second column group contains ME and N for the below-average-efficiency subset, but the table columns contain M_l_tilde and N; align the caption text with the actual column layout.","section":"Tables 1-3 captions"},{"comment":"The cycle-counting model for comparing BFS cost with CG cost ignores memory traffic, which typically dominates the runtime of BFS on irregular sparse graphs; the \"well below 1%\" overhead claim should acknowledge this modeling limitation.","section":"Section 7.2"},{"comment":"The expectation that the diameter effect persists under Jacobi preconditioning is stated as a conjecture in disguise; label it explicitly as a conjecture, since no preconditioned experiments are reported.","section":"Section 5.2, Remark 1, Conclusions"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's headline novelty—graph diameter as a predictor of rounding-error growth—is the weakest part of the paper, and the abstract overstates both the mechanism result and the 1.5% oracle gap (Tables 21 and 22 contradict it). The empirical pipeline (labels on training data, held-out tests, standard deviations, pessimistic omega) is a genuine strength, and the near-oracle kNN results would survive a reframing that treats the diameter as an empirical feature subject to ablation. I would ask the authors to add the ablation, correct the numerical inconsistencies, report k_0, and soften the mechanism claim; I do not see an irreparable flaw in the empirical scheme itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is genuinely new: using the pseudo-diameter of the matrix sparsity graph as a feature to choose when to switch from single to double precision in CG. The empirical pipeline is also done honestly — held-out test sets, standard deviations, oracle comparisons, and a small decision overhead. If the savings hold, this is a useful incremental engineering contribution to mixed-precision iterative solvers.\n\nThe soft spot is in Section 5, and it is not minor. The paper argues that for t < ℓ the power A^t stays sparse, so \"Krylov vectors ... tend to stay sparse as well,\" leading to slower rounding error accumulation. But in the experiments the right-hand side is dense (b = Ax with x uniform in (1,2), or b = A(1,...,1)), so the initial residual is dense, and every subsequent residual and search direction is dense after one sparse matrix-vector product. The sparsity of A^t simply does not control the density of A^t e0 when e0 is dense. The load-bearing causal story is therefore not supported by the paper's own setup.\n\nThat said, the empirical correlation in Tables 1–3 might still be real. But the paper does not isolate the contribution of the diameter feature. The feature vector also includes the average residual decay rate v, which likely captures most of the predictive signal; without an ablation that drops the diameter, we cannot tell whether the pseudo-diameter is doing any work. The absence of code and data makes the numbers uncheckable.\n\nThere are also minor issues: the clock-cycle model sets C+ = C× = 4, which is a rough approximation, but it is only used to argue that the parameter computation is cheap, and the conclusion is not sensitive to that detail.\n\nWho should read this? Researchers working on mixed-precision Krylov methods, and possibly practitioners looking for a cheap heuristic. The paper deserves a serious referee, but it needs substantial revision: fix or substantially weaken the mechanism claim, add ablations with and without the diameter feature, and ideally release code and data. As it stands, I would not cite it for the mechanism, and I would be cautious about citing the efficiency numbers until the feature's independent contribution is demonstrated.","headline":"A well-run empirical study of kNN-based precision switching in mixed-precision CG, but the paper's central mechanistic claim about graph diameter controlling rounding error growth is contradicted by its own dense right-hand sides.","tokens_in":29243,"tokens_out":3046,"would_cite":false,"duration_ms":33805,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","65F50","65G50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes that the optimal single-precision stopping tolerance for a two-stage mixed-precision CG solve can be predicted from cheap matrix features, chiefly the sparsity graph diameter, cutting equivalent double-precision work…","keywords":["mixed precision","conjugate gradient","sparse linear systems","precision switching","sparsity graph diameter","k-nearest neighbors","rounding error","iterative solver"],"falsifier":"Construct two symmetric positive definite sparse matrices with the same condition number but very different sparsity-graph diameters, for example a path-like matrix and a star-like matrix with matched spectra via diagonal scaling, and measure the iteration at which single-precision CG residuals stagnate on dense right-hand sides: if the large-diameter matrix does not allow more single-precision iterations than the small-diameter one, the diameter-based switching rule is not doing the work claimed.","tokens_in":28346,"feed_emoji":"🧮","tokens_out":6638,"duration_ms":60276,"temperature":0.7,"pith_summary":"This paper tries to show that the best moment to switch a conjugate gradient solve from single to double precision can be predicted from cheaply computable matrix features, so the switch does not have to be tuned by trial. The central predictor is the diameter of the matrix's sparsity graph: when this diameter is large, the powers of the matrix fill in slowly, Krylov vectors stay sparse longer, rounding errors accumulate more slowly, and more iterations can safely run in single precision. The proposed algorithm classifies the matrix by a four-component feature vector, size, nonzeros, pseudo-diameter, and early residual decay rate, using k-nearest neighbors, and then picks the single-precision tolerance that minimizes total equivalent double-precision work. On the paper's test matrices this reduces computational complexity by more than 17% on average and lands within 1.5% of the oracle choice of the tolerance. A reader should care because the overhead of choosing the switch point is kept under 1% of the cost of a full double-precision solve.","feed_headline":"Sparsity graph diameter predicts the optimal CG precision switch","feed_subtitle":"Cheap matrix features pick when to leave single precision, cutting double-precision work by 17 percent.","key_machinery":"The mechanism that carries the argument is the error expansion $e_k = (I + \\sum_{t=1}^k \\gamma_t^{(k)} A^t) e_0$, which expresses the CG error at iteration $k$ as a polynomial in the system matrix acting on the initial error. Because the sparsity pattern of $A^t$ is contained in the sparsity pattern of the $t$-th power of the adjacency matrix, the graph diameter $\\ell$ controls how many powers stay sparse: for $t<\\ell$, $A^t$ is still sparse, so residuals and search directions tend to stay sparse and rounding errors accumulate slowly. The paper operationalizes this by estimating the diameter with the 2BFS pseudo-diameter $\\tilde{\\ell}$ (two breadth-first searches, $O(m)$ work) and combining $\\tilde{\\ell}$ with the matrix size $n$, the number of nonzeros $m$, and the early single-precision residual decay rate $v$ into a four-component feature vector $\\chi(A)=(n,m,\\tilde{\\ell},v)$. A distance-weighted k-nearest-neighbors classifier assigns one of six candidate tolerances $\\varepsilon_1\\in\\{10^{-2},\\ldots,10^{-7}\\}$; the whole parameter-estimation overhead is bounded by 1% of a full double-precision CG solve via clock-cycle estimates.","core_discovery":"On its own terms, the paper's central claim is that the sparsity graph diameter of a symmetric positive definite sparse matrix is a genuinely informative predictor of rounding-error growth in finite-precision CG, and that it can be used to set the single-precision stopping tolerance $\\varepsilon_1$ in a two-stage mixed-precision solve. The argument runs through the error expansion $e_k = (I + \\sum_{t=1}^k \\gamma_t^{(k)} A^t) e_0$: because $A^t$ has nonzero entries only where the $t$-th power of the adjacency graph has walks, a large graph diameter delays fill-in and delays the densification of Krylov vectors, so rounding errors accumulate more slowly in early single-precision iterations. The paper reports that, across three matrix types, the resulting algorithm cuts equivalent double-precision iterations by roughly 22%, 22%, and 17.7% when the single-to-double iteration time ratio is fixed at 1:3, and by up to about 31% when that ratio is measured per matrix, always within 1.5% of the optimal-tolerance oracle. It also reports that the diameter effect persists for Jacobi iterations, whose transition matrix shares the system matrix's graph, but not for Gauss–Seidel, and that for well-conditioned banded matrices the diameter no longer controls efficiency.","pith_inferences":["Not stated in the paper: the same feature vector might predict stagnation points in lower-precision CG generally, not just the two-stage switch, since the graph-diameter effect is about rounding-error accumulation rather than about CG specifically.","The paper's experiments use dense right-hand sides; a natural test is whether the diameter-based schedule still holds for sparse or structured right-hand sides, where Krylov vectors may stay sparse for different reasons.","The 1% overhead bound relies on sequential clock-cycle estimates; on parallel or GPU hardware the relative cost of computing the pseudo-diameter and running kNN could change, though the paper notes parallel variants should not degrade the estimate.","One could test the diameter hypothesis directly by comparing two matrices with identical spectra but different sparsity graph diameters, isolating diameter from condition number."],"forward_implications":["If the claim holds, mixed-precision CG can choose its switching tolerance automatically from matrix structure, removing trial-and-error tuning.","The near-oracle performance, within 1.5% of the optimal tolerance, means the cheap classifier does not sacrifice the speedup that a perfect choice of $\\varepsilon_1$ would give.","The diameter effect is expected to persist when a graph-preserving preconditioner such as Jacobi is used, extending the method to matrices with condition numbers above 1000.","Because the Jacobi transition matrix shares the system matrix's graph, the same diameter-based staging applies to Jacobi iterations, while Gauss–Seidel and relaxation methods should not be expected to show the same dependence.","The reported efficiency increases with matrix size, so the algorithm becomes more attractive for large sparse problems."],"supporting_citations":[{"why":"Supplies the general context and definitions for mixed-precision iterative linear algebra that the two-stage scheme builds on.","marker":"[1]"},{"why":"Supplies the standard condition-number bound on CG convergence that the algorithm extends.","marker":"[8]"},{"why":"Alongside [8], grounds the analysis of Krylov subspace convergence and information propagation in the computational domain.","marker":"[9]"},{"why":"Supports the claim that information propagates through the matrix graph during iterative solves.","marker":"[10]"},{"why":"Provides the reference point for sparsity loss in Krylov vectors, which the diameter argument builds on.","marker":"[11]"},{"why":"Links mixed-precision refinement to sparse linear systems and rounding-error analysis, the background for the delayed-fill-in claim.","marker":"[14]"},{"why":"Connects mixed-precision iterative refinement with sparsity, the neighboring result the paper says it extends.","marker":"[15]"},{"why":"Provides the industrial evidence that a single-precision CG iteration is roughly three to four times faster than double precision, fixing $\\omega=1/3$.","marker":"[16]"},{"why":"Supplies the $O(m)$ algebraic breadth-first search algorithm used to compute the pseudo-diameter cheaply.","marker":"[17]"}],"fun_headline_variants":["Graph diameter guides CG precision switch","Sparsity shape predicts CG rounding error","Diameter feature cuts CG work by 17 percent","KNN sets CG precision with 17 percent gain","Graph diameter optimizes mixed-precision CG"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the sparsity pattern of powers of the matrix, captured by the sparsity graph diameter, controls how fast rounding errors accumulate in finite-precision CG, so that a large diameter genuinely allows more safe single-precision iterations; if Krylov vectors densify rapidly even when the diameter is large, the predicted link weakens.","fun_headline_variants_meta":{"raw":{"variants":["Graph diameter guides CG precision switch","Sparsity shape predicts CG rounding error","Diameter feature cuts CG work by 17 percent","KNN sets CG precision with 17 percent gain","Graph diameter optimizes mixed-precision CG"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000501,"raw_usage":{"total_tokens":2559,"prompt_tokens":1162,"completion_tokens":1397,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":778,"completion_tokens_details":{"reasoning_tokens":1329}},"tokens_in":778,"tokens_out":1397,"duration_ms":11022,"temperature":1.0,"reasoning_tokens":1329,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:16:17.914622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct two symmetric positive definite sparse matrices with the same condition number but very different sparsity-graph diameters, for example a path-like matrix and a star-like matrix with matched spectra via diagonal scaling, and measure the iteration at which single-precision CG residuals stagnate on dense right-hand sides: if the large-diameter matrix does not allow more single-precision iterations than the small-diameter one, the diameter-based switching rule is not doing the work claimed.","supporting_citations":[{"cited_title":"31, 347–414 (2022)","cited_arxiv_id":null,"evidence_quote":"Supplies the general context and definitions for mixed-precision iterative linear algebra that the two-stage scheme builds on."},{"cited_title":"Iterative Methods for Sparse Linear Systems","cited_arxiv_id":null,"evidence_quote":"Supplies the standard condition-number bound on CG convergence that the algorithm extends."},{"cited_title":"Iterative Methods for Solving Linear Systems","cited_arxiv_id":null,"evidence_quote":"Alongside [8], grounds the analysis of Krylov subspace convergence and information propagation in the computational domain."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the claim that information propagates through the matrix graph during iterative solves."},{"cited_title":"S., Noailles, J., Ruiz, D","cited_arxiv_id":null,"evidence_quote":"Provides the reference point for sparsity loss in Krylov vectors, which the diameter argument builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Links mixed-precision refinement to sparse linear systems and rounding-error analysis, the background for the delayed-fill-in claim."},{"cited_title":"Conference MOTOR-2024 Challenges","cited_arxiv_id":null,"evidence_quote":"Provides the industrial evidence that a single-precision CG iteration is roughly three to four times faster than double precision, fixing $\\omega=1/3$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the $O(m)$ algebraic breadth-first search algorithm used to compute the pseudo-diameter cheaply."}],"review_version":1}