STRIDE: Training Data Attribution via Sparse Recovery from Subset Perturbations

Scaling Training Data Attribution to LLMs via Activation-Space Steering

When an AI makes a mistake or retrieves a specific fact, it is notoriously difficult to pinpoint the cause. It is hard to know which part of its massive training corpus caused that behavior. This is the problem of Training Data Attribution (TDA). TDA aims to trace a model's predictions back to its source data. The gold standard for answering this is through causal interventions. This means observing how a model changes when specific data is added or removed. However, for Large Language Models (LLMs), repeatedly retraining the model is computationally impossible.

Current state-of-the-art approaches attempt to bypass retraining. They approximate these effects in the parameter space using gradients. This essentially tries to calculate how the model's weights would shift if a piece of data were present. But tracking gradients across billions of parameters is prohibitively expensive. These methods also rely on local linear approximations. These approximations often break down in the highly non-convex (complex, non-smooth) landscapes of deep learning.

A new paper introduces STRIDE (Steering-based Training Data Influence Decomposition). The authors propose a fundamental shift. Instead of estimating how weights change, they model the functional effect of training data in the activation space (the internal representations of the model). By treating attribution as a sparse recovery problem, the authors claim to achieve state-of-the-art accuracy. They also claim to be up to 12× faster than existing methods.

The bottleneck of parameter-space gradients

The status quo in TDA is stuck between two suboptimal poles. On one side are gradient-based methods like Influence Functions. These attempt to approximate the "Leave-One-Out" (LOO) effect. This is the change in model behavior when one example is removed. They do this via first-order Taylor expansions (mathematical approximations). As the authors note, these methods suffer from severe bottlenecks when applied to LLMs. Materializing and storing gradients for billions of parameters requires enormous memory and compute. Furthermore, these methods rely on the assumption of local convexity. This condition is frequently violated in deep learning.

On the other side are representation-based methods. These use embedding similarities or learned scoring functions to estimate influence. While these scale well, they often lack rigorous causal grounding. They rely on heuristic (rule-of-thumb) feature spaces. These spaces do not explicitly model how training data actually perturbs the model's output. As shown in, qualitative attribution can trace complex behaviors.

This includes a model's moral reasoning or mathematical errors. However, existing methods often struggle to bridge the gap between simple lexical similarity and actual functional shifts.

Moving the intervention to the activation space

STRIDE sidesteps the parameter bottleneck by operating in the low-dimensional activation space. The framework, illustrated in, moves through three distinct stages:

1. Learning Steering Operators: Instead of retraining the model on various data subsets, the authors learn lightweight, low-rank "steering operators." These operators are applied to the intermediate activations of a frozen base model. They mimic the behavioral shift that would have occurred if the model had been trained on those subsets. The steering is parameterized by a low-rank basis network and subset-specific matrices. These translate latent features into shifts in the logit space (the raw output scores).
2. Measuring Subset Responses: For any given query, the framework applies these learned operators to generate a response vector. This vector represents how the model's output probabilities would be perturbed by the influence of various training subsets.
3. Sparse Recovery via Compressive Sensing: This is the core mathematical engine. A single prediction typically depends on only a tiny fraction of the training corpus. Therefore, the authors formulate attribution as a sparse recovery problem. They use the $\ell_1$-regularized least squares problem, also known as Lasso (a regression method that promotes sparsity), to solve the underdetermined system $y_x \approx Mw$. Here, $M$ is a membership matrix constructed from an expander graph. This allows them to recover individual per-example influence scores from compressed subset-level measurements.

High accuracy with an order of magnitude less cost

The paper's primary claim is that this shift provides a massive win for both accuracy and efficiency. Evaluating on Nanochat models (ranging from 286M to 1.38B parameters), the authors report that STRIDE achieves the highest Linear Datamodeling Score (LDS). This metric correlates predicted influence with actual subset retraining. STRIDE outperforms all strongest baselines in this regard.

The efficiency gains are even more striking. At the 1.38B parameter scale, the authors report that STRIDE is over 12× faster than AirRep. It is also 5× faster than LoGRA. Looking at the scaling behavior in, STRIDE's runtime and VRAM requirements grow much more gracefully than gradient-based competitors.

For a 1.38B model, STRIDE completes in 9.9 hours on a single H100-80GB GPU. In contrast, baseline methods like AirRep are noted as being practically infeasible at that scale.

Beyond pure speed, the authors demonstrate the practical utility of these scores. In data contamination audits, combining LoGRA with STRIDE increased the recall of leaked training replicas to 74.2% .

This means the combined method identifies significantly more leaked data than using either method alone. They also show that the recovered scores are actionable for data selection. Using STRIDE to pick the top 1,000 examples for fine-tuning leads to meaningful performance improvements in downstream tasks.

Assumptions and potential failure modes

Despite the strong results, there are technical caveats to consider. STRIDE's efficacy is built on the assumption of "additive influence." This is the idea that the effect of a subset of data can be decomposed into the sum of individual examples. While the authors argue this holds for standard pre-training, it is an approximation. It could break down under extreme distribution shifts. It might also fail in cases of highly non-convex memorization.

Furthermore, because STRIDE is a representation-based steering method, its performance is tethered to the base model. It depends on the quality of the internal activations and the specific layer chosen for intervention. The ablation studies show that the choice of layer is critical. Intervening in early layers fails to capture actionable influence. Late layers perform best. Practitioners will need to tune this intervention point for different architectures.

Finally, the sparse recovery process relies on the membership matrix $M$ behaving like an expander graph. This ensures unique recovery. While the authors provide theoretical guarantees, the practical implementation involves random assignment. If the subset design is poorly constructed, the mathematical foundation for the Lasso recovery could weaken.

The verdict

STRIDE is a significant step forward for anyone tasked with auditing or curating LLM datasets. By moving the "intervention" from the heavy parameter space to the agile activation space, the authors have made a prohibitive task manageable. The combination of state-of-the-art LDS scores and a 12× speedup makes this a practical tool.

If you are struggling with the memory overhead of gradient-based influence functions, this is worth a prototype. If you lack the causal rigor of similarity-based methods, this is also worth investigating. The code is reportedly available at https://stride-tda.github.io. Given that the method scales predictably with model size, it is likely to become a standard component in the LLM safety and data engineering toolkit.

Figures from the paper