acceptodds
Under review as a conference paper at ICLR 2027

One-Write Associative Sketching for Partition-Invariant Lifelong Cross-Modal Hashing

Abstract

Lifelong cross-modal hashing updates compact image-text indexes as paired data arrive. Task-boundary updates can nevertheless change the items returned for the same query when an ordered stream is segmented differently, even at similar retrieval accuracy. The challenge is to preserve both the current query head and codes written by earlier heads. We propose (\method), which couples prefix learning with one-write indexing. With frozen features, permanent Dice-derived semantic targets and additive moments recover the full-prefix code-and-relation objective. We prove that its unique ridge solution and shared sample-count clock yield identical query heads, historical codes and rankings across taskifications. Perturbation bounds connect approximate moments to retrieval changes. We evaluate cross-partition top- agreement using the top- retrieval reproducibility rate, the mean Jaccard overlap of returned sets, alongside relevance. Across four datasets and three paired seeds, the analytic core returns identical sets and ordered lists at . Clocked discrete extensions retain this agreement, and fixed-gallery query calibration achieves the highest mean average precision on all four datasets, reaching 92.68% on MIRFlickr-25K at 64 bits when averaged over both retrieval directions.

Primary area:
transfer learning, meta learning, and lifelong learning
Keywords:
Lifelong Cross-Modal Hashing, Partition-Invariant Retrieval, One-Write Indexing, Associative Relation Sketching, Permanent Semantic Codes

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_mJTnOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper identifies a previously underexplored problem in lifelong cross-modal hashing: different task partitions of the same ordered data stream lead to inconsistent historical binary codes, even when query heads remain similar. The authors propose PILCH, which achieves partition invariance through frozen features, Dice-coefficient-based permanent semantic target encoding, additive prefix moments, and a shared sample-count clock. Theorem 1 proves invariance of prefix heads, historical codes, and ranking lists under explicit assumptions. Experiments introduce the TRR metric to quantify cross-partition retrieval reproducibility and validate the method on four datasets, where the PILCH core achieves 100% TRR and a calibrated clocked extension attains the highest directional mean mAP.

Critical strengths
  1. PILCH addresses partition sensitivity at the indexing level, offering clear computational advantages. By freezing features and using additive prefix moments, the method completely avoids the gallery rewriting or feature retraining overhead common in existing lifelong hashing schemes, with each write strictly O(1) complexity. This design forms a clear contrast with methods like LEMON that require periodic gallery rewriting, and demonstrates practical deployment value in large-scale stream data scenarios.
  2. The theoretical derivation and experimental design are both solid. The proof chain for Theorem 1's invariance claim is complete, and the appendix documents constants, seeds, and baseline recurrence details, which is a level of transparency uncommon in this area. TRR@20 as a new metric has practical utility for audit scenarios, and directional mean mAP avoids bias from single-direction reporting. Ablation experiments cover component contributions and state separation, making the overall evaluation thorough.
Critical weaknesses
  1. The choice of Dice coefficient for target code construction lacks comparative justification. PILCH uses Dice coefficients based on global label co-occurrence frequencies to generate permanent semantic target codes, but the paper does not discuss why Dice was chosen over other set similarity measures (e.g., Jaccard, overlap coefficient, cosine similarity). Different measures would produce different target code distributions, which could directly affect both the strength of partition invariance and final retrieval performance. While Dice offers algebraic convenience, the absence of comparison against alternatives leaves this core design choice insufficiently motivated and makes it difficult to judge whether this selection is critical to the method's success.
  2. The causal source of mAP gains is not isolated. PILCH outperforms baselines on both TRR and mAP, but these two improvements may stem from different mechanisms: TRR gains come directly from the partition invariance design, while mAP gains may arise from the quality of the Dice target encoding itself, independent of invariance. Table 8's ablation isolates component contributions but does not compare PILCH against the strongest baseline under a single fixed partition. Therefore it remains unclear whether the mAP advantage depends on the multi-partition setting.
