Technical Summary: Form and Function: Machine Unlearning as a Problem of Misaligned States

Problem Definition

The paper addresses a critical gap in machine unlearning evaluation: the focus on model performance (function) often neglects the internal geometry and state of the model (form). This is particularly acute for stateful optimizers like online L-BFGS, which maintain not only parameter vectors ($w_t$) but also a finite memory of curvature pairs ($Z_t$) used to approximate the inverse Hessian.

The authors argue that current unlearning methods, which often treat unlearning as a parameter-correction problem, are insufficient. In stateful optimizers, deleted data influences the trajectory of future curvature pairs and update directions even after the explicit curvature pairs containing that data have rotated out of the memory window. Consequently, a model that has "unlearned" data in its parameters may still possess a coupled state (parameters + memory) that is geometrically inconsistent with the counterfactual state that would have arisen had the data never been processed. The core problem is reframed as a counterfactual state-alignment problem: the goal is to align the actual optimizer state with the state generated by a deletion-edited event stream.

Methodology

Theoretical Framework

The paper formulates unlearning for online L-BFGS (o-LBFGS) within a sequential learning setting.

• Event Streams: The authors distinguish between the actual event stream ($H_t$) and the deletion-edited counterfactual stream ($H_t^{-D}$), which excludes specific samples.
• State Definition: The learner state is defined as $\theta_t = (w_t, Z_t)$, where $Z_t$ contains the curvature pairs $\{(v_i, r_i)\}$.
• State-Alignment Error: A new metric, $\Delta_t$, is introduced to measure the distance between the unlearned state and the counterfactual oracle state.
• Recursive Bounds: Under assumptions of strong convexity, smoothness, bounded gradients, and contractive updates, the authors derive a recursive bound on the state deviation. They demonstrate that the error consists of two components:
  1. Direct Memory: Explicit curvature pairs containing deleted data, which vanish after $\tau$ updates (the memory window size).
  2. Indirect Memory: Residual influence persisting through the parameter trajectory, which generates new curvature pairs and update directions. This influence decays geometrically but persists beyond the direct memory window.

Certificates for Unlearning

The paper proposes a method for State-Certified Unlearning. Unlike prior work that calibrates noise based solely on parameter sensitivity, this approach calibrates noise injection based on the total state deviation bound ($\alpha_t$). This bound accounts for both the initial disruption and the residual indirect memory, ensuring that the randomized unlearned state is indistinguishable from the counterfactual ideal within a defined probabilistic guarantee.

Experimental Benchmark

The authors introduce a state-aware benchmark that evaluates unlearning interventions across four distinct error metrics:

1. Parameter Error: Deviation in the weight vector.
2. Memory-Operator Error: Deviation in the curvature memory/inverse-Hessian approximation.
3. Combined State Error: The joint deviation of $(w_t, Z_t)$.
4. Update-Direction Error: The divergence in future gradient update directions.

Interventions tested include:

• Oracle Replay: Retraining on the exact counterfactual stream (ground truth).
• Window Replay: Replaying a recent window of events to reconstruct the state.
• Parameter-Only Correction: Adjusting $w_t$ while leaving $Z_t$ untouched.
• Memory-Only Correction: Resetting or dropping contaminated curvature pairs while leaving $w_t$ untouched.
• Contaminated Pair Drop: Removing specific curvature pairs.
• Drop-and-Refill: Discarding both parameters and memory, then continuing.

Key Results

1. Parameter Alignment Understates Persistence

Experiments on quadratic and ridge-logistic loss surfaces demonstrate that correcting only the parameter vector ($w_t$) fails to achieve true unlearning. While parameter-only interventions may reduce parameter error, they leave the curvature memory ($Z_t$) contaminated. This creates a "hybrid state" where the parameters assume the data was deleted, but the memory still encodes update directions based on the original trajectory. This misalignment results in the largest future trajectory error among non-oracle methods, often exceeding the error of performing no correction at all.

2. Indirect Memory and the Deletion Horizon

The study confirms that deleted data persists via indirect memory. Even after contaminated curvature pairs rotate out of the L-BFGS window (direct memory clearance), the altered parameter trajectory generates new curvature pairs that carry the "ghost" of the deleted data.

• Memory Size Trade-off: Larger memory windows ($\tau$) retain direct contamination longer but also slow the rate of state alignment. Smaller windows shorten the deletion horizon but may compromise optimization efficiency.
• Decay Dynamics: State deviation does not vanish immediately upon memory clearance; it decays geometrically over time, dependent on the contractivity of the optimizer.

3. Inadequacy of Local Interventions

Local edits (modifying only parameters or only memory) fail to reconstruct the counterfactual state.

• Memory-Only Reset: While it removes direct contamination, it fails to reconstruct the parameter trajectory that would have naturally generated the counterfactual memory, leading to significant update-direction errors.
• Drop-and-Refill: Aggressively removing data can be detrimental, moving the optimizer further from the counterfactual trajectory than doing nothing, as it destroys useful information shared by both the actual and counterfactual histories.

4. Success of Strategic Replay

Window Replay is the only non-oracle method shown to reliably approach exact recovery. By reconstructing the joint parameter-memory state from a window of data consistent with the deletion request, it aligns both form and function. Its effectiveness is highest when the deleted data falls within the replay window. As data moves from direct to indirect memory, the efficiency of replay diminishes, but it remains superior to partial corrections.

Significance and Claims

The paper claims that machine unlearning for stateful optimizers is fundamentally a state-reconstruction problem, not merely a parameter-correction problem.

• Ontological Shift: The authors argue that unlearning must be evaluated based on whether the system can assume the "form and function" of the counterfactual ideal. A model that performs well but possesses a misaligned internal state is not truly unlearned.
• New Evaluation Standard: The paper introduces state-aware metrics that reveal the insufficiency of current parameter-centric evaluation methods, which often miss residual information stored in the optimizer's geometric memory.
• Theoretical Contribution: It provides the first recursive bounds on counterfactual state deviation for online L-BFGS, distinguishing between direct and indirect memory effects, and offers a framework for state-certified unlearning that accounts for the full optimizer state.
• Practical Implication: The results suggest that reliable unlearning in online, memory-constrained environments requires either full state reconstruction (via replay) or a more sophisticated understanding of how curvature memory propagates deletion effects, rather than simple parameter perturbation.

The authors maintain modesty regarding their scope, noting that their theoretical bounds rely on convexity assumptions and that their experiments use synthetic streams, leaving the application to large-scale, non-convex, deployed models as future work.