acceptodds
Under review as a conference paper at ICLR 2027

Dimension-Free Data Filtering

Abstract

Selecting high quality data is a crucial prerequisite for training and fine-tuning large language models. While empirical filtering heuristics are widely used, they often lack rigorous guarantees regarding how well the filtered data aligns with the target task. In this paper we propose a theoretical framework for data filtering that provides explicit distribution matching guarantees. Given a small set of high quality examples and a larger set of lower quality examples, our goal is to design a filter to identify more high quality examples. Our main result is a simple mechanism that generates a distribution of examples that is within total variation distance of the high quality distribution. We also show nearly matching information-theoretic lower bounds.

Primary area:
learning theory
Keywords:
data filtering, PU learning, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_D4JQOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper filters a large unlabeled pool with a small sample from a target distribution. Under bounded features and approximate linear separation, it bounds the total variation distance between the filtered and target distributions, with complexity set by the margin rather than an ambient dimension. A lower bound matches the dependence on the positive sample size and the margin up to logarithmic factors, even with unlimited unlabeled data. Unknown margin is handled by selecting among candidates with independent validation samples. Experiments show downstream gains on synthetic data and target-source enrichment in a Wikipedia and C4 mixture.

Critical strengths
  1. Control of filtering error without labeled negatives. The false-positive argument is the strongest part of the upper-bound analysis. It uses the constrained objective to connect errors on the two mixture components, then obtains a TV guarantee with explicit dependence on sample sizes, target proportion, and overlap. This explains why the filtering strategy works under the stated geometry.

  2. A matching lower bound and a principled treatment of unknown margin. Keeping the mixture fixed across different targets isolates the information supplied by the positive sample. The resulting lower bound shows that the 1/(γ2NS)1/(\gamma^2 N_S) dependence is necessary, up to logarithmic factors. The margin-selection analysis adds a useful extension, with explicit control of the validation and selection errors.

Critical weaknesses
  1. The guarantee does not directly cover the filter the experiments run. Theorem 7 bounds the distance achieved by the solution of the constrained problem in (1), which keeps margin violations on the positive sample under a threshold while minimizing acceptance on the mixture. The synthetic experiment trains a weighted linear SVM and the text experiment an L2-regularised logistic regression, but neither is shown to solve (1) or inherit its guarantee. The conclusion lists robustness to inexact solutions as an open problem, and Section 6 still describes the experiments as a confirmation of the approach. A reader cannot tell how much of the reported gain the theory accounts for.
  2. The numbers in Table 1 and Figure 1 have no stated protocol. Table 1 reports false negative and false positive rates without saying which paragraphs they are computed on. The mixture holds 2,020 Wikipedia paragraphs and Table 1 reports 2,000 positive training examples, and the paper never says whether the positives come from that same pool. If they do, at most 20 target paragraphs stay outside training and the reported 0.180 and 0.173 are close to training error, so the enrichment from about 1 percent to roughly 9 and 18 percent target share cannot be checked. Figure 1 has the same gap, since the distance estimate is described only as histogram binning, with no word on which variables are binned or which samples are counted.
Questions for authors
  1. For the weighted SVM and the logistic regression used in the experiments, what is the margin violation rate on the positive sample, and how does the resulting filter compare with the solution of the constrained problem in (1)?
  2. Are the 2,000 positive training examples drawn from the same 2,020 Wikipedia paragraphs that make up the target component of the mixture? If so, which target paragraphs are left out when the rates in Table 1 are computed, and if not, how were the two sets kept apart?
  3. Which variables or projections are histogrammed for the distance estimate in Figure 1, how are the bins chosen, and which samples enter the calculation? Does the estimate describe the full feature distribution or a projection of it?
2 comments

Thank you for your detailed and thoughtful comments.

