{"id":"5d3643c9-afe6-43fc-af5f-6e7784523308","arxiv_id":"2605.28057","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces (ε,δ)-Recovery Complexity and (ε,ρ)-TTA Learnability with order-wise matching bounds on recovery time for TTA under gradual and abrupt shifts via a discrete surrogate model.","lead":"This paper introduces a theoretical framework for the learnability of test-time adaptation under non-stationary data streams, defining recovery complexity as the time needed to keep excess risk below a target after shifts. It derives matching bounds that highlight fundamental limits and an adaptivity-information trade-off.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Validity of discrete surrogate as faithful model of non-stationary dynamics","rationale":"The reader's weakest_assumption directly identifies the surrogate modeling choice as the load-bearing step; the abstract provides no independent verification (e.g., via continuous-limit analysis or real-data validation) that the surrogate is faithful, so the concern stands as stated. No other internal inconsistency is visible from the given material.","tokens_in":1727,"tokens_out":322,"duration_ms":20826,"concrete_test":"Take the paper's definition of the discrete surrogate (Section on modeling non-stationary streams) and instantiate it alongside a continuous-time counterpart (linear interpolation of distribution parameters between change points) on a simple online mean estimation task; compute empirical recovery steps for both and check whether the observed scaling with shift speed and sample size matches the paper's Θ(·) bounds to within a constant factor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The order-wise matching lower/upper bounds on (ε,δ)-recovery complexity and the claimed adaptivity-information trade-off are derived inside the novel discrete surrogate for test streams. The abstract states this surrogate enables unified tractable analysis of gradual and abrupt shifts, but the central claim requires that the surrogate preserves the essential information constraints and shift rates of real non-stationary processes. If discretization artifacts change the recovery time scaling (e.g., by altering the effective rate of distribution change or the information available per step), the matching bounds and unified learnability guarantees do not transfer.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces the first theoretical framework for the learnability of test-time adaptation (TTA) under non-stationary streams. It defines (ε,δ)-Recovery Complexity as the post-shift time to keep excess risk below a target with high probability, extends it to (ε,ρ)-TTA Learnability for long-term reliability, proposes a novel discrete surrogate for non-stationary test streams to unify analysis of gradual and abrupt shifts, and derives order-wise matching lower and upper bounds on recovery complexity that reveal an adaptivity-information trade-off and provide unified learnability guarantees complementing regret-based analyses.","tokens_in":1851,"tokens_out":545,"duration_ms":29178,"significance":"If the matching bounds hold under a surrogate that faithfully captures information constraints and shift rates, the work would be significant as the first principled learnability theory for TTA, identifying fundamental limits and trade-offs not addressed by regret analyses. The order-wise matching bounds, if rigorously derived with complete proofs, represent a clear strength in providing tight characterizations.","major_comments":[{"comment":"Abstract and the section defining the discrete surrogate: the order-wise matching bounds and adaptivity-information trade-off are derived inside this novel surrogate. The abstract claims it enables unified tractable analysis of gradual and abrupt shifts, but the central claim requires that discretization preserves the essential information constraints and shift rates of real non-stationary processes; without a theorem or explicit argument showing that discretization artifacts do not alter recovery-time scaling, the bounds do not necessarily transfer to practical TTA.","section":"Abstract and surrogate definition section"},{"comment":"The section deriving the lower and upper bounds: the claim of order-wise matching bounds is load-bearing for the fundamental limits and unified guarantees. The abstract states these are derived, but without the full proofs, explicit assumptions on the surrogate, or the definition of the (ε,δ)-Recovery Complexity in the main text, it is not possible to verify whether the math supports the claims or whether modeling choices affect the result.","section":"Bounds derivation section"}],"minor_comments":[{"comment":"Clarify the relationship between (ε,δ)-Recovery Complexity and (ε,ρ)-TTA Learnability with an explicit statement or diagram early in the paper.","section":"Introduction or definitions section"},{"comment":"Ensure all assumptions on the non-stationary streams (e.g., shift rates, information per step) are listed explicitly before the surrogate is introduced.","section":"Preliminaries"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the constructive feedback. We address each major comment below.","responses":[{"response":"The surrogate in Section 3 is constructed to preserve the governing parameters of shift rate and per-step information availability that control recovery scaling. The order-wise bounds are derived directly for this model, which unifies gradual and abrupt cases by design. We will add a proposition in revision that bounds the discretization error on recovery time under standard Lipschitz assumptions on the underlying shift process, confirming that the scaling is unaffected.","revision_made":"yes","referee_comment":"Abstract and the section defining the discrete surrogate: the order-wise matching bounds and adaptivity-information trade-off are derived inside this novel surrogate. The abstract claims it enables unified tractable analysis of gradual and abrupt shifts, but without a theorem or explicit argument showing that discretization artifacts do not alter recovery-time scaling, the bounds do not necessarily transfer to practical TTA."},{"response":"Definition 2.1 in the main text introduces (ε,δ)-Recovery Complexity. Section 3.1 lists the surrogate assumptions. Theorems 4.1 and 4.2 state the matching bounds, with complete proofs in the appendix. We will expand the main-text presentation of the definition and key assumptions for clarity, while retaining the appendix proofs.","revision_made":"partial","referee_comment":"The section deriving the lower and upper bounds: the claim of order-wise matching bounds is load-bearing for the fundamental limits and unified guarantees. The abstract states these are derived, but without the full proofs, explicit assumptions on the surrogate, or the definition of the (ε,δ)-Recovery Complexity in the main text, it is not possible to verify whether the math supports the claims or whether modeling choices affect the result."}],"tokens_in":1428,"tokens_out":392,"duration_ms":38947,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper introduces (ε,δ)-Recovery Complexity to measure how long TTA needs after a shift to keep excess risk low, then extends it to long-term learnability, and derives order-wise matching bounds via a new discrete surrogate for non-stationary streams.\n\nWhat is new is the framework itself: recovery complexity and TTA learnability as quantities that directly target the no-label reliability goal, plus the surrogate that handles gradual and abrupt changes in one analysis. Prior work was mostly regret-based; this tries to give explicit limits on recovery time and an adaptivity-information trade-off. That is a clear step in a direction the field has lacked.\n\nThe work does a solid job of aligning the theory with TTA's actual objective and of producing clean, order-wise tight bounds inside the model. The circularity risk looks low because the quantities are defined from the surrogate rather than reverse-engineered from results.\n\nThe soft spot is the surrogate. The matching bounds and the claimed trade-off live entirely inside this discretization. If the surrogate changes the effective rate of distribution change or the information per step relative to real streams, the limits do not transfer. The abstract states the surrogate enables unified analysis but does not detail how it is built or what assumptions it imposes, so it is hard to judge fidelity from the given text. The proofs are also not visible here, which leaves the exact tightness open.\n\nThis is for readers who work on theoretical foundations of adaptation and online learning. Someone looking for new algorithms or immediate practical guidance will not find much. A serious referee should see it because the gap is real and the structure is substantive enough to evaluate, even if the modeling choice requires close scrutiny in review.","headline":"The paper sets up recovery complexity and a discrete surrogate to bound TTA learnability under shifts, but the surrogate's realism is the part that needs checking.","tokens_in":2326,"tokens_out":420,"would_cite":false,"duration_ms":29657,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Test-time adaptation faces fundamental limits measured by recovery complexity under non-stationary streams.","keywords":["test-time adaptation","non-stationary streams","recovery complexity","learnability","distribution shifts","adaptivity-information trade-off","theoretical framework"],"falsifier":"Empirical recovery times in TTA experiments on streams with known shift types that fall outside the order of the derived upper and lower bounds.","tokens_in":2637,"feed_emoji":"","tokens_out":429,"duration_ms":20783,"temperature":0.7,"pith_summary":"The paper develops a theoretical framework to analyze whether test-time adaptation can reliably maintain performance on streams where the data distribution keeps changing without labels. It defines recovery complexity as the time after a shift until excess risk stays below a target level with high probability, and extends this to long-term TTA learnability. A discrete surrogate model for the streams unifies the study of gradual and abrupt changes. Order-wise matching lower and upper bounds on recovery complexity are derived, exposing fundamental limits and an adaptivity-information trade-off. This provides unified learnability guarantees that complement prior regret-based analyses.","feed_headline":"TTA recovery time after shifts has matching bounds","feed_subtitle":"Order-wise lower and upper bounds on recovery complexity reveal fundamental limits and an adaptivity-information trade-off.","key_machinery":"(ε,δ)-Recovery Complexity, which quantifies the time needed after a distribution shift to maintain low excess risk with high probability, and its extension to TTA learnability.","core_discovery":"The authors introduce (ε,δ)-Recovery Complexity to quantify the post-shift time required to keep excess risk below a target with high probability, extended to (ε,ρ)-TTA Learnability for long-term reliability. Using a novel discrete surrogate for non-stationary streams, they obtain order-wise matching lower and upper bounds on recovery complexity for gradual and abrupt shifts, which demonstrate fundamental limits of TTA and an intrinsic adaptivity-information trade-off, yielding unified learnability guarantees.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Matching bounds on TTA recovery complexity","Recovery complexity bounds for TTA learnability","TTA adaptivity trade-off in matching bounds","Order-wise bounds on post-shift TTA recovery","Fundamental TTA limits via recovery complexity"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The discrete surrogate model for non-stationary test streams preserves the essential dynamics of real distribution shifts.","fun_headline_variants_meta":{"raw":{"variants":["Matching bounds on TTA recovery complexity","Recovery complexity bounds for TTA learnability","TTA adaptivity trade-off in matching bounds","Order-wise bounds on post-shift TTA recovery","Fundamental TTA limits via recovery complexity"]},"model":"grok-4.3","cost_usd":0.003672,"raw_usage":{"total_tokens":1911,"prompt_tokens":669,"num_sources_used":0,"completion_tokens":64,"cost_in_usd_ticks":36724500,"prompt_tokens_details":{"text_tokens":669,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1178,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":669,"tokens_out":64,"duration_ms":12459,"temperature":1.0,"reasoning_tokens":1178,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T13:40:33.909697+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Empirical recovery times in TTA experiments on streams with known shift types that fall outside the order of the derived upper and lower bounds.","supporting_citations":[],"review_version":1}