Clustered Influence Functions

Influence functions are a standard tool for data debugging and unlearning, but they become impractical for **high-query** subset workloads such as large-$K$ cross-validation, repeated resampling, or interactive what-if analysis as each subset query typically requires an expensive inverse-curvature solve. We introduce **Clustered Influence Functions (CiF)**, which turns subset influence into an **amortized subset oracle**. We build a compact cache once by clustering training gradients, solve a damped Generalised Gauss-Newton system only for cluster means, and answer new subset queries by a linear recombination using cluster membership counts. This yields per-query cost of $O(Cp)$ linear in the cache size $C$, and the number of model parameters $p$. We further provide a diagnostic error bound that decomposes approximation error into a **clustering scatter** term and a **solver residual** term, making the accuracy-compute tradeoff explicit through the cache budget and solver tolerance. Evaluations across MNIST, CIFAR-10 show that CiF matches per-query influence rankings while significantly reducing the total runtime in high-$Q$ regimes, enabling influence-based workflows that are otherwise computationally prohibitive.

Training modern AI systems requires vast amounts of data, and a natural question is: which training examples actually matter for a given prediction? Influence functions answer this by estimating how much each training point shifts the model's output, but computing them is expensive, especially when you need answers for thousands of different subsets of the data at once, as in cross-validation or data debugging workflows. We introduce Clustered Influence Functions (CiF), which turns this repeated computation into a one-time investment. Instead of solving a costly linear system for every new query, CiF groups the training data by gradient similarity, solves the system once per group, and stores the results in a cache. Any future query is then answered in milliseconds by combining cached responses, no new solves required. This makes influence-based data analysis such as auditing training sets, detecting poisoned examples, and running large-scale cross-validation more practical at larger scales.