Question 1: Our experiments do not use the exact solution to (1) because we show that it is NP-hard to solve this problem exactly (see Appendix G). This is why we instead use a simple convex relaxation — analogous to the standard ML practice of using convex relaxations such as hinge of logistic loss in ordinary binary classification settings. We provide details of additional simulations in the response to reviewer TDuq, where we also provide numbers on the percentage of points in the small target sample that violate the margin, as you requested. They are uniformly quite small.

For the MiniLM/BGE experiments, we do not know the appropriate margin, so it is impossible to say how many points violate it. This will be true in any real-world scenario.

Question 2: The 2000 positive training samples are distinct from the 2020 samples in the mixture.

Question 3: For Figure 1’s histogram, each trial compared the first coordinate x1x_1 of the 200 positive training examples with x1x_1 of the filtered examples, because this is the only coordinate that is relevant for separating S and O. Doing a full density estimation is difficult because of the curse of dimensionality.

We used 50 equal-width bins shared by both groups, spanning their pooled minimum minus 0.5 to their pooled maximum plus 0.5. After normalizing each histogram to sum to one, we computed 12∑j∣p^j−q^j∣\tfrac12\sum_j|\hat p_j-\hat q_j|. This measures discrepancy along the separating coordinate. The downstream accuracy used 5,000 fresh examples from SS.

We will incorporate these points in the revision.

I thank the authors for addressing my questions. I have no further questions and have decided to maintain my original score of 3, which I believe is a fair assessment.

Reviewer_yHvSOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to enlarge a small high-quality set by filtering a much larger mixed corpus theoretically. The filter is a linear classifier that keeps the seed points on the positive side and rejects as many corpus points as possible. The main guarantee is that the accepted points stay close to the target in total variation, with an error that shrinks as the seed and the corpus grow and that does not depend on the embedding dimension. The weaknesses and questions are fully proposed by myself insetad of LLMs.

Critical strengths
  1. Clear problem definition.
  2. The information-theoretic lower bound matches this rate and remains valid with unlimited samples from the corpus.
  3. The unknown-margin procedure is fully analyzed.
Critical weaknesses
  1. The guarantee requires one hyperplane that separates the whole target from the noise, with small overlap and a clear margin. Suppose instead that both the corpus and the target contain code, math, and exam problems, and the target differs only by being cleaner, possibly with different mixture weights. Embeddings usually cluster by topic, so clean code lies near noisy code. Does any form of the total-variation guarantee survive in this case? The easier task of keeping only code seems to fit the assumption; the quality-within-topic task does not. The experiments use Wikipedia against C4 and Gaussians already separated by the first coordinate, so they stay in the easier case.
  2. How can a practitioner check the assumptions on a real corpus? The margin, the overlap, and the noise proportion are not observed. The theorem also analyzes an exact zero-one program, while the experiments use logistic regression.
  3. Which empirical findings does this explain? It fits quality classifiers that pull a corpus toward a clean seed, as in GPT-3, RefinedWeb, and FineWeb-Edu. It is less clear how it covers LESS, perplexity filtering, deduplication, or domain reweighting.
Questions for authors

See weaknesses.

2 comments

Question 1: Good question! Please take a look at our response to reviewer TDuq who raises a similar technical issue regarding the case that the bulk distribution is a mixture with some S’S’ rather than SS. We show that so long as SS and S’S’ have bounded density ratios (which your particular example would likely satisfy), then our same procedure achieves the same result up to a factor of the density ratio..

Question 2: In practice, we recommend simply fitting a standard classification loss like logistic loss or hinge loss; these losses do not require pre-specification of the margin and are the standard convex relaxations even if the margin is known.

Question 3: Our results provide some theoretical backing for filtering methods used in certain pre-training data cleaning processes, such as the examples you mention (GPT-3, FineWeb-Edu, etc). There are of course other important parts of the data preprocessing pipeline such as deduplication that we do not analyze as they do not concern filtering.

Reviewer_yHvSOpenReview ↗

Response to Authors by Reviewer yHvS

