acceptodds
Under review as a conference paper at ICLR 2027

Make Every Bit Count: Residual Capacity Reallocation for Unsupervised Cross-Modal Hashing

Abstract

Unsupervised cross-modal hashing (UCMH) maps heterogeneous modalities into compact Hamming spaces for efficient retrieval. However, existing methods typically optimize a fixed-length hash code as a whole, overlooking that individual bits may differ substantially in marginal utility while some cross-modal relations remain insufficiently represented. This leads to capacity misallocation under a fixed hash budget. To address this issue, we propose ReCapHash, a plug-in framework for fixed-budget residual capacity reallocation. ReCapHash first estimates the bidirectional marginal utility of individual hash dimensions and adaptively identifies reclaimable low-utility bits while preserving the remaining dimensions as an informative core. It then contrasts pretrained semantic affinity with the Hamming affinity captured by the retained core to mine unresolved cross-modal relations and organize them into a paired residual graph. Global spectral partitioning and diversity-aware binary recovery transform these relations into complementary residual targets, which are distilled into modality-specific predictors and reallocated to the reclaimed positions. Extensive experiments on MIRFlickr, NUS-WIDE, and IAPR-TC12 demonstrate strong retrieval performance across multiple code lengths and retrieval directions, while consistent improvements over diverse base hashing methods further validate the generality of ReCapHash.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Unsupervised Cross-Modal Hashing, Cross-Modal Retrieval

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_bTUxOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates how to further enhance the retrieval performance of existing cross-modal hashing systems without increasing hash code length or retraining the base models. The authors propose ReCapHash, a plug-in enhancement framework applicable to various base hashing methods. The core idea is to treat existing hash codes as reallocatable coding resources. By evaluating the contribution of individual hash bits, the framework retains important bits and reclaims inefficient ones. It then encodes previously under-represented semantic information into the reclaimed bits by integrating residual relationship mining, binary recovery, and cross-modal distillation. The framework requires no modification to the original hashing models' learning objectives, and the final encoding length remains unchanged. Experimental results demonstrate that ReCapHash achieves strong retrieval performance across multiple public datasets and varying code lengths, and enhances the performance of various existing hashing methods.

Critical strengths

(1) The plug-in design of ReCapHash offers practical value. It improves retrieval performance across different base hashing methods without modifying their original learning objectives, demonstrating good flexibility and applicability.

(2) The capacity reallocation strategy under a fixed bit budget is well conceived. By reusing low-utility hash bits, ReCapHash improves retrieval performance without increasing the original code length or storage overhead, making it practical for large-scale retrieval.

Critical weaknesses

(1) ReCapHash employs a uniform semantic candidate range for different query samples. However, the density of semantic neighborhoods can vary significantly across samples. A fixed number of candidates may result in some queries including weaker semantic relationships while simultaneously limiting the candidate coverage for semantically rich samples.

(2) Samples with fewer connections in the residual relation graph may have insufficient relational information for reliable residual recovery. The paper does not examine how node degree affects recovery quality.

(3) The paper primarily reports overall retrieval performance, offering limited analysis of improvements across queries of varying difficulty. Residual capacity reallocation may yield greater benefits for samples where the baseline hashing model performs poorly, whereas gains for simple queries might be constrained by their already high baseline performance.

(4) ReCapHash constructs the residual relation graph only once during training, which may limit its adaptability to new training data or distribution shifts. The paper does not discuss whether the graph can be updated efficiently in such cases.

Questions for authors
  1. When evaluating the contribution of hash bits, the paper selects candidates ranked immediately after the semantic positive set as negative samples. Why were these relatively similar candidates selected instead of samples with lower similarity?

  2. Since ReCapHash introduces additional residual prediction heads, how much inference-time overhead does it add compared with the original base hashing models?

  3. If ReCapHash is extended to three or more modalities, such as image, text, and audio, how should the residual relationship mining and shared residual graph construction be adjusted?

4 comments
AuthorsOpenReview ↗

Thanks for your review

Dear Reviewer bTUx,

Thank you for your thorough and constructive review. We greatly appreciate your recognition of the practical value and key contributions of ReCapHash. Your feedback provides a valuable opportunity to further clarify our methodology and strengthen its experimental validation. Below, we provide detailed responses and additional experimental evidence.

AuthorsOpenReview ↗

Response to Reviewer bTUx (Weaknesses) [1/2]

W1. Fixed Semantic Candidate Range