Questions for authors
  1. Is the choice of Dice coefficient critical to target code construction? Can you provide a comparison with alternative label co-occurrence measures (e.g., Jaccard, overlap coefficient) on TRR and mAP, or theoretically analyze which properties of Dice are essential for partition invariance?
  2. Table 8's ablation does not include a single-partition baseline comparison. Can you provide mAP numbers for PILCH vs. the strongest baselines under a single fixed partition? I want to know whether the mAP improvement actually comes from the invariance mechanism.
  3. The analytic core and fixed-clock discrete extensions both achieve partition invariance, but through somewhat different mechanisms. Could the authors clarify which parts of the guarantee rely on additive prefix statistics and the unique ridge solution, and which follow from synchronizing model updates and database writes at fixed sample counts?
  4. Equation (4) recovers the full-prefix pairwise relation objective without explicitly storing cross-task similarities. Could the authors briefly explain which algebraic properties make this exact recovery possible, and why the additive statistics in Equation (2) are sufficient to preserve cross-task relations?
8 comments
AuthorsOpenReview ↗

Response to Reviewer mJTn[1/6]

Dear Reviewer mJTn,

Thank you for your detailed review and for recognizing the indexing formulation, theoretical analysis, and reproducibility of our evaluation. Your suggestions helped us strengthen the justification for the permanent targets and explain the mechanisms more clearly.

We have added the controlled comparison of Dice, Jaccard, overlap, and cosine to the manuscript. We also clarified the fixed-partition accuracy comparison and expanded the derivation showing how the moments recover cross-task relations. The four responses below address each question in order and distinguish the analytic and discrete mechanisms behind the retrieval guarantee.

We are grateful for your constructive suggestions and for considering the revised explanations and evidence.

Sincerely,

The Authors

AuthorsOpenReview ↗

Response to Reviewer mJTn[2/6]

Response to Q1 and W1

Thank you for asking for a direct comparison and a clearer explanation of why we use Dice.

We respectfully clarify that the target is computed from each item's own label vector. Corpus-wide label frequencies play no role in this computation. For nonempty label sets A,BA,B, Dice similarity is D(A,B)=2∣A∩B∣/(∣A∣+∣B∣)D(A,B)=2|A\cap B|/(|A|+|B|). This measures their shared labels directly. The paper realizes this similarity with a fixed feature map and Gaussian projection. Equal label sets receive equal targets throughout the stream.

1. Applicability of Dice

Dice offers a useful mathematical property. For nonempty label sets, its positive-semidefinite, unit-diagonal kernel has an exact finite feature map ψ\psi. The inner product of two mapped labels equals their Dice similarity. A single Gaussian projection is then drawn and fixed to produce the binary targets. For Dice similarity DD, the probability of a matching bit over that draw is Pr⁡[cir=cjr]=1−arccos⁡(D)/π.\Pr[c_{ir}=c_{jr}]=1-\arccos(D)/\pi. Higher label similarity therefore gives a higher probability of matching bits. This is the link between the semantic measure and the permanent code. For binary labels, Jaccard similarity JJ satisfies J=D/(2−D)J=D/(2-D). Their continuous ordering agrees, while finite-bit codes can differ.

2. Controlled affinity comparison

Following your advice, we completed a controlled comparison of Dice, Jaccard, overlap, and cosine. We used the analytic encoder-write learner on NUS-WIDE, COCO, MIRFlickr, and IAPR. The original three seeds, frozen CLIP features, streams, solver, hyperparameters, shared clock, and queries were held fixed. Codes have 64 bits.

The four measures use the same encoder: up to 256 distinct bootstrap label vectors serve as fixed anchors, and a shared Gaussian projection maps their affinity vectors to bits. Only the affinity formula changes. The common affinity-vector projection gives a defined code for all four measures. Native Dice retains the paper's exact finite feature map; its original-query results were reproduced separately. The shared-encoder comparison isolates the similarity choice.

The solver retains code and relation weights of 10, ridge 10−510^{-5}, and the original sample-count solve schedule. Anchors are selected once by a fixed rule.

