Weak-to-Strong Generalization Through the Data-Centric Lens
Authors: Changho Shin
John Cooper
Frederic Sala
Venue: ICLR 2025 Poster (2025)
Keywords: weak to strong generalization
data-centric AI
Primary area: foundation or frontier models, including LLMs
TL;DR: We characterize data property that induces weak-to-strong generalization.

Abstract: The weak-to-strong generalization phenomenon is the driver for important machine learning applications including highly data-efficient learning and, most recently, performing superalignment. While decades of research have resulted in numerous algorithms that produce strong empirical performance, understanding what aspects of data enable weak-to-strong generalization has been understudied. We propose a simple data-centric mechanism that characterizes weak-to-strong generalization: the overlap density. Intuitively, generalization tracks the number of points that contain overlaps, i.e., both easy patterns (learnable by a weak model) and challenging patterns (only learnable by a stronger model), as with such points, weak predictions can be used to learn challenging patterns by stronger models. And, we provide a practical overlap detection algorithm to find overlap density from data. Finally, we provide an algorithm to learn, among multiple sources of data, which to query when seeking to maximize overlap density and thereby enhance weak-to-strong generalization. We provide a theoretical result showing that the generalization benefit is a function of the overlap density and a regret bound of our data selection algorithm. Empirically, we validate the mechanism and the overlap detection algorithm on a wide array of settings.

