{"id":"d2471fe3-4f7e-4ad9-a00f-7def36a13a25","arxiv_id":"2507.17647","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A graph-preserving HNSW for disaggregated memory that uses logical cache partitioning and adaptive query routing, reaching single-machine accuracy without partitioned-graph accuracy loss.","lead":"Shine runs the HNSW approximate nearest neighbor search index on disaggregated memory, where compute and memory are separate machines linked by RDMA. It preserves the full search graph instead of sharding it, and it speeds up queries by splitting the graph among compute nodes so their caches hold different data and are routed adaptively.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The routing oracle's k-means clustering on a tiny high-level HNSW sample may not predict base-level cache locality; without a random-routing ablation the claimed gains are not isolated.","rationale":"The reader's CONDITIONAL verdict is appropriate. I reviewed the graph-preserving accuracy claim and found it logically sound: the index layout (Sec. 3.1) retains all edges, the search algorithm (Alg. 1) is identical to standard HNSW except for remote reads, and the evaluation correctly states that recall need not be re-measured if the graph is truly preserved. Still, a recall comparison would be a cheap, prudent confirmation. The weakest link is the performance story. Shine-Cached-Aqr's throughput advantage comes from routing queries to a CN whose cache is specialized for that query's region. That mechanism depends on the oracle's centroid-distance ranking matching the actual base-level nodes visited by the HNSW walk. The paper provides end-to-end CHR/CSP evidence that the mechanism works on five datasets, but it does not isolate the oracle's contribution from the load-balancing effect of adaptive routing, nor does it justify clustering on a tiny high-level node sample. The proposed ablation would settle whether the k-means oracle is genuinely load-bearing or whether a cheaper policy suffices. This is a validation gap, not a refutation, so the verdict remains CONDITIONAL.","tokens_in":28108,"tokens_out":11585,"duration_ms":132928,"concrete_test":"Run an ablation on SPACEV and TTI with 5 CNs: (a) Shine-Cached-Aqr as reported; (b) same adaptive routing but with the oracle replaced by random balanced assignment of queries to CNs (no k-means); (c) same adaptive routing but with k-means centroids computed on a random sample of 100k base-level nodes instead of the high-level sample. If (b) achieves comparable CHR/throughput, the k-means oracle is not the source of the gains. If (c) materially improves CHR/CSP over the reported high-level-sample oracle, the current clustering sample is suboptimal and the Sec. 6.2 assumption is only partially validated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The performance contribution of Sections 6–7 rests on an unvalidated equivalence: the oracle's centroid ranking is assumed to predict which CN will have the best cache hit rate for a query. This is load-bearing because the sole advantage of Shine-Cached-Aqr over Shine-Cached is the logical partition plus routing; if routing does not send queries to the partition that owns the nodes the HNSW walk will visit, the CHR gains and the headline 1.7x throughput improvement vanish. The paper's clustering (Sec. 6.2) compounds the risk by computing balanced k-means on a tiny sample—the first level from the top with ≥1000 nodes—rather than on base-level nodes, which dominate cache misses (5770 of 6020 visited nodes for TTI, Sec. 5 Discussion). High-level nodes are hubs and are not representative of base-level query locality; with only |CN|=5 centroids, the sample may not even cover all dense query regions. Table 2 reports large CHR/CSP improvements, but no ablation isolates whether these come from the k-means oracle or from the balanced/adaptive routing that reduces duplicate cache entries. Figure 7 compares routing policies, but all use the same k-means oracle; a random-routing control is missing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SHINE, a distributed HNSW index for disaggregated memory. The index stores a global HNSW graph on memory nodes and preserves all edges, so the exact traversal and hence the accuracy of a single-machine HNSW is retained by construction. To reduce RDMA read amplification, SHINE adds per-compute-node caching, a logical partition of the graph built with balanced k-means, and an adaptive query-routing policy that sends each query to the compute node whose partition centroid is closest to the query. The evaluation on five 100M-vector datasets reports throughput improvements over three variants of SHINE and a new cache segmentation penalty metric. The paper also positions SHINE as the first graph-preserving HNSW index for disaggregated memory.","tokens_in":28371,"tokens_out":4606,"duration_ms":53064,"significance":"If the empirical claims hold, SHINE is a useful contribution to systems for approximate nearest neighbor search on disaggregated memory. The graph-preserving design is a clean and principled way to avoid the accuracy loss that comes from sharding HNSW graphs, and the same-accuracy claim is definitional if the graph and traversal are indeed preserved. The caching, logical partitioning, and adaptive routing address a real bandwidth bottleneck, and the authors provide an open-source implementation. The main risk is that the key mechanism behind the reported gains—the k-means oracle—is not independently validated. The evaluation also lacks measured recall values, error bars, and a comparison with existing distributed HNSW systems. These are addressable with additional experiments, so the paper merits major revision rather than rejection.","major_comments":[{"comment":"The central efficiency claim—that logical index partitioning and adaptive routing raise throughput by up to 1.7×—rests on an unvalidated assumption: that balanced k-means clustering on the first HNSW level with at least 1000 nodes (i.e., high-level hub nodes) predicts base-level cache locality. The discussion in §5 notes that for TTI, 5770 of 6020 visited nodes are at the base level, so the sample used for clustering is not representative of the nodes that dominate cache misses. Moreover, Figure 7 compares routing policies that all use the same k-means oracle; there is no random-routing control or ablation that isolates the oracle's contribution. Please add a random-routing baseline and a variant that routes according to a ground-truth partition derived from base-level query traversal; report CHR and throughput for each. Without this, the 1.7× improvement cannot be attributed to the proposed routing scheme.","section":"§6.2, §7.2, Table 2"},{"comment":"The cache segmentation penalty is defined in Eq. (1) as CSP = 1 − CHR/CHRmax, where CHRmax is the hit rate of a hypothetical single shared cache of the same total size. The paper reports CSP values in Table 2, but CHRmax is never measured or described. A reader cannot verify whether the reported CSP values are consistent with Definition 6.1, and the metric is not falsifiable from the data as presented. Please report how CHRmax is obtained (e.g., by simulating a global cache with deduplicated entries across all compute nodes) and include the CHRmax values used for each dataset and workload.","section":"§6.1, Table 2"},{"comment":"The abstract and Section 3 claim that SHINE 'reaches the same accuracy as a single-machine HNSW.' This is justified by construction, because the graph is preserved, but the paper explicitly states that accuracy is not evaluated ('our goal is not to evaluate the accuracy'). No end-to-end recall measurement is reported for the actual distributed implementation, so the claim is not verified experimentally. Please report R@10 for SHINE and for a single-machine HNSW on the same query sets and efS values, even for a single configuration, to confirm that the distributed remote-pointer traversal and caching do not introduce any accuracy regression.","section":"§8.1, §8.2"},{"comment":"The throughput improvements are reported without error bars or repeated runs. The statements such as 'improvement of 1.7× w.r.t. Shine' are single numbers from presumably one run, and the comparison is only against the authors' own baselines. Since the efficiency claim is central, please report the number of runs and the variance, or clearly state that each point is a single run. It would also strengthen the paper to include at least one comparison against a partitioned distributed HNSW baseline (e.g., the d-HNSW approach discussed in §9) to contextualize the gains.","section":"§8.2–§8.4"}],"minor_comments":[{"comment":"The admission probability for base-level nodes (1%) is a tuned parameter that strongly affects cache behavior. Please provide a sensitivity plot or a short discussion of how this value was chosen.","section":"§5.2"},{"comment":"The choice of the first level from the top with at least 1000 nodes as the clustering sample is heuristic. Please justify this choice or show that results are robust to the sample level.","section":"§6.2"},{"comment":"The statement 'a single core on our MNs can route about 167k queries per second' is given without a measurement or citation. Either provide the measurement or remove the specific number.","section":"§7.1"},{"comment":"In the text, 'modern CPUs use only 248 bits of the address space' should be '48 bits' (or '2^48 addresses').","section":"§3.1"},{"comment":"The cache size sensitivity is only shown for uniform workloads. A brief statement or figure for skewed workloads would make the sensitivity analysis complete.","section":"§8.4"},{"comment":"The limitation that the index does not support efficient updates is acknowledged in the text. Given that this is a static index, a short statement in the conclusion reiterating this scope would help readers.","section":"§3.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a database systems venue and the graph-preserving approach is a clean idea. The main risk is that the routing oracle is not validated, and the evaluation lacks accuracy checks and error bars. All of these are fixable with additional experiments, so I recommend major revision rather than rejection. I would ask the authors to add the random-routing ablation and CHRmax measurements in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: SHINE is a graph-preserving HNSW index for disaggregated memory, and that design choice is the real contribution. It keeps all edges of a standard HNSW graph, so the same-accuracy claim is a definitional result rather than an empirical leap. The logical cache-combining via partition-aware routing is a genuine trick, and the throughput numbers look plausible. The paper is clearly written and ships an open-source implementation.\n\nThe soft spots are in the evaluation, not the core design. The routing oracle is never isolated. Every policy in Figure 7 uses the same k-means oracle, so there is no random-routing control to show whether the centroid ranking actually improves cache hit rate or whether the balanced load distribution alone explains the gains. The clustering sample is taken from the first upper level with at least 1000 nodes, which is a weak proxy for base-level access locality; the paper does not validate that assumption. That is the main load-bearing concern, and it is fixable with an ablation.\n\nSecond, the cache segmentation penalty is defined against CHRmax, the hit rate of a single shared cache of equal aggregate size, but the paper never explains how CHRmax is measured. Without that methodology, the CSP numbers in Table 2 and Figure 10 are not interpretable. Third, the experiments compare only against their own baselines. A comparison with d-HNSW or at least one prior disaggregated ANN system would make the results much stronger. Also, no recall values are reported. The same-accuracy claim follows by construction, but a quick recall sanity check would cost little and remove doubt. The scale is 100M vectors on 5 compute nodes, which is a reasonable prototype but not the billion-scale the abstract hints at.\n\nFor a reading group, this paper is worth discussing: the graph-preserving idea is clean, the cache-combining pattern is reusable, and the evaluation gaps are instructive. I would accept it for peer review and ask for a round of revision with the ablation and CSP methodology fixed.","headline":"Graph-preserving HNSW for disaggregated memory is a genuine contribution; the evaluation needs an oracle ablation and an operationalized CSP before the throughput claims are airtight.","tokens_in":28897,"tokens_out":2943,"would_cite":true,"duration_ms":30283,"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":"Shine proposes a distributed HNSW index that keeps every graph edge and therefore matches the recall of a single-machine HNSW.","keywords":["approximate nearest neighbor search","HNSW","disaggregated memory","RDMA","distributed index","caching","query routing","cache segmentation penalty"],"falsifier":"Run the full system on a workload whose query vectors are uniform in coordinate space but whose HNSW traversal repeatedly crosses cluster boundaries, for example a synthetic manifold where all queries arrive near the same few hub vectors; if the oracle routes to the closest centroid yet cache hit rate and throughput stay at the no-routing level, coordinate clustering is not predicting cache locality.","tokens_in":27896,"feed_emoji":"🔍","tokens_out":8050,"duration_ms":81430,"temperature":0.7,"pith_summary":"This paper argues that a Hierarchical Navigable Small World (HNSW) nearest-neighbor index can be spread across disaggregated memory without paying the usual accuracy cost of sharding. Existing distributed approaches partition the graph and lose important edges; Shine instead stores a global HNSW graph whose nodes are scattered over memory nodes with every edge intact, so recall equals a single-machine HNSW. The obstacle is network bandwidth, because one query can read thousands of high-dimensional vectors from remote memory. Shine attacks this with compute-side caching, then with a logical partitioning of the graph so each compute node's cache specializes in one region, and with adaptive routing that sends each query to the compute node whose partition best matches it. On five 100-million-vector benchmark datasets the combined design lifts throughput by up to 1.7x over the uncached baseline and roughly doubles cache hit rates.","feed_headline":"Shine distributes HNSW across memory nodes with zero accuracy loss","feed_subtitle":"Routing each query to the compute node with the best-matching cache lifts throughput up to 1.7x.","key_machinery":"The load-bearing mechanism is the pairing of logical index partitioning with adaptive query routing over a global HNSW graph that keeps all edges. The index is divided only logically: balanced k-means clusters a small representative sample of nodes into as many near-equal partitions as there are compute nodes, using vector coordinates, and an oracle ranks compute nodes by the distance between the query vector and each partition's centroid. A router forwards each query to the best-ranked compute node that still has capacity in the current batch, relaying messages through a random memory node with two-sided RDMA, and the per-node limits are adjusted by broadcasting working-queue lengths. The cache itself is a lock-free hash table with a cooling-table replacement policy that admits upper-level nodes always and base-level nodes with a small fixed probability.","core_discovery":"The central claim is that a distributed ANN index in disaggregated memory can have the exact graph structure, and therefore the exact accuracy, of a single-machine HNSW, and that the network bottleneck this creates can be addressed by treating the union of compute-node caches as one logical cache. Shine stores node records, each holding vector components and remote pointers to neighbor lists, on arbitrary memory nodes, and leaves the HNSW search algorithm unchanged except that neighbor lists and vectors are fetched by RDMA. Because a query touches thousands of nodes, Shine clusters the HNSW nodes into as many balanced partitions as there are compute nodes, ranks partitions by centroid distance to the query through an oracle, and adaptively routes each query to the best-ranked compute node with spare capacity. The cache segmentation penalty formalizes how much hit rate is lost because separate caches duplicate entries; in the evaluation, routing reduces this penalty from roughly 70 percent to between 12 and 55 percent and raises throughput by up to 1.7x.","pith_inferences":["If coordinate proximity tracks graph-walk co-access, the same partition-and-route pattern should transfer to other graph-based ANN indexes, and the centroid oracle could be replaced by a learned router on harder workloads.","The cache segmentation penalty is a reusable diagnostic for any distributed cache: measuring it before and after a routing change separates the contribution of cache specialization from the contribution of load balancing.","A stress test the paper does not run is a workload with uniform query vectors but hub-heavy graph traversal; such a workload would reveal whether the oracle depends on coordinate space matching traversal locality.","The two-sided routing path through a random memory node could become the bottleneck at very high query rates or with many compute nodes, so routing scalability under those conditions is a natural next experiment."],"forward_implications":["A deployment can scale to billions of vectors by adding memory nodes without rebuilding or re-sharding the index, since the HNSW graph is global and individual nodes live on arbitrary memory nodes.","Recall parity with single-machine HNSW means accuracy parameters can be tuned on a small machine and carried over unchanged to the distributed setting.","Uniform query workloads, the worst case for caching, still gain throughput because partitioned caches collectively hold more distinct graph nodes.","Skewed workloads gain the most, with measured throughput up to 27.8k queries per second and cache hit rates of 70 to 81 percent when routing and caching are combined."],"supporting_citations":[{"why":"Defines the HNSW graph structure that Shine preserves without removing edges.","marker":"[48]"},{"why":"Supplies the balanced k-means approximation used to divide the index into near-equal partitions.","marker":"[11]"},{"why":"Provides the cache replacement and probabilistic admission design adopted for compute-side caching.","marker":"[42]"},{"why":"Introduces the cooling-table idea that underlies the low-overhead cache replacement strategy.","marker":"[37]"},{"why":"Presents a distributed HNSW approach that shards the graph and loses accuracy, the contrast that motivates graph preservation.","marker":"[12]"},{"why":"Extends the sharded approach to disaggregated memory and serves as the closest alternative that sacrifices accuracy.","marker":"[40]"},{"why":"Supplies the five 100-million-vector benchmark datasets used in the evaluation.","marker":"[61]"}],"fun_headline_variants":["SHINE builds exact-accuracy HNSW in disaggregated memory","Distributed HNSW without accuracy loss via logical cache union","SHINE coordinates caches to scale HNSW in disaggregated memory","Query routing lifts distributed HNSW throughput by 1.7x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that vector-space proximity, as captured by balanced k-means centroids, predicts which compute node will serve a query with the best cache hit rate; if graph-walk popularity does not align with coordinate clusters, best-fit routing will not raise hit rates and the throughput gains disappear.","fun_headline_variants_meta":{"raw":{"variants":["SHINE builds exact-accuracy HNSW in disaggregated memory","Distributed HNSW without accuracy loss via logical cache union","SHINE coordinates caches to scale HNSW in disaggregated memory","Query routing lifts distributed HNSW throughput by 1.7x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000322,"raw_usage":{"total_tokens":1825,"prompt_tokens":976,"completion_tokens":849,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":771}},"tokens_in":592,"tokens_out":849,"duration_ms":9207,"temperature":1.0,"reasoning_tokens":771,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T14:44:24.850989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the full system on a workload whose query vectors are uniform in coordinate space but whose HNSW traversal repeatedly crosses cluster boundaries, for example a synthetic manifold where all queries arrive near the same few hub vectors; if the oracle routes to the closest centroid yet cache hit rate and throughput stay at the no-routing level, coordinate clustering is not predicting cache locality.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the balanced k-means approximation used to divide the index into near-equal partitions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends the sharded approach to disaggregated memory and serves as the closest alternative that sacrifices accuracy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the five 100-million-vector benchmark datasets used in the evaluation."}],"review_version":1}