{"id":"366711d1-a626-45c2-bb78-b95266200786","arxiv_id":"1908.08623","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"EXACT computes exact likelihoods for all small trees under the noisy perfect phylogeny model and uses them for exact inference and tree ranking.","lead":"EXACT is a new tool that scores every possible small evolutionary tree exactly under the perfect phylogeny model with noisy mutation-frequency data, instead of using approximations. It gives researchers exact rankings and statistics for small tumor or bacterial evolution datasets, and serves as a benchmark for approximate tools.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"O(q^2) exactness claim rests on unproved general-D active-set lemmas (Supp. Sec. 10-11); the rate-bound and monotonicity proofs are omitted or only sketched, so Theorem 3.4 is not fully supported.","rationale":"The reader's weakest assumption correctly identifies the missing general-D proofs as the load-bearing gap. My pass independently checked the main derivations: the dual formulation in Theorem 3.3 follows from Moreau decomposition; the active-set logic would be sound if Lemmas 10.5 and 11.2 hold; the Prüfer-sequence enumeration and GPU benchmarking are consistent with the stated runtimes. The one place where the argument is under-specified is the generalization from D=I to general diagonal D: the paper explicitly omits the proofs and gives only a sketch for the crucial rate bound. This is a proof gap rather than a demonstrated counterexample, and the tree-Laplacian structure suggests the lemmas are likely true. Therefore the appropriate posture remains CONDITIONAL: accept the contribution conditional on the missing proofs being supplied or independently verified. I also noted minor internal issues, such as the undefined 't_r' in Algorithm 1 line 5 and the apparent typo 'I(x)=x' in Section 4, but neither is load-bearing for the central algorithmic claim.","tokens_in":28794,"tokens_out":13178,"duration_ms":139096,"concrete_test":"Run an independent randomized verifier for q=3..6: for at least 10^4 random trees, random positive diagonal D, and random N, solve the convex QP (12) exactly on a fine grid of t using a generic QP solver or active-set enumeration. Check that (a) every free-node slope lies in [0,1], (b) B(t) is monotone as t decreases and has at most q breakpoints, and (c) a clean-room reimplementation of Algorithm 1 matches the QP solution for random observed vectors. If any instance violates (a)-(c), Theorem 3.4 fails for general D; if all pass, the missing lemmas are empirically supported and should be completed by a maximum-principle proof on the weighted tree Laplacian.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim (Theorem 3.4: Algorithm 1 solves (9) in O(q^2) steps and O(q) memory) inherits all of its correctness from Lemmas 10.1-10.6 and Lemma 11.2, which are asserted for arbitrary strictly positive diagonal D. Supp. Sec. 10 states that these lemmas are 'almost identical' to lemmas in Jia et al. (2018) and omits the proofs, listing only two equation changes. Lemma 11.2, which bounds free-variable rates by 0 <= c1 <= 1, is only sketched in Sec. 12 via inequality (39); this sketch is not a complete derivation. Lemma 10.5, which asserts that the active set B(t) is monotone and changes at most q times, has no proof supplied. These are exactly the properties needed to guarantee that Algorithm 1's sequential extrapolation discovers all breakpoints of the piecewise-linear L(t). If any free variable had slope greater than 1, a node could hit the boundary, leave it, and hit again, making the number of breakpoints exceed q and breaking the O(q^2) bound and the exactness claim. No counterexample is demonstrated here; the issue is that the load-bearing proof is absent, so the exactness guarantee is conditional on an unstated proof. The rest of the paper (dual derivation, enumeration, GPU implementation, benchmarks) is coherent and reproducible in principle, but it cannot certify Theorem 3.4 without those proofs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents EXACT, a GPU-accelerated tool that performs exact inference under the noisy perfect phylogeny model (PPM) on VAF data. The main algorithmic contribution is a fast, non-iterative procedure (Algorithm 1) that computes the exact likelihood cost C(U; F_hat) for a given tree in O(q^2) steps and O(q) memory (Theorem 3.4), using a dual formulation (Theorem 3.3) and a piecewise-linear active-set analysis. EXACT then enumerates all rooted labeled trees of q nodes (via Prüfer sequences) or all spanning trees of a user-supplied DAG, and returns the top-k trees by cost, with BIC-based cluster-number selection. The authors benchmark EXACT against AncesTree, Canopy, CITUP, and PhyloWGS on 90 synthetic and 36 real data sets, reporting competitive or better accuracy and the unique ability to provide exact top-k statistics.","tokens_in":118,"tokens_out":5149,"duration_ms":115397,"significance":"If the algorithmic claims are fully substantiated, this is a genuinely useful contribution: it is the first tool, to my knowledge, that can exactly evaluate the likelihood of every tree in the q^(q-2) space for biologically relevant small sizes (q up to 10), enabling exact maximum-likelihood tree selection and exact top-k statistics under a noisy PPM. The paper is honest about the scope (small trees, simple k-means clustering) and about the fact that the real data violate the model assumptions. The machine-checkable parts, such as the dual derivation in Theorem 3.3 and the C/CUDA implementation with reproducible benchmark protocol, are strengths. The main significance is conditional on the completeness of the proof of Theorem 3.4, which currently rests on omitted or only sketched lemmas in the supplementary material.","major_comments":[{"comment":"The correctness of Algorithm 1 and the O(q^2) bound in Theorem 3.4 depend critically on Lemmas 10.1–10.6, especially Lemma 10.5 (monotonicity of the active set B(t), at most q changes) and Lemma 10.6 (fewer than q+1 linear segments). These lemmas are asserted for general strictly positive diagonal D, but no proofs are supplied; the text states that the proofs are 'almost identical' to Lemmas 3.2–3.9 of Jia et al. (2018), and lists only two equation changes. Lemma 10.5 is a combinatorial/monotonicity statement, not an equation change, and the paper does not explain how the D=I proof transfers to general D. Because Theorem 3.4 inherits all of its exactness and complexity guarantees from these lemmas, the central claim is not currently supported by a complete proof. I request that the authors provide the full proofs, or a detailed lemma-by-lemma mapping showing which parts of the Jia et al. proofs are unchanged and which require modification for general diagonal D.","section":"Supp. Mat. Sec. 10 (Lemmas 10.1–10.6)"},{"comment":"Lemma 11.2 is the load-bearing bound that rates c1 of free variables satisfy 0 <= c1 <= 1. This is exactly the property that makes the active set B(t) monotone: if a free variable had rate greater than 1, a node could hit the boundary, leave it, and hit again, potentially creating more than q breakpoints and destroying the O(q^2) claim. The proof given in Supp. Mat. Sec. 12 is only a sketch: the inequality in (39) is asserted, and the 'recursively applying the above inequality' step that produces (40) is not carried out. In particular, it is not shown that the constant C0 in (40) is independent of t, which is necessary for the conclusion c1 <= 1. This is not a merely cosmetic gap; the entire exactness guarantee of Algorithm 1 depends on it. A complete, self-contained proof of Lemma 11.2 for general D is needed.","section":"Supp. Mat. Sec. 11–12 (Lemma 11.2 and its proof sketch)"},{"comment":"The proof of Theorem 3.4 is not included in the manuscript; the text says it is 'exactly the same as a combination of the proofs of Theorems 3.10 and 3.11 in Jia et al. (2018)' with certain substitutions. Given that the two listed equation changes in Supp. Mat. Sec. 10 do not address the structure of Lemmas 10.3, 10.5, and 10.6, the reader cannot verify that the D=I proof transfers to the D != I setting. At minimum, the authors should state precisely which intermediate results from Jia et al. are used in each step of the proof of Theorem 3.4, and supply the missing arguments for the general diagonal D case.","section":"Supp. Mat. Sec. 10 (transfer argument for Theorem 3.4)"}],"minor_comments":[{"comment":"There is a typo in the proof of Theorem 3.3: 'Moureau's decomposition' should be 'Moreau's decomposition'.","section":"Supp. Mat. Sec. 12"},{"comment":"The main text says that using L0(t) we find t* such that '1+L0(t*)=0', but Algorithm 1 line 12 computes t* = t_i - (1+L0(t_i))/L00(t_i). This is consistent, but the sentence just before could be clarified to avoid the impression of a sign error.","section":"Section 3.3, Algorithm 1"},{"comment":"Several figures (especially Figures 2, 4, and 5) are low-resolution and axis labels are hard to read; the paper would benefit from larger panels and higher-resolution rendering.","section":"Figures 2–5"},{"comment":"The runtimes for k=46 are sometimes slightly smaller than for k=1 (e.g., 1.0 vs 1.1 for size 7); this is likely measurement noise, but it would be good to report that runtimes are measured once or to give a variance estimate.","section":"Table 5"},{"comment":"The extension to the '≤' constraint in (10) is described briefly; the sentence 'the first required adjustment to the proof of Lemma 3.3' suggests this refers to Theorem 3.3, not Lemma 3.3, and the numbering should be fixed.","section":"Supp. Mat. Sec. 9"}],"recommendation":"major_revision","confidential_remarks":"The paper's core selling point is exactness, and that exactness is currently conditional on unproved lemmas. I would be willing to accept once the authors supply a complete appendix with the D != I proofs, or a rigorous explicit reduction to the published D=I proofs. The experimental part is a useful application and is well executed, but it does not by itself certify Theorem 3.4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is the first tool I know of that exactly scores all trees under the noisy perfect phylogeny model for small q, and the contribution is real. The one load-bearing caveat is the proof of the fast cost algorithm: the O(q^2) exactness claim is delegated to lemmas from the authors' 2018 NeurIPS paper, and the extension to general diagonal precision is not fully proved.\n\nWhat is new: the paper extends the earlier projection algorithm from D=I to arbitrary strictly positive diagonal D, handles the ≤ mass constraint, and combines it with GPU-based Prüfer enumeration to exhaustively search all rooted trees up to q=10. That gives exact likelihood rankings and top-k statistics, which none of AncesTree, CITUP, PhyloWGS, or Canopy provide. The dual formulation (Theorem 3.3) is proved in the supplement and the derivation is clean. The experiments are honestly reported: they list files where other tools fail, compare only on overlapping files, and admit that the simple kmeans clustering is not the focus. Public code is provided.\n\nSoft spots: The central claim, Theorem 3.4, inherits everything from Lemmas 10.1-10.6 and Lemma 11.2 in the supplement. These assert that the dual cost is convex and piecewise quadratic, the active set is monotone with at most q changes, and free-variable rates satisfy 0 ≤ c1 ≤ 1. The supplement says the proofs are \"almost identical\" to Jia et al. (2018) and lists two equation changes, but does not actually give the general-D arguments. Lemma 11.2's proof is a sketch: inequality (39) is asserted, not derived, and the recursion to (40) is not fully justified. If any free variable had slope greater than 1, a node could hit the boundary, leave it, and re-enter, making the number of breakpoints exceed q and breaking both the O(q^2) bound and the exactness claim. I have not found a counterexample, and the result probably extends cleanly, but as written the guarantee is conditional. This is fixable in revision.\n\nMinor quibbles: the run-time comparisons are on different hardware (EXACT on GPU, others on CPU), and the real-data evaluation uses an expert-built tree as ground truth, which is fine but should be read as illustrative.\n\nBottom line: worth a serious referee. The proof gap is real but addressable, and the exact benchmark is valuable to the community. I'd cite it and bring it to reading group. I would not desk reject; ask for the omitted proofs or an explicit reduction to the prior paper.","headline":"First exact exhaustive inference under the noisy PPM for small trees; the O(q^2) guarantee is real but leans on unproved general-D lemmas, so the paper deserves a serious referee with a request for those proofs.","tokens_in":29702,"tokens_out":2990,"would_cite":true,"duration_ms":29355,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact inference under the perfect phylogeny model is achievable by exhaustive enumeration of all small trees.","keywords":["perfect phylogeny model","variant allele frequency","exact maximum likelihood","exhaustive tree enumeration","phylogenetic tree inference","tumor heterogeneity","GPU parallelization","noisy observations"],"falsifier":"Instrument Algorithm 1: for many random trees with random strictly positive diagonal D and random observations, count active-set changes and record all computed rates; if any run exceeds q changes or any rate falls outside [0,1], Theorem 3.4 is false. As a second check, compare Algorithm 1's output for q up to 8 against a direct convex quadratic solver on the same problem (9).","tokens_in":28609,"feed_emoji":"🧬","tokens_out":8820,"duration_ms":81036,"temperature":0.7,"pith_summary":"The paper sets out to show that exact inference under the perfect phylogeny model (PPM) with noisy variant-allele-frequency data is practical when the relevant mutations can be clustered into a small number of groups. Its tool, EXACT, scores every possible labeled rooted tree exactly, so it can return the maximum-likelihood tree and exact statistics over the whole tree space rather than a heuristic or sampling-based approximation. The enabling result is that the data-fit cost of one tree can be computed in $O(q^2)$ steps with $O(q)$ memory, which for $q \\le 10$ makes exhaustive search over $q^{q-2}$ trees feasible on a GPU. If the claim holds, researchers can separate what the PPM can explain from what approximate algorithms were missing, and can use exact scores as a benchmark for faster tools. In the paper's experiments, EXACT matches or beats the strongest approximate competitor on ancestral-relation accuracy on standard benchmark data.","feed_headline":"Exact inference replaces heuristics for small noisy phylogenies","feed_subtitle":"Every candidate tree is scored exactly, so the full space of trees can be ranked rather than sampled.","key_machinery":"The engine is a dual active-set path-following algorithm. Using the dual of the projection problem, the cost of a tree is written as $\\min_t [t + L(t)]$, where $L(t)$ is the minimum of $\\frac12 \\sum_i D_{ii}^{-2}(Z_i - Z_{\\bar i})^2$ over $Z$ with $Z_i \\le t - N_i$; here $\\bar i$ is the parent of node $i$ and $N_i$ is the weighted sum of observed frequencies over ancestors of $i$, including $i$. The algorithm starts at a large $t$ with no active constraints and walks downward through critical values $t_1>t_2>\\cdots>t_k$ at which a constraint becomes tight. The key structural facts are that $Z^*(t)$ is piecewise linear, each component changes at rate at most $1$, and the active set $B(t)$ grows monotonically and changes at most $q$ times, so extrapolating between critical values and recomputing rates yields the exact minimum in $O(q^2)$ steps. Rates are obtained by decomposing the tree into subtrees separated by active nodes and solving small convex quadratics recursively, while the outer exhaustive search maps integer indices to trees via Prüfer sequences.","core_discovery":"The central claim is Theorem 3.4: Algorithm 1 solves the per-tree cost problem (9) in $O(q^2)$ steps and $O(q)$ memory. Problem (9) is the projection of the noisy observed frequencies $\\hat F_O$ onto the set of frequency vectors compatible with a given tree, i.e. minimizing $\\|D(\\hat F_O - F_O)\\|^2$ subject to $F_O = U_{O,O}\\tilde M_O$, $\\tilde M_O \\ge 0$, and a sum constraint; $D$ encodes noise precisions. Computing this projection exactly and fast is what removes the need for heuristics: EXACT enumerates every labeled rooted tree (or every spanning tree of a user-supplied DAG), computes each tree's cost with Algorithm 1, and keeps the top $k$. The paper reports that on the 90 synthetic and 36 real benchmark files, the exact best tree is comparable to the best approximate tool on ancestral-relation error, and that the exact top-$k$ list contains a tree closer to ground truth than the single tree returned by approximate methods.","pith_inferences":["If the $O(q^2)$ claim holds for all positive diagonal $D$, a natural extension the paper does not take is exact model averaging over clusterings: instead of fixing one k-means clustering, one could enumerate plausible clusterings and sum exact tree scores, directly testing whether the remaining error gap is caused by clustering.","The exact top-$k$ output suggests a fast exact substitute for MCMC summaries on small instances: posterior probabilities of subclonal presence or ancestral relations can be read off the ranked list, as the paper's CLL example begins to do.","A stress test that follows naturally is to compare exact tree scores from Algorithm 1 with double-precision iterative solvers on ill-conditioned noise-weight matrices $D$, to locate where finite floating-point arithmetic starts to matter."],"forward_implications":["For problems with up to about ten mutation clusters, users can obtain the exact maximum-likelihood tree and exact top-$k$ rankings, not just a heuristic best guess.","The exact ranking of all trees makes it possible to decide whether a discrepancy between model and data is due to the PPM assumptions or to inference error.","EXACT can serve as a ground-truth benchmark for approximate and sampling-based tools on small PPM instances.","Because each tree cost is computed to machine precision in a finite number of steps, downstream statistics such as marginal ancestral-relation probabilities inherit exactness up to floating-point arithmetic.","The same fast per-tree solver can be embedded in an ADMM loop to handle more general convex objectives, as the paper sketches."],"supporting_citations":[{"why":"Source of the underlying projection algorithm and of the lemmas this paper extends from $D=I$ to general positive diagonal $D$; the O(q^2) exactness proof rests on them.","marker":"(Jia et al., 2018)"},{"why":"Supplies the synthetic and real benchmark data sets used for all comparisons, as well as the DAG-based ancestor constraints used in scenario B.","marker":"(El-Kebir et al., 2015b)"},{"why":"Gives the count $q^{q-2}$ of labeled rooted trees, defining the size of the exhaustive search space.","marker":"(Cayley, 1889)"},{"why":"Provides the Prüfer-sequence bijection used to turn each integer index into a tree during enumeration.","marker":"(Prufer, 1918)"},{"why":"CITUP baseline and source of the k-means clustering plus BIC model-size selection that EXACT adopts.","marker":"(Malikic et al., 2015)"},{"why":"PhyloWGS baseline and source of the expert-built CLL077 reference tree used in the real-data comparison.","marker":"(Deshwar et al., 2015)"},{"why":"Supplies Moreau's decomposition used in the proof of the dual formulation in Theorem 3.3.","marker":"(Parikh et al., 2014)"}],"fun_headline_variants":["Small phylogenies: exact scoring beats sampling heuristics","No more guessing: exact phylogeny inference for small trees","Rank every tree exactly: EXACT for small noisy phylogenies","Exact tree enumeration ends heuristic sampling in phylogenetics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The O($q^{2}$) bound assumes the unproved lemmas that the optimal dual variables are piecewise linear with slopes in [0,1] and that the active set can change at most q times when the noise weights D are arbitrary positive diagonal; the paper states these proofs are almost identical to those in earlier work but does not include them.","fun_headline_variants_meta":{"raw":{"variants":["Small phylogenies: exact scoring beats sampling heuristics","No more guessing: exact phylogeny inference for small trees","Rank every tree exactly: EXACT for small noisy phylogenies","Exact tree enumeration ends heuristic sampling in phylogenetics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000889,"raw_usage":{"total_tokens":3842,"prompt_tokens":959,"completion_tokens":2883,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":2817}},"tokens_in":575,"tokens_out":2883,"duration_ms":16828,"temperature":1.0,"reasoning_tokens":2817,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:34:51.639582+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument Algorithm 1: for many random trees with random strictly positive diagonal D and random observations, count active-set changes and record all computed rates; if any run exceeds q changes or any rate falls outside [0,1], Theorem 3.4 is false. As a second check, compare Algorithm 1's output for q up to 8 against a direct convex quadratic solver on the same problem (9).","supporting_citations":[],"review_version":1}