Introducing GIST: The next stage in smart sampling

Training modern AI models means wading through datasets so large that just processing them costs a fortune. Google Research's answer, presented at NeurIPS 2025, is an algorithm called Greedy Independent Set Thresholding, or GIST, which picks a smaller subset of data that's both diverse and useful without the guesswork that's plagued this problem for years.

The core tension GIST tackles is simple to describe and brutal to solve. You want your selected data points spread far apart in embedding space so you're not wasting training time on near-duplicate images or examples. But you also want each point to carry real informational value. Optimize purely for spread and you risk grabbing irrelevant outliers. Optimize purely for value and you end up with a redundant cluster. Google's researchers point out this is an NP-hard combinatorial problem, meaning no algorithm can crack it perfectly at scale, so the real goal becomes finding something provably close to optimal.

GIST gets there by chopping the problem into stages. First it fixes a minimum distance threshold and builds a graph connecting points that are too close together, which converts the diversity puzzle into a maximum independent set problem, the same species of problem behind seating charts where certain guests can't sit together. That's NP-complete too, so GIST runs a bicriteria greedy algorithm across many possible distance thresholds, grabbing the most valuable points at each step while respecting spacing rules, then keeping the best result across all the trials it ran.

What makes this notable isn't just the mechanics — it's the math behind it. GIST is the first algorithm here to carry a provable guarantee: whatever it selects is worth at least half of the true optimal subset, and Google's team also proved that beating a 0.56 fraction of optimal is itself NP-hard. That's a real ceiling on how much better anyone could theoretically do. In testing against baselines like random sampling, margin-based uncertainty picking, and k-center methods using a ResNet-56 model on ImageNet-style data, GIST-enhanced approaches consistently produced higher accuracy. And the selection step itself runs fast enough to be a rounding error next to the days of GPU time spent on actual training.

Google also says the underlying max-min diversity principle already found its way into YouTube's Home ranking system, improving long-term viewer value by diversifying recommendations. That's a small but telling sign this isn't just a theoretical exercise — it's already touching products people use daily.