- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The method decouples candidate retrieval from ranking. A frozen 32-bit base code stays in the search index, and residual hash bits are generated on demand, from retained frozen CLIP features, for the query and a shortlist of roughly 1% of the gallery. Residual heads are trained with a candidate-boundary margin objective (the k-th nearest relevant candidate versus the (K-k+1)-th nearest irrelevant candidate under complete Hamming distance), with the feature extractor, base hasher, and all earlier residual heads frozen, using a straight-through estimator for the binary distances. A two-tier rule picks how many new bits to retain at each growth stage. It keeps the shortest prefix whose empirical Top-K failure rate is at most 6% in both directions, and otherwise the shortest prefix passing a paired exact-binomial improvement test with a multiplicity-controlled cutoff (0.05/36). After growth, an independent Calibration set reselects the last increment using one-sided Clopper-Pearson bounds and a union bound over 120 statements, giving a joint 95% release guarantee. Two simple bounds, a candidate-coverage floor and a margin repair limit, characterize what added bits cannot fix.
Critical strengths
- Keeping the stored search index at its original width and generating historical-item bits only after candidate retrieval is a well-motivated answer to a genuine problem: no re-encoding or rewriting of historical codes, and exact recovery of the prior code when an extension is removed. The companion bounds (R(d) >= Pr{A(q)=1} from candidate coverage, and the margin repair limit M_old < -d, Appendix C) are simple but concretely tell a practitioner when new bits cannot help, which is more actionable than the asymptotic analysis typical in this area.
- All methods share frozen features, source identities, and arrival orders; three seeds repeat complete training; the length-selection rule is pre-specified with an explicitly allocated error budget (0.05/36 in development, beta = 0.05/120 across 120 statements at calibration, Appendix D); matched controls A1-A4 isolate the design choices (Section 4.5, Table S10); and the exact-result check (Appendix C.1) verifies the 1% shortlist reproduces full-gallery Top-K. The paper also reports where ODEH loses, BITS-CM's slightly lower COCO I2T failure (Section 4.2), cosine reranking being faster everywhere and better at 100k (Section 4.4), residual refitting reaching lower failure with fewer bits on NUS-WIDE (Table S5), and stage-local selection ending below target-only P@10 on COCO (Section F.5). That candor is a large part of why I trust the reported gains.
Critical weaknesses
- The paper motivates ODEH by the cost of materializing new bits for historical items, yet its own measurements suggest that cost is small at query time: one-time materialization amortizes after 33-154 queries (Figure S2), and the cumulative logical-writes advantage (Equation S2) is asserted rather than measured end to end. The incremental expansion path, which reuses stored residuals and is the scenario growth actually produces, "remains unmeasured" (Section 4.4). A measurement of cumulative encode and write cost, storage, and serving latency for materialization-at-every-accepted-expansion versus on-demand execution, over the paper's own growth trajectory, is exactly the evidence that would justify the mechanism the paper is named after.
- ODEH requires retaining a 2,048-byte FP32 feature per item against 4 bytes of index code (Table S4; features are 1172 MiB versus 2.29 MiB of codes at COCO 100k). Cosine reranking over the same features and the same shortlist needs no residual heads, is faster in all eight dataset-scale-direction groups, and beats ODEH's P@10 at COCO 100k by 1.46 and 0.41 points, while ODEH wins on NUS-WIDE and MIRFlickr at 22.5k and the cause "remains unresolved" (Section 4.5). Relatedly, Table S7 shows full-gallery mAP@all far below OH-ELS on NUS-WIDE (60.45 vs 78.79 I2T) and MIRFlickr (78.10 vs 92.24). As a result, the regime in which learned residual bits are preferable to simply reranking the retained features, or to materializing a full code, is not yet characterized. The paper is honest about each piece, but a reader cannot currently predict which regime a deployment falls in.
Questions for authors
-
Can you measure incremental materialization (encode plus write of newly accepted bits for the historical items at each accepted expansion) under your growth protocol, and compare cumulative writes, storage, and serving latency against on-demand execution over the whole trajectory? This is the direct test of the deployment claim W1 says is missing.
-
Under what deployment conditions is retaining 2,048 bytes of features per item acceptable while a roughly 10-byte materialized full code is not? Is the feature store assumed to already exist for training or other services? Please state the intended regime explicitly, since it determines who benefits from ODEH.
-
Why does ODEH lose to cosine reranking at COCO 100k while winning at 22.5k and on the other two datasets? Is there evidence discriminating between candidate coverage, residual head capacity, and objective misalignment as the cause?
-
Table S7 shows ODEH's full-gallery mAP@all well below several baselines on NUS-WIDE and MIRFlickr. Is this a price of the boundary objective, and does it matter for users who need full ranking rather than Top-10? A brief main-text discussion would materially change how I read the headline claim.
-
The improvement-test cutoff 0.05/36 is reused across the five-stage growth to 100k sources, and stage decisions are adaptive, since later stages condition on earlier acceptances. How sensitive are the retained lengths and final test results to this cutoff, for example at 0.05 or 0.05/12?
-
The PBEH latency comparison (Table S3) uses your optimized serving implementation against PBEH's native evaluator. Can you confirm the latency ordering survives a shared implementation, at least at one operating point?
6 comments
Q1. We measured incremental materialization over all five COCO growth stages: ODEH preserves identical rankings while eliminating historical residual writes and making updates available earlier, at the query latencies shown below. At each accepted extension, the stored-code control reuses existing blocks and encodes only the newly accepted bits for historical items. Both paths use the same models, candidates and ranking rules. Measurements include encoding, packing, durable writes and publication, with features resident.
Across the complete trajectory, on-demand execution requires zero historical residual writes and reduces update-ready time as follows. We separate historical backfill from the full update-time difference, which also includes residual processing for new arrivals and publication; on-demand execution defers residual computation to queries.
| Five-stage cumulative quantity | Seed 0 | Seed 1 | Seed 2 |
|---|---|---|---|
| Historical residual-code payload written (bytes) | 840,408 | 30,012 | 30,012 |
| Historical encoding, packing and durable writes (s) | 0.478 | 0.018 | 0.018 |
| Extra update-ready time of stored execution (s) | 2.077 | 1.393 | 1.396 |
The following table compares storage and serving latency throughout growth. Latencies are three-seed Validation means, I2T/T2I. Residual storage is additional to the common 32-bit index; ODEH stores zero residual-code payload at every stage. Feature and model storage are accounted for separately.
| COCO sources | On demand (ms) | Precomputed (ms) | Precomputed residuals (MiB) |
|---|---|---|---|
| 2,500 | 1.30/1.15 | 0.88/0.81 | 0.029 |
| 7,500 | 2.03/1.61 | 1.28/1.04 | 0.172 |
| 22,500 | 3.06/1.82 | 1.96/1.16 | 0.515 |
| 67,500 | 7.15/2.43 | 4.29/1.53 | 1.546 |
| 100,000 | 10.10/3.08 | 6.23/1.98 | 3.435/2.290/2.290 across seeds |
Using the full update-ready differences and the measured query latencies, equal query counts at each stage with equally frequent directions give cumulative crossovers of 327/223/223 queries per stage across seeds. Below those counts, ODEH takes less total serial update-plus-query time; above them, precomputation amortizes its update cost. This directly measures the incremental growth scenario requested. Fig. S2's 33–154 queries concern a different operation: one-time construction of the entire residual chain with OS-cache writes. Revised §4.4 and Appendix G.1 distinguish the two measurements.
The cumulative byte difference stems from seed 0's final 16-bit extension across 405,198 historical entries, which adds 810,396 payload bytes. The other seeds retain 64 bits at that stage (Appendix G.1).
Q2. Storing a ten-byte full code is feasible. ODEH addresses when to perform its database-wide computation and writing, using features that the intended service already retains for learning or another task. A resident feature uses 2,048 bytes per item, about 1,172 MiB at COCO 100k. Sharing an existing copy avoids a second feature store; a dedicated retrieval copy adds that amount. The base index uses four code bytes per item plus an identifier, while an 80-bit materialized code uses ten code bytes. Thus the deployment decision concerns update readiness and query volume, rather than an inability to store ten-byte codes.
The concurrent NUS-WIDE 100k experiment measures the value of early access directly. During a 96→112-bit update, with old codes already stored for the materialized controls, ODEH returns the first new-model result in 33.9–37.7 ms, versus 548.7–631.6 ms when serving the old version until backfill finishes. A hybrid that generates the new candidate block on demand during backfill also returns the new result in 34.5–37.5 ms, then uses stored codes for subsequent requests. Table 3 reports this experiment; it shows that on-demand generation supplies the early-update benefit even when a service later materializes residuals.
With an existing resident feature store, continuous on-demand execution is useful when queries between updates stay below the measured crossover and its query latency meets the service budget. With sustained traffic and permitted materialization, precomputed service amortizes update costs, while the hybrid additionally preserves early access. Cosine is the lower-latency option when its retrieval quality meets the application requirement; learned residuals are useful when their additional ranking quality justifies candidate computation, as quantified in Q3. Revised §4.4 specifies the shared-feature condition, the on-demand/hybrid choice and the measured quality–latency trade-off with cosine. Resident-feature timings include candidate access; Fig. S1 reports disk access separately.
Dear Reviewer Yeu5,
Thank you for your thorough review and for recognizing the value of preserving historical codes, the practical role of the candidate-coverage bounds, and the transparency of the evaluation. Your questions helped us turn the deployment discussion into measured comparisons and separate the explanations for the ranking results.
We have measured incremental materialization over the full growth trajectory, evaluated retained code widths at fixed weights, tested the training objective and selection threshold, and repeated the PBEH timing with shared operators. Sections 4.2 and 4.4 and Appendix G incorporate these results; Tables S3, S12 and S13 provide the corresponding comparisons. The four responses below address your questions and concerns point by point.
Unless stated otherwise, paired directional results are I2T/T2I, and metric differences are in percentage points.
We appreciate the time you have devoted to our work and hope the revised manuscript and additional evidence address your concerns.
Sincerely,
The Authors