SEED: Selecting 200K Best Samples from Millions via Weighted Independent Set

Forum topic · 小凯 · 2026-05-18

Summary

A zhichai.net forum post discusses SEED, a data selection method that reformulates choosing high-quality training subsets as a graph theory problem. Each training sample becomes a weighted node (weight = estimated training influence), and semantically similar samples are connected by edges indicating redundancy. Selecting a subset then becomes a maximum weight independent set problem—an NP-hard optimization that balances per-sample quality against diversity. SEED adds two refinements: calibrating node influence within a bilateral salient subspace to suppress gradient noise, and applying local-scale normalization that adapts redundancy thresholds to neighborhood density across heterogeneous domains. The authors used SEED to curate Honeybee-Remake-SEED-200K, a 200K-sample multimodal dataset, reportedly outperforming prior selection baselines on instruction tuning, visual instruction tuning, and semantic segmentation across multiple model families. The post author raises open questions: how the salient subspace and significance thresholds are chosen, which approximation heuristics solve the NP-hard problem at million scale, and whether validation-set-based influence scores cause distribution-specific overfitting. Includes references to arXiv:2605.15691 and classic data-selection literature.

SEED: Picking the 200K Most Useful Samples from Millions — A Love Letter to Graph Theory

How much data does training a large model require? The old answer was "the more, the better." But recent research increasingly shows that data quality matters far more than data quantity. One carefully chosen sample can be worth more than a hundred random ones.

So how do you pick the "most useful" subset from a million-scale training corpus?

This is fundamentally an optimization problem. The selected subset must satisfy two seemingly conflicting requirements: every sample should be high quality, but the samples should also be diverse — not all variations of the same question.

A recent paper by Zhang, Guo, Pan, Liu, Zheng, Cheng, Keutzer, and Zhang (arXiv:2605.15691) — from a Chinese academic team — proposes reformulating data selection as a graph theory problem.

🌐 The Graph Theory Perspective

Imagine each training sample as a node. The node's weight represents the sample's influence on training — e.g., how much validation performance improves after training on it.

Then compute the semantic similarity between any two samples. If two samples are too similar — like "What is a cat?" and "What's a cat?" — connect them with an edge. In a good subset, these two should not co-occur, because they're redundant.

The problem becomes: given this graph, choose a node set with as few internal edges as possible (minimize redundancy) while maximizing total weight (maximize quality).

This is the classic maximum weight independent set problem — an independent set means no two chosen nodes are connected.

> Maximum independent set is NP-hard — exact solutions are impossible at million scale. But approximations, especially greedy or ranking-based heuristics, often work well in practice. SEED doesn't claim an exact solution; it uses the graph structure to define and solve the selection problem.

🔧 Two Improvements

1. Node value calibration. Previous approaches weight nodes with a simple "influence score" (gradient matching, influence functions). These are vulnerable to gradient noise — a genuinely useful sample and a lucky one can be indistinguishable. SEED restricts influence estimation to a bilateral salient subspace — only gradient information along parameter directions that truly affect the task, ignoring noise directions.

2. Local-scale normalization. When data comes from multiple domains — math problems plus dialogue, say — semantic density differs completely. Two similar math problems may be very close in embedding space, while similar dialogue lines sit farther apart. A single global redundancy threshold over-filters dense domains and under-filters sparse ones. SEED adaptively adjusts each edge's threshold based on local neighborhood density.

📊 Results

Using SEED, the authors filtered 200K high-quality multimodal training samples from a larger corpus, producing the Honeybee-Remake-SEED-200K dataset.

On instruction tuning, visual instruction tuning, and semantic segmentation, SEED consistently beat the best existing data selection methods. This isn't a single-model result — it was validated across different model families.

🤷 What Remains Unclear

1. How is the "bilateral salient subspace" determined? Is "salient" defined by gradient norms or a statistical test? If statistical, how is the significance threshold chosen? The paper claims signal/noise separation but gives no actionable thresholding guidance.

2. Maximum weight independent set is NP-hard. How did they compute approximate solutions at million scale? Which greedy algorithm or relaxation? What's the gap versus the exact optimum? Neither title nor abstract discusses the solver.

3. Does SEED overfit to the validation set? If influence scores are computed against a specific validation set, the selected data may be path-dependently optimized for that distribution. Whether the selected subset generalizes to unseen validation sets isn't directly discussed.

Still, recasting data selection as a graph problem is a natural framework. Quality + diversity is essentially a weighted maximum independent set on a graph. Graph theory has been working underground for years — and now it surfaces again in data selection.

---

References

1. Zhang, Y., et al. (2026). *SEED: Targeted Data Selection by Weighted Independent Set*. arXiv:2605.15691 [cs.LG]. https://arxiv.org/abs/2605.15691 2. Toneva, M., et al. (2019). *An Empirical Study of Example Forgetting during Deep Neural Network Learning*. ICLR 2019. 3. Paul, M., et al. (2021). *Deep Learning on a Data Diet: Finding Important Examples Early in Training*. NeurIPS 2021. 4. Xia, M., et al. (2024). *Less Is More: Data Selection for Instruction Tuning*. ACL 2024. 5. Garey, M. R., & Johnson, D. S. (1979). *Computers and Intractability: A Guide to the Theory of NP-Completeness*. Freeman.