Thank you for the response. My main concerns seem to be resolved. I'm raising my score.

Considering that I did not fully understand the details of theorem proof and implementation, I sincerely suggest the ACs, SACs, and PCs more consider the assessment of other reviewers, which may be more reliable.

Reviewer_TDuqOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper casts data filtering as learning from positive and unlabeled data: given NSN_S samples from a target distribution SS and NBN_B samples from a mixture B=pS+(1−p)OB = pS + (1-p)O, it seeks a filter ff such that BB conditioned on f(x)=1f(x) = 1 is close to SS in total variation. It assumes bounded features (∥x∥≤R\|x\| \le R) and that SS and OO are linearly separable with margin γ\gamma up to error rates εS,εO\varepsilon_S, \varepsilon_O. Under these assumptions, it analyzes a halfspace filter obtained from a constrained 0-1 program (keep the SS samples with margin, reject as many BB samples as possible) and proves dTV(Bf,S)≤O~(εS+εO/p+(R2/γ2)(1/NS+1/(pNB)))d_{TV}(B^f, S) \le \tilde O\big(\varepsilon_S + \varepsilon_O/p + (R^2/\gamma^2)(1/N_S + 1/(pN_B))\big), independently of the dimension (Theorem 7). Experiments train a class-weighted linear SVM or logistic regression on synthetic 50-dimensional data and on Wikipedia vs. C4 paragraphs embedded with two sentence encoders.

Critical strengths

Theory explains how the error depends on the number of target samples. The upper bound and the lower bound are proved carefully, with explicit constants. Together they show that 1/(γ2NS)1/(\gamma^2 N_S) is the right rate, up to logarithmic factors and R2R^2, even with unlimited bulk data, because the bulk samples carry no information about which component is the target (Observation 11). This is the main reason I find the paper informative.

The studied problem is important: many works aim at producing better data filtering, and data filtering is a critical component of any large scale training pipeline. Having more theoretically grounded methods and principles is good for the field. The paper is very easy to read and gives precious insights.

Critical weaknesses

The experiments do not really test the analyzed method, and they do not support the practical claims drawn from them.

  • Sec. 6 never runs problem (1) or the procedure of Sec. 5, instead, it trains a class-weighted linear SVM or logistic regression and accepts the points with positive score (l.417–419). It does not check whether this surrogate satisfies the constraint of (1) or reaches a comparable objective.
  • The parameter regimes in the experiments give vacuous bounds from the theorems
    • In Sec. 6.1, R2/γ2=9/0.01=900R^2/\gamma^2 = 9/0.01 = 900 exceeds both d=50d = 50 and NS=200N_S = 200. So even a dimension-dependent rate d/NSd/N_S would be tighter than the margin rate, and the explicit bound of Theorem 7 exceeds 5×1045 \times 10^4.
    • No experiment varies dd, γ\gamma, NSN_S or pp, so the dimension-free behavior in the title is never tested.
    • The conclusion at l.461–463 ("filter quality depends directly on embedding quality rather than dimension") seems unsubstantiated, since the two embeddings differ in both model and dimension,.

The guarantees require the high-quality part of BB to be distributed exactly as SS, which is unlikely in the settings that motivate the paper. The paper does not discuss this.

All results assume B=pS+(1−p)OB = pS + (1-p)O (l.62–63, 80–82), with access to samples from SS to build the filter. The motivating settings are ones where the target-like documents in BB follow some S′≠SS' \neq S, typically with the same support but a different density. For instance, this is a realistic assumption if we consider text from "textbooks or other authoritative sources" against a web crawl or fine-tuning data augmented with pre-training data.

