On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective

• URL: http://arxiv.org/abs/2605.28057v1
• Date: Wed, 27 May 2026 07:04:23 GMT
• Title: On the Learnability of Test-Time Adaptation: A Recovery Complexity Perspective
• Abstract summary: Test-time adaptation (TTA) aims to adapt models to maintain reliable performance on non-stationary test streams without requiring labeled data.<n>Despite its empirical success, the learnability of TTA under non-stationary streams remains unexplored.<n>We propose the first theoretical framework for studying the learnability of TTA and introduce $(,)$-Recovery Complexity and $(,)$-TTA Learnability.
• Score: 25.09429306908567
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Test-time adaptation (TTA) aims to adapt models to maintain reliable performance on non-stationary test streams without requiring labeled data. Despite its empirical success, the learnability of TTA under non-stationary streams remains unexplored. A key challenge is the lack of a principled theoretical framework that simultaneously aligns with the TTA objective and captures both continuously evolving distribution shifts and intrinsic information constraints. To address this gap, we propose the first theoretical framework for studying the learnability of TTA and introduce $(ε,δ)$-Recovery Complexity and $(ε,ρ)$-TTA Learnability. Recovery complexity measures the post-shift time needed to maintain excess risk below a target level with high probability, and is further extended to TTA learnability, which measures the long-term reliability of TTA. Within this framework, we introduce a novel discrete surrogate for non-stationary test streams, enabling a unified and tractable analysis of both gradual and abrupt shifts. We derive order-wise matching lower and upper bounds on recovery complexity, revealing fundamental limits of TTA and an intrinsic adaptivity-information trade-off. These results provide unified learnability guarantees for TTA that complement regret-based analyses.

Related papers

• Fairness-Aware Test-Time Prompt Tuning [4.494887082521271]
  We develop a novel fairness-aware episodic test-time debiasing method called FairTPT.<n>We find that standard episodic TTA generally exacerbates disparities between majority and minority groups.<n>FairTPT outperforms all state-of-the-art episodic test-time debiasing methods and establishes a foundation for robust TTA.
  arXiv  Detail & Related papers  (2026-08-26T12:26:18Z)
• TTSD-FAR: Test-Time Self-Distillation with Fisher-Anchored Restoration for Missing-Modality Emotion Recognition in LVLMs [83.78708832901194]
  Large video-language models (LVLMs) have shown remarkable performance on multimodal tasks like multimodal emotion recognition (ER) in the wild.<n>However, real-world deployment remains challenging: modalities may be missing or noisy at test time.<n>We propose a solution in which a frozen teacher guides an adaptive low-rank student via self-distillation.<n>Experiments on MELD, DFEW, and BAH under 0%-50% missing modalities show that this unified adaptation-restoration design consistently outperforms entropy-based adaptation, RAG, and perplexity-based generation.
  arXiv  Detail & Related papers  (2026-08-18T23:40:28Z)
• Fair Context Learning for Evidence-Balanced Test-Time Adaptation in Vision-Language Models [10.45965859391796]
  Test-Time Adaptation (TTA) aims to improve robustness using only unlabeled test samples.<n>Most prompt-based TTA methods rely on entropy minimization.<n>We propose Fair Context Learning (FCL) that avoids entropy minimization by explicitly addressing shared-evidence bias.
  arXiv  Detail & Related papers  (2026-02-02T16:02:50Z)
• Test-Time Adaptation for Tactile-Vision-Language Models [6.918033886034668]
  Tactile-vision-language (TVL) models are increasingly deployed in real-world robotic and multimodal perception tasks.<n>Existing test-time adaptation methods provide filtering in unimodal settings but lack explicit treatment of modality-wise reliability under cross-modal shifts.<n>We propose a reliability-aware framework that estimates per-modality reliability from prediction uncertainty and perturbation-based responses.
  arXiv  Detail & Related papers  (2026-01-31T02:26:01Z)
• Neutralizing Token Aggregation via Information Augmentation for Efficient Test-Time Adaptation [59.1067331268383]
  Test-Time Adaptation (TTA) has emerged as an effective solution for adapting Vision Transformers (ViT) to distribution shifts without additional training data.<n>To reduce inference cost, plug-and-play token aggregation methods merge redundant tokens in ViTs to reduce total processed tokens.<n>We formalize this problem as Efficient Test-Time Adaptation (ETTA), seeking to preserve the adaptation capability of TTA while reducing inference latency.
  arXiv  Detail & Related papers  (2025-08-05T12:40:55Z)
• Reinforcement Fine-Tuning Naturally Mitigates Forgetting in Continual Post-Training [36.69514399442043]
  This paper presents a comparative analysis of two core post-training paradigms: supervised fine-tuning (SFT) and reinforcement fine-tuning (RFT)<n>Our experiments are conducted on a benchmark comprising seven diverse multimodal tasks.
  arXiv  Detail & Related papers  (2025-07-07T18:17:06Z)
• The Illusion of Progress? A Critical Look at Test-Time Adaptation for Vision-Language Models [86.9724209223541]
  We introduce TTA-VLM, a comprehensive benchmark for evaluating TTA methods on vision-language models (VLMs)<n>Our benchmark implements 8 episodic TTA and 7 online TTA methods within a unified and reproducible framework, and evaluates them across 15 widely used datasets.<n>We find that 1) existing TTA methods produce limited gains compared to the previous pioneering work; 2) current TTA methods exhibit poor collaboration with training-time fine-tuning methods; 3) accuracy gains frequently come at the cost of reduced model trustworthiness.
  arXiv  Detail & Related papers  (2025-06-30T16:05:55Z)
• ConCISE: Confidence-guided Compression in Step-by-step Efficient Reasoning [64.93140713419561]
  Large Reasoning Models (LRMs) perform strongly in complex reasoning tasks via Chain-of-Thought (CoT) prompting, but often suffer from verbose outputs.<n>Existing fine-tuning-based compression methods either operate post-hoc pruning, risking disruption to reasoning coherence, or rely on sampling-based selection.<n>We introduce ConCISE, a framework designed to generate concise reasoning chains, integrating Confidence Injection to boost reasoning confidence, and Early Stopping to terminate reasoning when confidence is sufficient.
  arXiv  Detail & Related papers  (2025-05-08T01:40:40Z)
• Global Convergence of Continual Learning on Non-IID Data [51.99584235667152]
  We provide a general and comprehensive theoretical analysis for continual learning of regression models.<n>We establish the almost sure convergence results of continual learning under a general data condition for the first time.
  arXiv  Detail & Related papers  (2025-03-24T10:06:07Z)
• Active Test-Time Adaptation: Theoretical Analyses and An Algorithm [51.84691955495693]
  Test-time adaptation (TTA) addresses distribution shifts for streaming test data in unsupervised settings. We propose the novel problem setting of active test-time adaptation (ATTA) that integrates active learning within the fully TTA setting.
  arXiv  Detail & Related papers  (2024-04-07T22:31:34Z)
• Persistent Test-time Adaptation in Recurring Testing Scenarios [12.024233973321756]
  Current test-time adaptation (TTA) approaches aim to adapt a machine learning model to environments that change continuously. Yet, it is unclear whether TTA methods can maintain their adaptability over prolonged periods. We propose persistent TTA (PeTTA) which senses when the model is diverging towards collapse and adjusts the adaptation strategy.
  arXiv  Detail & Related papers  (2023-11-30T02:24:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.