PaperlayerView exact revision on arXiv

Source-linked AI summary

Provenance Guided Incremental Learning Under Evolving Concept Definitions

Ismail Lamaakal

arXiv:2608.23893v1cs.AIcs.LG

TL;DR

The paper addresses learning systems whose target-defining rules change explicitly, making some historical labels obsolete without changing the underlying records. It proposes provenance-guided rule differencing, selective relabeling, and incremental predictor repair, achieving comparable predictive quality with substantially less reprocessing and latency. The framework also preserves stable knowledge and supports recurring concept definitions through versioned memory.

  • Problem

    The research gap is how to update historical supervision and predictive state after an explicit target-rule revision without inferring the change from errors or recomputing the entire collection.

  • Method

    The framework compiles consecutive concept definitions into rule deltas, traces changed dependencies through provenance, certifies stable records, selectively relabels or annotates affected records, and incrementally repairs the predictor.

  • Results

    Across RuleShift-Bench, Provenance-Guided Repair achieves 92.3% accuracy and 90.2% Macro-F1 while reprocessing 14.7% of historical data and reducing average latency from 993 s to 179 s.

  • Takeaways & Limitations

    Explicit concept revisions can serve as data-maintenance signals for updating dependent supervision and predictive state while preserving knowledge certified as valid.

Abstract

from arXiv · show

Learning systems deployed over long periods must adapt not only to statistical changes in incoming data, but also to revisions of the definitions that generate their prediction targets. Conventional concept-drift methods typically infer such changes from observations or prediction errors, even when the underlying policy, rule, or query has been explicitly modified. This paper studies rule-induced concept shift, where the target-defining concept is revised directly, causing previously stored instances to acquire different semantic labels without requiring any change in their observed data. We introduce a provenance-guided incremental learning framework that compiles consecutive concept definitions into a structured rule delta, traces the changed components through historical provenance, certifies records whose previous labels remain valid, and restricts reevaluation to a localized candidate region. Executable revisions are relabeled automatically, ambiguous cases are handled through selective supervision, and the resulting changes are used for incremental predictor repair. A versioned concept memory further supports recurring definitions. We also introduce RuleShift-Bench, spanning financial, demographic, cybersecurity, and graph-structured data with threshold, predicate, logical, relational, recurring, and mixed concept revisions. Across the benchmark, provenance-guided repair attains 92.3% accuracy and 90.2% Macro-F1 while reprocessing 14.7% of the historical collection and retaining 94.6% of affected records. Its average update latency is 179s compared with 993s for complete relabeling and retraining. The results demonstrate that an explicit concept revision can be exploited as a data-maintenance signal, allowing learning systems to update the supervision and predictive state that depend on the change while preserving knowledge that remains valid.

I. INTRODUCTION

The paper frames explicit revisions to target-defining rules as a distinct form of concept shift and asks how systems can update historical supervision without rediscovering or recomputing everything. It proposes combining rule differencing, provenance-guided localization, selective supervision, and incremental model repair.

  • Problem Setting: Conventional concept-drift methods usually infer changes from observations, prediction errors, class frequencies, or distributional shifts rather than from a directly revised target rule.The paper distinguishes hidden statistical change from explicit policy, query, compliance, relational, or graph-rule revisions.
  • Learning Under Evolving Concept Definitions: Rule-induced concept shift occurs when an explicit target-generating definition changes, even though stored records and their distributions remain unchanged.A historical instance can therefore receive a different correct label solely because the rule used to interpret it was revised.
  • Problem Setting: A known revision still does not reveal which historical examples became invalid, because different records may depend on different predicates, branches, relations, or graph paths.The paper treats localization as reasoning from the modified target computation and record-level dependencies.
  • Motivation: Full historical relabeling and retraining can be unnecessarily expensive when concept evaluation involves joins, graph dependencies, aggregates, external services, or other costly operations.The paper formulates the task as updating supervision and predictive state while minimizing unnecessary reevaluation.
  • Proposed Framework: The proposed framework compiles consecutive definitions into a structural rule delta, traces changed dependencies through provenance, selectively updates supervision, and incrementally repairs the predictor.Stable records are preserved, relevant records are reconsidered, and ambiguous cases can receive selective human annotation.

