f-INE: A Hypothesis Testing Framework for Estimating Influence under Training Randomness

AI summary

Overview

Research area: Data attribution and influence estimation for machine learning, connecting influence estimation to differential privacy (DP) auditing and hypothesis testing, with experiments on image classification and LLM instruction tuning.

Technical level: Advanced. The paper assumes familiarity with influence functions, Gaussian Differential Privacy, trade-off functions, Type I/II error theory, and stochastic gradient descent training pipelines.

Scope: The paper proposes a new definition of data influence ("f-influence") that explicitly accounts for training randomness, proves that it collapses to a single-scalar Gaussian influence ("G_mu-influence") for iteratively trained models, and presents a single-training-run algorithm (f-INE) that is benchmarked on mislabeled-data detection in MNIST and CIFAR-10 and on poisoned instruction detection in Llama-3.1-8B.

What This Paper Is About

Existing influence estimation methods try to predict how the model would change if a training sample were removed, but they produce unstable scores: the same example can look critical in one training run and irrelevant in the next because of randomness from seeding, weight initialization, batch size, and data shuffling. This instability makes it unclear whether a data cleanup decision (deleting or keeping a point) is actually correct. The paper reframes influence as a hypothesis test, asking whether removing a data subset changes a test statistic by more than what training randomness alone would produce, and builds an efficient estimator of this quantity.

Key Contributions

1. A new definition of influence grounded in hypothesis testing. The authors introduce "f-influence," motivated by privacy auditing and differential privacy. Influence is defined as the statistical distinguishability between the distribution of a test statistic when a subset is included in training (H₀) versus excluded (H₁), formalized through Type I/II errors and trade-off functions (Definition 2.3), with a scalar-parameterized special case called Gaussian or G_mu-influence.

2. Theoretical properties that rescue a total ordering. The paper proves a compositionality property (Theorem 2.6) and asymptotic normality (Theorem 2.8) for f-influence, plus a corollary (Corollary 2.7) bounding the k-fold composed influence by |μ√k|. These results establish that for highly iterative algorithms like SGD, f-influence is asymptotically G_mu-influence, so influence has a total order by ordering μ values, even though arbitrary trade-off curves only induce a partial order.

3. The f-INE algorithm, which estimates influence in a single training run. The method has two stages: Stage 1 collects gradient-similarity signals with and without the target subset at each update step (including a difference-of-differences correction using an auxiliary model), and Stage 2 sweeps decision thresholds to compute Type I and Type II errors and converts them into μ. Its complexity is 𝒪(Tnd), the same high-scalability class as TraceIn and LESS, and better than Influence Functions (𝒪(nd²+d³)) and TRAK (𝒪(M(nk²+k³))).

4. Scaling to LLM instruction tuning. The authors apply f-INE to Llama-3.1-8B finetuned on poisoned LIMA data, detecting biased instructions that steer model sentiment about Joe Biden and Abortion, and show lower run-to-run variability than LESS.

Main Findings

• Existing methods are inconsistent under randomness: Influence Functions, TraceIn, and TRAK show large score discrepancies under data shuffling. An MLP on a subset of MNIST was trained under two data loader configurations (Config-1 and Config-2) differing only in the order of the first two class-1 samples; the first class-1 sample receives a high influence score in Config-1 and a much lower one in Config-2. f-INE is mostly consistent in comparison. Consistency is measured as 1 − binom(R,2)⁻¹ Σ_{i,j∈R} J(I(A^i), I(A^j)), a score in [0,1] where 1 indicates perfect consistency.

• No total ordering exists in general: In the illustrative example, removing d₁ always decreases accuracy by 0.1%, while removing d₂ increases accuracy by 1% but only with probability 0.1. Both have the same mean influence, yet the correct ordering depends on the evaluation criterion (e.g., a single retrain versus picking the best of many runs).

• Asymptotic normality restores a usable order: Because training is a composition of many near-identical SGD update steps, the composed trade-off curve converges to G_mu, so influence can be summarized by the single signed scalar μ.

• Mislabeled-data detection in MNIST: With 20% of MNIST data randomly mislabeled and an MLP with hidden size 500, f-INE is comparable (only 0.05% better) to TraceIn, and on average outperforms TRAK by 13.85% and Influence Functions by 3.83%. Its recall curve is smoother and more predictable. Additional CIFAR-10 results are reported in the appendix.

• Better utility on poisoned LLM data: Training on the full poisoned LIMA data produced a 40% increase in negative responses for Joe Biden and 60% for Abortion versus the clean-LIMA model. In the top-20% most influential ranking, f-INE identified more than 60% of poisoned instructions for Joe Biden, compared with 44% by LESS. Results are averaged over 3 training runs with error bars showing standard deviation.

• Lower variability across training runs: Using the average coefficient of variation (1/n Σ σᵢ/|μᵢ|) over the top-p percent most influential data, f-INE is lower than LESS for both entities and across p values. At p = 1.0, f-INE's average coefficient of variability is 64% lower than LESS.

• Ablations: Projection dimensions d = [1024, 2048, 4069, 8192] showed low sensitivity, with slight degradation as the projection dimension decreases (a similar trend appears for LESS). Using 60 or 80 subsampled checkpoints gave lower utility than more checkpoints; the main experiments use 100 equally spaced checkpoints.