For each variant, we replayed the stream under P1,P10,PmicroP_1,P_{10},P_{\mathrm{micro}}. The replays compare the state and head at every solve, the historical gallery codes, query codes, and write times. Every variant reaches 100% TRR@20, with identical scoring inputs across these taskifications. The complete experiment includes all four datasets and all three original seeds. The four affinity variants plus the native-Dice reference give 60 completed experiment cells and 180 taskification replays. The native reference checks reproduction; the four shared-encoder columns provide the controlled affinity comparison.

3. Support for the results

This result agrees with the proof. A fixed deterministic target ci=f(ℓi;ω)c_i=f(\ell_i;\omega) yields the same additive statistics when ω\omega and the execution conditions are shared. Positive ridge then yields the same unique head. The target's permanence gives this guarantee; the chosen similarity affects which labels receive similar codes and hence retrieval relevance.

Table 3.1 reports full-gallery mAP over all final-prefix queries, averaged across both directions and three seeds. Relevance means any shared label, and Hamming ties use item ID. Within the shared encoder, Dice is within 0.24 mAP points of the best tested measure on every dataset. This shows that its mathematically convenient construction also gives competitive retrieval accuracy.

Section 3.2 now specifies item-label construction. Section 4.4 and new Appendix C.8 report the controlled comparison. Dice provides an exact fixed map and an explicit link to bit agreement; all four tested affinities preserve invariance with permanent targets.

Table 3.1. Shared-encoder mAP (%)

DatasetDiceJaccardOverlapCosine
NUS-WIDE71.6071.8470.8871.55
COCO75.9676.0875.8376.04
MIRFlickr80.4280.0180.0580.52
IAPR52.5052.2852.3852.53

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

AuthorsOpenReview ↗

Response to Reviewer mJTn[3/6]

Response to Q2 and W2

Thank you for asking whether the reported mAP gains remain under one fixed partition and which components produce them.

Table 1 evaluates mAP under a single fixed P10P_{10} taskification. The relevance scores are obtained within that partition. The cross-partition comparisons separately evaluate reproducibility. We reproduce the requested baseline comparison in Table 3.2 below.

1. Comparison under fixed P10

The comparison uses the paper's frozen features, ordered streams, 64-bit codes, both retrieval directions, and the three original seeds. Each method is evaluated on the same eligible query cohort against the same gallery population. Hamming ties follow the same item-ID rule. Values average directions within each seed and then average the three seeds. The tested uncalibrated baseline is selected separately for each dataset, so the table includes the strongest corresponding reference.

The calibrated pipeline has higher mean mAP on each dataset. These gains occur within the single fixed partition. They are therefore present in an ordinary retrieval comparison, independently of computing the cross-partition TRR metric.

2. The role of components in retrieval

We agree that this result needs precise component attribution. The high-accuracy row combines the selected discrete-code gallery with fixed-gallery query calibration. The gallery supplies binary codes learned by DOCH or LEMON under a sample-count clock. The query stage combines current, semantic, aligned alternate, and pairwise predictions, followed by the selected residual. It then binarizes the query prediction for Hamming retrieval. These stages fit later query predictions to the codes already stored in the gallery.

The analytic core explains why the historical index remains consistent. Its permanent targets and additive moments give an exact full-prefix objective and a unique regularized solution. Together with the shared write schedule, they preserve historical codes and rankings across taskifications. The highest-accuracy row is the calibrated discrete extension of that indexing framework.

The added target experiment in our response to Q1/W1 isolates similarity choice within the analytic encoder-write learner. It holds the encoder, solver, clock, features, and query population fixed while changing the affinity. All four affinities preserve TRR, while their mAP values differ. That comparison directly separates the target's relevance geometry from the permanence needed for invariance.

The original accumulation ablation further tests the use of historical information. With P10, the permanent Mode-T gallery, features, and solve counts fixed, retaining full-prefix statistics improves mAP by 0.432–7.720 points across the four datasets. This comparison isolates retained training history within the analytic learner.

Applying a shared schedule to LEMON yields perfect task-partition reproducibility while retaining its retrieval utility. Query calibration then improves compatibility with the selected fixed gallery.

