{"id":"74d975c5-693c-4fd5-a37d-66042e506da0","arxiv_id":"2501.14741","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Design choices in FlyHash embeddings, especially preprocessing and block sparse sparsification, can drastically change similarity search performance per stored bit.","lead":"The paper compares preprocessing, random projection sampling, and sparsification choices in FlyHash similarity embeddings on three benchmarks. It finds that mean-centered normalized inputs combined with angle-based ranking, hypergeometric projection sampling for dense data, and block sparse activations matched to storage bits can substantially improve search accuracy.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (13): no feasible k' exists at D=20k for k≳78, so the key 'matching bits' block-sparse comparison in Figs. 3 is not well-defined.","rationale":"The reader's weakest assumption was that D=20k is fixed without sensitivity analysis. My check exposes a stronger, internal problem: at D=20k the proposed bit-matching equation has no solution for the larger k values that the paper actually uses. The paper gives a derivation (Eqs. 11-13) but no k' table, no code, and no feasibility check. The 'matching bits' experiments are therefore not reproducible as described. I do not call the entire paper fraudulent; the preprocessing and projection-matrix experiments may stand. But the specific sub-claim singled out by the reader—that block-sparse matching-bits codes outperform binary kWTA at equal storage—is undefined under the stated formulas. The manuscript should be revised to specify the actual bit budget (≤ vs =) and recompute Figs. 3-4. This keeps the verdict CONDITIONAL rather than REJECT, because the claim is testable and the rest of the empirical study appears coherent.","tokens_in":11349,"tokens_out":11583,"duration_ms":110510,"concrete_test":"Independently re-derive k' from Eq. (13) for every k and D=20k used in Figs. 3, and require D/k' to be an integer. For values of k with no feasible k', rerun the comparison using the largest k' satisfying k' log2(D/k') ≤ k log2(D), and report the actual bit counts of both embeddings. If the 'matching bits' line no longer lies above binary kWTA across the whole range, the central storage-efficiency claim is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section III-C1's central comparison is undefined under the paper's own parameter setting. Eq. (13) fixes D=20k and asks for k' satisfying k' log2(D/k') = k log2(D). The LHS is maximized at k'=D/e=20k/e, where it equals (20k/e) log2 e ≈ 10.61k bits. The RHS is k log2(20k), which exceeds 10.61k whenever log2(20k)>10.61, i.e., k≳78. For example, at k=128, D=2560, the RHS is about 1449 bits but the maximum LHS is about 1358 bits; at k=256, D=5120, RHS≈3154 bits vs max LHS≈2717 bits. So for most k used in the paper (including the k=256, block size 20 setup in Fig. 4), no k' solves Eq. (13). The blue 'matching bits' curves therefore cannot be exactly at the same storage cost as binary kWTA; either they use fewer bits, making the 'equal storage' statement false, or they were computed from an undocumented different formula. This is the sub-claim that the strongest conclusion relies on, so the paper needs a corrected or explicitly budgeted comparison.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an empirical study of design choices in FlyHash-style expand-and-sparsify embeddings: preprocessing of input vectors (original FlyHash preprocessing, mean centering, normalization, and combinations), the distribution and density of the random projection matrix (binomial vs. hypergeometric, three density levels), and the sparsifying nonlinearity (nonbinary kWTA, binary kWTA, and two forms of k-block sparse codes). The evaluation uses MAP at K=200 on 10^4 vectors from SIFT, GLOVE, and MNIST, with 10 random initializations and 10^3 queries per matrix. The main findings are that preprocessing and the choice of ranking measure interact strongly with the embedding type, that the hypergeometric projection distribution helps substantially for the dense GLOVE vectors, and that block sparse codes with a number of blocks matched to the bit budget of binary kWTA outperform binary kWTA at supposedly equal storage cost. The paper also reports a null result for optimizing column densities with a genetic algorithm.","tokens_in":11622,"tokens_out":7518,"duration_ms":76699,"significance":"If the results hold, the paper provides useful practical guidance for designing FlyHash embeddings in hyperdimensional computing and similarity search, and the idea of comparing embeddings on a per-bit storage budget is a valuable addition to the literature. The experimental protocol is described carefully, with fixed dataset sizes, query counts, and numbers of random initializations, and the findings are broadly consistent across three datasets. The manuscript is, however, primarily an empirical design study rather than a theoretical contribution, and its central novelty—the 'matching bits' block-sparse comparison—is undermined by a technical flaw in Eq. (13) that makes the comparison undefined for most of the parameter values used in the experiments.","major_comments":[{"comment":"The 'matching bits' comparison is not well-defined for the parameter settings used in the paper. With D=20k, the function k' log2(D/k') on the left-hand side of Eq. (13) is maximized at k' = D/e ≈ 7.36k, where its value is (20k/e) log2 e ≈ 10.61k bits. The right-hand side is k log2(20k), which exceeds this maximum whenever log2(20k) > 10.61, i.e., for k ≳ 78. Concretely, for k=128 (D=2560) the right-hand side is about 1449 bits while the maximum left-hand side is about 1358 bits; for k=256 (D=5120, the setup used in Fig. 4) the right-hand side is about 3154 bits versus a maximum of about 2717 bits. Thus no k' solves Eq. (13) for these values. The 'block sparse; matching bits' curves in Fig. 3 therefore cannot represent embeddings at exactly the same storage cost as binary kWTA; either they use fewer bits, contradicting the 'equal storage cost' claim, or they were computed with a different, undocumented budget. This is load-bearing because the paper's strongest sub-claim is that block sparse codes with matched bit budgets outperform binary kWTA per stored bit. Please correct the comparison, for example by restricting to k where a solution exists, or by reporting actual bit counts and using a rounded or explicitly budgeted k' with the exact storage costs for both curves.","section":"Section III-C1, Eq. (13)"},{"comment":"All main experiments fix the expansion ratio to D = 20k, i.e., embedding density k/D = 0.05, and no sensitivity analysis over the expansion ratio is provided. The conclusions about which preprocessing, projection distribution, and sparsifier perform best are therefore demonstrated at a single operating point. If the ranking of these design choices depends on D/k—which is plausible given that the behavior of kWTA and of block sparsification changes with relative expansion—the paper's central claim that 'the right combination of design choices can lead to drastic difference' may not transfer to other expansion settings. Please add experiments at at least a few additional expansion ratios (e.g., D = 5k, 10k, 50k), or explicitly restrict the conclusions to the tested density and discuss the likely dependence on D/k.","section":"Section III (Figs. 1-3)"}],"minor_comments":[{"comment":"The genetic algorithm used to optimize column densities is described only as 'set to optimize the density of individual columns of M'; no population size, number of generations, mutation/crossover operators, fitness function, or number of independent runs is given. This makes the reported null result irreproducible. Please provide these details or rephrase the claim as preliminary.","section":"Section III-B2"},{"comment":"Results are reported as averages over 10 random initializations without error bars, standard deviations, or significance tests. This makes it difficult to assess whether differences such as those in Fig. 3 are reliable, especially for the claim that the 'matching bits' variant 'consistently outperformed' the alternatives. Please add variability information or state explicitly that the differences exceed the observed variation across initializations.","section":"Figures 1-3"},{"comment":"The term 'iWTA embedding' appears to be a typographical or notational error for the kWTA embedding formed by processing i blocks; please clarify the notation so that it is distinct from the kWTA parameter k used elsewhere.","section":"Fig. 4 and surrounding text"},{"comment":"The statement that block sparse codes reduce the information entropy from log2(D choose k) to k log2(D/k) uses an approximation for the binomial coefficient; please clarify that this is an asymptotic or approximate comparison rather than an exact equality, and likewise note that Eqs. (11)-(12) are fixed-length encoding costs rather than exact entropies.","section":"Section II-A"}],"recommendation":"major_revision","confidential_remarks":"The Eq. (13) infeasibility issue is the main blocker: the paper's most novel quantitative claim rests on a comparison that is undefined for the reported parameter range. If the authors cannot provide a well-defined equal-bit comparison (e.g., by reporting actual storage costs and using a feasible k'), then the 'matching bits' contribution should be substantially revised or removed from the central claims. The rest of the paper, including the preprocessing and projection-distribution results, is largely sound and within the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe empirical sweep in this paper is genuinely useful. It isolates preprocessing, projection-matrix sampling, and sparsifier as separate axes, and the finding that mean-centered normalized inputs with binary kWTA and angle ranking is a strong combination is concrete and actionable. The hypergeometric versus binomial sampling comparison on dense versus sparse inputs is also a good idea, and the sequential-processing experiment in Fig. 4 is a nice practical addition.\n\nBut the central new claim – that “matching bits” block-sparse codes outperform binary kWTA at equal storage cost – is not well-defined. Eq. (13) asks for k' satisfying k' log2(D/k') = k log2(D). With D = 20k, the LHS has a maximum of about 10.61k bits at k' = D/e, while the RHS is k log2(20k). For k ≳ 78, the RHS exceeds the maximum LHS, so no k' exists. The paper uses k = 128 and k = 256 in Fig. 4, and likely larger values in Figs. 1–3. This means the blue “matching bits” curves cannot be computed as stated. Either they used a different formula, or they are not actually at equal storage; either way, the headline comparison is unverifiable as written.\n\nThis is fixable. The authors could compare at equal true entropy (using log2(C(D,k))), or restrict the comparison to the range where Eq. (13) has a solution, or explicitly reframe the “matching bits” construction as an approximation. But as it stands, the strongest sub-claim rests on an undefined equality.\n\nOther soft spots are minor: no error bars or significance tests (MAP averages over 10 initializations only), all main figures fix D = 20k, and the genetic algorithm details are thin. These would matter less if the main comparison were sound.\n\nWho is this for? Practical users of FlyHash-style embeddings who want guidance on preprocessing and sparsifier choice. The preprocessing and sampling results are worth having even with the matching-bits problem. I would send this to serious peer review, but request a corrected or properly budgeted comparison of the block-sparse variant before publication. I wouldn't cite the matching-bits claim until that is fixed.","headline":"Useful empirical map of FlyHash design choices, but the headline 'matching bits' comparison is undefined for most of the tested range.","tokens_in":12154,"tokens_out":3163,"would_cite":false,"duration_ms":29040,"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":"FlyHash similarity-search quality depends heavily on three design choices, and block sparse codes matched for bits outperform binary kWTA at equal storage cost.","keywords":["FlyHash","sparse embeddings","kWTA","block sparse codes","random projection","similarity search","hyperdimensional computing","expand and sparsify"],"falsifier":"Re-run the same MAP comparisons at expansion ratios such as D = 5k and D = 100k, holding bit budgets matched; if binary kWTA outperforms matched-bit block sparse codes at any of these ratios, the claimed uniform advantage fails. A simpler check: on the same datasets, vary D continuously and plot where the MAP curves cross.","tokens_in":11132,"feed_emoji":"🧠","tokens_out":4239,"duration_ms":37996,"temperature":0.7,"pith_summary":"This paper asks how three practical design choices in the FlyHash algorithm—how input vectors are preprocessed, how the random projection matrix is sampled, and which sparsifying nonlinearity is applied—affect the quality of similarity search. Using SIFT, GloVe, and MNIST, it shows that these choices can produce drastic differences in mean average precision. The most concrete finding is that block sparse codes, when given the same storage budget as binary kWTA embeddings, consistently outperform binary kWTA across datasets and preprocessings.","feed_headline":"Block-sparse codes beat binary kWTA at equal bit cost","feed_subtitle":"Matched-bit block sparse embeddings give higher similarity-search accuracy on SIFT, GloVe, and MNIST.","key_machinery":"The central object is the FlyHash embedding pipeline y = Mx followed by sparsification. The load-bearing identity is Eq. (13), k′ log2(D/k′) = k log2(D), which equates the storage cost in bits of binary kWTA, k log2(D), with that of block sparse codes, where each of k′ blocks contributes log2(D/k′) bits. This identity lets the authors compare kWTA and block sparse codes at equal memory cost rather than equal k.","core_discovery":"On the paper's own terms, the central discovery is that the design choices surrounding FlyHash are not interchangeable: matching the right preprocessing (mean centering and normalization with binary kWTA) and the right projection distribution (hypergeometric for dense inputs) substantially changes search quality. The key quantitative claim is that replacing unconstrained kWTA with k-block sparse codes, and increasing the number of blocks k′ so that k′ log2(D/k′) = k log2(D), yields embeddings that use the same number of bits to store as binary kWTA yet achieve higher MAP on all three datasets.","pith_inferences":["If the D = 20k expansion ratio is not special, the matched-bit block sparse advantage should persist at other expansion ratios; a sweep over D would tell.","The bit-matching identity suggests a general recipe for comparing sparse codes of different structures: equalize information content, then measure accuracy.","The sequential-processing result hints that block sparse codes could be used in progressive retrieval, returning approximate answers before all blocks are processed."],"forward_implications":["Practitioners building similarity-search systems with FlyHash should treat preprocessing and projection sampling as performance-critical, not cosmetic.","Block sparse codes with matched bit budgets offer a strict memory-accuracy improvement over binary kWTA on the tested datasets.","For dense inputs such as GloVe, the hypergeometric projection distribution gives a substantial gain over the binomial distribution.","Sequential processing of block sparse codes reaches the same accuracy as processing the full code after fewer blocks, which can speed up early-exit search."],"supporting_citations":[{"why":"Defines the original FlyHash algorithm and provides the baseline performance that this paper improves upon.","marker":"[22]"},{"why":"Supplies the SIFT dataset used for evaluating the embeddings.","marker":"[28]"},{"why":"Supplies the GloVe dataset, which has dense input vectors that behave differently under the design choices.","marker":"[29]"},{"why":"Supplies the MNIST dataset, a third evaluation benchmark with sparse inputs.","marker":"[30]"},{"why":"Provides the theoretical basis for very sparse random projections, motivating the projection density levels tested.","marker":"[12]"},{"why":"Introduces the hypergeometric sampling scheme used as an alternative to binomial sampling for the projection matrix.","marker":"[13]"},{"why":"Establishes methods for constructing binary sparse vector representations via random projections and thresholding, which the binarization step relies on.","marker":"[20]"}],"fun_headline_variants":["Block-sparse codes outperform binary kWTA at equal bit cost","Sparse embeddings: matched block codes beat binary kWTA","FlyHash design matters: block-sparse codes improve search accuracy","Equal bit cost, higher accuracy: block-sparse beats binary kWTA","Block-sparse FlyHash boosts search on SIFT, GloVe, MNIST"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main experiments fix the expansion ratio at D = 20k; if the advantage of one design choice over another depends on this ratio, the paper's conclusions about which choices are best may not hold at other expansion levels.","fun_headline_variants_meta":{"raw":{"variants":["Block-sparse codes outperform binary kWTA at equal bit cost","Sparse embeddings: matched block codes beat binary kWTA","FlyHash design matters: block-sparse codes improve search accuracy","Equal bit cost, higher accuracy: block-sparse beats binary kWTA","Block-sparse FlyHash boosts search on SIFT, GloVe, MNIST"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000286,"raw_usage":{"total_tokens":1616,"prompt_tokens":814,"completion_tokens":802,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":710}},"tokens_in":430,"tokens_out":802,"duration_ms":8862,"temperature":1.0,"reasoning_tokens":710,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:11:18.883235+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the same MAP comparisons at expansion ratios such as D = 5k and D = 100k, holding bit budgets matched; if binary kWTA outperforms matched-bit block sparse codes at any of these ratios, the claimed uniform advantage fails. A simpler check: on the same datasets, vary D continuously and plot where the MAP curves cross.","supporting_citations":[{"cited_title":"A neural algorithm for a fundamental computing problem,","cited_arxiv_id":null,"evidence_quote":"Defines the original FlyHash algorithm and provides the baseline performance that this paper improves upon."},{"cited_title":"Product quantization for nearest neighbor search,","cited_arxiv_id":null,"evidence_quote":"Supplies the SIFT dataset used for evaluating the embeddings."},{"cited_title":"GloVe: Global vectors for word representation,","cited_arxiv_id":null,"evidence_quote":"Supplies the GloVe dataset, which has dense input vectors that behave differently under the design choices."},{"cited_title":"Gradient-based learning applied to document recogni- tion,","cited_arxiv_id":null,"evidence_quote":"Supplies the MNIST dataset, a third evaluation benchmark with sparse inputs."},{"cited_title":"Very sparse random projections,","cited_arxiv_id":null,"evidence_quote":"Provides the theoretical basis for very sparse random projections, motivating the projection density levels tested."},{"cited_title":"Sparser Johnson-Lindenstrauss transforms,","cited_arxiv_id":null,"evidence_quote":"Introduces the hypergeometric sampling scheme used as an alternative to binomial sampling for the projection matrix."},{"cited_title":"Randomized projective methods for the construction of binary sparse vector representations,","cited_arxiv_id":null,"evidence_quote":"Establishes methods for constructing binary sparse vector representations via random projections and thresholding, which the binarization step relies on."}],"review_version":1}