A. Learning Under Evolving Concept Definitions

The paper defines rule-induced concept shift as an explicit change from Q_t to Q_t+1 in the program that assigns targets. It represents these programs structurally, compiles their differences, and uses provenance to localize historical reevaluation.

  • Concept Definition: A concept program Q_t maps complete entity information z_i to the target y_i and may include thresholds, Boolean conditions, relational operations, or graph-path constraints.The complete information space can include relational, temporal, graph, external, or expert-provided information.
  • Information Setting: The framework distinguishes complete information z_i from prediction-time representation x_i because concept evaluation may require costly or unavailable joins, historical windows, external services, graph traversal, or manual verification.This distinction separates target construction from deployed prediction inputs.
  • Rule-Induced Shift: Rule-induced concept shift changes the target-generating concept from Q_t to Q_t+1 without requiring changes to records, prediction-time features, or their distributions.The same historical instance may acquire a different correct target under the revised interpretation.
  • Rule Representation: Each concept is represented as a canonical predicate directed acyclic graph whose nodes encode atomic, threshold, logical, relational, and graph-path computations.The graph preserves internal structure that would be hidden if Q_t and Q_t+1 were treated as opaque functions.
  • Rule Differencing: The rule-delta compiler aligns persistent components and records changed predicates, operators, parameters, or relational dependencies using typed edit categories.Threshold, insertion, deletion, logical, and relational or graph-path rewrites can induce different affected-record patterns.
  • Historical Localization: Provenance analysis combines changed dependencies with dependency closure to separate certified stable records from candidates whose previous evaluations may depend on altered components.Only candidates are reevaluated, while provenance eliminates records whose outputs can be proven invariant.

D. Exact and Ambiguous Concept Changes

The framework divides potentially affected records according to whether revised targets are executable, ambiguous, or stable, then uses the resulting supervision to repair the predictor while preserving certified behavior. Its repair objective is predictor agnostic and balances revision against stability.

  • Exact and Ambiguous Changes: Fully executable revisions produce deterministic revised targets that can be relabeled automatically, whereas unresolved revisions require additional supervision.Ambiguity can result from missing, delayed, uncertain, external, or expert-interpreted information.
  • Exact and Ambiguous Changes: Ambiguous cases are handled through selective annotation that prioritizes uncertainty and representativeness rather than labeling the entire ambiguous region.This concentrates human supervision where it provides the greatest information.
  • Exact and Ambiguous Changes: The decomposition reduces computational and supervision cost by automating exact revisions and restricting annotation to the ambiguous concept-delta region.The strategy avoids assuming that every revised concept is fully machine-executable.
  • Incremental Predictor Repair: The repair dataset contains deterministically revised and selectively annotated examples, while a stable subset preserves behavior on certified unchanged regions.Stable examples are not used to teach new semantics; they provide targeted preservation of valid prior behavior.
  • Incremental Predictor Repair: The predictor is updated with L = L_repair + λL_stable, where L_repair fits revised targets and L_stable constrains behavior on stable records.The scalar λ ≥ 0 controls the strength of preservation relative to revision.
  • Incremental Predictor Repair: The repair mechanism is predictor agnostic and can be instantiated with gradient boosting, neural tabular, or online decision-tree models.The framework’s contribution lies in concept-evolution maintenance and targeted updating rather than a task-specific backbone.

F. Versioned Concept Memory