Revised Section 4.2 explicitly states the fixed-P10 setting and attributes its gains to the calibrated pipeline. Section 4.4 and Appendix C.8 add the affinity comparison. Together with the shared-clock intervention, these results distinguish relevance from partition reproducibility.

Table 3.2. Fixed-P10P_{10} mAP (%)

DatasetUncalibrated baselineCalibrated pipeline
NUS-WIDEDOCH 83.2083.94
COCOLEMON 82.0284.46
MIRFlickrDOCH 92.2092.68
IAPRLEMON 67.5969.84
Reviewer_4XKcOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates task-partition sensitivity in lifelong cross-modal hashing under a one-write indexing setting. The authors observe that different taskifications of the same data stream may yield different retrieval results, even when retrieval accuracy remains similar. To address this issue, PILCH combines permanent semantic targets, additive prefix statistics, and a shared sample-count update schedule to ensure partition-invariant query heads, historical codes, and retrieval rankings.

The paper provides theoretical guarantees under explicit assumptions and evaluates retrieval reproducibility alongside retrieval accuracy. It further extends the fixed-clock principle to discrete hashing methods and introduces fixed-gallery query calibration to improve retrieval performance.

Critical strengths
  1. A meaningful and well-defined problem.

The paper identifies an interesting limitation of conventional retrieval evaluation: similar mAP does not necessarily imply consistent retrieved items. The distinction between the final query encoder and historical codes generated at different stages is particularly relevant to one-write indexing. While related work has explored analytic incremental learning and backward compatibility, this specific formulation of partition-invariant retrieval provides additional insight.

  1. Convincing theoretical and empirical validation.

The theoretical analysis establishes the claimed invariance under clearly stated assumptions. Experiments across different taskifications, datasets, and random seeds largely support the main claim. In particular, the fixed-clock experiments demonstrate that retrieval reproducibility can be achieved without materially sacrificing retrieval relevance.

Critical weaknesses
  1. The incremental algorithmic contribution is somewhat limited.

The experiments show that applying a fixed update clock to LEMON already achieves perfect cross-partition retrieval reproducibility. This suggests that a substantial part of the invariance property follows from making model updates and database writes independent of task boundaries, rather than from the proposed associative relation objective itself.

Moreover, the relation-loss ablation shows little improvement in retrieval accuracy, while the analytic core is less accurate than several discrete hashing baselines. Although these observations do not invalidate the theoretical contribution, they limit the demonstrated practical advantage of the analytic learning component.

  1. The strongest retrieval-accuracy results rely on a separate calibration pipeline.

The highest mAP results are obtained by combining fixed-clock discrete hashing with additional query calibration, rather than by the analytic core alone. The contributions of these components should therefore be interpreted separately. In addition, the retrospective evaluation note in Appendix B.9 leaves some uncertainty about the independence of the final calibration assessment.

Questions for authors

Questions for Authors

Q1. Given that fixed-clock LEMON already achieves perfect partition invariance, what do the authors consider the most important additional benefit of the associative prefix-learning formulation? In particular, how should its contribution be interpreted in light of the negligible empirical effect of the relation term?

Q2. Could the authors clarify the retrospective evaluation statement in Appendix B.9? Specifically, did any observations from the test set influence the design or selection of the final calibration pipeline, and which reported improvements can be regarded as strictly held-out evaluation results?

6 comments
AuthorsOpenReview ↗

Response to Reviewer 4XKc[1/6]

Dear Reviewer 4XKc,

We sincerely thank you for the thoughtful review and your positive assessment of the problem formulation and invariance analysis. We appreciate your careful distinction between the analytic learner, the shared clock, and the calibrated retrieval pipeline.

In the revised manuscript, we explain what the associative state adds beyond synchronized updates and how the relation term acts within the prefix objective. We also make the source of the accuracy gains explicit and clarify the data used during calibration development. The four comments below address your two questions and two weaknesses individually, with the relevant proofs and experimental evidence.

Thank you for giving us the opportunity to strengthen these explanations.

Sincerely,

The Authors

AuthorsOpenReview ↗

Response to Reviewer 4XKc[2/6]

Response to Q1

Thank you for asking what associative prefix learning adds to a shared clock and how the small relation-loss effect should be understood.

