🤖 AI

Constraint-Data-Value-Maximization: Utilizing Data Attribution for Effective Data Pruning in Low-Data Environments

This paper introduces Constraint-Data-Value-Maximization (CDVM), a novel approach that frames data pruning as a constrained optimization problem to effectively maximize model influence while penalizing excessive per-test contributions, thereby outperforming traditional Shapley-based methods in low-data scenarios.

Original authors: Danilo Brajovic, David A. Kreplin, Marco F. Huber

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Danilo Brajovic, David A. Kreplin, Marco F. Huber

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create the perfect soup. You have a massive pantry full of ingredients (your data), but your kitchen is small, your stove is weak, and you only have time to cook with a tiny fraction of what you have. You need to throw away most of the ingredients but keep the ones that make the soup taste the best.

This is the problem machine learning models face today. They need huge amounts of data to learn, but storing and processing all that data is expensive and slow. The goal is data pruning: figuring out which specific pieces of data are the "secret spices" and which are just "filler" that can be tossed out without ruining the dish.

The Old Way: The "Popularity Contest"

For a while, scientists tried to solve this using a method based on Shapley values (a concept from game theory). Think of this like a popularity contest where every ingredient gets a score based on how much it helps the soup when it's added to different combinations of other ingredients.

The paper argues that this old method has a fatal flaw: It hates groups.

Imagine your pantry has:

100 identical potatoes (a big cluster).
1 unique, rare truffle (a small cluster).

The old method looks at the potatoes and says, "Well, we have so many of you, any single potato isn't that special. You're all redundant." So, it gives them a very low score. It looks at the single truffle and says, "You are unique! You are essential!" So, it gives it a high score.

The Disaster: When the chef starts throwing away the "low score" ingredients, they throw away 99 potatoes first. But then, they run out of potatoes entirely. Suddenly, the soup has no starch at all, and it tastes terrible. The method removed the entire group of potatoes too early because it didn't realize that even though the potatoes were similar, the group as a whole was vital.

The New Solution: CDVM (The "Fair Coverage" Chef)

The authors introduce a new method called Constraint-Data-Value-Maximization (CDVM). Instead of just giving every single ingredient a score and sorting them from best to worst, CDVM acts like a smart chef who cares about balance.

Here is how CDVM works, using a simple analogy:

The Menu (The Test Set): Imagine you have a menu of 100 different customers, each with a specific taste preference (e.g., some like salty, some like sweet, some like spicy).
The Goal: You want to pick a small basket of ingredients (say, 10 items) that will satisfy everyone on the menu.
The Constraint: CDVM doesn't just ask, "Which ingredient makes the soup best overall?" It asks, "If I pick this ingredient, does it help the spicy customers? Does it help the sweet customers?"

CDVM sets a rule: No customer on the menu should be left completely unsatisfied.

If the old method would pick 9 potatoes and 1 truffle (ignoring that the potatoes are needed for the "starchy" customers), CDVM says, "Wait a minute. If I pick 9 potatoes, I'm ignoring the 'spicy' customers who need a pepper. Let's swap some potatoes for a pepper to make sure everyone gets something."

It treats the problem like a puzzle where you must maximize the total happiness of the customers while ensuring no single customer is ignored. It forces the selection to keep at least one representative from every "group" of ingredients until it absolutely has to let them go.

Why This Matters

The paper tested this new method against the old popularity-contest methods on six different datasets (like images of cars, text reviews, and medical data).

The Result: When the chefs were forced to use very small amounts of data (like keeping only 5% or 10% of the original ingredients), the CDVM method made much better soups (models) than the old methods.
The "Budget" Insight: The paper also discovered something surprising: The "best" 10% of ingredients is not necessarily a subset of the "best" 20%. Sometimes, the perfect 10% includes a weird ingredient that you would have kept in the 20% pile but would have thrown away in the 5% pile. CDVM is smart enough to re-calculate the perfect mix for every specific budget size, rather than just using a single "best to worst" list.

The Bottom Line

The paper claims that by changing how we look at data—from "ranking individuals" to "optimizing for balanced coverage"—we can cut down the size of our training datasets significantly without losing performance. This saves energy and money, especially when we are working with very limited data.

In short: The old way was like throwing away all the potatoes because one potato isn't special. The new way (CDVM) says, "Let's keep a few potatoes, a few carrots, and a few spices, so that no matter what the customer wants, we have something to offer."

Technical Summary: Constraint-Data-Value-Maximization for Effective Data Pruning in Low-Data Environments

1. Problem Statement

Machine learning models, particularly large language models, face an insatiable demand for data while data availability stagnates. Data valuation methods aim to attribute the influence of individual training instances on model performance to reduce dataset size, thereby saving energy and improving training efficiency. However, existing approaches for data pruning (removing low-value data) suffer from critical limitations, especially in low-data environments where only a small fraction of the dataset remains.

The authors identify three primary shortcomings in current state-of-the-art methods (specifically Shapley and Banzhaf value-based approaches):

Cluster-Size Bias: Shapley and Banzhaf values distribute a cluster's total utility among its members. Consequently, points in larger data clusters receive smaller marginal values than points in smaller clusters. This leads to the premature removal of entire large clusters, causing sharp drops in model performance once the last representative of a cluster is pruned.
Redundancy Bias: Leave-One-Out (LOO) methods often assign zero value to redundant samples, failing to distinguish between the utility of keeping one representative versus many.
Non-Nested Optimal Subsets: The subset of data that maximizes accuracy for a specific retention budget (e.g., 10%) is not necessarily a subset of the optimal set for a different budget (e.g., 5%). Standard pruning strategies that assume nestedness fail to adapt to these budget-specific optima.