• Qualitative case study: Because LESS compares only the means of gradient cosine similarities while f-INE uses the whole distribution, LESS can miss subtle poisonings. The authors attribute f-INE's gains to its ability to capture long tails of the gradient distribution.

Methodology in Plain English

The authors start from a simple question: if I delete a suspect data point and retrain, will the improvement be bigger than the noise I'd see anyway from random training? To answer this rigorously, they treat the presence or absence of the data subset as two competing hypotheses about the distribution of a test statistic (loss or gradient on a test point). How easily those two distributions can be told apart is the influence score. Following the Gaussian Differential Privacy framework, they define Type I error, Type II error, and a trade-off function, then define f-influence as that trade-off curve and G_mu-influence as its Gaussian special case, parameterized by a single signed number μ.

Naively estimating μ would require retraining hundreds of times with and without the subset. The algorithm avoids this using three ideas. First, it estimates the influence of a single update step rather than the whole trajectory, relying on the compositionality corollary to relate single-step influence to total influence. Second, instead of raw losses, it uses gradient similarity between the test point and training points, based on a first-order Taylor approximation of the loss change: l(θᵗ, z_test) − l(θᵗ⁺¹, z_test) ≈ η ∇l(θᵗ, z_test)ᵀ ∇l(θᵗ, z′). Third, first-order differencing removes the decreasing trend in losses, and a difference-of-differences step subtracts signals from an auxiliary model to reduce correlation between successive samples.

In Stage 1, the model is trained with mini-batch SGD for T epochs; two signal sets are collected, one where the mini-batch includes the target subset S and one where it is excluded, along with the auxiliary-model signals. In Stage 2, thresholds τ are swept across the range of observed signals; for each threshold the empirical Type I error α and Type II error β are computed, giving μ_th = Φ⁻¹(1 − α_th) − Φ⁻¹(β_th), and the final score is the maximum influence value (Algorithm 2 selects the largest in magnitude). For the LLM experiments the authors adopt the LESS optimizations (cosine similarity instead of dot products, LoRA checkpointing) but replace LESS's mean comparison with the distributional hypothesis test.

Why This Matters

Impact on research. The paper forges an explicit link between data influence estimation and differential privacy auditing, importing tools (trade-off functions, composition, asymptotic normality) that give influence scores a principled statistical interpretation under randomness. It also argues that a single scalar cannot order influence in general, sharpening how the community should think about evaluating attribution methods.

Real-world applications.

• Data cleaning and mislabeled-example detection in supervised learning pipelines (demonstrated on MNIST and CIFAR-10).
• Curating and auditing instruction-tuning datasets for LLMs before or after finetuning.
• Detecting data poisoning, including subtle poisons that steer a model's opinions on people or topics.
• Debugging model behavior by attributing generated outputs back to specific training examples.

Industry relevance. Data selection and cleanup are expensive parts of production ML, especially for LLMs where retraining is costly. f-INE produces influence scores in a single training run at the same 𝒪(Tnd) complexity class as the widely used LESS and TraceIn, requires no retraining ensembles, and produces stable rankings across seeds, which matters when decisions about which data to keep or drop are made once and relied upon later.

Future Directions

• Broader validation beyond the reported settings. The paper reports mislabeled-sample detection on MNIST (and CIFAR-10 in the appendix) and one LLM poisoning setup on two entities (Joe Biden and Abortion) with LIMA; extending to more models, datasets, and modalities is an open step.

• Improving estimation from limited checkpoints. The ablation shows utility improves with more checkpoints, and the authors suspect fewer checkpoints cause the method to miss long-tail gradient signals. Better sampling or long-tail-aware estimators could relax the 100-checkpoint budget.

• Understanding the threshold selection rule. The final score uses the maximum (largest in magnitude) μ across thresholds; whether this "best case" choice is optimal, versus a principled criterion grounded in the trade-off curve, is an open question.

• Sharpening the composition-based bound. Corollary 2.7 bounds k-fold composed influence by |μ√k|; tighter relations between single-step and full-trajectory influence could improve the accuracy of single-run estimates.

Target Audience

Researchers and practitioners working on data attribution, data curation, dataset debugging, and privacy auditing, particularly those with a background in influence functions or differential privacy. It is also relevant to ML engineers responsible for instruction-tuning data pipelines for large language models who need influence scores that are stable across training runs. Readers without grounding in trade-off functions, DP auditing, or SGD dynamics will find the theoretical sections demanding.

Authors’ abstract

Influence estimation methods promise to explain and debug machine learning by estimating the impact of individual samples on the final model. Yet, existing methods collapse under training randomness: the same example may appear critical in one run and irrelevant in the next. Such instability undermines their use in data curation or cleanup since it is unclear if we indeed deleted/kept the correct datapoints. To overcome this, we introduce *f-influence* -- a new influence estimation framework grounded in hypothesis testing that explicitly accounts for training randomness, and establish desirable properties that make it suitable for reliable influence estimation. We also design a highly efficient algorithm **f**-**IN**fluence **E**stimation (**f-INE**) that computes f-influence **in a single training run**. Finally, we scale up f-INE to estimate influence of instruction tuning data on Llama-3.1-8B and show it can reliably detect poisoned samples that steer model opinions, demonstrating its utility for data cleanup and attributing model behavior.