Published as a conference paper at ICLR 2025
WEAK-TO-STRONG GENERALIZATION THROUGH THE DATA-CENTRIC LENS
Changho Shin, John Cooper, Frederic Sala Department of Computer Science University of Wisconsin-Madie Madisso
(cshin23, j fcooper2, 2, fredsala la) @wi scisc.co edu
ABSTRACT
The weak-to-strong generalization phenomenon is the driver for important machine learning applications including highly data-efficient learning and, most recently, performing superalignment. While decades of research have resulted in numerous algorithms that produce strong empirical performance, understanding what aspects of data enable weak-to-strong generalization has been understudied. We propose simple data-centric mechanism that characterizes teak-to-stronn generalization: the overlap density. Intuitively, generalization tracks the number of points that tain overlaps, i.e., both easy patterns (learnalee by a weak model) and challenging patterns (only learnable by a stronger model), with such points, weak predic- tions can be used to learn challenging patterns by stronger models. We provide a practical overlap detection algorithm to find such points in datasets and leverage them to learn, among multiple sources of data, which to query when seeking to maximize overlap density and thereby enhance weak-to- to-strong generalization. We present a theoretical result showing that the generalization benefit is a function of the overlap density and regret bound for our data selection algorithm. Empirically, we validate the mechanism and the overlap detection algorithm on wide array of settings.
INTRODUCTION
recurring theme in machine learning the idea of less-capable entity (e.g., a weak model or an individual with limited expertise) supervising stronger, more capable one (a more powerful or higher- capacity system). The goal to enable the stronger entity to generalize beyond the capabilities of its weaker doumterpart-despite relying its supervision. This idea undergirds classical approaches (e.g., self self-training, co-training) for data-efficient learning that date back fifty years. Most recently, it drives embryonic attempts to perform superalignment- -the process of ensuring systems with capabilities far beyond those of humans align with human values (Burns et al.) 2023).
The typical flavor of works studying weak-to-strong generalization is to introduce techniques that, given a fixed dataset, can obtain the best performance (i.e., provide a strong model that best generalizes an unseen test set). A vast literature has studied thousands of techniques, including entire areas, such as semi-supervised learning (Zhu & Goldberg 2022 Ouali et al., 2020), co-training (Blum) Mitchell| 1998 Ling et al. 2009), pseudolabeling (Lee) 2013) Arazo et al. 2020), self-training (Scudder 1965] Amini et al.) 2023) student-teacht methods (Matiien et al. (202).. and more. Much less attention, however, has been focused on what aspects of the data enable such techniques to
succeed-aae and how to acquire additional data that further promotes weak-to-strone generalization.
This work focuses on this missing element. We begin by proposing simple mechanism that captures the potential for weak-to-stron, generalization. This measure, the overlap density, considers the potential presence of two kinds of patterns (i.e., sets of features or mechanisms for prediction) by weak and strong models-and hard pattern, only
within each datapoint: an easy accessible to the strong model. Intuitively, weak models can label points that have both patterns the overlapping points by taking advantage of the weak pattern (but cannot accurately label using the hard patterns). However, the strong model, using weak predictions obtained on overlapping points, can learn the harder patterns, and therefore generalize points only containing these hard patterns.

---

Published as a conference paper at ICLR 2025
Equipped with this intuition, we characterize the notion of overlap and provide theoretical results building on a recent theoretical framework for generalization (Lang et al. 2024). In practice. however, overlap points are latent, and it can be difficult distinguish between points with just an easy pattern and those with overlaps. To address this challenge, we introduce an approach for identifying points with overlaps and build on it obtain algorithm that can, when presented with multiple sources of data, estimate which one contains the largest overlap density. This suggests a future course of action for practitioners focused on maximizing weak-to-strong generalization: rather than focusing on algorithms, invest in the data and specifically into obtaining data from sources that are likely to produce the most overlaps.
Empirically, we first validate the presence of the mechanism in a variety of real-world settings. We use the tools we proposed to identify points with overlaps. This enables us to control how much data with overlaps is included. We do so in two important application areas,
Weak-to-strong generalization via fine-tuning. Here, tWO pretrained models are used as the weak and strong models. These have varying capacities, as in Burns et al. (2023),
Weak supervision. Weak supervision (Ratner et al., 2016 2018 Fu et al. 2020 is a framework for efficient data development. Multiple weak sources are combined via a label model, which serves as the weak model.
In both settings, we observe that scenarios with weak-to-strong generalization indeed correspond to overlap densiry. Next, we validate our proposed data source selection algorithm, showing enhanced data efficiency of pseudolabeled data across various datasets. We also include synthetic experiments confirming our findings and the effectiveness of our algorithm in controlled settings.
RELATED WORK
We give brief description of related areas. Our work is complementary to many of these, as focus is on understanding what forms of data promote weak-to-strong generalization and how to obtain more of it-rether than new frameworks training approaches. Extend related work is provided in Appendix
Self-Training and Data-Efficient Learning. Strategies that attempt train high-quality models with less labeled data date back to the infancy of machine learning (Scudder) 1965). This idea has spawned
entire fields, including semi-supervised learning (Zhu & Goldberg] (2022), weak supervision (Ratner iet al. 2016 Shin et al. 2022). self-training (Amini et al. 2023 Wei et al. 2022), and more. The key distinction between such works and ours is that we are not concerned with improving performance on benchmark datasets via algorithmic improvements. Instead, we seek to understand what aspects of data result in stronger performance-an how to obtain more the data that drives it.
Weak-to-Strong Generalization and Superalignment. A particularly interesting application of weak-to-strong generalization that of superalignment. Superalignment, in the narrow sense, the notion of aligning a superintelligent system to human values. More broadly, it can be thought of as aligning any large-scale system at a level of complexity beyond any individual person. As such systems may be far off into the future, researchers language models supervising larger and more capable ones (Burns et al. (023). Recently, several studies (Lang et al., 2024 Charikar et al. 2024; Somerstep al. (024) have proposed theoretical frameworks to understand weak-to-strong generalization. However, these works have yet to explore the specific data characteristics that facilitate weak-to-strong generalization. In contrast, our work provides a concrete characterization of the data that induces weak-to-stee to-sonn generalization: overlap density. Building on the theoretical framework from Lang et al. (2024), we derive new theoretical results that illuminate how overlap density drives weak-to-strone generalization.
currently studying proxies, such as smaller large
A SIMPLE DATA MECHANISM FOR WEAK-TO-STRON GENERALIZATION
Our goal is two-fold. First, seek to understand what properties of our data provide the possibility of weak-to-strong generalization. We introduce a simple mechanism (easy-hand haad overlap). formalize it, and provide theoretical result showing that it indeed characterizes generalization.
2

---

Published as a conference paper at ICLR 2025
Weak model provides accurate pscudolabels for easy-only and overlapping points based easy patterns.
weak
0.9
Accuracy
Easy only
Hard only
0.7
Overlap
w2s
0.6
Weak Model
Strong Model
W25
patterns overlapping points with accurate poeudolabels, generalizing to hard only region.
Weak-to-strorg
0.05
0.10
0.15
0.20
0.25
0,30
Overlap Ratio
(a) Overlap Density
(b) Weak-to-Strong Generalization
Figure 1: Left: overlapping easy and hard patterns in our dataset are the key to weak-to-strong generalization. Learning from overlapping points, where easy features and hard features coexist, enables weak-to-strong model fw2. that can generalize, while fweak is limited to reliably predicting points with easy patterns. Right: adding more such overlapping points has little influence on the performance of the weak model, but dramatically improves the performance of the weak-to-strong model. Adding such points-evt even a small percentage of the dataset- can push against the limits of the strong model.
Second, equipped with this mechanism, wish understand how maximize weak-to-strong generalization. Specifically, under a data budget and with access to multiple sources of data, how can we prioritize sources that lead greatest generalization? To address this challenge, we introduce simple algorithm that estimates which sources have the greatest overlap density.
3.1 THE OVERLAP DENSITY MECHANISM
We start with an extremely simple theoretical model; afterwards, we will comment on extensions that are likely to be encountered in real-life data. Nevertheless, perhaps surprisingly, the basic mechanism often tracks weak-to-strong generalization in real settings.
Setup. We have access to dataset Dirai I E X, E V. and D some distribution. In addition, we have access to a dataset Dw2s = (on+11..... In where we do not have access to any ground-truth labels. We weak model fweak and strong model fw2s- fweak trained (or fine-tuned) on D and used to output predictions Úū fweak(();) (I;) for points zj E Dw2s- fw2s is then trained fine-tuned the predictions provided by fwenk- Our goal is to understand in what settings the strong model sw generalizes better than the weak model fweak- despite only being trained on supervision obtained from Sweak.
(121.,1)..... (Ix, Mn)]. Here, (x,y) D,
models,
Dw2s with
Assumptions and Notation. For simplicity, we will assume that [Feasy: Ftana] where Teasy E Rday and Thard E Thod (in practice, this is not necessary). Here, Trasy are features producing easy patterns, learnable by the weak model, while Thard are hard patterns, which cannot be used by the weak model to obtain accurate predictions. In practice, feature vectors are not a priori decomposed into such patterns. To address this, we introduce an algorithm to estimate this identification later.
We note that any dataset D can be partitioned into
Dovertop: points containing both patterns, i.e., overlapping points,
Dhard only: points that only contain the hard pattern. For convenience, in our simplified model, we take Teasy for such points.
Deasy unly points that only contain the easy pattern. We take Thand = for such points.
D points that contain neither pattern.
These four possibilities (we ignore Dneiteer for simplicity) are illustrated Fig. (left.. This simple categorization explains the weak-to-strong generalization phenomenon.
After training, fweak has learned the easy pattern, and can therefore make reliable predictions on any points in Devertop Deasy only, these points contain the easy patterns. However, it will not be able to
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 UCB-Based Data Selection for Maximizing Overlap
Input: Data sources D1, D2,,.. ...,, DK, number of rounds T - K, sample size per round n, weak
model fweak
2: Output: Sampled data set D for weak-to-strong model training, Detected overlap samples Ó
3: Try each data source once, run Overlap Detection Algorithm (Algorithm 2). Initialize D, Ô with the sampled data and detected overlap data.
4: for t= 1 to 7' do
5: Compute the upper confidence bound (UCB) of overlap density in each source 8, log T (s), where (s(s) is # of trials for source s 6: Select the data source that maximizes UCB of overlap density.
(s) = (O(s)/|I(s)) + log
7: Run Algorithm 2 update D, Ô with the sampled data and detected overlap data.
8: end for
9:
Return Ō
make accurate predictions Drand only U D neitherr We denote the error rates as 81 61 (ac, y) E D Dovertap U D Deasy only) and E2 = P(weak (ar) * (ar, E Drand only U D neither). Thus, when labeling Dw2s. the predictions of fweak will be either reliable (in the first case), or highly unreliable (in the second case). Then, the labels for dataset D2 (labeled by fweak) are noisy with rates E1, E2.
[P (1) + y
Main assumptions
(A1). For any I E X', the features of x can be decomposed into easy and hard features, i.c. I. FFeay, Fhurd), where Teasy Rdwy and Thand R.hhut
(A2). The weak model Sweak has no access to hard patterns, i.e., for any x [Tewsy Thard),
f (weak(a) = fweak( (T), where ā [Tensy, 0).
(A3). We assume < $2, since fweak cannot use hard patterns in Daard only U D Decither.
Generalizing Beyond the Weak Model. Next, model fw2s is trained on dataset Dw2s with its noisy labels. Since fwis, by assumption, has the capacity to learn the hard pattern, it can do so in the presence of noise as well. This is a well-known observation (Natarajan al., 2013). Crucially, however, since the noise level for Drand only is typically severe, fw2. can only learn hard patterns from points Dowerlp- As result, the sample complexity for learning these hard patterns are given by [Doveinpl-nnd not the entire dataset size m.
At test time, fw2s has learned the easy patterns, and so will have a similar error rate as Swesk, but, unlike fweak. will have much smaller error rate on the hard patterns. We illustrate this idea in synthetic scenario in Figure I (right). Here, we observe three regimes. First, when there are very few overlaps (left), the weak-to-stree to-stoon model may struggle to learn the hard pattern, potentially compromising even its ability to predict easy ones. Afterwards, as the proportion of overlap points increases, the weak-to-strong. model begins to dramatically improve, correctly predicting on easy points while simultaneously learning the hard patterns. Finally, the weak-to-strong model's accuracy approaches that of the strong model trained on true labels (right-most region).
3.2 DATA SELECTION FOR MAXIMUM OVERLAP DENSITY
direct application of proposed mechanism is data source selection. Specifically, we consider the following common scenario. We have access to multiple sources of data, which we call Dı..... Dx- Given a limited budget to obtain unlabeled data points from these sources. which ones should we prioritize? Clearly, to maximize weak-to-strong generalization, we should target the sources D, with the largest overlap density. However, we face two challenges: (C1) we do not know a priori which sources have this property, and, (C2) even with access to data from these sources, overlaps are latent. That is, it is not clear how to distinguish between points in Dowerap and points in Deasy only-an as weak and strong models are both capable of accurate predictions such points.
We propose Algorithm [ to address these two challenges. For C1, we leverage stochastic bandit algorithms (Lattimore & Szepesvári 2020), which balance exploration and exploitation. Here, data sources act as arms, and their average reward correspond to overlap density. Using the UCB (Upper Confidence Bound) algorithm (Auer 2002), we explore underutilized data sources while exploiting
4

---

Published as a conference paper at ICLR 2025
Algorithm 2 Overlap Detection Algorithm
Input: Pscudolabeled dataset Dw2s. weak model fweak
2: Output: Overlap dataset, Doverlap
3: Step I: Separate Hard-only Points Using Confidence Scores
4: Calculate confidence scores {ci] where C; = arg max, w(Sweak (a:)) = j).
5: Identify hard-only points with threshold Thard CChangePoinDeetcction (c: i=1 1P
Duard only {x; E D w2s G Thadd
# Low confidence High confidence
Duon-hard only Dw2s Dhard only
6: Step 2: Identify Overlapping Points from hoon-hard only
7: Calculate overlap scores = max | #hard [haard Dant } for each 24 E Doon-hard only
8: Identify overlap points with threshold Toverlap =ChangePoinDDetcction
( Panndant only
Doverlap = {xr E non-hhard only |8; 2 Toverlap
# High overlap scores
9: return Doverlup
those with high overlap density. Each data source D, has an overlap density os, influenced by noise from the sampling process and overlap detection. Initially, we sample each source once. In subsequent iterations, we choose the source with the highest UCB. This computed as the sum the estimated overlap density and a confidence radius that promotes exploration (Algorithm A1).
To estimate the overlap densities, we must address C2. We propose an overlap detection algorithm
(Algorithm based on two insights from our data model in Section 3.1 i.e. x Teasy, Thard
Weak models are less confident on hard-only points because they lacks access to hard features.
Overlap points more closely aligned with hard-only points than easy-only points are.
We provide theoretical support for these in Section 4.2 Based on these, we use confidence scores to separate hard-only data points first, and then use the absolute values of inner products overlap scores to distinguish overlap points from easy-only points. In Algorithm 2, we first identify hard-only points by thresholding weak model confidence scores, split the dataset, and detect overlap points using inner products to distinguish them from easy-only points. We determine thresholds using change point detection technique (Sen & Srivastava 1975). The intuitions underlying our algorithms empirically validated in the experiments in Section where our overlap detection algorithm effectively isolates overlap points, leading to improved generalization.
THEORETICAL ANALYSIS
We introduce a theoretical result showing that weak-to-stie to-srong generalization is governed by the overlap density. Afterwards, we provide and interpret theoretical guarantees for our overlap detection and data source selection algorithms.
4.1 TTAK-TO-STRONN GENERALIZATION VIA OVERLAP EXPANSION
We build off of the framework in Lang et al. 2024), where generalization is governed by an expansion property. Specifically, we show that the model's pseudolabels on hard data points D only. since the pseudolabels produced by the weak model are (relatively) accurate on overlapping points and the strong model can learn hard patterns that address hard data points. We first introduce the relevant definitions and outline our setup.
model can correct the weak
Definition 1 (Expansion). (Lang et al. 2024) Fix sets A, B C X and neighborhood function N. We say the distribution Px satisfies (c, (. expannsio on (A, ifr all sets U B with IP B) q. P(N(U) A) > cP(
Definition 2 (rj-robust), (ang et al. 2024 For a classifier f and a point x, define r(f, x) = P(f(x') # fxx)(x' (x)) the probability of label disagreement between x and its neighbor x'. A classifier ff is robuuttt at x i(f. x) < n. The set of robbustt points for f is R, = {x r(f,)) S n)
5

---

Published as a conference paper at ICLR 2025
Problem Setup. We use the setup described in Section 3.1 Additionally, let S; represent the dataset whose labels are class i, Sooos be the correctly pseudolabeled subset of S, and Staa the incorrectly pseudolabeled subset of S.. With a little abuse of notation, we denote the true labeling function as y. Our goal is show how overlap density translates into the strong model's generalization on points in Daard only Via the expansion property. Our key assumption is that the data distribution and the weak-to-strong model behavior on Sgnnn n Poerrlp expands through the neighhorhood structure to Staa n Dhard only, where the weak model struggles with hard patterns, relying on robustness. This assumption captures the intuition that the strong model can learn patterns usable for predicting the hard points from the overlap points. We state a simplified version of the theorem first; the full version is in the Appendix [.I
Theorem 4.1. Suppose P satisfies (c. q) expansion on (Staad n Dhadd only, ggood O D Dovertap) for some O. Consider an arbitrary 17-robust classifier fwzs such that P "w (x) + fweak (x) at x18; n D Doveriap) 11-40 9- E1. Then, the classifier fw2n fuzs satisfies the following error bound:
err(Sw2s: DDDDD
hand ondy)) S &er([Jwass Swook SS O Dhard only) + 82
21 -erri err( S | O Dovertap) - (J22)) n Deveriup)
The full statement and proof are provided in Appendix [.T] and additional coverage expansion result is provided in Appendix [.2] We note that the bound is highly dependent the neighborhood function N which determines the parameters c and q. To understand the role of q, suppose that for any fixed q (0, 1), is optimal (i.e. any smaller value of fails the expansion criterion). Then, increasing 9 will cause e to increase as well, but we have a constraint g S P(fw2((x) * fweak (x) xlS, n Doverlap) E from rorobust condition, which subsequently constrains as well.
This bound demonstrates that weak-to-strong generalization is achievable as long as the over- lap density expands a sufficient extent (i.e., large c), the error rate in estimating the correct overlap density is low (i.e., small err(sw2s; [S n Devertap)) ,ad fuzs is adversarially robust
(..e small P( ((Rn(((wx)) (1 n Dovertap)) Specifically, when fwzs exactly replicates fweaks have err( err(fws, (| n D Drand only) = C2. We aim for a tighter bound than this. Pseudolabel correction is provably achieved when the right-hand side is less than E2, and the improvement of the bound over 22 can be quantified as
2c22 (I crr(fwaz fweakl Sgood n Dovertap) - 155 n Dovertap)
err(fw2ss fweak SS: n D only).
This result largely follows from the framework in Lang al. (202)) the upshot is that the overlap density mechanism is consistent with existing frameworks for weak-to-strong generalization. How- ever, as we shall soon see, it offers a critical advantage: it permits us operate with data-centric perspective that enables users to improve weak-to-stree -o-tong generalization.
4.2 THEORETICAL GUARANTEES FOR OVERLAP DETECTION AND DATA SELECTION
Equipped with the previous result, we provide a theoretical guarantee of our overlap detection algorithm under a Gaussian mixture assumption. We derive regret bound of our UCB-based data selection algorithm for overlap density maximization.
Overlap Detection. We provide a theoretical guarantee for the overlap score under the assumptions described in Section 3.1
i.e. x [Feway Thard,, where Teasy dod and Fiard E Rhhee Let
g(x) = [Zeasy 0) represent the input vector for the weak model, where hard features from x are zeroed
out. More detailed setup specific to this section is described in Appendix D.3 For x D D only- = [0, 0). so the weak model prediction probability is fweak (ar) = (0 x) = (0) = 0.5, which corresponds to the minimum confidence score. This ensures the perfect accuracy of detecting hard- only points using Algorithm with Thard = 0.5. Next, we aim to separate overlap points from easy-only points. Under the Gaussian mixture assumption in D.3 we have Xeasy only N(Peay, ef),
and Xoverlap N(Moverap:: cI), where Movertap [Measy Abard] Measy [Measy T T To show the effectiveness of overlap separation from easy-only points in Algorithm 2] we demonstrate that Xoverlap Xhard only and x x only Xhard only exhibit distributionally distinguishable gap.

---

Published as a conference paper at ICLR 2025
Overlap Regime
Medium Overlap Regime
High Overlap Regime
quartz
dream
polarity
0.75
0.70
LLM
0.00
0.90
0.55
0.60
0.80
0.55
Accuracy
0.50
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
10
cdr
Imdo
commercia
0.700
0.675
0.75
0.70
ws
0.225
0.5
0.600
0.80
0.7
Weat
0.55
0.0
0.2
0.4
0.6
0.8
1.0
0.00
0.2
0.44
0.6
0.5
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Overlap Density
Figure 2: Overlap density versus performance in weak-to-strong generalization with LLMs. Red lines show strong ceiling model accuracies, blue dashed lines represent weak model test accuracies, and W2S lines represent the accuracies of strong models trained on pseudolabeled data with controlled proportion of overlap density. general, the strong model's improvement over the weak model tracks the overlap proportion, suggesting that the overlap density is indeed important mechanism for generalization. We can observe three different regimes of weak-to-strome generalization in our experiments: low overlap regime, where the overlap density is insufficient for effective weak- to-strong generalization (here, few points contain overlaps, so choosing to rely on large overlap proportion translates to a small train set), a medium overlap regime, where the overlap density improves generalization but still yields performance close to that of the weak model, and a high- overlap regime, where the strong model's performance approaches that of the true strong model due to sufficient overlap points.
Theorem 4.2. Given the above setup, E overlap Xhard only) thermore, have
EixTrentap
E x easy only Xhard only)
|| Fur-
3 || 2
| 11 8c
IP Xoveerta Khard only
X Xeary only
Khand only)
S exp
(minn
min
16de2 + 18c ||
|
This result shows the average gap |bard between x Xoverlap Xhard only and x X Xhard only and the bound the probability that the overlap score of easy-only point exceeds that of an overlap point. The error bound result implies that the accuracy of the overlap detection algorithm deteriorates as the noise level and dimension d increase. The proof is provided in Appendix D.3
Data Selection. We provide a regret bound for our data selection algorithm (Algorithm [ which quantifies the gap in overlap density between selecting the optimal data source in every round and using our algorithm, which balances exploration and exploitation through the UCB algorithm. Let o(s) P(DoverappD,) be the population overlap density of source s, (s) [ be the empirical overlap density of source s at round f, and density. The following theorem establishes upper bound the expected average regret round I, Elo" ōr)-
max, o(s) be the optimal overlap
Theorem 4.3. Eio- - ōz] s 0 (V (O(VllogT/) logT/t) where is the number of data sources, T the total number of rounds.
For the details, refer to Appendix D.4 This result shows that the gap between the optimal and the empirical overlap ratio obtained with Algorithm decreases at of O (v (vlog T/T) in T. This implies that E[Ør] o² oT(T) T

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTS
We first validate the role of the data overlap mechanism in weak-to-strong generalization, examining Iwo cases; large language models following the setup of Burns al. (2023) and the weak supervision setting, where the weak model is a label model, often probabilistic graphical model. Next, we evaluate the effectiveness of our UCB- B-Beeddeddd data selection strategy from Algorithm Afterwards, we confirm our theoretical claims in a controlled setting, showing that the performance gains from overlap density primarily benefit hard-only data points, and that our data selection algorithm maximizes overlap density, improving weak-to-strong generalization. Our code is available at https://gg www./pprockeeaabbbttttcccco
c_w25
5.1 WEAK-TO-STRONE GENERALIZATION VIA OVERLAP DENSITY MECHANISM
We follow the approach in Burns al. (2023), where the goal is use large language models as proxies for weak agents supervising superintelligent agents. Our hypothesis is that the overlap density mechanism elicits weak-to-strong generalization this setting. We anticipate that higher overlap density generally enhances the performance of weak-to-strong models. Additionally, we hypothesize the existence of three regimes of veak-to-strong generalization from datasets can be observed depending on the amount of overlap data points in the dataset and the noise level of overlap detection.
Low overlap regime: Insufficient overlap points overly noisy detection hinder weak-to-strooe teak-to-strong generalization, leading to performance worse than sweak-
Medium overlap regime: Adequate overlap points and moderate noise levels enable weak-to- strong generalization, resulting in performance comparable to, or slightly better than, fweak-
High overlap regime: Sufficient overlap points with minimal noise in overlap detection induce strong reak-no-strong generalization, with performance approaching fauong.
Setup and Procedure. We split the original training data into two subsets, Duain and Dw2s- The weak models are trained on Duran and then generate weak labels for Dw2s- The weak-to-strong models subsequently trained on Dw2s using these weak labels. Using the overlap detection algorithm (Algorithm 2). we identified subsets Dvverlap and Dnonoveriap- and sampled recontrolled data points to control overlap density between 0% and 100%, creating the dataset D Doomtollld, where a denotes the overlap ratio. The weak-to-see to-soonn (W2S) models were then trained on Docatrolle, Crucially, the total quantity of overlap points is small (i.e., because the overlap density is small), building a dataset whose ratio is high translates into fewer overall points for training. Details on the distribution of detected easy-only, hard-only, and overlap points can be found in Appendix F
For the language model experiments, we followed the setup described in EleutherAl (202T). which replicates Burns et al. (2023). We used the Qwenl 0.5B model as the weak model and the Llama3 8B model as the strong model. We used linear probing based on the observation in Appendix D.2 of Burns et al. (223) that linear probing results often align with those from full fine-tuning. We used 19 datasets from EleutherA| (202I). For the weak supervision setting, we used datasets from the WRENCH weak supervision benchmark (Zhang al. 2021). We used Snorkel (Ratner al. 2018) as the label model (weak model), and a 4-layer MIP was used as the strong model.
Results. Figure 2 presents the results of this experiment. As expected, we observe that the strong model performance improves as the overlap proportion increases, providing evidence for the overlap density mechanism's 's role in weak-to-strong generalization. Also, were able observe three regimes of weak-to-strong generalization by our overlap detection method. We showcased each case in LLM and weak supervision settings, respectively. Full experimental results are provided in Appendix F.I Additionally, the ablation study on model architecture in the weak supervision setting presented Appendix F55) and the transferability study in Appendix F.6
5.2 DATA SOURCE SELECTION VIA OVERLAP DETECTION
Next, we validate our data selection procedure instantiated in Algorithm I We hypothesize that the UCB-based overlap maximization strategy leads to better weak-to-strong generalization by identifying the optimal data source given multiple sources with varying overlap densities.
8

---

Published as a conference paper at ICLR 2025
amazon polarity Train all samples
Estimated Overlap Ratio
Train overlap samples
Estimated Overtap Ratio
0.926
UCB
Accuracy
0.912
Accuracy
0.924
Raindoom
0.70
UCB
0.910
0.922
Random
0.65
0.906
0.60
0.904
Random
0.910
10
13
20
25
10
15
20
25
10
Round
Round
Round
dream Train all samples
Estimated Overlap Ratio
Train overlap samples
Estimated Overtap Ratio
0.59
0.60
Accuracy
Accuracy
0.58
0.50
Random
0.57
0.45
Random
0.56
Random
5
10
15
20
25
10
15
20
25
10
15
Round
Round
Round
Figure 3: Data selection results with Algorithm for Amazon Polarity and DREAM datasets. We report the average of 20 repeated experiments with different seeds. We observe that the data source selection procedure, based overlap density estimation, can produce enhancements random sampling across data sources.
Setup and Procedure. We used a similar setup and datasets as in the large language model experi- ments. Overlap density in the training sets was identified using our proposed method (Algorithm ( and the weak-to-strong training dataset was split into D1 and D2 with overlap densities of 0.9 and 0.1, respectively. With these two data sources, ran Algorithm and compared its performance random sampling. The number of rounds was set to T 25.
Results. The results presented in Figure 3 We observe that the (CB-based overlap maximization algorithm can lead to better weak-to-strong generalization. We note that we do not always expect to obtain results such as those in Figure 3 Indeed, there simply are very few overlap points-or if the procedure for identifying them is very noisy we will not observe these types of results or any type of weak-to-strong generalization. Full experimental results are provided in Appendix F2
5.3
SYNTHETIC EXPERIMENTS
We verify our overlap density mechanism and data selection algorithm in fully controllable settings.
5.3.1 OVERLAP DENSITY MECHANISM
We validate the claim that overlap density enhances the performance of a weak-to-strong model on hard data points, while the weak model exhibits random accuracy on those same points.
Setup and Procedure. We simulate weak-to-strong generalization using a simple mixture of Gaussians setup with logistic regression models, described in Section 3 In this setup, the hard features are intentionally blocked (set to 0) for the weak models to mimic the common scenario where weak models lack access to these features. Full details are provided in Appendix [E] The weak model Sweak is trained on dataset Derain and generates pseudolabels for Dw2s- The weak-to-strong model Jwz then trained on Dwzs using these pseudolabels and evaluated on Dres- We set Neasy = 100 and Thard 100, incrementing nooerrlap by 5 in each iteration. The performance of the weak-to-strong model is assessed on easy-only, hard-only, and overlap data points in the test set, respectively.
Results. Figure illustrates how accuracy varies with the overlap ratio across easy-only, hard-only, and overlap data points. As expected, the most substantial performance improvement over the weak pseudolabeler occurs on the hard-only data points. On the casy-only data, the weak-to-strong model initially underperforms compared to the weak model due to label noise. However, as the overlap density increases, the weak-to-strong model's performance approaches that of the weak model. On

---

Published as a conference paper at ICLR 2025
(a) Easy Accuracy
[b) Hard Accuracy
(c) Overlap Accuracy
1.0
Accurary
0.8
Whak Model Strong Model W25
Weak Model
Weak Model
Strang Model
Strang Model
W25
W25
0.1
0.2
0.3
0.1
0.2 Overiap Ratio
0.3
0.1
0.2 Overiap Ratio
0.3
Overiap Ratio
Figure 4: Accuracy in each data region in synthetic experiments. As expected, the performance gain mainly comes from hard data points as the overlap density increases.
Estimated Overlap Ratio
Accuracy
Estimated Overiap Rati
Oradle
UCB
Rendom
0.58
Weak
0.3
0.56
Oracc
0.54
Random
0.52
20
Raund
Round
Figure 5: Synthetic data selection experiment. Our algorithm demonstrates better data efficiency than random sampling by consistently identifying the data source with the highest overlap density.
overlap data points, the weak-to-strong model also starts off performing worse due to similar label noise, but as it learns hard patterns, eventually outperforms the weak model.
5.3.2 DATA SOURCE SELECTION
We validate the claim that the algorithm effectively identifies data sources with higher overlap density and progressively maximizes it with each round, leading to improved weak-to-strong generalization.
Setup. We set K data sources, each characterized by different overlap densities: [0.1, 0.15, 0.2, 0.05, 0.8). For the nonoverlap distribution, assumed that the half of the nonoverlap distribution is easy-only, and the rest half is hard-only. We compare our data source selection algorithm against random sampling and oracle setting, where data always sampled from the data source with the optmal overlap density. In each round, 100 data points were sampled from the selected data source, with the total number of rounds set to T = 50.
Results. Figure prresents the experimental results. As the rounds progress, our algorithm increas- ingly identifies the optimal data source, achieving better weak-to-stron teak-to-strong generalization compared to random sampling. Additional experimental results on easy-only and hard-only training are provided in Appendix along with a sensitivity analysis for overlap detection noise in Appendix [F.4
CONCLUSION
We studied a data-centric mechanism that explains weak strot generalization. This mechanism is centered on easy-hard overlaps: points where weak models leverage easy patterns for accurate labeling, while strong models learn hard patterns to generalize to hard-only points. We studied this idea conceptually, theoretically, and empirically; the latter in multiple popular settings. Finally, introduced algorithms for identifying overlapping points and determining, given a limited data budget, which data sources should be queried maximize weak-to-strong generalization.
Our study was limited to a simple version of what is likely to be a more complex mechanism in many realistic settings. We are interested in extending this work in several directions. These include allowing more complex patterss (multiple levels of overlapping difficulties). further theoretical results, and studying additional variations for the overlap identification procedure.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We are grateful for the support of the National Science Foundation (NSF) (CCF2106707), the Defense Advanced Research Projects Agency (DARPA Young Faculty Award), and the Wisconsin Alumni Research Foundation (WARF).
REFERENCES
Chirag Agarwal, Daniel D'souza, and Sara Hooker. Estimating example difficulty using variance of gradients. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pullern Recognition, pp. 10368-10378, 2022.
Massih-Reza Amini, Vasilii Feofanov, Loic Pauletto, Lies Hadjadj, Emilie Devijver, and Yury Maximov. Self-training: A survey, 2023.
Zachary Ankner, Cody Blakeney, Kartik Sreenivasan, Max Marion, Matthew Leavitt, and Mansheej Paul. Perplexed by perplexity: Perplexity-based data pruning with small reference models. arXiv preprint arXiv:24405.2 20541, 2024.
Eric Arazo, Diego Ortego, Paul Albert, Noel O' O'Connor, and Kevin McGuinness. Pseudo-labeling and confirmation bias in deep semi-supervised learning. In 2020 International joint conference on neural networks (IJCNN), pp. 1-8. IEEE, 2020.
P Auer. Finite-time analysis of the multiarmed bandit problem, 2002.
Robert Baldock, Hartmut Maennel, and Behnam Neyshabur. Deep learning through the lens of example difficulty. Advances in Neural Information Processing Systems, 34:10876-10889, 2021.
Qiang Ning Ben Zhou, Daniel Khashabi and Dan Roth. "going on vacation" takes longer than "going for a walk": study temporal commonsense understanding. EMNLPP 2019.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training. In Proceed- ings of the Eleventh Annual Conference Computational Learning Theory, 1998.
Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschenbrenner, Yining Chen, Adrien Ecoffet, Manas Joglekar, Jan Leike, et al. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. arXiv preprint arXiv:2312.099390, 2023.
Marco Campi and Simone Garatti. Compression, generalization and learning. Journal of Machine Learning Research, 24(339): 2023.
Moses Charikar, Chirag Pabbaraju, and Kirankumar Shiragur. Quantifying the gain in weak-to-strong generalization. arXiv preprint 2:Xiv:2405./5116 2024.
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794, 2016.
Christopher Clark, Kenton Lee, Ming- Ming-Wei Chang, Tom Kwiatkowski. Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 1924-2936, 2019.
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni, Analysis of perceptron-based active learning. In International conference computational learning theory, pp. 263.263. Springer, 2005.
Ran El-va and Yair Wiener. On the foundations of noise-free selective classification. JMLRR, 11: 1605-1641, aug 2010. ISSN 1532-4435.
EleutherAI. Weak to strong generalization: Some theoretical perspectives.
https://blog
tttttkoottotttttg/oooooo 2021. Accessed: 2024-09-26.
11

---

Published as a conference paper at ICLR 2025
Daniel Y. Fu, Mayee F. Chen, Frederie Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré. Fast and three-rious: Speeding up weak supervision with triplet methods. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020). 2020.
Deep Ganguli, Liane Lovitt, Jackson Kernion, Amanda Askell, Yuntao Bai, Saurav Kadavath, Ben Mann, Ethan Perez, Nicholas Schiefer, Kamal Ndousse, et al. Red teaming language models to reduce harms: Methods, scaling behaviors, and lessons learned. arXiv preprint arXiv:2209.07888 2022.
Yonatan Geifman and Ran Yaniv. Selective classification for deep neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pp. 2242-2251. PMLR, 2019.
Steve Hanneke. Theory of disagreement based active learning. Found. Trends Mach. Learn., 7(2-3): 131-309, jun 2014, ISSN 1935-8237.
Lifu Huang. Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Cosmos qa: Machine reading comprehension with contextual commonsense reasoning. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) pp. 2391-2401, 2019.
Alan Karr, Ashish P Sanil, and David L Banks. Data quality: A statistical perspective. Statistical Methodology, 337):337 2006.
Daniel Khashabi, Snigdha Chaturvedi, Michael Roth, Shyam Upadhyay, and Dan Roth. Looking beyond the surface: A challenge set for reading comprehension over multiple sentences. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pp. 252-262, 2018.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1885-1894, PMLR, 2017.
Hunter Lang, David Sontag, and Aravindan Vijayaraghavan. Theoretical analysis of weak-to-strong generalization, 2024. htttps:::////txii/ hacp////////// absaac/s/4000 16043
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In ICMI. Workshop on Challenges in Representation Learning, 2013.
Jeffrey Li, Alex Fang, Georgios Smyrnis, Maor Ivgi. Matt Jordan, Samir Gadre, Hritik Bansal, Etash Guha, Sedrick Keh, Kushal Arora, et al. Datacomp-Im: In search of the next generation of training sets for language models. arXiv preprint arXiv:2406.1 / 1794, 2024.
Charles X. Ling, Jun Du, and Zui-Hua Zhou. When does co-training work real data? In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD) 2009, 2009,
Tambet Matiisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Ibrahim Naji. TSATC: Twitter Sentiment Analysis Training Corpus. In thinknook, 2012.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances in neural information processing systems, 26, 2013.
Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kicla. Ad- versarial nli: A new benchmark for natural language understanding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2020.
Yassine Ouali, Céline Hudelot, and Myriam Tami. An overview of deep semi cemi-supervised learning. arXiv preprint a 20Xiv:2006.0522 2020.
12

---

Published as a conference paper at ICLR 2025
Dario Paccagnan. Marco C. Campi, and Simone Garatti. The pick-to-learn algorithm: empowering compression for tight generalization bounds and improved post- coat-traiing performance. NIPS '23. Curran Associates Inc., 2024.
Mohammad Taher Pilehvar and Jose Camacho-Collados. Wie: the word-in-context dataset for evaluating context-sensitive meaning representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 1267-1273, 2019.
A. J. Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, and C. Ré. Data programming: Creating large training sets, quickly. In Proceedings of the 29th Conference Neural Information Processing Systems (NIPS 2016), Barcelona, Spain, 2016.
Alexander Ratner, Stephen H. Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. Snorkel: Rapid training data creation with weak supervision. In Proceedings of the 44th International Conference Very Large Data Bases (VLDB), Rio de Janeiro, Brazil, 2018
Anna Rogers, Olga Kovaleva, Matthew Downey, and Anna Rumshisky, Getting closer to complete question answering: A set of prerequisite real tasks. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secone Innovative Applications of Artificial Intelli- gence Conference, IAAI 2020, The Tenth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 8722 8731, AAAI Press, 2020. URL www..aaaaaaa.oaaaaaaaaaaaaaaa..a org/ o j index. php/ AAAI wttaa//articeeevieeeee 6398
Maarten Sap, Hannah Rashkin, Derek Chen, Ronan Le Bras, and Yejin Choi. Social iqa: Common- sense reasoning about social interactions. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 4463 4473, 2019.
H. Scudder. Probability of error some adaptive pattern-recognition machines. IEEE Transactions on Information Theory, 1965.
Nabeel Seedat, Fergus Imrie, and Mihaela van der Schaar. Dissecting sample hardness: fine-gras fineigrained analysis of hardness characterization methods for data-centric ai. arXiv preprint arXiv:2403.04531 2024.
Ashish Sen and Muni S Srivastava. On tests for detecting change in mean. The Annals of statistics, pp. 98-108, 1975.
Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Universal- izing weak supervision. International Conference on Learning Representations, 2022.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Mamning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1641-1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL https: www acl web. org/ wttp://anntoooogg///33---------.
Seamus Somerstep, Felipe Maia Polo. Moulinath Banerjee, Ya'acov Ritov, Mikhail Yurochkin, and Yuekai Sun. A statistical framework for weak-to-strong generalization. arXiv preprint 2.Xi::2405.162366 2024.
Kai Sun, Dian Yu, Jianshu Chen, Dong Yu, Yejin Choi, and Claire Cardie. Dream: A challenge data and models for dialogue-based reading comprehension. Transactions of the Association for Computational Linguistics, 7:217-231, 2019.
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. Easy-to-hard generalization: Scalable alignment beyond human supervision. arXiv preprint 2xXiv:2403.09472. 2024.
Oyvind Tafjord, Matt Gardner, Kevin Lin, and Peter Clark. "quartz: An dataset of qualitative relationship questions". "2019".
13

---

Published as a conference paper at ICLR 2025
Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 167:107299, 2020.
Martin J Wainwright. Hligh-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Alex Warstadt, Amanpreet Singh, and Samuel Bowman. Neural network acceptability judgments. arXiv preprint vrXXiv/805 /2471, 2018
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self self-training with deep networks on unlabeled data. International Conference on Learning Representations, 2022.
Johannes Welbl, Nelson F Liu, and Matt Gardner. Crowdsourcing multiple choice science questions. In Proceedings of the 3rd Workshop Noisy User-generated Text, pp. 94-106, 2017.
Alexander Wettig, Aatmik Gupta, Saumya Malik, and Danqi Chen. Qurating: Selecting high-quality data for training language models. arXiv preprint arXiv:2402.09739, 2024.
Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, and Danqi Chen. Less: Selecting influential data for targeted instruction tuning. In Forty-first International Conference on Machine Learning, 2024.
Sang Michael Xie, Shibani Santurkar, Tengyu Ma, and Percy Liang. Data selection for language models via importance resampling. Advances in Neural Information Processing Systems, 36: 34201-34227, 2023.
Zhengyuan Yang. Zhe Gan, Jianfeng Wang, Xiaowei Hu, Yumao Lu, Zicheng Liu, and Lijuan Wang. An empirical study of gpt-3 for few-shot knowledge-basee vqa. In AAAI, 2022.
Jinsung Yoon, Sercan Arik, and Tomas Pfister. Data valuation using reinforcement learning. In International Conference on Machine Learning, pp. 10851. PMLR, 2020.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4791-4800, 2019.
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. Wrench: A comprehensive benchmark for weak supervision. arXiv preprint arXiv:2109.11377 2021.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Yuan Zhang, Jason Baldridge, and Luheng He. PAWS: Paraphrase Adversaries from Word Scrambling. In Proc. of NAACL, 2019.
Xiaojin Zhu and Andrew B Goldberg. Introduction to superviee learning. Springer Nature, 2022.
14

---

Published as a conference paper at ICLR 2025
APPENDIX
The appendix contains additional details, proofs, and experimental results. The glossary (Appendix A contains convenient reminder of terminology. Appendix B provides more related works and discussion about the relationship between our work and related papers. In Appendix we describe the details of our algorithms and discuss their implementations. Appendix [ provides the proofs of theorems that appeared in Section 4 Finally, we provide additional details and analysis of the experiments in Appendix Eld present further experimental results Appendix
A GLOSSARY
The glossary is given in Table A1
Symbol
Deñiition
Total number of samples
X
Feature space
Label space
2(-)
Underlying labeling function
D
Data distribution
D easy only
Set of data points that only contain the casy patterns
D bard only
Set of data points that only contain the hard patterns
D overlap
Set of data points containing both easy and hard patterns
D train
Labeled training set for weak model
D Dw2s
Unlabeled pseudolabeled training set for weak-to-strom models
D controlled.c
Sampled dataset from Dw2s with the controlled overlap ratio as a Weak model
fweak
Suunng
Strong model fine-tuned with true labels
fw2
Weak-to- treak-to-strong model (Strong model fine-tuned with pseudolabels generated by weak model)
E1
Error of weak model in easy-only and overlap, TP[ (I:) * y (xr, y)
D Doverlap U Deasy only)
82
Error rate of weak model in hard-only points, ((fweak(x) # y (ar, v)
Dhard only U Deeitbee)
S
Covered data points of class
Sgood
Correctly pscudolabeled data points class Incorrectly pseudolabeled data points of class Uncovered data points of class i Overlap density for specific data source s Best overlap density of all the data sources Empirical overlap density of data source s round Number of data selection rounds i-th data source
shad
T;
((s)
o"
(s)
T
D:
D
Sampled data from data sources Detected overlap points in D
O
D,(s)
Sampled data from data source up to round
(((s)
Detected overlap points sampled from data source up to round t
Table Al: Glossary
B EXTENDED RELATED WORK
Theory of Weak-To- To-Strong Generalization. Several theoretical approaches have been proposed to explain weak-to-strong generalization, reflecting growing interest in this area research. Somerstep et al. (2024) frame knowledge from weak models transferred to strong models. They propose label refinement to address the limitations of naive fine-tuning on pseudolabels, i.e. naive fine-tuning often leads the
generalization transfer learning problem, where latent
15

---

Published as a conference paper at ICLR 2025
strong model replicating the errors of the weak models. Charikar et al. (2024) present a theoretical
framework rooted in convex analysis to explain weak-to-strong generalization They suggest that the disagreements between strong models and weak models' pseudolabels predicts weak-to-strong generalization performance. This aligns with our theory, where a strong model trained on overlap density corrects pseudolabels hard data points. Finally, [Lang et al. (2024) introduce a framework that explains pseudolabel correction and coverage expansion based on the expansion property and model robustness. We specifically characterize where such expansions occur and provide both theoretical and empirical validation of how they lead to weak-to-stron generalization.
Evaluating the Difficulty of Data Points. has long history. There are several ways to define hardness in supervised learning alone. These include closeness to the decision boundary, as in active learning (Dasgupta et al., 2005 Hanneke 2014), low-confidence points, as in selective classification (EI-Yaniv & Wiener] 2010; Geifman & EI- Yaniv 2017). points (or sets of points) with high values of the loss function, and heuristic rules applied to the data (Sun al. 2024). Agarwal et al. (2022) assess sample difficulty by examining the
The idea that certain points are more difficult than others
variance of gradients during training. Baldock et al. (2021) employ deep neural networks, operating under the intuition that difficult samples are more likely to be predicted in higher layers when using linear probing at each layer. (Sedat et al. (2024) provide a comprehensive survey and taxonomy of data hardness characterization, along with a benchmark for comparing different methods. However, none of these studies address overlapping data points, which contain both easy and hard patterns and could be crucial for understanding weak-to-strone generalization.
Data Valuation. A large number of works have studied ways to understand the impact of each point in a training dataset on the performance of the resulting model. These include approaches via influence functions Koh & Liang (2017). Shapley values GGhorann & Zou (2019), and other methods Karr et al. (2006); Yoon et al. (2020). The main difference between these works and ours is that we are less concerned with any single point and model training in general, but with an overall data mechanism that is relevant to the weak-to-strong generalization setting.
Data Curation and Selection Selecting subsets of data to achieve better performance with less data has been extensively studied, particularly in the context of foundation model training. Xie et al.) (2023) introduce Data Selection with Importance Resampling (DSIR), which selects pretraining data for language models by estimating importance weights in a reduced feature space, aligning the selected data distribution with desired target distribution. Similarly, AAnknr et al. (2024) use the perplexity of smaller models to curate pretraining datasets, while WWttig et al. (2024) employ quality qualifiers to assign scores and steer data curation process. Xia et al. (2024) use inffuence functions to curate instruction-tuning datasets. Finally. [i et al.] (2024) present DataComp for Language Models (DCLM), a benchmark designed to evaluate dataset curation strategies within general data curation pipeline for pretraining large language models. Our overlap detection process aligns with the broader theme of data curation but is specifically tailored the context of weak-to-strong generalization.
In a more general context, Campi & Garatti (2023) introduce a theoretical framework for compression functions in learning. laying the foundation for data selection methods. Building on this framework, Paccagnan et al. (2024) propose Pick2Learn (P2L) meta- algorrtggii framework, which iteratively selects data subsets until a specified appropriateness criterion satisfied, producing compressed dataset that preserves most of the relevant information. While the concept of overlap density bears conceptual resemblance to the output of the P2L algorithm- both aim to identify data subsets that generalize effectively, overlap density explicitly addresses the noise inherent in pseudolabels generated by weak supervisors, making it particularly suited for weak-to-strong generalization. Nonetheless, P2L algorithm could potentially be adapted for overlap detection, provided appropriate criterion for overlap identification is defined within its framework.
C ALGORITHM DETAILS
We provide the detailed version of Algorithm T Algorithm
Al and discuss details of Algorithm 2
Threshold selection. For the thresholds in Algorithm we used a change point detection algorithm, specifically the binary segmentation method (Sen & Srivastava 1975). applied to the sorted confidence
16

---

Published as a conference paper at ICLR 2025
Algorithm A1 UCB-Based Data Selection for Maximizing Overlap (Detailed)
Input: Data sources D1, "2,...,,D) Dg. the number of rounds: T K, sample size per round: n,
weak model: fweak
2: Output: Sampled data set D for weak-to-strong model training, Detected overlap samples Ó
3: Initialization: D = 0, O = ()
4: Try each data source once
5: for
to K do
6: A: I, Sample n points S.(k) = (x1,..... In from D3
7: Do pscudolabeling of samples using the weak model: S((k) <- fwekkk((( S((k)
8: Initialize Dz( <- (kk,, Update D +- D U (k)
9: Detect overlap points (z(k)) in (k) using Algorithm 2 initialize Os(k) Os(k), Ó (k).
10:
Initialize choice count: ng (k)
11: end for
13:
# Choose data source in each round based on UCB (Upper Confidence Bound)
for K + 1 T do
15:
For each l: = 1 to K do
10)-
2 2 T
16:
Compute UCB score: UCB
Dr [k)1
(k)
17:
Select data source: k* <- arg maxk (k)
Sample points (k) .T, from D2
19:
Label new samples using fweak and do pscudolabeling with fweak
20:
Detect overlap points (k) (k: using Algorithm 2
21:
De(k*) D US (k)
D.-1(k) for & & k. D DUS
22:
Oz(k*) + (k*) UO (k) t -0,11 (k) for k & k 000
23:
Increment choice count: nz (kk)) +- -f(-1(kk)) (k) + π4 for
24:
end for
25:
Return D
and overlap scores. The implementation used the ruptures Python package (Truong et al. 2020). Change point detection methods identify points where statistical properties a data sequence shift. In our approach, we assume that the distributions of confidence scores and overlap scores vary across hard-only, easy-only, and overlap regions, allowing the change point detection method to identify these differences. Alternatively, segmentation methods like K-means clustering could also be used for this purpose.
Overlap scoring. While we provide theory for inner product scores and taking maximum as our algorithm to identify overlap density, we used the absolute value of the cosine similarity in large language model experiments and weak supervision experiments after testing various statisties like mean, median, 75th percentile, and Euclidean distance instead of the inner product. The core intuition is that overlap points are closer in distribution to hard-only points than to easy-only points. We anticipate other measures could capture this intuition, with influence functions (Koh & Liang 2017) being promising alternative for future work. Additionally, when using neural networks, we computed overlap points from the last layer activations rather than the inputs, this provided clearer signals practice.
D THEORY DETAILS
D.I PROOF OF THEBREM
We provide a theoretical result building off Lang et al. (2024). The main idea is that the strong model generalize better by learning from overlap data points, which leads to the expansion property and pseudolabel correction phenomenon in Lang et al. (024). We begin by adopting the definitions from Lang et al. 2024
17

---

Published as a conference paper at ICLR 2025
Notations. Let x denote random variable with distribution D, and x represent its realizations.
We assume the existence of a ground-truth labeler y : X' + y = I....,k k and a weak model (pseudolabeler) fweak X + (U which assigns to each z either label from Y or the abstention symbol Ø3.
Define 5= fx: 1 (weak (x) + 2 as the covered subset of X' (the set with pseudolabels), and {x [weak(r)= -] X' S as the uncovered subset. Training occurs on the pseudolabeled
source subset S, and evaluation spans both S and the uncovered larget T. Let {X; } be partition of X where the ground-truth label is constant in each X; (e.g.. X; {- y(x) i)). We use this partition for convenience, but our results generalize to other partitions. S and T are partitioned into S; SnX, and T; = T n R4, respectively. Finally, each S; is divided into correctly pseudolabeled examples Spund {x E S [w)ak(x) = )(x)} and incorrectly pseudolabeled examples Spad S; S
Definitions. For two classifiers /.g: X - y and a set U C X. we define err(S. as the probability of disagreement between J and y conditioned on x E U, i.e., P(]((x) + g(x) x E U). The probability is over x ~ D. which we often omit for simplicity. We focus on classifiers that minimize the error the non-abstaining weak labels within the strong model hypothesis class F, i.e,, approximate solutions to arg min ser (f [weak (S). Our goal is to derive upper bounds on the error ef D), which represents the classifier's 's error on the true labels on some D C X.
Definition 3 (Neighborhood), (Lang al. (024) Let N be a neighhorhood function that maps each point x to a set of points ((x) C X that we call the neighborhood of I. We will assume that N satisfies x E ex')) > x' E (xx), i.e. that the neighborhoods are symmetric. We can extend N to a function of sets as ((A) = A
Examples to keep in mind are (()) = {z' [1ıp(x)) - S r for some representation @p : X + R. or, in the case of text inputs x, the set of fluent paraphrases of x. However, our results work with any definition of N.
Definition 4 (Example graph). (Lang et al. 2024) Let G G= (X, E) be a graph with nodes representing elements of X (assumed to be finite but possibly very large), where two nodes (xr, x²) are connected if I E (xx) (or equivalently, x' E (N))),, with edge weight u(z,2') = P2)))(22))((r E [N²2)).
Definition 5 (17-robust neighborhood size). (Lang et al. 2024) For sets A,U C X, the size of the n-robust neighborhood of U in is: Pi-,(U, A) = (P(VA) : wVV.U) z (1
()))(N(U)
Definition (Expansion). [Lang et al. 2024g Fix sets A, C X. We say the distribution Px satisfies (c. 9) expansion on (A, B) if for all sets U C B with B)U > q. P()(U))A) > (U).
2024) A collection M of subsets of B Definition 7 (Expansion of a set collection). Lang el al.
satisfies (c. q) exxpansion on (A, B) for all U E .M with P PU
B) q. (P))( > cB)
Definition 8 (Robust expansion). (Lang et al. 2024) A collection M satisfies (c, q. -roobust ex- punsion on (A, B) ifr all U E M with P(U 4 (U, A) > cP(UU B). This recovers Desinition 7 when 1) = 0.
Lemma D.1 (Lang et al. ). For a set A C X and classifier f. if if +
f(x') S y for some 0, then for any 17 0, (R,,(())A)) S 7.
Good and bad edges. (ang et al. 2024 For a classifier f. set U X, and x' E E x E EN)).
the pair (zx, x²) is bad if f(z) * f(x'); otherwise, it is good. Let N(U) be the subset of (U) reachable by good edges. That is. N(x²)= = (= E N(x'): (x, good} and ((A)) = A The dependence of V on ff is omitted for notational simplicity. If f is 17-rbust all points in U, then bad edges account for little of the weight between ((tceenN(U)))) (U) and U' in the example graph (Definition
4 Thus, if robust expansion is large and f is n-robust on U, the neighborhood (U) reachable by good edges must also be large.
Lemma D.2 (Lang et al. (2024)). ). For any set U C X where f satisfies r(f,x) S for all x E U (i.e., U (f),, we have: w(N(U), U) 2 (1 T))(N(U).UU)
Expanding set family. (ang et al. 2024) Let F be the hypothesis class of the strong model, the ground function, and B X. For each f E F, define the mistake set U(B f) = {a B fxx A )(z)). Then, the family of 17-robust mistake sets is:
Mn
18

---

Published as a conference paper at ICLR 2025
Similarly, define the family of n--rbust non mistaae sets
= (B
Problem Setup. Suppose the input space can be partitioned into easy, hard, and overlapping points, Le. X' Deasy only U hard only Dvvertpp We assume that the pseudolabeler's accuracy is the same in the easy and overlapping regions (Deasy only and Doverta),, and is higher in these regions compared to the hard region only). Specifically,
have:
E = P(y(x)= + fweak (x)[;, n Deasy only) = P(y(x) + fweak (x)]S, Doverlap)
E2 = [P(((x)= + weak (x)|S; n hardd only) 2 13
We assume that 0 < S Eg 0.5. Further, denote the proportion of partitions
(easy)
P3
TP eassy easy only (S:)
Pj
(hard)
Paa hard only SS))
P = IP Doverlap S:)
(overlap)
Our goal is to show how the overlap density can make strong model perform better in pi on (robust) expansion property. Our main assumption is M' (S n Devertap, F) satisfies (c, q.7)
(hard) based
robust expansion on (Shaal n Dhard only, Sqnun Dowerlap.. ). It captures our intuition that strong model can learn something useful for hard data points from overlap data points.
In this setup, the trivial error bound obtained by perfectly mimicking the weak pseudolabeler is
err(J, y/S)) = (wi + Pi
(easy) (overtap))
E1
+ Ps 82.
(hard)
We claim that err(f, S n D Dhard only) < S2 when the expansion coefficient c- representing general- ization from overlap density hard density is large, the model error rate in the overlap density is low, and the model exhibits sufficient robustness. Consequently, the large amount of weak-to maak-to-strong generalization be attributed pi experiments.
(hard) (E2 err(f. y|S, n Drand only)) )), observed in our synthetic
Our proof follows similar structure Lang al. (2024).
Define
M. {x Ss f(x) v(*)}
E, E E S; f(x) # fwenk (x)}
U. SA
v= Rf) n., S. n Doverlap
Note that V2 U.. The following lemma shows that V, expands. Lemma D.3. Suppose an arbitrary classifier satisfies P(f(x) F fweal(x)) f not n-robust at x|S. O Dovertap) S - 61. Then, P(V.)
goood Dovertap) > q.
Proof. Suppose for a contradiction that (VV.]S Doverto) S q. Then by definition of V,,
P(V.)S ggood n Dovertap) = 1 P(V: goood Doverlap)
1 P(V; ggood n Doverlap (g0ood D Dovertap)
= 1 -P((S)) \ M,) n R2 n ggood D Dovertop sgood Devertap)
= 1 1P((MM n Sgood Duvertap) U ( n. D Doverlap)
19

---

Published as a conference paper at ICLR 2025
Fix arbitrary I Mj n Spann Syouod [week(() = y(z). Therefore, f() # fweak(z), thus a E E. Since this holds for an arbitrary E M1 n Spunn n D Doverlap, M, n s n D Doverta C E. Thus,
Dveetap. By definition of M, f() # y(æ). By definition of
P(Vilssood n Doverlap) = - IP(M, n Sg00d n Doverlap) U (5) sgood
Daveriap)
P(E, U (, 1S Devertap)
PPE, U (J) n Spood
D Dovertal S[ O Dovertap)
1-
E1
1
21
-1) (1
by assumption
9
1 -1
since 0 <1 S 0.5
Lemma D.4. Under the condition of Lemma D.3
P(U.|S Drant only) 2 cP cP.ViSs
D Doveriap)
Since M, n Doverlap; F) satisfies (c, q. 17) robust expansion on (Staal D hard only Dovertap); we have
S Sgoodd
Pi (V,, n Dhand only) 2 cIP(V.].s n Daverlap)
by the previous lemma. Also, by Lemma D.2
(V)))s) n Dhard only) 2 Pl (V,, Studl n D Dhard only))
Fix an arbitrary x E N(V).. ). By definition of (VV)), there exists x' E V, such that f(x) = f(x'). Since x' Vi U, x' E Mr thus we have that f=x = f(x') y(x'). And, y(x) y(x') since a and x' are both in S, This shows f(x) = v(x), thus x & M,, so x E U. Si Si Since was
arbitrary, ((V)) C Ug. This implies
Pe O only) 2 (VV() Shad n Dhard only);
thus
P(U Dhard only) 2 cPP(VP (Vilspod Dovertap).
We borrow the following lemma from Lang al. 2024 directly.
Lemma D.5 (Lang et al. 20244). E, C (Mr n Sgood)
U (U, Stadd.
The above lemma implies
Es n D hard only (Mc n S Sgnod
Dhard only)
(U; Sthad Dhard only).
Now state the formal version of Theorem setting 1) 0, q O, thus P(R, (f)= sgood
4. 1
and provide the proof. Theorem 4.1 obtained by O.
Deveriap)
Theorem D.1 (Formal version of Theorem
4.1 Suppose M,,SS (Soood n D F) satisfies (c, q, n)- robust expansion on (Shud n Dhand only, S Sgood Dovertap) for some c > 0 and 2 O. Consider an n-robust at x1S; 0 Doveriap) < ạ E1-
arbitrary classifier f such that P(((x) F Iweett (x)
then f satisfies the following error bound:
err(S, yS 0 Dhant S err(J, Swnak SS O D hhadd only) + E2
22 err(S, Sweak S 5good Doveriap) (S) n Donertap)
20

---

Published as a conference paper at ICLR 2025
Proof. By Lemma D.5 and using P( (S SS, O D hard only) 11 E2. have
P(E: St Daard only) 2 P Dhard ( -22) + P( n Dhard)82
goond
Applying Lemma D.4
P(E n Dard only) 2 5
D Dbard only (1 -11-2) + c Sgood
7 D Dovertap)
(1)
Applying Lemma D.4 again,
P(U:|S; n Dhard only)
- (U; n Dhard only) + (1 Sqoodd D Dhard only)
2 (V,1s( D Dovertap) (1 - ( Dhard only)
then we have
P(U.|SPoo Dhard unly) -
1
(P(UU)) n Dhard only) 0s PV D Doverlup)
E2
Combining this with U, = =SA,M
P(M n Dhard only)
= IP(U;
|S (ppood Dhard only)
1
(P(U,)Ss n Dhard oalyd - - D Dovertap)
2 1
1 52
Plugging this into D
have
P Eg S O D hard only)
2 - E2 PU 0 Dhand + 2c82P((V3|5 Doverlap)
(1 PSM 0 Dhard only) 1) 2P (V: S
D Doverlap
SS D Dbard only) )) E2 - 2CE2 n R., ( good
D Dovertap
-P(M n Diard only) )) E2 - 2CE2 (1 11-P(M, U R, Devertap)
2 (PMM n Daard only)) only))
+ (2c 1)82
2682 (P( n Dovertap)
((,, n Dovertup))
Note that err(f fweak S Dhard only) = (PEE,SS,NL hard only) and err( y/y.yyS Syarr only) ) = P(Mp1 S.n Dhard only) ). Plugging in those terms and rearranging leads to
err(f S/S; n Drand only)
I err(f, fweak n D only) ) + +11--1111111 - 22)
+ 20 y) y)So0od Dovertap) + 2c P R.,, ( 1
ggood Doverlap)
= err(f, fweak SS: ; n Dhard only) ) + (1 -2))22
+ 22ezeer(ff (f, fweek (590od Dovertop) + 2c5 2c,5 ( Doveriap)
= =err(f, fweak (S: n Dhard only) 5
-2052(1 err(f. fweak Sgood Dovertup) (f),(()))) Doveriap))
21

---

Published as a conference paper at ICLR 2025
D.2 COVERAGE EXPANSION BY OVERLAP DENSITY
Theorem D.2. Suppose (T; n Drard only F) satisfies (c, 9: -robust expansion on (S T; a
Dhant onls) for some > Fix an arbitrary classifier J X - The error of J on Tú n D hard only bounded by:
err(J, fweak Doveriap)
err(J,y(Zz Dhant) & ((BR, O Dhant only) + max
q.
c(1 - -1)
Proof. Again, the proof follows the similar steps to Lang et al. 2024). Define M, fo f(x) +
(()) n T3 n Dmard only as the set of mistakes of in T: n D hard only. and let U; M1 (,
Let E; = f-r E Si n Deverlap) } be the set of points in S; n Davertap where f disagrees with the weak labels. Since we have err(f, f. fweak| SS D overtap
P (E Sk)) and err(f.yIIz n Daadd only
(MM,TT hard only) I (PU Drard only) + (P RR, [2; D hard only) by union bound, it suffices
bound (f) n Dhard only). Since U2 (J)()), have P(N(U;) (S Doveriap) Z
(U, 5good n Dovertap) by Lemma D.2 Also, U² E (T; by definition. Then, P(U,
Dhard only) > 9 and (c, q, roobust expansion implies
(S S n Dovertap) 2 (1, Sp Dovertap) > cPP(U.]T n Dhard only).
We proceed two cases.
Case 1: PUUIT Dhard only) < g. In this case, directly obtain ear(f, y/ 1 n Dhard only) ((Mi); only) I P(Ra (D only P +P(U, only) - P (f)9T D only) ) q.
Case P(U.TT Dhard only) q. In this case, by the assumption that (Strndd Doverlap: T
Dhard only) satisfy (c, robustt expansion and (U:) n Doverlap) > cP(UU n Dhard only); we have
P(N(U)) n S
D overlap S n D Doveriap)
= -1- (PW())) n S n Doveriap)
2 (1- (1) D Phard only).
Suppose ((U.) n Spood n Dovertpp. By the definition of ((U)), there exists point x' E U
reachable from x by a good edge, such that (xx = [(x).. Then, since x Spnnd [weat(r) = y(x) =
(x²). Also, since x' MM, u(x') # f(x')= = f(r). Thus, f(x) * fweak(I)), which implies E. This leads to
fwenk (S
(EE.S 2 P(N(U.) Sii) ((U-E)) only) )
Rearranging the inequality, we have
err(f, fweak 1S; ( Doverlap)
er fTy n Drand) (F)T, O D only)
c(1 E1)
D.3 PROOF OF THEOREM 4.2
Setup
We extend the setup in Section 3
We consider label-conditioned Gaussian mixtures as
follows.
We denote mean parameters as Moverlap
Jennyy
where Phaay E Bdaay and Puhadd E Iha,
Phard
[eeasy
0
We set Heasy
Phard
to instantiate the distribution of overlap, easy-only and
Alund
hard-only data points. We set up common covariance Σ = Leasy
where Jensy and T I are
Ihard
identity matrices. The distribution input x follows Gaussian mixtures
P(xly 1) Teasy N (Measy Σ) + Thand N (Jhardd Σ) + Toverlup N (Mloverlap: E)
22

---

Published as a conference paper at ICLR 2025
P(x -1) Teaay Na- Σ) + Thard N( Mhard: Σ) + Tovertap N( -Moverlap E),
where Teasy 2 0, Ahard O, Toverlap 2 O, Teasy + Thard + Toverlap
Assuming Fly 1) 1o
11) = 0.5, Deasy only, Dhand only;
Dovertpp only can be described as
Deasy only
N(-Neasy, Σ) + N( Σ)
2
Dhard only
N(--hard, Whard 2
N(Hbard 2)
2
Doverlap
N Moverrap:: E)
(Poverlaps E)
2
2
Lemma D.6. VI- S eaT for 0 < y
11
Proof. Consider function f(v) = In( v1-y
In(1 - y)
2(- suffices to show
y
2
fly) S 0, which implies - vi-y S e z o7 by taking the exponential. First, we can derive
1
f'()) = 2(1 - y) 2(1 - y)²
2(1 - y)²
Thus, we can see (v) for < < Also, we have f(0) = -0. Then, since f(0) and f is decreasing for 0 < 1, f1y S 0.
Lemma D.7. Suppose X1 Nun,, X2 ~ Nu22 oz)) Then, X1X2 - pul2 ~ SE((2, (b),
where SE represents subexponetial with parameters v22 uřo3 + μद0 100002 b- 201
Proof. We can write
Xi 11 + 01
X₂ + 0022,
where Z1, Z2 N(0, 1). Then, -1X2-11X2111 41/222 = 11 -- Z2. Let = 2102Z2- 12201 Z1. Since A ~ (00 1Í/03 + p20?)) ), A subgaussian with variance proxy 0² = uΩo0 11307 This implies
SE(12, bA) for any ba > 0, where vAA = p3 + 1ă07. We choose ba = 221
Next, let B = 01 Zz. We can obtain MGF of B as
1
BB
V (A0102)² for |\]
01
Especially, for |^| y = (20102)2. Thus,
20102 we can bound the MGF using the inequality in Lemma D.6 with
(20102)2
Ble S exp
2(1 - (2
For [A] 20100 we have (A0102)²
1. so 1 (20102)² 1. Therefore,
1
2 (A0102)))
E < exp
By comparing it with the MGF bound for any subexponential random variable Y,
22
1 b'
E < exp
for |
we identify the subexponential parameters for as v2z = (2102)) by = 20102. Since BE),, SE bB), we have
X1X₂ Mil2 ~ SE (13 + v2. max(bax.bb)))
by the additivity of subexponential. Thus, we have
4
X, 11/2 SE(HÃO3 + 120
0 20 02)
3
23