Versioned concept memory records prior definitions, provenance state, affected-data information, and model states so recurring concepts can reuse earlier computation. The framework also establishes exact changed-label recovery when definitions are executable and stable-record certification is sound.

  • Versioned Concept Memory: Concept history stores each definition, predicate graph, provenance or index state, affected-data information, and adapted model state.This creates a compact record of concept evolution and model adaptation.
  • Versioned Concept Memory: Versioned memory supports auditing, reproducibility, rollback, reuse of structural knowledge, and recovery of recurring concept definitions.Previously built predicate graphs and provenance indices can reduce the cost of analyzing later updates.
  • Recurring Concepts: When a sequence returns from Q1 through Q2 and Q3 to Q1, the system can retrieve the earlier memory item and reuse its graph, provenance summaries, affected-data patterns, and model state.The recurring definition is not treated as completely unseen.
  • Exactness: When both concept versions are executable, changed-label membership is determined directly by disagreement between Q_t and Q_t+1 rather than by statistical estimation.This follows from the explicit concept definitions and the affected-set formulation.
  • Exactness: For deterministic executable definitions, evaluating both concept versions only on the candidate set recovers the same changed-label set as evaluating them over the full historical collection, provided stable certification is sound.The candidate restriction reduces computation without altering changed-target recovery.
  • Exactness: Provenance eliminates records whose outputs are provably invariant, rather than assigning heuristic drift scores to historical examples.Exact execution of the changed concept portions is reserved for remaining candidates.

B. Provenance Stability Certificate

The provenance stability certificate identifies records whose concept assignments are invariant under an explicit rule revision. It uses effective changed components, blocking nodes, and provenance paths to safely preserve unaffected records while sending uncertified cases to reevaluation.

  • B. Provenance Stability Certificate: A changed component can affect the final concept only if its influence propagates through an uninterrupted path to the root.An unchanged false input blocks an AND node, while an unchanged true input blocks an OR node.
  • B. Provenance Stability Certificate: Threshold revisions enter the effective changed set only when a record lies where old and revised evaluations can disagree.A changed component producing the same local result cannot alone alter the final concept output.
  • B. Provenance Stability Certificate: Theorem 1 certifies a record as invariant when every path from each effective changed component to the output contains a persistent blocking node.The decisive input at that blocking node remains unchanged under the revision.
  • B. Provenance Stability Certificate: Uncertified records remain candidates for selective reevaluation because failure to prove invariance does not imply that their targets changed.The certificate is conservative and establishes sufficient conditions for unaffectedness rather than estimating likelihood.
  • B. Provenance Stability Certificate: Provenance pruning preserves exact affected-set recovery by keeping every record with a changed label in the candidate region for revised-concept evaluation.Candidate evaluation recovers the changed-label set without executing the complete revised concept program.

C. Incremental Processing Complexity

Incremental concept maintenance replaces full historical recomputation with rule-delta compilation, provenance-based candidate discovery, localized reevaluation, and predictor repair. Its advantage is greatest for localized revisions and selective provenance indexes, but diminishes when nearly all records are candidates.

  • C. Incremental Processing Complexity: Full recomputation requires O(NCQ) concept-evaluation work before retraining, especially costly for joins, aggregates, external lookups, and multi-hop graph operations.Here N is the historical-record count and CQ is the average cost of the complete revised concept program per record.
  • C. Incremental Processing Complexity: Incremental maintenance costs O(C∆Q + Cprov + |Dcand_t|C∆) before adding predictor-repair and provenance-index maintenance costs.The total update cost is O(C∆Q + Cprov + |Dcand_t|C∆ + Crepair + Cindex), versus approximately O(NCQ + Cfull_train) for full relabeling and retraining.
  • C. Incremental Processing Complexity: An inverted provenance index retrieves postings for changed components, making lookup work proportional to changed-component postings rather than necessarily the complete database.The stated lookup cost is approximately O(|C_t| + Σ_c∈C_t |I_t(c)|), excluding duplicate elimination and index-maintenance overhead.
  • C. Incremental Processing Complexity: The largest computational advantage is expected when revisions are localized, provenance is selective, and changed-fragment evaluation is cheaper than complete concept execution.The record-level recomputation ratio is approximately ρ_t C∆/CQ.
  • C. Incremental Processing Complexity: When nearly every record depends on changed predicates and C∆≈CQ, selective maintenance approaches full-recomputation cost.This is an operating limit rather than a pathological failure, because selective maintenance benefits from localized semantic change.
  • C. Incremental Processing Complexity: RuleShift-Bench spans financial, demographic, cybersecurity, and graph-structured data with seven controlled revision protocols after an initial concept definition.The protocols include threshold, predicate, logical, relational or graph-path, recurring, and mixed concept–distribution changes.

