acceptodds
Under review as a conference paper at ICLR 2027

On-Demand Hash Expansion for Growing Cross-Modal Databases

Abstract

In growing cross-modal databases, adapting representations to continuous data arrivals while maintaining historical search indexes poses a persistent challenge. Although new arrivals provide supervision to improve representations, materializing newly learned hash bits requires an encoding and writing pass over historical entries. We introduce On-Demand Elastic Hashing (ODEH), which expands ranking capacity without widening the stored search index. ODEH retrieves candidates via a compact base index and ranks them by complete Hamming distance using residual bits generated on demand from frozen backing features. This decoupled design preserves lightweight index scans while trading historical code writes for retained feature storage and candidate computation. Residual blocks are trained against candidate ranking boundaries with earlier bits frozen. A two-tier rule selects the shortest extension meeting a prescribed Top-K quality target, falling back to statistically tested improvement when no extension meets the target. Experiments on COCO, NUS-WIDE, and MIRFlickr compare ODEH with six external baselines using shared frozen features. ODEH achieves the highest mean in five of six dataset–direction pairs for each of Precision@10, nDCG@10, and query success, while maintaining a 32-bit base index.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
cross-modal hashing, incremental retrieval, hash code expansion, two-stage retrieval, adaptive code length

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Yeu5OpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. 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.

  2. 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.

  3. 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?

  4. 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.

  5. 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?

  6. 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

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

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 quantitySeed 0Seed 1Seed 2
Historical residual-code payload written (bytes)840,40830,01230,012
Historical encoding, packing and durable writes (s)0.4780.0180.018
Extra update-ready time of stored execution (s)2.0771.3931.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 sourcesOn demand (ms)Precomputed (ms)Precomputed residuals (MiB)
2,5001.30/1.150.88/0.810.029
7,5002.03/1.611.28/1.040.172
22,5003.06/1.821.96/1.160.515
67,5007.15/2.434.29/1.531.546
100,00010.10/3.086.23/1.983.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.

Reviewer_MCkGOpenReview ↗
Rating
3(+1)
Confidence
2(−1)
Informativeness
3(+1)
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces On-Demand Elastic Hashing (ODEH), a method designed for continuously growing cross-modal databases. ODEH maintains a fixed 32-bit base index to first retrieve candidate items. It then utilizes stored, frozen features to dynamically generate residual hash bits for both the query and the retrieved candidates, allowing for re-ranking based on the Hamming distance of the full-length hash codes—all without requiring the modification or rewriting of existing hash codes for historical entries. The paper proposes a "boundary loss" tailored to Top-K query success criteria, along with a selection rule for shared hash-code lengths that prioritizes meeting quality targets (or otherwise accepts lengths that demonstrate improvement via paired testing); a separate calibration step is applied to the final selection. The authors analyze how candidate coverage and the length of extended hash bits constrain the system's ability to correct retrieval errors. Evaluations conducted on the COCO, NUS-WIDE, and MIRFlickr datasets—using three different training seeds—compare ODEH against six external baselines and internal control variants, while analyzing the trade-offs between retrieval quality, feature storage requirements, the need for historical data updates, and query latency.

Critical strengths

This paper proposes a specific mechanism that enables the utilization of newly learned hash bits without requiring the rewriting of historical retrieval codes. The division of labor between fixed candidate indexing and on-demand residual computation is clearly defined: the learned extended codes consistently yield performance improvements over 32-bit base codes of the same length. This demonstrates that the proposed architecture provides valuable additional ranking capability.

Critical weaknesses
  1. The practical advantages of on-demand execution remain unclear. Section 4.4 and Appendix E.1 demonstrate that precomputing residual codes yields identical ranking results while reducing query latency. Furthermore, under the tested conditions, the cost of full materialization is amortized within just 33–154 queries. Table S4 also indicates that, in the COCO setting with 22,500 source samples, storing full codes—as opposed to base codes—increases storage requirements by only ~0.773 MiB, whereas on-demand execution necessitates retaining 263.799 MiB of features. The paper must justify why the benefits of avoiding these write operations outweigh the costs associated with repeatedly computing and accessing features.
  2. The motivation for keeping all existing residual coordinates unchanged is not sufficiently substantiated. Residual retraining could similarly preserve the base index while avoiding the need to write back historical codes—an advantage also achieved through on-demand execution. On the NUS-WIDE dataset, 48-bit residual retraining achieves a higher P@10 than 80-bit ODEH (90.12/86.07 vs. 86.80/83.72), while also exhibiting lower failure rates and reduced query latency. The authors need to clarify what specific benefits necessitate keeping the residual coordinates immutable.