Thanks for your suggestion. ReCapHash employs a two-stage selection mechanism. The top-ksk_s semantic candidates define a candidate pool, while only the top-krk_r core-conditioned residual relations are retained, prioritizing semantically supported yet underrepresented relationships. To further evaluate candidate selection, we compare different fixed ranges with density-adaptive selection, whose average candidate budget matches the default ks=128k_s=128.

Table 1: Comparison of semantic candidate selection strategies at 32 bits (mAP@50).

Candidate StrategyMIR I→TMIR T→INUS I→TNUS T→IIAPR I→TIAPR T→I
Fixed ks=64k_s=640.89220.85280.79040.76180.76080.7425
Fixed ks=256k_s=2560.88580.84930.79120.75900.76210.7424
Density-Adaptive0.88620.85300.79210.76230.76040.7425
Fixed ks=128k_s=128 (Ours)0.89770.86260.79530.76320.76310.7497

As shown in Table 1, the default ks=128k_s=128 consistently outperforms both smaller and larger fixed candidate ranges, as well as density-adaptive selection, across all datasets and retrieval directions. These results suggest that a moderate fixed candidate range provides a favorable balance between semantic coverage and noise suppression, without requiring query-specific adaptation.

W2. Effect of Node Degree on Residual Recovery

Thanks for your comment. Appendix C.4 analyzes the structural properties of the residual graphs, with Table 4 showing that all three graphs remain connected, with average degrees of 88.00, 80.17, and 81.36. To further examine recovery reliability, we evaluate the correlation between node degree and residual graph agreement, and compare recovery quality across low- and high-degree nodes.

Table 2: Relationship between node degree and residual recovery quality at 32 bits.

MetricMIRFlickrNUS-WIDEIAPR-TC12
Average Degree88.0080.1781.36
Degree–Recovery Spearman's ρ\rho-0.1399-0.0375-0.0048
Low-Degree Agreement (Bottom 25%)0.86440.84800.8376
High-Degree Agreement (Top 25%)0.85620.83900.8304

Degree–recovery correlations are weak across all three datasets, while low-degree nodes achieve comparable or slightly higher recovery agreement than high-degree nodes. These results indicate that lower graph connectivity is not systematically associated with poorer residual recovery.

W3. Query-Level Improvements Across Different Difficulties

Thanks for your suggestion. To examine query-level improvements, we rank test queries by their AP@50 under the original hashing model and divide them into three equal-sized groups: Hard, Medium, and Easy. The corresponding retrieval gains are reported below.

Table 3: Retrieval improvements across query difficulty levels at 128 bits (ΔmAP@50).

DatasetTaskHardMediumEasy
MIRFlickrI→T+0.1975+0.0896+0.0515
T→I+0.2030+0.0970+0.0613
NUS-WIDEI→T+0.1243+0.0701+0.0357
T→I+0.1206+0.0611+0.0370
IAPR-TC12I→T+0.1108+0.0697+0.0287
T→I+0.1069+0.0619+0.0218

Hard queries consistently achieve the largest retrieval gains across all datasets and directions, demonstrating the effectiveness of ReCapHash on challenging queries.

W4. Incremental Updating of Residual Relations

Thanks for your comment. ReCapHash constructs the residual graph during offline training, but its learned modality-specific predictors can directly encode unseen samples without reconstructing the graph or repeating capacity reallocation. For newly added training data, local graph updates are possible in principle if the reclaimed coordinates remain fixed. Efficient incremental residual recovery and adaptation to distribution shifts remain promising directions for future work.

AuthorsOpenReview ↗

Response to Reviewer bTUx (Questions) [2/2]

Q1. Selection of Hard Negative Samples

Thanks for your feedback. We select candidates immediately following the semantic positive set as informative hard negatives. These candidates are semantically close to the query but lie outside its positive neighborhood, making them more effective for evaluating bit-level ranking discrimination. In contrast, distant negatives are often trivially separable and provide limited information about individual bit contributions. This design enables more discriminative marginal utility estimation.

Q2. Inference-Time Overhead

Thanks for your comment. ReCapHash introduces only lightweight modality-specific residual prediction heads while keeping the original feature encoders and hash learners unchanged. Residual graph construction and spectral recovery are performed offline and introduce no inference-time graph computation. We further measure the encoding latency before and after applying ReCapHash.

Table 4: Inference-time overhead of ReCapHash on MIRFlickr at 32 bits.

Base MethodBase Latency (ms) ↓+ReCapHash (ms) ↓Overhead (%) ↓
HEH0.22960.23150.83
USFTH0.10360.10501.35
ENHash0.20550.20710.78
HINT0.09470.09571.06
UWMCH0.20530.20630.49

ReCapHash introduces only 0.49%–1.35% encoding overhead across five base methods, demonstrating its lightweight inference cost.