B. Experimental Setup

The experiments compare provenance-guided repair with complete, windowed, online, replay, random, uncertainty-based, provenance-plus-full-retraining, and oracle strategies across four data families. Results show near-complete-recomputation predictive quality with substantially lower update cost and concentrated affected-record coverage.

  • B. Experimental Setup: The comparison includes complete relabeling and retraining, sliding-window, online, replay, random, uncertainty, provenance-selection with full retraining, and oracle affected-set strategies.These baselines separate candidate discovery from the contribution of incremental predictor repair.
  • B. Experimental Setup: The evaluation measures predictive performance, affected-record efficiency, and model-family robustness across RuleShift-Bench’s financial, demographic, cybersecurity, and graph datasets.Experiments use controlled concept-rule revisions and, unless otherwise stated, three random seeds with mean±standard deviation reporting.
  • B. Experimental Setup: 92.3% accuracy and 90.2% Macro-F1 remain within 0.5 percentage points of Full Relabel + Retrain while processing 14.7% of historical records.The method also retains 94.6% of affected records, compared with 79.0% for Uncertainty Reevaluation and 71.1% for Random Reevaluation.
  • B. Experimental Setup: 179 s versus 993 s reduces average update latency by approximately 5.5× relative to complete relabeling and retraining.Provenance Selection + Full Retraining identifies the same candidate region but takes 515 s, isolating the benefit of incremental repair.
  • B. Experimental Setup: Across all four data families, predictive differences from complete recomputation remain small while update-cost reductions are substantially larger.Dataset-level latency falls from 1775 s to 181 s on PaySim, 154 s to 28 s on Census-Income, 903 s to 148 s on UNSW-NB15, and 742 s to 121 s on ogbn-arxiv.
  • B. Experimental Setup: The largest latency reduction is approximately 9.8× on PaySim, while UNSW-NB15 and ogbn-arxiv each obtain approximately 6.1×.The graph benchmark remains relatively costly because relational and path-based concept evaluation requires additional structural processing.
  • B. Experimental Setup: Provenance-Guided Repair achieves 94.6% affected recall at a 14.7% reprocessing budget, outperforming random and uncertainty selection at the same budget.Full recomputation covers all affected records by processing the entire database, whereas provenance-based selection concentrates computation on dependency-relevant records.

F. Annotation Efficiency and Recurring Concepts

Under limited supervision, selecting annotations within the ambiguous concept-delta region improves efficiency, while versioned memory supports accurate and faster recovery when definitions recur. Ablations show that provenance, stability certification, and incremental repair determine the framework’s processing and update costs.

  • Annotation efficiency: 78.6% Macro-F1 with one annotation rises to 89.2% at B = 32 under delta-constrained uncertainty, outperforming global uncertainty and random sampling.The corresponding baselines are 75.2% and 72.4% with one annotation, and 85.8% and 83.5% at B = 32.
  • Recurring concepts: 90.6% accuracy on returning Q1 is close to its 91.5% first occurrence, with Versioned Repair reducing recovery latency to 146 s and reprocessing to 12.6%.Replay reaches 88.7%, with a 2.5-point recovery gap, 315 s latency, and an 18.0% reprocessed fraction.
  • Ablations: Removing the rule-delta compiler lowers Macro-F1 from 90.2% to 89.3% and affected recall from 94.6% to 88.1%, while more than doubling historical reprocessing.The compiler narrows the update region by extracting structural differences between consecutive concept definitions.
  • Ablations: Without provenance, affected recall reaches 100.0% but reprocessed data and update latency rise to 100.0% and 862 s, respectively.The ablation effectively revisits the entire historical collection instead of identifying records connected to revised rule components.
  • Ablations: Without stability certification, reprocessing increases from 14.7% to 38.9%, while removing ambiguous-region selection reduces Macro-F1 to 88.7% and affected recall to 92.0%.Certification excludes stable records; region selection directs supervision and reevaluation toward unresolved cases.
  • Ablations: Removing versioned memory raises reprocessed data to 24.6% and latency to 268 s, whereas removing incremental repair raises latency from 179 s to 515 s without changing the selected region.These results separate the efficiency benefits of reusing prior concept states from those of selective predictor repair.