Questions for authors
  1. Under what deployment conditions does on-demand execution offer a practical advantage over pre-computing and storing residual codes? Please specify the relationship between the associated costs and the break-even point—cited in the paper as 33–154 queries—at which the two approaches become equivalent. Additionally, please clarify whether retaining features increases server-side storage costs, and explain how the overhead of incremental encoding and persistent writes factors into this comparison.

  2. Beyond keeping the base index static, why is it required that all existing residual coordinates remain unchanged? Given that 48-bit residual retraining on the NUS-WIDE dataset yields superior retrieval quality and lower query latency compared to 80-bit ODEH, please articulate what specific functionality or guarantees are forfeited by allowing residual retraining. Furthermore, please justify how the benefits of keeping these coordinates fixed warrant the current trade-off between retrieval quality and query latency.

4 comments

Dear Reviewer MCkG,

Thank you for your careful review and for recognizing that the learned extensions provide additional ranking capacity without rewriting the base index. Your questions helped us focus the new evidence on the practical value of on-demand execution and coordinate preservation.

We have added measurements for incremental durable updates and concurrent serving, along with an equal-width comparison between freezing old heads and updating them while retaining the earlier model. Sections 4.2 and 4.4, Tables 2 and 3, and Appendix G now report the measured quality, availability and resource trade-offs. The two 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

Q1. Continuous on-demand execution saves update-plus-query time when features are already shared with another service and the queries between updates are too few to amortize materialization. For larger subsequent query volumes, computing on demand during backfill and then switching to stored codes provides earlier access to the new ranking and lower later query cost. These are two measured deployment choices, with feature storage accounted for separately.

The intended service already retains resident features for learning or another task. At COCO 22.5k, sharing this copy reuses 263.799 MiB of features; retaining features solely for retrieval adds that amount. Full codes require only 0.773 MiB beyond base codes (Table S4), so their storage is feasible. ODEH's benefit is deferring or avoiding the database-wide residual encoding and writing pass while making the learned ranking available immediately after the head is ready.

Let BB be the additional measured update time of the stored-code path relative to the on-demand path, and let ΔL=Lon−Lstored\Delta L=L_{\mathrm{on}}-L_{\mathrm{stored}} be the extra mean query time. For qq queries, the difference in serial execution time is Ton−Tstored=qΔL−BT_{\mathrm{on}}-T_{\mathrm{stored}}=q\Delta L-B. On-demand execution costs less time below q∗=B/ΔLq^*=B/\Delta L; stored scoring repays its update cost above it. The original 33–154-query crossovers measure one-time full-chain encoding and writes to the OS cache. Our new five-stage COCO replay instead reuses stored old blocks and measures incremental encoding, packing, durable writes and publication, including residual processing for new arrivals. Its 100k crossovers are 455/183/187 queries for the three seeds, with equally frequent retrieval directions. Common training and ingestion costs cancel between execution paths; resident-feature access and residual computation enter query time. Thus BB measures the overall update-time difference, rather than historical writes alone (Appendices E.1 and G.1).

The concurrent experiment separately tests when the learned update becomes usable. In a NUS-WIDE 100k update from 96 to 112 bits, all variants share resident features and a ready base index, while the stored-code variants already hold the old residuals. At the highest of three prespecified request rates (97.46 queries/s), continuous on-demand, hybrid, and old-version-then-stored serving return their first new-version result after 34.64, 37.45 and 631.65 ms, respectively. The first 50 requests attain mean P@10 of 91.47%, 91.47% and 90.00%. Across all 1,000 requests, mean response times including queueing are 9.23, 5.06 and 4.49 ms. The old version continues serving during backfill; on-demand execution makes the improved ranking available before backfill finishes. The hybrid then captures the lower recurring cost of stored codes (Table 3; three seeds and three repeats).

Q2. Freezing guarantees that truncating the current code exactly recovers the earlier code and scoring function within the same model. Allowing old heads to change removes this prefix guarantee; our refit control preserves the earlier mapping by retaining the old model. This is the specific property for which ODEH freezes residual coordinates (§3.2). Both designs can keep the base index fixed and generate residuals on demand with zero historical residual writes. Both can also support old queries: in our fixed-gallery comparison, the frozen chain and refitting plus the retained old model each recovered all 15,000 original ordered Top-10 lists. They differ in how the old mapping is preserved and how much of the model must be optimized and retained.

