GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection

2025/05/25 by Pengyan Hu, Hu, Pingbang, Melkonian, Joseph +6 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2505.18976

openalex publication_date 2025/05/25 · openalex created_date 2025/09/28 · openalex updated_date 2026/08/03

Abstract

Gradient-based data attribution methods, such as influence functions, are critical for understanding the impact of individual training samples without requiring repeated model retraining. However, their scalability is often limited by the high computational and memory costs associated with per-sample gradient computation. In this work, we propose GraSS, a novel gradient compression algorithm and its variants FactGraSS for linear layers specifically, that explicitly leverage the inherent sparsity of per-sample gradients to achieve sub-linear space and time complexity. Extensive experiments demonstrate the effectiveness of our approach, achieving substantial speedups while preserving data influence fidelity. In particular, FactGraSS achieves up to 165% faster throughput on billion-scale models compared to the previous state-of-the-art baselines. Our code is publicly available at https://github.com/TRAIS-Lab/GraSS.

Citations

• Capturing the Temporal Dependence of Training Data Influence
• dattri: A Library for Efficient Data Attribution
• Most Influential Subset Selection: Challenges, Promises, and Beyond
• Localize-and-Stitch: Efficient Model Merging via Sparse Task Arithmetic
• What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions
• Token-wise Influential Training Data Retrieval for Large Language Models
• DataInf: Efficiently Estimating Data Influence in LoRA-tuned LLMs and Diffusion Models
• Kronfluence: Influence Functions with Eigenvalue-corrected Kronecker-Factored Approximate Curvature
• TRAK: Attributing Model Behavior at Scale
• OPORP: One Permutation + One Random Projection
• The Fast Johnson-Lindenstrauss Transform is Even Faster
• Scaling Up Influence Functions
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• Estimating Training Data Influence by Tracing Gradient Descent
• Input Similarity from the Neural Network Perspective
• Fast and Accurate Network Embeddings via Very Sparse Random Projection
• Data Cleansing for Models Trained with SGD
• Enabling Factorized Piano Music Modeling and Generation with the MAESTRO Dataset
• Billion-scale Network Embedding with Iterative Random Projection
• The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• Understanding Black-box Predictions via Influence Functions
• Pointer Sentinel Mixture Models
• Lecture Notes on Randomized Linear Algebra
• Deep Residual Learning for Image Recognition
• Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Sparser Johnson-Lindenstrauss Transforms
• A Sparse Johnson--Lindenstrauss Transform
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors

Cited by

• Randomized Sketching is Robust to Low-Precision Rounding on GPUs
• STRIDE: Training Data Attribution via Sparse Recovery from Subset Perturbations

Related

• Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients
• Efficient Distributed Training through Gradient Compression with Sparsification and Quantization Techniques
• The Data Gradient: Quantifying Dataset Influence in End-to-End Machine Learning Systems
• An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems
• Toward Efficient Influence Function: Dropout as a Compression Tool