{"id":"cd2cad3a-7a01-41a3-9b43-9a016e15dd9b","arxiv_id":"1908.04000","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The stray algorithm detects anomalies and micro-clusters in high-dimensional data using the k-nearest-neighbor distance with the maximum gap, with an extreme-value-theory threshold, and outperforms HDoutliers on the illustrated cases.","lead":"This paper proposes stray, an unsupervised anomaly detection algorithm that scores each point by the largest gap among its k nearest neighbor distances. It is designed to fix known failures of the earlier HDoutliers method and ships as an open source R package.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"EVT threshold in §4.4 is applied to dependent, non-identically distributed max-gap scores without validation, and Table 1's FPR (~0.006) does not match the nominal α=0.05; the claimed probabilistic interpretation is unsupported.","rationale":"The reader's weakest assumption is the same as the one I consider most load-bearing: the threshold calculation is the only part of the paper that gives the binary labels a probabilistic meaning, and it is used in every experiment and application. The algorithm's core novelty—the max-gap score—is a reasonable heuristic, and the paper provides R code and honestly acknowledges evaluation limits, so rejection is not warranted. But the EVT step is not a minor technicality: if the scores are not in the Gumbel domain or the spacing approximation fails, the threshold is effectively an arbitrary quantile and the claimed α-level control is false. Table 1 already suggests miscalibration: for α=0.05, per-point false-positive rates near 0.006 are about an order of magnitude below nominal. This might be a consequence of the sequential bottom-up procedure, but the paper gives no analysis of what α means under that procedure. The proposed test directly checks calibration and the exponential-spacing assumption on null data, which would settle whether the concern lands. I therefore agree with the conditional verdict: the condition should be a validation or relaxation of the EVT threshold before the 'valid probabilistic interpretation' and broad applicability claims are accepted.","tokens_in":15750,"tokens_out":10391,"duration_ms":116982,"concrete_test":"Run the null-data experiment of Table 1 for n=500, d=10, k=10, α=0.05 over 1000 replicates using the stray package on standard-normal and uniform-[0,1]^10 data; record the empirical false-positive rate and the QQ fit of the standardized upper spacings of the score order statistics to an exponential distribution. If the empirical FPR differs from 0.05 by more than a factor of 2, or the spacings clearly deviate from exponential, the EVT threshold is not calibrated as claimed and Section 4.4 needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.4 applies Weissman's spacing theorem to the kNN max-gap anomaly scores: it assumes these scores are (at least approximately) order statistics from a single distribution in the Gumbel maximum domain of attraction, so that standardized upper spacings are exponential. That assumption is not justified for this score. Each score is a per-point maximum gap among k dependent nearest-neighbour distances; in multimodal or clustered data the scores are neither identically distributed nor independent, because points share neighbours. In the normalized unit hypercube the score distribution also has a finite upper endpoint, whose maximum-domain class is not established. The bottom-up procedure then fits an exponential to the upper tail of the lower 50% of scores—around the median, not the extreme tail where Weissman's theorem applies. The one empirical calibration check in Table 1 reports false-positive rates near 0.006 for α=0.05, not the nominal 0.05; if the threshold is meant to be the upper 1−α quantile, this is a large miscalibration. Since the binary classification and the claimed advantage of a 'valid probabilistic interpretation' rest on this threshold, the central claim is only as strong as this unvalidated EVT step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the 'stray' algorithm for unsupervised anomaly detection in high-dimensional data. Each observation is scored by the maximum gap among its k-nearest-neighbour distances, and a binary classification is obtained by comparing this score with a threshold derived from extreme value theory (EVT), following the approach of Weissman's spacing theorem as used in HDoutliers. The authors argue that this score addresses three limitations of HDoutliers: masking by nearby anomalous clusters, information loss from the Leader clustering step, and threshold instability. They illustrate the method on synthetic counterexamples, compare running times and false positive rates against HDoutliers, and demonstrate an application to pedestrian-count data using feature engineering. An R package, stray, is provided.","tokens_in":16043,"tokens_out":4317,"duration_ms":45453,"significance":"If the claims were fully supported, the paper would offer a useful, fast, clustering-free anomaly detector that handles singletons, micro clusters, and inliers, with an open-source implementation. The strengths of the manuscript include a clearly specified algorithm, an R package that makes the method reproducible, and an explicit comparison with a specific baseline algorithm (HDoutliers) on targeted examples that expose known failure modes. The paper also honestly acknowledges in Section 7 that the counterexamples are not diverse enough to claim general superiority. However, the central claim of a 'valid probabilistic interpretation' for the threshold rests on an EVT assumption that is not justified for the proposed score, and the empirical calibration in Table 1 appears to contradict the nominal error rate. The value of the paper therefore depends on whether the threshold step can be theoretically or empirically supported.","major_comments":[{"comment":"Weissman's spacing theorem is stated for spacings of order statistics from an iid sample whose distribution lies in the maximum domain of attraction of the Gumbel distribution. The paper applies this theorem directly to the kNN max-gap scores, but these scores are neither independent nor identically distributed: each score is a maximum gap among k nearest-neighbour distances, and points share neighbours; in multimodal data the score distribution is a mixture; and under min-max normalization the scores have bounded support in [0, 1], whose domain-of-attraction class is not established. Consequently, the 'valid probabilistic interpretation' claimed as an advantage in Section 1 (advantage 3) is unsupported. The authors should either provide a rigorous justification, or present simulation evidence that the resulting threshold is calibrated across distributions, dimensions, and sample sizes, or explicitly rescope the threshold as a heuristic.","section":"Section 4.4, Theorem 4.1"},{"comment":"Table 1 reports false positive rates for stray of approximately 0.006 for d=1 with alpha=0.05, falling to 0.000 or 0.001 for higher dimensions. If the threshold is intended to be the upper 1-alpha quantile of the fitted exponential distribution, the achieved FPR should be close to 0.05, not nearly an order of magnitude smaller. The text frames the low FPR as a positive feature, but this is in tension with the claimed probabilistic interpretation of the threshold. The authors should report the achieved FPR as a function of alpha for several configurations and reconcile the discrepancy, or revise the claim that the threshold has a nominal alpha interpretation.","section":"Table 1"},{"comment":"The threshold calculation fits an exponential distribution to the 'upper tail' of the lower 50% of the scores, i.e., around the median of the score distribution, rather than to the extreme upper tail where Weissman's spacing theorem operates. The subsequent bottom-up updating, which adds one point at a time and recomputes the cutoff, moves even further from a fixed EVT quantile. The procedure may work as a heuristic, but it should not be described as an EVT-based quantile without additional theoretical or empirical support.","section":"Section 4.4, bottom-up procedure"}],"minor_comments":[{"comment":"The text says the values in Table 1 are based on 1000 iterations, while the table caption says 100 iterations; this inconsistency should be corrected.","section":"Section 5"},{"comment":"The definition D_{i,n} = X_{i:n} - X_{i+1:n} with ascending order statistics gives non-positive spacings; the theorem should be stated for upper-order spacings, e.g., D_{i,n} = X_{n-i+1:n} - X_{n-i:n}, to match Figure 4 and the standard Weissman formulation.","section":"Section 4.4, Theorem 4.1"},{"comment":"In the sentence 'The second dataset, in Figure 3 b), has three anomalies', the reference should likely be Figure 3(c) or Figure 3(d); please correct.","section":"Section 4.3"},{"comment":"The sentence 'the k-nearest neighbour distance with the maximum gap occurs when k = 1' appears to mean the first gap (i = 1) is the maximum; please clarify the notation.","section":"Section 4.3"},{"comment":"The claim that min-max normalization 'does not change the distribution or squeeze points together masking anomalies' is too strong: linear rescaling can alter distances when variables have very different scales, and the presence of anomalies can affect the min-max range. Please soften or provide a supporting reference.","section":"Section 4.2"},{"comment":"A pseudo-code block or algorithm box summarizing the full stray procedure would improve clarity, since the score computation (Section 4.3) and the threshold computation (Section 4.4) are described in separate subsections.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The EVT threshold assumption is the main barrier to publication. The paper is an incremental but potentially useful contribution to the family of HDoutliers-style methods; if the authors can supply calibration evidence or rescope the threshold as a heuristic, the manuscript could be publishable after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stray algorithm is a clean, incremental improvement over HDoutliers. The key idea—use the largest gap among the k-nearest-neighbor distances as the anomaly score, and skip the Leader clustering step—is genuinely new relative to the cited prior work. It addresses real failure modes of HDoutliers: micro-clusters that become each other's nearest neighbors, dense clusters that get misrepresented by a single representative, and the high computational cost of clustering in high dimensions. The paper shows concrete counterexamples where HDoutliers fails and stray works, and the authors ship an R package, which makes the method immediately usable. They are also unusually honest about the evaluation being illustrative rather than exhaustive.\n\nThe main soft spot is the EVT threshold. Weissman's spacing theorem applies to spacings of order statistics from a distribution in the Gumbel maximum domain of attraction. The stray scores are per-point max-gaps among k dependent nearest-neighbor distances; they are neither independent nor identically distributed, especially in clustered or multimodal data. The paper simply asserts that the assumption holds. The bottom-up procedure then fits an exponential to the upper tail of the lower 50% of scores—that is around the median, not the extreme tail where the theorem operates. And Table 1 is telling: for a claimed α=0.05, the false positive rates are about 0.006 to 0.001, far below the nominal rate. If the threshold is supposed to be the upper 1−α quantile, that is a large miscalibration. The binary classification may still be reasonable—being conservative is not disaster—but the paper's claim of a 'valid probabilistic interpretation' is unsupported.\n\nThe experiments also compare only against HDoutliers, with mostly bivariate synthetic data and no other detectors. The authors acknowledge this at the end, so it is a stated limitation rather than a hidden one.\n\nAll that said, the algorithmic core is sound and the counterexamples are convincing as illustrations. The EVT step is inherited from Schwarz and Wilkinson, but stray leans on it heavily. What this paper needs is either a justification for why max-gap scores should fall in the Gumbel MDA, or an empirical calibration check that does not lean on the nominal α.\n\nThis is a solid contribution to the anomaly detection subfield, not a field reorganization. Practitioners who want a fast, simple unsupervised detector will get value from it, and the R package is a real asset. I would send it to peer review, with a clear request to address the threshold justification and calibration before acceptance.","headline":"Useful incremental algorithm with a simple max-gap kNN score, but the EVT threshold is applied to dependent scores without validation and the reported FPR doesn't match the nominal α; worth engaging if the threshold step is fixed.","tokens_in":16524,"tokens_out":1912,"would_cite":true,"duration_ms":20829,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","62G32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The stray algorithm turns the largest k-nearest-neighbour gap into one anomaly score that catches singletons, micro clusters, and inliers, without the clustering step that slows and misleads HDoutliers.","keywords":["anomaly detection","high-dimensional data","k-nearest neighbours","maximum gap","extreme value theory","micro clusters","inliers","stray algorithm"],"falsifier":"Run the stray algorithm with α = 0.05 on anomaly-free data drawn from a heavy-tailed multivariate distribution (for example, a multivariate t with three degrees of freedom) across several dimensions and sample sizes; if the empirical false-positive rate clearly exceeds 0.05, or if the upper-tail spacings of the max-gap scores fail an exponential fit, the threshold assumption is not doing the claimed work.","tokens_in":15555,"feed_emoji":"🔎","tokens_out":12883,"duration_ms":116947,"temperature":0.7,"pith_summary":"This paper tries to establish that a single distance-based score—the k-nearest-neighbour distance at the largest gap in the k-nearest-neighbour distance curve—can detect the anomalies that the HDoutliers algorithm misses, without the clustering pass that HDoutliers uses. The score makes anomalous singletons, micro clusters whose size is below k, and inliers between dense typical clusters visible, and it feeds a data-driven extreme-value threshold that separates typical points from anomalies. The paper shows on a series of counterexamples that this stray algorithm matches or beats both versions of HDoutliers in accuracy and is substantially faster, and it demonstrates the same approach on pedestrian-count data after converting days and sensors into feature vectors. If the claim holds, high-dimensional anomaly detection in fraud, security, environmental monitoring, and urban planning can be done with a simpler, faster, and more sensitive tool.","feed_headline":"Maximum-gap neighbours spot outliers HDoutliers misses","feed_subtitle":"The largest k-nearest-neighbour jump flags singletons, micro clusters, and inliers faster.","key_machinery":"The carrying object is the k-nearest-neighbour distance with the maximum gap, defined for each point as follows: compute its distances to the k nearest neighbours, take the successive differences between ordered distances, and record the largest difference as the point's anomalous score. For a singleton anomaly the maximum gap is typically the first nearest-neighbour distance; for a micro cluster of size less than k it is the jump from the cluster to the main body; for an inlier it is the large gap that separates it from every dense class. This score replaces the Leader-algorithm clustering step in HDoutliers, so the algorithm never down-samples the data and never lets close anomalous clusters act as each other's nearest neighbours. The threshold is set by assuming the scores' upper tail follows the exponential spacing law that governs extremes from the Gumbel maximum domain of attraction (a broad class of light-to-moderate-tailed distributions): the algorithm starts from the 50% of points with the smallest scores, fits an exponential to their upper tail, and walks upward through the remaining scores, updating the cut-off until a score exceeds it. The bottom-up search yields a binary typical/anomalous classification, and the scores themselves give each point a continuous anomaly rank.","core_discovery":"The central claim is that an anomaly is best characterised as a point whose nearest-neighbour structure contains a large distance gap, and that the largest such gap among the k nearest neighbours is a sufficient anomalous score in any dimension. On this definition, a group of up to k anomalous points no longer masks itself: each member sees the others among its nearest neighbours, but the jump from the group to the main body of data produces the maximum gap, so the whole group is flagged. The same score also catches inliers sitting between two dense classes, because their nearest neighbours are far away compared with the gaps inside the classes. The stray algorithm computes this score for every point, derives a cut-off from an extreme-value spacing model of the upper tail of the scores, and classifies everything above the cut-off as anomalous, assigning each point a continuous outlier rank. The paper demonstrates, on bivariate counterexamples and on the Melbourne pedestrian data, that this design removes the false negatives and false positives caused by the Leader-algorithm clustering step in HDoutliers and runs faster at scale.","pith_inferences":["Beyond the paper's examples, the same maximum-gap score could be applied to any distance matrix—kernel distances, graph distances, or embeddings—so the method may transfer to non-Euclidean anomaly detection after the same min-max normalisation.","A testable next step is to choose k from the data instead of by hand: since the paper interprets k as the maximum permissible size of a micro cluster, an adaptive k tied to local density or to the distribution of nearest-neighbour distances would remove the main user-set parameter.","If the extreme-value threshold is approximately correct for a wider class of distributions, the same spacing-based cutoff could give probabilistic meaning to the outputs of other distance- and density-based outlier scores, which usually rely on user-chosen thresholds."],"forward_implications":["Micro clusters of up to k points are detected directly from the gap score, so two anomalous clusters that sit close together no longer hide each other the way they do under HDoutliers.","Inliers—points that fall between dense typical classes—are flagged as anomalies, giving the algorithm a capability that the HDoutliers variants fail on when the inliers are near one another.","At α = 0.05 on anomaly-free Gaussian data, the stray algorithm reports lower false positive rates than both HDoutliers versions across dimensions 1, 10, and 100 and sample sizes from 100 to 10,000.","Because no clustering step is needed, stray runs far more quickly than HDoutliers with clustering, especially in dimensions above 10 and for large samples, and its brute-force variant is competitive with k-d-tree search.","The same algorithm carries over to time series and collections of scatterplots after feature engineering, which the paper demonstrates by detecting New Year's Eve and a concert day in Melbourne pedestrian data and by isolating the Southbank sensor."],"supporting_citations":[{"why":"Supplies the HDoutliers baseline algorithm that stray is designed to improve and the extreme-value threshold approach it builds on.","marker":"Wilkinson (2017)"},{"why":"States the spacing theorem for extremes in the Gumbel domain, the theoretical basis for modelling large score gaps as exponential spacings.","marker":"Weissman (1978)"},{"why":"Introduces the bottom-up threshold search and the 50% smallest-scores starting subset that stray adopts.","marker":"Schwarz (2008)"},{"why":"Provides the proposition on exponential spacings of Gumbel-domain order statistics that the threshold derivation relies on.","marker":"Burridge & Taylor (2006)"},{"why":"Defines the Leader clustering algorithm whose fixed-radius clustering step stray removes and identifies as a source of failure.","marker":"Hartigan & Hartigan (1975)"},{"why":"Supplies the HDoutliers R implementation used for comparisons, including the threshold-update behaviour that stray avoids.","marker":"Fraley (2018)"},{"why":"Characterises the Gumbel maximum domain of attraction, the distributional class assumed for the anomalous scores.","marker":"Embrechts, Klüppelberg & Mikosch (2013)"}],"fun_headline_variants":["Max-neighbor gap catches what HDoutliers misses","Stray algorithm uses largest k-NN jump to flag all outliers","One distance spike: new anomaly detector beats HDoutliers","Largest gap in k-nearest neighbours singles out groups and inliers","Anomaly score from max neighbor jump fixes HDoutliers blind spots"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the largest k-nearest-neighbour gap scores follow the same exponential spacing law as extremes of independent random values, so the extreme-value threshold carries its claimed false-positive probability; on dependent scores, or scores whose upper tail is not Gumbel-domain, the cut-off would be miscalibrated.","fun_headline_variants_meta":{"raw":{"variants":["Max-neighbor gap catches what HDoutliers misses","Stray algorithm uses largest k-NN jump to flag all outliers","One distance spike: new anomaly detector beats HDoutliers","Largest gap in k-nearest neighbours singles out groups and inliers","Anomaly score from max neighbor jump fixes HDoutliers blind spots"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1265,"prompt_tokens":886,"completion_tokens":379,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":291}},"tokens_in":502,"tokens_out":379,"duration_ms":4245,"temperature":1.0,"reasoning_tokens":291,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:54:19.597875+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the stray algorithm with α = 0.05 on anomaly-free data drawn from a heavy-tailed multivariate distribution (for example, a multivariate t with three degrees of freedom) across several dimensions and sample sizes; if the empirical false-positive rate clearly exceeds 0.05, or if the upper-tail spacings of the max-gap scores fail an exponential fit, the threshold assumption is not doing the claimed work.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the HDoutliers baseline algorithm that stray is designed to improve and the extreme-value threshold approach it builds on."}],"review_version":1}