---

Published as a conference paper at ICLR 2025
Proof of Theorem 4.2 Let Xdit
Xoverlap
Xeasy only
that
E Xoverlap
T Xhard only]
E Xeasy only
T Xhard only]
1 X Xhard only!.
This difference distribution will follow Xair
(Joovettap - Heasy only: 2cf) N( 2cI). Let
z
x (Naard only)i. Then, Xeasy only Xhard only
Ei=1 24. Since
(Xait))s ~ N ((Uhard)) 2c)
(bbard only) ) N( in c)2
8 +²²²t/0/
have 2, SE 3e (hard
4c by Lemma D.7 By additivity,
3
d
Zi ~ SE dc + 3c | 2.2 4c
Xain Xhard only
The concentration inequality then follows directly from the standard concentration inequality for subexponential distributions Wainwright 2019). We have
Searraa--aardd only easy only Xiturd only S M 122 -t) -1)) S exp (- 1-min( 2v2
12 t 20)
T P
where 2² dc + 3c ||Maard 1/ and b = 4c. By plugging in t || Mhard l can obtain the average error rate bound
| 12
|| 11
(Xiverlap Xtard only I Xeasy only Xhard only) I exp
-min de + 6e | 12
8c
D.4 PROOF OF THEBREM 4.3
Proof. Recall that o(s) = IP (Dvertt (D.) is the population overlap density of data source 8, Ōz [V([s)] is the empirical overlap density at round f,, and o* max, o(s) the optimal overlap density.
[D((s]
Define re(s) / 2lo where (s) denotes the number of times data source has been chosen up (s)
to round t. We first show that
P ((),(s) o(8) 2 rx)) S 27
Here, is a random variable, thus cannot apply Hoeffding's inequality directly. Instead, replace t with some fixed round first. Define (s(s) [s)l which represents the average overlap
[s)]
ratio the data source D, from the first rounds (j S T). Since j is fixed and ()(ss) < 1, by Hoeffding's 's inequality, we obtain
(())((s) o(s) rs)) 27
Define the event & = (Vs [K] < 7, (z, - o(s) 2 28))) Then, by the union bound, we have
K T
K T
P|
S
Σ
Σ
(1)
2 ry())) <
27 2KT -
==
==1 1=1
Thus, for the random variable ny (s). it holds that
P ((ō,(s) o(s) 2 (s)) < 27
Define the regret associated with the choice of source D, as A(s) = =0" o(s) and the contribution of data source D. to the accumulated regret at round i as R(t, s) = (s). The total regret is then given by R(()= ΣK R(I, 8) 1(0" - ō.)-
24