Q3. Extension to Multiple Modalities

Thanks for your suggestion. ReCapHash can be naturally extended to multiple aligned modalities. For image, text, and audio, residual relations can be mined across all modality pairs by comparing pretrained semantic affinities with retained-core affinities. These relations can then be aggregated into a shared residual graph, where each aligned multimodal instance forms a node. Global spectral recovery produces shared residual targets, which are distilled into modality-specific prediction heads. This preserves the fixed-budget capacity reallocation principle across multiple modalities.

We hope our additional analyses and experimental results have addressed your concerns and further demonstrated the robustness and practical effectiveness of ReCapHash. We will release the corresponding code and experimental logs to support reproducibility. We sincerely appreciate your consideration and welcome any further feedback.

Sincerely,
The Authors

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

This paper proposes ReCapHash, a plug-in framework for unsupervised cross-modal hashing. It identifies low-utility hash bits, preserves the remaining bits, and replaces the selected bits with complementary information recovered from semantic relations poorly represented by the preserved codes. Experiments on three datasets show retrieval improvements without increasing the code length.

Critical strengths
  1. ReCapHash addresses how to use an existing hash-code budget more effectively. Preserving useful bits and replacing low-utility ones offers a practical way to improve retrieval without increasing storage or changing the base learner.
  2. The evaluation covers three datasets, multiple code lengths, and five base methods. The ablations and appendix analyses also directly examine joint bit removal, residual relation validity, and recovered-bit redundancy. These results support the proposed design.
Critical weaknesses
  1. Although the paper discusses related methods such as VH-ABL, RCMH, and CASH (in related works), the differences are mainly explained conceptually. More targeted comparisons with existing bit selection and code regeneration methods would help clarify the unique contribution of the proposed capacity reallocation strategy.
  2. The paper assumes that differences between pretrained semantic affinity and the retained Hamming affinity indicate missing semantic information. However, these differences may also come from inaccurate semantic similarities produced by the pretrained encoder. The paper does not directly evaluate whether the discovered residual relations are reliable. Further analysis of their semantic correctness would strengthen the motivation.
  3. Although the paper includes several useful ablation studies, it remains unclear whether the improvements mainly come from reallocating low-utility bits or from the additional semantic learning process. For example, refining the original hash codes using the same semantic information may also improve retrieval performance. Comparisons with simple hash-code refinement or residual retraining under similar computational budgets would help demonstrate the necessity of the proposed reallocation strategy.
Questions for authors

Please find the questions or concerns in Critical Weaknesses.

5 comments
AuthorsOpenReview ↗

Thanks for your review

Dear Reviewer t6UH,

Thank you for your thorough and constructive review. We greatly appreciate your recognition of the practical significance of our approach and the comprehensive experimental evaluation. Your feedback provides a valuable opportunity to further clarify the distinctive contributions of ReCapHash and strengthen its empirical validation. Below, we provide detailed responses and additional experimental evidence.

AuthorsOpenReview ↗

Response to Reviewer t6UH [1/3]

W1. Comparison with Existing Bit Selection and Code Regeneration Methods

Thanks for your suggestion. VH-ABL adjusts the effective code length through bit selection, RCMH regenerates hash codes, and CASH allocates capacity for continual retrieval. In contrast, ReCapHash explicitly identifies low-utility bits, preserves the informative core, and reallocates reclaimed positions to semantic relations unexplained by that core, while maintaining the original bit budget. Its key distinction lies in core-conditioned residual capacity reallocation, rather than bit selection or code regeneration alone.

We further compare ReCapHash with existing bit selection and code regeneration methods under compatible evaluation protocols.

Table 1: Comparison with bit selection and code regeneration methods (mAP@50).

TaskMethodMIR-16MIR-32MIR-64MIR-128NUS-16NUS-32NUS-64NUS-128IAPR-16IAPR-32IAPR-64IAPR-128
I→TVH-ABL0.73310.78300.82370.84170.55460.62890.67900.71280.40740.50330.52010.5610
RCMH0.77630.81790.84060.86020.62840.67700.70540.72900.46020.53280.57040.5861
CASH0.76610.80580.83030.85780.62400.67920.71550.73440.44250.51540.56160.5827
ReCapHash0.88710.89770.90440.90510.77190.79530.81520.81310.67640.76310.78630.8042
T→IVH-ABL0.69470.72930.78170.78610.57120.62590.66410.68730.40290.50800.51200.5504
RCMH0.74300.77060.79210.79640.64560.68310.69730.71220.46760.55020.58050.5926
CASH0.71220.74240.76780.78550.61570.66200.66950.69860.43060.51380.55420.5770
ReCapHash0.85100.86260.86340.87010.74040.76320.78130.78810.66740.74970.77720.7902