1. Benefit beyond the clock

The additional benefit is a recoverable full-prefix solution. Fixed-clock LEMON repeats its update trajectory. The analytic formulation represents the complete code-and-relation objective in additive moments and recovers its unique regularized minimizer. Disjoint segments with shared feature and target maps can be merged by adding their raw moments and sample counts. Normalization then uses the combined count, preserving every observation's weight.

This result extends to the historical index through the shared solve/write schedule. Equal prefix states give equal heads at the scheduled solves. Each item receives the same write-time code across taskifications and retains that code as learning continues. The stored moments also allow the solution to be checked through its normal equation.

2. Meaning of the relation term

The relation term weights errors in fitting the same permanent codes. Let the query head be WW, prefix features UU, target codes CC, sample count nn, and code length bb:

\mathcal L_{\rm rel}=\\|(UW-C)C^\top\\|_F^2/(n^2b^2).$$ Both losses use the residual $UW-C$. Multiplying it by $C^\top$ makes the relation loss depend on correlations among the target codes. Define the feature Gram $G=U^\top U/n$, cross moment $D=U^\top C/n$, and target Gram $H=C^\top C/n$. For weights $\alpha>0,\beta\ge0$ and ridge $\lambda>0$, the stationary equation is $$2(GW-D)(\alpha I/b+\beta H/b^2)+\lambda W=0.$$ Writing $H=Q\operatorname{diag}(h)Q^\top$ and $\kappa_j=\alpha/b+\beta h_j/b^2$, each rotated column is $$(WQ)_{:j}=\left(G+\frac{\lambda}{2\kappa_j}I\right)^{-1}(DQ)_{:j}.$$ The relation weight changes the effective ridge in each target direction. For positive-definite $G$, the weak-ridge limit is $G^{-1}D$, independently of $\beta$. The small ablation effect at the reported ridge is consistent with this behavior. At finite ridge, the feature spectrum and target correlations determine the change. Positive ridge ensures a unique head even when $G$ is singular. ### **3. Evidence for retaining the prefix** Keeping earlier observations has a different effect. Setting the relation weight to zero still retains the full-prefix feature Gram and cross moment. Resetting the state at task boundaries removes earlier feature-target associations. In the original Mode-T ablation, full-prefix accumulation improves mAP on NUS-WIDE, COCO, MIRFlickr, and IAPR, with gains spanning 0.432–7.720 points. The comparison uses fixed P10, frozen CLIP features, 64-bit codes, three paired seeds, and a shared target gallery and solve schedule. We also checked recovery from merged states on all four datasets. At four prefixes per stream, 13 shards were merged in three orders. Across three seeds and both modalities, all 288 comparisons matched the single-batch query codes. The largest relative head deviation was $1.54\times10^{-12}$ in FP64. Revised Section 3.5 makes the recovery benefit explicit. Section 4.4 and Appendix A.2 explain the two roles: the relation term adjusts directional regularization; the associative state retains the observations and cross-task relations needed to recover the prefix solution.
AuthorsOpenReview ↗

Response to Reviewer 4XKc[3/6]

Response to Q2

Thank you for asking how test observations entered development and which improvements have a held-out evaluation.

Earlier diagnostic test mAP/nDCG and writer-compatibility measurements helped identify query-gallery compatibility as a research direction. Appendix B.9 therefore calls the four-dataset calibration matrix retrospective. The final numerical configurations were selected on development data and frozen before final scoring.

1. Training, selection, and scoring

The data roles in that final pipeline are as follows:

  1. Training-stream features and labels fit the semantic maps, gallery-compatible heads, and residuals. Residual fitting uses stream examples and stored gallery-code targets.
  2. Development queries select the gallery, residual objective, architecture, and scale. A fixed screen of 256 queries per seed is followed by validation on the disjoint remainder.
  3. Validation requires a mean mAP gain of at least 0.10 point, positive gains in at least two seeds, and an nDCG@100 loss of at most 0.10 point. Otherwise, the base head is retained.
  4. One configuration per dataset and direction is shared across seeds. Test evaluation uses that saved configuration and the fixed gallery; test labels define relevance for scoring.