APPENDIX A THEORETICAL ANALYSIS AND ALGORITHMIC DETAILS

The appendix formalizes executable concept definitions as canonical Boolean programs and compiles their consecutive versions into typed structural deltas. It establishes the representations and assumptions needed for provenance-guided maintenance.

  • Theoretical Foundations: The framework analyzes deterministic, executable concept programs evaluated over a fixed historical snapshot.Uncertain relational evidence, external knowledge, and expert interpretation are handled outside the exact guarantees.
  • Executable Concept Language: Concept definitions are represented as Boolean programs built from primitive predicates, negation, and logical conjunction.The primitive predicates may depend on attributes, relational data, or graph structure.
  • Executable Concept Language: Threshold parameters are modeled separately so revisions from γ_t to γ_t+1 preserve predicate identity instead of appearing as deletion and insertion.This representation directly exposes threshold changes as parameter revisions.
  • Canonicalization and Rule Deltas: Canonical predicate DAGs normalize equivalent expressions before comparison, aligning unchanged components across consecutive concept definitions.Associative operators are flattened, commutative children ordered deterministically, and structural signatures support efficient alignment.
  • Canonicalization and Rule Deltas: The typed rule delta records persistent, modified, inserted, and removed components, while conservative extra edits are acceptable because they only enlarge later examination.The compiler distinguishes threshold, predicate, logical, relational, and graph-path revisions.

E. Record-Level Provenance and Candidate Retrieval

Record-level maintenance connects structural rule changes to historical provenance and evaluates only records that may be affected. Conservative local analysis uses Boolean context to certify additional stable records.

  • Provenance and Retrieval: Historical provenance records predicate, operator, value, and source dependencies needed to connect changed computations to affected records.Source dependencies may include relational tuples, graph nodes, edges, or path signatures, and need not be minimal.
  • Provenance and Retrieval: An inverted provenance index retrieves records associated with an affected frontier of persistent components surrounding the revision.Inserted components use changed persistent ancestors or evaluation-context frontiers because they have no historical postings.
  • Local Change Analysis: Record-specific effective-change sets conservatively retain components whose local revised behavior could alter the computation.Threshold, logical, relational, and graph changes are pruned only when local invariance is established.
  • Stability Certification: Unchanged controlling inputs at persistent AND or OR nodes can block differences from propagating toward the concept output.False controls AND, true controls OR, while NOT transmits child differences rather than blocking them.
  • Stability Certification: If the final concept output changes, an effective changed component must connect to it through a dependency path without a persistent blocking node.This unblocked-difference property underlies the later stability certificate.

J. Complete Proof of the Provenance Stability Certificate

