Accelerating Influence Function Estimation for Large Language Models: A Practical Design

Abstract

Influence functions provide a principled framework for tracing model predictions back to training data, yet existing methods remain impractical for large language models due to prohibitive storage and I/O costs. Prior approaches face two critical barriers: the Fidelity Gap from coarse curvature approximations, and the I/O bottleneck from materializing per-example gradients, which renders million-scale datasets infeasible. We propose StructInf, a structure-aware influence estimation framework that addresses both gaps through system-algorithm co-design. For fidelity, we first replace the indefinite Hessian with an adaptive block-diagonal damped empirical Fisher surrogate, computed via quadratically convergent Newton--Schulz iterations. For efficiency, we then introduce a streaming algorithm that eliminates per-example gradient storage entirely, reducing space complexity from O(N • d) to O(d) and enabling processing of million-scale training instances on consumer hardware, where N denotes the number of training instances and d the parameter size. We further identify and resolve Split-View Bias, a distributed pitfall where naive averaging of local curvatures fails, via a distributed gradient calibration strategy that synchronizes global statistics with minimal communication. Finally, we conduct comprehensive experiments to evaluate StructInf against other baselines. Unlike prior methods requiring hours of pre-computation or TB-scale storage, StructInf enables real-time data selection during training. Across GLUE and instruction-tuning benchmarks, StructInf achieves up to +26% AUC on MRPC and average 7× speedup for 7B-scale models, making high-fidelity influence analysis practical on a single RTX 4090. These results suggest that practical IF for LoRA-tuned LLMs benefits from joint optimization of curvature modeling, memory management, and distributed coordination.