---

Published as a conference paper at ICLR 2025
re(s,, which is event in E According to the algorithm. (s) 2 UCBr(s*)) where s* denotes the index of the optimal source and where 8 denotes the data source chosen at round t. Trivially, we also have USB 2 o(s*). Thus, we have
Suppose (ō((s)
- o(s)
(sx)) + 2rr(s)) 2 (5t) + +r((s)) = (s:) z 2
which implies
2 2 T
= - -((x)) S 28x( -/ (s(
From this, we can obtain
K R(t)= R(t, 8)
==1
K
ns())((s)
Σ
m T/ (s)
2 2n (s) logT
K 2K v log
(s)
K
1
2K Vlog T
n((s)
Jensen's 's inequality
K
2K Vlog TV
K
=2 RogKl
We have the final result from this.
E[R(t)] = P
2TT +(+)(EE)()()
R(T) S T trivially
2T -1-220 21 222
Kt KologT
plugging in the previous result
O(v ()
It follows that
(V
El0" ōz] = B[R(T)/4 so
E EXPERIMENT DETAILS
Real datasets. In our language model experiments, we used subset of datasets in EleutherA]
20211. which includes ANLI-R2 (Nie et al.) 2020), CoLA (Warstadt et al., 2018), DREAM (Sun
et al. 2019), MC-TACO (Bnn Zhou & Roth 2019). HelleSwag (Zellers et al. 2019). MultiRC
Khashabi et al. 2018), PAWS (Zhang et al.) 2019). PICa (Yang et al. (022)). QuAIL (Rogers et al.
2020), QUARTZ (Tafjord et | "2019"), ). Social IQa Sap et al. (2019) SST2 (Socher al. 2013).
PiChpilehvaar Camacho- Camacho-Collados: 2019), Tweet Sentiment Naji (2012), Anthropic HH RLHF
(Ganguli al. 2022), SciQ (Welbl al. 2017), CosmosQA (Huang al. 2019), BoolQ Clark et al.
25