2. Which result is held out

The separate XMediaNet study provides held-out accuracy evidence for the permanent-target writer in label-visible Mode T. It uses the published features and fixed split of 32,000 training pairs, 4,000 validation queries, and 4,000 test queries. The first 3,200 training pairs construct frozen class prototypes. All compared methods use the same resulting feature coordinates.

Each gallery item is assigned its permanent 64-bit Dice code once. Its query heads use additive feature Gram and feature-target cross moments. Label visibility concerns database training items at write time. Test queries are encoded from features; their labels are used by the relevance scorer. The training-derived prototype map remains fixed.

A seven-value ridge grid is evaluated on all validation queries, averaging mAP over three seeds. The selected values, 0.0001 for image queries and 0.01 for text queries, are fixed before test variables are loaded. Evaluation then retains all test queries, the full training gallery, both directions, and every seed. Features, gallery population, relevance labels, and tie handling are shared within this comparison.

Table 2.1 reports means and sample standard deviations. Fixed-clock LEMON is the strongest tested comparator in both directions. The permanent-target writer improves directional-mean mAP by 7.55 points, with gains in both directions for every seed. These gains evaluate the permanent-target writer with its query-head ridge selected before test evaluation.

Appendices B.1 and B.9 now state these data roles and selection steps. Table 2.1 retains both directions and three-run sample standard deviations. Its held-out gain concerns the permanent-target writer and additive query heads under validation-selected settings.

Table 2.1. Held-out XMediaNet mAP (%, 64 bits)

MethodImage-to-textText-to-image
Fixed-clock LEMON57.56 ± 0.2820.07 ± 0.39
PILCH Mode T69.71 ± 0.7523.01 ± 0.39
Reviewer_xWxjOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This work studies task-partition sensitivity in lifelong cross-modal hashing, where different segmentations of the same ordered stream can change historical hash codes and retrieved items. The proposed PILCH framework combines permanent Dice-derived semantic targets, associative prefix statistics, sample-count-based updates, and one-write indexing. Its additive moments recover the full-prefix objective, enabling partition-invariant query heads, historical codes, and rankings under the stated assumptions. The authors further extend the idea to fixed-clock discrete learners and query-side calibration. Experiments on multiple cross-modal retrieval datasets evaluate both retrieval quality and cross-partition reproducibility using mAP, nDCG, and TRR, with additional ablations and robustness analyses.

Critical strengths

1.The paper identifies a meaningful and relatively underexplored problem in lifelong cross-modal hashing: the same ordered data stream can produce different historical codes and retrieval results under different task partitions. PILCH addresses this issue through permanent semantic targets, associative prefix statistics, and one-write indexing. The resulting partition-invariance formulation is conceptually clear and provides a useful perspective beyond conventional retrieval-accuracy evaluation. 2.The theoretical and empirical validation is fairly comprehensive. The paper provides an exact partition-invariance theorem, perturbation analysis, multiple datasets and code lengths, comparisons with online and lifelong hashing methods, as well as ablations on taskwise targets, accumulated state, numerical precision, and fixed-clock extensions. Overall, the experiments support the main reproducibility claim reasonably well.

Critical weaknesses

1.In the experiments, applying a shared sample-count clock to LEMON already achieves 100% TRR while preserving almost the same retrieval accuracy, whereas the analytic PILCH core is not consistently competitive with the strongest online baselines in mAP. The paper should clarify which benefits fundamentally require associative prefix learning rather than task-independent update scheduling alone. 2.The final calibrated row in Table 1 combines a selected clocked gallery with query-side transfer, aligned outputs and residual calibration. Section 4.1 gives candidate learners and interval lengths, and Appendix B.9 explains the calibration. However, a concise dataset-specific account of the selected gallery generator, interval and query stages would make the attribution of these gains easier to follow. In particular, readers should be able to identify how this row differs from the analytic PILCH core and the uncalibrated fixed-clock LEMON row. 3.The cached-feature timing in Appendix C.7 is useful, and its measurement scope is stated. The dominant computation within the analytic core could be explained more explicitly: accumulating the feature-code moments, diagonalizing the prefix matrices, or solving the transformed head entries. Relating these operations to feature dimension, code length and solve frequency would help readers assess the computational advantage when configuring a different stream, without confusing the analytic update cost with final-prefix query calibration.

