{"id":"1f54002f-9284-46c8-adbe-26f31d564aef","arxiv_id":"2506.22918","paper_version":3,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"Compressing a reversible Markov chain to a selected subset of states recovers the full dynamics with error at most a constant times the Nyström error of the inverse generator divided by time.","lead":"This paper proves the first rigorous error bounds for compressing a reversible Markov chain onto a small selected set of states: the compressed dynamics recover the full dynamics with error bounded by a Nyström approximation error divided by time. The bounds come with an algorithmic way to pick the states, and they are validated on a webgraph and on DNA folding models with up to a million states.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The bounds are rigorous but their algorithmic content rests entirely on the unquantified assumption that a small selected subset makes the Nyström error ε(I) small; no step in the proofs of Theorems 1–3 is internally inconsistent, so the verdict stands.","rationale":"I read the paper in good faith and found no internal inconsistency in the proof architecture. Theorem 1 is a clean contour-integral result with the constant 3√3/2π derived by optimizing α, β. Theorem 2 correctly obtains the singular case by applying Theorem 1 to Lγ = L + γI and letting γ→0; the triangle inequality term (1−e^{−γt})(∥P∥+∥P_I∥) vanishes, and Lemma B.2 establishes the limit εγ→ε. Theorem 3 is the most delicate, but the marked-chain construction is coherent: Q and W have orthonormal columns, Q^T W = C, L = Q^T ˚L Q, and L̂ = W^T ˚L W, so the α→∞ perturbation argument is legitimate. Proposition 4.14's probabilistic cycle argument proving ψ∗ ≤ |I|ε∗ is internally sound. The numerical experiments validate the bounds on realistic systems, including a 10^6-state DNA model. The reader's weakest assumption is exactly the right one: the theorem family is conditional on ε(I) being small, and the a priori control of ε(I) depends on the spectrum of K having a few dominant eigenvalues. The paper states this limitation openly and provides both a posteriori bounds (Theorem 3*) and an honest a priori tail bound (Theorem 4B). I therefore find no basis to change the ACCEPT verdict; at most, a user should check whether their chain's spectrum makes Theorem 4B informative, which is a practical caution rather than a defect in the paper's central claim.","tokens_in":61533,"tokens_out":2144,"duration_ms":30064,"concrete_test":"Run a synthetic reversible chain with a deliberately flat spectrum: e.g., n=200, with 20 eigenvalues of L at 1e-3 and the remaining 180 at 1. Use nuclear maximization for k=5 and k=20, compute ε∗(I), the Theorem 4B bound, and the actual errors ∥P−P_I∥∗ and ∥P−P^sp_I∥∗ at the intermediate time t=1/ε∗(I). If the actual errors are close to ε∗(I)/t and the Theorem 4B bound is loose by a large factor, the a priori control is weak but the theorems are validated; if ε∗(I) fails to decrease with k, the practical claim of algorithmic controllability is limited exactly as the caveat above suggests.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims, Theorems 1–3, are internally consistent; the contour-integral argument, the killed-chain limit in Theorem 2, and the marked-chain/obliqueness analysis in Theorem 3 all hang together. The genuinely load-bearing premise is that a user can find a small subset I with small Nyström error ε(I). That premise enters through Definition 3 and Section 5: the only a priori guarantee is Theorem 4B, which bounds ε∗(I) in terms of the nuclear eigenvalue tail Tr[K] − Tr^{(r)}[K] of K = L^+. For a chain with many comparable slow modes, this tail is O(Tr[K]), so the a priori bound becomes vacuous: it only asserts error ≤ C·Tr[K]/t, which is no better than the trivial bound in any meaningful time window. The paper explicitly acknowledges the t→0 and t→∞ vacuousness (Section 2.2) and correctly frames the result as an approximation theory rather than a universal algorithm; however, the phrase 'algorithmically controllable bounds' overstates the practical guarantee somewhat, because the control is inherited from a tail assumption that is not quantified for typical MSM spectra beyond Theorem 4B. This is a domain-restriction caveat, not a proof flaw; the a posteriori bounds of Theorem 3* do give honest computable control once I is chosen.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops an approximation theory for compressing reversible Markov chains. For a symmetric positive semidefinite Laplacian L obtained from a reversible chain, the authors define a projective compression P_I(t) based on Nyström approximation of the pseudoinverse K = L^+, and a structure-preserving compression P_I^sp(t) based on an induced chain over a selected subset I. The main results, Theorems 1-3, bound the recovery error by constants times the Nyström error ε(I) divided by t, with no spectral gap assumption. The paper also gives an a posteriori bound (Theorem 3*), an a priori selection guarantee via nuclear maximization (Theorems 4A and 4B), and numerical experiments on three systems of up to about 10^6 states.","tokens_in":61693,"tokens_out":15816,"duration_ms":158294,"significance":"If the results hold, this is the first rigorous, non-asymptotic approximation theory for the full time-dependent recovery error in Markov chain compression, connecting a Markov-chain problem to column subset selection and nuclear maximization. The paper provides complete proofs, several independently useful constructions (induced chain, marked chain, obliqueness norm), a posteriori bounds that are computable in practice, and an open-source implementation with reproducible experiments on webgraph and nucleic-acid secondary-structure systems. The main weakness is that the a priori control of ε(I) via Theorem 4B can be vacuous when the spectral tail of K decays slowly, so the practical guarantee is conditional on the existence of a small subset with small Nyström error; this is a domain restriction rather than an internal inconsistency.","major_comments":[{"comment":"The proof asserts that P_{I,γ}(t) = e^{-γt} P_I(t) for γ > 0. This identity is false in general: V_γ = orth((K_γ)_{:,I}) differs from V = orth(K_{:,I}) for finite γ, and one can check that V_γ^T L_γ V_γ ≠ V^T L V + γ I. For example, with L = [[2,-1],[-1,2]], I = {1}, γ = 1, a direct calculation gives V_γ^T L_γ V_γ = 2.4 while V^T L V + γ = 2.2. Consequently, the triangle inequality that follows does not control the desired quantity ∥P(t) - P_I(t)∥. The theorem is nevertheless salvageable by a simpler argument: apply Theorem 1 to the positive definite pair (L_γ, V_γ) to obtain ∥P_γ(t) - P_{I,γ}(t)∥ ≤ (3√3/(2π)) ε_γ(I)/t, and then pass γ → 0, using P_γ(t) → P(t), P_{I,γ}(t) → P_I(t), and ε_γ(I) → ε(I). This repair preserves the statement of Theorem 2 and its later use in Theorem 3* and Theorem 3, but the proof as written needs correction.","section":"Appendix B.2, proof of Theorem 2"}],"minor_comments":[{"comment":"The display of Theorem 4B appears to have a missing parenthesis in the second term; it should read ((s+1)/(s-r))(Tr[K] - Tr^{(r)}[K]) as in the proof. Similarly, the statement of Lemma E.1 writes Tr^{(k)}[K] where the proof uses Tr^{(r)}[K]; this is likely a typo.","section":"Theorem 4B and Lemma E.1"},{"comment":"The phrase \"algorithmically controllable bounds\" is somewhat overstated: the a priori control via Theorem 4B is vacuous when the tail Tr[K] - Tr^{(r)}[K] is of order Tr[K], which is exactly the regime where no small subset can make ε(I) small. The body of the paper is careful about this, but the abstract and contributions section should qualify the claim, for instance by saying the bounds are controllable when the Nyström error is small, or by referring to the spectral-tail condition.","section":"Abstract and Section 1.1"},{"comment":"The caption refers to a \"theoretical lower bound derived from the eigenvalues of L^+\" without defining it; please state the formula for this lower bound in the caption or in the text.","section":"Figure 4 caption"},{"comment":"The symbol P_I(t) is used both for the projective compression in Section 3 and for the general compression in Section 2, and the notation ∥·∥_{2,*} is introduced but not defined in the abstract; a brief reminder near the first use in the main text would help readers.","section":"Notation throughout"}],"recommendation":"major_revision","confidential_remarks":"The reader's report missed a genuine error in the proof of Theorem 2: the equality P_{I,γ}(t) = e^{-γt}P_I(t) is false. However, the theorem admits a one-paragraph fix by passing to the limit γ→0 directly in the Theorem 1 bound, so the central claims are likely correct. I recommend major revision rather than reject, with the expectation that the authors replace the faulty argument in Appendix B.2 with the direct limiting argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news here is Theorem 2 and Theorem 3: for reversible chains, the recovery error of both projective and structure-preserving compression of P(t) = e^{-Lt} is bounded by a constant times the Nyström error of the pseudo-inverse kernel divided by t. That is the first rigorous, computable control on the full time-dependent dynamics rather than just eigenvalue or long-time limits. The contour-integral mechanism is genuinely new, and the marked-chain analysis for the structure-preserving case is clever without being gimmicky.\n\nCredit where due: every main theorem has a complete proof in the appendices, and I spot-checked the resolvent difference and the contour optimization (the 3\\sqrt{3}/2\\pi constant) and found them correct. The numerical experiments compare against exact diagonalization on systems up to n=10^4 and against trajectory averages on a 10^6-state system; they are validating, not fitted. The a posteriori bounds in Theorem 3* are honestly computable and empirically tight. That is real evidence.\n\nThe soft spots are real but proportionate. First, the bounds are vacuous as t -> 0 and t -> infinity; the paper says this explicitly in Section 2.2, so it is not hidden. Second, the a priori control rests on Theorem 4B, which bounds the Nyström error by the nuclear eigenvalue tail of K = L^+. For a chain with many comparable slow modes, that tail is of order Tr[K], and the bound degrades to something no better than trivial. The phrase \"algorithmically controllable\" is thus somewhat stronger than what the theory actually delivers for a generic spectrum; the control is inherited from a tail assumption that is not quantified for typical MSM spectra. That is a domain-restriction caveat, not a proof flaw. Third, the |I| factor in Theorem 3 is empirically loose, which the authors admit in Section 6.1.\n\nThe load-bearing premise is that some small subset I makes the Nyström error small. That is exactly the standard MSM motivation, and the paper's contribution is to convert that premise into a clean error bound rather than to guarantee the premise. Given that the proofs are internally consistent and the numerics are genuine, I think the central argument holds up.\n\nWho is this for? People working on Markov state models, coarse-graining, or Nyström approximation who want a rigorous framework with honest error control. It deserves a serious referee and should be published after minor revision. I would take it to reading group.","headline":"First rigorous full-dynamics error bounds for reversible Markov chain compression; proofs check out, numerics are honest, and the main caveat is the slow-mode assumption, not the math.","tokens_in":62498,"tokens_out":1254,"would_cite":true,"duration_ms":16198,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C40","60J27","65F55","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that any reversible Markov chain can be compressed to a selected subset of states with a rigorously controlled recovery error that decays as $1/t$, with no spectral-gap assumption.","keywords":["Markov chain compression","Nyström approximation","column subset selection","error bounds","committor functions","Markov state models","nuclear norm","reversible Markov chains"],"falsifier":"Diagonalize a reversible chain with many comparable slow modes, such as a ring of weakly connected metastable clusters, pick a small subset $I$, compute the exact dynamics $P(t)$ and the compressed dynamics $P_I(t)$, and check whether the actual recovery error exceeds $\\frac{3\\sqrt{3}}{2\\pi}\\,\\frac{\\varepsilon_2(I)}{t}$ at any time after the initial transient; if it does, the central bound is false.","tokens_in":61093,"feed_emoji":"🧮","tokens_out":5997,"duration_ms":62621,"temperature":0.7,"pith_summary":"The paper develops an approximation theory for compressing reversible Markov chains: given a subset of selected states, it constructs reduced dynamics that can be lifted back to the full state space, and it proves explicit spectral and nuclear norm bounds on how much the lifted dynamics differ from the exact dynamics over time. The central claim is that the recovery error is bounded by a constant times a Nyström approximation error of the pseudo-inverse Laplacian, divided by time. Because that Nyström error can be controlled by a recently introduced column subset selection algorithm, the bounds are algorithmically actionable: they certify reduced models a priori. The paper presents two compression schemes, a projective one based on committor functions and a structure-preserving one that keeps a Markov-chain interpretation, and validates both numerically on large systems.","feed_headline":"Provable error bounds for Markov chain compression","feed_subtitle":"Recovery error stays below a computable Nyström error divided by time, with no spectral-gap assumption.","key_machinery":"The load-bearing identity is a contour integral representation of the matrix exponential, $e^{-Lt} = \\frac{1}{2\\pi i} \\oint e^{-1/z}(zI - K/t)^{-1}\\,dz$, which converts the difference of two dynamics into the difference of two resolvents. That difference is bounded by the Nyström error $\\varepsilon(I)$ of the kernel $K = L^+$ (or the killed-chain limit of it), and a universal contour integral gives the constant $3\\sqrt{3}/(2\\pi)$. For the structure-preserving scheme, a marked chain over an augmented state space supplies orthogonal projectors $W$ and $Q$ satisfying $Q^\\top W = C$, so that the non-orthogonal compression becomes an orthogonal projection in a lifted space; the additional price is an obliqueness term $\\psi_*(I) \\leq |I|\\varepsilon_*(I)$, controlled through mean first passage times.","core_discovery":"For a reversible Markov chain with symmetric Laplacian generator $L$ and a nonempty set $I$ of selected states, the projectively compressed dynamics $P_I(t) = V e^{-V^\\top L V t} V^\\top$ with $V$ an orthonormal basis of the committor matrix recover the exact dynamics $P(t) = e^{-Lt}$ up to $\\|P(t) - P_I(t)\\|_{2,*} \\leq \\frac{3\\sqrt{3}}{2\\pi}\\, \\frac{\\varepsilon_{2,*}(I)}{t}$, where $\\varepsilon_{2,*}(I)$ is the Nyström approximation error of the fundamental matrix $K = L^+$ in the spectral and nuclear norms, defined through a killed-chain limit. The structure-preserving compression $P^{\\mathrm{sp}}_I(t) = C e^{-C^\\top L C t} C^\\top$ obeys $\\|P^{\\mathrm{sp}}_I(t) - P(t)\\|_* \\leq \\left(\\frac{3\\sqrt{3}}{2\\pi} + |I|\\frac{2}{\\pi}\\right) \\frac{\\varepsilon_*(I)}{t}$. If correct, these are the first rigorous, computable bounds on full time-dependent recovery error for Markov chain compression, and they require no spectral gap assumption.","pith_inferences":["Beyond the paper: the $1/t$ bound suggests a natural timescale separation criterion, namely select $I$ so that $\\varepsilon(I)$ is small compared to the observation time $t$; this could be turned into an adaptive state-selection rule that the paper does not explicitly propose.","Beyond the paper: the same contour-integral and killed-chain machinery may extend to continuous state spaces through an initial basis projection step, using the singular-extension theorem, although the paper only sketches that direction.","Beyond the paper: because $\\varepsilon_*$ involves the pseudo-inverse kernel $L^+$, the quality of the reduced model is tied to mean first passage times; one could plausibly design subset-selection criteria based directly on hitting-time statistics, a connection the paper leaves implicit."],"forward_implications":["Reduced Markov state models come with a priori, computable error certificates for all but the fastest and the infinitely late timescales.","The error decays as $1/t$, so once the unselected fast modes have relaxed, projected and structure-preserving compressions track the full dynamics quantitatively.","Column subset selection by nuclear maximization makes the bounds algorithmic and nearly optimal, with almost-linear scaling in the number of graph edges.","Structure preservation guarantees entrywise nonnegative, row-stochastic lifted dynamics, so the reduced model remains interpretable as a Markov chain over selected states.","Autocorrelation functions of any observable are approximated with the same norm bounds, connecting the theory to standard Markov state model validation practice."],"supporting_citations":[{"why":"Supplies the nuclear maximization algorithm and its near-optimality guarantee used to control $\\varepsilon_*(I)$ and to make the bounds algorithmic.","marker":"[28]"},{"why":"Provides the fundamental matrix, committor, and renewal-reward identities that underlie the probabilistic arguments of Sections 3 and 4.","marker":"[2]"},{"why":"Supplies the Cauchy integral formula for matrix functions used in the contour-integral error bounds.","marker":"[36]"},{"why":"Defines the Nyström approximation whose error $\\varepsilon(I)$ is the central quantity appearing in every theorem.","marker":"[21]"},{"why":"Gives the determinantal point process expectation bound used in Theorem 4B's spectral estimate.","marker":"[3]"},{"why":"Gives the DPP bound on the elementary-symmetric-polynomial expectation used in Theorem 4B.","marker":"[35]"},{"why":"Cites the NP-completeness of general column subset selection, motivating the greedy near-optimal alternative.","marker":"[65]"},{"why":"Provides fast randomized Cholesky preconditioning used in the matrix-free implementation of nuclear maximization.","marker":"[9]"}],"fun_headline_variants":["Rigorous Markov chain compression error bounds","Error bounds for compression without spectral gap","First computable error bounds for chain compression","Compress Markov chains with provable error control"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The selected subset $I$ must make the Nyström error of the pseudo-inverse kernel small, which in practice requires the chain to have few dominant slow modes relative to the subset size.","fun_headline_variants_meta":{"raw":{"variants":["Rigorous Markov chain compression error bounds","Error bounds for compression without spectral gap","First computable error bounds for chain compression","Compress Markov chains with provable error control"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000212,"raw_usage":{"total_tokens":1411,"prompt_tokens":930,"completion_tokens":481,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":426}},"tokens_in":546,"tokens_out":481,"duration_ms":6265,"temperature":1.0,"reasoning_tokens":426,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:56:46.274840+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Diagonalize a reversible chain with many comparable slow modes, such as a ring of weakly connected metastable clusters, pick a small subset $I$, compute the exact dynamics $P(t)$ and the compressed dynamics $P_I(t)$, and check whether the actual recovery error exceeds $\\frac{3\\sqrt{3}}{2\\pi}\\,\\frac{\\varepsilon_2(I)}{t}$ at any time after the initial transient; if it does, the central bound is false.","supporting_citations":[{"cited_title":"Column and row subset selection using nuclear scores: algorithms and theory for Nystr\\\"{o}m approximation, CUR decomposition, and graph Laplacian reduction","cited_arxiv_id":"2407.01698","evidence_quote":"Supplies the nuclear maximization algorithm and its near-optimality guarantee used to control $\\varepsilon_*(I)$ and to make the bounds algorithmic."},{"cited_title":"On the Nystr¨ om method for approximating a Gram matrix for improved kernel-based learning","cited_arxiv_id":null,"evidence_quote":"Defines the Nyström approximation whose error $\\varepsilon(I)$ is the central quantity appearing in every theorem."},{"cited_title":"Optimal Column-Based Low-Rank Matrix Reconstruc- tion","cited_arxiv_id":null,"evidence_quote":"Gives the DPP bound on the elementary-symmetric-polynomial expectation used in Theorem 4B."},{"cited_title":"Column subset selection is NP-complete","cited_arxiv_id":null,"evidence_quote":"Cites the NP-completeness of general column subset selection, motivating the greedy near-optimal alternative."},{"cited_title":"RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems","cited_arxiv_id":null,"evidence_quote":"Provides fast randomized Cholesky preconditioning used in the matrix-free implementation of nuclear maximization."}],"review_version":1}