ReCapHash consistently outperforms all three methods across datasets, code lengths, and retrieval directions, further demonstrating the effectiveness of core-conditioned residual capacity reallocation under a fixed bit budget.

AuthorsOpenReview ↗

Response to Reviewer t6UH [2/3]

W2. Semantic Validity of Residual Relations

Thanks for your comment. We apologize for the lack of clarity in our references to the appendix. Appendix C.1 (Figs. 5–6) directly validates the mined residual relations using ground-truth semantic labels exclusively for evaluation. Our residual relations achieve 82.5% semantic hit rates in both retrieval directions, substantially outperforming Random (55.6%/55.7%) and Core-failed mining (35.9%/37.8%). Moreover, their retained-core affinities are markedly lower than those of semantic nearest neighbors (0.567 vs. 0.732 for I→T and 0.573 vs. 0.727 for T→I). These results provide direct evidence that the mined relations are semantically reliable and complementary to the preserved core, rather than merely reflecting inaccurate pretrained similarities.

Reviewer_5DaUOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper proposes an unsupervised cross-modal hashing framework ReCapHash for efficient retrieval, which aims to address the problem of uneven contribution of different bits in existing hashing methods, and the capacity misallocation under a fixed bit budget. ReCapHash first recognize low-utility bits by bidirectional marginal utility evaluation, adaptive reclaim them while preserving high-utility bits. Then it mines insufficiently encoded cross-modal relationships by comparing pretrained semantic similarities with the Hamming similarities of the preserved core bits, constructing a residual relationship graph. The method further combines global spectral recovery with diversity-aware binary optimization to generate complementary residual hashing targets, redistributing them to the inefficient hash bits through cross-modal distillation. Extensive experiments across multiple benchmark datasets demonstrate the effectiveness and superior performance of ReCapHash.

Critical strengths
  1. The motivation is clear as this paper accurately identify a key issue in unsupervised cross-modal hashing: the uneven contribution of different hash bits leads to underutilization of the fixed bit budget, making it difficult to sufficiently represent certain important relationships.
  2. Constructing a core-conditioned residual relation graph to mine semantic relationships that are not sufficiently represented by existing hash codes is an interesting design. This helps reduce redundant encoding of existing semantic information and makes better use of the reclaimed hash capacity.
Critical weaknesses
  1. The mining of residual relations relies on semantic similarity derived from pretrained features and may be affected by semantic noise or inaccurate neighbor relations.
  2. The row-wise normalization in Eq. (7) may amplify small similarity differences for queries with highly concentrated similarity distributions, making the residual relation scores sensitive to local fluctuations.
  3. Eq. (9) applies a fixed reciprocity enhancement regardless of the strength of reverse support. This may affect the reliability of the residual relation graph.
  4. Eq. (12) converts the continuous spectrum representation into binary residual targets, whereas Eq. (16) applies uniform supervision weights to all binary targets. For samples where the values approach zero after rotation, the binary signs may be sensitive to minute perturbations, but the distillation process does not distinguish between these uncertain targets and high-confidence ones.
Questions for authors
  1. How are kpk_p, knk_n, and ksk_s determined when constructing the sets of semantic positive/negative samples and candidate residual relations? Since semantic neighborhood density may vary across datasets, do these parameters need to be adjusted based on the specific characteristics of the dataset?

  2. The residual relation graph in ReCapHash is constructed once during the training phase. If new training data is added later, is it possible to update only a portion of the residual relations without re-executing the entire capacity reallocation process?

5 comments
AuthorsOpenReview ↗

Thanks for your review

Dear Reviewer 5DaU,

Thank you for your thorough and constructive review. We greatly appreciate your recognition of the motivation and key contributions of our work. Your feedback provides a valuable opportunity to further clarify our methodology and strengthen its empirical validation. Below, we provide detailed responses and additional experimental evidence.

AuthorsOpenReview ↗

Response to Reviewer 5DaU (Weaknesses) [1/2]

W1. Reliability of Pretrained Semantic Relations

Thanks for your comment. We apologize for the lack of clarity in our references to the appendix. Appendix C.1 evaluates the semantic validity of mined residual relations. As shown in Fig. 5, our residual relations achieve 82.5% ground-truth semantic hit rate in both retrieval directions, compared with 89.8%/89.0% for semantic nearest neighbors. Meanwhile, their lower retained-core affinities (0.567/0.573 versus 0.732/0.727) confirm that they capture complementary rather than redundant relations.