Questions for authors
  1. For each principal dataset, which gallery generator and update interval are selected for the final calibrated row of Table 1, and which query-side stages produce its reported scores? Could the authors clarify this mapping relative to the analytic core and fixed-clock LEMON?
  2. Within the reported cached-feature cost of the analytic core, which operation is dominant, and how does its cost depend on feature dimension, code length and the shared solve schedule? An explanation using the existing implementation and complexity analysis would be sufficient.
  3. Clarification of the calibration protocol. Appendix B.9 states that the final calibration matrix is retrospective because test IDs appeared in earlier diagnostic analyses. Could the authors clarify exactly what test-set information influenced model or hyperparameter selection.
6 comments
AuthorsOpenReview ↗

Response to Reviewer xWxj[1/6]

Dear Reviewer xWxj,

Thank you for your careful review and for recognizing the value of studying task-partition sensitivity in lifelong retrieval. Your questions helped us make the contribution and experimental protocol clearer.

We have revised the manuscript to explain the additional benefit of associative prefix learning, identify the selected calibration settings for each dataset, and break down the analytic learner's computation. We also clarified the calibration selection history and the separate held-out writer evaluation. The four responses below provide the supporting derivations, settings, and results.

We appreciate the time you have devoted to our work and hope these revisions address your concerns.

Sincerely,

The Authors

AuthorsOpenReview ↗

Response to Reviewer xWxj[2/6]

Response to Q1 and W2

Thank you for asking for the dataset-specific configurations; we agree that this mapping is needed to interpret Table 1.

Following your advice, we added the selected gallery, sample-count interval, and query residuals to Appendix B.9, referenced from Section 4.1. Table 1.1 reproduces these settings. One dataset-direction setting is shared across all three seeds.

1. What each row contains

Table 1 reports three constructions. The analytic core learns heads from permanent Dice targets and additive prefix moments. It writes each item's code with the head available at arrival. Uncalibrated fixed-clock LEMON retains LEMON's discrete updates, uses an interval of 128, and fits query heads to its written codes. The final calibrated row uses the selected discrete gallery and the query stages described below. Its retrieval scores belong to that combined pipeline.

The intervals count arriving samples; task boundaries leave this clock unchanged.

2. Query construction

The purpose of calibration is concrete: a later query head must work with gallery codes written at earlier times. We keep every gallery entry fixed and improve the query prediction in that gallery's coordinates. The stages are:

  1. Training-stream labels fit feature-to-label and label-to-gallery maps. This gives a semantic prediction in the selected gallery's code space.
  2. The current head is combined with that prediction, or fitted to the gallery through the selected compatibility ridge. Predictions from the alternate clocked learner are separately aligned to the same gallery.
  3. A pairwise head uses training-label similarities and fixed gallery anchors. The residual receives the current, alternate, and pairwise outputs, together with their interactions.
  4. The selected linear or MLP residual refines the query prediction. The result is binarized and scored by Hamming distance; ties are broken by item ID.

The semantic-transfer weight is 0.25 in the selected candidates, except for NUS-WIDE text-to-image retrieval, which retains the direct head. The compatibility ridge is 10 for MIRFlickr image-to-text and 1/0.1 for IAPR image-to-text/text-to-image. COCO additionally includes the pairwise output in its base prediction with weight 0.25 in both directions.

3. Fitting and selection

Residual fitting uses at most 4,096 stream examples and 2,048 gallery anchors for 15 epochs. The MLP has a 256-unit hidden layer and a zero-initialized output layer. Development queries select the residual type, objective, and scale. A fixed screen is followed by validation on its disjoint remainder; the base is retained when the validation criterion fails. These fitting and selection steps are separate from the streaming analytic update.

Validation requires at least a 0.10-point mean mAP gain, positive gains in at least two seeds, and at most a 0.10-point nDCG@100 loss. This checks both average relevance and its repeatability across seeds before a residual replaces the base head.