To isolate this choice, the new control starts from the same 64-bit NUS-WIDE model and compares two 80-bit updates, with identical architecture, data, candidates and 7,040 training steps. Frozen ODEH improves P@10 over the incoming model by 5.36/4.83 points (I2T/T2I); updating old heads improves it by 7.94/6.38 points. Jointly adjusting old and new coordinates supplies extra optimization freedom, with a measured 2.58/1.56-point gain over freezing. Freezing learns its gain by optimizing only the new block, reducing peak optimization memory from 386.87 ± 15.08 to 199.96 ± 5.79 MiB (48.3%) under matched FP32 AdamW measurements. Preserving old mappings within the same chain also uses 9.750 rather than 15.875 MiB of model storage (Table 2; three seeds).

The original 48-bit refit versus 80-bit ODEH comparison favors refit in both Test quality and query latency; it changes width as well as whether old coordinates can move. In the new 80-versus-80 control, mean new-query latencies differ by less than 0.003 ms per direction. The resource benefit of freezing is therefore in learning and retaining compatible updates, rather than faster same-width queries. For services that continue accepting query codes from earlier releases while limiting update memory, freezing supports those earlier mappings within the current chain and learns useful new ranking capacity with 48.3% less peak optimization memory. The measured price at equal width is 2.58/1.56 P@10 points, with essentially unchanged query latency. Refitting plus an old-model copy offers the other measured choice: higher current quality with more optimization memory and retained parameters. This is a resource and version-preservation choice, rather than a requirement for zero historical writes.

Thank you again for helping us clarify the two deployment choices at the center of your review. Sections 4.2 and 4.4, Tables 2 and 3, and Appendix G now specify when on-demand execution is useful and what preserving old coordinates provides at equal width. The new measurements make the quality, query-time and optimization-memory trade-offs concrete. We hope these additions address your concerns and would be glad to clarify any remaining questions.

We will release the corresponding code and experimental logs to support reproducibility.

Reviewer_1hFhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes On-Demand Elastic Hashing (ODEH) for incremental cross-modal retrieval. It preserves a compact 32-bit base index and generates additional hash bits on demand for shortlisted candidates, avoiding the need to rewrite historical codes. The method introduces a candidate-boundary ranking objective and a risk-based strategy for selecting the number of additional bits. Experiments on COCO, NUS-WIDE, and MIRFlickr demonstrate competitive retrieval performance, with trade-offs between accuracy, storage, and query latency.

Critical strengths

1、The paper addresses the cost of updating historical hash codes in growing cross-modal databases.

2、The candidate-boundary loss directly targets Top-K retrieval success, while the theoretical analysis identifies limitations caused by insufficient candidate coverage.

3、The experiments include multiple datasets, retrieval directions, ablations, statistical calibration, and latency and storage analyses.

Critical weaknesses

1、The distinction from existing incremental hashing and bit-expansion methods, particularly BITS, PBEH, and RCMH, is not sufficiently established.

2、The comparisons mix different update strategies and retrieval budgets, making it difficult to isolate the benefits of ODEH.

3、 ODEH does not consistently outperform competing methods. On NUS-WIDE, residual refitting achieves better retrieval quality with fewer bits, while PBEH performs better on COCO at 100,000 sources.

4、 ODEH avoids historical code writes but retains 2,048-byte FP32 features per item and incurs additional query computation. Its overall storage and lifecycle-cost advantages remain insufficiently demonstrated.

5、Evaluation relies on frozen CLIP features and three relatively small benchmarks, leaving scalability and robustness under changing feature distributions unclear.

Questions for authors

1、What is the fundamental technical novelty of ODEH beyond existing bit-expansion methods combined with candidate reranking?

2、Can the authors provide a matched comparison with materialized residual codes using identical models, candidates, and ranking rules?

3、Why does residual refitting outperform ODEH on NUS-WIDE despite using fewer bits? Can this difference be isolated under equal code lengths?

4、Under what realistic deployment conditions does ODEH provide a net advantage after accounting for feature storage, update costs, and query latency?

5、How robust is ODEH to larger galleries, different feature encoders, and changes in the underlying data distribution?

8 comments

Dear Reviewer 1hFh,

Thank you for your detailed review and for recognizing the importance of historical-index maintenance, the connection between our boundary objective and Top-K success, and the breadth of the evaluation. Your questions helped us sharpen the distinction between learning, execution and coordinate preservation.

We have clarified index width versus ranking width and full-gallery scanning versus candidate reranking in §4.2. In the revision, Tables 2 and 3 add comparisons on equal-width freezing and concurrent serving, while Appendix G includes controlled experiments across encoders, arrival distributions, and data scales. 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

