{"id":"d053ad27-d62e-4518-9e1b-e6a547c27343","arxiv_id":"2506.13144","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A log-based 'conjugate graph' added to a standard ANN index redirects stuck searches to true nearest neighbors, improving Recall@1 from 41.74% to 93.42% on GIST1M with negligible query-cost increase.","lead":"EnhanceGraph adds a second, smaller graph alongside an existing nearest-neighbor index, built from past query results and from edges discarded during index construction. The second graph redirects searches that get stuck at a local answer, lifting recall on hard datasets from about 42% to 93% at similar speed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Self-generated query labels in Algorithm 3 rely on an unproven Voronoi-adjacency assumption; if x_e is not truly in x_b's cell, conjugate-graph routing edges point to wrong targets and the central recall gains are not guaranteed.","rationale":"The paper is honest about the heuristic nature of Algorithm 3 and provides Observations 1-3 and shot-rate experiments, which give empirical support that local optima are often the base point or its nearest neighbor; this is genuine evidence. However, those observations do not directly measure whether x_g equals the true nearest neighbor of x_e: the shot-rate analysis in Figure 11 tracks the local optimum's identity relative to the base point, not the correctness of the global-optimum label. The missing theorem after Algorithm 3 means there is no analytical fallback. The construction-log side (Algorithm 4) and the historical-log utilization are less exposed: historical logs come with externally supplied global optima, and construction-log edges are simply pruned candidate edges. Thus the weakest point is the self-generated label. The proposed brute-force test would settle whether the assumption is empirically safe on the claimed datasets. If it passes, the conditional verdict could be upgraded to ACCEPT; if it fails, the central mechanism is unsound. The reader's weakest_assumption identifies the same issue, so agreement is 'agree'.","tokens_in":31375,"tokens_out":8091,"duration_ms":85218,"concrete_test":"For each dataset (GIST1M and GloVe-200) and each ω in {0.51, 0.6, 0.7, 0.8, 0.9}, run Algorithm 3's query generation on all base points, compute x_g exactly as in line 8, and brute-force compute the true nearest neighbor of each x_e. Report the fraction of generated queries where x_g equals the true NN and the fraction where x_b is the true NN. If either fraction is below 0.95 for any setting, the self-generated conjugate-graph edges contain a substantial share of wrong labels, and the recall improvement cannot be attributed to the claimed routing mechanism.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section IV-B, Equation (1), the paper generates x_e = ω·x_b + (1−ω)·x_k with ω > 0.5. This only makes x_e closer to x_b than to x_k; it does not put x_e in the Voronoi cell of x_b among all data points. The paper's own caveat is 'in most cases (i.e., when the two cells are adjacent)'. In high-dimensional data, exact Voronoi cells of a base point and its k-NN are not guaranteed to be adjacent, and Algorithm 3 replaces exact k-NNs with the approximate set from Algorithm 4, so x_k may not even be a true near neighbor. When x_e falls in a third cell V D(x_t), the x_g chosen in Algorithm 3 line 8 from ANN_k(x_b) ∪ {x_b} is not the true nearest neighbor, and the added edge (x_l, x_g) encodes a wrong label. Future queries that converge to x_l would then be routed to a point that is not their global optimum; if such mislabeled edges are frequent, the conjugate graph can degrade recall rather than enhance it. The promised theorem after Algorithm 3 is absent from the text, leaving the correctness guarantee unsupported. Because the public-benchmark historical logs are also synthetic and sampled from the same distribution as the test queries, the large GIST1M gains (41.74% to 93.42%) hinge on this labeling step being correct for the generated queries.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes EnhanceGraph, a framework that augments a static graph-based ANNS index with a secondary ``conjugate graph.'' The conjugate graph stores two kinds of logged information: pruned edges from the construction process, and routing edges from search-log local optima to their presumed global optima. At query time, a standard greedy search runs on the proximity graph, and then the conjugate graph is used to hop from the local optimum to the global optimum and to supplement the k-NN result. The authors instantiate the framework on NSG, VAMANA, τ-MNG, and HNSW and report consistent Recall@1 and Recall@10 improvements across eight datasets, with the headline GIST1M Recall@1 gain from 41.74% to 93.42% at essentially unchanged QPS. The framework has been integrated into Ant Group's VSAG library.","tokens_in":31733,"tokens_out":5104,"duration_ms":58970,"significance":"If the claimed effect is real, EnhanceGraph is a practically valuable and general contribution: it turns byproduct logs into a cheap, index-agnostic accuracy booster, and the reported gains are consistent across multiple base indexes and datasets. The paper also ships a concrete implementation path (VSAG) and a simple, sound cost observation for Algorithm 2: only the neighbor lists of the local optimum and the global optimum are touched in the conjugate-graph stage. However, the central mechanism for self-generated search logs depends on an unproven Voronoi-adjacency assumption, and the promised correctness theorem is absent from the text. These issues bear directly on whether the reported recall gains can be attributed to correctly labeled routing edges or to a distributional artifact of the experimental setup.","major_comments":[{"comment":"The correctness of the self-generated labels rests on the claim that x_e = ω·x_b + (1−ω)·x_k lies in the Voronoi cell of x_b. Equation (1) only guarantees that x_e is closer to x_b than to x_k; it does not rule out a third base point x_t with dis(x_t, x_e) < dis(x_b, x_e). The paper itself concedes this holds only ``in most cases (i.e., when the two cells are adjacent),'' and no empirical evidence on the eight datasets is provided for cell adjacency or for the fraction of generated x_e whose exact nearest neighbor is x_b. When x_e falls outside VD(x_b), Algorithm 3 line 8 labels as ``global optimum'' the point argmin over ANN_{k_g}(x_b)∪{x_b}, which is not the true nearest neighbor, and the inserted edge (x_l, x_g) routes future queries to a wrong target. Because the large GIST1M gains depend on these edges, this is a load-bearing assumption. I ask the authors to either supply a proof under explicitly stated conditions or, more feasibly, measure empirically the fraction of generated queries whose exact NN is x_b on each dataset and show that mislabeled edges do not degrade recall.","section":"Section IV-B and Algorithm 3 (lines 6-10)"},{"comment":"The text states, ``We have the following theorem to guarantee the accuracy of the nearest neighbor search with our EnhanceGraph framework,'' but the theorem statement and proof are missing; the paragraph immediately moves to an approximation caveat. This is not a stylistic gap: it is the only place where the paper promises a formal justification for why self-generated routing edges cannot mislead the second-stage search. Please either state and prove the theorem, or explicitly replace the promise with a statement that Algorithm 3 is a heuristic whose validity is empirical.","section":"Section V-A, after Algorithm 3"},{"comment":"For the public datasets, the synthetic historical search log and the test queries are generated from the same distribution: both add noise sampled from U(−0.5η, 0.5η) to base vectors, with only the requirement that test queries do not coincide with historical ones. This distributional alignment means the reported gains, including GIST1M 41.74%→93.42%, may substantially overstate performance on ad-hoc or out-of-distribution queries. The FACE experiment, which uses real historical queries, shows a much smaller gain (99.8%→99.9%). Please evaluate with standard benchmark query sets or another held-out distribution, and clarify how the global-optimum labels for the synthetic logs were obtained (exact ground truth vs. approximate search).","section":"Section VI-A, Implementation, and Table III"},{"comment":"The Voronoi argument in Section IV-B is formulated in Euclidean space, but FACE and GloVe datasets use Inner Product and Angular distances. For these metrics the ``Voronoi cell'' of a point is not the Euclidean cell used in the derivation, and the interpolation x_e = ω·x_b + (1−ω)·x_k has no clear geometric interpretation under the actual distance. The paper should either extend the argument to the relevant distance functions or restrict the self-generated-query claim to Euclidean datasets and justify the experimental transfer separately.","section":"Section IV-B and Table I"}],"minor_comments":[{"comment":"The approximate k_g-NN set ANN_{k_g}(x_b) is used as a substitute for exact k-NNs when generating queries. Please state which construction-log search parameters produce this set and whether any filtering is applied to remove points that are not true k-NNs.","section":"Algorithm 3, line 4"},{"comment":"The sentence ``The resulting QPS reduction is equivalent to increasing the search parameter L by 2'' is too strong: accessing the neighbor lists of two extra nodes is not the same as enlarging the candidate heap during the entire greedy search. A precise comparison would require measuring visited nodes and distance computations.","section":"Section V-A, Discussion"},{"comment":"The phrase ``does not sacrifices search efficiency'' should read ``does not sacrifice search efficiency''; also, the abstract's claim of the greatest improvement ``from 41.74% to 93.42%'' should identify the dataset and the specific base index to avoid overgeneralization.","section":"Abstract and Section VI-B"},{"comment":"The caption and text describe ``Rank of Local Optimum'' and ``20-NNs Overlap Rate,'' but the y-axis labels in Figure 4 are partially garbled. Please redraw the figures with readable axis labels and define the unit on the x-axis (the value of η) explicitly.","section":"Figure 4 and Observation 1"},{"comment":"The paper lists FACE as Inner Product distance, but the search algorithm in Algorithm 1 is described in terms of a generic distance function. Please clarify how the local-optimum test (closest point to the query) behaves under inner-product similarity, which is not a metric.","section":"Section VI-A, Datasets"}],"recommendation":"major_revision","confidential_remarks":"The strongest part of the paper is the breadth of the empirical evaluation: consistent gains over four base indexes and eight datasets, plus an industrial integration. The main risk is not circular fitting but label correctness for self-generated queries. The missing theorem after Algorithm 3 is a completeness problem that the authors should fix; if they instead reframe the contribution as fully heuristic and add a direct empirical verification of the Voronoi assumption, the paper could be publishable after a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this paper has a genuinely useful idea and a hole in its theory. The conjugate graph—a side structure that stores pruned construction edges and search-log shortcuts from local optima to global optima—is new as far as the cited literature goes, and it works in the reported experiments. Four base indexes, eight datasets, consistent Recall@1 and Recall@10 gains at roughly unchanged QPS, modest memory overhead, and an industrial integration. The cost argument is sound: at most two extra nodes' neighbors are examined per query.\n\nWhat is actually new is the combination of the two logs. Construction logs are usually discarded after pruning; search logs are usually ignored entirely. Using them together as a small second graph is simple and effective. The paper also deserves credit for the L2 dependence analysis—it clearly shows the conjugate graph only pays off when the search converges to the same local optimum as during log collection.\n\nThe soft spots are real but proportionate. The self-generated query heuristic (x_e = ω x_b + (1−ω) x_k) only guarantees x_e is closer to x_b than to x_k, not that x_e lies in x_b's Voronoi cell. The paper admits this—'in most cases'—and then promises a theorem that never appears. The text says 'we have the following theorem' and then moves on. That is a missing formal piece, not a fatal flaw, because Figure 11 empirically shows the local optima are usually the base point or its nearest neighbor; but the guarantee is absent and the mislabeling rate on high-dimensional data is unmeasured.\n\nThe more serious evaluation issue: the public-benchmark test queries are synthetic, generated from the same distribution as the historical search log used to build the conjugate graph. That is the right setup for an industrial system where the log matches the future workload, but it makes the headline numbers (41.74% to 93.42% on GIST1M) not directly comparable to standard ANN bench results. The authors should report on the original query sets, or at least present both.\n\nNo code or commit hash is provided, so the claims are not independently reproducible from the paper alone.\n\nBottom line: the core idea is sound and the experiments are extensive, but the missing theorem and the distributional overlap need to be addressed. This deserves a serious referee, with major revision. I'd bring it to reading group and I'd cite it if I worked in this area.","headline":"Genuinely novel log-driven graph enhancement with solid empirical gains; the missing theorem and same-distribution test queries are the main soft spots.","tokens_in":32247,"tokens_out":5335,"would_cite":true,"duration_ms":56861,"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":"Replaying failed searches lifts ANN recall from 42% to 93%","keywords":["approximate nearest neighbor search","graph-based index","conjugate graph","search log","construction log","recall improvement","Voronoi cell","high-dimensional indexing"],"falsifier":"Take a high-dimensional dataset (or a synthetic one with engineered nearest-neighbor layouts), generate queries $x_e = \\omega x_b + (1-\\omega)x_k$ for $\\omega>0.5$, and test whether $x_b$ is the exact nearest neighbor of $x_e$. If a large fraction of generated queries fail that test, Algorithm 3 writes conjugate edges to a point that is not the global optimum, and the reported Recall@1 gains should shrink or reverse on those queries.","tokens_in":31175,"feed_emoji":"📈","tokens_out":7122,"duration_ms":72942,"temperature":0.7,"pith_summary":"EnhanceGraph argues that graph-based approximate nearest neighbor indexes need not stay static after construction: the failures and near-misses recorded while serving queries, plus the edges discarded during construction, contain exactly the information needed to fix the index. The paper proposes a conjugate graph attached to any proximity graph, storing routing edges from local optima to global optima (from search logs) and pruned k-NN edges (from construction logs). At query time, after the ordinary greedy search stalls at a local optimum, the conjugate graph redirects the search to the true nearest neighbor and supplies the missing k nearest neighbors. The claimed payoff is a large recall gain at essentially unchanged query throughput, with the largest reported improvement from 41.74% to 93.42% Recall@1 on GIST1M.","feed_headline":"Replaying failed searches lifts ANN recall from 42% to 93%","feed_subtitle":"A conjugate graph reuses past local optima and pruned edges to raise Recall@1 and Recall@10 at the same query speed.","key_machinery":"The load-bearing object is the conjugate graph $G'$, a directed companion to the proximity graph $G$ that is not used for routing during the main search. It stores two kinds of edges: routing edges $(x_l, x_g)$ from a local optimum to the global optimum found in the search log, and non-routing edges that were pruned during construction, so that $G'[x_b]$ holds the discarded candidates from the construction log. Update (Algorithm 3) generates error-prone query points $x_e = \\omega x_b + (1-\\omega)x_k$ near the boundary of the base point's Voronoi cell, greedily searches them, and records $(x_l, x_g)$ whenever the local optimum misses the base point. At query time, Algorithm 2 first runs the ordinary greedy search, then takes the neighbors of the local optimum and of the recovered global optimum in $G'$ and merges them into the candidate set, which is equivalent to raising the search list size by about two.","core_discovery":"The paper's central claim is that a static proximity graph's two recurring failure modes can be diagnosed and repaired from data the index itself generates. When a greedy search stops at a local optimum $x_l$ instead of the true nearest neighbor $x_g$, many similar queries converge to that same $x_l$; recording the missing edge $(x_l, x_g)$ in a conjugate graph lets every later query that reaches $x_l$ step directly to $x_g$. Similarly, when construction prunes legitimate k-NN edges, storing those pruned edges in the same conjugate graph and reading them after the global optimum is found lifts Recall@k. The paper backs this with a theorem (with positive recall, the local optimum lies in the true k-NN set), with observations that local optima are usually close neighbors of the global optimum and that similar queries share local optima, and with a query-generation scheme placing synthetic queries near Voronoi cell boundaries to expose flaws. On top of existing graph indexes such as HNSW, NSG, Vamana, and tau-MNG, the framework reports consistent recall improvements at comparable query-per-second rates.","pith_inferences":["If the effect holds in production, a deployment could close the loop: every failed query logged during serving becomes a training edge, so the index improves with age rather than staying fixed at a known-bad state.","The same two-phase idea could be transplanted to partition-based and compressed indexes, where the 'local optimum' would be the best cell or bucket reached and the conjugate step would cross to better cells using logged failures.","The Voronoi-boundary query generator suggests a testable diagnostic for index health: the distribution of distances from generated points to their labelled global optimum measures how often the weakest assumption actually breaks in high dimensions.","A natural stress test is distribution shift: if new queries no longer resemble the logged ones, the conjugate edges become stale, and an adaptive version should retrain the conjugate graph from recent logs."],"forward_implications":["Applying EnhanceGraph to a graph index raises Recall@1 substantially where the baseline is weak; the paper reports the largest jump from 41.74% to 93.42% on GIST1M.","The same conjugate graph lifts Recall@10 because the stored construction-log edges restore pruned k-NN connections once the global optimum is reached.","Because the conjugate graph is consulted only after the proximity-graph search ends, the throughput cost is roughly that of increasing the search parameter L by 2, not a full re-run.","The framework is index-agnostic: it works by wrapping an existing graph index rather than building a new proximity graph from scratch, and it is demonstrated on four established graph indexes.","The benefit is tied to the search parameter used when collecting logs: at query time, using a list size L larger than the logged L2 can overshoot the logged local optimum and miss the conjugate edge, so the method is most effective near the logged operating point."],"supporting_citations":[{"why":"Supplies the MRNG edge-pruning strategy and the NSG baseline; its monotone decreasing path property underpins the analysis of local optima.","marker":"[7]"},{"why":"The HNSW baseline whose static index exhibits repeated recognition failures motivating the work.","marker":"[9]"},{"why":"Defines the RNG pruning criterion that removes long triangle edges, the type of construction-log edge the conjugate graph restores.","marker":"[20]"},{"why":"The Vamana/DiskANN index that serves as one of the four baselines and one of the paper's integration targets.","marker":"[23]"},{"why":"The tau-MNG baseline whose long/short-edge pruning criteria are compared and enhanced.","marker":"[24]"},{"why":"Provides the formal definition of Voronoi cells used in the heuristic for generating error-prone queries.","marker":"[28]"},{"why":"Defines k-NN graphs, the reference structure whose pruned edges the construction log tries to preserve.","marker":"[18]"}],"fun_headline_variants":["Reusing failed searches lifts ANN recall from 42% to 93%","Graph index learns from its own mistakes to boost recall","EnhanceGraph: past logs power higher recall at same speed","Failed searches become stepping stones to better ANN recall","Recall 42% to 93% by learning from past query failures"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework depends on the claim that a query produced along the segment between a base point and one of its nearest neighbors actually falls inside the base point's Voronoi cell, so the base point is that query's true nearest neighbor; the paper notes this is only guaranteed in most cases, when the two cells are adjacent.","fun_headline_variants_meta":{"raw":{"variants":["Reusing failed searches lifts ANN recall from 42% to 93%","Graph index learns from its own mistakes to boost recall","EnhanceGraph: past logs power higher recall at same speed","Failed searches become stepping stones to better ANN recall","Recall 42% to 93% by learning from past query failures"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000256,"raw_usage":{"total_tokens":1602,"prompt_tokens":1001,"completion_tokens":601,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":617,"completion_tokens_details":{"reasoning_tokens":514}},"tokens_in":617,"tokens_out":601,"duration_ms":6850,"temperature":1.0,"reasoning_tokens":514,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:37:00.406025+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a high-dimensional dataset (or a synthetic one with engineered nearest-neighbor layouts), generate queries $x_e = \\omega x_b + (1-\\omega)x_k$ for $\\omega>0.5$, and test whether $x_b$ is the exact nearest neighbor of $x_e$. If a large fraction of generated queries fail that test, Algorithm 3 writes conjugate edges to a point that is not the global optimum, and the reported Recall@1 gains should shrink or reverse on those queries.","supporting_citations":[{"cited_title":"Fast approximate nearest neighbor search with the navigating spreading-out graph,","cited_arxiv_id":null,"evidence_quote":"Supplies the MRNG edge-pruning strategy and the NSG baseline; its monotone decreasing path property underpins the analysis of local optima."},{"cited_title":"The relative neighbourhood graph of a finite planar set,","cited_arxiv_id":null,"evidence_quote":"Defines the RNG pruning criterion that removes long triangle edges, the type of construction-log edge the conjugate graph restores."},{"cited_title":"Diskann: Fast accurate billion-point nearest neighbor search on a single node,","cited_arxiv_id":null,"evidence_quote":"The Vamana/DiskANN index that serves as one of the four baselines and one of the paper's integration targets."},{"cited_title":"V oronoi diagrams—a survey of a fundamental ge- ometric data structure,","cited_arxiv_id":null,"evidence_quote":"Provides the formal definition of Voronoi cells used in the heuristic for generating error-prone queries."},{"cited_title":"Fast approximate nearest-neighbor search with k-nearest neighbor graph,","cited_arxiv_id":null,"evidence_quote":"Defines k-NN graphs, the reference structure whose pruned edges the construction log tries to preserve."}],"review_version":1}