---

Published as a conference paper at ICLR 2025
2019), and the Amazon Polarity (Zhang et al. 2013) datasets. The training dataset was divided into the weak model training data, Duain and the weak-to-stront -t-snn model training data, Dw2s. We sampled Mrain 10, 000, Phat 1, 000, and Rrea 5, 000 for the training, validation, and test datasets, respectively, for datasets with larger splits than the specified sizes, in accordance with the default parameters provided in http:///ttuu..oom/lluueeeeeer.
In Wrench experiments, we used a subset of Wrench benchmark Zhang et al. 2021). which includes CDR, Census, Commercial, iMDb, Mushroom, SMS, Spambase, Tennis, Yelp, and Youtube datasets.
show dataset sizes, the sizes of detected easy-only, hard-only, and overlap sizes, and Tecontolled that is used for overlap mechanism experiments Section 5.1
Dataset sizes
Table A2
A3
Table A2: Summary of data statistics from Section 5.3.
The mean and standard deviation are calculated from 20 repeated experiments, each using different random seeds.
Dataset
Pusis
Yhao
fly2
Teaatelle
Daw mals
D
Sample size per round
amazon _aaaziry
5000
5000
1150 =
3850 105
73
anli-r2
5000
668
5000
1404 +
1734 +
1863
1404
45
72 +
anthropic_he hh
5000
5000
5000
1976 1: 62
296 1:
2729
1976
62
$4 1:
boolg
3053
2474
3053
1483 +:
598 +
922
1537 52
56
cola
2028
644
2028
568 + 45
126 + 34
442 21
1461 + 45
27 27:1
cosmos_qa
78 1
dream
2541
1984
2541
1037 + 45
261 +
777 42
1504 + 45
43
bellaswag
5000
5000
5000
1545
52
499 +
2957
1545
39 +
Iaco
2698
2458
2698
1250 1:
756 1:
1250
61
49 2
multire
5000
4150
5000
1763
1: 57
1267 1
1970
1763
1 57
66 1
paws
5000
5000
5000
663 +
1808
2529
663
$1
piqa
5000
1832
5000
1591 + 51
627 + 33
2783 26
1591
51
59
quail
4613
1:2
quartz
833
764
833
347 +
302 +
183
347 34
12 12
sciq
4837
2980
4837
2240
831 +
1767
2240
82 +
social_i_qu
5000
1888
5000
1578 1.
1.
2424
1578
51
60
sst
5000
856
5000
1876 4:
984 +:
892
3125
95 15
twiter-sentimmnn
5000
5000
+
1298
2827
98
wie
2214
638
2214
1073 +: 31
325
+: 36
813 34
1076
37
Table A3: Summary of data statistics from Section 5.3.1
The mean and standard deviation are calculated from 20 repeated experiments, each using different random seeds.
Dataset
Tuain
Rw22
Peontrolled
Deasy only
[ only|
D
cdr
4215
4673
4215
1108 +: 63
191 + 37
2916 + 67
1108 +: 63
census
5041
16281
5042
1629 = 66
280 - 69
1349 + 30
3413 - 66
commercial
32065
7496
32065
8988 + 934
2216 835
6773 - 616
23077 934
imdb
10000
2500
10000
2469 + 688
630 + 425
4885 3004
4485 + 2621
2285
500
2286
662 + 107
107
117
1507 + 113
662 107
spambase
1840
461
1840
633 + 34
102
531 + 24
1207 - 34
tennis
3479
1098
3480
754 688
680 706
77 + 40
2723 693
yelp
15200
3800
15200
5721 485
1160 +414
4934 + 1387
9106 = 1246
youtube
793
250
793
341 28
54
290 + 24
449 = 34
26

---

Published as a conference paper at ICLR 2025
Synthetic datasets. Synthetic datasets in Section 5.3 are genarated with Gaussian mixture dis-
Measy
tribution. We first sample mean parameters Moverlap
from uniform distribution, where
/haad
Measy E Ray and Phard IR
We set Measy
Measy
Phard
0 to simulate ['hard
data points with easy+hard (overlap), easy, hard patterns. Similarly, we up the covariances
Tewsy
Densy Ehard Eoverlap
hhard Leasy and Ihard being identity matrices. We used 5, deasy dhard = 20 in synthetic experiments. Labels (Y) are sampled from {-1,1} uniformly. The distribution input follows Gaussian mixtures
P(X 1) Tensy (Hensy: Deasy) ) Caand-N(Haaaaa Emard) + Woverlap N (Hoverlnp. Loverlap
= -1) Teasy N N(-Neess Measy; Eeasy) + Thard (M/Nuuuddd Emara) + Tovertap N( Moverlap Eoverlap);
where Teasy 2 O, Thard 2 0, Toverlap 2
0. Teasy + Thard + Toverlap 1. We control parameters
Teasy: Thard Toverlap to see how they affect the weak to strong generalization.
We fixed Reasy Thard 100 and increase overlap data points each time. We trained weak-to-strong model on overlap data points only.
Computing resources We used GPU cluster with 8 NVIDIA A100 SXM2 40GB HBM2 NV- LINK, 2x Intel@ Xeon Cascade Lake 5218 (2.3GHz) Processor (24-Core), 16x 32 GB ECC REG DDR4-2933 RAM.
27

---

Published as a conference paper at ICLR 2025
polarity
anli-12
anthropic
boolq
0.58
0,520
0.70
Accuraty
0.900
Accuraty
0.56
Accuracy
0.515
Accuraly
0.510
0.875
0.54
0.850
0.52
0.55
0.0
0.5
0.0
0.5
0.9
0.5
0.0
0.5
Overlap Density cola
Overlap Density
Overlap Density
Overiap Density
hellaswag
0.75
0.70
0.63
Accursty
Accurazy
0.70
Accuracy
Accuracy
0.03
0.85
0.60
0.60
0.65
0.60
0.55
0.60
0.55
0.50
0.0
0.5
0.0
0.5
0.0
0.5
1.0
0.0
0.5
Overlap Density
Overlap Density multire
Overiap Density
Overiap Density
0.80
0.58
0.70
Accuraty
0.75
Accuraty
0.75
Accurasy
Accuracy
0.54
0.70
0.60
0.65
0.50
0.0
0.5
0.0
0.5
0.0
0.5
1.0
0.0
0.5
Overlap Density
Overlap Density guartz
Overlap Density
Overlap Density
social
0.65
0.675
Accun
Accurcy
Accurcy
0.80
Accurayy
0.60
0.600
3.655
0.55
0.70
0.575
0.600
0.65
0.550
0.50
0.80
0.0
0.5
0.0
0.5
0.0
0.5
1.0
0.0
0.5
Overlap Density 5st2
Overlap Density
Overlap Density
Overlap Density
twitter sentiment
0.800
0.650
Accunry
0.85
0.750
Accuracy
0.625
0.725
0.600
0.75
0.575
0.675
0.70
0.0
0.5
10
0.0
0.5
10
0,550
0.0
0.5
1.0
Overlap Density
Overlap Density
Overlap Density
Weak
Strang
W25
Controltd W25
Figure A1: Overlap density versus performance in weak-to hard generalization with large language models. The red lines represent the accuracies of strong models trained true labels, while the blue dashed lines indicate the accuracies of weak models on the test set. The green dashed lines (Full W2S) show the accuracies of weak-to-strong models trained the entire pseudolabeled dataset. Lastly, the Controlled W2S lines represent the accuracies of strong models trained on data with a controlled proportion of overlap density. In general, the strong model's improvement over the weak model tracks the overlap proportion, suggesting that the overlap density is indeed an important mechanism for generalization.
ADDITIONAL EXPERIMENTAL RESULTS
F.1 COMPLETE RESULTS FROM SECTION
Figure AI presents the full experimental results for the 19 LLM datasets and Figure A2 presents the full experimental results for 9 weak supervision datasets in Section 5.2
28

---

Published as a conference paper at ICLR 2025
cdr
commercial
Weak
Strong
0.80
Full
0.75
Weak
Controlled W25
Strong
0.70
Weak
Controlled W25
Strong
Full W25
0.55
0.60
Controlled W25
0.0
0.2
0.6
0.8
1.0
imdb
Sms
spambase
Weak
0.75
Strong
Accuracy
0.65
0.70
Weak
Weak
0.8
Controlled ed W25
W25
0.60
Strong
Strong
0.7
0.55
Controlled W25
0.4
Controlled W25
0.6
0.8
0.2
0.2
0.6
0.8
1.0
yelp
youtube
0.8
0.70
0.6
Weak
0.65
Weak
Weak
Strong
Strong
Strong
0.60
0.4
Controlled W25
Controlled w25
Controlled W25
0.55
0.6
0.8 1.0
Overlap Density
Figure A2: Overlap density mechanism weak supervision. The lines represent accuracies strong models trained on true labels, while the blue dashed lines indicate the accuracies of weak models on the test set. The green dashed lines (Full W2S) show the accuracies of pscudolabeled dataset. Lastly, the Controlled W2S lines represent the accuracies of strong models trained on data with controlled proportion of overlap density. In many tasks, the strong model 4-layer MLP) surpasses the accuracy of the weak model (the label model) as the overlap density ratio increases. Notably, the Controlled W2S model uses less data compared to the Full WS setting to manage the overlap density proportion.
models trained on the entire
29