Binary ranking separates anchors that share a label with the query from the remaining anchors. Graded ranking also uses their degree of label overlap. The selected residual scale controls the correction applied to the base prediction.

In Table 1.1, I2T/T2I mean image-to-text/text-to-image. Each residual entry gives its type, ranking objective, and scale. “Base” denotes the direct head.

Table 1.1. Selected configurations (64 bits)

DatasetGallery / intervalI2T residualT2I residual
NUS-WIDEDOCH / 512Linear binary, 0.75Base
COCOLEMON / 2,048MLP graded, 0.75MLP graded, 0.75
MIRFlickrDOCH / 512MLP graded, 0.75Linear graded, 0.50
IAPRLEMON / 2,048MLP graded, 0.75MLP binary, 1.00
AuthorsOpenReview ↗

Response to Reviewer xWxj[3/6]

Response to Q2 and W3

Thank you for asking which operations dominate the analytic core and how their costs change with the configuration.

Moment accumulation accounts for a median 91.6% of recorded learner time in the five original NUS-WIDE repeats. We obtained this figure by matching the saved checkpoint timers and summing accumulation and complete-solve time within each repeat. Revised Appendix C.7 adds all five repeats and the cost analysis below; Table 1.2 reproduces the timings.

1. Operations and scaling

Each arriving item contributes to a feature Gram matrix, a target Gram matrix, and a feature-target cross moment. These outer-product updates account for the accumulation timer. Each scheduled solve then diagonalizes the prefix matrices, rotates the right-hand side, divides the transformed entries, and rotates the head back. The complete-solve timer also includes objective and normal-equation checks. Its suboperations were recorded together; their separate growth rates follow from the matrix dimensions.

Let the image/text feature dimensions be rx,ryr_x,r_y, the code length be b, the stream length be NN, and the number of scheduled solves be K. Accumulation costs $ O\left(N[r_x^2+r_y^2+b^2+(r_x+r_y)b]\right). $ The feature Grams give the quadratic feature terms. The target Gram gives b2b^2, and the cross moments give (rx+ry)b(r_x+r_y)b. Every item contributes once, independently of how task boundaries divide the stream.

At each solve, eigendecomposition costs $ O(r_x^3+r_y^3+b^3). $ The basis rotations cost $ O((r_x^2+r_y^2)b+(r_x+r_y)b^2), $ and the entrywise divisions cost O((rx+ry)b)O((r_x+r_y)b). These divisions are scalar operations after the matrices have been diagonalized. They are the final step of a matrix solve whose decomposition and rotation costs must also be counted.

For a different stream, this gives a practical guide. Increasing feature dimension raises accumulation quadratically and feature diagonalization cubically. Increasing code length affects the target Gram, cross moments, rotations, and target eigendecomposition. Increasing solve frequency multiplies the per-solve terms by KK, while leaving the once-per-item accumulation work unchanged. These are arithmetic scaling relations, with actual runtimes also depending on the matrix library and hardware.

2. Storage and timing scope

The prefix moments require O(rx2+ry2+b2+(rx+ry)b)O(r_x^2+r_y^2+b^2+(r_x+r_y)b) storage, independently of stream length. Heads, the semantic map, and the growing gallery are additional storage.

For the reported CLIP setting, each modality has 512 feature coordinates plus a bias, so rx=ry=513r_x=r_y=513, with b=64b=64. The moment arrays contain 596,098 FP64 entries, giving the reported 4.55 MiB.

This also clarifies the timing scope. Appendix C.7 reports run wall time, which includes retrieval evaluation and overhead. Table 1.2 isolates the recorded learner operations within those same runs. Backbone extraction and final-prefix query calibration lie outside this analytic-core measurement. The calibrated discrete pipeline has its own gallery learning and query-fitting costs.

Table 1.2. NUS-WIDE learner time (seconds)

RepeatAccumulationComplete solveLearner total
14.0650.3604.425
23.8400.3874.227
33.9010.3704.271
43.9690.3624.331
54.0960.3344.430

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.