2. Methodology: Constraint-Data-Value-Maximization (CDVM)

To address these limitations, the authors propose Constraint-Data-Value-Maximization (CDVM), an optimization-based framework that treats data pruning as a constrained optimization problem over a data attribution matrix.

Core Concepts

Data Attribution Matrix ( $T$ ): Unlike scalar data values, CDVM utilizes a matrix $T \in \mathbb{R}^{n \times m}$ where $n$ is the number of training instances and $m$ is the number of test instances. Entry $T_{i,j}$ quantifies the influence of training instance $i$ on the prediction of test instance $j$ . This matrix is estimated using the Maximum Sample Reuse (MSR) principle, training models on sampled subsets to approximate influence without full retraining for every instance.
Optimization Formulation: CDVM formulates pruning as selecting a binary vector $w \in \{0, 1\}^n$ $w \in {0, 1}^{n}$ (indicating which $S$ $S$ training instances to retain) to maximize a utility function subject to constraints.
- Objective: Maximize the total influence on test samples while penalizing excessive concentration of influence on a few test samples.
- Constraint: The number of retained instances must equal the budget $S$ .
- Slack Variables: To prevent the "winner-take-all" scenario where a few test samples dominate the utility, the method introduces slack variables $t_j$ that cap the influence per test sample at a threshold $\kappa$ . Any influence exceeding $\kappa$ is penalized.

The formal optimization problem is:
$\begin{aligned} \max_{w, t} \quad & \alpha \sum_{j=1}^m v_j - (1-\alpha) \sum_{j=1}^m t_j \\ \text{s.t.} \quad & v = T^\top w \\ & \sum_{i=1}^n w_i = S \\ & t_j \ge 0, \quad t_j \ge v_j - \kappa \\ & w_i \in \{0, 1\} \end{aligned}$
where $v_j$ is the induced utility for test sample $j$ , and $\alpha$ balances total utility against the penalty for exceeding the threshold.

Implementation

The authors relax the binary constraint $w_i \in \{0, 1\}$ to $w_i \in [0, 1]$ to solve the problem as a Mixed-Integer Linear Program (MILP) using the Disciplined Parametrized Programming framework. After solving, the top- $S$ entries of $w$ are retained. This approach ensures balanced coverage, guaranteeing that no test sample (and thus no implicit data cluster) is left with zero total influence as long as the budget permits.

3. Key Contributions

The paper makes four primary contributions:

Analysis of Existing Limitations: The authors demonstrate theoretically and empirically that Shapley and Banzhaf attributions allocate smaller marginal contributions to instances in larger data clusters, leading to unbalanced removal patterns and suboptimal pruning performance in low-data regimes.
Budget-Specificity Insight: They show that optimal retention sets are budget-specific; the subset maximizing accuracy for one retention level does not necessarily contain the subset optimized for another.
CDVM Algorithm: The introduction of CDVM, which casts pruning as an optimization over an attribution matrix, explicitly addressing redundancy and cluster-size biases by enforcing balanced influence across test samples.
Benchmarking: Comprehensive evaluation on six datasets from the OpenDataVal benchmark, demonstrating strong performance and competitive runtime compared to state-of-the-art techniques.

4. Experimental Results

The authors evaluated CDVM on six datasets from the OpenDataVal benchmark (including CIFAR-10, Adult, IMDB, BBC, Pol, and Nomao) across retention levels from 5% to 30%.

Performance: CDVM achieved state-of-the-art performance in 28 out of 36 configurations (6 datasets $\times$ 6 pruning rates). It consistently outperformed random removal, DataBanzhaf, and DataOob/Memorization methods.
Comparison with Influence Optimization: While the Influence Optimization method (Yang et al., 2023) performed competitively on some datasets (notably Nomao), CDVM was the only method to consistently beat random baselines across all six benchmarks when hyperparameters were appropriately tuned.
Runtime Efficiency: CDVM offers a superior speed-accuracy trade-off. While computing the attribution matrix $T$ is the primary bottleneck (shared by all semi-value-based methods), the optimization step is fast. CDVM with 5,000 models achieved results comparable to or better than methods requiring 10,000 models, with significantly lower optimization time than Influence Optimization (which requires Hessian inversion).
Robustness: The method is robust to hyperparameter choices. A default configuration ( $\alpha=0.5$ , $\kappa$ derived from dataset statistics) performed nearly as well as grid-searched parameters, incurring zero search overhead.

5. Significance and Claims

The paper claims that CDVM provides a robust solution for data pruning in low-data regimes, a scenario where existing Shapley-based methods often fail due to their inherent biases. By shifting from scalar data values to a constrained optimization over an attribution matrix, CDVM ensures that the remaining dataset maintains balanced coverage of the test distribution.

The authors emphasize that their findings highlight "substantial room to improve data pruning," which directly translates to reduced training costs and energy consumption. They note that while CDVM is computationally competitive, the primary bottleneck remains the computation and storage of the attribution matrix $T$ . Future work could explore more efficient attribution estimators or exploit the sparsity of $T$ to scale to larger datasets like ImageNet.

The paper concludes that CDVM effectively leverages data attributions to prune low-value examples without sacrificing model quality, offering a practical alternative to random selection and existing valuation-based pruning strategies.