Q1. Beyond evaluating expanded codes on a shortlist, ODEH learns new bits to correct a fixed old-code distance and selects their width by query success. Restricting an existing expansion model to retrieved candidates changes where its bits are evaluated. ODEH additionally specifies how to learn and accept an extension when every earlier coordinate must remain unchanged. Each candidate already has a fixed old-code distance; the new bits must improve the resulting Top-K ordering under that constraint. ODEH's boundary loss evaluates that ordering using the complete old-plus-new distance, while gradients update only the appended block (§3.3). Its length rule then evaluates retrieval success on held-out queries, first retaining the shortest width that meets the failure target in both directions, then testing for paired improvement if none qualifies, and keeping the old code if neither criterion is met (§3.4). Thus the learned correction and the capacity decision address the same retrieval requirement under the frozen-coordinate constraint.

This differs from the historical-code handling described in §2: BITS duplicates historical codes, PBEH compares against their stored widths, and RCMH regenerates codes at a specified length. ODEH generates newly supervised coordinates for historical candidates from retained features while keeping their earlier coordinate functions fixed. The matched COCO A3 control confirms the benefit of retaining these features: when adding 32 bits, replacing features with old-code embeddings increases failure rates by 0.973/0.560 points, with both paired 95% confidence intervals strictly above zero (§4.5). Items sharing an old code can therefore acquire different learned extensions.

Q2. Yes: the matched execution control uses identical models, candidates and ranking rules, and returns identical Top-10 items in identical order. We fix the frozen model, gallery, 1% shortlist, complete Hamming distance and identifier-based tie-breaking rule, and change only whether residuals are generated for candidates or read from precomputed codes (Fig. 5, Appendix E.1). On NUS-WIDE, with timing starting once query features and base codes are available, on-demand generation adds 0.824 ms per query in each direction relative to stored residuals (Table S6), while eliminating historical residual writes.

Q3. Refitting gains optimization freedom by adjusting old and new coordinates jointly; freezing preserves old mappings within one chain and reduces optimization memory. Frozen expansion improves the existing distance using only new bits. The equal-width control below isolates the effect of this constraint. The original 48-bit refit also replaces heads, so its comparison with 80-bit ODEH changes both representation and width. To isolate the effect of updating old heads, we added an equal-width (80- vs. 80-bit) control from the same NUS-WIDE 64-bit checkpoint, with identical architecture, data and 7,040 training steps. Frozen expansion improves Validation P@10 by 5.36/4.83 points over that checkpoint; allowing old heads to update gains a further 2.58/1.56 points (Table 2). The equal-width result establishes that extra optimization freedom improves quality in this setting, separately from the width difference in the original comparison.

Freezing achieves prefix preservation with lower optimization memory. Both designs recover all 15,000 cached queries' original ordered Top-10 on a fixed gallery: ODEH reuses its current prefix, while the updated-head control retains the old model. Training only ODEH's new block reduces peak optimization-step memory by 48.3%, from 386.87 to 199.96 MiB, and avoids a 6.125 MiB old-model copy (Table 2, Appendix G.1). This is the measured resource and compatibility trade-off for preserving the old coordinates.

Q4. Continuous on-demand execution reduces total update-plus-query time when a service already shares resident features, receives fewer queries per update than the measured crossover, and can accommodate candidate-generation latency. Using the improved ranking before backfill completes is a separate benefit, available to both continuous on-demand and hybrid serving. The feature store must be accounted for: it occupies 2,048 bytes per item, about 1,172 MiB at COCO 100k. In the intended deployment, this feature store is shared with model training or other downstream services; retaining it solely for retrieval incurs that extra storage cost. The deployment decision therefore accounts for the feature store's incremental cost together with measured update and query times, rather than the four-byte index alone.

The incremental COCO replay includes residual encoding of new arrivals, historical backfill (when triggered), packing, durable writes, and publication. Using measured update costs and query latencies, precomputation recovers its extra update time after 455/183/187 equally mixed I2T/T2I queries at 100k, across the three seeds. Below those counts, ODEH uses less total serial time; above them, stored residuals amortize their update cost (Appendix G.1).

Earlier use of the learned ranking is a separate benefit. At the prespecified 97.46 queries/s NUS-WIDE replay, ODEH returns its first new-version result 34.64 ms after head readiness, versus 631.65 ms for serving the old version until backfill finishes. The first 50 requests then achieve 91.47% rather than 90.00% mean P@10 (Table 3). When precomputation is allowed and subsequent traffic is large, a hybrid uses the same on-demand mechanism during backfill and then switches to stored codes: it preserves the early new-model results and reduces mean response over 1,000 requests from ODEH's 9.23 ms to 5.06 ms. These measurements identify when to keep continuous on-demand serving and when to use it during a transition to materialized serving.

Comments on the paper

1 comment

We are truly glad for your positive feedback and the score raise, it really means a lot to us. Your two questions helped us define the applicable scenns and design trade-offs of ODEH much more clearly, so we added the necessary experiments and analysis. Thank you again for your valuable time and your careful review of our paper!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.