---

Published as a conference paper at ICLR 2025
amazon ppolarittyy Train samples
amazon_polaarty
Estimated Overlap Ratio
Train overlap samples
Estiated Overtap Ratio
0.926
UCB
0.912
0.924
Accuracy
0.70
0.910
0.922
0.65
Random
0.908
0.920
0.906
UCB
Random
20
Round
anli-r2
Estimated Overlap Ratio
Train all samples
Train overlap samples
Estimated Overlap Rabio
0.48
UCB
0.535
UCB
Random
Random
Accuracy
0.54
Accuracy
0.530
UCB
0.525
0.44
Random
0.53
0.520
0.515
5
1.0
1.5
20
25
20
25
10
15
Round
Round
anthropic hh
Estimated Overlap Ratio
Train on all samples
Train on overiap samples
Estimated Overag Ratio
0.400
0.521
0.350
0.375
UCB
Accuracy
0.518
Random
Accuracy
0.519
0.520
Random
0.325
Random
0.516
0.518
0.300
0.517
0.275
0.514
0.516
5
10
15
20
25
20
25
10
15
Round
Round di
Round
baoiq
Estimated Overiap Ratio
Train on samples
Train on overiap samples
Estimated Overiap Rabo
0.55
UCB
Accuracy
0.580
Accuracy
0.58
Random
0.575
0.45
0.570
Random
Randoo
0.56
10
20
15
20
25
10
Round
Round
Round
cola
Estimated Overiap Ratio
Train samples
Train overiap samples
Estimated Overtap Ratio
0.65
0.605
UCB
0.620
UCB
0.000
Accuracy
0.615
0.55
0.595
0.610
0.590
0.605
UCB
0.600
0.45
0.595
Round
Round
Round
Figure A3: Data selection experiments with Algorithm
F.2
COMPLETE RESULTS FROM SECTION 5.2
Figures A3
A4
A5
and
A6 present the full experimental results for the datasets discussed in
Section
5.2
30