The proof establishes that persistent blocking nodes certify unchanged historical targets by preventing effective rule differences from reaching the concept output. The resulting procedure conservatively separates stable records from candidates.

  • Stability Certificate: A record is certified stable when every path from an effective changed component to the concept output contains a persistent blocking node.The blocking node has an unchanged controlling input that fixes its output independently of the changed branch.
  • Graph-Separation Interpretation: The certificate has a graph-separation interpretation: blocking nodes form a vertex cut between effective sources of semantic difference and the output.This interpretation supports upward traversal that stops when a blocking node is encountered.
  • Algorithmic Behavior: The certification algorithm returns only stable or not-certified, with failure to certify meaning that exclusion conditions were not established.Missing provenance, ambiguous alignment, and unavailable witnesses conservatively leave records in the candidate region.
  • Candidate Discovery: Candidate discovery combines dependency-complete frontier retrieval with individual record certification to exploit Boolean context beyond posting-list membership.Records outside a complete affected frontier can be excluded directly.
  • Guarantee Conditions: The guarantees require a fixed snapshot, deterministic executability, change-complete deltas, dependency-complete retrieval, sound witnesses, and conservative effective-change construction.These conditions define the boundary of the exact correctness result.

7 Initialize Dcand

The final analysis shows that conservative certification and candidate-only reevaluation recover the exact changed-label set under the stated conditions. Unresolved candidates are separated for deterministic relabeling or selective supervision.

  • Record Partitioning: 11 add zi to Dsafe and 13 add zi to Dcand implement the algorithm’s stable-versus-candidate partition.The procedure returns both regions after record-level certification.
  • Assumptions and Guarantees: The exact guarantees rely on conservative uncertainty handling: unresolved relations, missing provenance, and ambiguous semantics remain candidates rather than being treated as stable.This prevents uncertainty from causing erroneous stable-set exclusions.
  • Exact Recovery: Candidate over-approximation increases computation but cannot lose affected records when the stable set is sound.False-positive candidates are acceptable because they are reevaluated rather than excluded.
  • Exact Recovery: Candidate-only reevaluation recovers exactly the changed-label set obtained by evaluating the complete historical collection.The result follows when every truly affected record remains in the candidate region and stable records are soundly excluded.
  • Exact Recovery: Under Conditions C1–C7, exact reevaluation of the candidate region recovers the complete changed-label set.The corollary combines sound stability certification with candidate completeness.
  • Unresolved Candidates: Executable candidates are relabeled exactly, while unresolved candidates undergo annotation selection without assuming that every unresolved record is affected.This avoids circularly requesting supervision only after knowing the revised label.

R. Complete Incremental Maintenance Algorithm

Algorithm 4 separates concept analysis, historical-data maintenance, semantic resolution, predictor repair, and version-state maintenance. It localizes reevaluation through rule deltas and provenance, then incrementally updates the predictor and stored maintenance state.

  • Maintenance pipeline: The procedure compiles consecutive concepts into canonical graphs, computes a typed rule delta, and constructs the affected provenance frontier.It then derives stable and candidate record sets from that frontier.
  • Maintenance pipeline: Stable records are certified, while candidate records are evaluated under the revised concept and partitioned into exact repairs and unresolved cases.Ambiguous candidates are selected for revised supervision within annotation budget B.
  • Predictor repair: The algorithm constructs revised labeled and repair sets before incrementally repairing the predictor with the repair set and stability buffer.This separates semantic relabeling from model adaptation.
  • Version maintenance: After repair, it updates provenance and indexes and stores the revised rule, graph, provenance, affected-data, and predictor states in versioned concept memory.The output is an updated predictor and maintenance state.
  • Cost decomposition: The maintenance cost combines rule processing, provenance retrieval and certification, candidate reevaluation, predictor repair, and index maintenance.The incremental end-to-end cost is Tinc = O (C∆Q + Cprov + KtC∆ + Crepair + Cindex).
  • Cost decomposition: The complete incremental cost is Tinc = O (C∆Q + Cprov + KtC∆ + Crepair + Cindex), contrasting candidate-local work with complete retraining costs.The decomposition distinguishes structural, data-maintenance, model-update, and indexing terms.

T. Complete Proof of the Incremental Advantage

