{"id":"f0bded92-815e-4d01-9831-8a3e53904d67","arxiv_id":"2501.10479","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Lossless compression of vector IDs in IVF and graph indexes, using random-order and random-edge coding plus wavelet trees, reduces ID storage by up to 7x and total index size by 30% at billion scale.","lead":"This paper compresses the numeric IDs and graph links used in approximate nearest neighbor search without losing information, cutting ID storage by up to 7x in some settings and total index size by about 30% on a billion-scale benchmark. It applies random-order entropy coding and wavelet trees to exploit the fact that the order of IDs inside clusters or neighbor lists is irrelevant to the search.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Graph-index 'lossless' claim leans on an untested order-invariance of friend lists; without a permutation ablation the graph compression results are not validated.","rationale":"The reader's weakest assumption is indeed the graph order-invariance, and that is the most load-bearing concern because it underpins all graph-index claims. The IVF results are independent and likely sound. I considered the abstract's 'no impact on search runtime' claim, which is contradicted by Table 4 (ROC 14.9ms vs 11.8ms uncompressed) and Table 2 (up to 19% slowdown); that is a corrigible factual overstatement rather than a threat to the compression construction and should be fixed in revision. The code-compression 'random access' claim is also loosely worded because adaptive column-wise entropy coding is not truly random-access per element. The graph permutation test is the one experiment that would settle the central correctness question.","tokens_in":16338,"tokens_out":4216,"duration_ms":46210,"concrete_test":"Use the same Faiss NSG256 index and query set as Table 1, with fixed nprobe/efSearch=16. Randomly permute the friend list of every node (e.g., 5 seeds), then measure recall@10 and the multiset of visited nodes per query against the unpermuted baseline. If recall or visited-node sets change beyond floating-point tie noise, the graph-order invariance fails and the graph index claims need qualification. If they are identical, the assumption is validated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's graph-index contribution depends on Section 4's assertion that 'for graph based indices the invariance is with respect to the order of elements in the friend list.' ROC and REC encode each friend list as a set, so decompressed lists have a canonical order rather than the original order. If greedy NSG routing is order-sensitive, the compressed graph can follow different search paths and yield different recall. NSG search is a best-first expansion over a priority queue; with floating-point distances ties are unlikely, but order can still matter when a bounded candidate set is maintained (e.g., efSearch=16 here) or when an implementation prunes candidates. The paper reports no experiment that permutes friend lists and compares search results, and it deliberately omits recall measurements because the compression is asserted to be lossless. Thus for Tables 1-3 and the offline REC results, the 'same search behavior' premise is unsupported. This is not a claim that the premise is false; it is a load-bearing assumption that should be verified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes and evaluates lossless compression methods for auxiliary data in approximate nearest neighbor (ANN) indexes: vector identifiers in IVF inverted lists and edges in graph-based indexes. It applies entropy coders based on asymmetric numeral systems (ANS), notably ROC for sets/multisets and REC for graphs, as well as wavelet-tree and Elias-Fano baselines, under three access regimes: full random access, partial random access, and offline whole-index compression. On 1M-vector benchmarks, it reports reducing IVF ID storage from 64 bits per ID to roughly 9-12 bits per ID (a factor of about 7 for IVF256), and reducing graph ID storage from 32 bits to about 14-20 bits per ID depending on graph degree. On a billion-scale QINCo+IVF index, it reports an overall index-size reduction of about 30%. The paper also reports lossless compression of PQ codes conditioned on cluster ID for some datasets. Because the transformations are lossless by construction, the paper does not measure search recall, and it claims no impact on accuracy or search runtime.","tokens_in":16491,"tokens_out":7171,"duration_ms":81096,"significance":"If the claims hold, this is a useful systems contribution: it shows that a large fraction of ANN index memory can be saved by exploiting the order-invariance of ID sets, with measured rates close to information-theoretic bounds. The IVF results are internally consistent and reproducible in spirit: the authors implement the codecs in Faiss, report bit rates on standard datasets, and the Elias-Fano/ROC gap is consistent with the known 0.56-bit redundancy. The main novelty is empirical rather than methodological, since ROC/REC are prior work by the same group; nevertheless, an independent evaluation of speed versus compression for ANN indexes is valuable. The central caveat is that the graph-index 'lossless with same search behavior' claim relies on an unvalidated assumption about friend-list order invariance, and the runtime claims are stronger than some of the paper's own tables support.","major_comments":[{"comment":"The claim that graph-based search is invariant to the order of elements in friend lists is load-bearing for the graph compression results in Tables 1-3, but it is not empirically validated. ROC and REC encode each friend list as a set, so after decompression the adjacency lists are stored in a canonical order that may differ from the original. Best-first graph search with a bounded candidate set (the paper uses efSearch=16 for NSG) and with possible tie-breaking can plausibly be sensitive to the order in which neighbors are inserted into the priority queue. The paper explicitly does not measure recall (Section 5.1: 'we do not evaluate the vector search recall'), so this premise is asserted rather than tested. Please add an ablation that randomly permutes each friend list (and, separately, applies the actual compress-decompress pipeline) and compares recall@k and, if feasible, the set of visited nodes against the original graph. Without such evidence, the 'lossless, same behavior' claim for graph indexes is unsupported.","section":"Section 4, \"Exploiting invariances for compression\"; Section 5.1, Metrics"},{"comment":"The abstract states that the methods compress IDs 'with no impact on accuracy or search runtime,' but the paper's own timing results show substantial slowdowns in several settings. In Table 2, NSG16 with ROC is 0.29s versus 0.12s for the uncompressed index (about 2.4x slower), and NSG64 with ROC is 0.51s versus 0.29s (about 1.8x slower). In the billion-scale experiment of Table 4, ROC raises search time from 11.8s to 14.9s (about 26% slower), while the text emphasizes only the 30% index-size reduction. If the 'no impact on search runtime' claim is meant to apply only to the IVF settings where vector compression dominates, it should be qualified explicitly; as written, it is contradicted by the reported data.","section":"Abstract; Tables 2 and 4"}],"minor_comments":[{"comment":"Typo: 'natural numberss' should be 'natural numbers'.","section":"Section 3.1"},{"comment":"Typo: 'if the distance if better than the worst' should be 'if the distance is better than the worst'; similarly, 'or or they are evicted' should be 'or they are evicted'.","section":"Section 4.1"},{"comment":"Typo: 'the baseline WT uses a flat binary binary string' should read 'a flat binary string'; also, 'Succint library' should be 'Succinct library'.","section":"Section 5.2"},{"comment":"The displayed formula for the sequential predictive distribution is hard to parse because of the line break; please use a proper fraction, e.g., Pr(...) = (1 + count) / (256 + i), and clarify the role of the Laplace smoothing term.","section":"Equation (7)"},{"comment":"Minor wording: 'The source code for our approach available' should be 'The source code for our approach is available'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The methodological novelty is limited because ROC and REC are prior work by the first author, and the present contribution is an empirical evaluation plus engineering integration into Faiss. That is a legitimate contribution if the journal accepts systems papers, but the graph-order-invariance assumption must be tested before publication; otherwise the graph section should be reframed as compression under an explicit semantic-equivalence assumption. I would also ask the authors to reconcile the abstract's runtime claim with Tables 2 and 4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a useful systems paper and the core IVF results hold up. The idea is simple and correct: in inverted-file indexes you can losslessly compress the vector ID lists with orderless codecs (ROC, Elias-Fano) and get roughly 7x ID compression on the tested datasets with negligible search slowdown. The numbers in Table 1 are internally consistent and match information-theoretic bounds: ROC sits near the Shannon limit and Elias-Fano is about 0.56 bits above it, just as expected. The billion-scale result (30% index reduction with ROC) is a practical win and the paper's main selling point. That part deserves a serious referee. Where the paper gets soft is the graph-index claim. Section 4 assumes that permuting the friend list of each node does not change search results or speed, and the paper then skips recall measurements because the compression is asserted to be lossless. That is circular. NSG and HNSW search uses a priority queue and a bounded candidate set; order can matter for tie-breaking or pruning even if distances are floating-point. The paper reports no ablation that permutes friend lists and compares recall, so the claim that compressed graphs have the same search behavior is unsupported. This is not a fatal flaw: it may well be true, but it is a load-bearing assumption and easy to test. Two smaller issues. First, the abstract says \"no impact on search runtime,\" but Table 2 shows up to a 19% slowdown for PQ4 on Deep1M. That is an overclaim and should be corrected to something like \"negligible in most settings.\" Second, the quantized-code compression section says the codes are compressed \"while still providing random access,\" but the model is a sequential predictive coder: to decode element i you must process the prefix. That is not random access to individual codes, only to a whole cluster's code stream. The wording is misleading and should be fixed. The authors lean heavily on their own previous work (ROC, REC), but that is appropriate here: they are applying those codecs to a new problem and evaluating them on public datasets with independent measurements. The self-citation is not a red flag. Who gets value from this paper: anyone working on memory-bound ANNS serving, especially billion-scale IVF or graph indexes. It deserves peer review: conditional acceptance with a required permutation ablation for graph indexes and a revision of the runtime and random-access claims.","headline":"Solid IVF compression results with a practical payoff, but the graph-index claim needs an order-invariance ablation and the abstract overstates the runtime story.","tokens_in":650,"tokens_out":896,"would_cite":true,"duration_ms":33065,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P30","94A29"],"pacs":[],"model":"deepseek-v4-flash","headline":"Vector-search indexes can shed order information and shrink 30% with no recall loss.","keywords":["approximate nearest neighbor search","lossless compression","vector id compression","asymmetric numeral systems","random order coding","wavelet trees","inverted file index","graph-based index"],"falsifier":"Run a query batch on an NSG or HNSW index, then on the same index with every node's friend list randomly permuted, and compare the fraction of true nearest neighbors returned and the sequence of visited nodes; any systematic difference would show that order is not irrelevant for graph search. Separately, compress and decompress an index and verify that every id comes back bit-identical, distinguishing lossless storage from lossless search behavior.","tokens_in":16132,"feed_emoji":"🗜️","tokens_out":9532,"duration_ms":96667,"temperature":0.7,"pith_summary":"The paper's claim is that a large fraction of a vector-search index is order information that the search never uses, and that this can be removed losslessly. In inverted-file indexes each cluster is a set of vector ids, and in graph indexes each node's neighbor list is a set, so coding these lists as ordered sequences wastes about $\\log n!$ bits per list. The authors build entropy coders, random-order coding on asymmetric numeral systems for online access, wavelet trees for full random access, and random-edge coding for offline graph compression, that realize these savings. On million-scale benchmarks the id storage falls from 32 or 64 bits to about 8–12 bits per id, a sevenfold reduction in IVF settings, and on a billion-scale index the overall size drops about 30% at unchanged recall. For some datasets the same conditional entropy argument also compresses the quantized vector codes by up to 19%.","feed_headline":"Treating vector ids as sets shrinks indexes 30 percent","feed_subtitle":"Lossless coding of unordered id lists cuts billion-scale index size from 17.8 GB to 12.5 GB at same accuracy.","key_machinery":"The load-bearing object is the order-invariance itself: a list of ids stores membership and nothing else, so the compressor can discard the ordering. The codec that carries the argument is Random Order Coding (ROC), a bits-back scheme built on asymmetric numeral systems (ANS), an entropy coder, that models an observed sequence as a set plus a hidden permutation, samples the permutation back from the ANS state during decoding, and thereby pays about $\\log n!$ fewer bits. For full random access to individual ids, the paper uses a wavelet tree over the cluster-id sequence, where the select operation finds the database id at a given offset inside a cluster; the compressed-bitvector variant trades speed for more compression. For offline graph compression, Random Edge Coding (REC) flattens all edges of the graph into one ANS-coded node sequence and exploits the edge-order freedom globally. The same ANS machinery, with an adaptive per-cluster byte model, is what extracts the redundancy from quantized product-quantization codes.","core_discovery":"The central discovery is that auxiliary identifiers in approximate nearest neighbor indexes are sets, not sequences, and therefore carry $\\log n!$ redundant bits that a lossless codec can recover. The paper demonstrates this with Random Order Coding (ROC), which uses bits-back coding with a latent permutation to encode each inverted list or friend list at close to the set-entropy rate, and with Random Edge Coding (REC) for whole-graph offline compression. The measured consequences are concrete: IVF ids compress from 64 bits to about 9 bits per id, graph friend lists compress to roughly 16–20 bits per id, with short lists failing to beat the $\\lceil \\log N\\rceil$ baseline, and the total size of a billion-scale IVF+QINCo index falls from 17.8 GB to 12.5 GB with recall unchanged. The paper also shows that product-quantization codes, usually assumed to be incompressible, are not uniformly distributed within clusters: conditioning the entropy model on cluster membership compresses SIFT1M codes by up to 19%.","pith_inferences":["Beyond the paper, the order-invariance argument is structural, so the same lossless id-compression recipe should transfer to other graph and partitioned index families, with similar bit savings wherever membership lists appear.","Beyond the paper, the uniform probability model used in ROC ignores correlations among ids; a data-dependent neighbor model could shave more bits from graph friend lists, at the price of slower decoding.","Beyond the paper, the graph-index claim of unchanged search behavior implicitly assumes friend-list order does not affect greedy routing; rerunning queries after randomly permuting each friend list would test that directly, and the paper reports no such ablation.","Beyond the paper, the cluster-conditional code compression implies quantizers leave cluster-local structure on the table, so jointly training quantizers with an entropy model could make the lossless code gains larger than the reported 19%."],"forward_implications":["IVF indexes can store ids at about 14.7% of their uncompressed size, roughly 9 bits per id instead of 64, with search accuracy identical because the representation is lossless and with negligible slowdown for typical product-quantization settings.","On billion-scale IVF+QINCo indexes the total RAM footprint falls from 17.8 GB to 12.5 GB at the same recall@10, so the same machine can serve a larger database.","Compressed indexes trade access granularity against rate: wavelet trees provide random access to any id at a 2–3x select cost, per-cluster streams give partial random access at near-optimal rates, and single-stream offline compression gives the best rates but requires full decompression before search.","For graph indexes, offline REC compression reaches up to 2.31x reduction on HNSW/NSG graphs, but online per-node friend-list coding is only competitive when lists are long; for NSG16 the baseline $\\lceil\\log N\\rceil$ bits per id wins.","Quantized vector codes are not always max-entropy; conditional entropy coding within clusters extracts up to 19% for SIFT1M and about 5% for Deep1M, with negligible benefit for FB-ssnpp."],"supporting_citations":[{"why":"Supplies Random Order Coding, the bits-back set-compression codec used for every online IVF and graph id-list experiment.","marker":"[52]"},{"why":"Supplies Random Edge Coding, the bits-back graph codec used for the offline whole-graph compression results.","marker":"[51]"},{"why":"Introduces asymmetric numeral systems, the near-optimal entropy coder underlying ROC and the conditional code compression.","marker":"[16]"},{"why":"Defines the monotone-sequence baseline codec used for comparison against the set codecs.","marker":"[17]"},{"why":"Provides the wavelet-trie structure on which the select-based random-access id lookup is built.","marker":"[24]"},{"why":"Introduces the compressed bitvector dictionary used by the higher-compression wavelet-tree variant.","marker":"[46]"},{"why":"Defines product quantization, the index code regime whose ids and cluster-conditional codes are compressed.","marker":"[30]"},{"why":"Supplies the QINCo quantizer used in the billion-scale experiment that shows total index size falling 30%.","marker":"[28]"},{"why":"Serves as the offline graph-compression baseline that REC is measured against.","marker":"[62]"},{"why":"Provides the search library in which the codecs are implemented, supplying the uncompressed 32/64-bit id baseline.","marker":"[13]"}],"fun_headline_variants":["ID compression cuts ANN index size 30% with no accuracy loss","Set-based coding squeezes 7x from ANN vector IDs","Lossless trick shrinks billion-scale ANN indexes by 30%","Vector IDs as sets unlock 7x compression for ANN"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the claim that the ordering of ids inside a cluster list or a graph node's neighbor list is irrelevant to search results and speed; if reordering a neighbor list changes which approximate neighbors a greedy search finds, the graph-index savings are not behaviorally lossless.","fun_headline_variants_meta":{"raw":{"variants":["ID compression cuts ANN index size 30% with no accuracy loss","Set-based coding squeezes 7x from ANN vector IDs","Lossless trick shrinks billion-scale ANN indexes by 30%","Vector IDs as sets unlock 7x compression for ANN"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000394,"raw_usage":{"total_tokens":2078,"prompt_tokens":967,"completion_tokens":1111,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":1039}},"tokens_in":583,"tokens_out":1111,"duration_ms":9616,"temperature":1.0,"reasoning_tokens":1039,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:38:46.259069+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a query batch on an NSG or HNSW index, then on the same index with every node's friend list randomly permuted, and compare the fraction of true nearest neighbors returned and the sequence of visited nodes; any systematic difference would show that order is not irrelevant for graph search. Separately, compress and decompress an index and verify that every id comes back bit-identical, distinguishing lossless storage from lossless search behavior.","supporting_citations":[{"cited_title":"Compressing multisets with large alphabets","cited_arxiv_id":null,"evidence_quote":"Supplies Random Order Coding, the bits-back set-compression codec used for every online IVF and graph id-list experiment."},{"cited_title":"Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs","cited_arxiv_id":"2305.09705","evidence_quote":"Supplies Random Edge Coding, the bits-back graph codec used for the offline whole-graph compression results."},{"cited_title":"Efficient storage and retrieval by content and address of static files","cited_arxiv_id":null,"evidence_quote":"Defines the monotone-sequence baseline codec used for comparison against the set codecs."},{"cited_title":"The wavelet trie: maintaining an indexed sequence of strings in compressed space","cited_arxiv_id":null,"evidence_quote":"Provides the wavelet-trie structure on which the select-based random-access id lookup is built."},{"cited_title":"Succinct indexable dictionaries with applica- tions to encoding k-ary trees, prefix sums and multi- sets","cited_arxiv_id":null,"evidence_quote":"Introduces the compressed bitvector dictionary used by the higher-compression wavelet-tree variant."},{"cited_title":"Product quantization for nearest neighbor search","cited_arxiv_id":null,"evidence_quote":"Defines product quantization, the index code regime whose ids and cluster-conditional codes are compressed."},{"cited_title":"Huijben, Matthijs Douze, Matthew J","cited_arxiv_id":null,"evidence_quote":"Supplies the QINCo quantizer used in the billion-scale experiment that shows total index size falling 30%."},{"cited_title":"Zuckerli: A new compressed represen- tation for graphs","cited_arxiv_id":null,"evidence_quote":"Serves as the offline graph-compression baseline that REC is measured against."}],"review_version":1}