---

Published as a conference paper at ICLR 2025
cosmos
Estimated Overlap Ratio
Train on all samples
Train on overlap samples
Estimated Overlap Ratio
UCB
0.645
0.6400
Random
Accuracy
0.6375
Accuracy
0.640
UCB
Random
0.6350
0.635
0.48
0.6325
0.630
Randoo
0.625
10
15
25
10
15
10
15
Round
Round
Round
dream Train samples
Estimated Overlap
overlap samples
EStimated Overtap Racio
0.60
UCB
0.55
Accuracy
0.57
Accuracy
0.58
UCB
Random
0.56
Rainoom
0.55
10
10
Round
Round
Round
hellaswag
Estimated Overlap Ratio
Train all samples
Train overlap samples
Estimated Overtap Rabio
0.34
0.520
UCB
0.32
0.515
Random
Accuracy
0.518
Accuracy
0.516
Random
0.28
0.514
0.505
UCB
0.512
0.500
10
15
Round
Round
Round
mc taco
Estimated Overlap Ratio
Train on all samples
Train overlap samples
Estimted Overlap Ratio
0.690
0.63
0.55
UCB
Random
0.605
Accuracy
Accuracy
0.50
0.680
0.67
0.45
0.675
UCB Random
UCB
0.40
0.670
0.66
Random
10
10
Round
Round
multirc
Estimated Overlap Ratio
Train on all samples
Train on overlap samples
Overiap Rati
0.705
Random
Edimated Overiaa
Accuracy
Accuracy
0.715
0.30
UCB
0.700
0.710
0.695
0.36
0.690
Random
5
10
15
20
25
5
10
155
20
25
5
10
15
20
Round
Round
Round
Figure A4: Data selection experiments with Algorithm T (Continued).
31

---

Published as a conference paper at ICLR 2025
Estimated Overlap Ratio
Train on all samples
Train on overlap samples
Estimated Overtap Ratio
0.62
UCB
Random
Accuracy
Accuracy
0.00
UCB
Random
0.60
0.59
0.56
Randoo
5
10
15
25
5
10
15
10
15
Round
Round
Round
piga
Estimated Overlap
Train samples
Train overlap samples
EStimated Overtap Racio
0.36
UCB
UCB
0.34
0.5225
Accuracy
0.32
0.5200
0.515
0.30
0.5175
0.510
0.28
Rainoom
0.5125
0.505
10
10
Round
Round
Round
quail
Estimated Overlap Ratio
Train all samples
Train overlap samples
Estimated Overtap Raho
UCB
0.64
Random
Accuracy
0.6225
0.40
Random
0.63
0.6175
UCB
0.62
0.6150
10
15
10
15
Round
Round
Round
quartz
Estimated Overlap Ratio
Train on all samples
Train overlap samples
Ectimated Overlap Ratio
UCB
Random
Accuracy
Accuracy
0.52
0.52
UCB
UCB
Random
Random
10
10
Round
sciq
Estimated Overlap Ratio
Train on all samples
Train on overlap samples
Overiaa Ratio
0.55
Edimated Overiap
0.50
0.70
Random
Accuracy
Accuracy
0.45
0.89
0.40
0.705
Random
Random
0.700
5
10
15
20
25
5
10
15
20
25
5
10
15
20
Round
Round
Round
Figure A5: Data selection experiments with Algorithm T (Continued).
32

---

Published as a conference paper at ICLR 2025
social Train on all samples
Estimated Overlap Ratlo
Train on overlap samples
Estiated Overtap Rabio
0.38
0.59
0.37
0.578
Accurac)
Accuracy
UCB
0.35
Random
0.574
0.57
0.34
0.572
UCB Random
UCB Random
0.570
0.32
0.55
15
10
15
20
Round
Round
Round
5st2
Estimated Overlap Ratio
Train all samples
Train overlap samples
Edimatted Overiap Ratio
0.860
0.88
0.855
0.87
Accuracy
0.850
Accuracy
0.55
UCB
0.845
Random
0.50
0.45
0.835
UCB
0.84
UCB
0.830
Round
Raund
Round
twitter-sentimenn
Estimated Overlap Ratio
Train all samples
Train overlap samples
Edtiatted Overiap Ratio
0.65
UCB
Random
UCB
Random
0.772
0.60
Accuracy
Accuracy
0.770
0.55
0.760
0.50
0.750
0.764
UCB
Random
0.45
0.745
0.762
Round
Round
Round
wic
Estimated Overlap Ratio
Train all samples
Train overiap samples
Estimated Overtap Ratio
0.61
0.54
0.590
Accuracy
UCB
0.585
0.59
0.48
0.46
0.580
0.58
UCB
Random
Random
10
25
10
5
10
15
20
Round
Round
Round
Figure A6: Data selection experiments with Algorithm I (Continued).
33

---

Published as a conference paper at ICLR 2025
0.8
0.7
0.6
Week Made
Sirong Modal W25
Easy Rotio
Hard Ratio
(a) Easy-only Density
(b) Hard-only Density
Figure A7: Ablation on the easy-only and hard-only density. Note that the y-axis represents the average accuracy across the easy, hard, and overlap data points. As expected, increasing easy-only and hard-only data points does not lead to weak- weak-to-strong generalization.
(a) Easy Accuracy
(b) Hard Accuracy
(c) Overlap Accuracy
1.0
Strong Model
W25
Weak Model
Week Model Strong
0.1
0.2
0.3 Easy Ratio
0.4
0.1
0.2
0.3
0.4
0.1
0.2
0.3 Easy Ratio
0.4
Easy Ratio
Figure A8: Accuracy in each data region easy-only data controlled synthetic experiments. As expected, increasing the number of easy-only data points does not improve the accuracy of W2S model hard-only data points (middle).
(a) Easy Accuracy
Accuracy
Overlap Accuracy
Week Model
Strong Model
0.5
W25
0.6
Weak Mocel
Weak Model
0.4
Strong Model
Strong Modil
w25
6.1
0.2
0.3
0'4
Figure A9: Accuracy in each data region in hard-onlydata controlled synthetic experiments. As expected, increasing the number of hard-only data points does not improve the performance of the W2S model due to the high error rate of pseudolabels in hard-only data points.
F.3 SYNTHETIC EXPERIMENT ON EASY-ONLY AND HARD-ONLY DENSITY
To demonstrate that overlap density is essential for weak-to-strong generalization, we perform an ablation study focusing on easy-only and hard-only densities. We hypothesize that easy-only and hard-only points do not lead to weak-to-strong generalization.
Setup. We follow the experimental setup described in Section 5.3.1 with modifications to the number of easy-only, hard-only, and overlap data points. In the easy-only ratio ablation, we train the weak-to-strong model exclusively on easy-only points. We fix the number of hard-only points 100 and overlap points at 10, then incrementally add 5 easy-only points at each step. Similarly, in the hard-only ratio ablation, we train the model exclusively on hard-only points, with the number of easy-only points fixed at 100 and overlap points at 10, while adding 5 hard-only points at each step.
Figure A7 presents the average accuracy results in ablation experiments, and Figure A8 A9 show the decomposed views of the accuracy. The results indicate that increasing the number of easy-only points fails to achieve weak-to-strong generalization, these points do not contribute
Results.
34

---

Published as a conference paper at ICLR 2025
information to the hard-only data region, shown in Figure A8 (middle). Meanwhile, increasing the number of hard-only points also fails, as the severe label noise impairs the learning of the weak-to- model.
35

---

Published as a conference paper at ICLR 2025
Mixed noise
Easy noise
Hard noise
0.9
Weak Model
Strong Model
W25 0.00
W25 Is 0.13
W25
Accuracy
W25 [e 0.3)
0.7
Weak Model
Weak Model
Strong Model
Strong Model
0.6
W25 0.0)
W25 0.0)
W25 0.31
W25 is- 0.1)
0.5
W25 (e 0.2)
W25 (2 0.21
W25 (c=
W25 0.3)
0.0
0.0
0.1
Overlap Ratio
Overlap Ratio
Overlap Ratio
Figure A10: Average accuracy for each noise type.
Easy noise
(a) Easy Accuracy
(b) Hard Accuracy
(c) Overlap Accuracy
0.9
Accuracy
0.8
0.7
Weak Model
Model
Model
Strong Model
Strong Model
Strong Model
W25 (c- 0.0)
W2S (c - 0.0)
W2S (r- 0.0)
W25 0.1)
W25 0.1)
0.5
W25 (e 0.2)
W25 (e 0.2)
W25 (e 0,2)
0.3)
0.3)
(e 0.3)
0.0
Overlap Ratio
Overlap Ratio
Overlap Ratio
Figure A11: Accuracy in each data region for the easy noise type (NI).
Hard noise
(a) Easy Accuracy
(b) Hard Accuracy
(c) Overlap Accuracy
1.0
Weak Model
Strong Model W25
W25 0.1)
Accuracy
W25 0.2)
W25 00.))
Weak Model
Weak Model
Strong Model
Strong Model
0.6
W25 (c= 0.0)
W25 (e= 0.0)
W25
W25 0.13
0.5
W25 (e= 0.2)
W25 (c 0.2)
0.4
W25 (r 0.3)
W25 (r 0.3)
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
Overlap Ratio
Overlap Ratio
Overlap Ratio
Figure A12: Accuracy in each data region for the hard noise type (N2).
F.4 SYNTHETIC EXPERIMENT ON THE NOISE IN OVERLAP DETECTION
trained weak-to teak-to-strong model exclusively on overlap data points, under the assumption that our overlap detection algorithm is perfect. However, in practice, the overlap detection algorithm may introduce noise. In this section, we investigate the impact of noisy overlap detection on model performance in a fully controllabel experiment setup.
In the main synthetic experiment in Section 5.3
Setup. The experimental setup follows the description in Section 5.3.1 with specific modifications to the weak-to-strong model's training data points. We examine three noise scenarios characterized
36

---

