{"id":"4eca1139-e667-4094-8b7d-43fa4a15abeb","arxiv_id":"2505.06758","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Appending one data point to Apache Otava's change point detection now triggers a constant-time O(W^2) incremental recomputation, advancing the algorithm from cubic to effectively constant time for the common case.","lead":"After eight years of open-source tweaks by many contributors, the change point detection tool Apache Otava has become dramatically faster. A new incremental update means that when one new data point is appended, the tool recomputes its detection in constant time, which makes interactive browser use realistic.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 2 contradicts the O(W^2) incremental claim: incremental runtime grows 28x with change-point density although only the last window should be recomputed.","rationale":"The paper is a retrospective plus an algorithmic contribution. The historical speedup claims are not the crux for me; the O(1) incremental claim is. The window-independence assumption is the pivot, and the reader correctly identified it. My read did not find a formal proof of independence, but the absence of a proof alone would not be decisive. What is decisive is that the paper's own benchmark table behaves as if independence fails. If the incremental update really recomputed only the last 1-2 windows, varying p would change which change points are reported but not the number of windows touched; each window's significance test is local. The 28x swing in incremental runtime is too large to arise from a bounded number of recursive splits inside a fixed W=30/50 window. The most plausible explanations are (a) the implementation re-runs the global merge/filter over all weak change points, which scales with kappa or T, or (b) the benchmark methodology subtracts runs in a way that does not isolate the incremental update. Both are fixable: a code-level window count and a T-scaling run would settle it. Because the evidence currently contradicts the headline, I cannot accept the O(1) claim as established. I agree with the reader's CONDITIONAL verdict; I would not change the verdict, but I would make the required condition more specific: demonstrate flat incremental time in T and kappa, or show a window-count trace.","tokens_in":7343,"tokens_out":11223,"duration_ms":112870,"concrete_test":"Run the Otava pytest benchmark on the TigerBeetle dataset at p=0.1 with T=365, T=730, and T=1460, and instrument the incremental path to count how many windows are recomputed after one append. If the O(W^2) claim is correct, the window count should stay at 1-2 and the incremental wall time should be flat in T and close to the p=0.001 value; if the count or wall time grows with T or with change-point count, the last-window independence assertion fails. Additionally, profile the 157 ms p=0.1 run to see which functions and windows consume the time.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central O(1) claim rests on Section 6's assertion that after appending one point, \"it is sufficient to recompute 1-2 window length's worth of points from the end of the series,\" giving O(W^2). With W fixed and T=365, the number of windows that can be affected by the new point is at most two, so the incremental time should be flat across the four p-value columns. Table 2 instead shows the Incremental row growing from 5.5 ms at p=0.001 (6 change points) to 157 ms at p=0.1 (31 change points), a 28x increase. At p=0.1 the incremental run is only about 1.17x faster than the full Student+W pass (157 vs 184 ms), which is not what an O(W^2) last-window update should look like. The benchmark therefore suggests either that the incremental run re-evaluates more than the last window — for instance, all windows or the global weak-change-point merge — or that the window-independence assumption breaks down when change points are dense. Either way, the paper's own data do not support the claimed constant-time behavior.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper reviews eight years of performance optimizations applied to the E-Divisive change point detection implementation now known as Apache Otava (incubating), attributing the improvements to a loosely connected group of open source contributors. It contributes a complexity analysis of earlier optimizations, adds the Monte Carlo permutation count m to the O() notation for the naive implementation, and introduces a new incremental optimization: when a single data point is appended to the end of a time series, the paper claims that only the last one or two windows need to be recomputed, reducing the cost of the common append operation to O(W^2) (in practice O(1) since the window size W is constant). The paper presents benchmark results on a 365-point TigerBeetle dataset comparing Native (C), Student+W, and Incremental modes, and claims a cumulative speedup of 18,000 to 300,000 over the original 'by the book' implementation.","tokens_in":7543,"tokens_out":5011,"duration_ms":49614,"significance":"If the O(1) incremental claim were rigorously established, this would be a practically valuable result for real-time change point detection in continuous performance engineering, and the paper provides a useful historical narrative of how open source contributors progressively improved a statistical algorithm. The paper makes a concrete, falsifiable performance claim, which is commendable, and the historical complexity analysis in Section 4 is a useful correction to earlier papers that omitted the Monte Carlo cost. However, the manuscript currently lacks a formal proof of the central window-independence assumption, and the paper's own benchmark data appear to contradict the constant-time claim. The cumulative speedup headline is also not reproducible from the measurements reported here because it aggregates results from different papers, different hardware, and different implementations.","major_comments":[{"comment":"Table 2 directly contradicts the central O(1) claim. The Incremental row grows from 5.5 ms at p=0.001 (6 change points) to 157 ms at p=0.1 (31 change points), a 28x increase, even though the algorithm is said to recompute only the last window. At p=0.1 the Incremental time is 157 ms versus 184 ms for Student+W, only a 1.17x improvement, which is not what a constant-time incremental update should look like. The paper needs to either explain why the incremental runtime depends strongly on the number of change points or revise the claim; as written, the data suggest that the incremental pass re-evaluates more than the last one or two windows.","section":"Section 6, Table 2"},{"comment":"The load-bearing assumption 'the newly appended last point cannot have any effects on the points that are earlier than the last W points' is asserted but not proven. Since the e-divisive algorithm recursively splits the series at change points and the Hunter variant uses a weak-change-point merge step, it is not self-evident that appending a point cannot affect earlier windows or the global list of change points. A formal statement of the incremental algorithm and a proof of window independence (or a precise set of conditions under which it holds) are needed to support the O(W^2) complexity claim.","section":"Section 6"},{"comment":"The text states that 'the incremental Otava version is between 4x and 50x faster than the Native C version', but Table 2 reports an Incremental relative time of 0.41 at p=0.1, which is only a 2.4x speedup. This is inconsistent with the stated 4x lower bound. The relative values in the table are also labeled 'Relative improvement' while the numbers appear to be fractions of the Native (C) time; the label and the claimed range need to be reconciled.","section":"Table 2 and Section 6"},{"comment":"The headline cumulative speedup of 18,000 to 300,000 is not reproducible from this paper. It combines speedups reported in earlier papers (Daly et al. 2020, Fleming et al. 2023) that were measured on different hardware, with different datasets, and without a common baseline, and the present paper only measures three of the seven versions on a single dataset. A rigorous cumulative speedup claim requires an apples-to-apples benchmark that runs all versions in the same environment, or at least a clearly stated renormalization procedure; neither is provided.","section":"Abstract and Sections 6-7"}],"minor_comments":[{"comment":"There are several typos that should be corrected, including 'continuosly' in the abstract and 'comopanies' in Section 1.1; a full proofreading pass is recommended.","section":"Abstract, Section 1.1"},{"comment":"The row label 'Relative improvement' is ambiguous because the values are fractions of the Native (C) time rather than percentage improvements; consider renaming to 'Relative time (fraction of Native C)' or making the direction explicit.","section":"Table 2"},{"comment":"The paper reports only medians from 100 runs without confidence intervals or dispersion measures; given the large differences across columns, reporting standard deviation or an error range would strengthen the empirical claims.","section":"Table 2"},{"comment":"The role of the weak-change-point merge() step in the incremental mode is not explained; the paper should clarify whether the incremental recomputation re-runs the merge globally, since that could be a source of the dependence on change point density observed in Table 2.","section":"Section 6"},{"comment":"The relative speed ranges in Table 1 (e.g., '0.03 - 0.32') are given without specifying the configuration or dataset used to produce the endpoints, making the ranges difficult to interpret or reproduce.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The self-citation pattern is heavy, but the more serious issue is that the paper's own Table 2 undermines the O(1) claim. If the authors can provide a rigorous algorithm specification, a proof of window independence, and a corrected benchmark that separates the effect of change point density from the effect of series length, the contribution could be salvageable. I would ask the editor to require the authors to address the Table 2 inconsistency explicitly before any reconsideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new piece here is the incremental O(W^2) update for appending a point, and that is also where the paper's trouble sits: the benchmark table does not support the constant-time story. That is the first thing you should know.\n\nTo give credit where it is due, the paper does a few things well. The historical review of eight years of optimizations to what is now Apache Otava is readable and honest about the messiness of open source. The complexity corrections to prior work are real: adding the Monte Carlo permutation count m to the O() notation for the original e-divisive implementation fixes an actual omission, and supplying a complexity analysis for the Hunter modifications is useful. The incremental idea itself is a natural extension of Hunter's windowing scheme, and the derivation is not circular; it follows from the code's structure rather than being fit to any result. The author also clearly identifies his own role and the self-citation concern, which is mild.\n\nNow the soft spots, in proportion. The aggregate 18,000-300,000 speedup is assembled from benchmarks on different hardware and published in different papers, so it is a historical claim rather than a controlled measurement. That is a minor issue if treated as history. The larger issue is Table 2. The incremental row grows from 5.5 ms at p=0.001 (6 change points) to 157 ms at p=0.1 (31 change points), a 28x increase. If only the last one or two windows of size W are recomputed, the runtime should be roughly flat across those columns—the number of change points in the whole series should not matter. At p=0.1 the incremental pass is only 1.17x faster than the full Student+W pass, which is not what an O(W^2) tail update should look like. Either the incremental implementation is redoing more than the last window, or the window-independence assumption is breaking down when change points are dense, or the benchmark methodology is measuring something unintended. The paper neither explains this nor acknowledges it. The window-independence assumption itself is asserted, not proved; the benchmark data suggests it deserves scrutiny. Also missing are error bars; reporting medians without variance is thin, especially when the claim is about constant time.\n\nWho is this for? Performance engineers working with change point detection in CI or web UIs will find the history and the complexity corrections useful, and the incremental update is worth trying. But the benchmark needs major revision before the constant-time claim is credible. My recommendation: send it to peer review—the incremental extension deserves referee time—but expect heavy revision, and the reviewer should push hard on Table 2.","headline":"A useful historical review with a plausible incremental extension, but the paper's own benchmark table appears to contradict the headline constant-time claim.","tokens_in":8077,"tokens_out":4623,"would_cite":false,"duration_ms":46271,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Appending a data point now recomputes change points in constant time","keywords":["change point detection","e-divisive","incremental algorithm","constant time","performance optimization","benchmarking","continuous integration","Monte Carlo significance test"],"falsifier":"Take a long series with a weak change point near position T-W, then append a single large outlier that sharply increases the estimated variance in the final window. If recomputing incrementally changes the significance or location of the earlier change point compared with a full recompute, the window-independence assumption fails.","tokens_in":7106,"feed_emoji":"⚡","tokens_out":5245,"duration_ms":48181,"temperature":0.7,"pith_summary":"The paper recounts eight years of performance work on an open-source implementation of the e-divisive change point detection algorithm and adds a new incremental mode. Its central claim is that when a new data point is appended to a series, only the last window of W points needs to be recomputed, so the common update runs in constant time O($W^{2}$). Together with earlier optimizations, this yields a claimed speedup of 18,000 to 300,000 over the original by-the-book implementation. The authors also supply complexity analyses that earlier papers missed, most notably the effect of Monte Carlo permutation testing, and they report benchmarks on a 365-point series.","feed_headline":"Appending a data point now recomputes change points in constant time","feed_subtitle":"Eight years of optimizations, capped by a new incremental mode, make change point detection interactive.","key_machinery":"The load-bearing mechanism is the windowed e-divisive algorithm: the series is split into overlapping or adjacent windows of size W, and the pairwise distance matrix is computed only within each window, giving O(TW) instead of O($T^{3}$). The new incremental update exploits the locality of this windowing: appending a point requires recomputation of only the final 1-2 windows, so the update cost is O($W^{2}$), a constant because W is fixed. The earlier switch from Monte Carlo significance testing to Student's t-test also matters, since it removed the O(m $T^{2}$) cost of running m permutations of the whole series.","core_discovery":"On the authors' own terms, the discovery is that e-divisive change point detection can be made incremental. Because the Hunter-style modification splits the series into windows of fixed width W, appending a single point only changes windows at the very end; windows more than W points away are unaffected. Recomputing the last one or two windows costs O($W^{2}$), and since W is a constant, this is O(1) with respect to series length T. The paper reports that this incremental version is 4x to 50x faster than the previous fastest version, and that the full sequence of optimizations represents a speedup of roughly four to five orders of magnitude over the original implementation.","pith_inferences":["The constant-time result is conditional on the authors' window-independence assumption; if statistical significance depends on global variance or if change points are allowed to propagate across window boundaries, the O(1) bound may not hold for adversarial series.","A natural extension would be to derive formal error bounds for the incremental mode versus a full recomputation, since the paper provides benchmarks but no proof that detection quality is unaffected.","The same incremental idea could be applied to multivariate e-divisive detection, where the window statistics would be covariance matrices rather than scalars."],"forward_implications":["Incremental updates make it feasible to recompute change points on every data append or page view, without background jobs, for series up to at least the tested length.","For monitoring dashboards, the cost of adding a new observation no longer grows with the history length, enabling real-time regression alerts.","The complexity analysis clarifies that the Monte Carlo significance test, not the pairwise distance matrix, was the original bottleneck, guiding future optimization effort.","The windowing plus incremental approach may transfer to other change point detection methods that use local test statistics."],"supporting_citations":[{"why":"Defines the e-divisive means algorithm and its iterative segmentation procedure that all later implementations follow.","marker":"[Matteson and James 2014]"},{"why":"First applied e-divisive to software performance testing and supplied the initial implementation plus the first round of optimizations.","marker":"[Daly et al. 2020]"},{"why":"Introduced the windowed computation, Student's t-test significance test, and weak change points that the new incremental mode builds on.","marker":"[Fleming et al. 2023]"},{"why":"Provides the open-source Hunter tool with the merge() function that filters weak change points into final ones, used for instant parameter re-tuning.","marker":"[Piotr Kołaczkowski [n. d.]]"}],"fun_headline_variants":["Change point detection now runs in constant time per new point","8 years of work yields constant-time change point updates","Incremental e-divisive: change points in O(1) per append","From O(n3) to O(1): change point detection goes real-time","Constant-time change point detection: appending is now O(1)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's constant-time claim rests on the assertion that a newly appended point cannot change the change point decisions in any window that begins more than W points before the end of the series; that assertion is stated, not proven.","fun_headline_variants_meta":{"raw":{"variants":["Change point detection now runs in constant time per new point","8 years of work yields constant-time change point updates","Incremental e-divisive: change points in O(1) per append","From O(n3) to O(1): change point detection goes real-time","Constant-time change point detection: appending is now O(1)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000834,"raw_usage":{"total_tokens":3665,"prompt_tokens":1000,"completion_tokens":2665,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2572}},"tokens_in":616,"tokens_out":2665,"duration_ms":17641,"temperature":1.0,"reasoning_tokens":2572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:34:18.859706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a long series with a weak change point near position T-W, then append a single large outlier that sharply increases the estimated variance in the final window. If recomputing incrementally changes the significance or location of the earlier change point compared with a full recompute, the window-independence assumption fails.","supporting_citations":[],"review_version":1}