This matters because the paper's case for relevance, "explicit distribution matching guarantees" for selecting LLM training data rests on this assumption. Two additions would address it:

  • a bound for the misspecified case, e.g. with an extra dTV(S′,S)d_{TV}(S', S) term under a bounded density ratio dS′/dSdS'/dS, which is what Theorem 6's proof (p. 14) would need;
  • an experiment in which BB is not built from SS's source.
Questions for authors
  • Are the FN and FP rates in Table 1 given by Pr⁡S[f=0]\Pr_S[f=0] and Pr⁡O[f=1]\Pr_O[f=1], and are they measured on paragraphs held out from training?
  • How do the results change when B=pS+(1−p)OB = pS + (1-p)O but where the target is S′S' with a different density, same support as SS? Would it be possible to have experiments in this direction?
3 comments
AuthorsOpenReview ↗

Response 1/2

Thank you for your detailed and insightful review! Please find our responses and additional experiment details:

Surrogate: Please note that problem (1) is NP-hard (see Appendix G; see lines 243--248). Our results are similar to the ones in statistical learning theory in which one might show that, eg, the 0-1 classification loss on a train set is related to the 0-1 classification loss on the population data (eg, [Shalev-Shwartz & Ben-David 2014, Chap 4 & 6]). Since we cannot actually minimize the 0-1 loss due to NP-hardness, we instead use the common convex relaxation for our simulations. In this way, our theory provides the overall intuition. We will include a new discussion of analyzing particular convex relaxations as a valuable follow-up direction.

Vacuous parameter regimes: We made no effort to optimize the constants in our theorems. In general, real world performance far outstrips the specific numerical predictions of theory. Instead, theory helps us understand the general effect of scaling different parameters (eg, dataset size). In our case, our theory suggests that even with relatively small NSN_S, we should be able to obtain strong filters; our experiments validate this.

Regarding varying d,γ,NS,pd, \gamma, N_S, p: We have conducted some more simulated experiments to probe these dependencies.

Below, Held-out FN is the false negative rate, $S$-only accuracy is the accuracy on “downstream task” using only the original small sample. The filtered accuracy is the accuracy using the filtered data, and the oracle accuracy is accuracy using an oracle filter. At high margins, the filter is near-perfect as expected.

γ\gammaHeld-out FNHeld-out FPSS-only accuracyFiltered accuracySource oracle
0.014.831.1286.7087.4694.81
0.052.520.2986.7091.1494.80
0.100.870.0486.7193.9494.81
0.250.030.0086.7294.8294.82
0.500.000.0086.7394.8294.82
1.000.000.0086.7494.8194.81

For d,NSd, N_S, and pp, we report values at both γ=0.01\gamma=0.01 and at γ=0.1\gamma=0.1. At the largest d values the convex relaxation becomes less accurate and we do see some mild degradation, we suspect this is due to being unable to perfectly solve the objective (1).

ddHeld-out FNHeld-out FPSS-only accuracyFiltered accuracySource oracleNSN_S with margin ≤γ\le\gamma (%)
101.92 / 0.010.68 / 0.0087.20 / 87.2089.22 / 95.3095.30 / 95.301.60 / 1.50
504.83 / 0.871.12 / 0.0486.70 / 86.7187.46 / 93.9494.81 / 94.810.60 / 0.60
10010.03 / 4.901.34 / 0.1586.32 / 86.3286.70 / 92.0594.47 / 94.470.10 / 0.20
20022.65 / 19.211.16 / 0.3285.66 / 85.6685.54 / 89.2994.11 / 94.120.00 / 3.90
NSN_SHeld-out FNHeld-out FPSS-only accuracyFiltered accuracySource oracleNSN_S with margin ≤γ\le\gamma (%)
5024.13 / 20.721.01 / 0.2784.08 / 84.0886.70 / 89.7794.34 / 94.350.00 / 0.00
10012.60 / 7.451.43 / 0.2184.59 / 84.5986.17 / 91.1694.45 / 94.470.00 / 0.00
2004.83 / 0.871.12 / 0.0486.70 / 86.7187.46 / 93.9494.81 / 94.810.60 / 0.60
5002.96 / 0.120.77 / 0.0090.99 / 90.9988.86 / 95.4395.49 / 95.511.20 / 1.16
1,0002.21 / 0.030.58 / 0.0093.62 / 93.6190.23 / 96.0196.00 / 96.011.72 / 1.88
ppHeld-out FNHeld-out FPSS-only accuracyFiltered accuracySource oracleNSN_S with margin ≤γ\le\gamma (%)
0.0023.55 / 0.240.66 / 0.0086.70 / 86.7184.54 / 89.4289.69 / 89.680.00 / 0.00
0.0054.17 / 0.490.91 / 0.0186.70 / 86.7185.68 / 92.0892.73 / 92.710.30 / 0.20
0.0104.83 / 0.871.12 / 0.0486.70 / 86.7187.46 / 93.9494.81 / 94.810.60 / 0.60
0.0205.89 / 1.521.35 / 0.0786.70 / 86.7189.35 / 95.1696.43 / 96.421.30 / 1.80
0.0508.52 / 3.391.50 / 0.1586.70 / 86.7192.15 / 96.8698.22 / 98.202.80 / 4.70

Regarding SS vs S’S’: It is indeed an interesting problem to consider such a mismatch; our results are robust to them. For example, consider your case of SS being textbooks and BB being a web-crawl. Since a web-crawl arguably “contains” all textbooks, we might imagine that p(S)/p(S’)p(S)/p(S’) is bounded in say [1/τ,τ][1/\tau, \tau] for some τ\tau. It is fairly straightforward to see that our results showing 1/NS1/N_S scaling apply in this case (because the constraint imposed by the small sample of NSN_S points is essentially unchanged). Moreover, we can also show that our results hold in general with an additive DTV(S,S’)D_{TV}(S,S’) term when SS is not equal to S’S’. We have added a final section to the Appendix (in the pdf revision) describing these results.

AuthorsOpenReview ↗

Response 2/2

Question 1: Yes to both.

Question 2: We re-ran our synthetic data experiments while shifting the mean of the SS component of BB (table below). This results in very little degradation in the results. As you suggest, it is indeed the case that if SS and S’S’ have densities with bounded ratios, then our results hold essentially unchanged.

To do this, we shifted the mean of S’S’ along the “downstream task” coordinate by varying amounts at both γ=0.01\gamma=0.01 and γ=0.1\gamma=0.1. As expected, we see a smooth degradation as the shift moves away from zero.

We will include the above points in the revision.

Δ\DeltaHeld-out FN on SSHeld-out FN on S′S'Held-out FP on OOSS-only accuracyFiltered accuracySource oracleNSN_S with margin ≤γ\le\gamma (%)
−1.005.20 / 1.4210.57 / 3.871.16 / 0.0887.99 / 87.9986.04 / 95.6299.20 / 99.210.80 / 1.05
−0.505.13 / 1.147.34 / 1.821.05 / 0.0487.99 / 87.9990.61 / 97.2798.97 / 98.960.75 / 1.05
−0.255.12 / 1.056.11 / 1.281.01 / 0.0387.99 / 87.9990.41 / 97.3498.55 / 98.550.80 / 1.00
0.005.11 / 0.965.14 / 0.950.97 / 0.0287.99 / 87.9988.92 / 97.1498.15 / 98.160.75 / 0.80
+0.255.10 / 0.914.32 / 0.750.93 / 0.0287.99 / 87.9987.12 / 96.3497.19 / 97.200.75 / 0.80
+0.505.10 / 0.873.79 / 0.670.89 / 0.0287.99 / 87.9985.88 / 95.4996.11 / 96.130.75 / 0.80
+1.005.17 / 0.883.27 / 0.760.85 / 0.0187.99 / 87.9984.76 / 91.8392.85 / 92.850.70 / 0.95

Dear authors,

Thank you for your response, which clarifies the paper. I have raised my score accordingly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.