Published as a conference paper at ICLR 2025
Mixed noise
(a) Easy Accuracy
(b) Hard Accuracy
(c) Overlap Accuracy
1,0
Weak Model
Strong Model
W25 0.0)
W25 0.3)
Accuracy
W25 0.21
W25 0033)
Weak Model
Weak Model
Strong Model
Strong Model
0.0)
0.0)
W25 0.11
W2S (e 0.1)
0.5
W25 (e- 0.2)
W25 0.2)
W25 (c=
W25 (e= 0.3)
0.0
0.0
Overlap Ratio
Overtap Ratio
Overlap Ratio
Figure A13: Accuracy in each data region for the hard noise type (N3).
by the overlap detection error rate c. These scenarios are as follows: (1) Mixed noise: Half of the errors select easy-only points, and the other half select hard-only points; (2) Easy noise: All errors select easy-only points; (3) Hard noise: All errors select hard-only points. The number of data points in the weak-to-strong model training
is similarly distributed as before. Starting with Neasy = 100, Ahard 500, Roverlap 10, we increment Roverlap by 10 each time. Accordingly, the weak-to-strong model's 's training data is derived from the following distributions:
(NI) Easy noise:
e/loveriap easy points + (1 Hoverlap overlap points
(N2) Hard noise:
efloverlap hard points + Pooertap overlap points
eovverap
Cnooerlap hard points + (1 - <) overlap points
(N3) Mixed noise:
easy points
+
2
Results. Figure A10 presents the overall accuracy for each noise type, while Figure All A12 A13
show the decomposed accuracy for each noise type. We can observe Mixed noise and hard noise deteriorates data efficiency on overlap ratio as expected. Hard noise, purely adding randomly labeled hard points, significantly drops data efficiency of overlap data points. Interestingly, while easy noise has minimal impact at low error rates, it significantly degrades performance when the error rate is high (e 0.3). This degradation is due the model assigning higher weights easy features under high easy noise conditions, leading the weak-to-strop to-sn model to over-rely on these features at high error rates.
37

---

Published as a conference paper at ICLR 2025
census
commercial
0.85
Strong
0.80
0.94
Full W25
Controlled
0.75
Strong
0.60
Full W25
Weak
Controlled W25
0.90
Strong
0.55
0.65
Controlled W25
0.60
0.88
0.0
0.4
0.6
0.8
1.0
imdb
5m5
spambase
1.0
0.95
0.90
Accuracy
0.70
Strong
W25
0.65
Full W25
Strong
0.7
Full W25
Strong
0.80
Contralled
Controlled
Controlled W25
0.75
0.4
0.6
tennis
yelp
youtube
0.875
0.75
Strong
0.85
Full w25
0.850
0.70
0.825
0.800
Strong
W25
0.65
0.70
Strong
Full W25
0.775
Controlled W25
0.60
Controlled W2s
Overlap Density
Figure A14:
Overlap density mechanism weak supervision with XGBoost as the weak so-ssong model. The red lines represent the accuracies of strong models trained on true labels, while the blue dashed lines indicate the accuracies of weak models the test set. The green dashed lines (Full W2S) show the accuracies of weak-to-strong models trained the entire pseudolabeled dataset. Lastly, the Controlled W2S lines represent accuracies strong models trained on data with a controlled proportion of overlap density.
F.5 OVERLAP DENSITY MECHANISM WITHOUT NEURAL NETWORKS
One might assume that the overlap density mechanism is primarily feature of deep neural network architectures, given that our experiments mainly use deep neural networks as strong models. While deep neural networks offer useful representations, we demonstrate that the overlap density mechanism can also be shown even without the use of neural networks.
Setup. We adopt the same weak supervision experiment setup as in Section 5.1 raw inputs for the overlap detection algorithm and XGBoost (Chen & Guestrin 2016) the strong model.
except that we use
Results. Figure A14 presents the experimental results. Although the outcomes appear noisier due to the less powerful representations, which lead to a noisier overlap detection algorithm, we can still observe that the overlap density mechanism effective- improvememesosseess in the weak-to-strong model correspond with increases in overlap density.
38

---

Published as a conference paper at ICLR 2025
cdr
census
commercial
0.85
Strong
0.80
Full W25
Contralled
0.75
Strong
0.60
0.70
Full W25
Weak
Controlled w25
Strong
0.55
0.65
Controlled W25
0.50
1.0
Sms
spambase
0.75
0.95
0.70
0.8
Accuracy
0.65
0.85
Strong
Full W25
0.60
Strong
Strong
Controll W25
0.55
Full W25
Controlled
Controlled
Full W25
0.75
tennis
yelp
youtube
0.75
Strong
W2S
Controlled
0.6
Strong
0.60
Strong
Full W25
0.6
Full W25
0.4
Controlled
0.55
Controlled w2s
Overlap Density
Figure A15: Overlap density mechanism in weak supervision with XGBoost as the weak-to to stron model and transferred overlap points from 4-layer ReLU networks. The red lines represent the accuracies of strong models trained true labels, while the blue dashed lines indicate the accuracics of weak models the test The green dashed lines (Full W2S) show the accuracies of weak-to-strong models trained the entire pseudolabeled dataset. Lastly, Controlled W2S lines represent accuracies strong models trained on data with controlled proportion of overlap density.
F.6 TRANSFERABILITY OF DETECTED OVERLAP DENSITY
Since overlap detection relies on the model's representation, one might assume that overlap points are model-dependent different weak models and weak-to -to-strong models would have different overlap points. However, we hypothesize that the overlap property a latent property of data and therefore the detected overlap points are transferable across models.
Setup. We use the same setup as in Section 5. except that overlap/non-overlap points are detected using a 4-layer DNN trained on pseudolabels in Dwss- and then the weak-to-strooe to-soong model evaluation is performed with XGBoost after training it on Dw2s
Results. Figure A13 shows the experimental results. We can observe a similar trend to that in Section 5.1
supporting our hypothesis.
39


Reviews:
[{"review_id": "yWNFoNj3Lb", "reviewer": "Reviewer_YoBV", "summary": "The paper discusses weak-to-strong generalization, the process by which a large capacity model is trained using pseudo-labels generated by the predictions of a smaller model.\nThe goal is to have the final model achieve better performance than what would have been obtained by simply training on the available ground truth labels, or by the weaker models.\n\nA hypothesis is raised regarding the mechanism that facilitates this type of generalization. Namely, it is hypothesized that there are two types of patterns associated with the label, \"easy\" ones that the smaller model can learn and \"hard\" ones that it cannot.\nThe hypothesis is then that examples in the dataset which contain both easy and hard patterns, form an overlap between the examples that the weak model can classify successfully and those that the stronger model can classify using the hard patterns.\nPseudo-labels for this overlap set then help the larger model leverage the hard patterns learn them and classify examples that do not contain easy patterns.\n\nBased on this hypothesis, a method for selection of data for pseudo-labelling is proposed, and some formal results are given to show upper bounds on error that depend on the amount of overlap, and for motivating the proposed sample selection methods using a toy problem with Gaussian data. In experiments, the improvements due to larger overlap and how the sample selection method can be used to induce larger overlap, are demonstrated by linear probing of LLMs on a variety of datasets, and on the proposed toy problem.", "questions": "In figure 2, is there a reason that different datasets are presented for each regime (low, medium and high), instead of showing 2 datasets through all regimes? Since the amount of overlap is induced by selection, I'd imagine this would give a more apples-to-apples comparison of the regimes.\n\nMinor comments:\nIn definition 1, what does $\\mathcal{N}(U)$ denote? Is it simple supposed to be $U$?\nLine 278: information -> informal\nLines 248-249: \"while easy-only points lack are not\"\nLine 312: what's $\\tilde{x}$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper touches upon an important problem and raises an original, interesting and intuitive hypothesis. The writing is conveys the contributions of the paper clearly, and the findings seem significant, even though I am not an expert on this topic so I am not entirely sure what are the appropriate baselines.\nFinally, I also like that the authors reasoned formally about the empirical phenomenon and method.", "weaknesses": "I think that the paper covers a lot of material at the expense of some details that would've made the argument more precise and convincing.\n\n1) The result in Theorem 4.1 makes sense in terms of being an upper bound on the error we are concerned with, but I could not see immediately whether the bound is very loose or not. For instance, it looks like if $f_{weak}$ preforms poorly on on $S_i \\cap D_{hard only}$, then an accurate $f_{w2s}$ means the term on the RHS should be very large (since the disagreement with $f_{weak}$ on this set is large) and the bound becomes vacuous. A better explanation for the significance of this bound would be much appreciated. The example given for a scenario where the bound reduces to the disagreement between $f_{w2s}$ and $f_{weak}$ on the hard-only examples is nice, but still the right hand side can be very large and in we also expect it to be large when $f_{w2s}$ gives a significant improvement. Hence, seems like this bound also has the property of becoming loose when the error of $f_{w2s}$ becomes smaller.\n\nSince the result here relies on a paper from Lang et al. 2024 that is an arXiv paper and readers in ICLR may have not had the time to read and appreciate yet, I think that such clarifications are even more important.\n\n2) It is unclear how the hyperparameters $\\tau_{\\text{hard}}$ and $\\tau_{\\text{overlap}}$ are selected.\n\n3) For the experiments, I did not see why the results convey that the improved performance indeed comes from succeeding on \"hard-only\" examples, and not just from better generalization to overlap examples. A study that shows this more fine-grained analysis, and how accuracy depends on $\\tau_{\\text{hard}}$ and $\\tau_{\\text{overlap}}$ would be appreciated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "d2LyPhdJQI", "reviewer": "Reviewer_5BLm", "summary": "The paper provides a notion of data overlap to describe the process of weak-to-strong generalization, which occurs when one uses pseudo labels from a “weak” model to train a “strong” model to achieve better performance. The paper presents a theoretical analysis of the error of the strong model and provides experiments on both language modeling tasks and weak supervision tasks.", "questions": "1. The paper talks about focusing on improving generalization but does not clearly define what this means. In line 88, the paper mentions, “we seek to understand what aspects of data result in stronger performance,” but it does not define what “performance” means here. In line 141, the paper mentions, “how can we prioritize sources that lead to the greatest generalization?”\n\n   Are we measuring performance on test points drawn from the same distribution as the training data, or something else? It would be helpful to define “performance” or “generalization” clearly early on. Furthermore, the paper discusses using overlap detection to improve learning from multiple datasets, making the notion of performance even less clear.\n\n2. The terms “easy pattern” and “hard pattern” are rather informal and somewhat vague. The assumptions about easy and hard patterns, which force $x_{\\text{easy}}$ and $x_{\\text{hard}}$ to be zero in lines 177–182, seem very strong.\n\n3. Typo in line 154: “Dw2s” , w2s is in the subscript ?\n\n4. Some important assumptions are not clearly stated in the paper and are instead embedded within paragraphs. For example, the assumption in lines 242–250 seems very important.\n\n   It would be helpful if the paper could reorganize and clarify what crucial assumptions are needed.\n\n5. Typo in line 290: “$\\text{err}(f_{w2s}, y \\dots)$” to “$\\text{err}(f_{w2s}, f_{\\text{weak}} \\dots)$” ?\n\n6. Is there any experiment that verifies that the strong model only learns hard patterns?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The theoretical results seem correct to me (though I did not go through the appendix), and the experiments are comprehensive, illustrating that the results described in the paper also hold in practice.", "weaknesses": "My main concern is the clarity of the writing. I found it hard to understand the paper when reading it, due to the use of some terms without proper definitions (see questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5sbXrAnPFr", "reviewer": "Reviewer_enrk", "summary": "This work focuses on the weak-to-strong (W2S) generalisation mechanism, focusing on making an agent with strong generalisation ability to learn under the supervision of a weak agent, a paradigm of interest, eg, in the context of superalignment for LLMs. While W2S generalisation is already well studied from an algorithmic perspective, little work has been made on the intrinsic structures in data that allow W2S generalisation to be made . This work is then a step in this direction, authors propose and discuss the notion of $\\emph{overlap}$ which consists of data containing both weak patterns (usable by the weak agent) and strong ones (only exploitable by the strong agent). Such a structure is meaningful as those points allow the strong agent to learn from the weak ones and beyond. Authors propose algorithms to characterise, recognise and select overlapping data. Then, then propose a short theoretical analysis of their results and show that real-life dataset may contain overlapping data and that those data may explain the W2S generalisation phenomenon.", "questions": "- l.155 $f_{strong}$ is not defined, do you mean $f_{w2s}$?\n- About theorem 4.1: can we reasonably hope for $c$ to be greater than $0.5$ in practice? Is there a way to estimate it? It seems that this condition is the key to kill the impact of  $\\varepsilon_2$ . More generally is there a way to detect whether a data distribution satisfies a $(c,q)$ expansion? \n- As acknowledged by authors, the data model $x= [x_{easy},x_{hard}]$ is unlikely to be verified in practice, what is the justification to focus on such a particular case then?\n- Although it is not about weak to strong generalisation, the idea of selecting data wrt relevant information already appeared recently in statistical learning. In [1,2], authors derived the Pick 2 Learn (P2L) algorithm, which compress the available dataset in order to maintain the major part of relevant information while strongly decreasing the dataset size. I suggest you to briefly discuss this to provide more perspective in your work. \n- Is it possible to use simply algorithm 2 in a learning setting where you have only 1 dataset? Does it lead to good performance?\n- In Algorithm 2, you fix your hard and overlap threshold yourself. How do you choose them?  \n- At the beginning of page 4 I remark that having two patterns (weak and strong) leads to 4 subsets to partition data, if we add multiple level of overlapping as suggested in your conclusion, this may result in a exploding number of subsets to partition data.  Would it be a problem to adapt both the algorithms and theoretical results?\n\nBiblio: \n[1] Compression, generalization and learning. Campi et al. 2023, Journal of Machine Learning Research\n[2] The Pick-to-Learn Algorithm: Empowering Compression for Tight Generalization Bounds and Improved Post-training Performance, Paccagnan et al. NeuriPS 2023", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, as a non-expert of W2S generalisation, goals are clearly stated and the notion of overlap, while hand-wavy, is well explained.\n- The empirical study is very complete and shows both relevance and limitation of the current approach of overlapping with only two distinguishable patterns.\n- Theoretical result are various and justify why overlapping and the proposed algorithms should be considered.", "weaknesses": "See Questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a9yF4UwqCh", "reviewer": "Reviewer_3AtN", "summary": "The weak-to-strong generalization in this paper refers to the phenomenon that strong model can generalize better on the unseen data (or say hard patterns) than the weak model, even only being trained on supervision (e.g. pseudolabel) obtained from weak model. To solve the challenge, this paper proposes a data-centric mechanism, named overlap density, to characterize weak-to-strong generalization ability, provide an overlap detection algorithm to find the points with high overlap density from one data source, and then leverage them to facilitate learning among multiple source of data. This paper further provides theoretical analysis and empirical experiments to demonstrate the effectiveness of the proposed overlap density and overlap detection algorithm.", "questions": "(1)\tCan you give more theoretical explanations for why the regret bound in Theorem 4.3 is $O(\\sqrt{\\log{T}/t})$, not $O(\\sqrt{\\log{t}/t})$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1)\tThis paper provides a novel and practical data-centric mechanism, overlap density, to measure what aspects of data enable weak-to-strong empirical performance.\n\n(2)\tThe proposed overlap detection algorithm (i.e. Algorithm 2) is new for me, and particularly, is simple and practical in real-life applications. Besides, using UCB algorithm to choose the data source with the highest overlap density is also of high interest.\n\n(3)\tThe proposed error bound in Theorem 4.1 directly reveals the influence of overlap density and error rate in estimating the correct overlap density to the weak-to-strong generalization ability of strong model.\n\n(4)\tThe concentration inequality in Theorem 4.2 theoretically demonstrates with high probability, the Algorithm 2 (i.e. overlap detection algorithm) can select truly overlap dataset, which truly makes sense. The regret bound in theorem 4.3 also guarantees the asymptotic performance of Algorithm 1.\n\n(5)\tThe experiments are also extensive, and in my opinion truly validate the effectiveness of the proposed mechanism from an empirical view.\n\nOverall, I find this paper is novel. The proposed overlap density mechanism, the overlap detection algorithm, the theoretical guarantees for the proposed mechanism and algorithms, as well as the extensive experiments, form a full story. I check the proof as possible as I can, and I think it is sound.", "weaknesses": "(1)\tThe major weakness is that many important notations, in both the main paper and the appendix, lack clear explanations. For example, the most important concept proposed in this work is the so-called overlap density, then where is the formal definition (or say mathematical definition) of it? I could not find such rigorous definition until I read line 16 in Algorithm A1 in appendix. I believe the formal definition of such mechanism should be depicted very clearly in the main paper. Besides, in pseudo code of Algorithm 1, the upper confidence bound of overlap density should be explained clearly in both Algorithm 1 and the main paper, instead of deferring it into Algorithm A1, because it is very important in UCB algorithm and truly help readers to understand what pseudocode means.\n\n(2)\tIf I understand correctly, the confidence scores in step 5 of Algorithm 2 lack clear explanations either. There is no explanations for how to compute it in the main paper.\n\n\n(3)\tThe adversarial robustness assumption mentioned in Theorem 4.1 should at best be listed in the main paper (although its definition is a little lengthy), or at least should be clearly pointed out in which part of Appendix such definition locates.\n\n(4)\tThe mathematic definition of the empirical overlap ratio and optimal overlap density should be given before Theorem 4.3.\n\n\n(5)\tin Definition 1, what does $\\mathcal{N}$ mean? Neighbor? Should be explained.\n\n(6)\tIn Theorem 4.3, the regret bound is of $O(\\sqrt{K\\log{T}/t})$, not the common forms of $O(\\sqrt{K\\log{t}/t})$. This means that Algorithm 1 could not achieve a vanishing regret in the first $\\log{T}$ rounds. What is the insightful reason for it? Can we improve this regret upper bound?\n\nMinor:\n\n(7)\tLine 21, leverage it -> leverage them\n\n(8)\tLine 22 densityand\n\n(9)\tLine 154, Dw2s\n\n(10)\tLine 224 in Algorithm 2, $\\tau$ -> $\\tau _{hard}$\n\n(11)\tLine 295, addiitional\n\n(12)\tLine 846, WWe\n\n(13)\tLine 854, is $f _{weak}(y)(x)$ a typo?\n\n(14)\tLine 1097, lack left parenthesis.\n\n(15)\tLine 1220, $o(s)$ lacks formal definition.\n\n(16)\tLine 1248, $R(t,a)$ -> $R(t,s)$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)