{"id":"7e4d0fad-e77d-4993-a7e3-e507be6a2bca","arxiv_id":"2509.00365","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"CRouting prunes unpromising neighbors in graph-based ANNS by estimating their distance with a fixed angle from the dataset's angle distribution, cutting distance computations by up to 41.5% and boosting QPS by up to 1.48x.","lead":"This paper proposes CRouting, a plugin that speeds up graph-based approximate nearest neighbor search by skipping distance calculations it estimates as unlikely to improve the result. Tests on HNSW and NSG show up to 1.48x higher query throughput and up to 41.5% fewer distance computations at matched recall.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Accuracy claim rests on unmeasured revisit recovery; single-angle pruning demonstrably removes the small-angle positive nodes the method needs.","rationale":"The paper is a competently executed empirical systems contribution with released code, and the reported speedups are internally consistent with the provided curves. The central claim, however, is not just that distance calls are reduced—it is that accuracy is maintained. The mechanism that restores accuracy is the revisit heuristic, and the paper provides no measurements of revisit rates, no proof of recovery, and explicitly declines to bound the approximation error (§5.4). Table 3 shows that the pruning-only component catastrophically drops recall precisely because it removes small-angle positive nodes; CRouting's success therefore rests entirely on the unverified assumption that those nodes are reached again through other paths. This is the same load-bearing assumption identified by the Reader, and it is a genuine soft spot: if the graph is sparser, the query distribution shifts, or the angle threshold is chosen differently, the recovery mechanism could fail while the distance-call reduction remains. A conditional acceptance is appropriate: the empirical evidence supports the claims on the tested workloads, but the 'same accuracy' generalization should be validated by measuring the revisit-recovery process directly and by selecting the threshold on held-out queries.","tokens_in":20811,"tokens_out":6679,"duration_ms":83103,"concrete_test":"Instrument the released code to log, for each node marked pruned at Algorithm 2 line 12, (i) whether its exact distance would have passed the upper-bound test, and (ii) whether it is later revisited and exact-computed before termination. Run on all five datasets with HNSW/NSG at efs=100, 300 and thresholds at the 50th, 90th, and 99th percentiles. If the fraction of false-positive prunings that are never revisited is non-negligible (e.g., >1% of all pruned nodes), or if recall@10 at matched efs falls below the HNSW/NSG baseline by more than 0.01, the revisit heuristic does not carry the accuracy claim. Repeat on a low-connectivity variant (HNSW M=8, NSG R=20) to see whether recovery degrades when alternative paths are scarce.","verdict_should_be":"UNCHANGED","load_bearing_attack":"CRouting's accuracy guarantee hinges on the assumption that a single fixed angle (the 90th percentile) approximates ∠ncq well enough that pruned positive nodes are later recovered through alternate graph paths. The justification in §3.3 uses the high-dimensional 'random vectors are nearly orthogonal' property, and Figure 7 shows global angle concentration. But the angles of decision-relevant neighbors are not drawn from this global distribution: positive nodes—those that would enter the candidate set—are biased toward small ∠ncq. The paper's own Figure 9 and Table 3 expose this: pruning-only CRouting_O drops DEEP recall from 0.978 to 0.453 at efs=100, showing that exactly the informative small-angle nodes are pruned. CRouting's final recall therefore depends entirely on the unproven claim (§4.2, Figure 1) that such nodes are revisited through other graph paths. No error bound is given (§5.4), and the revisit rate is not measured. If the graph is sparser or the query distribution differs from the random sampling used to set θ, the recovery mechanism can fail silently, so 'maintaining the same accuracy' is not established beyond the tested configurations.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CRouting, a plugin for graph-based approximate nearest neighbor search (HNSW and NSG) that avoids many exact distance computations during greedy search. The idea is to estimate dist(n,q) with the cosine theorem using the already-known dist(c,q) and stored dist(c,n), substituting a fixed representative angle θ (the 90th percentile of a measured angle distribution) for the actual angle ∠ncq. Nodes whose estimated distance is not below the current upper bound are pruned; a subsequent error-correction step recomputes exact distances if a pruned node is encountered again via another path. The paper reports up to a 41.5% reduction in distance calls, QPS gains up to 1.48x, construction overhead below 4%, and memory overhead of 2-21% on five public datasets. The code is publicly available.","tokens_in":21062,"tokens_out":5651,"duration_ms":72401,"significance":"If the reported gains hold beyond the specific configuration tested, CRouting would be a practical, low-overhead drop-in optimization for two widely used graph indexes. The paper has clear strengths: it compares against two routing baselines (TOGG and FINGER), includes an ablation isolating the pruning and error-correction components (CRouting_O vs CRouting), reports construction time and index-size overhead, and evaluates generality across distance metrics and dataset scales. The main claims are internally consistent: the 1.71x distance-call speedup corresponds to a 41.5% reduction. However, the central accuracy claim depends on a parameter (θ percentile) that is selected post hoc on the same benchmark datasets, and on an unmeasured revisit-recovery mechanism. The paper explicitly acknowledges at §5.4 that no approximation error bound is proved. These load-bearing gaps need to be addressed before the results can be considered established.","major_comments":[{"comment":"The pruning threshold θ is a free parameter, and the paper selects the 90th percentile because it gives the best recall-QPS curves on the same five datasets used in the headline evaluation. This is a post hoc selection on the test bed: the reported 41.5% distance-call reduction and up to 1.48x QPS are therefore not independent predictions for those datasets. In addition, Figure 13 shows only the GIST dataset, while §5.5 states the 90th percentile is consistently best 'across all datasets and algorithms' without showing the supporting curves. The paper should either fix θ by an a-priori rule (e.g., based on dimensionality) or evaluate on a calibration split, and should report the sensitivity grid for all datasets.","section":"§5.5, Figure 13"},{"comment":"The final recall of CRouting rests entirely on the error-correction mechanism, but the paper provides no direct evidence that incorrectly pruned positive nodes are actually revisited and reinserted. Table 3 shows that pruning alone (CRouting_O) collapses recall from 0.978 to 0.453 at efs=100, and CRouting recovers only to 0.917, not to the 0.978 baseline. §5.4 reports relative error and incorrect-pruning ratios (max 5.83%) but does not measure how many of those incorrectly pruned nodes are later reached through alternative paths, which is the key assumption of Figure 1. Without a revisit-rate measurement or an oracle experiment, the claim that 'the same accuracy' is maintained is not established. Add a direct metric: fraction of pruned positive nodes later visited and inserted into the candidate set, and an ablation that compares against an oracle that never prunes positives.","section":"§5.4, §4.2, Table 3"},{"comment":"The theoretical motivation assumes 'the position of neighbor n is completely random with respect to the current node c,' so that ∠ncq follows the near-orthogonal random-vector distribution. This is not consistent with how proximity graphs are built: neighbors are selected precisely because they are close to c, and the nodes that matter for the search (positive nodes) are biased toward small angles, as the paper's own Figure 9 and Table 3 demonstrate. The fixed-angle estimate is therefore systematically biased for exactly the nodes where pruning decisions matter. The paper should either frame the angle concentration as an empirical observation only, or analyze the conditional angle distribution for decision-relevant nodes and show that the representative angle remains safe under different graph densities and query distributions.","section":"§3.3, §4.2"}],"minor_comments":[{"comment":"The 'speedup in distance calls' is defined as the ratio to the brute-force method, but the experiments compare against vanilla HNSW/NSG, not brute force. Please clarify the baseline in the definition.","section":"§5.1"},{"comment":"Caption reads 'HSNW' for HNSW; please fix the typo.","section":"Figure 7 caption"},{"comment":"The section heading 'Sensitive Analysis' should be 'Sensitivity Analysis'.","section":"§5.5 heading"},{"comment":"The formula IPDist(c,q) = 1 - ||c||||q||cosθ is unconventional. If this is the definition used in the implementation, please define it explicitly and state how it relates to standard inner-product distance on unnormalized vectors.","section":"§4.3"},{"comment":"The sentence 'the angle distribution is solely determined by the dimensionality' refers to the random-vector density in Eq. (3), but the subsequent argument correctly notes that the search-path angle distribution depends on the dataset. Please rephrase to avoid the apparent contradiction.","section":"§3.3"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"CRouting is a genuinely practical plugin for HNSW and NSG that cuts distance calls by up to 41.5% and raises QPS up to 1.48x on the tested sets. The core idea—estimate neighbor-query distances with the cosine theorem using a single dataset-specific angle, then recheck pruned nodes when they are revisited—is new relative to TOGG and FINGER, and the paper is honest about what it does not prove. The ablation is clear: pruning alone (CRouting_O) kills recall, and the error-correction step brings it back. The time breakdown is useful, and the code is public.\n\nThe main soft spots are two. First, the pruning threshold (90th percentile) is chosen after looking at the sensitivity curves on the same evaluation datasets (Figure 13). That makes the headline gains partly a function of post hoc tuning; no hold-out or run-to-run variance is reported. Second, the accuracy guarantee leans on an unmeasured mechanism: the claim that wrongly pruned nodes are later revisited through other graph paths. The paper's own Table 3 shows CRouting_O drops DEEP recall from 0.978 to 0.453 at efs=100, which tells you that the informative small-angle nodes are exactly the ones getting pruned, and the recovery rate is never measured. The authors explicitly decline to provide approximation error bounds (§5.4). None of this breaks the central empirical claim for the tested datasets, but it does mean the \"same accuracy\" statement is a property of these experiments, not a demonstrated general result.\n\nWho should read it: system builders working on vector indexes and anyone comparing pruning techniques. This deserves a serious referee. The right asks are a hold-out or principled threshold rule and some measurement of the recovery mechanism (e.g., what fraction of pruned positive nodes are eventually re-examined). If those hold, this is a solid contribution to the ANNS engineering literature.\n\nI would send it to peer review.","headline":"A clean, honestly-reported pruning plugin for HNSW/NSG; the gains are real on the tested data, but post hoc threshold selection and an unverified recovery mechanism keep the generality claims from being fully established.","tokens_in":21570,"tokens_out":2385,"would_cite":true,"duration_ms":28546,"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":"CRouting estimates neighbor–query distances with a single dataset-derived angle in the cosine theorem, pruning up to 41.5% of distance calls on HNSW and NSG without losing recall.","keywords":["approximate nearest neighbor search","graph-based ANNS","distance computation reduction","cosine theorem distance estimation","angle distribution","pruning strategy","error correction","HNSW/NSG"],"falsifier":"On a given dataset and graph, measure the actual distribution of the routing angle along real search paths and compare it with the single fixed value CRouting uses; if the spread is wide, the estimate error grows. Then run CRouting with the 90th-percentile threshold on an anisotropic or strongly clustered dataset, for example synthetic mixtures of Gaussians with local directional structure, and compare its recall-QPS curve against exact greedy search: if recall at matched efS falls below the baseline, or if the fraction of wrongly pruned nodes that are never revisited exceeds the fraction rest","tokens_in":20712,"feed_emoji":"📐","tokens_out":6196,"duration_ms":70766,"temperature":0.7,"pith_summary":"The paper claims that the dominant cost in graph-based approximate nearest neighbor search is repeated exact distance computations, most spent on neighbors that never enter the candidate set. CRouting attacks this by estimating the distance from a neighbor to the query using two known distances and one fixed angle taken from the dataset's angle distribution, via the cosine theorem. If the estimate exceeds the current upper bound, the neighbor is pruned without an exact distance call; a revisit-based error-correction step then recomputes exact distances for pruned nodes that reappear through other graph paths. On HNSW and NSG over five datasets, the paper reports up to 41.5% fewer distance computations and up to 1.48x higher queries per second at matched recall, with construction time overhead under 4% and memory overhead of 2% to 21%. A sympathetic reader would care because CRouting is designed as a minimal-code plugin to two widely used graph indexes.","feed_headline":"One angle prunes 41.5% of ANNS distance calls","feed_subtitle":"A single dataset-derived angle, plugged into the cosine theorem, skips neighbors that would never enter the candidate set.","key_machinery":"The load-bearing object is the angle distribution of theta = angle(n, c, q), reduced to a single scalar: the 90th percentile of the dataset's measured angle values. CRouting replaces each exact distance call with a cosine-theorem estimate built from the stored edge length dist(c,n), the known dist(c,q), and that fixed representative angle. The error-correction pass rides on graph connectivity: a node pruned at one frontier is likely to be reached from another frontier, at which point its exact distance is computed before it is used.","core_discovery":"The central claim is that the angle between the edge from the current node to a neighbor and the edge from the current node to the query concentrates around a dataset-specific value, so a single representative angle can stand in for every such angle in the cosine theorem. With the neighbor distance saved from graph construction and the current-node-to-query distance already known, the neighbor-to-query distance becomes a few arithmetic operations; if the estimate lies beyond the candidate set's upper bound, the neighbor is skipped. Because the estimate is approximate, CRouting marks pruned nodes and computes their exact distance if they are encountered again, betting that graph connectivity","pith_inferences":["The single-angle approximation is likely to be most reliable on graphs whose edges are built by diversity- or spread-out-promoting criteria; on graphs with strong directional hub structure, the actual per-node angle distribution may vary with node degree, so an extension would measure theta separately by degree class and use a per-class representative angle.","Because error correction only recovers pruned nodes that are revisited through other paths, datasets with weak connectivity or very small candidate-queue limits could see recall loss at aggressive pruning; an adaptive threshold tied to efS or candidate-queue size is a natural testable extension.","The 90th-percentile threshold is chosen empirically; the paper's own framework could support a tunable accuracy-latency budget by treating the angle as a continuous knob and precomputing the trade-off curve between pruning ratio and revisit cost for a given dataset.","CRouting's scalar estimate could serve as a cheap coarse pre-filter in front of more expensive estimators, such as residual-vector or LSH-based distance decompositions, reducing the number of times those heavier estimators must run."],"forward_implications":["Distance-call speedups of 1.22x to 1.58x over HNSW and 1.15x to 1.71x over NSG at matched recall translate directly into QPS gains of up to 1.48x and 1.47x, making the method a drop-in accelerator for greedy-search-based graph indexes.","At 95% recall, CRouting cuts the time spent on negative-node distance calls by roughly 47% to 62%, and total search runtime by 12% to 31%, since the pruning check itself costs only a few multiply-add operations.","The plugin's overhead stays low: construction time rises by no more than 1% on HNSW and 4% on NSG, while index memory grows by 2% to 21%, with the ratio shrinking as dimensionality increases.","The reported gains hold across distance metrics (Euclidean, inner-product, cosine), across dataset sizes up to 100 million vectors, and across different graph-neighbor counts, with larger neighbor counts making the pruning opportunity larger."],"supporting_citations":[{"why":"Supplies the HNSW graph index and greedy-search baseline that CRouting plugs into and accelerates.","marker":"[55]"},{"why":"Supplies the NSG graph index and baseline, the second target algorithm in the evaluation.","marker":"[26]"},{"why":"Supplies the high-dimensional geometry fact that random vectors are nearly orthogonal, motivating the concentrated angle distribution.","marker":"[9]"},{"why":"Supplies the FINGER routing method, the main accuracy-preserving competitor whose construction and memory overhead CRouting is compared against.","marker":"[15]"},{"why":"Supplies the TOGG routing method, the direction-based competitor showing the accuracy loss CRouting avoids.","marker":"[76]"},{"why":"Supplies the SIFT and GIST benchmark datasets used to measure the reported recall, QPS, and speedup numbers.","marker":"[1]"}],"fun_headline_variants":["Angle routing cuts 41.5% of ANNS distance calls","CRouting: one angle prunes 41.5% of graph distances","Skip needless distance calls with CRouting's angle trick","Graph ANNS speedup: 41.5% fewer distance calcs via angles","Angle-based routing boosts ANNS QPS 1.48x"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The method assumes that one fixed angle, measured from the dataset, is close enough to the real angle at every routing step that the cosine-theorem estimate prunes mostly useless neighbors, and that any useful neighbor it wrongly prunes will be reached again through another graph path.","fun_headline_variants_meta":{"raw":{"variants":["Angle routing cuts 41.5% of ANNS distance calls","CRouting: one angle prunes 41.5% of graph distances","Skip needless distance calls with CRouting's angle trick","Graph ANNS speedup: 41.5% fewer distance calcs via angles","Angle-based routing boosts ANNS QPS 1.48x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000178,"raw_usage":{"total_tokens":1095,"prompt_tokens":670,"completion_tokens":425,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":414,"completion_tokens_details":{"reasoning_tokens":330}},"tokens_in":414,"tokens_out":425,"duration_ms":5371,"temperature":1.0,"reasoning_tokens":330,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:39:29.486780+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a given dataset and graph, measure the actual distribution of the routing angle along real search paths and compare it with the single fixed value CRouting uses; if the spread is wide, the estimate error grows. Then run CRouting with the 90th-percentile threshold on an anisotropic or strongly clustered dataset, for example synthetic mixtures of Gaussians with local directional structure, and compare its recall-QPS curve against exact greedy search: if recall at matched efS falls below the baseline, or if the fraction of wrongly pruned nodes that are never revisited exceeds the fraction rest","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the NSG graph index and baseline, the second target algorithm in the evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the high-dimensional geometry fact that random vectors are nearly orthogonal, motivating the concentrated angle distribution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the FINGER routing method, the main accuracy-preserving competitor whose construction and memory overhead CRouting is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the TOGG routing method, the direction-based competitor showing the accuracy loss CRouting avoids."}],"review_version":1}