# URECA: The Chain of Two Minimum Set Cover Problems exists behind Adaptation to Shifts in Semantic Code Search

arXiv: https://arxiv.org/abs/2502.07494 · HTML: https://mlsanity.com/paper/2502.07494/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 44 references that are in the map.
- First posted on arXiv 11 Feb 2025.

## Builds on (most cited first, 29 of 29)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [CodeBERT: A Pre-Trained Model for Programming and Natural Languages](https://mlsanity.com/paper/2002.08155/) (2020)
- [CodeT5: Identifier-aware Unified Pre-trained Encoder-Decoder Models for Code Understanding and Generation](https://mlsanity.com/paper/2109.00859/) (2021)
- [InfoGAN: Interpretable Representation Learning by Information Maximizing Generative Adversarial Nets](https://mlsanity.com/paper/1606.03657/) (2016)
- [CodeSearchNet Challenge: Evaluating the State of Semantic Code Search](https://mlsanity.com/paper/1909.09436/) (2019)
- [GraphCodeBERT: Pre-training Code Representations with Data Flow](https://mlsanity.com/paper/2009.08366/) (2020)
- [UniXcoder: Unified Cross-Modal Pre-training for Code Representation](https://mlsanity.com/paper/2203.03850/) (2022)
- [CodeT5+: Open Code Large Language Models for Code Understanding and Generation](https://mlsanity.com/paper/2305.07922/) (2023)
- [Cross-Entropy Loss Functions: Theoretical Analysis and Applications](https://mlsanity.com/paper/2304.07288/) (2023)
- [A Fine-Grained Analysis on Distribution Shift](https://mlsanity.com/paper/2110.11328/) (2021)
- [Learning to Mine Aligned Code and Natural Language Pairs from Stack Overflow](https://mlsanity.com/paper/1805.08949/) (2018)
- [DocPrompting: Generating Code by Retrieving the Docs](https://mlsanity.com/paper/2207.05987/) (2022)
- [Unsupervised Learning of Disentangled Representations from Video](https://mlsanity.com/paper/1705.10915/) (2017)
- [Disentangled Representation Learning](https://mlsanity.com/paper/2211.11695/) (2022)
- [Entropy is not Enough for Test-Time Adaptation: From the Perspective of Disentangled Factors](https://mlsanity.com/paper/2403.07366/) (2024)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [CoSQA: 20,000+ Web Queries for Code Search and Question Answering](https://mlsanity.com/paper/2105.13239/) (2021)
- [When Deep Learning Met Code Search](https://mlsanity.com/paper/1905.03813/) (2019)
- [In-Context Sharpness as Alerts: An Inner Representation Perspective for Hallucination Mitigation](https://mlsanity.com/paper/2403.01548/) (2024)
- [The Entropy Enigma: Success and Failure of Entropy Minimization](https://mlsanity.com/paper/2405.05012/) (2024)
- [CoCoSoDa: Effective Contrastive Learning for Code Search](https://mlsanity.com/paper/2204.03293/) (2022)
- [Rewriting the Code: A Simple Method for Large Language Model Augmented Code Search](https://mlsanity.com/paper/2401.04514/) (2024)
- [DNA-GAN: Learning Disentangled Representations from Multi-Attribute Images](https://mlsanity.com/paper/1711.05415/) (2017)
- [InfoGAN-CR and ModelCentrality: Self-supervised Model Training and Selection for Disentangling GANs](https://mlsanity.com/paper/1906.06034/) (2019)
- [Exploring Distributional Shifts in Large Language Models for Code Analysis](https://mlsanity.com/paper/2303.09128/) (2023)
- [Rethinking Negative Pairs in Code Search](https://mlsanity.com/paper/2310.08069/) (2023)

## Abstract (arXiv)

Adaptation is to make model learn the patterns shifted from the training distribution. In general, this adaptation is formulated as the minimum entropy problem. However, the minimum entropy problem has inherent limitation -- shifted initialization cascade phenomenon. We extend the relationship between the minimum entropy problem and the minimum set cover problem via Lebesgue integral. This extension reveals that internal mechanism of the minimum entropy problem ignores the relationship between disentangled representations, which leads to shifted initialization cascade. From the analysis, we introduce a new clustering algorithm, Union-find based Recursive Clustering Algorithm~(URECA). URECA is an efficient clustering algorithm for the leverage of the relationships between disentangled representations. The update rule of URECA depends on Thresholdly-Updatable Stationary Assumption to dynamics as a released version of Stationary Assumption. This assumption helps URECA to transport disentangled representations with no errors based on the relationships between disentangled representations. URECA also utilize simulation trick to efficiently cluster disentangled representations. The wide range of evaluations show that URECA achieves consistent performance gains for the few-shot adaptation to diverse types of shifts along with advancement to State-of-The-Art performance in CoSQA in the scenario of query shift.