The proof establishes that certified provenance-guided maintenance can be asymptotically smaller than complete historical recomputation when candidate, provenance, and overhead terms remain sufficiently localized. Its practical advantage is therefore governed by both the affected fraction and the cost of executing the changed fragment.

  • Proof setup: The proof compares complete recomputation over N records with rule compilation, provenance processing, candidate-only evaluation, index maintenance, and incremental repair.Predictor-specific optimization is excluded from the formal asymptotic proposition because model families have different update complexities.
  • Asymptotic argument: Under the proposition’s assumptions, normalized rule, provenance, candidate, and index terms converge to zero relative to complete concept recomputation.The proof derives these limits through nonnegative-cost bounds and the squeeze theorem.
  • Conclusion: The concept-recomputation component is asymptotically smaller than complete historical concept recomputation under the stated assumptions.This conclusion follows after showing every normalized term vanishes.
  • Efficiency determinants: The dominant record-level ratio depends on candidate fraction ρt and changed-fragment cost relative to full concept cost.Ignoring fixed structural and indexing overhead, savings arise from reducing both the number of evaluated records and the work per candidate.
  • Operating limit: When revisions are global or the changed fragment costs as much as the complete concept, selective maintenance approaches full recomputation without losing correctness.The limitation reflects little exploitable locality rather than a correctness failure.
  • Relational and graph concepts: Relational and graph predicates can be localized through Boolean invariance and provenance, allowing expensive reevaluation to be skipped when affected outputs are already certified stable.Graph provenance identifies nodes, edges, relation types, or path signatures relevant to propagation.
  • Recurring concepts: Recurring definitions permit reuse of canonical rule graphs and prior predictor states, but data-dependent provenance and model validity still require checks after data changes.Valid state combines reusable historical provenance with newly constructed provenance for changed or new data.

X. Scope of the Formal Guarantees

The formal guarantees are exact only under certified dependency conditions, while experiments show strong retention and efficiency when revisions remain localized. The analysis also identifies trade-offs across predictor families, recurring concepts, storage, repair parameters, provenance granularity, and stress conditions.

  • X. Scope of the Formal Guarantees: Under Conditions C1–C7, certified invariance yields a sound stable set and exact affected-set recovery.These are formal guarantees of the certified operating mode.
  • X. Scope of the Formal Guarantees: Approximate provenance or dependency reconstruction makes affected-set recall empirical rather than mathematically guaranteed.Omitted relevant dependencies may violate the theorem’s sufficient conditions.
  • X. Scope of the Formal Guarantees: The computational advantage is substantial when the candidate region is small relative to the historical collection.This links correctness-preserving localization to efficiency.
  • A. Robustness Across Predictor Families: Across predictor families, repaired models retain approximately 99% or more of complete-retraining Macro-F1, while update-time reductions range from about 2.8× to 6.2×.XGBoost has the strongest speedups; the Hoeffding Adaptive Tree has smaller gains but remains close in predictive performance.
  • B. Long-Horizon Recurring Concept Sequences: Versioned Repair remains close to Oracle Reuse across twelve revisions and improves when previously observed concepts return.For repeated Q1 occurrences, accuracy ranges from 90.5% to 90.9% versus 91.4% initially.
  • B. Long-Horizon Recurring Concept Sequences: Across twelve transitions, Versioned Repair requires approximately 30 minutes, compared with 202 minutes for complete retraining and 25 minutes for Oracle Reuse.The cumulative-cost gap grows with the number of revisions.
  • C. Storage Overhead of Provenance and Versioned Memory: Shared version maintenance grows from approximately 6.1% to 10.2% of training-data size across twelve versions and reduces storage by more than 8× versus independent snapshots.Graph data has the largest reported proportional overhead, at approximately 15.1%.
  • D. Sensitivity to Repair and Provenance Parameters: Macro-F1 is strongest with stability weight approximately 0.5–1.0 and a stable buffer of roughly 2–5% of the certified stable region.The maximum evaluated Macro-F1 is 90.6%; stronger preservation can constrain adaptation.
Loading 2608.23893v1…