To further assess robustness to imperfect semantic similarities, we evaluate ReCapHash under increasing semantic noise levels.

Table 1: Robustness to semantic similarity noise at 32 bits (mAP@50).

Noise LevelMIR I→TMIR T→INUS I→TNUS T→IIAPR I→TIAPR T→I
Clean0.89770.86260.79530.76320.76310.7497
5%0.88860.85350.79220.76270.75630.7463
10%0.88950.85370.79130.76130.75810.7470
20%0.88820.85280.78960.75880.75870.7479

ReCapHash maintains stable retrieval performance even under 20% semantic noise across all three datasets and both retrieval directions, demonstrating its robustness to imperfect pretrained semantic similarities.

W2. Stability of Row-Wise Normalization

Thanks for your comment. Row-wise normalization in Eq. (7) aligns the query-dependent scales of semantic and Hamming affinities. To assess its robustness, we compare the original Z-score with variance-floored and robust normalization across three datasets.

Table 2: Comparison of normalization strategies at 32 bits (mAP@50).

TaskNormalizationMIRFlickrNUS-WIDEIAPR-TC12
I→TVariance-Floored0.88820.78060.7504
Robust Normalization0.88960.78130.7555
Original Z-score (Ours)0.89770.79530.7631
T→IVariance-Floored0.85680.75180.7360
Robust Normalization0.85520.75090.7385
Original Z-score (Ours)0.86260.76320.7497

The original Z-score consistently outperforms both alternatives across all datasets and retrieval directions. These results indicate that normalization strategies designed to mitigate sensitivity to small similarity fluctuations do not improve retrieval performance over our original design.

W3. Fixed Reciprocity Enhancement

Thanks for your comment. Although Eq. (9) uses a fixed reciprocity multiplier, the enhancement is applied to the underlying directional evidence rather than assigning uniform edge weights. Combining Eqs. (9) and (10), reciprocal relations satisfy

Wij=1+β2(Aij+Aji)W_{ij} = \frac{1+\beta}{2}(A_{ij}+A_{ji})

before graph sparsification. Thus, the reciprocity indicator captures mutual structural support, while the edge weight retains the magnitude of bidirectional evidence. Importantly, weakly supported relations remain distinguishable from strongly supported ones and are further filtered by top-kgk_g sparsification. Moreover, Fig. 4 demonstrates stable retrieval performance across different values of β\beta, supporting the robustness of this design. We will clarify this distinction.

W4. Reliability of Binary Residual Targets

Thanks for your comment. Eq. (12) employs iterative quantization with optimized orthogonal rotations to minimize quantization error, while Eq. (15) further selects residual codes by jointly considering graph fidelity and inter-bit diversity. These designs promote reliable and complementary binary targets before distillation. To further validate the effectiveness of uniform supervision, we compare it with margin-weighted and confidence-filtered distillation under identical settings.

Table 3: Comparison of residual distillation strategies at 32 bits (mAP@50).

TaskStrategyMIRFlickrNUS-WIDEIAPR-TC12
I→TConfidence-Filtered0.88570.78560.7543
Margin-Weighted0.88860.78650.7567
Uniform (Ours)0.89770.79530.7631
T→IConfidence-Filtered0.85230.75330.7367
Margin-Weighted0.85400.75770.7375
Uniform (Ours)0.86260.76320.7497

Uniform supervision consistently outperforms both margin-weighted and confidence-filtered alternatives across all datasets and retrieval directions. These results indicate that explicitly down-weighting or filtering uncertain binary targets does not improve retrieval performance over uniform supervision in our evaluated settings.

AuthorsOpenReview ↗

Response to Reviewer 5DaU (Questions) [2/2]

Q1. Selection of kpk_p, knk_n, and ksk_s

Thanks for your feedback. We consistently set kp=32k_p=32, kn=4k_n=4, and ks=128k_s=128 across all three datasets without dataset-specific tuning. Specifically, kpk_p balances positive-neighbor coverage and semantic reliability, knk_n focuses utility estimation on informative hard negatives, and ksk_s provides sufficient candidates for residual mining while limiting semantic noise. The consistent retrieval performance across three datasets supports the effectiveness of these shared settings.

Q2. Incremental Updating of Residual Relations

Thanks for your suggestion. ReCapHash constructs the residual graph during offline training, but its learned modality-specific predictors can directly encode unseen samples without reconstructing the graph or repeating capacity reallocation. For newly added training data, local graph updates are possible in principle if the reclaimed coordinates remain fixed. Building on this design, efficient incremental residual recovery represents a promising direction for future work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.